release/src/router/php/Zend/zend_hash.c

   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
  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 #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
 146 static const Bucket *uninitialized_bucket = NULL;
 147
 148 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)
 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
 179 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)
 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
 188 ZEND_API void zend_hash_set_apply_protection(HashTable *ht, zend_bool bApplyProtection)
 189 {
 190         ht->bApplyProtection = bApplyProtection;
 191 }
 192
 193
 194
 195 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)
 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
 278 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)
 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
 359 ZEND_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
 367 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)
 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
 440 static 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
 465 ZEND_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
 486 ZEND_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
 547 ZEND_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
 575 ZEND_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  */
 610 static 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
 662 ZEND_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
 679 ZEND_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
 707 ZEND_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
 731 ZEND_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
 755 ZEND_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
 790 ZEND_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
 814 ZEND_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
 845 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)
 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
 871 static 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
 882 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)
 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
 903 ZEND_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  */
 913 ZEND_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
 937 ZEND_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
 963 ZEND_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
 986 ZEND_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
1012 ZEND_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
1033 ZEND_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
1053 ZEND_API int zend_hash_num_elements(const HashTable *ht)
1054 {
1055         IS_CONSISTENT(ht);
1056
1057         return ht->nNumOfElements;
1058 }
1059
1060
1061 ZEND_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
1073 ZEND_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
1094 ZEND_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  */
1108 ZEND_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
1119 ZEND_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
1132 ZEND_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  */
1147 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)
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
1175 ZEND_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
1194 ZEND_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  */
1213 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)
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
1421 ZEND_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
1484 ZEND_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
1570 ZEND_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
1597 ZEND_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
1607 void 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
1618 void 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  */