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