Back to index

php5  5.3.10
zend_hash.c
Go to the documentation of this file.
00001 /*
00002    +----------------------------------------------------------------------+
00003    | Zend Engine                                                          |
00004    +----------------------------------------------------------------------+
00005    | Copyright (c) 1998-2012 Zend Technologies Ltd. (http://www.zend.com) |
00006    +----------------------------------------------------------------------+
00007    | This source file is subject to version 2.00 of the Zend license,     |
00008    | that is bundled with this package in the file LICENSE, and is        | 
00009    | available through the world-wide-web at the following url:           |
00010    | http://www.zend.com/license/2_00.txt.                                |
00011    | If you did not receive a copy of the Zend license and are unable to  |
00012    | obtain it through the world-wide-web, please send a note to          |
00013    | license@zend.com so we can mail you a copy immediately.              |
00014    +----------------------------------------------------------------------+
00015    | Authors: Andi Gutmans <andi@zend.com>                                |
00016    |          Zeev Suraski <zeev@zend.com>                                |
00017    +----------------------------------------------------------------------+
00018 */
00019 
00020 /* $Id: zend_hash.c 321634 2012-01-01 13:15:04Z felipe $ */
00021 
00022 #include "zend.h"
00023 
00024 #define CONNECT_TO_BUCKET_DLLIST(element, list_head)           \
00025        (element)->pNext = (list_head);                                              \
00026        (element)->pLast = NULL;                                                     \
00027        if ((element)->pNext) {                                                             \
00028               (element)->pNext->pLast = (element);                           \
00029        }
00030 
00031 #define CONNECT_TO_GLOBAL_DLLIST(element, ht)                         \
00032        (element)->pListLast = (ht)->pListTail;                               \
00033        (ht)->pListTail = (element);                                                 \
00034        (element)->pListNext = NULL;                                                 \
00035        if ((element)->pListLast != NULL) {                                          \
00036               (element)->pListLast->pListNext = (element);            \
00037        }                                                                                                 \
00038        if (!(ht)->pListHead) {                                                             \
00039               (ht)->pListHead = (element);                                          \
00040        }                                                                                                 \
00041        if ((ht)->pInternalPointer == NULL) {                                 \
00042               (ht)->pInternalPointer = (element);                                   \
00043        }
00044 
00045 #if ZEND_DEBUG
00046 #define HT_OK                      0
00047 #define HT_IS_DESTROYING    1
00048 #define HT_DESTROYED        2
00049 #define HT_CLEANING                3
00050 
00051 static void _zend_is_inconsistent(const HashTable *ht, const char *file, int line)
00052 {
00053        if (ht->inconsistent==HT_OK) {
00054               return;
00055        }
00056        switch (ht->inconsistent) {
00057               case HT_IS_DESTROYING:
00058                      zend_output_debug_string(1, "%s(%d) : ht=%p is being destroyed", file, line, ht);
00059                      break;
00060               case HT_DESTROYED:
00061                      zend_output_debug_string(1, "%s(%d) : ht=%p is already destroyed", file, line, ht);
00062                      break;
00063               case HT_CLEANING:
00064                      zend_output_debug_string(1, "%s(%d) : ht=%p is being cleaned", file, line, ht);
00065                      break;
00066               default:
00067                      zend_output_debug_string(1, "%s(%d) : ht=%p is inconsistent", file, line, ht);
00068                      break;
00069        }
00070        zend_bailout();
00071 }
00072 #define IS_CONSISTENT(a) _zend_is_inconsistent(a, __FILE__, __LINE__);
00073 #define SET_INCONSISTENT(n) ht->inconsistent = n;
00074 #else
00075 #define IS_CONSISTENT(a)
00076 #define SET_INCONSISTENT(n)
00077 #endif
00078 
00079 #define HASH_PROTECT_RECURSION(ht)                                                                                            \
00080        if ((ht)->bApplyProtection) {                                                                                                 \
00081               if ((ht)->nApplyCount++ >= 3) {                                                                                        \
00082                      zend_error(E_ERROR, "Nesting level too deep - recursive dependency?");              \
00083               }                                                                                                                                           \
00084        }
00085 
00086 
00087 #define HASH_UNPROTECT_RECURSION(ht)                                                                                          \
00088        if ((ht)->bApplyProtection) {                                                                                                 \
00089               (ht)->nApplyCount--;                                                                                                   \
00090        }
00091 
00092 
00093 #define ZEND_HASH_IF_FULL_DO_RESIZE(ht)                        \
00094        if ((ht)->nNumOfElements > (ht)->nTableSize) {   \
00095               zend_hash_do_resize(ht);                                \
00096        }
00097 
00098 static int zend_hash_do_resize(HashTable *ht);
00099 
00100 ZEND_API ulong zend_hash_func(const char *arKey, uint nKeyLength)
00101 {
00102        return zend_inline_hash_func(arKey, nKeyLength);
00103 }
00104 
00105 
00106 #define UPDATE_DATA(ht, p, pData, nDataSize)                                                                           \
00107        if (nDataSize == sizeof(void*)) {                                                                                      \
00108               if ((p)->pData != &(p)->pDataPtr) {                                                                                    \
00109                      pefree_rel((p)->pData, (ht)->persistent);                                                         \
00110               }                                                                                                                                           \
00111               memcpy(&(p)->pDataPtr, pData, sizeof(void *));                                                           \
00112               (p)->pData = &(p)->pDataPtr;                                                                                           \
00113        } else {                                                                                                                                    \
00114               if ((p)->pData == &(p)->pDataPtr) {                                                                                    \
00115                      (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);                    \
00116                      (p)->pDataPtr=NULL;                                                                                                    \
00117               } else {                                                                                                                             \
00118                      (p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent);       \
00119                      /* (p)->pDataPtr is already NULL so no need to initialize it */                            \
00120               }                                                                                                                                           \
00121               memcpy((p)->pData, pData, nDataSize);                                                                           \
00122        }
00123 
00124 #define INIT_DATA(ht, p, pData, nDataSize);                                                       \
00125        if (nDataSize == sizeof(void*)) {                                                          \
00126               memcpy(&(p)->pDataPtr, pData, sizeof(void *));                               \
00127               (p)->pData = &(p)->pDataPtr;                                                               \
00128        } else {                                                                                                        \
00129               (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);\
00130               if (!(p)->pData) {                                                                                \
00131                      pefree_rel(p, (ht)->persistent);                                             \
00132                      return FAILURE;                                                                                   \
00133               }                                                                                                               \
00134               memcpy((p)->pData, pData, nDataSize);                                               \
00135               (p)->pDataPtr=NULL;                                                                               \
00136        }
00137 
00138 
00139 
00140 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)
00141 {
00142        uint i = 3;
00143        Bucket **tmp;
00144 
00145        SET_INCONSISTENT(HT_OK);
00146 
00147        if (nSize >= 0x80000000) {
00148               /* prevent overflow */
00149               ht->nTableSize = 0x80000000;
00150        } else {
00151               while ((1U << i) < nSize) {
00152                      i++;
00153               }
00154               ht->nTableSize = 1 << i;
00155        }
00156 
00157        ht->nTableMask = ht->nTableSize - 1;
00158        ht->pDestructor = pDestructor;
00159        ht->arBuckets = NULL;
00160        ht->pListHead = NULL;
00161        ht->pListTail = NULL;
00162        ht->nNumOfElements = 0;
00163        ht->nNextFreeElement = 0;
00164        ht->pInternalPointer = NULL;
00165        ht->persistent = persistent;
00166        ht->nApplyCount = 0;
00167        ht->bApplyProtection = 1;
00168        
00169        /* Uses ecalloc() so that Bucket* == NULL */
00170        if (persistent) {
00171               tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *));
00172               if (!tmp) {
00173                      return FAILURE;
00174               }
00175               ht->arBuckets = tmp;
00176        } else {
00177               tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket *));
00178               if (tmp) {
00179                      ht->arBuckets = tmp;
00180               }
00181        }
00182        
00183        return SUCCESS;
00184 }
00185 
00186 
00187 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)
00188 {
00189        int retval = _zend_hash_init(ht, nSize, pHashFunction, pDestructor, persistent ZEND_FILE_LINE_CC);
00190 
00191        ht->bApplyProtection = bApplyProtection;
00192        return retval;
00193 }
00194 
00195 
00196 ZEND_API void zend_hash_set_apply_protection(HashTable *ht, zend_bool bApplyProtection)
00197 {
00198        ht->bApplyProtection = bApplyProtection;
00199 }
00200 
00201 
00202 
00203 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)
00204 {
00205        ulong h;
00206        uint nIndex;
00207        Bucket *p;
00208 
00209        IS_CONSISTENT(ht);
00210 
00211        if (nKeyLength <= 0) {
00212 #if ZEND_DEBUG
00213               ZEND_PUTS("zend_hash_update: Can't put in empty key\n");
00214 #endif
00215               return FAILURE;
00216        }
00217 
00218        h = zend_inline_hash_func(arKey, nKeyLength);
00219        nIndex = h & ht->nTableMask;
00220 
00221        p = ht->arBuckets[nIndex];
00222        while (p != NULL) {
00223               if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
00224                      if (!memcmp(p->arKey, arKey, nKeyLength)) {
00225                             if (flag & HASH_ADD) {
00226                                    return FAILURE;
00227                             }
00228                             HANDLE_BLOCK_INTERRUPTIONS();
00229 #if ZEND_DEBUG
00230                             if (p->pData == pData) {
00231                                    ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n");
00232                                    HANDLE_UNBLOCK_INTERRUPTIONS();
00233                                    return FAILURE;
00234                             }
00235 #endif
00236                             if (ht->pDestructor) {
00237                                    ht->pDestructor(p->pData);
00238                             }
00239                             UPDATE_DATA(ht, p, pData, nDataSize);
00240                             if (pDest) {
00241                                    *pDest = p->pData;
00242                             }
00243                             HANDLE_UNBLOCK_INTERRUPTIONS();
00244                             return SUCCESS;
00245                      }
00246               }
00247               p = p->pNext;
00248        }
00249        
00250        p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
00251        if (!p) {
00252               return FAILURE;
00253        }
00254        memcpy(p->arKey, arKey, nKeyLength);
00255        p->nKeyLength = nKeyLength;
00256        INIT_DATA(ht, p, pData, nDataSize);
00257        p->h = h;
00258        CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
00259        if (pDest) {
00260               *pDest = p->pData;
00261        }
00262 
00263        HANDLE_BLOCK_INTERRUPTIONS();
00264        CONNECT_TO_GLOBAL_DLLIST(p, ht);
00265        ht->arBuckets[nIndex] = p;
00266        HANDLE_UNBLOCK_INTERRUPTIONS();
00267 
00268        ht->nNumOfElements++;
00269        ZEND_HASH_IF_FULL_DO_RESIZE(ht);          /* If the Hash table is full, resize it */
00270        return SUCCESS;
00271 }
00272 
00273 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)
00274 {
00275        uint nIndex;
00276        Bucket *p;
00277 
00278        IS_CONSISTENT(ht);
00279 
00280        if (nKeyLength == 0) {
00281               return zend_hash_index_update(ht, h, pData, nDataSize, pDest);
00282        }
00283 
00284        nIndex = h & ht->nTableMask;
00285        
00286        p = ht->arBuckets[nIndex];
00287        while (p != NULL) {
00288               if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
00289                      if (!memcmp(p->arKey, arKey, nKeyLength)) {
00290                             if (flag & HASH_ADD) {
00291                                    return FAILURE;
00292                             }
00293                             HANDLE_BLOCK_INTERRUPTIONS();
00294 #if ZEND_DEBUG
00295                             if (p->pData == pData) {
00296                                    ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n");
00297                                    HANDLE_UNBLOCK_INTERRUPTIONS();
00298                                    return FAILURE;
00299                             }
00300 #endif
00301                             if (ht->pDestructor) {
00302                                    ht->pDestructor(p->pData);
00303                             }
00304                             UPDATE_DATA(ht, p, pData, nDataSize);
00305                             if (pDest) {
00306                                    *pDest = p->pData;
00307                             }
00308                             HANDLE_UNBLOCK_INTERRUPTIONS();
00309                             return SUCCESS;
00310                      }
00311               }
00312               p = p->pNext;
00313        }
00314        
00315        p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
00316        if (!p) {
00317               return FAILURE;
00318        }
00319 
00320        memcpy(p->arKey, arKey, nKeyLength);
00321        p->nKeyLength = nKeyLength;
00322        INIT_DATA(ht, p, pData, nDataSize);
00323        p->h = h;
00324        
00325        CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
00326 
00327        if (pDest) {
00328               *pDest = p->pData;
00329        }
00330 
00331        HANDLE_BLOCK_INTERRUPTIONS();
00332        ht->arBuckets[nIndex] = p;
00333        CONNECT_TO_GLOBAL_DLLIST(p, ht);
00334        HANDLE_UNBLOCK_INTERRUPTIONS();
00335 
00336        ht->nNumOfElements++;
00337        ZEND_HASH_IF_FULL_DO_RESIZE(ht);          /* If the Hash table is full, resize it */
00338        return SUCCESS;
00339 }
00340 
00341 
00342 ZEND_API int zend_hash_add_empty_element(HashTable *ht, const char *arKey, uint nKeyLength)
00343 {
00344        void *dummy = (void *) 1;
00345 
00346        return zend_hash_add(ht, arKey, nKeyLength, &dummy, sizeof(void *), NULL);
00347 }
00348 
00349 
00350 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)
00351 {
00352        uint nIndex;
00353        Bucket *p;
00354 
00355        IS_CONSISTENT(ht);
00356 
00357        if (flag & HASH_NEXT_INSERT) {
00358               h = ht->nNextFreeElement;
00359        }
00360        nIndex = h & ht->nTableMask;
00361 
00362        p = ht->arBuckets[nIndex];
00363        while (p != NULL) {
00364               if ((p->nKeyLength == 0) && (p->h == h)) {
00365                      if (flag & HASH_NEXT_INSERT || flag & HASH_ADD) {
00366                             return FAILURE;
00367                      }
00368                      HANDLE_BLOCK_INTERRUPTIONS();
00369 #if ZEND_DEBUG
00370                      if (p->pData == pData) {
00371                             ZEND_PUTS("Fatal error in zend_hash_index_update: p->pData == pData\n");
00372                             HANDLE_UNBLOCK_INTERRUPTIONS();
00373                             return FAILURE;
00374                      }
00375 #endif
00376                      if (ht->pDestructor) {
00377                             ht->pDestructor(p->pData);
00378                      }
00379                      UPDATE_DATA(ht, p, pData, nDataSize);
00380                      HANDLE_UNBLOCK_INTERRUPTIONS();
00381                      if ((long)h >= (long)ht->nNextFreeElement) {
00382                             ht->nNextFreeElement = h < LONG_MAX ? h + 1 : LONG_MAX;
00383                      }
00384                      if (pDest) {
00385                             *pDest = p->pData;
00386                      }
00387                      return SUCCESS;
00388               }
00389               p = p->pNext;
00390        }
00391        p = (Bucket *) pemalloc_rel(sizeof(Bucket) - 1, ht->persistent);
00392        if (!p) {
00393               return FAILURE;
00394        }
00395        p->nKeyLength = 0; /* Numeric indices are marked by making the nKeyLength == 0 */
00396        p->h = h;
00397        INIT_DATA(ht, p, pData, nDataSize);
00398        if (pDest) {
00399               *pDest = p->pData;
00400        }
00401 
00402        CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
00403 
00404        HANDLE_BLOCK_INTERRUPTIONS();
00405        ht->arBuckets[nIndex] = p;
00406        CONNECT_TO_GLOBAL_DLLIST(p, ht);
00407        HANDLE_UNBLOCK_INTERRUPTIONS();
00408 
00409        if ((long)h >= (long)ht->nNextFreeElement) {
00410               ht->nNextFreeElement = h < LONG_MAX ? h + 1 : LONG_MAX;
00411        }
00412        ht->nNumOfElements++;
00413        ZEND_HASH_IF_FULL_DO_RESIZE(ht);
00414        return SUCCESS;
00415 }
00416 
00417 
00418 static int zend_hash_do_resize(HashTable *ht)
00419 {
00420        Bucket **t;
00421 
00422        IS_CONSISTENT(ht);
00423 
00424        if ((ht->nTableSize << 1) > 0) {   /* Let's double the table size */
00425               t = (Bucket **) perealloc_recoverable(ht->arBuckets, (ht->nTableSize << 1) * sizeof(Bucket *), ht->persistent);
00426               if (t) {
00427                      HANDLE_BLOCK_INTERRUPTIONS();
00428                      ht->arBuckets = t;
00429                      ht->nTableSize = (ht->nTableSize << 1);
00430                      ht->nTableMask = ht->nTableSize - 1;
00431                      zend_hash_rehash(ht);
00432                      HANDLE_UNBLOCK_INTERRUPTIONS();
00433                      return SUCCESS;
00434               }
00435               return FAILURE;
00436        }
00437        return SUCCESS;
00438 }
00439 
00440 ZEND_API int zend_hash_rehash(HashTable *ht)
00441 {
00442        Bucket *p;
00443        uint nIndex;
00444 
00445        IS_CONSISTENT(ht);
00446 
00447        memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
00448        p = ht->pListHead;
00449        while (p != NULL) {
00450               nIndex = p->h & ht->nTableMask;
00451               CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
00452               ht->arBuckets[nIndex] = p;
00453               p = p->pListNext;
00454        }
00455        return SUCCESS;
00456 }
00457 
00458 ZEND_API int zend_hash_del_key_or_index(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, int flag)
00459 {
00460        uint nIndex;
00461        Bucket *p;
00462 
00463        IS_CONSISTENT(ht);
00464 
00465        if (flag == HASH_DEL_KEY) {
00466               h = zend_inline_hash_func(arKey, nKeyLength);
00467        }
00468        nIndex = h & ht->nTableMask;
00469 
00470        p = ht->arBuckets[nIndex];
00471        while (p != NULL) {
00472               if ((p->h == h) 
00473                       && (p->nKeyLength == nKeyLength)
00474                       && ((p->nKeyLength == 0) /* Numeric index (short circuits the memcmp() check) */
00475                              || !memcmp(p->arKey, arKey, nKeyLength))) { /* String index */
00476                      HANDLE_BLOCK_INTERRUPTIONS();
00477                      if (p == ht->arBuckets[nIndex]) {
00478                             ht->arBuckets[nIndex] = p->pNext;
00479                      } else {
00480                             p->pLast->pNext = p->pNext;
00481                      }
00482                      if (p->pNext) {
00483                             p->pNext->pLast = p->pLast;
00484                      }
00485                      if (p->pListLast != NULL) {
00486                             p->pListLast->pListNext = p->pListNext;
00487                      } else { 
00488                             /* Deleting the head of the list */
00489                             ht->pListHead = p->pListNext;
00490                      }
00491                      if (p->pListNext != NULL) {
00492                             p->pListNext->pListLast = p->pListLast;
00493                      } else {
00494                             ht->pListTail = p->pListLast;
00495                      }
00496                      if (ht->pInternalPointer == p) {
00497                             ht->pInternalPointer = p->pListNext;
00498                      }
00499                      if (ht->pDestructor) {
00500                             ht->pDestructor(p->pData);
00501                      }
00502                      if (p->pData != &p->pDataPtr) {
00503                             pefree(p->pData, ht->persistent);
00504                      }
00505                      pefree(p, ht->persistent);
00506                      HANDLE_UNBLOCK_INTERRUPTIONS();
00507                      ht->nNumOfElements--;
00508                      return SUCCESS;
00509               }
00510               p = p->pNext;
00511        }
00512        return FAILURE;
00513 }
00514 
00515 
00516 ZEND_API void zend_hash_destroy(HashTable *ht)
00517 {
00518        Bucket *p, *q;
00519 
00520        IS_CONSISTENT(ht);
00521 
00522        SET_INCONSISTENT(HT_IS_DESTROYING);
00523 
00524        p = ht->pListHead;
00525        while (p != NULL) {
00526               q = p;
00527               p = p->pListNext;
00528               if (ht->pDestructor) {
00529                      ht->pDestructor(q->pData);
00530               }
00531               if (q->pData != &q->pDataPtr) {
00532                      pefree(q->pData, ht->persistent);
00533               }
00534               pefree(q, ht->persistent);
00535        }
00536        pefree(ht->arBuckets, ht->persistent);
00537 
00538        SET_INCONSISTENT(HT_DESTROYED);
00539 }
00540 
00541 
00542 ZEND_API void zend_hash_clean(HashTable *ht)
00543 {
00544        Bucket *p, *q;
00545 
00546        IS_CONSISTENT(ht);
00547 
00548        p = ht->pListHead;
00549 
00550        memset(ht->arBuckets, 0, ht->nTableSize*sizeof(Bucket *));
00551        ht->pListHead = NULL;
00552        ht->pListTail = NULL;
00553        ht->nNumOfElements = 0;
00554        ht->nNextFreeElement = 0;
00555        ht->pInternalPointer = NULL;
00556 
00557        while (p != NULL) {
00558               q = p;
00559               p = p->pListNext;
00560               if (ht->pDestructor) {
00561                      ht->pDestructor(q->pData);
00562               }
00563               if (q->pData != &q->pDataPtr) {
00564                      pefree(q->pData, ht->persistent);
00565               }
00566               pefree(q, ht->persistent);
00567        }
00568 }
00569 
00570 /* This function is used by the various apply() functions.
00571  * It deletes the passed bucket, and returns the address of the
00572  * next bucket.  The hash *may* be altered during that time, the
00573  * returned value will still be valid.
00574  */
00575 static Bucket *zend_hash_apply_deleter(HashTable *ht, Bucket *p)
00576 {
00577        Bucket *retval;
00578 
00579        HANDLE_BLOCK_INTERRUPTIONS();
00580        if (p->pLast) {
00581               p->pLast->pNext = p->pNext;
00582        } else {
00583               uint nIndex;
00584 
00585               nIndex = p->h & ht->nTableMask;
00586               ht->arBuckets[nIndex] = p->pNext;
00587        }
00588        if (p->pNext) {
00589               p->pNext->pLast = p->pLast;
00590        } else {
00591               /* Nothing to do as this list doesn't have a tail */
00592        }
00593 
00594        if (p->pListLast != NULL) {
00595               p->pListLast->pListNext = p->pListNext;
00596        } else { 
00597               /* Deleting the head of the list */
00598               ht->pListHead = p->pListNext;
00599        }
00600        if (p->pListNext != NULL) {
00601               p->pListNext->pListLast = p->pListLast;
00602        } else {
00603               ht->pListTail = p->pListLast;
00604        }
00605        if (ht->pInternalPointer == p) {
00606               ht->pInternalPointer = p->pListNext;
00607        }
00608        ht->nNumOfElements--;
00609        HANDLE_UNBLOCK_INTERRUPTIONS();
00610 
00611        if (ht->pDestructor) {
00612               ht->pDestructor(p->pData);
00613        }
00614        if (p->pData != &p->pDataPtr) {
00615               pefree(p->pData, ht->persistent);
00616        }
00617        retval = p->pListNext;
00618        pefree(p, ht->persistent);
00619 
00620        return retval;
00621 }
00622 
00623 
00624 ZEND_API void zend_hash_graceful_destroy(HashTable *ht)
00625 {
00626        Bucket *p;
00627 
00628        IS_CONSISTENT(ht);
00629 
00630        p = ht->pListHead;
00631        while (p != NULL) {
00632               p = zend_hash_apply_deleter(ht, p);
00633        }
00634        pefree(ht->arBuckets, ht->persistent);
00635 
00636        SET_INCONSISTENT(HT_DESTROYED);
00637 }
00638 
00639 ZEND_API void zend_hash_graceful_reverse_destroy(HashTable *ht)
00640 {
00641        Bucket *p;
00642 
00643        IS_CONSISTENT(ht);
00644 
00645        p = ht->pListTail;
00646        while (p != NULL) {
00647               zend_hash_apply_deleter(ht, p);
00648               p = ht->pListTail;
00649        }
00650 
00651        pefree(ht->arBuckets, ht->persistent);
00652 
00653        SET_INCONSISTENT(HT_DESTROYED);
00654 }
00655 
00656 /* This is used to recurse elements and selectively delete certain entries 
00657  * from a hashtable. apply_func() receives the data and decides if the entry 
00658  * should be deleted or recursion should be stopped. The following three 
00659  * return codes are possible:
00660  * ZEND_HASH_APPLY_KEEP   - continue
00661  * ZEND_HASH_APPLY_STOP   - stop iteration
00662  * ZEND_HASH_APPLY_REMOVE - delete the element, combineable with the former
00663  */
00664 
00665 ZEND_API void zend_hash_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC)
00666 {
00667        Bucket *p;
00668 
00669        IS_CONSISTENT(ht);
00670 
00671        HASH_PROTECT_RECURSION(ht);
00672        p = ht->pListHead;
00673        while (p != NULL) {
00674               int result = apply_func(p->pData TSRMLS_CC);
00675               
00676               if (result & ZEND_HASH_APPLY_REMOVE) {
00677                      p = zend_hash_apply_deleter(ht, p);
00678               } else {
00679                      p = p->pListNext;
00680               }
00681               if (result & ZEND_HASH_APPLY_STOP) {
00682                      break;
00683               }
00684        }
00685        HASH_UNPROTECT_RECURSION(ht);
00686 }
00687 
00688 
00689 ZEND_API void zend_hash_apply_with_argument(HashTable *ht, apply_func_arg_t apply_func, void *argument TSRMLS_DC)
00690 {
00691        Bucket *p;
00692 
00693        IS_CONSISTENT(ht);
00694 
00695        HASH_PROTECT_RECURSION(ht);
00696        p = ht->pListHead;
00697        while (p != NULL) {
00698               int result = apply_func(p->pData, argument TSRMLS_CC);
00699               
00700               if (result & ZEND_HASH_APPLY_REMOVE) {
00701                      p = zend_hash_apply_deleter(ht, p);
00702               } else {
00703                      p = p->pListNext;
00704               }
00705               if (result & ZEND_HASH_APPLY_STOP) {
00706                      break;
00707               }
00708        }
00709        HASH_UNPROTECT_RECURSION(ht);
00710 }
00711 
00712 
00713 ZEND_API void zend_hash_apply_with_arguments(HashTable *ht TSRMLS_DC, apply_func_args_t apply_func, int num_args, ...)
00714 {
00715        Bucket *p;
00716        va_list args;
00717        zend_hash_key hash_key;
00718 
00719        IS_CONSISTENT(ht);
00720 
00721        HASH_PROTECT_RECURSION(ht);
00722 
00723        p = ht->pListHead;
00724        while (p != NULL) {
00725               int result;
00726               va_start(args, num_args);
00727               hash_key.arKey = p->arKey;
00728               hash_key.nKeyLength = p->nKeyLength;
00729               hash_key.h = p->h;
00730               result = apply_func(p->pData TSRMLS_CC, num_args, args, &hash_key);
00731 
00732               if (result & ZEND_HASH_APPLY_REMOVE) {
00733                      p = zend_hash_apply_deleter(ht, p);
00734               } else {
00735                      p = p->pListNext;
00736               }
00737               if (result & ZEND_HASH_APPLY_STOP) {
00738                      va_end(args);
00739                      break;
00740               }
00741               va_end(args);
00742        }
00743 
00744        HASH_UNPROTECT_RECURSION(ht);
00745 }
00746 
00747 
00748 ZEND_API void zend_hash_reverse_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC)
00749 {
00750        Bucket *p, *q;
00751 
00752        IS_CONSISTENT(ht);
00753 
00754        HASH_PROTECT_RECURSION(ht);
00755        p = ht->pListTail;
00756        while (p != NULL) {
00757               int result = apply_func(p->pData TSRMLS_CC);
00758 
00759               q = p;
00760               p = p->pListLast;
00761               if (result & ZEND_HASH_APPLY_REMOVE) {
00762                      zend_hash_apply_deleter(ht, q);
00763               }
00764               if (result & ZEND_HASH_APPLY_STOP) {
00765                      break;
00766               }
00767        }
00768        HASH_UNPROTECT_RECURSION(ht);
00769 }
00770 
00771 
00772 ZEND_API void zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size)
00773 {
00774        Bucket *p;
00775        void *new_entry;
00776        zend_bool setTargetPointer;
00777 
00778        IS_CONSISTENT(source);
00779        IS_CONSISTENT(target);
00780 
00781        setTargetPointer = !target->pInternalPointer;
00782        p = source->pListHead;
00783        while (p) {
00784               if (setTargetPointer && source->pInternalPointer == p) {
00785                      target->pInternalPointer = NULL;
00786               }
00787               if (p->nKeyLength) {
00788                      zend_hash_quick_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &new_entry);
00789               } else {
00790                      zend_hash_index_update(target, p->h, p->pData, size, &new_entry);
00791               }
00792               if (pCopyConstructor) {
00793                      pCopyConstructor(new_entry);
00794               }
00795               p = p->pListNext;
00796        }
00797        if (!target->pInternalPointer) {
00798               target->pInternalPointer = target->pListHead;
00799        }
00800 }
00801 
00802 
00803 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)
00804 {
00805        Bucket *p;
00806        void *t;
00807        int mode = (overwrite?HASH_UPDATE:HASH_ADD);
00808 
00809        IS_CONSISTENT(source);
00810        IS_CONSISTENT(target);
00811 
00812        p = source->pListHead;
00813        while (p) {
00814               if (p->nKeyLength>0) {
00815                      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) {
00816                             pCopyConstructor(t);
00817                      }
00818               } else {
00819                      if ((mode==HASH_UPDATE || !zend_hash_index_exists(target, p->h)) && zend_hash_index_update(target, p->h, p->pData, size, &t)==SUCCESS && pCopyConstructor) {
00820                             pCopyConstructor(t);
00821                      }
00822               }
00823               p = p->pListNext;
00824        }
00825        target->pInternalPointer = target->pListHead;
00826 }
00827 
00828 
00829 static zend_bool zend_hash_replace_checker_wrapper(HashTable *target, void *source_data, Bucket *p, void *pParam, merge_checker_func_t merge_checker_func)
00830 {
00831        zend_hash_key hash_key;
00832 
00833        hash_key.arKey = p->arKey;
00834        hash_key.nKeyLength = p->nKeyLength;
00835        hash_key.h = p->h;
00836        return merge_checker_func(target, source_data, &hash_key, pParam);
00837 }
00838 
00839 
00840 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)
00841 {
00842        Bucket *p;
00843        void *t;
00844 
00845        IS_CONSISTENT(source);
00846        IS_CONSISTENT(target);
00847 
00848        p = source->pListHead;
00849        while (p) {
00850               if (zend_hash_replace_checker_wrapper(target, p->pData, p, pParam, pMergeSource)) {
00851                      if (zend_hash_quick_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &t)==SUCCESS && pCopyConstructor) {
00852                             pCopyConstructor(t);
00853                      }
00854               }
00855               p = p->pListNext;
00856        }
00857        target->pInternalPointer = target->pListHead;
00858 }
00859 
00860 
00861 ZEND_API ulong zend_get_hash_value(const char *arKey, uint nKeyLength)
00862 {
00863        return zend_inline_hash_func(arKey, nKeyLength);
00864 }
00865 
00866 
00867 /* Returns SUCCESS if found and FAILURE if not. The pointer to the
00868  * data is returned in pData. The reason is that there's no reason
00869  * someone using the hash table might not want to have NULL data
00870  */
00871 ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData)
00872 {
00873        ulong h;
00874        uint nIndex;
00875        Bucket *p;
00876 
00877        IS_CONSISTENT(ht);
00878 
00879        h = zend_inline_hash_func(arKey, nKeyLength);
00880        nIndex = h & ht->nTableMask;
00881 
00882        p = ht->arBuckets[nIndex];
00883        while (p != NULL) {
00884               if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
00885                      if (!memcmp(p->arKey, arKey, nKeyLength)) {
00886                             *pData = p->pData;
00887                             return SUCCESS;
00888                      }
00889               }
00890               p = p->pNext;
00891        }
00892        return FAILURE;
00893 }
00894 
00895 
00896 ZEND_API int zend_hash_quick_find(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h, void **pData)
00897 {
00898        uint nIndex;
00899        Bucket *p;
00900 
00901        if (nKeyLength==0) {
00902               return zend_hash_index_find(ht, h, pData);
00903        }
00904 
00905        IS_CONSISTENT(ht);
00906 
00907        nIndex = h & ht->nTableMask;
00908 
00909        p = ht->arBuckets[nIndex];
00910        while (p != NULL) {
00911               if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
00912                      if (!memcmp(p->arKey, arKey, nKeyLength)) {
00913                             *pData = p->pData;
00914                             return SUCCESS;
00915                      }
00916               }
00917               p = p->pNext;
00918        }
00919        return FAILURE;
00920 }
00921 
00922 
00923 ZEND_API int zend_hash_exists(const HashTable *ht, const char *arKey, uint nKeyLength)
00924 {
00925        ulong h;
00926        uint nIndex;
00927        Bucket *p;
00928 
00929        IS_CONSISTENT(ht);
00930 
00931        h = zend_inline_hash_func(arKey, nKeyLength);
00932        nIndex = h & ht->nTableMask;
00933 
00934        p = ht->arBuckets[nIndex];
00935        while (p != NULL) {
00936               if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
00937                      if (!memcmp(p->arKey, arKey, nKeyLength)) {
00938                             return 1;
00939                      }
00940               }
00941               p = p->pNext;
00942        }
00943        return 0;
00944 }
00945 
00946 
00947 ZEND_API int zend_hash_quick_exists(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h)
00948 {
00949        uint nIndex;
00950        Bucket *p;
00951 
00952        if (nKeyLength==0) {
00953               return zend_hash_index_exists(ht, h);
00954        }
00955 
00956        IS_CONSISTENT(ht);
00957 
00958        nIndex = h & ht->nTableMask;
00959 
00960        p = ht->arBuckets[nIndex];
00961        while (p != NULL) {
00962               if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
00963                      if (!memcmp(p->arKey, arKey, nKeyLength)) {
00964                             return 1;
00965                      }
00966               }
00967               p = p->pNext;
00968        }
00969        return 0;
00970 
00971 }
00972 
00973 
00974 ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData)
00975 {
00976        uint nIndex;
00977        Bucket *p;
00978 
00979        IS_CONSISTENT(ht);
00980 
00981        nIndex = h & ht->nTableMask;
00982 
00983        p = ht->arBuckets[nIndex];
00984        while (p != NULL) {
00985               if ((p->h == h) && (p->nKeyLength == 0)) {
00986                      *pData = p->pData;
00987                      return SUCCESS;
00988               }
00989               p = p->pNext;
00990        }
00991        return FAILURE;
00992 }
00993 
00994 
00995 ZEND_API int zend_hash_index_exists(const HashTable *ht, ulong h)
00996 {
00997        uint nIndex;
00998        Bucket *p;
00999 
01000        IS_CONSISTENT(ht);
01001 
01002        nIndex = h & ht->nTableMask;
01003 
01004        p = ht->arBuckets[nIndex];
01005        while (p != NULL) {
01006               if ((p->h == h) && (p->nKeyLength == 0)) {
01007                      return 1;
01008               }
01009               p = p->pNext;
01010        }
01011        return 0;
01012 }
01013 
01014 
01015 ZEND_API int zend_hash_num_elements(const HashTable *ht)
01016 {
01017        IS_CONSISTENT(ht);
01018 
01019        return ht->nNumOfElements;
01020 }
01021 
01022 
01023 ZEND_API int zend_hash_get_pointer(const HashTable *ht, HashPointer *ptr)
01024 {
01025        ptr->pos = ht->pInternalPointer;
01026        if (ht->pInternalPointer) {
01027               ptr->h = ht->pInternalPointer->h;
01028               return 1;
01029        } else {
01030               ptr->h = 0;
01031               return 0;
01032        }
01033 }
01034 
01035 ZEND_API int zend_hash_set_pointer(HashTable *ht, const HashPointer *ptr)
01036 {
01037        if (ptr->pos == NULL) {
01038               ht->pInternalPointer = NULL;
01039        } else if (ht->pInternalPointer != ptr->pos) {
01040               Bucket *p;
01041 
01042               IS_CONSISTENT(ht);
01043               p = ht->arBuckets[ptr->h & ht->nTableMask];
01044               while (p != NULL) {
01045                      if (p == ptr->pos) {
01046                             ht->pInternalPointer = p;
01047                             return 1;
01048                      }
01049                      p = p->pNext;
01050               }
01051               return 0;
01052        }
01053        return 1;
01054 }
01055 
01056 ZEND_API void zend_hash_internal_pointer_reset_ex(HashTable *ht, HashPosition *pos)
01057 {
01058        IS_CONSISTENT(ht);
01059 
01060        if (pos)
01061               *pos = ht->pListHead;
01062        else
01063               ht->pInternalPointer = ht->pListHead;
01064 }
01065 
01066 
01067 /* This function will be extremely optimized by remembering 
01068  * the end of the list
01069  */
01070 ZEND_API void zend_hash_internal_pointer_end_ex(HashTable *ht, HashPosition *pos)
01071 {
01072        IS_CONSISTENT(ht);
01073 
01074        if (pos)
01075               *pos = ht->pListTail;
01076        else
01077               ht->pInternalPointer = ht->pListTail;
01078 }
01079 
01080 
01081 ZEND_API int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos)
01082 {
01083        HashPosition *current = pos ? pos : &ht->pInternalPointer;
01084 
01085        IS_CONSISTENT(ht);
01086 
01087        if (*current) {
01088               *current = (*current)->pListNext;
01089               return SUCCESS;
01090        } else
01091               return FAILURE;
01092 }
01093 
01094 ZEND_API int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos)
01095 {
01096        HashPosition *current = pos ? pos : &ht->pInternalPointer;
01097 
01098        IS_CONSISTENT(ht);
01099 
01100        if (*current) {
01101               *current = (*current)->pListLast;
01102               return SUCCESS;
01103        } else
01104               return FAILURE;
01105 }
01106 
01107 
01108 /* This function should be made binary safe  */
01109 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)
01110 {
01111        Bucket *p;
01112 
01113        p = pos ? (*pos) : ht->pInternalPointer;
01114 
01115        IS_CONSISTENT(ht);
01116 
01117        if (p) {
01118               if (p->nKeyLength) {
01119                      if (duplicate) {
01120                             *str_index = estrndup(p->arKey, p->nKeyLength - 1);
01121                      } else {
01122                             *str_index = p->arKey;
01123                      }
01124                      if (str_length) {
01125                             *str_length = p->nKeyLength;
01126                      }
01127                      return HASH_KEY_IS_STRING;
01128               } else {
01129                      *num_index = p->h;
01130                      return HASH_KEY_IS_LONG;
01131               }
01132        }
01133        return HASH_KEY_NON_EXISTANT;
01134 }
01135 
01136 
01137 ZEND_API int zend_hash_get_current_key_type_ex(HashTable *ht, HashPosition *pos)
01138 {
01139        Bucket *p;
01140 
01141        p = pos ? (*pos) : ht->pInternalPointer;
01142 
01143        IS_CONSISTENT(ht);
01144 
01145        if (p) {
01146               if (p->nKeyLength) {
01147                      return HASH_KEY_IS_STRING;
01148               } else {
01149                      return HASH_KEY_IS_LONG;
01150               }
01151        }
01152        return HASH_KEY_NON_EXISTANT;
01153 }
01154 
01155 
01156 ZEND_API int zend_hash_get_current_data_ex(HashTable *ht, void **pData, HashPosition *pos)
01157 {
01158        Bucket *p;
01159 
01160        p = pos ? (*pos) : ht->pInternalPointer;
01161 
01162        IS_CONSISTENT(ht);
01163 
01164        if (p) {
01165               *pData = p->pData;
01166               return SUCCESS;
01167        } else {
01168               return FAILURE;
01169        }
01170 }
01171 
01172 /* This function changes key of current element without changing elements'
01173  * order. If element with target key already exists, it will be deleted first.
01174  */
01175 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)
01176 {
01177        Bucket *p, *q;
01178 
01179        p = pos ? (*pos) : ht->pInternalPointer;
01180 
01181        IS_CONSISTENT(ht);
01182 
01183        if (p) {
01184               if (key_type == HASH_KEY_IS_LONG) {
01185                      str_length = 0;
01186                      if (!p->nKeyLength && p->h == num_index) {
01187                             return SUCCESS;
01188                      }
01189 
01190                      q = ht->arBuckets[num_index & ht->nTableMask];
01191                      while (q != NULL) {
01192                             if (!q->nKeyLength && q->h == num_index) {
01193                                    break;
01194                             }
01195                             q = q->pNext;
01196                      }
01197               } else if (key_type == HASH_KEY_IS_STRING) {
01198                      ulong h;
01199 
01200                      if (p->nKeyLength == str_length &&
01201                          memcmp(p->arKey, str_index, str_length) == 0) {
01202                             return SUCCESS;
01203                      }
01204 
01205                      h = zend_inline_hash_func(str_index, str_length);
01206                      q = ht->arBuckets[h & ht->nTableMask];
01207 
01208                      while (q != NULL) {
01209                             if (q->h == h && q->nKeyLength == str_length && 
01210                                        memcmp(q->arKey, str_index, str_length) == 0) {
01211                                    break;
01212                             }
01213                             q = q->pNext;
01214                      }
01215               } else {
01216                      return FAILURE;
01217               }
01218 
01219               HANDLE_BLOCK_INTERRUPTIONS();
01220 
01221               if (q) {
01222                      if (mode != HASH_UPDATE_KEY_ANYWAY) {
01223                             Bucket *r = p->pListLast;
01224                             int found = HASH_UPDATE_KEY_IF_BEFORE;
01225                                           
01226                             while (r) {
01227                                    if (r == q) {
01228                                           found = HASH_UPDATE_KEY_IF_AFTER;
01229                                           break;
01230                                    }
01231                                    r = r->pListLast;
01232                             }
01233                             if (mode & found) {
01234                                    /* delete current bucket */
01235                                    if (p == ht->arBuckets[p->h & ht->nTableMask]) {
01236                                           ht->arBuckets[p->h & ht->nTableMask] = p->pNext;
01237                                    } else {
01238                                           p->pLast->pNext = p->pNext;
01239                                    }
01240                                    if (p->pNext) {
01241                                           p->pNext->pLast = p->pLast;
01242                                    }
01243                                    if (p->pListLast != NULL) {
01244                                           p->pListLast->pListNext = p->pListNext;
01245                                    } else { 
01246                                           /* Deleting the head of the list */
01247                                           ht->pListHead = p->pListNext;
01248                                    }
01249                                    if (p->pListNext != NULL) {
01250                                           p->pListNext->pListLast = p->pListLast;
01251                                    } else {
01252                                           ht->pListTail = p->pListLast;
01253                                    }
01254                                    if (ht->pInternalPointer == p) {
01255                                           ht->pInternalPointer = p->pListNext;
01256                                    }
01257                                    if (ht->pDestructor) {
01258                                           ht->pDestructor(p->pData);
01259                                    }
01260                                    if (p->pData != &p->pDataPtr) {
01261                                           pefree(p->pData, ht->persistent);
01262                                    }
01263                                    pefree(p, ht->persistent);
01264                                    ht->nNumOfElements--;
01265                                    HANDLE_UNBLOCK_INTERRUPTIONS();
01266                                    return FAILURE;
01267                             }
01268                      }
01269                      /* delete another bucket with the same key */
01270                      if (q == ht->arBuckets[q->h & ht->nTableMask]) {
01271                             ht->arBuckets[q->h & ht->nTableMask] = q->pNext;
01272                      } else {
01273                             q->pLast->pNext = q->pNext;
01274                      }
01275                      if (q->pNext) {
01276                             q->pNext->pLast = q->pLast;
01277                      }
01278                      if (q->pListLast != NULL) {
01279                             q->pListLast->pListNext = q->pListNext;
01280                      } else { 
01281                             /* Deleting the head of the list */
01282                             ht->pListHead = q->pListNext;
01283                      }
01284                      if (q->pListNext != NULL) {
01285                             q->pListNext->pListLast = q->pListLast;
01286                      } else {
01287                             ht->pListTail = q->pListLast;
01288                      }
01289                      if (ht->pInternalPointer == q) {
01290                             ht->pInternalPointer = q->pListNext;
01291                      }
01292                      if (ht->pDestructor) {
01293                             ht->pDestructor(q->pData);
01294                      }
01295                      if (q->pData != &q->pDataPtr) {
01296                             pefree(q->pData, ht->persistent);
01297                      }
01298                      pefree(q, ht->persistent);
01299                      ht->nNumOfElements--;
01300               }
01301 
01302               if (p->pNext) {
01303                      p->pNext->pLast = p->pLast;
01304               }
01305               if (p->pLast) {
01306                      p->pLast->pNext = p->pNext;
01307               } else {
01308                      ht->arBuckets[p->h & ht->nTableMask] = p->pNext;
01309               }
01310 
01311               if (p->nKeyLength != str_length) {
01312                      Bucket *q = (Bucket *) pemalloc(sizeof(Bucket) - 1 + str_length, ht->persistent);
01313 
01314                      q->nKeyLength = str_length;
01315                      if (p->pData == &p->pDataPtr) {
01316                             q->pData = &q->pDataPtr;
01317                      } else {
01318                             q->pData = p->pData;
01319                      }
01320                      q->pDataPtr = p->pDataPtr;
01321                      q->pListNext = p->pListNext;
01322                      q->pListLast = p->pListLast;
01323                      if (q->pListNext) {
01324                             p->pListNext->pListLast = q;
01325                      } else {
01326                             ht->pListTail = q;
01327                      }
01328                      if (q->pListLast) {
01329                             p->pListLast->pListNext = q;
01330                      } else {
01331                             ht->pListHead = q;
01332                      }
01333                      if (ht->pInternalPointer == p) {
01334                             ht->pInternalPointer = q;
01335                      }
01336                      if (pos) {
01337                             *pos = q;
01338                      }
01339                      pefree(p, ht->persistent);
01340                      p = q;
01341               }
01342 
01343               if (key_type == HASH_KEY_IS_LONG) {
01344                      p->h = num_index;
01345               } else {
01346                      memcpy(p->arKey, str_index, str_length);
01347                      p->h = zend_inline_hash_func(str_index, str_length);
01348               }
01349 
01350               CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[p->h & ht->nTableMask]);
01351               ht->arBuckets[p->h & ht->nTableMask] = p;
01352               HANDLE_UNBLOCK_INTERRUPTIONS();
01353 
01354               return SUCCESS;
01355        } else {
01356               return FAILURE;
01357        }
01358 }
01359 
01360 ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func,
01361                                                  compare_func_t compar, int renumber TSRMLS_DC)
01362 {
01363        Bucket **arTmp;
01364        Bucket *p;
01365        int i, j;
01366 
01367        IS_CONSISTENT(ht);
01368 
01369        if (!(ht->nNumOfElements>1) && !(renumber && ht->nNumOfElements>0)) { /* Doesn't require sorting */
01370               return SUCCESS;
01371        }
01372        arTmp = (Bucket **) pemalloc(ht->nNumOfElements * sizeof(Bucket *), ht->persistent);
01373        if (!arTmp) {
01374               return FAILURE;
01375        }
01376        p = ht->pListHead;
01377        i = 0;
01378        while (p) {
01379               arTmp[i] = p;
01380               p = p->pListNext;
01381               i++;
01382        }
01383 
01384        (*sort_func)((void *) arTmp, i, sizeof(Bucket *), compar TSRMLS_CC);
01385 
01386        HANDLE_BLOCK_INTERRUPTIONS();
01387        ht->pListHead = arTmp[0];
01388        ht->pListTail = NULL;
01389        ht->pInternalPointer = ht->pListHead;
01390 
01391        arTmp[0]->pListLast = NULL;
01392        if (i > 1) {
01393               arTmp[0]->pListNext = arTmp[1];
01394               for (j = 1; j < i-1; j++) {
01395                      arTmp[j]->pListLast = arTmp[j-1];
01396                      arTmp[j]->pListNext = arTmp[j+1];
01397               }
01398               arTmp[j]->pListLast = arTmp[j-1];
01399               arTmp[j]->pListNext = NULL;
01400        } else {
01401               arTmp[0]->pListNext = NULL;
01402        }
01403        ht->pListTail = arTmp[i-1];
01404 
01405        pefree(arTmp, ht->persistent);
01406        HANDLE_UNBLOCK_INTERRUPTIONS();
01407 
01408        if (renumber) {
01409               p = ht->pListHead;
01410               i=0;
01411               while (p != NULL) {
01412                      p->nKeyLength = 0;
01413                      p->h = i++;
01414                      p = p->pListNext;
01415               }
01416               ht->nNextFreeElement = i;
01417               zend_hash_rehash(ht);
01418        }
01419        return SUCCESS;
01420 }
01421 
01422 
01423 ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered TSRMLS_DC)
01424 {
01425        Bucket *p1, *p2 = NULL;
01426        int result;
01427        void *pData2;
01428 
01429        IS_CONSISTENT(ht1);
01430        IS_CONSISTENT(ht2);
01431 
01432        HASH_PROTECT_RECURSION(ht1); 
01433        HASH_PROTECT_RECURSION(ht2); 
01434 
01435        result = ht1->nNumOfElements - ht2->nNumOfElements;
01436        if (result!=0) {
01437               HASH_UNPROTECT_RECURSION(ht1); 
01438               HASH_UNPROTECT_RECURSION(ht2); 
01439               return result;
01440        }
01441 
01442        p1 = ht1->pListHead;
01443        if (ordered) {
01444               p2 = ht2->pListHead;
01445        }
01446 
01447        while (p1) {
01448               if (ordered && !p2) {
01449                      HASH_UNPROTECT_RECURSION(ht1); 
01450                      HASH_UNPROTECT_RECURSION(ht2); 
01451                      return 1; /* That's not supposed to happen */
01452               }
01453               if (ordered) {
01454                      if (p1->nKeyLength==0 && p2->nKeyLength==0) { /* numeric indices */
01455                             result = p1->h - p2->h;
01456                             if (result!=0) {
01457                                    HASH_UNPROTECT_RECURSION(ht1); 
01458                                    HASH_UNPROTECT_RECURSION(ht2); 
01459                                    return result;
01460                             }
01461                      } else { /* string indices */
01462                             result = p1->nKeyLength - p2->nKeyLength;
01463                             if (result!=0) {
01464                                    HASH_UNPROTECT_RECURSION(ht1); 
01465                                    HASH_UNPROTECT_RECURSION(ht2); 
01466                                    return result;
01467                             }
01468                             result = memcmp(p1->arKey, p2->arKey, p1->nKeyLength);
01469                             if (result!=0) {
01470                                    HASH_UNPROTECT_RECURSION(ht1); 
01471                                    HASH_UNPROTECT_RECURSION(ht2); 
01472                                    return result;
01473                             }
01474                      }
01475                      pData2 = p2->pData;
01476               } else {
01477                      if (p1->nKeyLength==0) { /* numeric index */
01478                             if (zend_hash_index_find(ht2, p1->h, &pData2)==FAILURE) {
01479                                    HASH_UNPROTECT_RECURSION(ht1); 
01480                                    HASH_UNPROTECT_RECURSION(ht2); 
01481                                    return 1;
01482                             }
01483                      } else { /* string index */
01484                             if (zend_hash_quick_find(ht2, p1->arKey, p1->nKeyLength, p1->h, &pData2)==FAILURE) {
01485                                    HASH_UNPROTECT_RECURSION(ht1); 
01486                                    HASH_UNPROTECT_RECURSION(ht2); 
01487                                    return 1;
01488                             }
01489                      }
01490               }
01491               result = compar(p1->pData, pData2 TSRMLS_CC);
01492               if (result!=0) {
01493                      HASH_UNPROTECT_RECURSION(ht1); 
01494                      HASH_UNPROTECT_RECURSION(ht2); 
01495                      return result;
01496               }
01497               p1 = p1->pListNext;
01498               if (ordered) {
01499                      p2 = p2->pListNext;
01500               }
01501        }
01502        
01503        HASH_UNPROTECT_RECURSION(ht1); 
01504        HASH_UNPROTECT_RECURSION(ht2); 
01505        return 0;
01506 }
01507 
01508 
01509 ZEND_API int zend_hash_minmax(const HashTable *ht, compare_func_t compar, int flag, void **pData TSRMLS_DC)
01510 {
01511        Bucket *p, *res;
01512 
01513        IS_CONSISTENT(ht);
01514 
01515        if (ht->nNumOfElements == 0 ) {
01516               *pData=NULL;
01517               return FAILURE;
01518        }
01519 
01520        res = p = ht->pListHead;
01521        while ((p = p->pListNext)) {
01522               if (flag) {
01523                      if (compar(&res, &p TSRMLS_CC) < 0) { /* max */
01524                             res = p;
01525                      }
01526               } else {
01527                      if (compar(&res, &p TSRMLS_CC) > 0) { /* min */
01528                             res = p;
01529                      }
01530               }
01531        }
01532        *pData = res->pData;
01533        return SUCCESS;
01534 }
01535 
01536 ZEND_API ulong zend_hash_next_free_element(const HashTable *ht)
01537 {
01538        IS_CONSISTENT(ht);
01539 
01540        return ht->nNextFreeElement;
01541 
01542 }
01543 
01544 
01545 #if ZEND_DEBUG
01546 void zend_hash_display_pListTail(const HashTable *ht)
01547 {
01548        Bucket *p;
01549 
01550        p = ht->pListTail;
01551        while (p != NULL) {
01552               zend_output_debug_string(0, "pListTail has key %s\n", p->arKey);
01553               p = p->pListLast;
01554        }
01555 }
01556 
01557 void zend_hash_display(const HashTable *ht)
01558 {
01559        Bucket *p;
01560        uint i;
01561 
01562        for (i = 0; i < ht->nTableSize; i++) {
01563               p = ht->arBuckets[i];
01564               while (p != NULL) {
01565                      zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h);
01566                      p = p->pNext;
01567               }
01568        }
01569 
01570        p = ht->pListTail;
01571        while (p != NULL) {
01572               zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h);
01573               p = p->pListLast;
01574        }
01575 }
01576 #endif
01577 
01578 /*
01579  * Local variables:
01580  * tab-width: 4
01581  * c-basic-offset: 4
01582  * indent-tabs-mode: t
01583  * End:
01584  */