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