Annotation of embedaddon/php/Zend/zend_hash.c, revision 1.1
1.1 ! misho 1: /*
! 2: +----------------------------------------------------------------------+
! 3: | Zend Engine |
! 4: +----------------------------------------------------------------------+
! 5: | Copyright (c) 1998-2012 Zend Technologies Ltd. (http://www.zend.com) |
! 6: +----------------------------------------------------------------------+
! 7: | This source file is subject to version 2.00 of the Zend license, |
! 8: | that is bundled with this package in the file LICENSE, and is |
! 9: | available through the world-wide-web at the following url: |
! 10: | http://www.zend.com/license/2_00.txt. |
! 11: | If you did not receive a copy of the Zend license and are unable to |
! 12: | obtain it through the world-wide-web, please send a note to |
! 13: | license@zend.com so we can mail you a copy immediately. |
! 14: +----------------------------------------------------------------------+
! 15: | Authors: Andi Gutmans <andi@zend.com> |
! 16: | Zeev Suraski <zeev@zend.com> |
! 17: +----------------------------------------------------------------------+
! 18: */
! 19:
! 20: /* $Id: zend_hash.c 321634 2012-01-01 13:15:04Z felipe $ */
! 21:
! 22: #include "zend.h"
! 23: #include "zend_compile.h"
! 24:
! 25: #define CONNECT_TO_BUCKET_DLLIST(element, list_head) \
! 26: (element)->pNext = (list_head); \
! 27: (element)->pLast = NULL; \
! 28: if ((element)->pNext) { \
! 29: (element)->pNext->pLast = (element); \
! 30: }
! 31:
! 32: #define CONNECT_TO_GLOBAL_DLLIST(element, ht) \
! 33: (element)->pListLast = (ht)->pListTail; \
! 34: (ht)->pListTail = (element); \
! 35: (element)->pListNext = NULL; \
! 36: if ((element)->pListLast != NULL) { \
! 37: (element)->pListLast->pListNext = (element); \
! 38: } \
! 39: if (!(ht)->pListHead) { \
! 40: (ht)->pListHead = (element); \
! 41: } \
! 42: if ((ht)->pInternalPointer == NULL) { \
! 43: (ht)->pInternalPointer = (element); \
! 44: }
! 45:
! 46: #if ZEND_DEBUG
! 47: #define HT_OK 0
! 48: #define HT_IS_DESTROYING 1
! 49: #define HT_DESTROYED 2
! 50: #define HT_CLEANING 3
! 51:
! 52: static void _zend_is_inconsistent(const HashTable *ht, const char *file, int line)
! 53: {
! 54: if (ht->inconsistent==HT_OK) {
! 55: return;
! 56: }
! 57: switch (ht->inconsistent) {
! 58: case HT_IS_DESTROYING:
! 59: zend_output_debug_string(1, "%s(%d) : ht=%p is being destroyed", file, line, ht);
! 60: break;
! 61: case HT_DESTROYED:
! 62: zend_output_debug_string(1, "%s(%d) : ht=%p is already destroyed", file, line, ht);
! 63: break;
! 64: case HT_CLEANING:
! 65: zend_output_debug_string(1, "%s(%d) : ht=%p is being cleaned", file, line, ht);
! 66: break;
! 67: default:
! 68: zend_output_debug_string(1, "%s(%d) : ht=%p is inconsistent", file, line, ht);
! 69: break;
! 70: }
! 71: zend_bailout();
! 72: }
! 73: #define IS_CONSISTENT(a) _zend_is_inconsistent(a, __FILE__, __LINE__);
! 74: #define SET_INCONSISTENT(n) ht->inconsistent = n;
! 75: #else
! 76: #define IS_CONSISTENT(a)
! 77: #define SET_INCONSISTENT(n)
! 78: #endif
! 79:
! 80: #define HASH_PROTECT_RECURSION(ht) \
! 81: if ((ht)->bApplyProtection) { \
! 82: if ((ht)->nApplyCount++ >= 3) { \
! 83: zend_error(E_ERROR, "Nesting level too deep - recursive dependency?"); \
! 84: } \
! 85: }
! 86:
! 87:
! 88: #define HASH_UNPROTECT_RECURSION(ht) \
! 89: if ((ht)->bApplyProtection) { \
! 90: (ht)->nApplyCount--; \
! 91: }
! 92:
! 93:
! 94: #define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \
! 95: if ((ht)->nNumOfElements > (ht)->nTableSize) { \
! 96: zend_hash_do_resize(ht); \
! 97: }
! 98:
! 99: static int zend_hash_do_resize(HashTable *ht);
! 100:
! 101: ZEND_API ulong zend_hash_func(const char *arKey, uint nKeyLength)
! 102: {
! 103: return zend_inline_hash_func(arKey, nKeyLength);
! 104: }
! 105:
! 106:
! 107: #define UPDATE_DATA(ht, p, pData, nDataSize) \
! 108: if (nDataSize == sizeof(void*)) { \
! 109: if ((p)->pData != &(p)->pDataPtr) { \
! 110: pefree_rel((p)->pData, (ht)->persistent); \
! 111: } \
! 112: memcpy(&(p)->pDataPtr, pData, sizeof(void *)); \
! 113: (p)->pData = &(p)->pDataPtr; \
! 114: } else { \
! 115: if ((p)->pData == &(p)->pDataPtr) { \
! 116: (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent); \
! 117: (p)->pDataPtr=NULL; \
! 118: } else { \
! 119: (p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent); \
! 120: /* (p)->pDataPtr is already NULL so no need to initialize it */ \
! 121: } \
! 122: memcpy((p)->pData, pData, nDataSize); \
! 123: }
! 124:
! 125: #define INIT_DATA(ht, p, pData, nDataSize); \
! 126: if (nDataSize == sizeof(void*)) { \
! 127: memcpy(&(p)->pDataPtr, pData, sizeof(void *)); \
! 128: (p)->pData = &(p)->pDataPtr; \
! 129: } else { \
! 130: (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);\
! 131: if (!(p)->pData) { \
! 132: pefree_rel(p, (ht)->persistent); \
! 133: return FAILURE; \
! 134: } \
! 135: memcpy((p)->pData, pData, nDataSize); \
! 136: (p)->pDataPtr=NULL; \
! 137: }
! 138:
! 139:
! 140: #if SUHOSIN_PATCH
! 141: #ifdef ZTS
! 142: static MUTEX_T zend_hash_dprot_mx_reader;
! 143: static MUTEX_T zend_hash_dprot_mx_writer;
! 144: static unsigned int zend_hash_dprot_reader;
! 145: #endif
! 146: static unsigned int zend_hash_dprot_counter;
! 147: static unsigned int zend_hash_dprot_curmax;
! 148: static dtor_func_t *zend_hash_dprot_table = NULL;
! 149:
! 150: static void zend_hash_dprot_begin_read()
! 151: {
! 152: #ifdef ZTS
! 153: tsrm_mutex_lock(zend_hash_dprot_mx_reader);
! 154: if ((++(zend_hash_dprot_reader)) == 1) {
! 155: tsrm_mutex_lock(zend_hash_dprot_mx_writer);
! 156: }
! 157: tsrm_mutex_unlock(zend_hash_dprot_mx_reader);
! 158: #endif
! 159: }
! 160:
! 161: static void zend_hash_dprot_end_read()
! 162: {
! 163: #ifdef ZTS
! 164: tsrm_mutex_lock(zend_hash_dprot_mx_reader);
! 165: if ((--(zend_hash_dprot_reader)) == 0) {
! 166: tsrm_mutex_unlock(zend_hash_dprot_mx_writer);
! 167: }
! 168: tsrm_mutex_unlock(zend_hash_dprot_mx_reader);
! 169: #endif
! 170: }
! 171:
! 172: static void zend_hash_dprot_begin_write()
! 173: {
! 174: #ifdef ZTS
! 175: tsrm_mutex_lock(zend_hash_dprot_mx_writer);
! 176: #endif
! 177: }
! 178:
! 179: static void zend_hash_dprot_end_write()
! 180: {
! 181: #ifdef ZTS
! 182: tsrm_mutex_unlock(zend_hash_dprot_mx_writer);
! 183: #endif
! 184: }
! 185:
! 186: /*ZEND_API void zend_hash_dprot_dtor()
! 187: {
! 188: #ifdef ZTS
! 189: tsrm_mutex_free(zend_hash_dprot_mx_reader);
! 190: tsrm_mutex_free(zend_hash_dprot_mx_writer);
! 191: #endif
! 192: free(zend_hash_dprot_table);
! 193: }*/
! 194:
! 195: static void zend_hash_add_destructor(dtor_func_t pDestructor)
! 196: {
! 197: int left, right, mid;
! 198: zend_bool found = 0;
! 199: unsigned long value;
! 200:
! 201: if (pDestructor == NULL || pDestructor == ZVAL_PTR_DTOR || pDestructor == ZVAL_INTERNAL_PTR_DTOR
! 202: || pDestructor == ZEND_FUNCTION_DTOR || pDestructor == ZEND_CLASS_DTOR) {
! 203: return;
! 204: }
! 205:
! 206: if (zend_hash_dprot_table == NULL) {
! 207: #ifdef ZTS
! 208: zend_hash_dprot_mx_reader = tsrm_mutex_alloc();
! 209: zend_hash_dprot_mx_writer = tsrm_mutex_alloc();
! 210: zend_hash_dprot_reader = 0;
! 211: #endif
! 212: zend_hash_dprot_counter = 0;
! 213: zend_hash_dprot_curmax = 256;
! 214: zend_hash_dprot_table = (dtor_func_t *) malloc(256 * sizeof(dtor_func_t));
! 215: }
! 216:
! 217: zend_hash_dprot_begin_write();
! 218:
! 219: if (zend_hash_dprot_counter == 0) {
! 220: zend_hash_dprot_counter++;
! 221: zend_hash_dprot_table[0] = pDestructor;
! 222: } else {
! 223: value = (unsigned long) pDestructor;
! 224: left = 0;
! 225: right = zend_hash_dprot_counter-1;
! 226: mid = 0;
! 227:
! 228: while (left < right) {
! 229: mid = (right - left) >> 1;
! 230: mid += left;
! 231: if ((unsigned long)zend_hash_dprot_table[mid] == value) {
! 232: found = 1;
! 233: break;
! 234: }
! 235: if (value < (unsigned long)zend_hash_dprot_table[mid]) {
! 236: right = mid-1;
! 237: } else {
! 238: left = mid+1;
! 239: }
! 240: }
! 241: if ((unsigned long)zend_hash_dprot_table[left] == value) {
! 242: found = 1;
! 243: }
! 244:
! 245: if (!found) {
! 246:
! 247: if (zend_hash_dprot_counter >= zend_hash_dprot_curmax) {
! 248: zend_hash_dprot_curmax += 256;
! 249: zend_hash_dprot_table = (dtor_func_t *) realloc(zend_hash_dprot_table, zend_hash_dprot_curmax * sizeof(dtor_func_t));
! 250: }
! 251:
! 252: if ((unsigned long)zend_hash_dprot_table[left] < value) {
! 253: memmove(zend_hash_dprot_table+left+2, zend_hash_dprot_table+left+1, (zend_hash_dprot_counter-left-1)*sizeof(dtor_func_t));
! 254: zend_hash_dprot_table[left+1] = pDestructor;
! 255: } else {
! 256: memmove(zend_hash_dprot_table+left+1, zend_hash_dprot_table+left, (zend_hash_dprot_counter-left)*sizeof(dtor_func_t));
! 257: zend_hash_dprot_table[left] = pDestructor;
! 258: }
! 259:
! 260: zend_hash_dprot_counter++;
! 261: }
! 262: }
! 263:
! 264: zend_hash_dprot_end_write();
! 265: }
! 266:
! 267: static void zend_hash_check_destructor(dtor_func_t pDestructor)
! 268: {
! 269: unsigned long value;
! 270:
! 271: if (pDestructor == NULL || pDestructor == ZVAL_PTR_DTOR || pDestructor == ZVAL_INTERNAL_PTR_DTOR
! 272: #ifdef ZEND_ENGINE_2
! 273: || pDestructor == suhosin_zend_destroy_property_info_internal || pDestructor == suhosin_zend_destroy_property_info
! 274: #endif
! 275: || pDestructor == ZEND_FUNCTION_DTOR || pDestructor == ZEND_CLASS_DTOR) {
! 276: return;
! 277: }
! 278:
! 279: zend_hash_dprot_begin_read();
! 280:
! 281: if (zend_hash_dprot_counter > 0) {
! 282: int left, right, mid;
! 283: zend_bool found = 0;
! 284:
! 285: value = (unsigned long) pDestructor;
! 286: left = 0;
! 287: right = zend_hash_dprot_counter-1;
! 288:
! 289: while (left < right) {
! 290: mid = (right - left) >> 1;
! 291: mid += left;
! 292: if ((unsigned long)zend_hash_dprot_table[mid] == value) {
! 293: found = 1;
! 294: break;
! 295: }
! 296: if (value < (unsigned long)zend_hash_dprot_table[mid]) {
! 297: right = mid-1;
! 298: } else {
! 299: left = mid+1;
! 300: }
! 301: }
! 302: if ((unsigned long)zend_hash_dprot_table[left] == value) {
! 303: found = 1;
! 304: }
! 305:
! 306: if (!found) {
! 307: zend_hash_dprot_end_read();
! 308:
! 309: zend_suhosin_log(S_MEMORY, "possible memory corruption detected - unknown Hashtable destructor");
! 310: if (SUHOSIN_CONFIG(SUHOSIN_HT_IGNORE_INVALID_DESTRUCTOR) == 0) {
! 311: _exit(1);
! 312: }
! 313: return;
! 314: }
! 315:
! 316: } else {
! 317: zend_hash_dprot_end_read();
! 318:
! 319: zend_suhosin_log(S_MEMORY, "possible memory corruption detected - unknown Hashtable destructor");
! 320: if (SUHOSIN_CONFIG(SUHOSIN_HT_IGNORE_INVALID_DESTRUCTOR) == 0) {
! 321: _exit(1);
! 322: }
! 323: return;
! 324: }
! 325:
! 326: zend_hash_dprot_end_read();
! 327: }
! 328:
! 329: #else
! 330: #define zend_hash_add_destructor(pDestructor) do {} while(0)
! 331: #define zend_hash_check_destructor(pDestructor) do {} while(0)
! 332: #endif
! 333:
! 334: ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
! 335: {
! 336: uint i = 3;
! 337: Bucket **tmp;
! 338:
! 339: SET_INCONSISTENT(HT_OK);
! 340:
! 341: if (nSize >= 0x80000000) {
! 342: /* prevent overflow */
! 343: ht->nTableSize = 0x80000000;
! 344: } else {
! 345: while ((1U << i) < nSize) {
! 346: i++;
! 347: }
! 348: ht->nTableSize = 1 << i;
! 349: }
! 350:
! 351: ht->nTableMask = ht->nTableSize - 1;
! 352: ht->pDestructor = pDestructor;
! 353: zend_hash_add_destructor(pDestructor);
! 354: ht->arBuckets = NULL;
! 355: ht->pListHead = NULL;
! 356: ht->pListTail = NULL;
! 357: ht->nNumOfElements = 0;
! 358: ht->nNextFreeElement = 0;
! 359: ht->pInternalPointer = NULL;
! 360: ht->persistent = persistent;
! 361: ht->nApplyCount = 0;
! 362: ht->bApplyProtection = 1;
! 363:
! 364: /* Uses ecalloc() so that Bucket* == NULL */
! 365: if (persistent) {
! 366: tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *));
! 367: if (!tmp) {
! 368: return FAILURE;
! 369: }
! 370: ht->arBuckets = tmp;
! 371: } else {
! 372: tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket *));
! 373: if (tmp) {
! 374: ht->arBuckets = tmp;
! 375: }
! 376: }
! 377:
! 378: return SUCCESS;
! 379: }
! 380:
! 381:
! 382: ZEND_API int _zend_hash_init_ex(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent, zend_bool bApplyProtection ZEND_FILE_LINE_DC)
! 383: {
! 384: int retval = _zend_hash_init(ht, nSize, pHashFunction, pDestructor, persistent ZEND_FILE_LINE_CC);
! 385:
! 386: ht->bApplyProtection = bApplyProtection;
! 387: return retval;
! 388: }
! 389:
! 390:
! 391: ZEND_API void zend_hash_set_apply_protection(HashTable *ht, zend_bool bApplyProtection)
! 392: {
! 393: ht->bApplyProtection = bApplyProtection;
! 394: }
! 395:
! 396:
! 397:
! 398: ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
! 399: {
! 400: ulong h;
! 401: uint nIndex;
! 402: Bucket *p;
! 403:
! 404: IS_CONSISTENT(ht);
! 405:
! 406: if (nKeyLength <= 0) {
! 407: #if ZEND_DEBUG
! 408: ZEND_PUTS("zend_hash_update: Can't put in empty key\n");
! 409: #endif
! 410: return FAILURE;
! 411: }
! 412:
! 413: h = zend_inline_hash_func(arKey, nKeyLength);
! 414: nIndex = h & ht->nTableMask;
! 415:
! 416: p = ht->arBuckets[nIndex];
! 417: while (p != NULL) {
! 418: if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
! 419: if (!memcmp(p->arKey, arKey, nKeyLength)) {
! 420: if (flag & HASH_ADD) {
! 421: return FAILURE;
! 422: }
! 423: HANDLE_BLOCK_INTERRUPTIONS();
! 424: #if ZEND_DEBUG
! 425: if (p->pData == pData) {
! 426: ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n");
! 427: HANDLE_UNBLOCK_INTERRUPTIONS();
! 428: return FAILURE;
! 429: }
! 430: #endif
! 431: zend_hash_check_destructor(ht->pDestructor);
! 432: if (ht->pDestructor) {
! 433: ht->pDestructor(p->pData);
! 434: }
! 435: UPDATE_DATA(ht, p, pData, nDataSize);
! 436: if (pDest) {
! 437: *pDest = p->pData;
! 438: }
! 439: HANDLE_UNBLOCK_INTERRUPTIONS();
! 440: return SUCCESS;
! 441: }
! 442: }
! 443: p = p->pNext;
! 444: }
! 445:
! 446: p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
! 447: if (!p) {
! 448: return FAILURE;
! 449: }
! 450: memcpy(p->arKey, arKey, nKeyLength);
! 451: p->nKeyLength = nKeyLength;
! 452: INIT_DATA(ht, p, pData, nDataSize);
! 453: p->h = h;
! 454: CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
! 455: if (pDest) {
! 456: *pDest = p->pData;
! 457: }
! 458:
! 459: HANDLE_BLOCK_INTERRUPTIONS();
! 460: CONNECT_TO_GLOBAL_DLLIST(p, ht);
! 461: ht->arBuckets[nIndex] = p;
! 462: HANDLE_UNBLOCK_INTERRUPTIONS();
! 463:
! 464: ht->nNumOfElements++;
! 465: ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */
! 466: return SUCCESS;
! 467: }
! 468:
! 469: ZEND_API int _zend_hash_quick_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
! 470: {
! 471: uint nIndex;
! 472: Bucket *p;
! 473:
! 474: IS_CONSISTENT(ht);
! 475:
! 476: if (nKeyLength == 0) {
! 477: return zend_hash_index_update(ht, h, pData, nDataSize, pDest);
! 478: }
! 479:
! 480: nIndex = h & ht->nTableMask;
! 481:
! 482: p = ht->arBuckets[nIndex];
! 483: while (p != NULL) {
! 484: if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
! 485: if (!memcmp(p->arKey, arKey, nKeyLength)) {
! 486: if (flag & HASH_ADD) {
! 487: return FAILURE;
! 488: }
! 489: HANDLE_BLOCK_INTERRUPTIONS();
! 490: #if ZEND_DEBUG
! 491: if (p->pData == pData) {
! 492: ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n");
! 493: HANDLE_UNBLOCK_INTERRUPTIONS();
! 494: return FAILURE;
! 495: }
! 496: #endif
! 497: zend_hash_check_destructor(ht->pDestructor);
! 498: if (ht->pDestructor) {
! 499: ht->pDestructor(p->pData);
! 500: }
! 501: UPDATE_DATA(ht, p, pData, nDataSize);
! 502: if (pDest) {
! 503: *pDest = p->pData;
! 504: }
! 505: HANDLE_UNBLOCK_INTERRUPTIONS();
! 506: return SUCCESS;
! 507: }
! 508: }
! 509: p = p->pNext;
! 510: }
! 511:
! 512: p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
! 513: if (!p) {
! 514: return FAILURE;
! 515: }
! 516:
! 517: memcpy(p->arKey, arKey, nKeyLength);
! 518: p->nKeyLength = nKeyLength;
! 519: INIT_DATA(ht, p, pData, nDataSize);
! 520: p->h = h;
! 521:
! 522: CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
! 523:
! 524: if (pDest) {
! 525: *pDest = p->pData;
! 526: }
! 527:
! 528: HANDLE_BLOCK_INTERRUPTIONS();
! 529: ht->arBuckets[nIndex] = p;
! 530: CONNECT_TO_GLOBAL_DLLIST(p, ht);
! 531: HANDLE_UNBLOCK_INTERRUPTIONS();
! 532:
! 533: ht->nNumOfElements++;
! 534: ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */
! 535: return SUCCESS;
! 536: }
! 537:
! 538:
! 539: ZEND_API int zend_hash_add_empty_element(HashTable *ht, const char *arKey, uint nKeyLength)
! 540: {
! 541: void *dummy = (void *) 1;
! 542:
! 543: return zend_hash_add(ht, arKey, nKeyLength, &dummy, sizeof(void *), NULL);
! 544: }
! 545:
! 546:
! 547: ZEND_API int _zend_hash_index_update_or_next_insert(HashTable *ht, ulong h, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
! 548: {
! 549: uint nIndex;
! 550: Bucket *p;
! 551:
! 552: IS_CONSISTENT(ht);
! 553:
! 554: if (flag & HASH_NEXT_INSERT) {
! 555: h = ht->nNextFreeElement;
! 556: }
! 557: nIndex = h & ht->nTableMask;
! 558:
! 559: p = ht->arBuckets[nIndex];
! 560: while (p != NULL) {
! 561: if ((p->nKeyLength == 0) && (p->h == h)) {
! 562: if (flag & HASH_NEXT_INSERT || flag & HASH_ADD) {
! 563: return FAILURE;
! 564: }
! 565: HANDLE_BLOCK_INTERRUPTIONS();
! 566: #if ZEND_DEBUG
! 567: if (p->pData == pData) {
! 568: ZEND_PUTS("Fatal error in zend_hash_index_update: p->pData == pData\n");
! 569: HANDLE_UNBLOCK_INTERRUPTIONS();
! 570: return FAILURE;
! 571: }
! 572: #endif
! 573: zend_hash_check_destructor(ht->pDestructor);
! 574: if (ht->pDestructor) {
! 575: ht->pDestructor(p->pData);
! 576: }
! 577: UPDATE_DATA(ht, p, pData, nDataSize);
! 578: HANDLE_UNBLOCK_INTERRUPTIONS();
! 579: if ((long)h >= (long)ht->nNextFreeElement) {
! 580: ht->nNextFreeElement = h < LONG_MAX ? h + 1 : LONG_MAX;
! 581: }
! 582: if (pDest) {
! 583: *pDest = p->pData;
! 584: }
! 585: return SUCCESS;
! 586: }
! 587: p = p->pNext;
! 588: }
! 589: p = (Bucket *) pemalloc_rel(sizeof(Bucket) - 1, ht->persistent);
! 590: if (!p) {
! 591: return FAILURE;
! 592: }
! 593: p->nKeyLength = 0; /* Numeric indices are marked by making the nKeyLength == 0 */
! 594: p->h = h;
! 595: INIT_DATA(ht, p, pData, nDataSize);
! 596: if (pDest) {
! 597: *pDest = p->pData;
! 598: }
! 599:
! 600: CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
! 601:
! 602: HANDLE_BLOCK_INTERRUPTIONS();
! 603: ht->arBuckets[nIndex] = p;
! 604: CONNECT_TO_GLOBAL_DLLIST(p, ht);
! 605: HANDLE_UNBLOCK_INTERRUPTIONS();
! 606:
! 607: if ((long)h >= (long)ht->nNextFreeElement) {
! 608: ht->nNextFreeElement = h < LONG_MAX ? h + 1 : LONG_MAX;
! 609: }
! 610: ht->nNumOfElements++;
! 611: ZEND_HASH_IF_FULL_DO_RESIZE(ht);
! 612: return SUCCESS;
! 613: }
! 614:
! 615:
! 616: static int zend_hash_do_resize(HashTable *ht)
! 617: {
! 618: Bucket **t;
! 619:
! 620: IS_CONSISTENT(ht);
! 621:
! 622: if ((ht->nTableSize << 1) > 0) { /* Let's double the table size */
! 623: t = (Bucket **) perealloc_recoverable(ht->arBuckets, (ht->nTableSize << 1) * sizeof(Bucket *), ht->persistent);
! 624: if (t) {
! 625: HANDLE_BLOCK_INTERRUPTIONS();
! 626: ht->arBuckets = t;
! 627: ht->nTableSize = (ht->nTableSize << 1);
! 628: ht->nTableMask = ht->nTableSize - 1;
! 629: zend_hash_rehash(ht);
! 630: HANDLE_UNBLOCK_INTERRUPTIONS();
! 631: return SUCCESS;
! 632: }
! 633: return FAILURE;
! 634: }
! 635: return SUCCESS;
! 636: }
! 637:
! 638: ZEND_API int zend_hash_rehash(HashTable *ht)
! 639: {
! 640: Bucket *p;
! 641: uint nIndex;
! 642:
! 643: IS_CONSISTENT(ht);
! 644:
! 645: memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
! 646: p = ht->pListHead;
! 647: while (p != NULL) {
! 648: nIndex = p->h & ht->nTableMask;
! 649: CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
! 650: ht->arBuckets[nIndex] = p;
! 651: p = p->pListNext;
! 652: }
! 653: return SUCCESS;
! 654: }
! 655:
! 656: ZEND_API int zend_hash_del_key_or_index(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, int flag)
! 657: {
! 658: uint nIndex;
! 659: Bucket *p;
! 660:
! 661: IS_CONSISTENT(ht);
! 662:
! 663: if (flag == HASH_DEL_KEY) {
! 664: h = zend_inline_hash_func(arKey, nKeyLength);
! 665: }
! 666: nIndex = h & ht->nTableMask;
! 667:
! 668: p = ht->arBuckets[nIndex];
! 669: while (p != NULL) {
! 670: if ((p->h == h)
! 671: && (p->nKeyLength == nKeyLength)
! 672: && ((p->nKeyLength == 0) /* Numeric index (short circuits the memcmp() check) */
! 673: || !memcmp(p->arKey, arKey, nKeyLength))) { /* String index */
! 674: HANDLE_BLOCK_INTERRUPTIONS();
! 675: if (p == ht->arBuckets[nIndex]) {
! 676: ht->arBuckets[nIndex] = p->pNext;
! 677: } else {
! 678: p->pLast->pNext = p->pNext;
! 679: }
! 680: if (p->pNext) {
! 681: p->pNext->pLast = p->pLast;
! 682: }
! 683: if (p->pListLast != NULL) {
! 684: p->pListLast->pListNext = p->pListNext;
! 685: } else {
! 686: /* Deleting the head of the list */
! 687: ht->pListHead = p->pListNext;
! 688: }
! 689: if (p->pListNext != NULL) {
! 690: p->pListNext->pListLast = p->pListLast;
! 691: } else {
! 692: ht->pListTail = p->pListLast;
! 693: }
! 694: if (ht->pInternalPointer == p) {
! 695: ht->pInternalPointer = p->pListNext;
! 696: }
! 697: zend_hash_check_destructor(ht->pDestructor);
! 698: if (ht->pDestructor) {
! 699: ht->pDestructor(p->pData);
! 700: }
! 701: if (p->pData != &p->pDataPtr) {
! 702: pefree(p->pData, ht->persistent);
! 703: }
! 704: pefree(p, ht->persistent);
! 705: HANDLE_UNBLOCK_INTERRUPTIONS();
! 706: ht->nNumOfElements--;
! 707: return SUCCESS;
! 708: }
! 709: p = p->pNext;
! 710: }
! 711: return FAILURE;
! 712: }
! 713:
! 714:
! 715: ZEND_API void zend_hash_destroy(HashTable *ht)
! 716: {
! 717: Bucket *p, *q;
! 718:
! 719: IS_CONSISTENT(ht);
! 720:
! 721: SET_INCONSISTENT(HT_IS_DESTROYING);
! 722:
! 723: p = ht->pListHead;
! 724: zend_hash_check_destructor(ht->pDestructor);
! 725: while (p != NULL) {
! 726: q = p;
! 727: p = p->pListNext;
! 728: if (ht->pDestructor) {
! 729: ht->pDestructor(q->pData);
! 730: }
! 731: if (q->pData != &q->pDataPtr) {
! 732: pefree(q->pData, ht->persistent);
! 733: }
! 734: pefree(q, ht->persistent);
! 735: }
! 736: pefree(ht->arBuckets, ht->persistent);
! 737:
! 738: SET_INCONSISTENT(HT_DESTROYED);
! 739: }
! 740:
! 741:
! 742: ZEND_API void zend_hash_clean(HashTable *ht)
! 743: {
! 744: Bucket *p, *q;
! 745:
! 746: IS_CONSISTENT(ht);
! 747:
! 748: p = ht->pListHead;
! 749:
! 750: memset(ht->arBuckets, 0, ht->nTableSize*sizeof(Bucket *));
! 751: ht->pListHead = NULL;
! 752: ht->pListTail = NULL;
! 753: ht->nNumOfElements = 0;
! 754: ht->nNextFreeElement = 0;
! 755: ht->pInternalPointer = NULL;
! 756:
! 757: zend_hash_check_destructor(ht->pDestructor);
! 758: while (p != NULL) {
! 759: q = p;
! 760: p = p->pListNext;
! 761: if (ht->pDestructor) {
! 762: ht->pDestructor(q->pData);
! 763: }
! 764: if (q->pData != &q->pDataPtr) {
! 765: pefree(q->pData, ht->persistent);
! 766: }
! 767: pefree(q, ht->persistent);
! 768: }
! 769: }
! 770:
! 771: /* This function is used by the various apply() functions.
! 772: * It deletes the passed bucket, and returns the address of the
! 773: * next bucket. The hash *may* be altered during that time, the
! 774: * returned value will still be valid.
! 775: */
! 776: static Bucket *zend_hash_apply_deleter(HashTable *ht, Bucket *p)
! 777: {
! 778: Bucket *retval;
! 779:
! 780: HANDLE_BLOCK_INTERRUPTIONS();
! 781: if (p->pLast) {
! 782: p->pLast->pNext = p->pNext;
! 783: } else {
! 784: uint nIndex;
! 785:
! 786: nIndex = p->h & ht->nTableMask;
! 787: ht->arBuckets[nIndex] = p->pNext;
! 788: }
! 789: if (p->pNext) {
! 790: p->pNext->pLast = p->pLast;
! 791: } else {
! 792: /* Nothing to do as this list doesn't have a tail */
! 793: }
! 794:
! 795: if (p->pListLast != NULL) {
! 796: p->pListLast->pListNext = p->pListNext;
! 797: } else {
! 798: /* Deleting the head of the list */
! 799: ht->pListHead = p->pListNext;
! 800: }
! 801: if (p->pListNext != NULL) {
! 802: p->pListNext->pListLast = p->pListLast;
! 803: } else {
! 804: ht->pListTail = p->pListLast;
! 805: }
! 806: if (ht->pInternalPointer == p) {
! 807: ht->pInternalPointer = p->pListNext;
! 808: }
! 809: ht->nNumOfElements--;
! 810: HANDLE_UNBLOCK_INTERRUPTIONS();
! 811:
! 812: zend_hash_check_destructor(ht->pDestructor);
! 813: if (ht->pDestructor) {
! 814: ht->pDestructor(p->pData);
! 815: }
! 816: if (p->pData != &p->pDataPtr) {
! 817: pefree(p->pData, ht->persistent);
! 818: }
! 819: retval = p->pListNext;
! 820: pefree(p, ht->persistent);
! 821:
! 822: return retval;
! 823: }
! 824:
! 825:
! 826: ZEND_API void zend_hash_graceful_destroy(HashTable *ht)
! 827: {
! 828: Bucket *p;
! 829:
! 830: IS_CONSISTENT(ht);
! 831:
! 832: p = ht->pListHead;
! 833: zend_hash_check_destructor(ht->pDestructor);
! 834: while (p != NULL) {
! 835: p = zend_hash_apply_deleter(ht, p);
! 836: }
! 837: pefree(ht->arBuckets, ht->persistent);
! 838:
! 839: SET_INCONSISTENT(HT_DESTROYED);
! 840: }
! 841:
! 842: ZEND_API void zend_hash_graceful_reverse_destroy(HashTable *ht)
! 843: {
! 844: Bucket *p;
! 845:
! 846: IS_CONSISTENT(ht);
! 847:
! 848: p = ht->pListTail;
! 849: while (p != NULL) {
! 850: zend_hash_apply_deleter(ht, p);
! 851: p = ht->pListTail;
! 852: }
! 853:
! 854: pefree(ht->arBuckets, ht->persistent);
! 855:
! 856: SET_INCONSISTENT(HT_DESTROYED);
! 857: }
! 858:
! 859: /* This is used to recurse elements and selectively delete certain entries
! 860: * from a hashtable. apply_func() receives the data and decides if the entry
! 861: * should be deleted or recursion should be stopped. The following three
! 862: * return codes are possible:
! 863: * ZEND_HASH_APPLY_KEEP - continue
! 864: * ZEND_HASH_APPLY_STOP - stop iteration
! 865: * ZEND_HASH_APPLY_REMOVE - delete the element, combineable with the former
! 866: */
! 867:
! 868: ZEND_API void zend_hash_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC)
! 869: {
! 870: Bucket *p;
! 871:
! 872: IS_CONSISTENT(ht);
! 873:
! 874: HASH_PROTECT_RECURSION(ht);
! 875: p = ht->pListHead;
! 876: while (p != NULL) {
! 877: int result = apply_func(p->pData TSRMLS_CC);
! 878:
! 879: if (result & ZEND_HASH_APPLY_REMOVE) {
! 880: p = zend_hash_apply_deleter(ht, p);
! 881: } else {
! 882: p = p->pListNext;
! 883: }
! 884: if (result & ZEND_HASH_APPLY_STOP) {
! 885: break;
! 886: }
! 887: }
! 888: HASH_UNPROTECT_RECURSION(ht);
! 889: }
! 890:
! 891:
! 892: ZEND_API void zend_hash_apply_with_argument(HashTable *ht, apply_func_arg_t apply_func, void *argument TSRMLS_DC)
! 893: {
! 894: Bucket *p;
! 895:
! 896: IS_CONSISTENT(ht);
! 897:
! 898: HASH_PROTECT_RECURSION(ht);
! 899: p = ht->pListHead;
! 900: while (p != NULL) {
! 901: int result = apply_func(p->pData, argument TSRMLS_CC);
! 902:
! 903: if (result & ZEND_HASH_APPLY_REMOVE) {
! 904: p = zend_hash_apply_deleter(ht, p);
! 905: } else {
! 906: p = p->pListNext;
! 907: }
! 908: if (result & ZEND_HASH_APPLY_STOP) {
! 909: break;
! 910: }
! 911: }
! 912: HASH_UNPROTECT_RECURSION(ht);
! 913: }
! 914:
! 915:
! 916: ZEND_API void zend_hash_apply_with_arguments(HashTable *ht TSRMLS_DC, apply_func_args_t apply_func, int num_args, ...)
! 917: {
! 918: Bucket *p;
! 919: va_list args;
! 920: zend_hash_key hash_key;
! 921:
! 922: IS_CONSISTENT(ht);
! 923:
! 924: HASH_PROTECT_RECURSION(ht);
! 925:
! 926: p = ht->pListHead;
! 927: while (p != NULL) {
! 928: int result;
! 929: va_start(args, num_args);
! 930: hash_key.arKey = p->arKey;
! 931: hash_key.nKeyLength = p->nKeyLength;
! 932: hash_key.h = p->h;
! 933: result = apply_func(p->pData TSRMLS_CC, num_args, args, &hash_key);
! 934:
! 935: if (result & ZEND_HASH_APPLY_REMOVE) {
! 936: p = zend_hash_apply_deleter(ht, p);
! 937: } else {
! 938: p = p->pListNext;
! 939: }
! 940: if (result & ZEND_HASH_APPLY_STOP) {
! 941: va_end(args);
! 942: break;
! 943: }
! 944: va_end(args);
! 945: }
! 946:
! 947: HASH_UNPROTECT_RECURSION(ht);
! 948: }
! 949:
! 950:
! 951: ZEND_API void zend_hash_reverse_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC)
! 952: {
! 953: Bucket *p, *q;
! 954:
! 955: IS_CONSISTENT(ht);
! 956:
! 957: HASH_PROTECT_RECURSION(ht);
! 958: p = ht->pListTail;
! 959: while (p != NULL) {
! 960: int result = apply_func(p->pData TSRMLS_CC);
! 961:
! 962: q = p;
! 963: p = p->pListLast;
! 964: if (result & ZEND_HASH_APPLY_REMOVE) {
! 965: zend_hash_apply_deleter(ht, q);
! 966: }
! 967: if (result & ZEND_HASH_APPLY_STOP) {
! 968: break;
! 969: }
! 970: }
! 971: HASH_UNPROTECT_RECURSION(ht);
! 972: }
! 973:
! 974:
! 975: ZEND_API void zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size)
! 976: {
! 977: Bucket *p;
! 978: void *new_entry;
! 979: zend_bool setTargetPointer;
! 980:
! 981: IS_CONSISTENT(source);
! 982: IS_CONSISTENT(target);
! 983:
! 984: setTargetPointer = !target->pInternalPointer;
! 985: p = source->pListHead;
! 986: while (p) {
! 987: if (setTargetPointer && source->pInternalPointer == p) {
! 988: target->pInternalPointer = NULL;
! 989: }
! 990: if (p->nKeyLength) {
! 991: zend_hash_quick_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &new_entry);
! 992: } else {
! 993: zend_hash_index_update(target, p->h, p->pData, size, &new_entry);
! 994: }
! 995: if (pCopyConstructor) {
! 996: pCopyConstructor(new_entry);
! 997: }
! 998: p = p->pListNext;
! 999: }
! 1000: if (!target->pInternalPointer) {
! 1001: target->pInternalPointer = target->pListHead;
! 1002: }
! 1003: }
! 1004:
! 1005:
! 1006: ZEND_API void _zend_hash_merge(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size, int overwrite ZEND_FILE_LINE_DC)
! 1007: {
! 1008: Bucket *p;
! 1009: void *t;
! 1010: int mode = (overwrite?HASH_UPDATE:HASH_ADD);
! 1011:
! 1012: IS_CONSISTENT(source);
! 1013: IS_CONSISTENT(target);
! 1014:
! 1015: p = source->pListHead;
! 1016: while (p) {
! 1017: if (p->nKeyLength>0) {
! 1018: if (_zend_hash_quick_add_or_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &t, mode ZEND_FILE_LINE_RELAY_CC)==SUCCESS && pCopyConstructor) {
! 1019: pCopyConstructor(t);
! 1020: }
! 1021: } else {
! 1022: if ((mode==HASH_UPDATE || !zend_hash_index_exists(target, p->h)) && zend_hash_index_update(target, p->h, p->pData, size, &t)==SUCCESS && pCopyConstructor) {
! 1023: pCopyConstructor(t);
! 1024: }
! 1025: }
! 1026: p = p->pListNext;
! 1027: }
! 1028: target->pInternalPointer = target->pListHead;
! 1029: }
! 1030:
! 1031:
! 1032: static zend_bool zend_hash_replace_checker_wrapper(HashTable *target, void *source_data, Bucket *p, void *pParam, merge_checker_func_t merge_checker_func)
! 1033: {
! 1034: zend_hash_key hash_key;
! 1035:
! 1036: hash_key.arKey = p->arKey;
! 1037: hash_key.nKeyLength = p->nKeyLength;
! 1038: hash_key.h = p->h;
! 1039: return merge_checker_func(target, source_data, &hash_key, pParam);
! 1040: }
! 1041:
! 1042:
! 1043: ZEND_API void zend_hash_merge_ex(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, uint size, merge_checker_func_t pMergeSource, void *pParam)
! 1044: {
! 1045: Bucket *p;
! 1046: void *t;
! 1047:
! 1048: IS_CONSISTENT(source);
! 1049: IS_CONSISTENT(target);
! 1050:
! 1051: p = source->pListHead;
! 1052: while (p) {
! 1053: if (zend_hash_replace_checker_wrapper(target, p->pData, p, pParam, pMergeSource)) {
! 1054: if (zend_hash_quick_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &t)==SUCCESS && pCopyConstructor) {
! 1055: pCopyConstructor(t);
! 1056: }
! 1057: }
! 1058: p = p->pListNext;
! 1059: }
! 1060: target->pInternalPointer = target->pListHead;
! 1061: }
! 1062:
! 1063:
! 1064: ZEND_API ulong zend_get_hash_value(const char *arKey, uint nKeyLength)
! 1065: {
! 1066: return zend_inline_hash_func(arKey, nKeyLength);
! 1067: }
! 1068:
! 1069:
! 1070: /* Returns SUCCESS if found and FAILURE if not. The pointer to the
! 1071: * data is returned in pData. The reason is that there's no reason
! 1072: * someone using the hash table might not want to have NULL data
! 1073: */
! 1074: ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData)
! 1075: {
! 1076: ulong h;
! 1077: uint nIndex;
! 1078: Bucket *p;
! 1079:
! 1080: IS_CONSISTENT(ht);
! 1081:
! 1082: h = zend_inline_hash_func(arKey, nKeyLength);
! 1083: nIndex = h & ht->nTableMask;
! 1084:
! 1085: p = ht->arBuckets[nIndex];
! 1086: while (p != NULL) {
! 1087: if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
! 1088: if (!memcmp(p->arKey, arKey, nKeyLength)) {
! 1089: *pData = p->pData;
! 1090: return SUCCESS;
! 1091: }
! 1092: }
! 1093: p = p->pNext;
! 1094: }
! 1095: return FAILURE;
! 1096: }
! 1097:
! 1098:
! 1099: ZEND_API int zend_hash_quick_find(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h, void **pData)
! 1100: {
! 1101: uint nIndex;
! 1102: Bucket *p;
! 1103:
! 1104: if (nKeyLength==0) {
! 1105: return zend_hash_index_find(ht, h, pData);
! 1106: }
! 1107:
! 1108: IS_CONSISTENT(ht);
! 1109:
! 1110: nIndex = h & ht->nTableMask;
! 1111:
! 1112: p = ht->arBuckets[nIndex];
! 1113: while (p != NULL) {
! 1114: if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
! 1115: if (!memcmp(p->arKey, arKey, nKeyLength)) {
! 1116: *pData = p->pData;
! 1117: return SUCCESS;
! 1118: }
! 1119: }
! 1120: p = p->pNext;
! 1121: }
! 1122: return FAILURE;
! 1123: }
! 1124:
! 1125:
! 1126: ZEND_API int zend_hash_exists(const HashTable *ht, const char *arKey, uint nKeyLength)
! 1127: {
! 1128: ulong h;
! 1129: uint nIndex;
! 1130: Bucket *p;
! 1131:
! 1132: IS_CONSISTENT(ht);
! 1133:
! 1134: h = zend_inline_hash_func(arKey, nKeyLength);
! 1135: nIndex = h & ht->nTableMask;
! 1136:
! 1137: p = ht->arBuckets[nIndex];
! 1138: while (p != NULL) {
! 1139: if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
! 1140: if (!memcmp(p->arKey, arKey, nKeyLength)) {
! 1141: return 1;
! 1142: }
! 1143: }
! 1144: p = p->pNext;
! 1145: }
! 1146: return 0;
! 1147: }
! 1148:
! 1149:
! 1150: ZEND_API int zend_hash_quick_exists(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h)
! 1151: {
! 1152: uint nIndex;
! 1153: Bucket *p;
! 1154:
! 1155: if (nKeyLength==0) {
! 1156: return zend_hash_index_exists(ht, h);
! 1157: }
! 1158:
! 1159: IS_CONSISTENT(ht);
! 1160:
! 1161: nIndex = h & ht->nTableMask;
! 1162:
! 1163: p = ht->arBuckets[nIndex];
! 1164: while (p != NULL) {
! 1165: if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
! 1166: if (!memcmp(p->arKey, arKey, nKeyLength)) {
! 1167: return 1;
! 1168: }
! 1169: }
! 1170: p = p->pNext;
! 1171: }
! 1172: return 0;
! 1173:
! 1174: }
! 1175:
! 1176:
! 1177: ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData)
! 1178: {
! 1179: uint nIndex;
! 1180: Bucket *p;
! 1181:
! 1182: IS_CONSISTENT(ht);
! 1183:
! 1184: nIndex = h & ht->nTableMask;
! 1185:
! 1186: p = ht->arBuckets[nIndex];
! 1187: while (p != NULL) {
! 1188: if ((p->h == h) && (p->nKeyLength == 0)) {
! 1189: *pData = p->pData;
! 1190: return SUCCESS;
! 1191: }
! 1192: p = p->pNext;
! 1193: }
! 1194: return FAILURE;
! 1195: }
! 1196:
! 1197:
! 1198: ZEND_API int zend_hash_index_exists(const HashTable *ht, ulong h)
! 1199: {
! 1200: uint nIndex;
! 1201: Bucket *p;
! 1202:
! 1203: IS_CONSISTENT(ht);
! 1204:
! 1205: nIndex = h & ht->nTableMask;
! 1206:
! 1207: p = ht->arBuckets[nIndex];
! 1208: while (p != NULL) {
! 1209: if ((p->h == h) && (p->nKeyLength == 0)) {
! 1210: return 1;
! 1211: }
! 1212: p = p->pNext;
! 1213: }
! 1214: return 0;
! 1215: }
! 1216:
! 1217:
! 1218: ZEND_API int zend_hash_num_elements(const HashTable *ht)
! 1219: {
! 1220: IS_CONSISTENT(ht);
! 1221:
! 1222: return ht->nNumOfElements;
! 1223: }
! 1224:
! 1225:
! 1226: ZEND_API int zend_hash_get_pointer(const HashTable *ht, HashPointer *ptr)
! 1227: {
! 1228: ptr->pos = ht->pInternalPointer;
! 1229: if (ht->pInternalPointer) {
! 1230: ptr->h = ht->pInternalPointer->h;
! 1231: return 1;
! 1232: } else {
! 1233: ptr->h = 0;
! 1234: return 0;
! 1235: }
! 1236: }
! 1237:
! 1238: ZEND_API int zend_hash_set_pointer(HashTable *ht, const HashPointer *ptr)
! 1239: {
! 1240: if (ptr->pos == NULL) {
! 1241: ht->pInternalPointer = NULL;
! 1242: } else if (ht->pInternalPointer != ptr->pos) {
! 1243: Bucket *p;
! 1244:
! 1245: IS_CONSISTENT(ht);
! 1246: p = ht->arBuckets[ptr->h & ht->nTableMask];
! 1247: while (p != NULL) {
! 1248: if (p == ptr->pos) {
! 1249: ht->pInternalPointer = p;
! 1250: return 1;
! 1251: }
! 1252: p = p->pNext;
! 1253: }
! 1254: return 0;
! 1255: }
! 1256: return 1;
! 1257: }
! 1258:
! 1259: ZEND_API void zend_hash_internal_pointer_reset_ex(HashTable *ht, HashPosition *pos)
! 1260: {
! 1261: IS_CONSISTENT(ht);
! 1262:
! 1263: if (pos)
! 1264: *pos = ht->pListHead;
! 1265: else
! 1266: ht->pInternalPointer = ht->pListHead;
! 1267: }
! 1268:
! 1269:
! 1270: /* This function will be extremely optimized by remembering
! 1271: * the end of the list
! 1272: */
! 1273: ZEND_API void zend_hash_internal_pointer_end_ex(HashTable *ht, HashPosition *pos)
! 1274: {
! 1275: IS_CONSISTENT(ht);
! 1276:
! 1277: if (pos)
! 1278: *pos = ht->pListTail;
! 1279: else
! 1280: ht->pInternalPointer = ht->pListTail;
! 1281: }
! 1282:
! 1283:
! 1284: ZEND_API int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos)
! 1285: {
! 1286: HashPosition *current = pos ? pos : &ht->pInternalPointer;
! 1287:
! 1288: IS_CONSISTENT(ht);
! 1289:
! 1290: if (*current) {
! 1291: *current = (*current)->pListNext;
! 1292: return SUCCESS;
! 1293: } else
! 1294: return FAILURE;
! 1295: }
! 1296:
! 1297: ZEND_API int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos)
! 1298: {
! 1299: HashPosition *current = pos ? pos : &ht->pInternalPointer;
! 1300:
! 1301: IS_CONSISTENT(ht);
! 1302:
! 1303: if (*current) {
! 1304: *current = (*current)->pListLast;
! 1305: return SUCCESS;
! 1306: } else
! 1307: return FAILURE;
! 1308: }
! 1309:
! 1310:
! 1311: /* This function should be made binary safe */
! 1312: ZEND_API int zend_hash_get_current_key_ex(const HashTable *ht, char **str_index, uint *str_length, ulong *num_index, zend_bool duplicate, HashPosition *pos)
! 1313: {
! 1314: Bucket *p;
! 1315:
! 1316: p = pos ? (*pos) : ht->pInternalPointer;
! 1317:
! 1318: IS_CONSISTENT(ht);
! 1319:
! 1320: if (p) {
! 1321: if (p->nKeyLength) {
! 1322: if (duplicate) {
! 1323: *str_index = estrndup(p->arKey, p->nKeyLength - 1);
! 1324: } else {
! 1325: *str_index = p->arKey;
! 1326: }
! 1327: if (str_length) {
! 1328: *str_length = p->nKeyLength;
! 1329: }
! 1330: return HASH_KEY_IS_STRING;
! 1331: } else {
! 1332: *num_index = p->h;
! 1333: return HASH_KEY_IS_LONG;
! 1334: }
! 1335: }
! 1336: return HASH_KEY_NON_EXISTANT;
! 1337: }
! 1338:
! 1339:
! 1340: ZEND_API int zend_hash_get_current_key_type_ex(HashTable *ht, HashPosition *pos)
! 1341: {
! 1342: Bucket *p;
! 1343:
! 1344: p = pos ? (*pos) : ht->pInternalPointer;
! 1345:
! 1346: IS_CONSISTENT(ht);
! 1347:
! 1348: if (p) {
! 1349: if (p->nKeyLength) {
! 1350: return HASH_KEY_IS_STRING;
! 1351: } else {
! 1352: return HASH_KEY_IS_LONG;
! 1353: }
! 1354: }
! 1355: return HASH_KEY_NON_EXISTANT;
! 1356: }
! 1357:
! 1358:
! 1359: ZEND_API int zend_hash_get_current_data_ex(HashTable *ht, void **pData, HashPosition *pos)
! 1360: {
! 1361: Bucket *p;
! 1362:
! 1363: p = pos ? (*pos) : ht->pInternalPointer;
! 1364:
! 1365: IS_CONSISTENT(ht);
! 1366:
! 1367: if (p) {
! 1368: *pData = p->pData;
! 1369: return SUCCESS;
! 1370: } else {
! 1371: return FAILURE;
! 1372: }
! 1373: }
! 1374:
! 1375: /* This function changes key of current element without changing elements'
! 1376: * order. If element with target key already exists, it will be deleted first.
! 1377: */
! 1378: ZEND_API int zend_hash_update_current_key_ex(HashTable *ht, int key_type, const char *str_index, uint str_length, ulong num_index, int mode, HashPosition *pos)
! 1379: {
! 1380: Bucket *p, *q;
! 1381:
! 1382: p = pos ? (*pos) : ht->pInternalPointer;
! 1383:
! 1384: IS_CONSISTENT(ht);
! 1385:
! 1386: zend_hash_check_destructor(ht->pDestructor);
! 1387: if (p) {
! 1388: if (key_type == HASH_KEY_IS_LONG) {
! 1389: str_length = 0;
! 1390: if (!p->nKeyLength && p->h == num_index) {
! 1391: return SUCCESS;
! 1392: }
! 1393:
! 1394: q = ht->arBuckets[num_index & ht->nTableMask];
! 1395: while (q != NULL) {
! 1396: if (!q->nKeyLength && q->h == num_index) {
! 1397: break;
! 1398: }
! 1399: q = q->pNext;
! 1400: }
! 1401: } else if (key_type == HASH_KEY_IS_STRING) {
! 1402: ulong h;
! 1403:
! 1404: if (p->nKeyLength == str_length &&
! 1405: memcmp(p->arKey, str_index, str_length) == 0) {
! 1406: return SUCCESS;
! 1407: }
! 1408:
! 1409: h = zend_inline_hash_func(str_index, str_length);
! 1410: q = ht->arBuckets[h & ht->nTableMask];
! 1411:
! 1412: while (q != NULL) {
! 1413: if (q->h == h && q->nKeyLength == str_length &&
! 1414: memcmp(q->arKey, str_index, str_length) == 0) {
! 1415: break;
! 1416: }
! 1417: q = q->pNext;
! 1418: }
! 1419: } else {
! 1420: return FAILURE;
! 1421: }
! 1422:
! 1423: HANDLE_BLOCK_INTERRUPTIONS();
! 1424:
! 1425: if (q) {
! 1426: if (mode != HASH_UPDATE_KEY_ANYWAY) {
! 1427: Bucket *r = p->pListLast;
! 1428: int found = HASH_UPDATE_KEY_IF_BEFORE;
! 1429:
! 1430: while (r) {
! 1431: if (r == q) {
! 1432: found = HASH_UPDATE_KEY_IF_AFTER;
! 1433: break;
! 1434: }
! 1435: r = r->pListLast;
! 1436: }
! 1437: if (mode & found) {
! 1438: /* delete current bucket */
! 1439: if (p == ht->arBuckets[p->h & ht->nTableMask]) {
! 1440: ht->arBuckets[p->h & ht->nTableMask] = p->pNext;
! 1441: } else {
! 1442: p->pLast->pNext = p->pNext;
! 1443: }
! 1444: if (p->pNext) {
! 1445: p->pNext->pLast = p->pLast;
! 1446: }
! 1447: if (p->pListLast != NULL) {
! 1448: p->pListLast->pListNext = p->pListNext;
! 1449: } else {
! 1450: /* Deleting the head of the list */
! 1451: ht->pListHead = p->pListNext;
! 1452: }
! 1453: if (p->pListNext != NULL) {
! 1454: p->pListNext->pListLast = p->pListLast;
! 1455: } else {
! 1456: ht->pListTail = p->pListLast;
! 1457: }
! 1458: if (ht->pInternalPointer == p) {
! 1459: ht->pInternalPointer = p->pListNext;
! 1460: }
! 1461: if (ht->pDestructor) {
! 1462: ht->pDestructor(p->pData);
! 1463: }
! 1464: if (p->pData != &p->pDataPtr) {
! 1465: pefree(p->pData, ht->persistent);
! 1466: }
! 1467: pefree(p, ht->persistent);
! 1468: ht->nNumOfElements--;
! 1469: HANDLE_UNBLOCK_INTERRUPTIONS();
! 1470: return FAILURE;
! 1471: }
! 1472: }
! 1473: /* delete another bucket with the same key */
! 1474: if (q == ht->arBuckets[q->h & ht->nTableMask]) {
! 1475: ht->arBuckets[q->h & ht->nTableMask] = q->pNext;
! 1476: } else {
! 1477: q->pLast->pNext = q->pNext;
! 1478: }
! 1479: if (q->pNext) {
! 1480: q->pNext->pLast = q->pLast;
! 1481: }
! 1482: if (q->pListLast != NULL) {
! 1483: q->pListLast->pListNext = q->pListNext;
! 1484: } else {
! 1485: /* Deleting the head of the list */
! 1486: ht->pListHead = q->pListNext;
! 1487: }
! 1488: if (q->pListNext != NULL) {
! 1489: q->pListNext->pListLast = q->pListLast;
! 1490: } else {
! 1491: ht->pListTail = q->pListLast;
! 1492: }
! 1493: if (ht->pInternalPointer == q) {
! 1494: ht->pInternalPointer = q->pListNext;
! 1495: }
! 1496: if (ht->pDestructor) {
! 1497: ht->pDestructor(q->pData);
! 1498: }
! 1499: if (q->pData != &q->pDataPtr) {
! 1500: pefree(q->pData, ht->persistent);
! 1501: }
! 1502: pefree(q, ht->persistent);
! 1503: ht->nNumOfElements--;
! 1504: }
! 1505:
! 1506: if (p->pNext) {
! 1507: p->pNext->pLast = p->pLast;
! 1508: }
! 1509: if (p->pLast) {
! 1510: p->pLast->pNext = p->pNext;
! 1511: } else {
! 1512: ht->arBuckets[p->h & ht->nTableMask] = p->pNext;
! 1513: }
! 1514:
! 1515: if (p->nKeyLength != str_length) {
! 1516: Bucket *q = (Bucket *) pemalloc(sizeof(Bucket) - 1 + str_length, ht->persistent);
! 1517:
! 1518: q->nKeyLength = str_length;
! 1519: if (p->pData == &p->pDataPtr) {
! 1520: q->pData = &q->pDataPtr;
! 1521: } else {
! 1522: q->pData = p->pData;
! 1523: }
! 1524: q->pDataPtr = p->pDataPtr;
! 1525: q->pListNext = p->pListNext;
! 1526: q->pListLast = p->pListLast;
! 1527: if (q->pListNext) {
! 1528: p->pListNext->pListLast = q;
! 1529: } else {
! 1530: ht->pListTail = q;
! 1531: }
! 1532: if (q->pListLast) {
! 1533: p->pListLast->pListNext = q;
! 1534: } else {
! 1535: ht->pListHead = q;
! 1536: }
! 1537: if (ht->pInternalPointer == p) {
! 1538: ht->pInternalPointer = q;
! 1539: }
! 1540: if (pos) {
! 1541: *pos = q;
! 1542: }
! 1543: pefree(p, ht->persistent);
! 1544: p = q;
! 1545: }
! 1546:
! 1547: if (key_type == HASH_KEY_IS_LONG) {
! 1548: p->h = num_index;
! 1549: } else {
! 1550: memcpy(p->arKey, str_index, str_length);
! 1551: p->h = zend_inline_hash_func(str_index, str_length);
! 1552: }
! 1553:
! 1554: CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[p->h & ht->nTableMask]);
! 1555: ht->arBuckets[p->h & ht->nTableMask] = p;
! 1556: HANDLE_UNBLOCK_INTERRUPTIONS();
! 1557:
! 1558: return SUCCESS;
! 1559: } else {
! 1560: return FAILURE;
! 1561: }
! 1562: }
! 1563:
! 1564: ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func,
! 1565: compare_func_t compar, int renumber TSRMLS_DC)
! 1566: {
! 1567: Bucket **arTmp;
! 1568: Bucket *p;
! 1569: int i, j;
! 1570:
! 1571: IS_CONSISTENT(ht);
! 1572:
! 1573: if (!(ht->nNumOfElements>1) && !(renumber && ht->nNumOfElements>0)) { /* Doesn't require sorting */
! 1574: return SUCCESS;
! 1575: }
! 1576: arTmp = (Bucket **) pemalloc(ht->nNumOfElements * sizeof(Bucket *), ht->persistent);
! 1577: if (!arTmp) {
! 1578: return FAILURE;
! 1579: }
! 1580: p = ht->pListHead;
! 1581: i = 0;
! 1582: while (p) {
! 1583: arTmp[i] = p;
! 1584: p = p->pListNext;
! 1585: i++;
! 1586: }
! 1587:
! 1588: (*sort_func)((void *) arTmp, i, sizeof(Bucket *), compar TSRMLS_CC);
! 1589:
! 1590: HANDLE_BLOCK_INTERRUPTIONS();
! 1591: ht->pListHead = arTmp[0];
! 1592: ht->pListTail = NULL;
! 1593: ht->pInternalPointer = ht->pListHead;
! 1594:
! 1595: arTmp[0]->pListLast = NULL;
! 1596: if (i > 1) {
! 1597: arTmp[0]->pListNext = arTmp[1];
! 1598: for (j = 1; j < i-1; j++) {
! 1599: arTmp[j]->pListLast = arTmp[j-1];
! 1600: arTmp[j]->pListNext = arTmp[j+1];
! 1601: }
! 1602: arTmp[j]->pListLast = arTmp[j-1];
! 1603: arTmp[j]->pListNext = NULL;
! 1604: } else {
! 1605: arTmp[0]->pListNext = NULL;
! 1606: }
! 1607: ht->pListTail = arTmp[i-1];
! 1608:
! 1609: pefree(arTmp, ht->persistent);
! 1610: HANDLE_UNBLOCK_INTERRUPTIONS();
! 1611:
! 1612: if (renumber) {
! 1613: p = ht->pListHead;
! 1614: i=0;
! 1615: while (p != NULL) {
! 1616: p->nKeyLength = 0;
! 1617: p->h = i++;
! 1618: p = p->pListNext;
! 1619: }
! 1620: ht->nNextFreeElement = i;
! 1621: zend_hash_rehash(ht);
! 1622: }
! 1623: return SUCCESS;
! 1624: }
! 1625:
! 1626:
! 1627: ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered TSRMLS_DC)
! 1628: {
! 1629: Bucket *p1, *p2 = NULL;
! 1630: int result;
! 1631: void *pData2;
! 1632:
! 1633: IS_CONSISTENT(ht1);
! 1634: IS_CONSISTENT(ht2);
! 1635:
! 1636: HASH_PROTECT_RECURSION(ht1);
! 1637: HASH_PROTECT_RECURSION(ht2);
! 1638:
! 1639: result = ht1->nNumOfElements - ht2->nNumOfElements;
! 1640: if (result!=0) {
! 1641: HASH_UNPROTECT_RECURSION(ht1);
! 1642: HASH_UNPROTECT_RECURSION(ht2);
! 1643: return result;
! 1644: }
! 1645:
! 1646: p1 = ht1->pListHead;
! 1647: if (ordered) {
! 1648: p2 = ht2->pListHead;
! 1649: }
! 1650:
! 1651: while (p1) {
! 1652: if (ordered && !p2) {
! 1653: HASH_UNPROTECT_RECURSION(ht1);
! 1654: HASH_UNPROTECT_RECURSION(ht2);
! 1655: return 1; /* That's not supposed to happen */
! 1656: }
! 1657: if (ordered) {
! 1658: if (p1->nKeyLength==0 && p2->nKeyLength==0) { /* numeric indices */
! 1659: result = p1->h - p2->h;
! 1660: if (result!=0) {
! 1661: HASH_UNPROTECT_RECURSION(ht1);
! 1662: HASH_UNPROTECT_RECURSION(ht2);
! 1663: return result;
! 1664: }
! 1665: } else { /* string indices */
! 1666: result = p1->nKeyLength - p2->nKeyLength;
! 1667: if (result!=0) {
! 1668: HASH_UNPROTECT_RECURSION(ht1);
! 1669: HASH_UNPROTECT_RECURSION(ht2);
! 1670: return result;
! 1671: }
! 1672: result = memcmp(p1->arKey, p2->arKey, p1->nKeyLength);
! 1673: if (result!=0) {
! 1674: HASH_UNPROTECT_RECURSION(ht1);
! 1675: HASH_UNPROTECT_RECURSION(ht2);
! 1676: return result;
! 1677: }
! 1678: }
! 1679: pData2 = p2->pData;
! 1680: } else {
! 1681: if (p1->nKeyLength==0) { /* numeric index */
! 1682: if (zend_hash_index_find(ht2, p1->h, &pData2)==FAILURE) {
! 1683: HASH_UNPROTECT_RECURSION(ht1);
! 1684: HASH_UNPROTECT_RECURSION(ht2);
! 1685: return 1;
! 1686: }
! 1687: } else { /* string index */
! 1688: if (zend_hash_quick_find(ht2, p1->arKey, p1->nKeyLength, p1->h, &pData2)==FAILURE) {
! 1689: HASH_UNPROTECT_RECURSION(ht1);
! 1690: HASH_UNPROTECT_RECURSION(ht2);
! 1691: return 1;
! 1692: }
! 1693: }
! 1694: }
! 1695: result = compar(p1->pData, pData2 TSRMLS_CC);
! 1696: if (result!=0) {
! 1697: HASH_UNPROTECT_RECURSION(ht1);
! 1698: HASH_UNPROTECT_RECURSION(ht2);
! 1699: return result;
! 1700: }
! 1701: p1 = p1->pListNext;
! 1702: if (ordered) {
! 1703: p2 = p2->pListNext;
! 1704: }
! 1705: }
! 1706:
! 1707: HASH_UNPROTECT_RECURSION(ht1);
! 1708: HASH_UNPROTECT_RECURSION(ht2);
! 1709: return 0;
! 1710: }
! 1711:
! 1712:
! 1713: ZEND_API int zend_hash_minmax(const HashTable *ht, compare_func_t compar, int flag, void **pData TSRMLS_DC)
! 1714: {
! 1715: Bucket *p, *res;
! 1716:
! 1717: IS_CONSISTENT(ht);
! 1718:
! 1719: if (ht->nNumOfElements == 0 ) {
! 1720: *pData=NULL;
! 1721: return FAILURE;
! 1722: }
! 1723:
! 1724: res = p = ht->pListHead;
! 1725: while ((p = p->pListNext)) {
! 1726: if (flag) {
! 1727: if (compar(&res, &p TSRMLS_CC) < 0) { /* max */
! 1728: res = p;
! 1729: }
! 1730: } else {
! 1731: if (compar(&res, &p TSRMLS_CC) > 0) { /* min */
! 1732: res = p;
! 1733: }
! 1734: }
! 1735: }
! 1736: *pData = res->pData;
! 1737: return SUCCESS;
! 1738: }
! 1739:
! 1740: ZEND_API ulong zend_hash_next_free_element(const HashTable *ht)
! 1741: {
! 1742: IS_CONSISTENT(ht);
! 1743:
! 1744: return ht->nNextFreeElement;
! 1745:
! 1746: }
! 1747:
! 1748:
! 1749: #if ZEND_DEBUG
! 1750: void zend_hash_display_pListTail(const HashTable *ht)
! 1751: {
! 1752: Bucket *p;
! 1753:
! 1754: p = ht->pListTail;
! 1755: while (p != NULL) {
! 1756: zend_output_debug_string(0, "pListTail has key %s\n", p->arKey);
! 1757: p = p->pListLast;
! 1758: }
! 1759: }
! 1760:
! 1761: void zend_hash_display(const HashTable *ht)
! 1762: {
! 1763: Bucket *p;
! 1764: uint i;
! 1765:
! 1766: for (i = 0; i < ht->nTableSize; i++) {
! 1767: p = ht->arBuckets[i];
! 1768: while (p != NULL) {
! 1769: zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h);
! 1770: p = p->pNext;
! 1771: }
! 1772: }
! 1773:
! 1774: p = ht->pListTail;
! 1775: while (p != NULL) {
! 1776: zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h);
! 1777: p = p->pListLast;
! 1778: }
! 1779: }
! 1780: #endif
! 1781:
! 1782: /*
! 1783: * Local variables:
! 1784: * tab-width: 4
! 1785: * c-basic-offset: 4
! 1786: * indent-tabs-mode: t
! 1787: * End:
! 1788: */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to zend_hash.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / Zend