1/*
2   +----------------------------------------------------------------------+
3   | Zend Engine                                                          |
4   +----------------------------------------------------------------------+
5   | Copyright (c) 1998-2016 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   |          Dmitry Stogov <dmitry@zend.com>                             |
18   +----------------------------------------------------------------------+
19*/
20
21/* $Id$ */
22
23#ifndef ZEND_HASH_H
24#define ZEND_HASH_H
25
26#include "zend.h"
27
28#define HASH_KEY_IS_STRING 1
29#define HASH_KEY_IS_LONG 2
30#define HASH_KEY_NON_EXISTENT 3
31
32#define HASH_UPDATE 			(1<<0)
33#define HASH_ADD				(1<<1)
34#define HASH_UPDATE_INDIRECT	(1<<2)
35#define HASH_ADD_NEW			(1<<3)
36#define HASH_ADD_NEXT			(1<<4)
37
38#define HASH_FLAG_PERSISTENT       (1<<0)
39#define HASH_FLAG_APPLY_PROTECTION (1<<1)
40#define HASH_FLAG_PACKED           (1<<2)
41#define HASH_FLAG_INITIALIZED      (1<<3)
42#define HASH_FLAG_STATIC_KEYS      (1<<4)
43#define HASH_FLAG_HAS_EMPTY_IND    (1<<5)
44
45#define HASH_MASK_CONSISTENCY      0xc0
46
47typedef struct _zend_hash_key {
48	zend_ulong h;
49	zend_string *key;
50} zend_hash_key;
51
52typedef zend_bool (*merge_checker_func_t)(HashTable *target_ht, zval *source_data, zend_hash_key *hash_key, void *pParam);
53
54BEGIN_EXTERN_C()
55
56/* startup/shutdown */
57ZEND_API void ZEND_FASTCALL _zend_hash_init(HashTable *ht, uint32_t nSize, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC);
58ZEND_API void ZEND_FASTCALL _zend_hash_init_ex(HashTable *ht, uint32_t nSize, dtor_func_t pDestructor, zend_bool persistent, zend_bool bApplyProtection ZEND_FILE_LINE_DC);
59ZEND_API void ZEND_FASTCALL zend_hash_destroy(HashTable *ht);
60ZEND_API void ZEND_FASTCALL zend_hash_clean(HashTable *ht);
61#define zend_hash_init(ht, nSize, pHashFunction, pDestructor, persistent)						_zend_hash_init((ht), (nSize), (pDestructor), (persistent) ZEND_FILE_LINE_CC)
62#define zend_hash_init_ex(ht, nSize, pHashFunction, pDestructor, persistent, bApplyProtection)		_zend_hash_init_ex((ht), (nSize), (pDestructor), (persistent), (bApplyProtection) ZEND_FILE_LINE_CC)
63
64ZEND_API void ZEND_FASTCALL zend_hash_real_init(HashTable *ht, zend_bool packed);
65ZEND_API void ZEND_FASTCALL zend_hash_packed_to_hash(HashTable *ht);
66ZEND_API void ZEND_FASTCALL zend_hash_to_packed(HashTable *ht);
67ZEND_API void ZEND_FASTCALL zend_hash_extend(HashTable *ht, uint32_t nSize, zend_bool packed);
68
69/* additions/updates/changes */
70ZEND_API zval* ZEND_FASTCALL _zend_hash_add_or_update(HashTable *ht, zend_string *key, zval *pData, uint32_t flag ZEND_FILE_LINE_DC);
71ZEND_API zval* ZEND_FASTCALL _zend_hash_update(HashTable *ht, zend_string *key,zval *pData ZEND_FILE_LINE_DC);
72ZEND_API zval* ZEND_FASTCALL _zend_hash_update_ind(HashTable *ht, zend_string *key,zval *pData ZEND_FILE_LINE_DC);
73ZEND_API zval* ZEND_FASTCALL _zend_hash_add(HashTable *ht, zend_string *key,zval *pData ZEND_FILE_LINE_DC);
74ZEND_API zval* ZEND_FASTCALL _zend_hash_add_new(HashTable *ht, zend_string *key,zval *pData ZEND_FILE_LINE_DC);
75
76#define zend_hash_update(ht, key, pData) \
77		_zend_hash_update(ht, key, pData ZEND_FILE_LINE_CC)
78#define zend_hash_update_ind(ht, key, pData) \
79		_zend_hash_update_ind(ht, key, pData ZEND_FILE_LINE_CC)
80#define zend_hash_add(ht, key, pData) \
81		_zend_hash_add(ht, key, pData ZEND_FILE_LINE_CC)
82#define zend_hash_add_new(ht, key, pData) \
83		_zend_hash_add_new(ht, key, pData ZEND_FILE_LINE_CC)
84
85ZEND_API zval* ZEND_FASTCALL _zend_hash_str_add_or_update(HashTable *ht, const char *key, size_t len, zval *pData, uint32_t flag ZEND_FILE_LINE_DC);
86ZEND_API zval* ZEND_FASTCALL _zend_hash_str_update(HashTable *ht, const char *key, size_t len, zval *pData ZEND_FILE_LINE_DC);
87ZEND_API zval* ZEND_FASTCALL _zend_hash_str_update_ind(HashTable *ht, const char *key, size_t len, zval *pData ZEND_FILE_LINE_DC);
88ZEND_API zval* ZEND_FASTCALL _zend_hash_str_add(HashTable *ht, const char *key, size_t len, zval *pData ZEND_FILE_LINE_DC);
89ZEND_API zval* ZEND_FASTCALL _zend_hash_str_add_new(HashTable *ht, const char *key, size_t len, zval *pData ZEND_FILE_LINE_DC);
90
91#define zend_hash_str_update(ht, key, len, pData) \
92		_zend_hash_str_update(ht, key, len, pData ZEND_FILE_LINE_CC)
93#define zend_hash_str_update_ind(ht, key, len, pData) \
94		_zend_hash_str_update_ind(ht, key, len, pData ZEND_FILE_LINE_CC)
95#define zend_hash_str_add(ht, key, len, pData) \
96		_zend_hash_str_add(ht, key, len, pData ZEND_FILE_LINE_CC)
97#define zend_hash_str_add_new(ht, key, len, pData) \
98		_zend_hash_str_add_new(ht, key, len, pData ZEND_FILE_LINE_CC)
99
100ZEND_API zval* ZEND_FASTCALL _zend_hash_index_add_or_update(HashTable *ht, zend_ulong h, zval *pData, uint32_t flag ZEND_FILE_LINE_DC);
101ZEND_API zval* ZEND_FASTCALL _zend_hash_index_add(HashTable *ht, zend_ulong h, zval *pData ZEND_FILE_LINE_DC);
102ZEND_API zval* ZEND_FASTCALL _zend_hash_index_add_new(HashTable *ht, zend_ulong h, zval *pData ZEND_FILE_LINE_DC);
103ZEND_API zval* ZEND_FASTCALL _zend_hash_index_update(HashTable *ht, zend_ulong h, zval *pData ZEND_FILE_LINE_DC);
104ZEND_API zval* ZEND_FASTCALL _zend_hash_next_index_insert(HashTable *ht, zval *pData ZEND_FILE_LINE_DC);
105ZEND_API zval* ZEND_FASTCALL _zend_hash_next_index_insert_new(HashTable *ht, zval *pData ZEND_FILE_LINE_DC);
106
107#define zend_hash_index_add(ht, h, pData) \
108		_zend_hash_index_add(ht, h, pData ZEND_FILE_LINE_CC)
109#define zend_hash_index_add_new(ht, h, pData) \
110		_zend_hash_index_add_new(ht, h, pData ZEND_FILE_LINE_CC)
111#define zend_hash_index_update(ht, h, pData) \
112		_zend_hash_index_update(ht, h, pData ZEND_FILE_LINE_CC)
113#define zend_hash_next_index_insert(ht, pData) \
114		_zend_hash_next_index_insert(ht, pData ZEND_FILE_LINE_CC)
115#define zend_hash_next_index_insert_new(ht, pData) \
116		_zend_hash_next_index_insert_new(ht, pData ZEND_FILE_LINE_CC)
117
118ZEND_API zval* ZEND_FASTCALL zend_hash_index_add_empty_element(HashTable *ht, zend_ulong h);
119ZEND_API zval* ZEND_FASTCALL zend_hash_add_empty_element(HashTable *ht, zend_string *key);
120ZEND_API zval* ZEND_FASTCALL zend_hash_str_add_empty_element(HashTable *ht, const char *key, size_t len);
121
122#define ZEND_HASH_APPLY_KEEP				0
123#define ZEND_HASH_APPLY_REMOVE				1<<0
124#define ZEND_HASH_APPLY_STOP				1<<1
125
126typedef int (*apply_func_t)(zval *pDest);
127typedef int (*apply_func_arg_t)(zval *pDest, void *argument);
128typedef int (*apply_func_args_t)(zval *pDest, int num_args, va_list args, zend_hash_key *hash_key);
129
130ZEND_API void ZEND_FASTCALL zend_hash_graceful_destroy(HashTable *ht);
131ZEND_API void ZEND_FASTCALL zend_hash_graceful_reverse_destroy(HashTable *ht);
132ZEND_API void ZEND_FASTCALL zend_hash_apply(HashTable *ht, apply_func_t apply_func);
133ZEND_API void ZEND_FASTCALL zend_hash_apply_with_argument(HashTable *ht, apply_func_arg_t apply_func, void *);
134ZEND_API void ZEND_FASTCALL zend_hash_apply_with_arguments(HashTable *ht, apply_func_args_t apply_func, int, ...);
135
136/* This function should be used with special care (in other words,
137 * it should usually not be used).  When used with the ZEND_HASH_APPLY_STOP
138 * return value, it assumes things about the order of the elements in the hash.
139 * Also, it does not provide the same kind of reentrancy protection that
140 * the standard apply functions do.
141 */
142ZEND_API void ZEND_FASTCALL zend_hash_reverse_apply(HashTable *ht, apply_func_t apply_func);
143
144
145/* Deletes */
146ZEND_API int ZEND_FASTCALL zend_hash_del(HashTable *ht, zend_string *key);
147ZEND_API int ZEND_FASTCALL zend_hash_del_ind(HashTable *ht, zend_string *key);
148ZEND_API int ZEND_FASTCALL zend_hash_str_del(HashTable *ht, const char *key, size_t len);
149ZEND_API int ZEND_FASTCALL zend_hash_str_del_ind(HashTable *ht, const char *key, size_t len);
150ZEND_API int ZEND_FASTCALL zend_hash_index_del(HashTable *ht, zend_ulong h);
151ZEND_API void ZEND_FASTCALL zend_hash_del_bucket(HashTable *ht, Bucket *p);
152
153/* Data retreival */
154ZEND_API zval* ZEND_FASTCALL zend_hash_find(const HashTable *ht, zend_string *key);
155ZEND_API zval* ZEND_FASTCALL zend_hash_str_find(const HashTable *ht, const char *key, size_t len);
156ZEND_API zval* ZEND_FASTCALL zend_hash_index_find(const HashTable *ht, zend_ulong h);
157
158/* Misc */
159ZEND_API zend_bool ZEND_FASTCALL zend_hash_exists(const HashTable *ht, zend_string *key);
160ZEND_API zend_bool ZEND_FASTCALL zend_hash_str_exists(const HashTable *ht, const char *str, size_t len);
161ZEND_API zend_bool ZEND_FASTCALL zend_hash_index_exists(const HashTable *ht, zend_ulong h);
162
163/* traversing */
164#define zend_hash_has_more_elements_ex(ht, pos) \
165	(zend_hash_get_current_key_type_ex(ht, pos) == HASH_KEY_NON_EXISTENT ? FAILURE : SUCCESS)
166ZEND_API int   ZEND_FASTCALL zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos);
167ZEND_API int   ZEND_FASTCALL zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos);
168ZEND_API int   ZEND_FASTCALL zend_hash_get_current_key_ex(const HashTable *ht, zend_string **str_index, zend_ulong *num_index, HashPosition *pos);
169ZEND_API void  ZEND_FASTCALL zend_hash_get_current_key_zval_ex(const HashTable *ht, zval *key, HashPosition *pos);
170ZEND_API int   ZEND_FASTCALL zend_hash_get_current_key_type_ex(HashTable *ht, HashPosition *pos);
171ZEND_API zval* ZEND_FASTCALL zend_hash_get_current_data_ex(HashTable *ht, HashPosition *pos);
172ZEND_API void  ZEND_FASTCALL zend_hash_internal_pointer_reset_ex(HashTable *ht, HashPosition *pos);
173ZEND_API void  ZEND_FASTCALL zend_hash_internal_pointer_end_ex(HashTable *ht, HashPosition *pos);
174
175#define zend_hash_has_more_elements(ht) \
176	zend_hash_has_more_elements_ex(ht, &(ht)->nInternalPointer)
177#define zend_hash_move_forward(ht) \
178	zend_hash_move_forward_ex(ht, &(ht)->nInternalPointer)
179#define zend_hash_move_backwards(ht) \
180	zend_hash_move_backwards_ex(ht, &(ht)->nInternalPointer)
181#define zend_hash_get_current_key(ht, str_index, num_index) \
182	zend_hash_get_current_key_ex(ht, str_index, num_index, &(ht)->nInternalPointer)
183#define zend_hash_get_current_key_zval(ht, key) \
184	zend_hash_get_current_key_zval_ex(ht, key, &(ht)->nInternalPointer)
185#define zend_hash_get_current_key_type(ht) \
186	zend_hash_get_current_key_type_ex(ht, &(ht)->nInternalPointer)
187#define zend_hash_get_current_data(ht) \
188	zend_hash_get_current_data_ex(ht, &(ht)->nInternalPointer)
189#define zend_hash_internal_pointer_reset(ht) \
190	zend_hash_internal_pointer_reset_ex(ht, &(ht)->nInternalPointer)
191#define zend_hash_internal_pointer_end(ht) \
192	zend_hash_internal_pointer_end_ex(ht, &(ht)->nInternalPointer)
193
194/* Copying, merging and sorting */
195ZEND_API void  ZEND_FASTCALL zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor);
196ZEND_API void  ZEND_FASTCALL _zend_hash_merge(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, zend_bool overwrite ZEND_FILE_LINE_DC);
197ZEND_API void  ZEND_FASTCALL zend_hash_merge_ex(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, merge_checker_func_t pMergeSource, void *pParam);
198ZEND_API void  zend_hash_bucket_swap(Bucket *p, Bucket *q);
199ZEND_API void  zend_hash_bucket_renum_swap(Bucket *p, Bucket *q);
200ZEND_API void  zend_hash_bucket_packed_swap(Bucket *p, Bucket *q);
201ZEND_API int   zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered);
202ZEND_API int   ZEND_FASTCALL zend_hash_sort_ex(HashTable *ht, sort_func_t sort_func, compare_func_t compare_func, zend_bool renumber);
203ZEND_API zval* ZEND_FASTCALL zend_hash_minmax(const HashTable *ht, compare_func_t compar, uint32_t flag);
204
205#define zend_hash_merge(target, source, pCopyConstructor, overwrite)					\
206	_zend_hash_merge(target, source, pCopyConstructor, overwrite ZEND_FILE_LINE_CC)
207
208#define zend_hash_sort(ht, compare_func, renumber) \
209	zend_hash_sort_ex(ht, zend_sort, compare_func, renumber)
210
211#define zend_hash_num_elements(ht) \
212	(ht)->nNumOfElements
213
214#define zend_hash_next_free_element(ht) \
215	(ht)->nNextFreeElement
216
217ZEND_API int ZEND_FASTCALL zend_hash_rehash(HashTable *ht);
218
219ZEND_API uint32_t zend_array_count(HashTable *ht);
220ZEND_API HashTable* ZEND_FASTCALL zend_array_dup(HashTable *source);
221ZEND_API void ZEND_FASTCALL zend_array_destroy(HashTable *ht);
222ZEND_API void ZEND_FASTCALL zend_symtable_clean(HashTable *ht);
223
224ZEND_API int ZEND_FASTCALL _zend_handle_numeric_str_ex(const char *key, size_t length, zend_ulong *idx);
225
226ZEND_API uint32_t     ZEND_FASTCALL zend_hash_iterator_add(HashTable *ht, HashPosition pos);
227ZEND_API HashPosition ZEND_FASTCALL zend_hash_iterator_pos(uint32_t idx, HashTable *ht);
228ZEND_API HashPosition ZEND_FASTCALL zend_hash_iterator_pos_ex(uint32_t idx, zval *array);
229ZEND_API void         ZEND_FASTCALL zend_hash_iterator_del(uint32_t idx);
230ZEND_API HashPosition ZEND_FASTCALL zend_hash_iterators_lower_pos(HashTable *ht, HashPosition start);
231ZEND_API void         ZEND_FASTCALL _zend_hash_iterators_update(HashTable *ht, HashPosition from, HashPosition to);
232
233static zend_always_inline void zend_hash_iterators_update(HashTable *ht, HashPosition from, HashPosition to)
234{
235	if (UNEXPECTED(ht->u.v.nIteratorsCount)) {
236		_zend_hash_iterators_update(ht, from, to);
237	}
238}
239
240
241END_EXTERN_C()
242
243#define ZEND_INIT_SYMTABLE(ht)								\
244	ZEND_INIT_SYMTABLE_EX(ht, 8, 0)
245
246#define ZEND_INIT_SYMTABLE_EX(ht, n, persistent)			\
247	zend_hash_init(ht, n, NULL, ZVAL_PTR_DTOR, persistent)
248
249static zend_always_inline int _zend_handle_numeric_str(const char *key, size_t length, zend_ulong *idx)
250{
251	const char *tmp = key;
252
253	if (*tmp > '9') {
254		return 0;
255	} else if (*tmp < '0') {
256		if (*tmp != '-') {
257			return 0;
258		}
259		tmp++;
260		if (*tmp > '9' || *tmp < '0') {
261			return 0;
262		}
263	}
264	return _zend_handle_numeric_str_ex(key, length, idx);
265}
266
267#define ZEND_HANDLE_NUMERIC_STR(key, length, idx) \
268	_zend_handle_numeric_str(key, length, &idx)
269
270#define ZEND_HANDLE_NUMERIC(key, idx) \
271	ZEND_HANDLE_NUMERIC_STR(ZSTR_VAL(key), ZSTR_LEN(key), idx)
272
273
274static zend_always_inline zval *zend_hash_find_ind(const HashTable *ht, zend_string *key)
275{
276	zval *zv;
277
278	zv = zend_hash_find(ht, key);
279	return (zv && Z_TYPE_P(zv) == IS_INDIRECT) ?
280		((Z_TYPE_P(Z_INDIRECT_P(zv)) != IS_UNDEF) ? Z_INDIRECT_P(zv) : NULL) : zv;
281}
282
283
284static zend_always_inline int zend_hash_exists_ind(const HashTable *ht, zend_string *key)
285{
286	zval *zv;
287
288	zv = zend_hash_find(ht, key);
289	return zv && (Z_TYPE_P(zv) != IS_INDIRECT ||
290			Z_TYPE_P(Z_INDIRECT_P(zv)) != IS_UNDEF);
291}
292
293
294static zend_always_inline zval *zend_hash_str_find_ind(const HashTable *ht, const char *str, size_t len)
295{
296	zval *zv;
297
298	zv = zend_hash_str_find(ht, str, len);
299	return (zv && Z_TYPE_P(zv) == IS_INDIRECT) ?
300		((Z_TYPE_P(Z_INDIRECT_P(zv)) != IS_UNDEF) ? Z_INDIRECT_P(zv) : NULL) : zv;
301}
302
303
304static zend_always_inline zval *zend_symtable_update(HashTable *ht, zend_string *key, zval *pData)
305{
306	zend_ulong idx;
307
308	if (ZEND_HANDLE_NUMERIC(key, idx)) {
309		return zend_hash_index_update(ht, idx, pData);
310	} else {
311		return zend_hash_update(ht, key, pData);
312	}
313}
314
315
316static zend_always_inline zval *zend_symtable_update_ind(HashTable *ht, zend_string *key, zval *pData)
317{
318	zend_ulong idx;
319
320	if (ZEND_HANDLE_NUMERIC(key, idx)) {
321		return zend_hash_index_update(ht, idx, pData);
322	} else {
323		return zend_hash_update_ind(ht, key, pData);
324	}
325}
326
327
328static zend_always_inline int zend_symtable_del(HashTable *ht, zend_string *key)
329{
330	zend_ulong idx;
331
332	if (ZEND_HANDLE_NUMERIC(key, idx)) {
333		return zend_hash_index_del(ht, idx);
334	} else {
335		return zend_hash_del(ht, key);
336	}
337}
338
339
340static zend_always_inline int zend_symtable_del_ind(HashTable *ht, zend_string *key)
341{
342	zend_ulong idx;
343
344	if (ZEND_HANDLE_NUMERIC(key, idx)) {
345		return zend_hash_index_del(ht, idx);
346	} else {
347		return zend_hash_del_ind(ht, key);
348	}
349}
350
351
352static zend_always_inline zval *zend_symtable_find(const HashTable *ht, zend_string *key)
353{
354	zend_ulong idx;
355
356	if (ZEND_HANDLE_NUMERIC(key, idx)) {
357		return zend_hash_index_find(ht, idx);
358	} else {
359		return zend_hash_find(ht, key);
360	}
361}
362
363
364static zend_always_inline zval *zend_symtable_find_ind(const HashTable *ht, zend_string *key)
365{
366	zend_ulong idx;
367
368	if (ZEND_HANDLE_NUMERIC(key, idx)) {
369		return zend_hash_index_find(ht, idx);
370	} else {
371		return zend_hash_find_ind(ht, key);
372	}
373}
374
375
376static zend_always_inline int zend_symtable_exists(HashTable *ht, zend_string *key)
377{
378	zend_ulong idx;
379
380	if (ZEND_HANDLE_NUMERIC(key, idx)) {
381		return zend_hash_index_exists(ht, idx);
382	} else {
383		return zend_hash_exists(ht, key);
384	}
385}
386
387
388static zend_always_inline zval *zend_symtable_str_update(HashTable *ht, const char *str, size_t len, zval *pData)
389{
390	zend_ulong idx;
391
392	if (ZEND_HANDLE_NUMERIC_STR(str, len, idx)) {
393		return zend_hash_index_update(ht, idx, pData);
394	} else {
395		return zend_hash_str_update(ht, str, len, pData);
396	}
397}
398
399
400static zend_always_inline zval *zend_symtable_str_update_ind(HashTable *ht, const char *str, size_t len, zval *pData)
401{
402	zend_ulong idx;
403
404	if (ZEND_HANDLE_NUMERIC_STR(str, len, idx)) {
405		return zend_hash_index_update(ht, idx, pData);
406	} else {
407		return zend_hash_str_update_ind(ht, str, len, pData);
408	}
409}
410
411
412static zend_always_inline int zend_symtable_str_del(HashTable *ht, const char *str, size_t len)
413{
414	zend_ulong idx;
415
416	if (ZEND_HANDLE_NUMERIC_STR(str, len, idx)) {
417		return zend_hash_index_del(ht, idx);
418	} else {
419		return zend_hash_str_del(ht, str, len);
420	}
421}
422
423
424static zend_always_inline int zend_symtable_str_del_ind(HashTable *ht, const char *str, size_t len)
425{
426	zend_ulong idx;
427
428	if (ZEND_HANDLE_NUMERIC_STR(str, len, idx)) {
429		return zend_hash_index_del(ht, idx);
430	} else {
431		return zend_hash_str_del_ind(ht, str, len);
432	}
433}
434
435
436static zend_always_inline zval *zend_symtable_str_find(HashTable *ht, const char *str, size_t len)
437{
438	zend_ulong idx;
439
440	if (ZEND_HANDLE_NUMERIC_STR(str, len, idx)) {
441		return zend_hash_index_find(ht, idx);
442	} else {
443		return zend_hash_str_find(ht, str, len);
444	}
445}
446
447
448static zend_always_inline int zend_symtable_str_exists(HashTable *ht, const char *str, size_t len)
449{
450	zend_ulong idx;
451
452	if (ZEND_HANDLE_NUMERIC_STR(str, len, idx)) {
453		return zend_hash_index_exists(ht, idx);
454	} else {
455		return zend_hash_str_exists(ht, str, len);
456	}
457}
458
459static zend_always_inline void *zend_hash_add_ptr(HashTable *ht, zend_string *key, void *pData)
460{
461	zval tmp, *zv;
462
463	ZVAL_PTR(&tmp, pData);
464	zv = zend_hash_add(ht, key, &tmp);
465	if (zv) {
466		ZEND_ASSUME(Z_PTR_P(zv));
467		return Z_PTR_P(zv);
468	} else {
469		return NULL;
470	}
471}
472
473static zend_always_inline void *zend_hash_add_new_ptr(HashTable *ht, zend_string *key, void *pData)
474{
475	zval tmp, *zv;
476
477	ZVAL_PTR(&tmp, pData);
478	zv = zend_hash_add_new(ht, key, &tmp);
479	if (zv) {
480		ZEND_ASSUME(Z_PTR_P(zv));
481		return Z_PTR_P(zv);
482	} else {
483		return NULL;
484	}
485}
486
487static zend_always_inline void *zend_hash_str_add_ptr(HashTable *ht, const char *str, size_t len, void *pData)
488{
489	zval tmp, *zv;
490
491	ZVAL_PTR(&tmp, pData);
492	zv = zend_hash_str_add(ht, str, len, &tmp);
493	if (zv) {
494		ZEND_ASSUME(Z_PTR_P(zv));
495		return Z_PTR_P(zv);
496	} else {
497		return NULL;
498	}
499}
500
501static zend_always_inline void *zend_hash_str_add_new_ptr(HashTable *ht, const char *str, size_t len, void *pData)
502{
503	zval tmp, *zv;
504
505	ZVAL_PTR(&tmp, pData);
506	zv = zend_hash_str_add_new(ht, str, len, &tmp);
507	if (zv) {
508		ZEND_ASSUME(Z_PTR_P(zv));
509		return Z_PTR_P(zv);
510	} else {
511		return NULL;
512	}
513}
514
515static zend_always_inline void *zend_hash_update_ptr(HashTable *ht, zend_string *key, void *pData)
516{
517	zval tmp, *zv;
518
519	ZVAL_PTR(&tmp, pData);
520	zv = zend_hash_update(ht, key, &tmp);
521	if (zv) {
522		ZEND_ASSUME(Z_PTR_P(zv));
523		return Z_PTR_P(zv);
524	} else {
525		return NULL;
526	}
527}
528
529static zend_always_inline void *zend_hash_str_update_ptr(HashTable *ht, const char *str, size_t len, void *pData)
530{
531	zval tmp, *zv;
532
533	ZVAL_PTR(&tmp, pData);
534	zv = zend_hash_str_update(ht, str, len, &tmp);
535	if (zv) {
536		ZEND_ASSUME(Z_PTR_P(zv));
537		return Z_PTR_P(zv);
538	} else {
539		return NULL;
540	}
541}
542
543static zend_always_inline void *zend_hash_add_mem(HashTable *ht, zend_string *key, void *pData, size_t size)
544{
545	zval tmp, *zv;
546
547	ZVAL_PTR(&tmp, NULL);
548	if ((zv = zend_hash_add(ht, key, &tmp))) {
549		Z_PTR_P(zv) = pemalloc(size, ht->u.flags & HASH_FLAG_PERSISTENT);
550		memcpy(Z_PTR_P(zv), pData, size);
551		return Z_PTR_P(zv);
552	}
553	return NULL;
554}
555
556static zend_always_inline void *zend_hash_str_add_mem(HashTable *ht, const char *str, size_t len, void *pData, size_t size)
557{
558	zval tmp, *zv;
559
560	ZVAL_PTR(&tmp, NULL);
561	if ((zv = zend_hash_str_add(ht, str, len, &tmp))) {
562		Z_PTR_P(zv) = pemalloc(size, ht->u.flags & HASH_FLAG_PERSISTENT);
563		memcpy(Z_PTR_P(zv), pData, size);
564		return Z_PTR_P(zv);
565	}
566	return NULL;
567}
568
569static zend_always_inline void *zend_hash_update_mem(HashTable *ht, zend_string *key, void *pData, size_t size)
570{
571	void *p;
572
573	p = pemalloc(size, ht->u.flags & HASH_FLAG_PERSISTENT);
574	memcpy(p, pData, size);
575	return zend_hash_update_ptr(ht, key, p);
576}
577
578static zend_always_inline void *zend_hash_str_update_mem(HashTable *ht, const char *str, size_t len, void *pData, size_t size)
579{
580	void *p;
581
582	p = pemalloc(size, ht->u.flags & HASH_FLAG_PERSISTENT);
583	memcpy(p, pData, size);
584	return zend_hash_str_update_ptr(ht, str, len, p);
585}
586
587static zend_always_inline void *zend_hash_index_add_ptr(HashTable *ht, zend_ulong h, void *pData)
588{
589	zval tmp, *zv;
590
591	ZVAL_PTR(&tmp, pData);
592	zv = zend_hash_index_add(ht, h, &tmp);
593	return zv ? Z_PTR_P(zv) : NULL;
594}
595
596static zend_always_inline void *zend_hash_index_add_new_ptr(HashTable *ht, zend_ulong h, void *pData)
597{
598	zval tmp, *zv;
599
600	ZVAL_PTR(&tmp, pData);
601	zv = zend_hash_index_add_new(ht, h, &tmp);
602	return zv ? Z_PTR_P(zv) : NULL;
603}
604
605static zend_always_inline void *zend_hash_index_update_ptr(HashTable *ht, zend_ulong h, void *pData)
606{
607	zval tmp, *zv;
608
609	ZVAL_PTR(&tmp, pData);
610	zv = zend_hash_index_update(ht, h, &tmp);
611	if (zv) {
612		ZEND_ASSUME(Z_PTR_P(zv));
613		return Z_PTR_P(zv);
614	} else {
615		return NULL;
616	}
617}
618
619static zend_always_inline void *zend_hash_index_add_mem(HashTable *ht, zend_ulong h, void *pData, size_t size)
620{
621	zval tmp, *zv;
622
623	ZVAL_PTR(&tmp, NULL);
624	if ((zv = zend_hash_index_add(ht, h, &tmp))) {
625		Z_PTR_P(zv) = pemalloc(size, ht->u.flags & HASH_FLAG_PERSISTENT);
626		memcpy(Z_PTR_P(zv), pData, size);
627		return Z_PTR_P(zv);
628	}
629	return NULL;
630}
631
632static zend_always_inline void *zend_hash_next_index_insert_ptr(HashTable *ht, void *pData)
633{
634	zval tmp, *zv;
635
636	ZVAL_PTR(&tmp, pData);
637	zv = zend_hash_next_index_insert(ht, &tmp);
638	if (zv) {
639		ZEND_ASSUME(Z_PTR_P(zv));
640		return Z_PTR_P(zv);
641	} else {
642		return NULL;
643	}
644}
645
646static zend_always_inline void *zend_hash_index_update_mem(HashTable *ht, zend_ulong h, void *pData, size_t size)
647{
648	void *p;
649
650	p = pemalloc(size, ht->u.flags & HASH_FLAG_PERSISTENT);
651	memcpy(p, pData, size);
652	return zend_hash_index_update_ptr(ht, h, p);
653}
654
655static zend_always_inline void *zend_hash_next_index_insert_mem(HashTable *ht, void *pData, size_t size)
656{
657	zval tmp, *zv;
658
659	ZVAL_PTR(&tmp, NULL);
660	if ((zv = zend_hash_next_index_insert(ht, &tmp))) {
661		Z_PTR_P(zv) = pemalloc(size, ht->u.flags & HASH_FLAG_PERSISTENT);
662		memcpy(Z_PTR_P(zv), pData, size);
663		return Z_PTR_P(zv);
664	}
665	return NULL;
666}
667
668static zend_always_inline void *zend_hash_find_ptr(const HashTable *ht, zend_string *key)
669{
670	zval *zv;
671
672	zv = zend_hash_find(ht, key);
673	if (zv) {
674		ZEND_ASSUME(Z_PTR_P(zv));
675		return Z_PTR_P(zv);
676	} else {
677		return NULL;
678	}
679}
680
681static zend_always_inline void *zend_hash_str_find_ptr(const HashTable *ht, const char *str, size_t len)
682{
683	zval *zv;
684
685	zv = zend_hash_str_find(ht, str, len);
686	if (zv) {
687		ZEND_ASSUME(Z_PTR_P(zv));
688		return Z_PTR_P(zv);
689	} else {
690		return NULL;
691	}
692}
693
694static zend_always_inline void *zend_hash_index_find_ptr(const HashTable *ht, zend_ulong h)
695{
696	zval *zv;
697
698	zv = zend_hash_index_find(ht, h);
699	if (zv) {
700		ZEND_ASSUME(Z_PTR_P(zv));
701		return Z_PTR_P(zv);
702	} else {
703		return NULL;
704	}
705}
706
707static zend_always_inline void *zend_symtable_str_find_ptr(HashTable *ht, const char *str, size_t len)
708{
709	zend_ulong idx;
710
711	if (ZEND_HANDLE_NUMERIC_STR(str, len, idx)) {
712		return zend_hash_index_find_ptr(ht, idx);
713	} else {
714		return zend_hash_str_find_ptr(ht, str, len);
715	}
716}
717
718static zend_always_inline void *zend_hash_get_current_data_ptr_ex(HashTable *ht, HashPosition *pos)
719{
720	zval *zv;
721
722	zv = zend_hash_get_current_data_ex(ht, pos);
723	if (zv) {
724		ZEND_ASSUME(Z_PTR_P(zv));
725		return Z_PTR_P(zv);
726	} else {
727		return NULL;
728	}
729}
730
731#define zend_hash_get_current_data_ptr(ht) \
732	zend_hash_get_current_data_ptr_ex(ht, &(ht)->nInternalPointer)
733
734#define ZEND_HASH_FOREACH(_ht, indirect) do { \
735		Bucket *_p = (_ht)->arData; \
736		Bucket *_end = _p + (_ht)->nNumUsed; \
737		for (; _p != _end; _p++) { \
738			zval *_z = &_p->val; \
739			if (indirect && Z_TYPE_P(_z) == IS_INDIRECT) { \
740				_z = Z_INDIRECT_P(_z); \
741			} \
742			if (UNEXPECTED(Z_TYPE_P(_z) == IS_UNDEF)) continue;
743
744#define ZEND_HASH_REVERSE_FOREACH(_ht, indirect) do { \
745		uint _idx; \
746		for (_idx = (_ht)->nNumUsed; _idx > 0; _idx--) { \
747			Bucket *_p = (_ht)->arData + _idx - 1; \
748			zval *_z = &_p->val; \
749			if (indirect && Z_TYPE_P(_z) == IS_INDIRECT) { \
750				_z = Z_INDIRECT_P(_z); \
751			} \
752			if (UNEXPECTED(Z_TYPE_P(_z) == IS_UNDEF)) continue;
753
754#define ZEND_HASH_FOREACH_END() \
755		} \
756	} while (0)
757
758#define ZEND_HASH_FOREACH_BUCKET(ht, _bucket) \
759	ZEND_HASH_FOREACH(ht, 0); \
760	_bucket = _p;
761
762#define ZEND_HASH_FOREACH_VAL(ht, _val) \
763	ZEND_HASH_FOREACH(ht, 0); \
764	_val = _z;
765
766#define ZEND_HASH_FOREACH_VAL_IND(ht, _val) \
767	ZEND_HASH_FOREACH(ht, 1); \
768	_val = _z;
769
770#define ZEND_HASH_FOREACH_PTR(ht, _ptr) \
771	ZEND_HASH_FOREACH(ht, 0); \
772	_ptr = Z_PTR_P(_z);
773
774#define ZEND_HASH_FOREACH_NUM_KEY(ht, _h) \
775	ZEND_HASH_FOREACH(ht, 0); \
776	_h = _p->h;
777
778#define ZEND_HASH_FOREACH_STR_KEY(ht, _key) \
779	ZEND_HASH_FOREACH(ht, 0); \
780	_key = _p->key;
781
782#define ZEND_HASH_FOREACH_KEY(ht, _h, _key) \
783	ZEND_HASH_FOREACH(ht, 0); \
784	_h = _p->h; \
785	_key = _p->key;
786
787#define ZEND_HASH_FOREACH_NUM_KEY_VAL(ht, _h, _val) \
788	ZEND_HASH_FOREACH(ht, 0); \
789	_h = _p->h; \
790	_val = _z;
791
792#define ZEND_HASH_FOREACH_STR_KEY_VAL(ht, _key, _val) \
793	ZEND_HASH_FOREACH(ht, 0); \
794	_key = _p->key; \
795	_val = _z;
796
797#define ZEND_HASH_FOREACH_KEY_VAL(ht, _h, _key, _val) \
798	ZEND_HASH_FOREACH(ht, 0); \
799	_h = _p->h; \
800	_key = _p->key; \
801	_val = _z;
802
803#define ZEND_HASH_FOREACH_STR_KEY_VAL_IND(ht, _key, _val) \
804	ZEND_HASH_FOREACH(ht, 1); \
805	_key = _p->key; \
806	_val = _z;
807
808#define ZEND_HASH_FOREACH_KEY_VAL_IND(ht, _h, _key, _val) \
809	ZEND_HASH_FOREACH(ht, 1); \
810	_h = _p->h; \
811	_key = _p->key; \
812	_val = _z;
813
814#define ZEND_HASH_FOREACH_NUM_KEY_PTR(ht, _h, _ptr) \
815	ZEND_HASH_FOREACH(ht, 0); \
816	_h = _p->h; \
817	_ptr = Z_PTR_P(_z);
818
819#define ZEND_HASH_FOREACH_STR_KEY_PTR(ht, _key, _ptr) \
820	ZEND_HASH_FOREACH(ht, 0); \
821	_key = _p->key; \
822	_ptr = Z_PTR_P(_z);
823
824#define ZEND_HASH_FOREACH_KEY_PTR(ht, _h, _key, _ptr) \
825	ZEND_HASH_FOREACH(ht, 0); \
826	_h = _p->h; \
827	_key = _p->key; \
828	_ptr = Z_PTR_P(_z);
829
830#define ZEND_HASH_REVERSE_FOREACH_BUCKET(ht, _bucket) \
831	ZEND_HASH_REVERSE_FOREACH(ht, 0); \
832	_bucket = _p;
833
834#define ZEND_HASH_REVERSE_FOREACH_VAL(ht, _val) \
835	ZEND_HASH_REVERSE_FOREACH(ht, 0); \
836	_val = _z;
837
838#define ZEND_HASH_REVERSE_FOREACH_PTR(ht, _ptr) \
839	ZEND_HASH_REVERSE_FOREACH(ht, 0); \
840	_ptr = Z_PTR_P(_z);
841
842#define ZEND_HASH_REVERSE_FOREACH_VAL_IND(ht, _val) \
843	ZEND_HASH_REVERSE_FOREACH(ht, 1); \
844	_val = _z;
845
846#define ZEND_HASH_REVERSE_FOREACH_KEY_VAL(ht, _h, _key, _val) \
847	ZEND_HASH_REVERSE_FOREACH(ht, 0); \
848	_h = _p->h; \
849	_key = _p->key; \
850	_val = _z;
851
852#define ZEND_HASH_REVERSE_FOREACH_KEY_VAL_IND(ht, _h, _key, _val) \
853	ZEND_HASH_REVERSE_FOREACH(ht, 1); \
854	_h = _p->h; \
855	_key = _p->key; \
856	_val = _z;
857
858#define ZEND_HASH_APPLY_PROTECTION(ht) \
859	((ht)->u.flags & HASH_FLAG_APPLY_PROTECTION)
860
861#define ZEND_HASH_APPLY_SHIFT         8
862#define ZEND_HASH_APPLY_COUNT_MASK    0xff00
863#define ZEND_HASH_GET_APPLY_COUNT(ht) (((ht)->u.flags & ZEND_HASH_APPLY_COUNT_MASK) >> ZEND_HASH_APPLY_SHIFT)
864#define ZEND_HASH_INC_APPLY_COUNT(ht) ((ht)->u.flags += (1 << ZEND_HASH_APPLY_SHIFT))
865#define ZEND_HASH_DEC_APPLY_COUNT(ht) ((ht)->u.flags -= (1 << ZEND_HASH_APPLY_SHIFT))
866
867
868/* The following macros are useful to insert a sequence of new elements
869 * of packed array. They may be use insted of series of
870 * zend_hash_next_index_insert_new()
871 * (HashTable must have enough free buckets).
872 */
873#define ZEND_HASH_FILL_PACKED(ht) do { \
874		HashTable *__fill_ht = (ht); \
875		Bucket *__fill_bkt = __fill_ht->arData + __fill_ht->nNumUsed; \
876		uint32_t __fill_idx = __fill_ht->nNumUsed; \
877		ZEND_ASSERT(__fill_ht->u.flags & HASH_FLAG_PACKED);
878
879#define ZEND_HASH_FILL_ADD(_val) do { \
880		ZVAL_COPY_VALUE(&__fill_bkt->val, _val); \
881		__fill_bkt->h = (__fill_idx); \
882		__fill_bkt->key = NULL; \
883		__fill_bkt++; \
884		__fill_idx++; \
885	} while (0)
886
887#define ZEND_HASH_FILL_END() \
888		__fill_ht->nNumUsed = __fill_idx; \
889		__fill_ht->nNumOfElements = __fill_idx; \
890		__fill_ht->nNextFreeElement = __fill_idx; \
891		__fill_ht->nInternalPointer = __fill_idx ? 0 : HT_INVALID_IDX; \
892	} while (0)
893
894static zend_always_inline zval *_zend_hash_append(HashTable *ht, zend_string *key, zval *zv)
895{
896	uint32_t idx = ht->nNumUsed++;
897	uint32_t nIndex;
898	Bucket *p = ht->arData + idx;
899
900	ZVAL_COPY_VALUE(&p->val, zv);
901	if (!ZSTR_IS_INTERNED(key)) {
902		ht->u.flags &= ~HASH_FLAG_STATIC_KEYS;
903		zend_string_addref(key);
904		zend_string_hash_val(key);
905	}
906	p->key = key;
907	p->h = ZSTR_H(key);
908	nIndex = (uint32_t)p->h | ht->nTableMask;
909	Z_NEXT(p->val) = HT_HASH(ht, nIndex);
910	HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);
911	ht->nNumUsed = idx + 1;
912	ht->nNumOfElements++;
913	return &p->val;
914}
915
916static zend_always_inline zval *_zend_hash_append_ptr(HashTable *ht, zend_string *key, void *ptr)
917{
918	uint32_t idx = ht->nNumUsed++;
919	uint32_t nIndex;
920	Bucket *p = ht->arData + idx;
921
922	ZVAL_PTR(&p->val, ptr);
923	if (!ZSTR_IS_INTERNED(key)) {
924		ht->u.flags &= ~HASH_FLAG_STATIC_KEYS;
925		zend_string_addref(key);
926		zend_string_hash_val(key);
927	}
928	p->key = key;
929	p->h = ZSTR_H(key);
930	nIndex = (uint32_t)p->h | ht->nTableMask;
931	Z_NEXT(p->val) = HT_HASH(ht, nIndex);
932	HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);
933	ht->nNumUsed = idx + 1;
934	ht->nNumOfElements++;
935	return &p->val;
936}
937
938static zend_always_inline void _zend_hash_append_ind(HashTable *ht, zend_string *key, zval *ptr)
939{
940	uint32_t idx = ht->nNumUsed++;
941	uint32_t nIndex;
942	Bucket *p = ht->arData + idx;
943
944	ZVAL_INDIRECT(&p->val, ptr);
945	if (!ZSTR_IS_INTERNED(key)) {
946		ht->u.flags &= ~HASH_FLAG_STATIC_KEYS;
947		zend_string_addref(key);
948		zend_string_hash_val(key);
949	}
950	p->key = key;
951	p->h = ZSTR_H(key);
952	nIndex = (uint32_t)p->h | ht->nTableMask;
953	Z_NEXT(p->val) = HT_HASH(ht, nIndex);
954	HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);
955	ht->nNumUsed = idx + 1;
956	ht->nNumOfElements++;
957}
958
959#endif							/* ZEND_HASH_H */
960
961/*
962 * Local variables:
963 * tab-width: 4
964 * c-basic-offset: 4
965 * indent-tabs-mode: t
966 * End:
967 */
968