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: zend_hash.c,v 1.1.1.4 2014/06/15 20:04:03 misho Exp $ */
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:
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:
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:
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:
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:
188: ZEND_API void zend_hash_set_apply_protection(HashTable *ht, zend_bool bApplyProtection)
189: {
190: ht->bApplyProtection = bApplyProtection;
191: }
192:
193:
194:
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:
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:
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:
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:
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:
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:
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:
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:
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: */
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:
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:
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:
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:
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:
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:
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:
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:
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:
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:
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:
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: */
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:
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:
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:
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:
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:
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:
1053: ZEND_API int zend_hash_num_elements(const HashTable *ht)
1054: {
1055: IS_CONSISTENT(ht);
1056:
1057: return ht->nNumOfElements;
1058: }
1059:
1060:
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:
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:
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: */
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:
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:
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 */
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:
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:
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: */
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:
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:
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: result = p1->h - p2->h;
1517: if (result!=0) {
1518: HASH_UNPROTECT_RECURSION(ht1);
1519: HASH_UNPROTECT_RECURSION(ht2);
1520: return result;
1521: }
1522: } else { /* string indices */
1523: result = p1->nKeyLength - p2->nKeyLength;
1524: if (result!=0) {
1525: HASH_UNPROTECT_RECURSION(ht1);
1526: HASH_UNPROTECT_RECURSION(ht2);
1527: return result;
1528: }
1529: result = memcmp(p1->arKey, p2->arKey, p1->nKeyLength);
1530: if (result!=0) {
1531: HASH_UNPROTECT_RECURSION(ht1);
1532: HASH_UNPROTECT_RECURSION(ht2);
1533: return result;
1534: }
1535: }
1536: pData2 = p2->pData;
1537: } else {
1538: if (p1->nKeyLength==0) { /* numeric index */
1539: if (zend_hash_index_find(ht2, p1->h, &pData2)==FAILURE) {
1540: HASH_UNPROTECT_RECURSION(ht1);
1541: HASH_UNPROTECT_RECURSION(ht2);
1542: return 1;
1543: }
1544: } else { /* string index */
1545: if (zend_hash_quick_find(ht2, p1->arKey, p1->nKeyLength, p1->h, &pData2)==FAILURE) {
1546: HASH_UNPROTECT_RECURSION(ht1);
1547: HASH_UNPROTECT_RECURSION(ht2);
1548: return 1;
1549: }
1550: }
1551: }
1552: result = compar(p1->pData, pData2 TSRMLS_CC);
1553: if (result!=0) {
1554: HASH_UNPROTECT_RECURSION(ht1);
1555: HASH_UNPROTECT_RECURSION(ht2);
1556: return result;
1557: }
1558: p1 = p1->pListNext;
1559: if (ordered) {
1560: p2 = p2->pListNext;
1561: }
1562: }
1563:
1564: HASH_UNPROTECT_RECURSION(ht1);
1565: HASH_UNPROTECT_RECURSION(ht2);
1566: return 0;
1567: }
1568:
1569:
1570: ZEND_API int zend_hash_minmax(const HashTable *ht, compare_func_t compar, int flag, void **pData TSRMLS_DC)
1571: {
1572: Bucket *p, *res;
1573:
1574: IS_CONSISTENT(ht);
1575:
1576: if (ht->nNumOfElements == 0 ) {
1577: *pData=NULL;
1578: return FAILURE;
1579: }
1580:
1581: res = p = ht->pListHead;
1582: while ((p = p->pListNext)) {
1583: if (flag) {
1584: if (compar(&res, &p TSRMLS_CC) < 0) { /* max */
1585: res = p;
1586: }
1587: } else {
1588: if (compar(&res, &p TSRMLS_CC) > 0) { /* min */
1589: res = p;
1590: }
1591: }
1592: }
1593: *pData = res->pData;
1594: return SUCCESS;
1595: }
1596:
1597: ZEND_API ulong zend_hash_next_free_element(const HashTable *ht)
1598: {
1599: IS_CONSISTENT(ht);
1600:
1601: return ht->nNextFreeElement;
1602:
1603: }
1604:
1605:
1606: #if ZEND_DEBUG
1607: void zend_hash_display_pListTail(const HashTable *ht)
1608: {
1609: Bucket *p;
1610:
1611: p = ht->pListTail;
1612: while (p != NULL) {
1613: zend_output_debug_string(0, "pListTail has key %s\n", p->arKey);
1614: p = p->pListLast;
1615: }
1616: }
1617:
1618: void zend_hash_display(const HashTable *ht)
1619: {
1620: Bucket *p;
1621: uint i;
1622:
1623: if (UNEXPECTED(ht->nNumOfElements == 0)) {
1624: zend_output_debug_string(0, "The hash is empty");
1625: return;
1626: }
1627: for (i = 0; i < ht->nTableSize; i++) {
1628: p = ht->arBuckets[i];
1629: while (p != NULL) {
1630: zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h);
1631: p = p->pNext;
1632: }
1633: }
1634:
1635: p = ht->pListTail;
1636: while (p != NULL) {
1637: zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h);
1638: p = p->pListLast;
1639: }
1640: }
1641: #endif
1642:
1643: /*
1644: * Local variables:
1645: * tab-width: 4
1646: * c-basic-offset: 4
1647: * indent-tabs-mode: t
1648: * End:
1649: */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to zend_hash.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / Zend