1 : /*
2 : +----------------------------------------------------------------------+
3 : | Zend Engine |
4 : +----------------------------------------------------------------------+
5 : | Copyright (c) 1998-2007 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.121.2.4.2.7 2007/02/21 14:11:00 dmitry Exp $ */
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 1990 : {
99 1990 : 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 121711 : {
139 121711 : uint i = 3;
140 : Bucket **tmp;
141 :
142 : SET_INCONSISTENT(HT_OK);
143 :
144 121711 : if (nSize >= 0x80000000) {
145 : /* prevent overflow */
146 0 : ht->nTableSize = 0x80000000;
147 : } else {
148 249302 : while ((1U << i) < nSize) {
149 5880 : i++;
150 : }
151 121711 : ht->nTableSize = 1 << i;
152 : }
153 :
154 121711 : ht->nTableMask = ht->nTableSize - 1;
155 121711 : ht->pDestructor = pDestructor;
156 121711 : ht->arBuckets = NULL;
157 121711 : ht->pListHead = NULL;
158 121711 : ht->pListTail = NULL;
159 121711 : ht->nNumOfElements = 0;
160 121711 : ht->nNextFreeElement = 0;
161 121711 : ht->pInternalPointer = NULL;
162 121711 : ht->persistent = persistent;
163 121711 : ht->nApplyCount = 0;
164 121711 : ht->bApplyProtection = 1;
165 :
166 : /* Uses ecalloc() so that Bucket* == NULL */
167 121711 : if (persistent) {
168 101232 : tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *));
169 101232 : if (!tmp) {
170 0 : return FAILURE;
171 : }
172 101232 : ht->arBuckets = tmp;
173 : } else {
174 20479 : tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket *));
175 20479 : if (tmp) {
176 20479 : ht->arBuckets = tmp;
177 : }
178 : }
179 :
180 121711 : 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 97265 : {
186 97265 : int retval = _zend_hash_init(ht, nSize, pHashFunction, pDestructor, persistent ZEND_FILE_LINE_CC);
187 :
188 97265 : ht->bApplyProtection = bApplyProtection;
189 97265 : 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 578662 : {
202 : ulong h;
203 : uint nIndex;
204 : Bucket *p;
205 :
206 : IS_CONSISTENT(ht);
207 :
208 578662 : 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 578662 : h = zend_inline_hash_func(arKey, nKeyLength);
216 578662 : nIndex = h & ht->nTableMask;
217 :
218 578662 : p = ht->arBuckets[nIndex];
219 1492855 : while (p != NULL) {
220 343282 : if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
221 7751 : if (!memcmp(p->arKey, arKey, nKeyLength)) {
222 7751 : if (flag & HASH_ADD) {
223 1 : return FAILURE;
224 : }
225 7750 : 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 7750 : if (ht->pDestructor) {
234 7750 : ht->pDestructor(p->pData);
235 : }
236 7750 : UPDATE_DATA(ht, p, pData, nDataSize);
237 7750 : if (pDest) {
238 1 : *pDest = p->pData;
239 : }
240 7750 : HANDLE_UNBLOCK_INTERRUPTIONS();
241 7750 : return SUCCESS;
242 : }
243 : }
244 335531 : p = p->pNext;
245 : }
246 :
247 570911 : p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
248 570911 : if (!p) {
249 0 : return FAILURE;
250 : }
251 570911 : memcpy(p->arKey, arKey, nKeyLength);
252 570911 : p->nKeyLength = nKeyLength;
253 570911 : INIT_DATA(ht, p, pData, nDataSize);
254 570911 : p->h = h;
255 570911 : CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
256 570911 : if (pDest) {
257 355846 : *pDest = p->pData;
258 : }
259 :
260 570911 : HANDLE_BLOCK_INTERRUPTIONS();
261 570911 : CONNECT_TO_GLOBAL_DLLIST(p, ht);
262 570911 : ht->arBuckets[nIndex] = p;
263 570911 : HANDLE_UNBLOCK_INTERRUPTIONS();
264 :
265 570911 : ht->nNumOfElements++;
266 570911 : ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */
267 570911 : 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 404525 : {
272 : uint nIndex;
273 : Bucket *p;
274 :
275 : IS_CONSISTENT(ht);
276 :
277 404525 : if (nKeyLength == 0) {
278 0 : return zend_hash_index_update(ht, h, pData, nDataSize, pDest);
279 : }
280 :
281 404525 : nIndex = h & ht->nTableMask;
282 :
283 404525 : p = ht->arBuckets[nIndex];
284 994462 : while (p != NULL) {
285 185436 : if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
286 24 : if (!memcmp(p->arKey, arKey, nKeyLength)) {
287 24 : if (flag & HASH_ADD) {
288 0 : return FAILURE;
289 : }
290 24 : 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 24 : if (ht->pDestructor) {
299 24 : ht->pDestructor(p->pData);
300 : }
301 24 : UPDATE_DATA(ht, p, pData, nDataSize);
302 24 : if (pDest) {
303 16 : *pDest = p->pData;
304 : }
305 24 : HANDLE_UNBLOCK_INTERRUPTIONS();
306 24 : return SUCCESS;
307 : }
308 : }
309 185412 : p = p->pNext;
310 : }
311 :
312 404501 : p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
313 404501 : if (!p) {
314 0 : return FAILURE;
315 : }
316 :
317 404501 : memcpy(p->arKey, arKey, nKeyLength);
318 404501 : p->nKeyLength = nKeyLength;
319 404501 : INIT_DATA(ht, p, pData, nDataSize);
320 404501 : p->h = h;
321 :
322 404501 : CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
323 :
324 404501 : if (pDest) {
325 403989 : *pDest = p->pData;
326 : }
327 :
328 404501 : HANDLE_BLOCK_INTERRUPTIONS();
329 404501 : ht->arBuckets[nIndex] = p;
330 404501 : CONNECT_TO_GLOBAL_DLLIST(p, ht);
331 404501 : HANDLE_UNBLOCK_INTERRUPTIONS();
332 :
333 404501 : ht->nNumOfElements++;
334 404501 : ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */
335 404501 : return SUCCESS;
336 : }
337 :
338 :
339 : ZEND_API int zend_hash_add_empty_element(HashTable *ht, char *arKey, uint nKeyLength)
340 0 : {
341 0 : void *dummy = (void *) 1;
342 :
343 0 : 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 24286 : {
349 : uint nIndex;
350 : Bucket *p;
351 :
352 : IS_CONSISTENT(ht);
353 :
354 24286 : if (flag & HASH_NEXT_INSERT) {
355 12797 : h = ht->nNextFreeElement;
356 : }
357 24286 : nIndex = h & ht->nTableMask;
358 :
359 24286 : p = ht->arBuckets[nIndex];
360 49295 : while (p != NULL) {
361 724 : if ((p->nKeyLength == 0) && (p->h == h)) {
362 1 : if (flag & HASH_NEXT_INSERT || flag & HASH_ADD) {
363 0 : return FAILURE;
364 : }
365 1 : 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 1 : if (ht->pDestructor) {
374 1 : ht->pDestructor(p->pData);
375 : }
376 1 : UPDATE_DATA(ht, p, pData, nDataSize);
377 1 : HANDLE_UNBLOCK_INTERRUPTIONS();
378 1 : if ((long)h >= (long)ht->nNextFreeElement) {
379 0 : ht->nNextFreeElement = h + 1;
380 : }
381 1 : if (pDest) {
382 0 : *pDest = p->pData;
383 : }
384 1 : return SUCCESS;
385 : }
386 723 : p = p->pNext;
387 : }
388 24285 : p = (Bucket *) pemalloc_rel(sizeof(Bucket) - 1, ht->persistent);
389 24285 : if (!p) {
390 0 : return FAILURE;
391 : }
392 24285 : p->nKeyLength = 0; /* Numeric indices are marked by making the nKeyLength == 0 */
393 24285 : p->h = h;
394 24285 : INIT_DATA(ht, p, pData, nDataSize);
395 24285 : if (pDest) {
396 10340 : *pDest = p->pData;
397 : }
398 :
399 24285 : CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
400 :
401 24285 : HANDLE_BLOCK_INTERRUPTIONS();
402 24285 : ht->arBuckets[nIndex] = p;
403 24285 : CONNECT_TO_GLOBAL_DLLIST(p, ht);
404 24285 : HANDLE_UNBLOCK_INTERRUPTIONS();
405 :
406 24285 : if ((long)h >= (long)ht->nNextFreeElement) {
407 24240 : ht->nNextFreeElement = h + 1;
408 : }
409 24285 : ht->nNumOfElements++;
410 24285 : ZEND_HASH_IF_FULL_DO_RESIZE(ht);
411 24285 : return SUCCESS;
412 : }
413 :
414 :
415 : static int zend_hash_do_resize(HashTable *ht)
416 27705 : {
417 : Bucket **t;
418 :
419 : IS_CONSISTENT(ht);
420 :
421 27705 : if ((ht->nTableSize << 1) > 0) { /* Let's double the table size */
422 27705 : t = (Bucket **) perealloc_recoverable(ht->arBuckets, (ht->nTableSize << 1) * sizeof(Bucket *), ht->persistent);
423 27705 : if (t) {
424 27705 : HANDLE_BLOCK_INTERRUPTIONS();
425 27705 : ht->arBuckets = t;
426 27705 : ht->nTableSize = (ht->nTableSize << 1);
427 27705 : ht->nTableMask = ht->nTableSize - 1;
428 27705 : zend_hash_rehash(ht);
429 27705 : HANDLE_UNBLOCK_INTERRUPTIONS();
430 27705 : return SUCCESS;
431 : }
432 0 : return FAILURE;
433 : }
434 0 : return SUCCESS;
435 : }
436 :
437 : ZEND_API int zend_hash_rehash(HashTable *ht)
438 27706 : {
439 : Bucket *p;
440 : uint nIndex;
441 :
442 : IS_CONSISTENT(ht);
443 :
444 27706 : memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
445 27706 : p = ht->pListHead;
446 763859 : while (p != NULL) {
447 708447 : nIndex = p->h & ht->nTableMask;
448 708447 : CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
449 708447 : ht->arBuckets[nIndex] = p;
450 708447 : p = p->pListNext;
451 : }
452 27706 : 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 150086 : {
457 : uint nIndex;
458 : Bucket *p;
459 :
460 : IS_CONSISTENT(ht);
461 :
462 150086 : if (flag == HASH_DEL_KEY) {
463 148387 : h = zend_inline_hash_func(arKey, nKeyLength);
464 : }
465 150086 : nIndex = h & ht->nTableMask;
466 :
467 150086 : p = ht->arBuckets[nIndex];
468 341820 : while (p != NULL) {
469 190823 : 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 149175 : HANDLE_BLOCK_INTERRUPTIONS();
474 149175 : if (p == ht->arBuckets[nIndex]) {
475 114568 : ht->arBuckets[nIndex] = p->pNext;
476 : } else {
477 34607 : p->pLast->pNext = p->pNext;
478 : }
479 149175 : if (p->pNext) {
480 11393 : p->pNext->pLast = p->pLast;
481 : }
482 149175 : if (p->pListLast != NULL) {
483 147500 : p->pListLast->pListNext = p->pListNext;
484 : } else {
485 : /* Deleting the head of the list */
486 1675 : ht->pListHead = p->pListNext;
487 : }
488 149175 : if (p->pListNext != NULL) {
489 146810 : p->pListNext->pListLast = p->pListLast;
490 : } else {
491 2365 : ht->pListTail = p->pListLast;
492 : }
493 149175 : if (ht->pInternalPointer == p) {
494 1708 : ht->pInternalPointer = p->pListNext;
495 : }
496 149175 : if (ht->pDestructor) {
497 146949 : ht->pDestructor(p->pData);
498 : }
499 149175 : if (p->pData != &p->pDataPtr) {
500 146896 : pefree(p->pData, ht->persistent);
501 : }
502 149175 : pefree(p, ht->persistent);
503 149175 : HANDLE_UNBLOCK_INTERRUPTIONS();
504 149175 : ht->nNumOfElements--;
505 149175 : return SUCCESS;
506 : }
507 41648 : p = p->pNext;
508 : }
509 911 : return FAILURE;
510 : }
511 :
512 :
513 : ZEND_API void zend_hash_destroy(HashTable *ht)
514 120370 : {
515 : Bucket *p, *q;
516 :
517 : IS_CONSISTENT(ht);
518 :
519 : SET_INCONSISTENT(HT_IS_DESTROYING);
520 :
521 120370 : p = ht->pListHead;
522 859940 : while (p != NULL) {
523 619200 : q = p;
524 619200 : p = p->pListNext;
525 619200 : if (ht->pDestructor) {
526 602784 : ht->pDestructor(q->pData);
527 : }
528 619200 : if (q->pData != &q->pDataPtr) {
529 445883 : pefree(q->pData, ht->persistent);
530 : }
531 619200 : pefree(q, ht->persistent);
532 : }
533 120370 : pefree(ht->arBuckets, ht->persistent);
534 :
535 : SET_INCONSISTENT(HT_DESTROYED);
536 120370 : }
537 :
538 :
539 : ZEND_API void zend_hash_clean(HashTable *ht)
540 29416 : {
541 : Bucket *p, *q;
542 :
543 : IS_CONSISTENT(ht);
544 :
545 : SET_INCONSISTENT(HT_CLEANING);
546 :
547 29416 : p = ht->pListHead;
548 246009 : while (p != NULL) {
549 187177 : q = p;
550 187177 : p = p->pListNext;
551 187177 : if (ht->pDestructor) {
552 187177 : ht->pDestructor(q->pData);
553 : }
554 187177 : if (q->pData != &q->pDataPtr) {
555 0 : pefree(q->pData, ht->persistent);
556 : }
557 187177 : pefree(q, ht->persistent);
558 : }
559 29416 : memset(ht->arBuckets, 0, ht->nTableSize*sizeof(Bucket *));
560 29416 : ht->pListHead = NULL;
561 29416 : ht->pListTail = NULL;
562 29416 : ht->nNumOfElements = 0;
563 29416 : ht->nNextFreeElement = 0;
564 29416 : ht->pInternalPointer = NULL;
565 :
566 : SET_INCONSISTENT(HT_OK);
567 29416 : }
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 40792 : {
576 : Bucket *retval;
577 :
578 40792 : HANDLE_BLOCK_INTERRUPTIONS();
579 40792 : if (p->pLast) {
580 3066 : p->pLast->pNext = p->pNext;
581 : } else {
582 : uint nIndex;
583 :
584 37726 : nIndex = p->h & ht->nTableMask;
585 37726 : ht->arBuckets[nIndex] = p->pNext;
586 : }
587 40792 : if (p->pNext) {
588 7100 : p->pNext->pLast = p->pLast;
589 : } else {
590 : /* Nothing to do as this list doesn't have a tail */
591 : }
592 :
593 40792 : if (p->pListLast != NULL) {
594 21806 : p->pListLast->pListNext = p->pListNext;
595 : } else {
596 : /* Deleting the head of the list */
597 18986 : ht->pListHead = p->pListNext;
598 : }
599 40792 : if (p->pListNext != NULL) {
600 32203 : p->pListNext->pListLast = p->pListLast;
601 : } else {
602 8589 : ht->pListTail = p->pListLast;
603 : }
604 40792 : if (ht->pInternalPointer == p) {
605 18986 : ht->pInternalPointer = p->pListNext;
606 : }
607 40792 : ht->nNumOfElements--;
608 40792 : HANDLE_UNBLOCK_INTERRUPTIONS();
609 :
610 40792 : if (ht->pDestructor) {
611 6817 : ht->pDestructor(p->pData);
612 : }
613 40792 : if (p->pData != &p->pDataPtr) {
614 37304 : pefree(p->pData, ht->persistent);
615 : }
616 40792 : retval = p->pListNext;
617 40792 : pefree(p, ht->persistent);
618 :
619 40792 : 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 876 : {
640 : Bucket *p;
641 :
642 : IS_CONSISTENT(ht);
643 :
644 876 : p = ht->pListTail;
645 7464 : while (p != NULL) {
646 5712 : zend_hash_apply_deleter(ht, p);
647 5712 : p = ht->pListTail;
648 : }
649 :
650 876 : pefree(ht->arBuckets, ht->persistent);
651 :
652 : SET_INCONSISTENT(HT_DESTROYED);
653 876 : }
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 1567 : {
666 : Bucket *p;
667 :
668 : IS_CONSISTENT(ht);
669 :
670 1567 : HASH_PROTECT_RECURSION(ht);
671 1567 : p = ht->pListHead;
672 33175 : while (p != NULL) {
673 30041 : int result = apply_func(p->pData TSRMLS_CC);
674 :
675 30041 : if (result & ZEND_HASH_APPLY_REMOVE) {
676 34 : p = zend_hash_apply_deleter(ht, p);
677 : } else {
678 30007 : p = p->pListNext;
679 : }
680 30041 : if (result & ZEND_HASH_APPLY_STOP) {
681 0 : break;
682 : }
683 : }
684 1567 : HASH_UNPROTECT_RECURSION(ht);
685 1567 : }
686 :
687 :
688 : ZEND_API void zend_hash_apply_with_argument(HashTable *ht, apply_func_arg_t apply_func, void *argument TSRMLS_DC)
689 2266 : {
690 : Bucket *p;
691 :
692 : IS_CONSISTENT(ht);
693 :
694 2266 : HASH_PROTECT_RECURSION(ht);
695 2266 : p = ht->pListHead;
696 250141 : while (p != NULL) {
697 245609 : int result = apply_func(p->pData, argument TSRMLS_CC);
698 :
699 245609 : if (result & ZEND_HASH_APPLY_REMOVE) {
700 33941 : p = zend_hash_apply_deleter(ht, p);
701 : } else {
702 211668 : p = p->pListNext;
703 : }
704 245609 : if (result & ZEND_HASH_APPLY_STOP) {
705 0 : break;
706 : }
707 : }
708 2266 : HASH_UNPROTECT_RECURSION(ht);
709 2266 : }
710 :
711 :
712 : ZEND_API void zend_hash_apply_with_arguments(HashTable *ht, apply_func_args_t apply_func, int num_args, ...)
713 10274 : {
714 : Bucket *p;
715 : va_list args;
716 : zend_hash_key hash_key;
717 :
718 : IS_CONSISTENT(ht);
719 :
720 10274 : HASH_PROTECT_RECURSION(ht);
721 :
722 10274 : p = ht->pListHead;
723 21010 : while (p != NULL) {
724 : int result;
725 462 : va_start(args, num_args);
726 462 : hash_key.arKey = p->arKey;
727 462 : hash_key.nKeyLength = p->nKeyLength;
728 462 : hash_key.h = p->h;
729 462 : result = apply_func(p->pData, num_args, args, &hash_key);
730 :
731 462 : if (result & ZEND_HASH_APPLY_REMOVE) {
732 0 : p = zend_hash_apply_deleter(ht, p);
733 : } else {
734 462 : p = p->pListNext;
735 : }
736 462 : if (result & ZEND_HASH_APPLY_STOP) {
737 0 : break;
738 : }
739 462 : va_end(args);
740 : }
741 :
742 10274 : HASH_UNPROTECT_RECURSION(ht);
743 10274 : }
744 :
745 :
746 : ZEND_API void zend_hash_reverse_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC)
747 1343 : {
748 : Bucket *p, *q;
749 :
750 : IS_CONSISTENT(ht);
751 :
752 1343 : HASH_PROTECT_RECURSION(ht);
753 1343 : p = ht->pListTail;
754 8531 : while (p != NULL) {
755 6940 : int result = apply_func(p->pData TSRMLS_CC);
756 :
757 6940 : q = p;
758 6940 : p = p->pListLast;
759 6940 : if (result & ZEND_HASH_APPLY_REMOVE) {
760 1105 : zend_hash_apply_deleter(ht, q);
761 : }
762 6940 : if (result & ZEND_HASH_APPLY_STOP) {
763 1095 : break;
764 : }
765 : }
766 1343 : HASH_UNPROTECT_RECURSION(ht);
767 1343 : }
768 :
769 :
770 : ZEND_API void zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size)
771 2576 : {
772 : Bucket *p;
773 : void *new_entry;
774 :
775 : IS_CONSISTENT(source);
776 : IS_CONSISTENT(target);
777 :
778 2576 : p = source->pListHead;
779 21534 : while (p) {
780 16382 : if (p->nKeyLength) {
781 8316 : zend_hash_quick_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &new_entry);
782 : } else {
783 8066 : zend_hash_index_update(target, p->h, p->pData, size, &new_entry);
784 : }
785 16382 : if (pCopyConstructor) {
786 16382 : pCopyConstructor(new_entry);
787 : }
788 16382 : p = p->pListNext;
789 : }
790 2576 : target->pInternalPointer = target->pListHead;
791 2576 : }
792 :
793 :
794 : 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)
795 20250 : {
796 : Bucket *p;
797 : void *t;
798 20250 : int mode = (overwrite?HASH_UPDATE:HASH_ADD);
799 :
800 : IS_CONSISTENT(source);
801 : IS_CONSISTENT(target);
802 :
803 20250 : p = source->pListHead;
804 85296 : while (p) {
805 44796 : if (p->nKeyLength>0) {
806 44796 : 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) {
807 44796 : pCopyConstructor(t);
808 : }
809 : } else {
810 0 : if ((mode==HASH_UPDATE || !zend_hash_index_exists(target, p->h)) && zend_hash_index_update(target, p->h, p->pData, size, &t)==SUCCESS && pCopyConstructor) {
811 0 : pCopyConstructor(t);
812 : }
813 : }
814 44796 : p = p->pListNext;
815 : }
816 20250 : target->pInternalPointer = target->pListHead;
817 20250 : }
818 :
819 :
820 : static zend_bool zend_hash_replace_checker_wrapper(HashTable *target, void *source_data, Bucket *p, void *pParam, merge_checker_func_t merge_checker_func)
821 200888 : {
822 : zend_hash_key hash_key;
823 :
824 200888 : hash_key.arKey = p->arKey;
825 200888 : hash_key.nKeyLength = p->nKeyLength;
826 200888 : hash_key.h = p->h;
827 200888 : return merge_checker_func(target, source_data, &hash_key, pParam);
828 : }
829 :
830 :
831 : 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)
832 36530 : {
833 : Bucket *p;
834 : void *t;
835 :
836 : IS_CONSISTENT(source);
837 : IS_CONSISTENT(target);
838 :
839 36530 : p = source->pListHead;
840 273948 : while (p) {
841 200888 : if (zend_hash_replace_checker_wrapper(target, p->pData, p, pParam, pMergeSource)) {
842 146733 : if (zend_hash_quick_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &t)==SUCCESS && pCopyConstructor) {
843 146733 : pCopyConstructor(t);
844 : }
845 : }
846 200888 : p = p->pListNext;
847 : }
848 36530 : target->pInternalPointer = target->pListHead;
849 36530 : }
850 :
851 :
852 : ZEND_API ulong zend_get_hash_value(char *arKey, uint nKeyLength)
853 16667 : {
854 16667 : return zend_inline_hash_func(arKey, nKeyLength);
855 : }
856 :
857 :
858 : /* Returns SUCCESS if found and FAILURE if not. The pointer to the
859 : * data is returned in pData. The reason is that there's no reason
860 : * someone using the hash table might not want to have NULL data
861 : */
862 : ZEND_API int zend_hash_find(HashTable *ht, char *arKey, uint nKeyLength, void **pData)
863 226845 : {
864 : ulong h;
865 : uint nIndex;
866 : Bucket *p;
867 :
868 : IS_CONSISTENT(ht);
869 :
870 226845 : h = zend_inline_hash_func(arKey, nKeyLength);
871 226845 : nIndex = h & ht->nTableMask;
872 :
873 226845 : p = ht->arBuckets[nIndex];
874 540958 : while (p != NULL) {
875 267665 : if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
876 180397 : if (!memcmp(p->arKey, arKey, nKeyLength)) {
877 180397 : *pData = p->pData;
878 180397 : return SUCCESS;
879 : }
880 : }
881 87268 : p = p->pNext;
882 : }
883 46448 : return FAILURE;
884 : }
885 :
886 :
887 : ZEND_API int zend_hash_quick_find(HashTable *ht, char *arKey, uint nKeyLength, ulong h, void **pData)
888 398442 : {
889 : uint nIndex;
890 : Bucket *p;
891 :
892 398442 : if (nKeyLength==0) {
893 0 : return zend_hash_index_find(ht, h, pData);
894 : }
895 :
896 : IS_CONSISTENT(ht);
897 :
898 398442 : nIndex = h & ht->nTableMask;
899 :
900 398442 : p = ht->arBuckets[nIndex];
901 986710 : while (p != NULL) {
902 235813 : if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
903 45987 : if (!memcmp(p->arKey, arKey, nKeyLength)) {
904 45987 : *pData = p->pData;
905 45987 : return SUCCESS;
906 : }
907 : }
908 189826 : p = p->pNext;
909 : }
910 352455 : return FAILURE;
911 : }
912 :
913 :
914 : ZEND_API int zend_hash_exists(HashTable *ht, char *arKey, uint nKeyLength)
915 1063 : {
916 : ulong h;
917 : uint nIndex;
918 : Bucket *p;
919 :
920 : IS_CONSISTENT(ht);
921 :
922 1063 : h = zend_inline_hash_func(arKey, nKeyLength);
923 1063 : nIndex = h & ht->nTableMask;
924 :
925 1063 : p = ht->arBuckets[nIndex];
926 2864 : while (p != NULL) {
927 1409 : if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
928 671 : if (!memcmp(p->arKey, arKey, nKeyLength)) {
929 671 : return 1;
930 : }
931 : }
932 738 : p = p->pNext;
933 : }
934 392 : return 0;
935 : }
936 :
937 :
938 : ZEND_API int zend_hash_quick_exists(HashTable *ht, char *arKey, uint nKeyLength, ulong h)
939 2 : {
940 : uint nIndex;
941 : Bucket *p;
942 :
943 2 : if (nKeyLength==0) {
944 0 : return zend_hash_index_exists(ht, h);
945 : }
946 :
947 : IS_CONSISTENT(ht);
948 :
949 2 : nIndex = h & ht->nTableMask;
950 :
951 2 : p = ht->arBuckets[nIndex];
952 4 : while (p != NULL) {
953 0 : if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
954 0 : if (!memcmp(p->arKey, arKey, nKeyLength)) {
955 0 : return 1;
956 : }
957 : }
958 0 : p = p->pNext;
959 : }
960 2 : return 0;
961 :
962 : }
963 :
964 :
965 : ZEND_API int zend_hash_index_find(HashTable *ht, ulong h, void **pData)
966 72596 : {
967 : uint nIndex;
968 : Bucket *p;
969 :
970 : IS_CONSISTENT(ht);
971 :
972 72596 : nIndex = h & ht->nTableMask;
973 :
974 72596 : p = ht->arBuckets[nIndex];
975 148688 : while (p != NULL) {
976 69409 : if ((p->h == h) && (p->nKeyLength == 0)) {
977 65913 : *pData = p->pData;
978 65913 : return SUCCESS;
979 : }
980 3496 : p = p->pNext;
981 : }
982 6683 : return FAILURE;
983 : }
984 :
985 :
986 : ZEND_API int zend_hash_index_exists(HashTable *ht, ulong h)
987 0 : {
988 : uint nIndex;
989 : Bucket *p;
990 :
991 : IS_CONSISTENT(ht);
992 :
993 0 : nIndex = h & ht->nTableMask;
994 :
995 0 : p = ht->arBuckets[nIndex];
996 0 : while (p != NULL) {
997 0 : if ((p->h == h) && (p->nKeyLength == 0)) {
998 0 : return 1;
999 : }
1000 0 : p = p->pNext;
1001 : }
1002 0 : return 0;
1003 : }
1004 :
1005 :
1006 : ZEND_API int zend_hash_num_elements(HashTable *ht)
1007 7409 : {
1008 : IS_CONSISTENT(ht);
1009 :
1010 7409 : return ht->nNumOfElements;
1011 : }
1012 :
1013 :
1014 : ZEND_API int zend_hash_get_pointer(HashTable *ht, HashPointer *ptr)
1015 5543 : {
1016 5543 : ptr->pos = ht->pInternalPointer;
1017 5543 : if (ht->pInternalPointer) {
1018 5017 : ptr->h = ht->pInternalPointer->h;
1019 5017 : return 1;
1020 : } else {
1021 526 : ptr->h = 0;
1022 526 : return 0;
1023 : }
1024 : }
1025 :
1026 : ZEND_API int zend_hash_set_pointer(HashTable *ht, const HashPointer *ptr)
1027 5318 : {
1028 5318 : if (ptr->pos == NULL) {
1029 301 : ht->pInternalPointer = NULL;
1030 5017 : } else if (ht->pInternalPointer != ptr->pos) {
1031 : Bucket *p;
1032 :
1033 : IS_CONSISTENT(ht);
1034 0 : p = ht->arBuckets[ptr->h & ht->nTableMask];
1035 0 : while (p != NULL) {
1036 0 : if (p == ptr->pos) {
1037 0 : ht->pInternalPointer = p;
1038 0 : return 1;
1039 : }
1040 0 : p = p->pNext;
1041 : }
1042 0 : return 0;
1043 : }
1044 5318 : return 1;
1045 : }
1046 :
1047 : ZEND_API void zend_hash_internal_pointer_reset_ex(HashTable *ht, HashPosition *pos)
1048 10619 : {
1049 : IS_CONSISTENT(ht);
1050 :
1051 10619 : if (pos)
1052 2890 : *pos = ht->pListHead;
1053 : else
1054 7729 : ht->pInternalPointer = ht->pListHead;
1055 10619 : }
1056 :
1057 :
1058 : /* This function will be extremely optimized by remembering
1059 : * the end of the list
1060 : */
1061 : ZEND_API void zend_hash_internal_pointer_end_ex(HashTable *ht, HashPosition *pos)
1062 311 : {
1063 : IS_CONSISTENT(ht);
1064 :
1065 311 : if (pos)
1066 0 : *pos = ht->pListTail;
1067 : else
1068 311 : ht->pInternalPointer = ht->pListTail;
1069 311 : }
1070 :
1071 :
1072 : ZEND_API int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos)
1073 46017 : {
1074 46017 : HashPosition *current = pos ? pos : &ht->pInternalPointer;
1075 :
1076 : IS_CONSISTENT(ht);
1077 :
1078 46017 : if (*current) {
1079 46017 : *current = (*current)->pListNext;
1080 46017 : return SUCCESS;
1081 : } else
1082 0 : return FAILURE;
1083 : }
1084 :
1085 : ZEND_API int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos)
1086 0 : {
1087 0 : HashPosition *current = pos ? pos : &ht->pInternalPointer;
1088 :
1089 : IS_CONSISTENT(ht);
1090 :
1091 0 : if (*current) {
1092 0 : *current = (*current)->pListLast;
1093 0 : return SUCCESS;
1094 : } else
1095 0 : return FAILURE;
1096 : }
1097 :
1098 :
1099 : /* This function should be made binary safe */
1100 : 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)
1101 23049 : {
1102 : Bucket *p;
1103 :
1104 23049 : p = pos ? (*pos) : ht->pInternalPointer;
1105 :
1106 : IS_CONSISTENT(ht);
1107 :
1108 23049 : if (p) {
1109 22554 : if (p->nKeyLength) {
1110 21556 : if (duplicate) {
1111 2267 : *str_index = estrndup(p->arKey, p->nKeyLength - 1);
1112 : } else {
1113 19289 : *str_index = p->arKey;
1114 : }
1115 21556 : if (str_length) {
1116 21553 : *str_length = p->nKeyLength;
1117 : }
1118 21556 : return HASH_KEY_IS_STRING;
1119 : } else {
1120 998 : *num_index = p->h;
1121 998 : return HASH_KEY_IS_LONG;
1122 : }
1123 : }
1124 495 : return HASH_KEY_NON_EXISTANT;
1125 : }
1126 :
1127 :
1128 : ZEND_API int zend_hash_get_current_key_type_ex(HashTable *ht, HashPosition *pos)
1129 527 : {
1130 : Bucket *p;
1131 :
1132 527 : p = pos ? (*pos) : ht->pInternalPointer;
1133 :
1134 : IS_CONSISTENT(ht);
1135 :
1136 527 : if (p) {
1137 302 : if (p->nKeyLength) {
1138 116 : return HASH_KEY_IS_STRING;
1139 : } else {
1140 186 : return HASH_KEY_IS_LONG;
1141 : }
1142 : }
1143 225 : return HASH_KEY_NON_EXISTANT;
1144 : }
1145 :
1146 :
1147 : ZEND_API int zend_hash_get_current_data_ex(HashTable *ht, void **pData, HashPosition *pos)
1148 54227 : {
1149 : Bucket *p;
1150 :
1151 54227 : p = pos ? (*pos) : ht->pInternalPointer;
1152 :
1153 : IS_CONSISTENT(ht);
1154 :
1155 54227 : if (p) {
1156 46115 : *pData = p->pData;
1157 46115 : return SUCCESS;
1158 : } else {
1159 8112 : return FAILURE;
1160 : }
1161 : }
1162 :
1163 : /* This function changes key of currevt element without changing elements'
1164 : * order. If element with target key already exists, it will be deleted first.
1165 : */
1166 : 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)
1167 0 : {
1168 : Bucket *p;
1169 :
1170 0 : p = pos ? (*pos) : ht->pInternalPointer;
1171 :
1172 : IS_CONSISTENT(ht);
1173 :
1174 0 : if (p) {
1175 0 : if (key_type == HASH_KEY_IS_LONG) {
1176 0 : str_length = 0;
1177 0 : if (!p->nKeyLength && p->h == num_index) {
1178 0 : return SUCCESS;
1179 : }
1180 0 : zend_hash_index_del(ht, num_index);
1181 0 : } else if (key_type == HASH_KEY_IS_STRING) {
1182 0 : if (p->nKeyLength == str_length &&
1183 : memcmp(p->arKey, str_index, str_length) == 0) {
1184 0 : return SUCCESS;
1185 : }
1186 0 : zend_hash_del(ht, str_index, str_length);
1187 : } else {
1188 0 : return FAILURE;
1189 : }
1190 :
1191 0 : HANDLE_BLOCK_INTERRUPTIONS();
1192 :
1193 0 : if (p->pNext) {
1194 0 : p->pNext->pLast = p->pLast;
1195 : }
1196 0 : if (p->pLast) {
1197 0 : p->pLast->pNext = p->pNext;
1198 : } else{
1199 0 : ht->arBuckets[p->h & ht->nTableMask] = p->pNext;
1200 : }
1201 :
1202 0 : if (p->nKeyLength != str_length) {
1203 0 : Bucket *q = (Bucket *) pemalloc(sizeof(Bucket) - 1 + str_length, ht->persistent);
1204 :
1205 0 : q->nKeyLength = str_length;
1206 0 : if (p->pData == &p->pDataPtr) {
1207 0 : q->pData = &q->pDataPtr;
1208 : } else {
1209 0 : q->pData = p->pData;
1210 : }
1211 0 : q->pDataPtr = p->pDataPtr;
1212 0 : q->pListNext = p->pListNext;
1213 0 : q->pListLast = p->pListLast;
1214 0 : if (q->pListNext) {
1215 0 : p->pListNext->pListLast = q;
1216 : } else {
1217 0 : ht->pListTail = q;
1218 : }
1219 0 : if (q->pListLast) {
1220 0 : p->pListLast->pListNext = q;
1221 : } else {
1222 0 : ht->pListHead = q;
1223 : }
1224 0 : if (ht->pInternalPointer == p) {
1225 0 : ht->pInternalPointer = q;
1226 : }
1227 0 : if (pos) {
1228 0 : *pos = q;
1229 : }
1230 0 : pefree(p, ht->persistent);
1231 0 : p = q;
1232 : }
1233 :
1234 0 : if (key_type == HASH_KEY_IS_LONG) {
1235 0 : p->h = num_index;
1236 : } else {
1237 0 : memcpy(p->arKey, str_index, str_length);
1238 0 : p->h = zend_inline_hash_func(str_index, str_length);
1239 : }
1240 :
1241 0 : CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[p->h & ht->nTableMask]);
1242 0 : ht->arBuckets[p->h & ht->nTableMask] = p;
1243 0 : HANDLE_UNBLOCK_INTERRUPTIONS();
1244 :
1245 0 : return SUCCESS;
1246 : } else {
1247 0 : return FAILURE;
1248 : }
1249 : }
1250 :
1251 : ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func,
1252 : compare_func_t compar, int renumber TSRMLS_DC)
1253 230 : {
1254 : Bucket **arTmp;
1255 : Bucket *p;
1256 : int i, j;
1257 :
1258 : IS_CONSISTENT(ht);
1259 :
1260 230 : if (!(ht->nNumOfElements>1) && !(renumber && ht->nNumOfElements>0)) { /* Doesn't require sorting */
1261 3 : return SUCCESS;
1262 : }
1263 227 : arTmp = (Bucket **) pemalloc(ht->nNumOfElements * sizeof(Bucket *), ht->persistent);
1264 227 : if (!arTmp) {
1265 0 : return FAILURE;
1266 : }
1267 227 : p = ht->pListHead;
1268 227 : i = 0;
1269 2775 : while (p) {
1270 2321 : arTmp[i] = p;
1271 2321 : p = p->pListNext;
1272 2321 : i++;
1273 : }
1274 :
1275 227 : (*sort_func)((void *) arTmp, i, sizeof(Bucket *), compar TSRMLS_CC);
1276 :
1277 227 : HANDLE_BLOCK_INTERRUPTIONS();
1278 227 : ht->pListHead = arTmp[0];
1279 227 : ht->pListTail = NULL;
1280 227 : ht->pInternalPointer = ht->pListHead;
1281 :
1282 227 : arTmp[0]->pListLast = NULL;
1283 227 : if (i > 1) {
1284 227 : arTmp[0]->pListNext = arTmp[1];
1285 2094 : for (j = 1; j < i-1; j++) {
1286 1867 : arTmp[j]->pListLast = arTmp[j-1];
1287 1867 : arTmp[j]->pListNext = arTmp[j+1];
1288 : }
1289 227 : arTmp[j]->pListLast = arTmp[j-1];
1290 227 : arTmp[j]->pListNext = NULL;
1291 : } else {
1292 0 : arTmp[0]->pListNext = NULL;
1293 : }
1294 227 : ht->pListTail = arTmp[i-1];
1295 :
1296 227 : pefree(arTmp, ht->persistent);
1297 227 : HANDLE_UNBLOCK_INTERRUPTIONS();
1298 :
1299 227 : if (renumber) {
1300 1 : p = ht->pListHead;
1301 1 : i=0;
1302 112 : while (p != NULL) {
1303 110 : p->nKeyLength = 0;
1304 110 : p->h = i++;
1305 110 : p = p->pListNext;
1306 : }
1307 1 : ht->nNextFreeElement = i;
1308 1 : zend_hash_rehash(ht);
1309 : }
1310 227 : return SUCCESS;
1311 : }
1312 :
1313 :
1314 : ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered TSRMLS_DC)
1315 3 : {
1316 3 : Bucket *p1, *p2 = NULL;
1317 : int result;
1318 : void *pData2;
1319 :
1320 : IS_CONSISTENT(ht1);
1321 : IS_CONSISTENT(ht2);
1322 :
1323 3 : HASH_PROTECT_RECURSION(ht1);
1324 3 : HASH_PROTECT_RECURSION(ht2);
1325 :
1326 3 : result = ht1->nNumOfElements - ht2->nNumOfElements;
1327 3 : if (result!=0) {
1328 0 : HASH_UNPROTECT_RECURSION(ht1);
1329 0 : HASH_UNPROTECT_RECURSION(ht2);
1330 0 : return result;
1331 : }
1332 :
1333 3 : p1 = ht1->pListHead;
1334 3 : if (ordered) {
1335 2 : p2 = ht2->pListHead;
1336 : }
1337 :
1338 8 : while (p1) {
1339 4 : if (ordered && !p2) {
1340 0 : HASH_UNPROTECT_RECURSION(ht1);
1341 0 : HASH_UNPROTECT_RECURSION(ht2);
1342 0 : return 1; /* That's not supposed to happen */
1343 : }
1344 4 : if (ordered) {
1345 6 : if (p1->nKeyLength==0 && p2->nKeyLength==0) { /* numeric indices */
1346 3 : result = p1->h - p2->h;
1347 3 : if (result!=0) {
1348 0 : HASH_UNPROTECT_RECURSION(ht1);
1349 0 : HASH_UNPROTECT_RECURSION(ht2);
1350 0 : return result;
1351 : }
1352 : } else { /* string indices */
1353 0 : result = p1->nKeyLength - p2->nKeyLength;
1354 0 : if (result!=0) {
1355 0 : HASH_UNPROTECT_RECURSION(ht1);
1356 0 : HASH_UNPROTECT_RECURSION(ht2);
1357 0 : return result;
1358 : }
1359 0 : result = memcmp(p1->arKey, p2->arKey, p1->nKeyLength);
1360 0 : if (result!=0) {
1361 0 : HASH_UNPROTECT_RECURSION(ht1);
1362 0 : HASH_UNPROTECT_RECURSION(ht2);
1363 0 : return result;
1364 : }
1365 : }
1366 3 : pData2 = p2->pData;
1367 : } else {
1368 1 : if (p1->nKeyLength==0) { /* numeric index */
1369 0 : if (zend_hash_index_find(ht2, p1->h, &pData2)==FAILURE) {
1370 0 : HASH_UNPROTECT_RECURSION(ht1);
1371 0 : HASH_UNPROTECT_RECURSION(ht2);
1372 0 : return 1;
1373 : }
1374 : } else { /* string index */
1375 1 : if (zend_hash_find(ht2, p1->arKey, p1->nKeyLength, &pData2)==FAILURE) {
1376 0 : HASH_UNPROTECT_RECURSION(ht1);
1377 0 : HASH_UNPROTECT_RECURSION(ht2);
1378 0 : return 1;
1379 : }
1380 : }
1381 : }
1382 4 : result = compar(p1->pData, pData2 TSRMLS_CC);
1383 4 : if (result!=0) {
1384 2 : HASH_UNPROTECT_RECURSION(ht1);
1385 2 : HASH_UNPROTECT_RECURSION(ht2);
1386 2 : return result;
1387 : }
1388 2 : p1 = p1->pListNext;
1389 2 : if (ordered) {
1390 2 : p2 = p2->pListNext;
1391 : }
1392 : }
1393 :
1394 1 : HASH_UNPROTECT_RECURSION(ht1);
1395 1 : HASH_UNPROTECT_RECURSION(ht2);
1396 1 : return 0;
1397 : }
1398 :
1399 :
1400 : ZEND_API int zend_hash_minmax(HashTable *ht, compare_func_t compar, int flag, void **pData TSRMLS_DC)
1401 0 : {
1402 : Bucket *p, *res;
1403 :
1404 : IS_CONSISTENT(ht);
1405 :
1406 0 : if (ht->nNumOfElements == 0 ) {
1407 0 : *pData=NULL;
1408 0 : return FAILURE;
1409 : }
1410 :
1411 0 : res = p = ht->pListHead;
1412 0 : while ((p = p->pListNext)) {
1413 0 : if (flag) {
1414 0 : if (compar(&res, &p TSRMLS_CC) < 0) { /* max */
1415 0 : res = p;
1416 : }
1417 : } else {
1418 0 : if (compar(&res, &p TSRMLS_CC) > 0) { /* min */
1419 0 : res = p;
1420 : }
1421 : }
1422 : }
1423 0 : *pData = res->pData;
1424 0 : return SUCCESS;
1425 : }
1426 :
1427 : ZEND_API ulong zend_hash_next_free_element(HashTable *ht)
1428 1781 : {
1429 : IS_CONSISTENT(ht);
1430 :
1431 1781 : return ht->nNextFreeElement;
1432 :
1433 : }
1434 :
1435 :
1436 : #if ZEND_DEBUG
1437 : void zend_hash_display_pListTail(HashTable *ht)
1438 : {
1439 : Bucket *p;
1440 :
1441 : p = ht->pListTail;
1442 : while (p != NULL) {
1443 : zend_output_debug_string(0, "pListTail has key %s\n", p->arKey);
1444 : p = p->pListLast;
1445 : }
1446 : }
1447 :
1448 : void zend_hash_display(HashTable *ht)
1449 : {
1450 : Bucket *p;
1451 : uint i;
1452 :
1453 : for (i = 0; i < ht->nTableSize; i++) {
1454 : p = ht->arBuckets[i];
1455 : while (p != NULL) {
1456 : zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h);
1457 : p = p->pNext;
1458 : }
1459 : }
1460 :
1461 : p = ht->pListTail;
1462 : while (p != NULL) {
1463 : zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h);
1464 : p = p->pListLast;
1465 : }
1466 : }
1467 : #endif
1468 :
1469 : /*
1470 : * Local variables:
1471 : * tab-width: 4
1472 : * c-basic-offset: 4
1473 : * indent-tabs-mode: t
1474 : * End:
1475 : */
|
