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