LTP GCOV extension - code coverage report
Current view: directory - Zend - zend_hash.c
Test: PHP Code Coverage
Date: 2007-04-10 Instrumented lines: 651
Code covered: 76.8 % Executed lines: 500
Legend: not executed executed

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

Generated by: LTP GCOV extension version 1.5