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 281779 2009-06-07 19:28:33Z 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(HashTable *ht, 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(char *arKey, uint nKeyLength)
98 169 : {
99 169 : 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 14588839 : {
139 14588839 : uint i = 3;
140 : Bucket **tmp;
141 :
142 : SET_INCONSISTENT(HT_OK);
143 :
144 14588839 : if (nSize >= 0x80000000) {
145 : /* prevent overflow */
146 0 : ht->nTableSize = 0x80000000;
147 : } else {
148 29738930 : while ((1U << i) < nSize) {
149 561252 : i++;
150 : }
151 14588839 : ht->nTableSize = 1 << i;
152 : }
153 :
154 14588839 : ht->nTableMask = ht->nTableSize - 1;
155 14588839 : ht->pDestructor = pDestructor;
156 14588839 : ht->arBuckets = NULL;
157 14588839 : ht->pListHead = NULL;
158 14588839 : ht->pListTail = NULL;
159 14588839 : ht->nNumOfElements = 0;
160 14588839 : ht->nNextFreeElement = 0;
161 14588839 : ht->pInternalPointer = NULL;
162 14588839 : ht->persistent = persistent;
163 14588839 : ht->nApplyCount = 0;
164 14588839 : ht->bApplyProtection = 1;
165 :
166 : /* Uses ecalloc() so that Bucket* == NULL */
167 14588839 : if (persistent) {
168 9441306 : tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *));
169 9441306 : if (!tmp) {
170 0 : return FAILURE;
171 : }
172 9441306 : ht->arBuckets = tmp;
173 : } else {
174 5147533 : tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket *));
175 5147533 : if (tmp) {
176 5147533 : ht->arBuckets = tmp;
177 : }
178 : }
179 :
180 14588839 : 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 8811338 : {
186 8811338 : int retval = _zend_hash_init(ht, nSize, pHashFunction, pDestructor, persistent ZEND_FILE_LINE_CC);
187 :
188 8811338 : ht->bApplyProtection = bApplyProtection;
189 8811338 : 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, char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
201 87825622 : {
202 : ulong h;
203 : uint nIndex;
204 : Bucket *p;
205 :
206 : IS_CONSISTENT(ht);
207 :
208 87825622 : 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 87825622 : h = zend_inline_hash_func(arKey, nKeyLength);
216 87825622 : nIndex = h & ht->nTableMask;
217 :
218 87825622 : p = ht->arBuckets[nIndex];
219 230503601 : while (p != NULL) {
220 55551803 : if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
221 699446 : if (!memcmp(p->arKey, arKey, nKeyLength)) {
222 699446 : if (flag & HASH_ADD) {
223 177813 : return FAILURE;
224 : }
225 521633 : 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 521633 : if (ht->pDestructor) {
234 494456 : ht->pDestructor(p->pData);
235 : }
236 521632 : UPDATE_DATA(ht, p, pData, nDataSize);
237 521632 : if (pDest) {
238 70640 : *pDest = p->pData;
239 : }
240 521632 : HANDLE_UNBLOCK_INTERRUPTIONS();
241 521632 : return SUCCESS;
242 : }
243 : }
244 54852357 : p = p->pNext;
245 : }
246 :
247 87126176 : p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
248 87126176 : if (!p) {
249 0 : return FAILURE;
250 : }
251 87126176 : memcpy(p->arKey, arKey, nKeyLength);
252 87126176 : p->nKeyLength = nKeyLength;
253 87126176 : INIT_DATA(ht, p, pData, nDataSize);
254 87126176 : p->h = h;
255 87126176 : CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
256 87126176 : if (pDest) {
257 46823213 : *pDest = p->pData;
258 : }
259 :
260 87126176 : HANDLE_BLOCK_INTERRUPTIONS();
261 87126176 : CONNECT_TO_GLOBAL_DLLIST(p, ht);
262 87126176 : ht->arBuckets[nIndex] = p;
263 87126176 : HANDLE_UNBLOCK_INTERRUPTIONS();
264 :
265 87126176 : ht->nNumOfElements++;
266 87126176 : ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */
267 87126176 : return SUCCESS;
268 : }
269 :
270 : ZEND_API int _zend_hash_quick_add_or_update(HashTable *ht, char *arKey, uint nKeyLength, ulong h, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
271 22876524 : {
272 : uint nIndex;
273 : Bucket *p;
274 :
275 : IS_CONSISTENT(ht);
276 :
277 22876524 : if (nKeyLength == 0) {
278 0 : return zend_hash_index_update(ht, h, pData, nDataSize, pDest);
279 : }
280 :
281 22876524 : nIndex = h & ht->nTableMask;
282 :
283 22876524 : p = ht->arBuckets[nIndex];
284 55953911 : while (p != NULL) {
285 10200939 : if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
286 76 : if (!memcmp(p->arKey, arKey, nKeyLength)) {
287 76 : if (flag & HASH_ADD) {
288 48 : return FAILURE;
289 : }
290 28 : 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 28 : if (ht->pDestructor) {
299 28 : ht->pDestructor(p->pData);
300 : }
301 28 : UPDATE_DATA(ht, p, pData, nDataSize);
302 28 : if (pDest) {
303 22 : *pDest = p->pData;
304 : }
305 28 : HANDLE_UNBLOCK_INTERRUPTIONS();
306 28 : return SUCCESS;
307 : }
308 : }
309 10200863 : p = p->pNext;
310 : }
311 :
312 22876448 : p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
313 22876448 : if (!p) {
314 0 : return FAILURE;
315 : }
316 :
317 22876448 : memcpy(p->arKey, arKey, nKeyLength);
318 22876448 : p->nKeyLength = nKeyLength;
319 22876448 : INIT_DATA(ht, p, pData, nDataSize);
320 22876448 : p->h = h;
321 :
322 22876448 : CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
323 :
324 22876448 : if (pDest) {
325 22875654 : *pDest = p->pData;
326 : }
327 :
328 22876448 : HANDLE_BLOCK_INTERRUPTIONS();
329 22876448 : ht->arBuckets[nIndex] = p;
330 22876448 : CONNECT_TO_GLOBAL_DLLIST(p, ht);
331 22876448 : HANDLE_UNBLOCK_INTERRUPTIONS();
332 :
333 22876448 : ht->nNumOfElements++;
334 22876448 : ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */
335 22876448 : return SUCCESS;
336 : }
337 :
338 :
339 : ZEND_API int zend_hash_add_empty_element(HashTable *ht, char *arKey, uint nKeyLength)
340 1810 : {
341 1810 : void *dummy = (void *) 1;
342 :
343 1810 : 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 7716815 : {
349 : uint nIndex;
350 : Bucket *p;
351 :
352 : IS_CONSISTENT(ht);
353 :
354 7716815 : if (flag & HASH_NEXT_INSERT) {
355 3551254 : h = ht->nNextFreeElement;
356 : }
357 7716815 : nIndex = h & ht->nTableMask;
358 :
359 7716815 : p = ht->arBuckets[nIndex];
360 15973798 : while (p != NULL) {
361 544933 : if ((p->nKeyLength == 0) && (p->h == h)) {
362 4765 : if (flag & HASH_NEXT_INSERT || flag & HASH_ADD) {
363 2 : return FAILURE;
364 : }
365 4763 : 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 4763 : if (ht->pDestructor) {
374 4763 : ht->pDestructor(p->pData);
375 : }
376 4763 : UPDATE_DATA(ht, p, pData, nDataSize);
377 4763 : HANDLE_UNBLOCK_INTERRUPTIONS();
378 4763 : if ((long)h >= (long)ht->nNextFreeElement) {
379 1 : ht->nNextFreeElement = h < LONG_MAX ? h + 1 : LONG_MAX;
380 : }
381 4763 : if (pDest) {
382 2 : *pDest = p->pData;
383 : }
384 4763 : return SUCCESS;
385 : }
386 540168 : p = p->pNext;
387 : }
388 7712050 : p = (Bucket *) pemalloc_rel(sizeof(Bucket) - 1, ht->persistent);
389 7712050 : if (!p) {
390 0 : return FAILURE;
391 : }
392 7712050 : p->nKeyLength = 0; /* Numeric indices are marked by making the nKeyLength == 0 */
393 7712050 : p->h = h;
394 7712050 : INIT_DATA(ht, p, pData, nDataSize);
395 7712050 : if (pDest) {
396 3617435 : *pDest = p->pData;
397 : }
398 :
399 7712050 : CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
400 :
401 7712050 : HANDLE_BLOCK_INTERRUPTIONS();
402 7712050 : ht->arBuckets[nIndex] = p;
403 7712050 : CONNECT_TO_GLOBAL_DLLIST(p, ht);
404 7712050 : HANDLE_UNBLOCK_INTERRUPTIONS();
405 :
406 7712050 : if ((long)h >= (long)ht->nNextFreeElement) {
407 6896342 : ht->nNextFreeElement = h < LONG_MAX ? h + 1 : LONG_MAX;
408 : }
409 7712050 : ht->nNumOfElements++;
410 7712050 : ZEND_HASH_IF_FULL_DO_RESIZE(ht);
411 7712050 : return SUCCESS;
412 : }
413 :
414 :
415 : static int zend_hash_do_resize(HashTable *ht)
416 2744269 : {
417 : Bucket **t;
418 :
419 : IS_CONSISTENT(ht);
420 :
421 2744269 : if ((ht->nTableSize << 1) > 0) { /* Let's double the table size */
422 2744269 : t = (Bucket **) perealloc_recoverable(ht->arBuckets, (ht->nTableSize << 1) * sizeof(Bucket *), ht->persistent);
423 2744269 : if (t) {
424 2744269 : HANDLE_BLOCK_INTERRUPTIONS();
425 2744269 : ht->arBuckets = t;
426 2744269 : ht->nTableSize = (ht->nTableSize << 1);
427 2744269 : ht->nTableMask = ht->nTableSize - 1;
428 2744269 : zend_hash_rehash(ht);
429 2744269 : HANDLE_UNBLOCK_INTERRUPTIONS();
430 2744269 : return SUCCESS;
431 : }
432 0 : return FAILURE;
433 : }
434 0 : return SUCCESS;
435 : }
436 :
437 : ZEND_API int zend_hash_rehash(HashTable *ht)
438 2834686 : {
439 : Bucket *p;
440 : uint nIndex;
441 :
442 : IS_CONSISTENT(ht);
443 :
444 2834686 : memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
445 2834686 : p = ht->pListHead;
446 128001813 : while (p != NULL) {
447 122332441 : nIndex = p->h & ht->nTableMask;
448 122332441 : CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
449 122332441 : ht->arBuckets[nIndex] = p;
450 122332441 : p = p->pListNext;
451 : }
452 2834686 : return SUCCESS;
453 : }
454 :
455 : ZEND_API int zend_hash_del_key_or_index(HashTable *ht, char *arKey, uint nKeyLength, ulong h, int flag)
456 28552571 : {
457 : uint nIndex;
458 : Bucket *p;
459 :
460 : IS_CONSISTENT(ht);
461 :
462 28552571 : if (flag == HASH_DEL_KEY) {
463 28121010 : h = zend_inline_hash_func(arKey, nKeyLength);
464 : }
465 28552571 : nIndex = h & ht->nTableMask;
466 :
467 28552571 : p = ht->arBuckets[nIndex];
468 59934434 : while (p != NULL) {
469 31203206 : 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 28373914 : HANDLE_BLOCK_INTERRUPTIONS();
474 28373914 : if (p == ht->arBuckets[nIndex]) {
475 25803291 : ht->arBuckets[nIndex] = p->pNext;
476 : } else {
477 2570623 : p->pLast->pNext = p->pNext;
478 : }
479 28373914 : if (p->pNext) {
480 4205844 : p->pNext->pLast = p->pLast;
481 : }
482 28373914 : if (p->pListLast != NULL) {
483 28291338 : p->pListLast->pListNext = p->pListNext;
484 : } else {
485 : /* Deleting the head of the list */
486 82576 : ht->pListHead = p->pListNext;
487 : }
488 28373914 : if (p->pListNext != NULL) {
489 27714961 : p->pListNext->pListLast = p->pListLast;
490 : } else {
491 658953 : ht->pListTail = p->pListLast;
492 : }
493 28373914 : if (ht->pInternalPointer == p) {
494 82584 : ht->pInternalPointer = p->pListNext;
495 : }
496 28373914 : if (ht->pDestructor) {
497 27979455 : ht->pDestructor(p->pData);
498 : }
499 28373913 : if (p->pData != &p->pDataPtr) {
500 27969145 : pefree(p->pData, ht->persistent);
501 : }
502 28373913 : pefree(p, ht->persistent);
503 28373913 : HANDLE_UNBLOCK_INTERRUPTIONS();
504 28373913 : ht->nNumOfElements--;
505 28373913 : return SUCCESS;
506 : }
507 2829292 : p = p->pNext;
508 : }
509 178657 : return FAILURE;
510 : }
511 :
512 :
513 : ZEND_API void zend_hash_destroy(HashTable *ht)
514 14557103 : {
515 : Bucket *p, *q;
516 :
517 : IS_CONSISTENT(ht);
518 :
519 : SET_INCONSISTENT(HT_IS_DESTROYING);
520 :
521 14557103 : p = ht->pListHead;
522 109824444 : while (p != NULL) {
523 80710242 : q = p;
524 80710242 : p = p->pListNext;
525 80710242 : if (ht->pDestructor) {
526 69346977 : ht->pDestructor(q->pData);
527 : }
528 80710238 : if (q->pData != &q->pDataPtr) {
529 57947383 : pefree(q->pData, ht->persistent);
530 : }
531 80710238 : pefree(q, ht->persistent);
532 : }
533 14557099 : pefree(ht->arBuckets, ht->persistent);
534 :
535 : SET_INCONSISTENT(HT_DESTROYED);
536 14557099 : }
537 :
538 :
539 : ZEND_API void zend_hash_clean(HashTable *ht)
540 1335377 : {
541 : Bucket *p, *q;
542 :
543 : IS_CONSISTENT(ht);
544 :
545 : SET_INCONSISTENT(HT_CLEANING);
546 :
547 1335377 : p = ht->pListHead;
548 7589322 : while (p != NULL) {
549 4918568 : q = p;
550 4918568 : p = p->pListNext;
551 4918568 : if (ht->pDestructor) {
552 4918568 : ht->pDestructor(q->pData);
553 : }
554 4918568 : if (q->pData != &q->pDataPtr) {
555 0 : pefree(q->pData, ht->persistent);
556 : }
557 4918568 : pefree(q, ht->persistent);
558 : }
559 1335377 : memset(ht->arBuckets, 0, ht->nTableSize*sizeof(Bucket *));
560 1335377 : ht->pListHead = NULL;
561 1335377 : ht->pListTail = NULL;
562 1335377 : ht->nNumOfElements = 0;
563 1335377 : ht->nNextFreeElement = 0;
564 1335377 : ht->pInternalPointer = NULL;
565 :
566 : SET_INCONSISTENT(HT_OK);
567 1335377 : }
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 3956200 : {
576 : Bucket *retval;
577 :
578 3956200 : HANDLE_BLOCK_INTERRUPTIONS();
579 3956200 : if (p->pLast) {
580 232560 : p->pLast->pNext = p->pNext;
581 : } else {
582 : uint nIndex;
583 :
584 3723640 : nIndex = p->h & ht->nTableMask;
585 3723640 : ht->arBuckets[nIndex] = p->pNext;
586 : }
587 3956200 : if (p->pNext) {
588 981707 : p->pNext->pLast = p->pLast;
589 : } else {
590 : /* Nothing to do as this list doesn't have a tail */
591 : }
592 :
593 3956200 : if (p->pListLast != NULL) {
594 2585836 : p->pListLast->pListNext = p->pListNext;
595 : } else {
596 : /* Deleting the head of the list */
597 1370364 : ht->pListHead = p->pListNext;
598 : }
599 3956200 : if (p->pListNext != NULL) {
600 2603161 : p->pListNext->pListLast = p->pListLast;
601 : } else {
602 1353039 : ht->pListTail = p->pListLast;
603 : }
604 3956200 : if (ht->pInternalPointer == p) {
605 1370364 : ht->pInternalPointer = p->pListNext;
606 : }
607 3956200 : ht->nNumOfElements--;
608 3956200 : HANDLE_UNBLOCK_INTERRUPTIONS();
609 :
610 3956200 : if (ht->pDestructor) {
611 1315797 : ht->pDestructor(p->pData);
612 : }
613 3956199 : if (p->pData != &p->pDataPtr) {
614 3510125 : pefree(p->pData, ht->persistent);
615 : }
616 3956199 : retval = p->pListNext;
617 3956199 : pefree(p, ht->persistent);
618 :
619 3956199 : 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 54364 : {
640 : Bucket *p;
641 :
642 : IS_CONSISTENT(ht);
643 :
644 54364 : p = ht->pListTail;
645 1184453 : while (p != NULL) {
646 1075726 : zend_hash_apply_deleter(ht, p);
647 1075725 : p = ht->pListTail;
648 : }
649 :
650 54363 : pefree(ht->arBuckets, ht->persistent);
651 :
652 : SET_INCONSISTENT(HT_DESTROYED);
653 54363 : }
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 130859 : {
666 : Bucket *p;
667 :
668 : IS_CONSISTENT(ht);
669 :
670 130859 : HASH_PROTECT_RECURSION(ht);
671 130859 : p = ht->pListHead;
672 4590894 : while (p != NULL) {
673 4329177 : int result = apply_func(p->pData TSRMLS_CC);
674 :
675 4329176 : if (result & ZEND_HASH_APPLY_REMOVE) {
676 2172 : p = zend_hash_apply_deleter(ht, p);
677 : } else {
678 4327004 : p = p->pListNext;
679 : }
680 4329176 : if (result & ZEND_HASH_APPLY_STOP) {
681 0 : break;
682 : }
683 : }
684 130858 : HASH_UNPROTECT_RECURSION(ht);
685 130858 : }
686 :
687 :
688 : ZEND_API void zend_hash_apply_with_argument(HashTable *ht, apply_func_arg_t apply_func, void *argument TSRMLS_DC)
689 508947 : {
690 : Bucket *p;
691 :
692 : IS_CONSISTENT(ht);
693 :
694 508947 : HASH_PROTECT_RECURSION(ht);
695 508947 : p = ht->pListHead;
696 45360184 : while (p != NULL) {
697 44342291 : int result = apply_func(p->pData, argument TSRMLS_CC);
698 :
699 44342290 : if (result & ZEND_HASH_APPLY_REMOVE) {
700 2823920 : p = zend_hash_apply_deleter(ht, p);
701 : } else {
702 41518370 : p = p->pListNext;
703 : }
704 44342290 : if (result & ZEND_HASH_APPLY_STOP) {
705 0 : break;
706 : }
707 : }
708 508946 : HASH_UNPROTECT_RECURSION(ht);
709 508946 : }
710 :
711 :
712 : ZEND_API void zend_hash_apply_with_arguments(HashTable *ht, apply_func_args_t apply_func, int num_args, ...)
713 731466 : {
714 : Bucket *p;
715 : va_list args;
716 : zend_hash_key hash_key;
717 :
718 : IS_CONSISTENT(ht);
719 :
720 731466 : HASH_PROTECT_RECURSION(ht);
721 :
722 731464 : p = ht->pListHead;
723 1539963 : while (p != NULL) {
724 : int result;
725 77042 : va_start(args, num_args);
726 77042 : hash_key.arKey = p->arKey;
727 77042 : hash_key.nKeyLength = p->nKeyLength;
728 77042 : hash_key.h = p->h;
729 77042 : result = apply_func(p->pData, num_args, args, &hash_key);
730 :
731 77035 : if (result & ZEND_HASH_APPLY_REMOVE) {
732 0 : p = zend_hash_apply_deleter(ht, p);
733 : } else {
734 77035 : p = p->pListNext;
735 : }
736 77035 : if (result & ZEND_HASH_APPLY_STOP) {
737 0 : break;
738 : }
739 77035 : va_end(args);
740 : }
741 :
742 731457 : HASH_UNPROTECT_RECURSION(ht);
743 731457 : }
744 :
745 :
746 : ZEND_API void zend_hash_reverse_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC)
747 97481 : {
748 : Bucket *p, *q;
749 :
750 : IS_CONSISTENT(ht);
751 :
752 97481 : HASH_PROTECT_RECURSION(ht);
753 97481 : p = ht->pListTail;
754 1365207 : while (p != NULL) {
755 1238165 : int result = apply_func(p->pData TSRMLS_CC);
756 :
757 1238165 : q = p;
758 1238165 : p = p->pListLast;
759 1238165 : if (result & ZEND_HASH_APPLY_REMOVE) {
760 54382 : zend_hash_apply_deleter(ht, q);
761 : }
762 1238165 : if (result & ZEND_HASH_APPLY_STOP) {
763 67920 : break;
764 : }
765 : }
766 97481 : HASH_UNPROTECT_RECURSION(ht);
767 97481 : }
768 :
769 :
770 : ZEND_API void zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size)
771 1128898 : {
772 : Bucket *p;
773 : void *new_entry;
774 : zend_bool setTargetPointer;
775 :
776 : IS_CONSISTENT(source);
777 : IS_CONSISTENT(target);
778 :
779 1128898 : setTargetPointer = !target->pInternalPointer;
780 1128898 : p = source->pListHead;
781 5850491 : while (p) {
782 3592695 : if (setTargetPointer && source->pInternalPointer == p) {
783 674540 : target->pInternalPointer = NULL;
784 : }
785 3592695 : if (p->nKeyLength) {
786 1125960 : zend_hash_quick_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &new_entry);
787 : } else {
788 2466735 : zend_hash_index_update(target, p->h, p->pData, size, &new_entry);
789 : }
790 3592695 : if (pCopyConstructor) {
791 3591987 : pCopyConstructor(new_entry);
792 : }
793 3592695 : p = p->pListNext;
794 : }
795 1128898 : if (!target->pInternalPointer) {
796 454150 : target->pInternalPointer = target->pListHead;
797 : }
798 1128898 : }
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 1520813 : {
803 : Bucket *p;
804 : void *t;
805 1520813 : int mode = (overwrite?HASH_UPDATE:HASH_ADD);
806 :
807 : IS_CONSISTENT(source);
808 : IS_CONSISTENT(target);
809 :
810 1520813 : p = source->pListHead;
811 6748462 : while (p) {
812 3706836 : if (p->nKeyLength>0) {
813 3706827 : 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 1943329 : pCopyConstructor(t);
815 : }
816 : } else {
817 9 : 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 0 : pCopyConstructor(t);
819 : }
820 : }
821 3706836 : p = p->pListNext;
822 : }
823 1520813 : target->pInternalPointer = target->pListHead;
824 1520813 : }
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 14588863 : {
829 : zend_hash_key hash_key;
830 :
831 14588863 : hash_key.arKey = p->arKey;
832 14588863 : hash_key.nKeyLength = p->nKeyLength;
833 14588863 : hash_key.h = p->h;
834 14588863 : 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 2389443 : {
840 : Bucket *p;
841 : void *t;
842 :
843 : IS_CONSISTENT(source);
844 : IS_CONSISTENT(target);
845 :
846 2389443 : p = source->pListHead;
847 19367708 : while (p) {
848 14588863 : if (zend_hash_replace_checker_wrapper(target, p->pData, p, pParam, pMergeSource)) {
849 11440537 : if (zend_hash_quick_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &t)==SUCCESS && pCopyConstructor) {
850 11440537 : pCopyConstructor(t);
851 : }
852 : }
853 14588822 : p = p->pListNext;
854 : }
855 2389402 : target->pInternalPointer = target->pListHead;
856 2389402 : }
857 :
858 :
859 : ZEND_API ulong zend_get_hash_value(char *arKey, uint nKeyLength)
860 711067 : {
861 711067 : 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(HashTable *ht, char *arKey, uint nKeyLength, void **pData)
870 25525424 : {
871 : ulong h;
872 : uint nIndex;
873 : Bucket *p;
874 :
875 : IS_CONSISTENT(ht);
876 :
877 25525424 : h = zend_inline_hash_func(arKey, nKeyLength);
878 25525424 : nIndex = h & ht->nTableMask;
879 :
880 25525424 : p = ht->arBuckets[nIndex];
881 56460955 : while (p != NULL) {
882 26198740 : if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
883 20788633 : if (!memcmp(p->arKey, arKey, nKeyLength)) {
884 20788633 : *pData = p->pData;
885 20788633 : return SUCCESS;
886 : }
887 : }
888 5410107 : p = p->pNext;
889 : }
890 4736791 : return FAILURE;
891 : }
892 :
893 :
894 : ZEND_API int zend_hash_quick_find(HashTable *ht, char *arKey, uint nKeyLength, ulong h, void **pData)
895 21073708 : {
896 : uint nIndex;
897 : Bucket *p;
898 :
899 21073708 : if (nKeyLength==0) {
900 0 : return zend_hash_index_find(ht, h, pData);
901 : }
902 :
903 : IS_CONSISTENT(ht);
904 :
905 21073708 : nIndex = h & ht->nTableMask;
906 :
907 21073708 : p = ht->arBuckets[nIndex];
908 51482101 : while (p != NULL) {
909 12010842 : if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
910 2676157 : if (!memcmp(p->arKey, arKey, nKeyLength)) {
911 2676157 : *pData = p->pData;
912 2676157 : return SUCCESS;
913 : }
914 : }
915 9334685 : p = p->pNext;
916 : }
917 18397551 : return FAILURE;
918 : }
919 :
920 :
921 : ZEND_API int zend_hash_exists(HashTable *ht, char *arKey, uint nKeyLength)
922 258171 : {
923 : ulong h;
924 : uint nIndex;
925 : Bucket *p;
926 :
927 : IS_CONSISTENT(ht);
928 :
929 258171 : h = zend_inline_hash_func(arKey, nKeyLength);
930 258171 : nIndex = h & ht->nTableMask;
931 :
932 258171 : p = ht->arBuckets[nIndex];
933 578066 : while (p != NULL) {
934 208485 : if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
935 146761 : if (!memcmp(p->arKey, arKey, nKeyLength)) {
936 146761 : return 1;
937 : }
938 : }
939 61724 : p = p->pNext;
940 : }
941 111410 : return 0;
942 : }
943 :
944 :
945 : ZEND_API int zend_hash_quick_exists(HashTable *ht, char *arKey, uint nKeyLength, ulong h)
946 931 : {
947 : uint nIndex;
948 : Bucket *p;
949 :
950 931 : if (nKeyLength==0) {
951 0 : return zend_hash_index_exists(ht, h);
952 : }
953 :
954 : IS_CONSISTENT(ht);
955 :
956 931 : nIndex = h & ht->nTableMask;
957 :
958 931 : p = ht->arBuckets[nIndex];
959 1950 : while (p != NULL) {
960 490 : if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
961 402 : if (!memcmp(p->arKey, arKey, nKeyLength)) {
962 402 : return 1;
963 : }
964 : }
965 88 : p = p->pNext;
966 : }
967 529 : return 0;
968 :
969 : }
970 :
971 :
972 : ZEND_API int zend_hash_index_find(HashTable *ht, ulong h, void **pData)
973 15947213 : {
974 : uint nIndex;
975 : Bucket *p;
976 :
977 : IS_CONSISTENT(ht);
978 :
979 15947213 : nIndex = h & ht->nTableMask;
980 :
981 15947213 : p = ht->arBuckets[nIndex];
982 32555525 : while (p != NULL) {
983 14364948 : if ((p->h == h) && (p->nKeyLength == 0)) {
984 13703849 : *pData = p->pData;
985 13703849 : return SUCCESS;
986 : }
987 661099 : p = p->pNext;
988 : }
989 2243364 : return FAILURE;
990 : }
991 :
992 :
993 : ZEND_API int zend_hash_index_exists(HashTable *ht, ulong h)
994 1017756 : {
995 : uint nIndex;
996 : Bucket *p;
997 :
998 : IS_CONSISTENT(ht);
999 :
1000 1017756 : nIndex = h & ht->nTableMask;
1001 :
1002 1017756 : p = ht->arBuckets[nIndex];
1003 2428916 : while (p != NULL) {
1004 583534 : if ((p->h == h) && (p->nKeyLength == 0)) {
1005 190130 : return 1;
1006 : }
1007 393404 : p = p->pNext;
1008 : }
1009 827626 : return 0;
1010 : }
1011 :
1012 :
1013 : ZEND_API int zend_hash_num_elements(HashTable *ht)
1014 2744690 : {
1015 : IS_CONSISTENT(ht);
1016 :
1017 2744690 : return ht->nNumOfElements;
1018 : }
1019 :
1020 :
1021 : ZEND_API int zend_hash_get_pointer(HashTable *ht, HashPointer *ptr)
1022 1411301 : {
1023 1411301 : ptr->pos = ht->pInternalPointer;
1024 1411301 : if (ht->pInternalPointer) {
1025 1370587 : ptr->h = ht->pInternalPointer->h;
1026 1370587 : return 1;
1027 : } else {
1028 40714 : ptr->h = 0;
1029 40714 : return 0;
1030 : }
1031 : }
1032 :
1033 : ZEND_API int zend_hash_set_pointer(HashTable *ht, const HashPointer *ptr)
1034 1411059 : {
1035 1411059 : if (ptr->pos == NULL) {
1036 40666 : ht->pInternalPointer = NULL;
1037 1370393 : } 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 1410990 : return 1;
1052 : }
1053 :
1054 : ZEND_API void zend_hash_internal_pointer_reset_ex(HashTable *ht, HashPosition *pos)
1055 2756876 : {
1056 : IS_CONSISTENT(ht);
1057 :
1058 2756876 : if (pos)
1059 215412 : *pos = ht->pListHead;
1060 : else
1061 2541464 : ht->pInternalPointer = ht->pListHead;
1062 2756876 : }
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 277 : {
1070 : IS_CONSISTENT(ht);
1071 :
1072 277 : if (pos)
1073 162 : *pos = ht->pListTail;
1074 : else
1075 115 : ht->pInternalPointer = ht->pListTail;
1076 277 : }
1077 :
1078 :
1079 : ZEND_API int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos)
1080 9085003 : {
1081 9085003 : HashPosition *current = pos ? pos : &ht->pInternalPointer;
1082 :
1083 : IS_CONSISTENT(ht);
1084 :
1085 9085003 : if (*current) {
1086 9084978 : *current = (*current)->pListNext;
1087 9084978 : return SUCCESS;
1088 : } else
1089 25 : return FAILURE;
1090 : }
1091 :
1092 : ZEND_API int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos)
1093 572 : {
1094 572 : HashPosition *current = pos ? pos : &ht->pInternalPointer;
1095 :
1096 : IS_CONSISTENT(ht);
1097 :
1098 572 : if (*current) {
1099 570 : *current = (*current)->pListLast;
1100 570 : 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(HashTable *ht, char **str_index, uint *str_length, ulong *num_index, zend_bool duplicate, HashPosition *pos)
1108 2307206 : {
1109 : Bucket *p;
1110 :
1111 2307206 : p = pos ? (*pos) : ht->pInternalPointer;
1112 :
1113 : IS_CONSISTENT(ht);
1114 :
1115 2307206 : if (p) {
1116 2298074 : if (p->nKeyLength) {
1117 2244679 : if (duplicate) {
1118 1002040 : *str_index = estrndup(p->arKey, p->nKeyLength - 1);
1119 : } else {
1120 1242639 : *str_index = p->arKey;
1121 : }
1122 2244679 : if (str_length) {
1123 2243514 : *str_length = p->nKeyLength;
1124 : }
1125 2244679 : return HASH_KEY_IS_STRING;
1126 : } else {
1127 53395 : *num_index = p->h;
1128 53395 : return HASH_KEY_IS_LONG;
1129 : }
1130 : }
1131 9132 : return HASH_KEY_NON_EXISTANT;
1132 : }
1133 :
1134 :
1135 : ZEND_API int zend_hash_get_current_key_type_ex(HashTable *ht, HashPosition *pos)
1136 45561 : {
1137 : Bucket *p;
1138 :
1139 45561 : p = pos ? (*pos) : ht->pInternalPointer;
1140 :
1141 : IS_CONSISTENT(ht);
1142 :
1143 45561 : if (p) {
1144 44849 : if (p->nKeyLength) {
1145 25745 : return HASH_KEY_IS_STRING;
1146 : } else {
1147 19104 : return HASH_KEY_IS_LONG;
1148 : }
1149 : }
1150 712 : 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 11201152 : {
1156 : Bucket *p;
1157 :
1158 11201152 : p = pos ? (*pos) : ht->pInternalPointer;
1159 :
1160 : IS_CONSISTENT(ht);
1161 :
1162 11201152 : if (p) {
1163 9091808 : *pData = p->pData;
1164 9091808 : return SUCCESS;
1165 : } else {
1166 2109344 : 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, char *str_index, uint str_length, ulong num_index, HashPosition *pos)
1174 28 : {
1175 : Bucket *p;
1176 :
1177 28 : p = pos ? (*pos) : ht->pInternalPointer;
1178 :
1179 : IS_CONSISTENT(ht);
1180 :
1181 28 : if (p) {
1182 28 : if (key_type == HASH_KEY_IS_LONG) {
1183 12 : str_length = 0;
1184 12 : if (!p->nKeyLength && p->h == num_index) {
1185 0 : return SUCCESS;
1186 : }
1187 12 : zend_hash_index_del(ht, num_index);
1188 16 : } else if (key_type == HASH_KEY_IS_STRING) {
1189 16 : if (p->nKeyLength == str_length &&
1190 : memcmp(p->arKey, str_index, str_length) == 0) {
1191 0 : return SUCCESS;
1192 : }
1193 16 : zend_hash_del(ht, str_index, str_length);
1194 : } else {
1195 0 : return FAILURE;
1196 : }
1197 :
1198 28 : HANDLE_BLOCK_INTERRUPTIONS();
1199 :
1200 28 : if (p->pNext) {
1201 0 : p->pNext->pLast = p->pLast;
1202 : }
1203 28 : if (p->pLast) {
1204 0 : p->pLast->pNext = p->pNext;
1205 : } else{
1206 28 : ht->arBuckets[p->h & ht->nTableMask] = p->pNext;
1207 : }
1208 :
1209 28 : if (p->nKeyLength != str_length) {
1210 28 : Bucket *q = (Bucket *) pemalloc(sizeof(Bucket) - 1 + str_length, ht->persistent);
1211 :
1212 28 : q->nKeyLength = str_length;
1213 28 : if (p->pData == &p->pDataPtr) {
1214 28 : q->pData = &q->pDataPtr;
1215 : } else {
1216 0 : q->pData = p->pData;
1217 : }
1218 28 : q->pDataPtr = p->pDataPtr;
1219 28 : q->pListNext = p->pListNext;
1220 28 : q->pListLast = p->pListLast;
1221 28 : if (q->pListNext) {
1222 7 : p->pListNext->pListLast = q;
1223 : } else {
1224 21 : ht->pListTail = q;
1225 : }
1226 28 : if (q->pListLast) {
1227 6 : p->pListLast->pListNext = q;
1228 : } else {
1229 22 : ht->pListHead = q;
1230 : }
1231 28 : if (ht->pInternalPointer == p) {
1232 28 : ht->pInternalPointer = q;
1233 : }
1234 28 : if (pos) {
1235 0 : *pos = q;
1236 : }
1237 28 : pefree(p, ht->persistent);
1238 28 : p = q;
1239 : }
1240 :
1241 28 : if (key_type == HASH_KEY_IS_LONG) {
1242 12 : p->h = num_index;
1243 : } else {
1244 16 : memcpy(p->arKey, str_index, str_length);
1245 16 : p->h = zend_inline_hash_func(str_index, str_length);
1246 : }
1247 :
1248 28 : CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[p->h & ht->nTableMask]);
1249 28 : ht->arBuckets[p->h & ht->nTableMask] = p;
1250 28 : HANDLE_UNBLOCK_INTERRUPTIONS();
1251 :
1252 28 : return SUCCESS;
1253 : } else {
1254 0 : return FAILURE;
1255 : }
1256 : }
1257 :
1258 : ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func,
1259 : compare_func_t compar, int renumber TSRMLS_DC)
1260 14276 : {
1261 : Bucket **arTmp;
1262 : Bucket *p;
1263 : int i, j;
1264 :
1265 : IS_CONSISTENT(ht);
1266 :
1267 14276 : if (!(ht->nNumOfElements>1) && !(renumber && ht->nNumOfElements>0)) { /* Doesn't require sorting */
1268 51 : return SUCCESS;
1269 : }
1270 14225 : arTmp = (Bucket **) pemalloc(ht->nNumOfElements * sizeof(Bucket *), ht->persistent);
1271 14225 : if (!arTmp) {
1272 0 : return FAILURE;
1273 : }
1274 14225 : p = ht->pListHead;
1275 14225 : i = 0;
1276 858985 : while (p) {
1277 830535 : arTmp[i] = p;
1278 830535 : p = p->pListNext;
1279 830535 : i++;
1280 : }
1281 :
1282 14225 : (*sort_func)((void *) arTmp, i, sizeof(Bucket *), compar TSRMLS_CC);
1283 :
1284 14225 : HANDLE_BLOCK_INTERRUPTIONS();
1285 14225 : ht->pListHead = arTmp[0];
1286 14225 : ht->pListTail = NULL;
1287 14225 : ht->pInternalPointer = ht->pListHead;
1288 :
1289 14225 : arTmp[0]->pListLast = NULL;
1290 14225 : if (i > 1) {
1291 14217 : arTmp[0]->pListNext = arTmp[1];
1292 816310 : for (j = 1; j < i-1; j++) {
1293 802093 : arTmp[j]->pListLast = arTmp[j-1];
1294 802093 : arTmp[j]->pListNext = arTmp[j+1];
1295 : }
1296 14217 : arTmp[j]->pListLast = arTmp[j-1];
1297 14217 : arTmp[j]->pListNext = NULL;
1298 : } else {
1299 8 : arTmp[0]->pListNext = NULL;
1300 : }
1301 14225 : ht->pListTail = arTmp[i-1];
1302 :
1303 14225 : pefree(arTmp, ht->persistent);
1304 14225 : HANDLE_UNBLOCK_INTERRUPTIONS();
1305 :
1306 14225 : if (renumber) {
1307 223 : p = ht->pListHead;
1308 223 : i=0;
1309 10705 : while (p != NULL) {
1310 10259 : p->nKeyLength = 0;
1311 10259 : p->h = i++;
1312 10259 : p = p->pListNext;
1313 : }
1314 223 : ht->nNextFreeElement = i;
1315 223 : zend_hash_rehash(ht);
1316 : }
1317 14225 : return SUCCESS;
1318 : }
1319 :
1320 :
1321 : ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered TSRMLS_DC)
1322 645 : {
1323 645 : Bucket *p1, *p2 = NULL;
1324 : int result;
1325 : void *pData2;
1326 :
1327 : IS_CONSISTENT(ht1);
1328 : IS_CONSISTENT(ht2);
1329 :
1330 645 : HASH_PROTECT_RECURSION(ht1);
1331 645 : HASH_PROTECT_RECURSION(ht2);
1332 :
1333 645 : result = ht1->nNumOfElements - ht2->nNumOfElements;
1334 645 : if (result!=0) {
1335 116 : HASH_UNPROTECT_RECURSION(ht1);
1336 116 : HASH_UNPROTECT_RECURSION(ht2);
1337 116 : return result;
1338 : }
1339 :
1340 529 : p1 = ht1->pListHead;
1341 529 : if (ordered) {
1342 36 : p2 = ht2->pListHead;
1343 : }
1344 :
1345 1701 : while (p1) {
1346 953 : if (ordered && !p2) {
1347 0 : HASH_UNPROTECT_RECURSION(ht1);
1348 0 : HASH_UNPROTECT_RECURSION(ht2);
1349 0 : return 1; /* That's not supposed to happen */
1350 : }
1351 953 : if (ordered) {
1352 784 : if (p1->nKeyLength==0 && p2->nKeyLength==0) { /* numeric indices */
1353 339 : result = p1->h - p2->h;
1354 339 : if (result!=0) {
1355 0 : HASH_UNPROTECT_RECURSION(ht1);
1356 0 : HASH_UNPROTECT_RECURSION(ht2);
1357 0 : return result;
1358 : }
1359 : } else { /* string indices */
1360 106 : result = p1->nKeyLength - p2->nKeyLength;
1361 106 : if (result!=0) {
1362 0 : HASH_UNPROTECT_RECURSION(ht1);
1363 0 : HASH_UNPROTECT_RECURSION(ht2);
1364 0 : return result;
1365 : }
1366 106 : result = memcmp(p1->arKey, p2->arKey, p1->nKeyLength);
1367 106 : if (result!=0) {
1368 0 : HASH_UNPROTECT_RECURSION(ht1);
1369 0 : HASH_UNPROTECT_RECURSION(ht2);
1370 0 : return result;
1371 : }
1372 : }
1373 445 : pData2 = p2->pData;
1374 : } else {
1375 508 : if (p1->nKeyLength==0) { /* numeric index */
1376 200 : if (zend_hash_index_find(ht2, p1->h, &pData2)==FAILURE) {
1377 2 : HASH_UNPROTECT_RECURSION(ht1);
1378 2 : HASH_UNPROTECT_RECURSION(ht2);
1379 2 : return 1;
1380 : }
1381 : } else { /* string index */
1382 308 : if (zend_hash_find(ht2, p1->arKey, p1->nKeyLength, &pData2)==FAILURE) {
1383 2 : HASH_UNPROTECT_RECURSION(ht1);
1384 2 : HASH_UNPROTECT_RECURSION(ht2);
1385 2 : return 1;
1386 : }
1387 : }
1388 : }
1389 949 : result = compar(p1->pData, pData2 TSRMLS_CC);
1390 949 : if (result!=0) {
1391 306 : HASH_UNPROTECT_RECURSION(ht1);
1392 306 : HASH_UNPROTECT_RECURSION(ht2);
1393 306 : return result;
1394 : }
1395 643 : p1 = p1->pListNext;
1396 643 : if (ordered) {
1397 442 : p2 = p2->pListNext;
1398 : }
1399 : }
1400 :
1401 219 : HASH_UNPROTECT_RECURSION(ht1);
1402 219 : HASH_UNPROTECT_RECURSION(ht2);
1403 219 : return 0;
1404 : }
1405 :
1406 :
1407 : ZEND_API int zend_hash_minmax(HashTable *ht, compare_func_t compar, int flag, void **pData TSRMLS_DC)
1408 78 : {
1409 : Bucket *p, *res;
1410 :
1411 : IS_CONSISTENT(ht);
1412 :
1413 78 : if (ht->nNumOfElements == 0 ) {
1414 4 : *pData=NULL;
1415 4 : return FAILURE;
1416 : }
1417 :
1418 74 : res = p = ht->pListHead;
1419 316 : while ((p = p->pListNext)) {
1420 168 : if (flag) {
1421 142 : if (compar(&res, &p TSRMLS_CC) < 0) { /* max */
1422 20 : res = p;
1423 : }
1424 : } else {
1425 26 : if (compar(&res, &p TSRMLS_CC) > 0) { /* min */
1426 4 : res = p;
1427 : }
1428 : }
1429 : }
1430 74 : *pData = res->pData;
1431 74 : return SUCCESS;
1432 : }
1433 :
1434 : ZEND_API ulong zend_hash_next_free_element(HashTable *ht)
1435 435364 : {
1436 : IS_CONSISTENT(ht);
1437 :
1438 435364 : return ht->nNextFreeElement;
1439 :
1440 : }
1441 :
1442 :
1443 : #if ZEND_DEBUG
1444 : void zend_hash_display_pListTail(HashTable *ht)
1445 : {
1446 : Bucket *p;
1447 :
1448 : p = ht->pListTail;
1449 : while (p != NULL) {
1450 : zend_output_debug_string(0, "pListTail has key %s\n", p->arKey);
1451 : p = p->pListLast;
1452 : }
1453 : }
1454 :
1455 : void zend_hash_display(HashTable *ht)
1456 : {
1457 : Bucket *p;
1458 : uint i;
1459 :
1460 : for (i = 0; i < ht->nTableSize; i++) {
1461 : p = ht->arBuckets[i];
1462 : while (p != NULL) {
1463 : zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h);
1464 : p = p->pNext;
1465 : }
1466 : }
1467 :
1468 : p = ht->pListTail;
1469 : while (p != NULL) {
1470 : zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h);
1471 : p = p->pListLast;
1472 : }
1473 : }
1474 : #endif
1475 :
1476 : /*
1477 : * Local variables:
1478 : * tab-width: 4
1479 : * c-basic-offset: 4
1480 : * indent-tabs-mode: t
1481 : * End:
1482 : */
|
