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