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