This source file includes following definitions.
- _zend_is_inconsistent
- zend_hash_func
- i_zend_hash_bucket_delete
- zend_hash_bucket_delete
- _zend_hash_init
- _zend_hash_init_ex
- zend_hash_set_apply_protection
- _zend_hash_add_or_update
- _zend_hash_quick_add_or_update
- zend_hash_add_empty_element
- _zend_hash_index_update_or_next_insert
- zend_hash_do_resize
- zend_hash_rehash
- zend_hash_reindex
- zend_hash_del_key_or_index
- zend_hash_destroy
- zend_hash_clean
- zend_hash_graceful_destroy
- zend_hash_graceful_reverse_destroy
- zend_hash_apply
- zend_hash_apply_with_argument
- zend_hash_apply_with_arguments
- zend_hash_reverse_apply
- zend_hash_copy
- _zend_hash_merge
- zend_hash_replace_checker_wrapper
- zend_hash_merge_ex
- zend_hash_find
- zend_hash_quick_find
- zend_hash_exists
- zend_hash_quick_exists
- zend_hash_index_find
- zend_hash_index_exists
- zend_hash_num_elements
- zend_hash_get_pointer
- zend_hash_set_pointer
- zend_hash_internal_pointer_reset_ex
- zend_hash_internal_pointer_end_ex
- zend_hash_move_forward_ex
- zend_hash_move_backwards_ex
- zend_hash_get_current_key_ex
- zend_hash_get_current_key_zval_ex
- zend_hash_get_current_key_type_ex
- zend_hash_get_current_data_ex
- zend_hash_update_current_key_ex
- _zend_hash_splice
- zend_hash_sort
- zend_hash_compare
- zend_hash_minmax
- zend_hash_next_free_element
- zend_hash_display_pListTail
- zend_hash_display
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 ZEND_API ulong zend_hash_func(const char *arKey, uint nKeyLength)
108 {
109 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 \
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 HANDLE_BLOCK_INTERRUPTIONS();
157 if (p->pLast) {
158 p->pLast->pNext = p->pNext;
159 } else {
160 ht->arBuckets[p->h & ht->nTableMask] = p->pNext;
161 }
162 if (p->pNext) {
163 p->pNext->pLast = p->pLast;
164 }
165 if (p->pListLast != NULL) {
166 p->pListLast->pListNext = p->pListNext;
167 } else {
168
169 ht->pListHead = p->pListNext;
170 }
171 if (p->pListNext != NULL) {
172 p->pListNext->pListLast = p->pListLast;
173 } else {
174
175 ht->pListTail = p->pListLast;
176 }
177 if (ht->pInternalPointer == p) {
178 ht->pInternalPointer = p->pListNext;
179 }
180 ht->nNumOfElements--;
181 if (ht->pDestructor) {
182 ht->pDestructor(p->pData);
183 }
184 if (p->pData != &p->pDataPtr) {
185 pefree(p->pData, ht->persistent);
186 }
187 pefree(p, ht->persistent);
188 HANDLE_UNBLOCK_INTERRUPTIONS();
189 }
190
191 static void zend_hash_bucket_delete(HashTable *ht, Bucket *p) {
192 i_zend_hash_bucket_delete(ht, p);
193 }
194
195 ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
196 {
197 uint i = 3;
198
199 SET_INCONSISTENT(HT_OK);
200
201 if (nSize >= 0x80000000) {
202
203 ht->nTableSize = 0x80000000;
204 } else {
205 while ((1U << i) < nSize) {
206 i++;
207 }
208 ht->nTableSize = 1 << i;
209 }
210
211 ht->nTableMask = 0;
212 ht->pDestructor = pDestructor;
213 ht->arBuckets = (Bucket**)&uninitialized_bucket;
214 ht->pListHead = NULL;
215 ht->pListTail = NULL;
216 ht->nNumOfElements = 0;
217 ht->nNextFreeElement = 0;
218 ht->pInternalPointer = NULL;
219 ht->persistent = persistent;
220 ht->nApplyCount = 0;
221 ht->bApplyProtection = 1;
222 return SUCCESS;
223 }
224
225
226 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 int retval = _zend_hash_init(ht, nSize, pDestructor, persistent ZEND_FILE_LINE_CC);
229
230 ht->bApplyProtection = bApplyProtection;
231 return retval;
232 }
233
234
235 ZEND_API void zend_hash_set_apply_protection(HashTable *ht, zend_bool bApplyProtection)
236 {
237 ht->bApplyProtection = bApplyProtection;
238 }
239
240
241
242 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 CHECK_INIT(ht);
256
257 h = zend_inline_hash_func(arKey, nKeyLength);
258 nIndex = h & ht->nTableMask;
259
260 p = ht->arBuckets[nIndex];
261 while (p != NULL) {
262 if (p->arKey == arKey ||
263 ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
264 if (flag & HASH_ADD) {
265 return FAILURE;
266 }
267 ZEND_ASSERT(p->pData != pData);
268 HANDLE_BLOCK_INTERRUPTIONS();
269 if (ht->pDestructor) {
270 ht->pDestructor(p->pData);
271 }
272 UPDATE_DATA(ht, p, pData, nDataSize);
273 if (pDest) {
274 *pDest = p->pData;
275 }
276 HANDLE_UNBLOCK_INTERRUPTIONS();
277 return SUCCESS;
278 }
279 p = p->pNext;
280 }
281
282 if (IS_INTERNED(arKey)) {
283 p = (Bucket *) pemalloc(sizeof(Bucket), ht->persistent);
284 p->arKey = arKey;
285 } else {
286 p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent);
287 p->arKey = (const char*)(p + 1);
288 memcpy((char*)p->arKey, arKey, nKeyLength);
289 }
290 p->nKeyLength = nKeyLength;
291 INIT_DATA(ht, p, pData, nDataSize);
292 p->h = h;
293 CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
294 if (pDest) {
295 *pDest = p->pData;
296 }
297
298 HANDLE_BLOCK_INTERRUPTIONS();
299 CONNECT_TO_GLOBAL_DLLIST(p, ht);
300 ht->arBuckets[nIndex] = p;
301 HANDLE_UNBLOCK_INTERRUPTIONS();
302
303 ht->nNumOfElements++;
304 ZEND_HASH_IF_FULL_DO_RESIZE(ht);
305 return SUCCESS;
306 }
307
308 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 CHECK_INIT(ht);
321 nIndex = h & ht->nTableMask;
322
323 p = ht->arBuckets[nIndex];
324 while (p != NULL) {
325 if (p->arKey == arKey ||
326 ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
327 if (flag & HASH_ADD) {
328 return FAILURE;
329 }
330 ZEND_ASSERT(p->pData != pData);
331 HANDLE_BLOCK_INTERRUPTIONS();
332 if (ht->pDestructor) {
333 ht->pDestructor(p->pData);
334 }
335 UPDATE_DATA(ht, p, pData, nDataSize);
336 if (pDest) {
337 *pDest = p->pData;
338 }
339 HANDLE_UNBLOCK_INTERRUPTIONS();
340 return SUCCESS;
341 }
342 p = p->pNext;
343 }
344
345 if (IS_INTERNED(arKey)) {
346 p = (Bucket *) pemalloc(sizeof(Bucket), ht->persistent);
347 p->arKey = arKey;
348 } else {
349 p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent);
350 p->arKey = (const char*)(p + 1);
351 memcpy((char*)p->arKey, arKey, nKeyLength);
352 }
353
354 p->nKeyLength = nKeyLength;
355 INIT_DATA(ht, p, pData, nDataSize);
356 p->h = h;
357
358 CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
359
360 if (pDest) {
361 *pDest = p->pData;
362 }
363
364 HANDLE_BLOCK_INTERRUPTIONS();
365 ht->arBuckets[nIndex] = p;
366 CONNECT_TO_GLOBAL_DLLIST(p, ht);
367 HANDLE_UNBLOCK_INTERRUPTIONS();
368
369 ht->nNumOfElements++;
370 ZEND_HASH_IF_FULL_DO_RESIZE(ht);
371 return SUCCESS;
372 }
373
374
375 ZEND_API int zend_hash_add_empty_element(HashTable *ht, const char *arKey, uint nKeyLength)
376 {
377 void *dummy = (void *) 1;
378
379 return zend_hash_add(ht, arKey, nKeyLength, &dummy, sizeof(void *), NULL);
380 }
381
382
383 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 CHECK_INIT(ht);
393
394 if (flag & HASH_NEXT_INSERT) {
395 h = ht->nNextFreeElement;
396 }
397 nIndex = h & ht->nTableMask;
398
399 p = ht->arBuckets[nIndex];
400 while (p != NULL) {
401 if ((p->nKeyLength == 0) && (p->h == h)) {
402 if (flag & HASH_NEXT_INSERT || flag & HASH_ADD) {
403 return FAILURE;
404 }
405 ZEND_ASSERT(p->pData != pData);
406 HANDLE_BLOCK_INTERRUPTIONS();
407 if (ht->pDestructor) {
408 ht->pDestructor(p->pData);
409 }
410 UPDATE_DATA(ht, p, pData, nDataSize);
411 HANDLE_UNBLOCK_INTERRUPTIONS();
412 if (pDest) {
413 *pDest = p->pData;
414 }
415 return SUCCESS;
416 }
417 p = p->pNext;
418 }
419 p = (Bucket *) pemalloc_rel(sizeof(Bucket), ht->persistent);
420 p->arKey = NULL;
421 p->nKeyLength = 0;
422 p->h = h;
423 INIT_DATA(ht, p, pData, nDataSize);
424 if (pDest) {
425 *pDest = p->pData;
426 }
427
428 CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
429
430 HANDLE_BLOCK_INTERRUPTIONS();
431 ht->arBuckets[nIndex] = p;
432 CONNECT_TO_GLOBAL_DLLIST(p, ht);
433 HANDLE_UNBLOCK_INTERRUPTIONS();
434
435 if ((long)h >= (long)ht->nNextFreeElement) {
436 ht->nNextFreeElement = h < LONG_MAX ? h + 1 : LONG_MAX;
437 }
438 ht->nNumOfElements++;
439 ZEND_HASH_IF_FULL_DO_RESIZE(ht);
440 return SUCCESS;
441 }
442
443
444 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 if ((ht->nTableSize << 1) > 0) {
454 t = (Bucket **) perealloc(ht->arBuckets, (ht->nTableSize << 1) * sizeof(Bucket *), ht->persistent);
455 HANDLE_BLOCK_INTERRUPTIONS();
456 ht->arBuckets = t;
457 ht->nTableSize = (ht->nTableSize << 1);
458 ht->nTableMask = ht->nTableSize - 1;
459 zend_hash_rehash(ht);
460 HANDLE_UNBLOCK_INTERRUPTIONS();
461 }
462 }
463
464 ZEND_API int zend_hash_rehash(HashTable *ht)
465 {
466 Bucket *p;
467 uint nIndex;
468
469 IS_CONSISTENT(ht);
470 if (UNEXPECTED(ht->nNumOfElements == 0)) {
471 return SUCCESS;
472 }
473
474 memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
475 for (p = ht->pListHead; p != NULL; p = p->pListNext) {
476 nIndex = p->h & ht->nTableMask;
477 CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
478 ht->arBuckets[nIndex] = p;
479 }
480 return SUCCESS;
481 }
482
483 ZEND_API void zend_hash_reindex(HashTable *ht, zend_bool only_integer_keys) {
484 Bucket *p;
485 uint nIndex;
486 ulong offset = 0;
487
488 IS_CONSISTENT(ht);
489 if (UNEXPECTED(ht->nNumOfElements == 0)) {
490 ht->nNextFreeElement = 0;
491 return;
492 }
493
494 memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
495 for (p = ht->pListHead; p != NULL; p = p->pListNext) {
496 if (!only_integer_keys || p->nKeyLength == 0) {
497 p->h = offset++;
498 p->nKeyLength = 0;
499 }
500
501 nIndex = p->h & ht->nTableMask;
502 CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
503 ht->arBuckets[nIndex] = p;
504 }
505 ht->nNextFreeElement = offset;
506 }
507
508 ZEND_API int zend_hash_del_key_or_index(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, int flag)
509 {
510 uint nIndex;
511 Bucket *p;
512
513 IS_CONSISTENT(ht);
514
515 if (flag == HASH_DEL_KEY) {
516 h = zend_inline_hash_func(arKey, nKeyLength);
517 }
518 nIndex = h & ht->nTableMask;
519
520 p = ht->arBuckets[nIndex];
521 while (p != NULL) {
522 if ((p->h == h)
523 && (p->nKeyLength == nKeyLength)
524 && ((p->nKeyLength == 0)
525 || !memcmp(p->arKey, arKey, nKeyLength))) {
526 i_zend_hash_bucket_delete(ht, p);
527 return SUCCESS;
528 }
529 p = p->pNext;
530 }
531 return FAILURE;
532 }
533
534
535 ZEND_API void zend_hash_destroy(HashTable *ht)
536 {
537 Bucket *p, *q;
538
539 IS_CONSISTENT(ht);
540
541 SET_INCONSISTENT(HT_IS_DESTROYING);
542
543 p = ht->pListHead;
544 while (p != NULL) {
545 q = p;
546 p = p->pListNext;
547 if (ht->pDestructor) {
548 ht->pDestructor(q->pData);
549 }
550 if (q->pData != &q->pDataPtr) {
551 pefree(q->pData, ht->persistent);
552 }
553 pefree(q, ht->persistent);
554 }
555 if (ht->nTableMask) {
556 pefree(ht->arBuckets, ht->persistent);
557 }
558
559 SET_INCONSISTENT(HT_DESTROYED);
560 }
561
562
563 ZEND_API void zend_hash_clean(HashTable *ht)
564 {
565 Bucket *p, *q;
566
567 IS_CONSISTENT(ht);
568
569 p = ht->pListHead;
570
571 if (ht->nTableMask) {
572 memset(ht->arBuckets, 0, ht->nTableSize*sizeof(Bucket *));
573 }
574 ht->pListHead = NULL;
575 ht->pListTail = NULL;
576 ht->nNumOfElements = 0;
577 ht->nNextFreeElement = 0;
578 ht->pInternalPointer = NULL;
579
580 while (p != NULL) {
581 q = p;
582 p = p->pListNext;
583 if (ht->pDestructor) {
584 ht->pDestructor(q->pData);
585 }
586 if (q->pData != &q->pDataPtr) {
587 pefree(q->pData, ht->persistent);
588 }
589 pefree(q, ht->persistent);
590 }
591 }
592
593 ZEND_API void zend_hash_graceful_destroy(HashTable *ht)
594 {
595 IS_CONSISTENT(ht);
596
597 while (ht->pListHead != NULL) {
598 zend_hash_bucket_delete(ht, ht->pListHead);
599 }
600
601 if (ht->nTableMask) {
602 pefree(ht->arBuckets, ht->persistent);
603 }
604
605 SET_INCONSISTENT(HT_DESTROYED);
606 }
607
608 ZEND_API void zend_hash_graceful_reverse_destroy(HashTable *ht)
609 {
610 IS_CONSISTENT(ht);
611
612 while (ht->pListTail != NULL) {
613 zend_hash_bucket_delete(ht, ht->pListTail);
614 }
615
616 if (ht->nTableMask) {
617 pefree(ht->arBuckets, ht->persistent);
618 }
619
620 SET_INCONSISTENT(HT_DESTROYED);
621 }
622
623
624
625
626
627
628
629
630
631
632 ZEND_API void zend_hash_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC)
633 {
634 Bucket *p;
635
636 IS_CONSISTENT(ht);
637
638 HASH_PROTECT_RECURSION(ht);
639 p = ht->pListHead;
640 while (p != NULL) {
641 int result = apply_func(p->pData TSRMLS_CC);
642
643 Bucket *p_next = p->pListNext;
644 if (result & ZEND_HASH_APPLY_REMOVE) {
645 zend_hash_bucket_delete(ht, p);
646 }
647 p = p_next;
648
649 if (result & ZEND_HASH_APPLY_STOP) {
650 break;
651 }
652 }
653 HASH_UNPROTECT_RECURSION(ht);
654 }
655
656
657 ZEND_API void zend_hash_apply_with_argument(HashTable *ht, apply_func_arg_t apply_func, void *argument TSRMLS_DC)
658 {
659 Bucket *p;
660
661 IS_CONSISTENT(ht);
662
663 HASH_PROTECT_RECURSION(ht);
664 p = ht->pListHead;
665 while (p != NULL) {
666 int result = apply_func(p->pData, argument TSRMLS_CC);
667
668 Bucket *p_next = p->pListNext;
669 if (result & ZEND_HASH_APPLY_REMOVE) {
670 zend_hash_bucket_delete(ht, p);
671 }
672 p = p_next;
673
674 if (result & ZEND_HASH_APPLY_STOP) {
675 break;
676 }
677 }
678 HASH_UNPROTECT_RECURSION(ht);
679 }
680
681
682 ZEND_API void zend_hash_apply_with_arguments(HashTable *ht TSRMLS_DC, apply_func_args_t apply_func, int num_args, ...)
683 {
684 Bucket *p;
685 va_list args;
686 zend_hash_key hash_key;
687
688 IS_CONSISTENT(ht);
689
690 HASH_PROTECT_RECURSION(ht);
691
692 p = ht->pListHead;
693 while (p != NULL) {
694 int result;
695 Bucket *p_next;
696
697 va_start(args, num_args);
698 hash_key.arKey = p->arKey;
699 hash_key.nKeyLength = p->nKeyLength;
700 hash_key.h = p->h;
701 result = apply_func(p->pData TSRMLS_CC, num_args, args, &hash_key);
702
703 p_next = p->pListNext;
704 if (result & ZEND_HASH_APPLY_REMOVE) {
705 zend_hash_bucket_delete(ht, p);
706 }
707 p = p_next;
708
709 if (result & ZEND_HASH_APPLY_STOP) {
710 va_end(args);
711 break;
712 }
713 va_end(args);
714 }
715
716 HASH_UNPROTECT_RECURSION(ht);
717 }
718
719
720 ZEND_API void zend_hash_reverse_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC)
721 {
722 Bucket *p;
723
724 IS_CONSISTENT(ht);
725
726 HASH_PROTECT_RECURSION(ht);
727 p = ht->pListTail;
728 while (p != NULL) {
729 int result = apply_func(p->pData TSRMLS_CC);
730
731 Bucket *p_last = p->pListLast;
732 if (result & ZEND_HASH_APPLY_REMOVE) {
733 zend_hash_bucket_delete(ht, p);
734 }
735 p = p_last;
736
737 if (result & ZEND_HASH_APPLY_STOP) {
738 break;
739 }
740 }
741 HASH_UNPROTECT_RECURSION(ht);
742 }
743
744
745 ZEND_API void zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size)
746 {
747 Bucket *p;
748 void *new_entry;
749 zend_bool setTargetPointer;
750
751 IS_CONSISTENT(source);
752 IS_CONSISTENT(target);
753
754 setTargetPointer = !target->pInternalPointer;
755 p = source->pListHead;
756 while (p) {
757 if (setTargetPointer && source->pInternalPointer == p) {
758 target->pInternalPointer = NULL;
759 }
760 if (p->nKeyLength) {
761 zend_hash_quick_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &new_entry);
762 } else {
763 zend_hash_index_update(target, p->h, p->pData, size, &new_entry);
764 }
765 if (pCopyConstructor) {
766 pCopyConstructor(new_entry);
767 }
768 p = p->pListNext;
769 }
770 if (!target->pInternalPointer) {
771 target->pInternalPointer = target->pListHead;
772 }
773 }
774
775
776 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)
777 {
778 Bucket *p;
779 void *t;
780 int mode = (overwrite?HASH_UPDATE:HASH_ADD);
781
782 IS_CONSISTENT(source);
783 IS_CONSISTENT(target);
784
785 p = source->pListHead;
786 while (p) {
787 if (p->nKeyLength>0) {
788 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) {
789 pCopyConstructor(t);
790 }
791 } else {
792 if ((mode==HASH_UPDATE || !zend_hash_index_exists(target, p->h)) && zend_hash_index_update(target, p->h, p->pData, size, &t)==SUCCESS && pCopyConstructor) {
793 pCopyConstructor(t);
794 }
795 }
796 p = p->pListNext;
797 }
798 target->pInternalPointer = target->pListHead;
799 }
800
801
802 static zend_bool zend_hash_replace_checker_wrapper(HashTable *target, void *source_data, Bucket *p, void *pParam, merge_checker_func_t merge_checker_func)
803 {
804 zend_hash_key hash_key;
805
806 hash_key.arKey = p->arKey;
807 hash_key.nKeyLength = p->nKeyLength;
808 hash_key.h = p->h;
809 return merge_checker_func(target, source_data, &hash_key, pParam);
810 }
811
812
813 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)
814 {
815 Bucket *p;
816 void *t;
817
818 IS_CONSISTENT(source);
819 IS_CONSISTENT(target);
820
821 p = source->pListHead;
822 while (p) {
823 if (zend_hash_replace_checker_wrapper(target, p->pData, p, pParam, pMergeSource)) {
824 if (zend_hash_quick_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &t)==SUCCESS && pCopyConstructor) {
825 pCopyConstructor(t);
826 }
827 }
828 p = p->pListNext;
829 }
830 target->pInternalPointer = target->pListHead;
831 }
832
833
834
835
836
837
838 ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData)
839 {
840 ulong h;
841 uint nIndex;
842 Bucket *p;
843
844 IS_CONSISTENT(ht);
845
846 h = zend_inline_hash_func(arKey, nKeyLength);
847 nIndex = h & ht->nTableMask;
848
849 p = ht->arBuckets[nIndex];
850 while (p != NULL) {
851 if (p->arKey == arKey ||
852 ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
853 *pData = p->pData;
854 return SUCCESS;
855 }
856 p = p->pNext;
857 }
858 return FAILURE;
859 }
860
861
862 ZEND_API int zend_hash_quick_find(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h, void **pData)
863 {
864 uint nIndex;
865 Bucket *p;
866
867 ZEND_ASSERT(nKeyLength != 0);
868
869 IS_CONSISTENT(ht);
870
871 nIndex = h & ht->nTableMask;
872
873 p = ht->arBuckets[nIndex];
874 while (p != NULL) {
875 if (p->arKey == arKey ||
876 ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
877 *pData = p->pData;
878 return SUCCESS;
879 }
880 p = p->pNext;
881 }
882 return FAILURE;
883 }
884
885
886 ZEND_API int zend_hash_exists(const HashTable *ht, const char *arKey, uint nKeyLength)
887 {
888 ulong h;
889 uint nIndex;
890 Bucket *p;
891
892 IS_CONSISTENT(ht);
893
894 h = zend_inline_hash_func(arKey, nKeyLength);
895 nIndex = h & ht->nTableMask;
896
897 p = ht->arBuckets[nIndex];
898 while (p != NULL) {
899 if (p->arKey == arKey ||
900 ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
901 return 1;
902 }
903 p = p->pNext;
904 }
905 return 0;
906 }
907
908
909 ZEND_API int zend_hash_quick_exists(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h)
910 {
911 uint nIndex;
912 Bucket *p;
913
914 ZEND_ASSERT(nKeyLength != 0);
915
916 IS_CONSISTENT(ht);
917
918 nIndex = h & ht->nTableMask;
919
920 p = ht->arBuckets[nIndex];
921 while (p != NULL) {
922 if (p->arKey == arKey ||
923 ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
924 return 1;
925 }
926 p = p->pNext;
927 }
928 return 0;
929
930 }
931
932
933 ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData)
934 {
935 uint nIndex;
936 Bucket *p;
937
938 IS_CONSISTENT(ht);
939
940 nIndex = h & ht->nTableMask;
941
942 p = ht->arBuckets[nIndex];
943 while (p != NULL) {
944 if ((p->h == h) && (p->nKeyLength == 0)) {
945 *pData = p->pData;
946 return SUCCESS;
947 }
948 p = p->pNext;
949 }
950 return FAILURE;
951 }
952
953
954 ZEND_API int zend_hash_index_exists(const HashTable *ht, ulong h)
955 {
956 uint nIndex;
957 Bucket *p;
958
959 IS_CONSISTENT(ht);
960
961 nIndex = h & ht->nTableMask;
962
963 p = ht->arBuckets[nIndex];
964 while (p != NULL) {
965 if ((p->h == h) && (p->nKeyLength == 0)) {
966 return 1;
967 }
968 p = p->pNext;
969 }
970 return 0;
971 }
972
973
974 ZEND_API int zend_hash_num_elements(const HashTable *ht)
975 {
976 IS_CONSISTENT(ht);
977
978 return ht->nNumOfElements;
979 }
980
981
982 ZEND_API int zend_hash_get_pointer(const HashTable *ht, HashPointer *ptr)
983 {
984 ptr->pos = ht->pInternalPointer;
985 if (ht->pInternalPointer) {
986 ptr->h = ht->pInternalPointer->h;
987 return 1;
988 } else {
989 ptr->h = 0;
990 return 0;
991 }
992 }
993
994 ZEND_API int zend_hash_set_pointer(HashTable *ht, const HashPointer *ptr)
995 {
996 if (ptr->pos == NULL) {
997 ht->pInternalPointer = NULL;
998 } else if (ht->pInternalPointer != ptr->pos) {
999 Bucket *p;
1000
1001 IS_CONSISTENT(ht);
1002 p = ht->arBuckets[ptr->h & ht->nTableMask];
1003 while (p != NULL) {
1004 if (p == ptr->pos) {
1005 ht->pInternalPointer = p;
1006 return 1;
1007 }
1008 p = p->pNext;
1009 }
1010 return 0;
1011 }
1012 return 1;
1013 }
1014
1015 ZEND_API void zend_hash_internal_pointer_reset_ex(HashTable *ht, HashPosition *pos)
1016 {
1017 IS_CONSISTENT(ht);
1018
1019 if (pos)
1020 *pos = ht->pListHead;
1021 else
1022 ht->pInternalPointer = ht->pListHead;
1023 }
1024
1025
1026
1027
1028
1029 ZEND_API void zend_hash_internal_pointer_end_ex(HashTable *ht, HashPosition *pos)
1030 {
1031 IS_CONSISTENT(ht);
1032
1033 if (pos)
1034 *pos = ht->pListTail;
1035 else
1036 ht->pInternalPointer = ht->pListTail;
1037 }
1038
1039
1040 ZEND_API int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos)
1041 {
1042 HashPosition *current = pos ? pos : &ht->pInternalPointer;
1043
1044 IS_CONSISTENT(ht);
1045
1046 if (*current) {
1047 *current = (*current)->pListNext;
1048 return SUCCESS;
1049 } else
1050 return FAILURE;
1051 }
1052
1053 ZEND_API int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos)
1054 {
1055 HashPosition *current = pos ? pos : &ht->pInternalPointer;
1056
1057 IS_CONSISTENT(ht);
1058
1059 if (*current) {
1060 *current = (*current)->pListLast;
1061 return SUCCESS;
1062 } else
1063 return FAILURE;
1064 }
1065
1066
1067
1068 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)
1069 {
1070 Bucket *p;
1071
1072 p = pos ? (*pos) : ht->pInternalPointer;
1073
1074 IS_CONSISTENT(ht);
1075
1076 if (p) {
1077 if (p->nKeyLength) {
1078 if (duplicate) {
1079 *str_index = estrndup(p->arKey, p->nKeyLength - 1);
1080 } else {
1081 *str_index = (char*)p->arKey;
1082 }
1083 if (str_length) {
1084 *str_length = p->nKeyLength;
1085 }
1086 return HASH_KEY_IS_STRING;
1087 } else {
1088 *num_index = p->h;
1089 return HASH_KEY_IS_LONG;
1090 }
1091 }
1092 return HASH_KEY_NON_EXISTENT;
1093 }
1094
1095 ZEND_API void zend_hash_get_current_key_zval_ex(const HashTable *ht, zval *key, HashPosition *pos) {
1096 Bucket *p;
1097
1098 IS_CONSISTENT(ht);
1099
1100 p = pos ? (*pos) : ht->pInternalPointer;
1101
1102 if (!p) {
1103 Z_TYPE_P(key) = IS_NULL;
1104 } else if (p->nKeyLength) {
1105 Z_TYPE_P(key) = IS_STRING;
1106 Z_STRVAL_P(key) = IS_INTERNED(p->arKey) ? (char*)p->arKey : estrndup(p->arKey, p->nKeyLength - 1);
1107 Z_STRLEN_P(key) = p->nKeyLength - 1;
1108 } else {
1109 Z_TYPE_P(key) = IS_LONG;
1110 Z_LVAL_P(key) = p->h;
1111 }
1112 }
1113
1114 ZEND_API int zend_hash_get_current_key_type_ex(HashTable *ht, HashPosition *pos)
1115 {
1116 Bucket *p;
1117
1118 p = pos ? (*pos) : ht->pInternalPointer;
1119
1120 IS_CONSISTENT(ht);
1121
1122 if (p) {
1123 if (p->nKeyLength) {
1124 return HASH_KEY_IS_STRING;
1125 } else {
1126 return HASH_KEY_IS_LONG;
1127 }
1128 }
1129 return HASH_KEY_NON_EXISTENT;
1130 }
1131
1132
1133 ZEND_API int zend_hash_get_current_data_ex(HashTable *ht, void **pData, HashPosition *pos)
1134 {
1135 Bucket *p;
1136
1137 p = pos ? (*pos) : ht->pInternalPointer;
1138
1139 IS_CONSISTENT(ht);
1140
1141 if (p) {
1142 *pData = p->pData;
1143 return SUCCESS;
1144 } else {
1145 return FAILURE;
1146 }
1147 }
1148
1149
1150
1151
1152 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)
1153 {
1154 Bucket *p, *q;
1155 ulong h;
1156 #ifdef ZEND_SIGNALS
1157 TSRMLS_FETCH();
1158 #endif
1159
1160 p = pos ? (*pos) : ht->pInternalPointer;
1161
1162 IS_CONSISTENT(ht);
1163
1164 if (p) {
1165 if (key_type == HASH_KEY_IS_LONG) {
1166 str_length = 0;
1167 if (!p->nKeyLength && p->h == num_index) {
1168 return SUCCESS;
1169 }
1170
1171 q = ht->arBuckets[num_index & ht->nTableMask];
1172 while (q != NULL) {
1173 if (!q->nKeyLength && q->h == num_index) {
1174 break;
1175 }
1176 q = q->pNext;
1177 }
1178 } else if (key_type == HASH_KEY_IS_STRING) {
1179 if (IS_INTERNED(str_index)) {
1180 h = INTERNED_HASH(str_index);
1181 } else {
1182 h = zend_inline_hash_func(str_index, str_length);
1183 }
1184
1185 if (p->arKey == str_index ||
1186 (p->nKeyLength == str_length &&
1187 p->h == h &&
1188 memcmp(p->arKey, str_index, str_length) == 0)) {
1189 return SUCCESS;
1190 }
1191
1192 q = ht->arBuckets[h & ht->nTableMask];
1193
1194 while (q != NULL) {
1195 if (q->arKey == str_index ||
1196 (q->h == h && q->nKeyLength == str_length &&
1197 memcmp(q->arKey, str_index, str_length) == 0)) {
1198 break;
1199 }
1200 q = q->pNext;
1201 }
1202 } else {
1203 return FAILURE;
1204 }
1205
1206 if (q) {
1207 if (mode != HASH_UPDATE_KEY_ANYWAY) {
1208 Bucket *r = p->pListLast;
1209 int found = HASH_UPDATE_KEY_IF_BEFORE;
1210
1211 while (r) {
1212 if (r == q) {
1213 found = HASH_UPDATE_KEY_IF_AFTER;
1214 break;
1215 }
1216 r = r->pListLast;
1217 }
1218 if (mode & found) {
1219
1220 zend_hash_bucket_delete(ht, p);
1221 return FAILURE;
1222 }
1223 }
1224
1225
1226 zend_hash_bucket_delete(ht, q);
1227 }
1228
1229 HANDLE_BLOCK_INTERRUPTIONS();
1230
1231 if (p->pNext) {
1232 p->pNext->pLast = p->pLast;
1233 }
1234 if (p->pLast) {
1235 p->pLast->pNext = p->pNext;
1236 } else {
1237 ht->arBuckets[p->h & ht->nTableMask] = p->pNext;
1238 }
1239
1240 if ((IS_INTERNED(p->arKey) != IS_INTERNED(str_index)) ||
1241 (!IS_INTERNED(p->arKey) && p->nKeyLength != str_length)) {
1242 Bucket *q;
1243
1244 if (IS_INTERNED(str_index)) {
1245 q = (Bucket *) pemalloc(sizeof(Bucket), ht->persistent);
1246 } else {
1247 q = (Bucket *) pemalloc(sizeof(Bucket) + str_length, ht->persistent);
1248 }
1249
1250 q->nKeyLength = str_length;
1251 if (p->pData == &p->pDataPtr) {
1252 q->pData = &q->pDataPtr;
1253 } else {
1254 q->pData = p->pData;
1255 }
1256 q->pDataPtr = p->pDataPtr;
1257
1258 CONNECT_TO_GLOBAL_DLLIST_EX(q, ht, p->pListLast, p->pListNext);
1259 if (ht->pInternalPointer == p) {
1260 ht->pInternalPointer = q;
1261 }
1262
1263 if (pos) {
1264 *pos = q;
1265 }
1266 pefree(p, ht->persistent);
1267 p = q;
1268 }
1269
1270 if (key_type == HASH_KEY_IS_LONG) {
1271 p->h = num_index;
1272 if ((long)num_index >= (long)ht->nNextFreeElement) {
1273 ht->nNextFreeElement = num_index < LONG_MAX ? num_index + 1 : LONG_MAX;
1274 }
1275 } else {
1276 p->h = h;
1277 p->nKeyLength = str_length;
1278 if (IS_INTERNED(str_index)) {
1279 p->arKey = str_index;
1280 } else {
1281 p->arKey = (const char*)(p+1);
1282 memcpy((char*)p->arKey, str_index, str_length);
1283 }
1284 }
1285
1286 CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[p->h & ht->nTableMask]);
1287 ht->arBuckets[p->h & ht->nTableMask] = p;
1288 HANDLE_UNBLOCK_INTERRUPTIONS();
1289
1290 return SUCCESS;
1291 } else {
1292 return FAILURE;
1293 }
1294 }
1295
1296
1297
1298
1299
1300
1301 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)
1302 {
1303 int pos;
1304 Bucket *p;
1305
1306 IS_CONSISTENT(ht);
1307 CHECK_INIT(ht);
1308
1309
1310 for (pos = 0, p = ht->pListHead; pos < offset && p; pos++, p = p->pListNext);
1311
1312 while (pos < offset + length && p) {
1313
1314 if (removed != NULL) {
1315 void *new_entry;
1316
1317 if (p->nKeyLength == 0) {
1318 zend_hash_next_index_insert(removed, p->pData, sizeof(zval *), &new_entry);
1319 } else {
1320 zend_hash_quick_update(removed, p->arKey, p->nKeyLength, p->h, p->pData, sizeof(zval *), &new_entry);
1321 }
1322
1323 if (pCopyConstructor) {
1324 pCopyConstructor(new_entry);
1325 }
1326 }
1327
1328
1329 {
1330 Bucket *p_next = p->pListNext;
1331 zend_hash_bucket_delete(ht, p);
1332 p = p_next;
1333 }
1334
1335 pos++;
1336 }
1337
1338 if (list != NULL) {
1339 int i;
1340 for (i = 0; i < list_count; i++) {
1341
1342
1343 Bucket *q = pemalloc_rel(sizeof(Bucket), ht->persistent);
1344 q->arKey = NULL;
1345 q->nKeyLength = 0;
1346 q->h = 0;
1347 INIT_DATA(ht, q, list[i], nDataSize);
1348
1349 CONNECT_TO_GLOBAL_DLLIST_EX(q, ht, p ? p->pListLast : ht->pListTail, p);
1350
1351 ht->nNumOfElements++;
1352
1353 if (pCopyConstructor) {
1354 pCopyConstructor(q->pData);
1355 }
1356 }
1357
1358 ZEND_HASH_IF_FULL_DO_RESIZE(ht);
1359 }
1360
1361 zend_hash_reindex(ht, 1);
1362 }
1363
1364
1365 ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func,
1366 compare_func_t compar, int renumber TSRMLS_DC)
1367 {
1368 Bucket **arTmp;
1369 Bucket *p;
1370 int i, j;
1371
1372 IS_CONSISTENT(ht);
1373
1374 if (!(ht->nNumOfElements>1) && !(renumber && ht->nNumOfElements>0)) {
1375 return SUCCESS;
1376 }
1377 arTmp = (Bucket **) pemalloc(ht->nNumOfElements * sizeof(Bucket *), ht->persistent);
1378 p = ht->pListHead;
1379 i = 0;
1380 while (p) {
1381 arTmp[i] = p;
1382 p = p->pListNext;
1383 i++;
1384 }
1385
1386 (*sort_func)((void *) arTmp, i, sizeof(Bucket *), compar TSRMLS_CC);
1387
1388 HANDLE_BLOCK_INTERRUPTIONS();
1389 ht->pListHead = arTmp[0];
1390 ht->pListTail = NULL;
1391 ht->pInternalPointer = ht->pListHead;
1392
1393 arTmp[0]->pListLast = NULL;
1394 if (i > 1) {
1395 arTmp[0]->pListNext = arTmp[1];
1396 for (j = 1; j < i-1; j++) {
1397 arTmp[j]->pListLast = arTmp[j-1];
1398 arTmp[j]->pListNext = arTmp[j+1];
1399 }
1400 arTmp[j]->pListLast = arTmp[j-1];
1401 arTmp[j]->pListNext = NULL;
1402 } else {
1403 arTmp[0]->pListNext = NULL;
1404 }
1405 ht->pListTail = arTmp[i-1];
1406
1407 pefree(arTmp, ht->persistent);
1408 HANDLE_UNBLOCK_INTERRUPTIONS();
1409
1410 if (renumber) {
1411 zend_hash_reindex(ht, 0);
1412 }
1413 return SUCCESS;
1414 }
1415
1416
1417 ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered TSRMLS_DC)
1418 {
1419 Bucket *p1, *p2 = NULL;
1420 int result;
1421 void *pData2;
1422
1423 IS_CONSISTENT(ht1);
1424 IS_CONSISTENT(ht2);
1425
1426 HASH_PROTECT_RECURSION(ht1);
1427 HASH_PROTECT_RECURSION(ht2);
1428
1429 result = ht1->nNumOfElements - ht2->nNumOfElements;
1430 if (result!=0) {
1431 HASH_UNPROTECT_RECURSION(ht1);
1432 HASH_UNPROTECT_RECURSION(ht2);
1433 return result;
1434 }
1435
1436 p1 = ht1->pListHead;
1437 if (ordered) {
1438 p2 = ht2->pListHead;
1439 }
1440
1441 while (p1) {
1442 if (ordered && !p2) {
1443 HASH_UNPROTECT_RECURSION(ht1);
1444 HASH_UNPROTECT_RECURSION(ht2);
1445 return 1;
1446 }
1447 if (ordered) {
1448 if (p1->nKeyLength==0 && p2->nKeyLength==0) {
1449 if (p1->h != p2->h) {
1450 HASH_UNPROTECT_RECURSION(ht1);
1451 HASH_UNPROTECT_RECURSION(ht2);
1452 return p1->h > p2->h ? 1 : -1;
1453 }
1454 } else {
1455 result = p1->nKeyLength - p2->nKeyLength;
1456 if (result!=0) {
1457 HASH_UNPROTECT_RECURSION(ht1);
1458 HASH_UNPROTECT_RECURSION(ht2);
1459 return result;
1460 }
1461 result = memcmp(p1->arKey, p2->arKey, p1->nKeyLength);
1462 if (result!=0) {
1463 HASH_UNPROTECT_RECURSION(ht1);
1464 HASH_UNPROTECT_RECURSION(ht2);
1465 return result;
1466 }
1467 }
1468 pData2 = p2->pData;
1469 } else {
1470 if (p1->nKeyLength==0) {
1471 if (zend_hash_index_find(ht2, p1->h, &pData2)==FAILURE) {
1472 HASH_UNPROTECT_RECURSION(ht1);
1473 HASH_UNPROTECT_RECURSION(ht2);
1474 return 1;
1475 }
1476 } else {
1477 if (zend_hash_quick_find(ht2, p1->arKey, p1->nKeyLength, p1->h, &pData2)==FAILURE) {
1478 HASH_UNPROTECT_RECURSION(ht1);
1479 HASH_UNPROTECT_RECURSION(ht2);
1480 return 1;
1481 }
1482 }
1483 }
1484 result = compar(p1->pData, pData2 TSRMLS_CC);
1485 if (result!=0) {
1486 HASH_UNPROTECT_RECURSION(ht1);
1487 HASH_UNPROTECT_RECURSION(ht2);
1488 return result;
1489 }
1490 p1 = p1->pListNext;
1491 if (ordered) {
1492 p2 = p2->pListNext;
1493 }
1494 }
1495
1496 HASH_UNPROTECT_RECURSION(ht1);
1497 HASH_UNPROTECT_RECURSION(ht2);
1498 return 0;
1499 }
1500
1501
1502 ZEND_API int zend_hash_minmax(const HashTable *ht, compare_func_t compar, int flag, void **pData TSRMLS_DC)
1503 {
1504 Bucket *p, *res;
1505
1506 IS_CONSISTENT(ht);
1507
1508 if (ht->nNumOfElements == 0 ) {
1509 *pData=NULL;
1510 return FAILURE;
1511 }
1512
1513 res = p = ht->pListHead;
1514 while ((p = p->pListNext)) {
1515 if (flag) {
1516 if (compar(&res, &p TSRMLS_CC) < 0) {
1517 res = p;
1518 }
1519 } else {
1520 if (compar(&res, &p TSRMLS_CC) > 0) {
1521 res = p;
1522 }
1523 }
1524 }
1525 *pData = res->pData;
1526 return SUCCESS;
1527 }
1528
1529 ZEND_API ulong zend_hash_next_free_element(const HashTable *ht)
1530 {
1531 IS_CONSISTENT(ht);
1532
1533 return ht->nNextFreeElement;
1534
1535 }
1536
1537
1538 #if ZEND_DEBUG
1539 void zend_hash_display_pListTail(const HashTable *ht)
1540 {
1541 Bucket *p;
1542
1543 p = ht->pListTail;
1544 while (p != NULL) {
1545 zend_output_debug_string(0, "pListTail has key %s\n", p->arKey);
1546 p = p->pListLast;
1547 }
1548 }
1549
1550 void zend_hash_display(const HashTable *ht)
1551 {
1552 Bucket *p;
1553 uint i;
1554
1555 if (UNEXPECTED(ht->nNumOfElements == 0)) {
1556 zend_output_debug_string(0, "The hash is empty");
1557 return;
1558 }
1559 for (i = 0; i < ht->nTableSize; i++) {
1560 p = ht->arBuckets[i];
1561 while (p != NULL) {
1562 zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h);
1563 p = p->pNext;
1564 }
1565 }
1566
1567 p = ht->pListTail;
1568 while (p != NULL) {
1569 zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h);
1570 p = p->pListLast;
1571 }
1572 }
1573 #endif
1574
1575
1576
1577
1578
1579
1580
1581