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