PHP  
 PHP: Test and Code Coverage Analysis
downloads | QA | documentation | faq | getting help | mailing lists | reporting bugs | php.net sites | links | my php.net 
 

LCOV - code coverage report
Current view: top level - Zend - zend_hash.c (source / functions) Hit Total Coverage
Test: PHP Code Coverage Lines: 0 694 0.0 %
Date: 2014-04-16 Functions: 0 48 0.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.10

Generated at Wed, 16 Apr 2014 12:47:45 +0000 (12 hours ago)

Copyright © 2005-2014 The PHP Group
All rights reserved.