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);
157ZEND_API zval* ZEND_FASTCALL _zend_hash_index_find(const HashTable *ht, zend_ulong h);
158
159#define ZEND_HASH_INDEX_FIND(_ht, _h, _ret, _not_found) do { \
160		if (EXPECTED((_ht)->u.flags & HASH_FLAG_PACKED)) { \
161			if (EXPECTED((_h) < (_ht)->nNumUsed)) { \
162				_ret = &ht->arData[_h].val; \
163				if (UNEXPECTED(Z_TYPE_P(_ret) == IS_UNDEF)) { \
164					goto _not_found; \
165				} \
166			} else { \
167				goto _not_found; \
168			} \
169		} else { \
170			_ret = _zend_hash_index_find(_ht, _h); \
171			if (UNEXPECTED(_ret == NULL)) { \
172				goto _not_found; \
173			} \
174		} \
175	} while (0)
176
177
178/* Misc */
179ZEND_API zend_bool ZEND_FASTCALL zend_hash_exists(const HashTable *ht, zend_string *key);
180ZEND_API zend_bool ZEND_FASTCALL zend_hash_str_exists(const HashTable *ht, const char *str, size_t len);
181ZEND_API zend_bool ZEND_FASTCALL zend_hash_index_exists(const HashTable *ht, zend_ulong h);
182
183/* traversing */
184#define zend_hash_has_more_elements_ex(ht, pos) \
185	(zend_hash_get_current_key_type_ex(ht, pos) == HASH_KEY_NON_EXISTENT ? FAILURE : SUCCESS)
186ZEND_API int   ZEND_FASTCALL zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos);
187ZEND_API int   ZEND_FASTCALL zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos);
188ZEND_API int   ZEND_FASTCALL zend_hash_get_current_key_ex(const HashTable *ht, zend_string **str_index, zend_ulong *num_index, HashPosition *pos);
189ZEND_API void  ZEND_FASTCALL zend_hash_get_current_key_zval_ex(const HashTable *ht, zval *key, HashPosition *pos);
190ZEND_API int   ZEND_FASTCALL zend_hash_get_current_key_type_ex(HashTable *ht, HashPosition *pos);
191ZEND_API zval* ZEND_FASTCALL zend_hash_get_current_data_ex(HashTable *ht, HashPosition *pos);
192ZEND_API void  ZEND_FASTCALL zend_hash_internal_pointer_reset_ex(HashTable *ht, HashPosition *pos);
193ZEND_API void  ZEND_FASTCALL zend_hash_internal_pointer_end_ex(HashTable *ht, HashPosition *pos);
194
195#define zend_hash_has_more_elements(ht) \
196	zend_hash_has_more_elements_ex(ht, &(ht)->nInternalPointer)
197#define zend_hash_move_forward(ht) \
198	zend_hash_move_forward_ex(ht, &(ht)->nInternalPointer)
199#define zend_hash_move_backwards(ht) \
200	zend_hash_move_backwards_ex(ht, &(ht)->nInternalPointer)
201#define zend_hash_get_current_key(ht, str_index, num_index) \
202	zend_hash_get_current_key_ex(ht, str_index, num_index, &(ht)->nInternalPointer)
203#define zend_hash_get_current_key_zval(ht, key) \
204	zend_hash_get_current_key_zval_ex(ht, key, &(ht)->nInternalPointer)
205#define zend_hash_get_current_key_type(ht) \
206	zend_hash_get_current_key_type_ex(ht, &(ht)->nInternalPointer)
207#define zend_hash_get_current_data(ht) \
208	zend_hash_get_current_data_ex(ht, &(ht)->nInternalPointer)
209#define zend_hash_internal_pointer_reset(ht) \
210	zend_hash_internal_pointer_reset_ex(ht, &(ht)->nInternalPointer)
211#define zend_hash_internal_pointer_end(ht) \
212	zend_hash_internal_pointer_end_ex(ht, &(ht)->nInternalPointer)
213
214/* Copying, merging and sorting */
215ZEND_API void  ZEND_FASTCALL zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor);
216ZEND_API void  ZEND_FASTCALL _zend_hash_merge(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, zend_bool overwrite ZEND_FILE_LINE_DC);
217ZEND_API void  ZEND_FASTCALL zend_hash_merge_ex(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, merge_checker_func_t pMergeSource, void *pParam);
218ZEND_API void  zend_hash_bucket_swap(Bucket *p, Bucket *q);
219ZEND_API void  zend_hash_bucket_renum_swap(Bucket *p, Bucket *q);
220ZEND_API void  zend_hash_bucket_packed_swap(Bucket *p, Bucket *q);
221ZEND_API int   zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered);
222ZEND_API int   ZEND_FASTCALL zend_hash_sort_ex(HashTable *ht, sort_func_t sort_func, compare_func_t compare_func, zend_bool renumber);
223ZEND_API zval* ZEND_FASTCALL zend_hash_minmax(const HashTable *ht, compare_func_t compar, uint32_t flag);
224
225#define zend_hash_merge(target, source, pCopyConstructor, overwrite)					\
226	_zend_hash_merge(target, source, pCopyConstructor, overwrite ZEND_FILE_LINE_CC)
227
228#define zend_hash_sort(ht, compare_func, renumber) \
229	zend_hash_sort_ex(ht, zend_sort, compare_func, renumber)
230
231#define zend_hash_num_elements(ht) \
232	(ht)->nNumOfElements
233
234#define zend_hash_next_free_element(ht) \
235	(ht)->nNextFreeElement
236
237ZEND_API int ZEND_FASTCALL zend_hash_rehash(HashTable *ht);
238
239ZEND_API uint32_t zend_array_count(HashTable *ht);
240ZEND_API HashTable* ZEND_FASTCALL zend_array_dup(HashTable *source);
241ZEND_API void ZEND_FASTCALL zend_array_destroy(HashTable *ht);
242ZEND_API void ZEND_FASTCALL zend_symtable_clean(HashTable *ht);
243
244ZEND_API int ZEND_FASTCALL _zend_handle_numeric_str_ex(const char *key, size_t length, zend_ulong *idx);
245
246ZEND_API uint32_t     ZEND_FASTCALL zend_hash_iterator_add(HashTable *ht, HashPosition pos);
247ZEND_API HashPosition ZEND_FASTCALL zend_hash_iterator_pos(uint32_t idx, HashTable *ht);
248ZEND_API HashPosition ZEND_FASTCALL zend_hash_iterator_pos_ex(uint32_t idx, zval *array);
249ZEND_API void         ZEND_FASTCALL zend_hash_iterator_del(uint32_t idx);
250ZEND_API HashPosition ZEND_FASTCALL zend_hash_iterators_lower_pos(HashTable *ht, HashPosition start);
251ZEND_API void         ZEND_FASTCALL _zend_hash_iterators_update(HashTable *ht, HashPosition from, HashPosition to);
252
253static zend_always_inline void zend_hash_iterators_update(HashTable *ht, HashPosition from, HashPosition to)
254{
255	if (UNEXPECTED(ht->u.v.nIteratorsCount)) {
256		_zend_hash_iterators_update(ht, from, to);
257	}
258}
259
260
261END_EXTERN_C()
262
263#define ZEND_INIT_SYMTABLE(ht)								\
264	ZEND_INIT_SYMTABLE_EX(ht, 8, 0)
265
266#define ZEND_INIT_SYMTABLE_EX(ht, n, persistent)			\
267	zend_hash_init(ht, n, NULL, ZVAL_PTR_DTOR, persistent)
268
269static zend_always_inline int _zend_handle_numeric_str(const char *key, size_t length, zend_ulong *idx)
270{
271	const char *tmp = key;
272
273	if (*tmp > '9') {
274		return 0;
275	} else if (*tmp < '0') {
276		if (*tmp != '-') {
277			return 0;
278		}
279		tmp++;
280		if (*tmp > '9' || *tmp < '0') {
281			return 0;
282		}
283	}
284	return _zend_handle_numeric_str_ex(key, length, idx);
285}
286
287#define ZEND_HANDLE_NUMERIC_STR(key, length, idx) \
288	_zend_handle_numeric_str(key, length, &idx)
289
290#define ZEND_HANDLE_NUMERIC(key, idx) \
291	ZEND_HANDLE_NUMERIC_STR(ZSTR_VAL(key), ZSTR_LEN(key), idx)
292
293
294static zend_always_inline zval *zend_hash_find_ind(const HashTable *ht, zend_string *key)
295{
296	zval *zv;
297
298	zv = zend_hash_find(ht, key);
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 int zend_hash_exists_ind(const HashTable *ht, zend_string *key)
305{
306	zval *zv;
307
308	zv = zend_hash_find(ht, key);
309	return zv && (Z_TYPE_P(zv) != IS_INDIRECT ||
310			Z_TYPE_P(Z_INDIRECT_P(zv)) != IS_UNDEF);
311}
312
313
314static zend_always_inline zval *zend_hash_str_find_ind(const HashTable *ht, const char *str, size_t len)
315{
316	zval *zv;
317
318	zv = zend_hash_str_find(ht, str, len);
319	return (zv && Z_TYPE_P(zv) == IS_INDIRECT) ?
320		((Z_TYPE_P(Z_INDIRECT_P(zv)) != IS_UNDEF) ? Z_INDIRECT_P(zv) : NULL) : zv;
321}
322
323
324static zend_always_inline zval *zend_symtable_update(HashTable *ht, zend_string *key, zval *pData)
325{
326	zend_ulong idx;
327
328	if (ZEND_HANDLE_NUMERIC(key, idx)) {
329		return zend_hash_index_update(ht, idx, pData);
330	} else {
331		return zend_hash_update(ht, key, pData);
332	}
333}
334
335
336static zend_always_inline zval *zend_symtable_update_ind(HashTable *ht, zend_string *key, zval *pData)
337{
338	zend_ulong idx;
339
340	if (ZEND_HANDLE_NUMERIC(key, idx)) {
341		return zend_hash_index_update(ht, idx, pData);
342	} else {
343		return zend_hash_update_ind(ht, key, pData);
344	}
345}
346
347
348static zend_always_inline int zend_symtable_del(HashTable *ht, zend_string *key)
349{
350	zend_ulong idx;
351
352	if (ZEND_HANDLE_NUMERIC(key, idx)) {
353		return zend_hash_index_del(ht, idx);
354	} else {
355		return zend_hash_del(ht, key);
356	}
357}
358
359
360static zend_always_inline int zend_symtable_del_ind(HashTable *ht, zend_string *key)
361{
362	zend_ulong idx;
363
364	if (ZEND_HANDLE_NUMERIC(key, idx)) {
365		return zend_hash_index_del(ht, idx);
366	} else {
367		return zend_hash_del_ind(ht, key);
368	}
369}
370
371
372static zend_always_inline zval *zend_symtable_find(const HashTable *ht, zend_string *key)
373{
374	zend_ulong idx;
375
376	if (ZEND_HANDLE_NUMERIC(key, idx)) {
377		return zend_hash_index_find(ht, idx);
378	} else {
379		return zend_hash_find(ht, key);
380	}
381}
382
383
384static zend_always_inline zval *zend_symtable_find_ind(const HashTable *ht, zend_string *key)
385{
386	zend_ulong idx;
387
388	if (ZEND_HANDLE_NUMERIC(key, idx)) {
389		return zend_hash_index_find(ht, idx);
390	} else {
391		return zend_hash_find_ind(ht, key);
392	}
393}
394
395
396static zend_always_inline int zend_symtable_exists(HashTable *ht, zend_string *key)
397{
398	zend_ulong idx;
399
400	if (ZEND_HANDLE_NUMERIC(key, idx)) {
401		return zend_hash_index_exists(ht, idx);
402	} else {
403		return zend_hash_exists(ht, key);
404	}
405}
406
407
408static zend_always_inline int zend_symtable_exists_ind(HashTable *ht, zend_string *key)
409{
410	zend_ulong idx;
411
412	if (ZEND_HANDLE_NUMERIC(key, idx)) {
413		return zend_hash_index_exists(ht, idx);
414	} else {
415		return zend_hash_exists_ind(ht, key);
416	}
417}
418
419
420static zend_always_inline zval *zend_symtable_str_update(HashTable *ht, const char *str, size_t len, zval *pData)
421{
422	zend_ulong idx;
423
424	if (ZEND_HANDLE_NUMERIC_STR(str, len, idx)) {
425		return zend_hash_index_update(ht, idx, pData);
426	} else {
427		return zend_hash_str_update(ht, str, len, pData);
428	}
429}
430
431
432static zend_always_inline zval *zend_symtable_str_update_ind(HashTable *ht, const char *str, size_t len, zval *pData)
433{
434	zend_ulong idx;
435
436	if (ZEND_HANDLE_NUMERIC_STR(str, len, idx)) {
437		return zend_hash_index_update(ht, idx, pData);
438	} else {
439		return zend_hash_str_update_ind(ht, str, len, pData);
440	}
441}
442
443
444static zend_always_inline int zend_symtable_str_del(HashTable *ht, const char *str, size_t len)
445{
446	zend_ulong idx;
447
448	if (ZEND_HANDLE_NUMERIC_STR(str, len, idx)) {
449		return zend_hash_index_del(ht, idx);
450	} else {
451		return zend_hash_str_del(ht, str, len);
452	}
453}
454
455
456static zend_always_inline int zend_symtable_str_del_ind(HashTable *ht, const char *str, size_t len)
457{
458	zend_ulong idx;
459
460	if (ZEND_HANDLE_NUMERIC_STR(str, len, idx)) {
461		return zend_hash_index_del(ht, idx);
462	} else {
463		return zend_hash_str_del_ind(ht, str, len);
464	}
465}
466
467
468static zend_always_inline zval *zend_symtable_str_find(HashTable *ht, const char *str, size_t len)
469{
470	zend_ulong idx;
471
472	if (ZEND_HANDLE_NUMERIC_STR(str, len, idx)) {
473		return zend_hash_index_find(ht, idx);
474	} else {
475		return zend_hash_str_find(ht, str, len);
476	}
477}
478
479
480static zend_always_inline int zend_symtable_str_exists(HashTable *ht, const char *str, size_t len)
481{
482	zend_ulong idx;
483
484	if (ZEND_HANDLE_NUMERIC_STR(str, len, idx)) {
485		return zend_hash_index_exists(ht, idx);
486	} else {
487		return zend_hash_str_exists(ht, str, len);
488	}
489}
490
491static zend_always_inline void *zend_hash_add_ptr(HashTable *ht, zend_string *key, void *pData)
492{
493	zval tmp, *zv;
494
495	ZVAL_PTR(&tmp, pData);
496	zv = zend_hash_add(ht, key, &tmp);
497	if (zv) {
498		ZEND_ASSUME(Z_PTR_P(zv));
499		return Z_PTR_P(zv);
500	} else {
501		return NULL;
502	}
503}
504
505static zend_always_inline void *zend_hash_add_new_ptr(HashTable *ht, zend_string *key, void *pData)
506{
507	zval tmp, *zv;
508
509	ZVAL_PTR(&tmp, pData);
510	zv = zend_hash_add_new(ht, key, &tmp);
511	if (zv) {
512		ZEND_ASSUME(Z_PTR_P(zv));
513		return Z_PTR_P(zv);
514	} else {
515		return NULL;
516	}
517}
518
519static zend_always_inline void *zend_hash_str_add_ptr(HashTable *ht, const char *str, size_t len, void *pData)
520{
521	zval tmp, *zv;
522
523	ZVAL_PTR(&tmp, pData);
524	zv = zend_hash_str_add(ht, str, len, &tmp);
525	if (zv) {
526		ZEND_ASSUME(Z_PTR_P(zv));
527		return Z_PTR_P(zv);
528	} else {
529		return NULL;
530	}
531}
532
533static zend_always_inline void *zend_hash_str_add_new_ptr(HashTable *ht, const char *str, size_t len, void *pData)
534{
535	zval tmp, *zv;
536
537	ZVAL_PTR(&tmp, pData);
538	zv = zend_hash_str_add_new(ht, str, len, &tmp);
539	if (zv) {
540		ZEND_ASSUME(Z_PTR_P(zv));
541		return Z_PTR_P(zv);
542	} else {
543		return NULL;
544	}
545}
546
547static zend_always_inline void *zend_hash_update_ptr(HashTable *ht, zend_string *key, void *pData)
548{
549	zval tmp, *zv;
550
551	ZVAL_PTR(&tmp, pData);
552	zv = zend_hash_update(ht, key, &tmp);
553	if (zv) {
554		ZEND_ASSUME(Z_PTR_P(zv));
555		return Z_PTR_P(zv);
556	} else {
557		return NULL;
558	}
559}
560
561static zend_always_inline void *zend_hash_str_update_ptr(HashTable *ht, const char *str, size_t len, void *pData)
562{
563	zval tmp, *zv;
564
565	ZVAL_PTR(&tmp, pData);
566	zv = zend_hash_str_update(ht, str, len, &tmp);
567	if (zv) {
568		ZEND_ASSUME(Z_PTR_P(zv));
569		return Z_PTR_P(zv);
570	} else {
571		return NULL;
572	}
573}
574
575static zend_always_inline void *zend_hash_add_mem(HashTable *ht, zend_string *key, void *pData, size_t size)
576{
577	zval tmp, *zv;
578
579	ZVAL_PTR(&tmp, NULL);
580	if ((zv = zend_hash_add(ht, key, &tmp))) {
581		Z_PTR_P(zv) = pemalloc(size, ht->u.flags & HASH_FLAG_PERSISTENT);
582		memcpy(Z_PTR_P(zv), pData, size);
583		return Z_PTR_P(zv);
584	}
585	return NULL;
586}
587
588static zend_always_inline void *zend_hash_str_add_mem(HashTable *ht, const char *str, size_t len, void *pData, size_t size)
589{
590	zval tmp, *zv;
591
592	ZVAL_PTR(&tmp, NULL);
593	if ((zv = zend_hash_str_add(ht, str, len, &tmp))) {
594		Z_PTR_P(zv) = pemalloc(size, ht->u.flags & HASH_FLAG_PERSISTENT);
595		memcpy(Z_PTR_P(zv), pData, size);
596		return Z_PTR_P(zv);
597	}
598	return NULL;
599}
600
601static zend_always_inline void *zend_hash_update_mem(HashTable *ht, zend_string *key, void *pData, size_t size)
602{
603	void *p;
604
605	p = pemalloc(size, ht->u.flags & HASH_FLAG_PERSISTENT);
606	memcpy(p, pData, size);
607	return zend_hash_update_ptr(ht, key, p);
608}
609
610static zend_always_inline void *zend_hash_str_update_mem(HashTable *ht, const char *str, size_t len, void *pData, size_t size)
611{
612	void *p;
613
614	p = pemalloc(size, ht->u.flags & HASH_FLAG_PERSISTENT);
615	memcpy(p, pData, size);
616	return zend_hash_str_update_ptr(ht, str, len, p);
617}
618
619static zend_always_inline void *zend_hash_index_add_ptr(HashTable *ht, zend_ulong h, void *pData)
620{
621	zval tmp, *zv;
622
623	ZVAL_PTR(&tmp, pData);
624	zv = zend_hash_index_add(ht, h, &tmp);
625	return zv ? Z_PTR_P(zv) : NULL;
626}
627
628static zend_always_inline void *zend_hash_index_add_new_ptr(HashTable *ht, zend_ulong h, void *pData)
629{
630	zval tmp, *zv;
631
632	ZVAL_PTR(&tmp, pData);
633	zv = zend_hash_index_add_new(ht, h, &tmp);
634	return zv ? Z_PTR_P(zv) : NULL;
635}
636
637static zend_always_inline void *zend_hash_index_update_ptr(HashTable *ht, zend_ulong h, void *pData)
638{
639	zval tmp, *zv;
640
641	ZVAL_PTR(&tmp, pData);
642	zv = zend_hash_index_update(ht, h, &tmp);
643	if (zv) {
644		ZEND_ASSUME(Z_PTR_P(zv));
645		return Z_PTR_P(zv);
646	} else {
647		return NULL;
648	}
649}
650
651static zend_always_inline void *zend_hash_index_add_mem(HashTable *ht, zend_ulong h, void *pData, size_t size)
652{
653	zval tmp, *zv;
654
655	ZVAL_PTR(&tmp, NULL);
656	if ((zv = zend_hash_index_add(ht, h, &tmp))) {
657		Z_PTR_P(zv) = pemalloc(size, ht->u.flags & HASH_FLAG_PERSISTENT);
658		memcpy(Z_PTR_P(zv), pData, size);
659		return Z_PTR_P(zv);
660	}
661	return NULL;
662}
663
664static zend_always_inline void *zend_hash_next_index_insert_ptr(HashTable *ht, void *pData)
665{
666	zval tmp, *zv;
667
668	ZVAL_PTR(&tmp, pData);
669	zv = zend_hash_next_index_insert(ht, &tmp);
670	if (zv) {
671		ZEND_ASSUME(Z_PTR_P(zv));
672		return Z_PTR_P(zv);
673	} else {
674		return NULL;
675	}
676}
677
678static zend_always_inline void *zend_hash_index_update_mem(HashTable *ht, zend_ulong h, void *pData, size_t size)
679{
680	void *p;
681
682	p = pemalloc(size, ht->u.flags & HASH_FLAG_PERSISTENT);
683	memcpy(p, pData, size);
684	return zend_hash_index_update_ptr(ht, h, p);
685}
686
687static zend_always_inline void *zend_hash_next_index_insert_mem(HashTable *ht, void *pData, size_t size)
688{
689	zval tmp, *zv;
690
691	ZVAL_PTR(&tmp, NULL);
692	if ((zv = zend_hash_next_index_insert(ht, &tmp))) {
693		Z_PTR_P(zv) = pemalloc(size, ht->u.flags & HASH_FLAG_PERSISTENT);
694		memcpy(Z_PTR_P(zv), pData, size);
695		return Z_PTR_P(zv);
696	}
697	return NULL;
698}
699
700static zend_always_inline void *zend_hash_find_ptr(const HashTable *ht, zend_string *key)
701{
702	zval *zv;
703
704	zv = zend_hash_find(ht, key);
705	if (zv) {
706		ZEND_ASSUME(Z_PTR_P(zv));
707		return Z_PTR_P(zv);
708	} else {
709		return NULL;
710	}
711}
712
713static zend_always_inline void *zend_hash_str_find_ptr(const HashTable *ht, const char *str, size_t len)
714{
715	zval *zv;
716
717	zv = zend_hash_str_find(ht, str, len);
718	if (zv) {
719		ZEND_ASSUME(Z_PTR_P(zv));
720		return Z_PTR_P(zv);
721	} else {
722		return NULL;
723	}
724}
725
726static zend_always_inline void *zend_hash_index_find_ptr(const HashTable *ht, zend_ulong h)
727{
728	zval *zv;
729
730	zv = zend_hash_index_find(ht, h);
731	if (zv) {
732		ZEND_ASSUME(Z_PTR_P(zv));
733		return Z_PTR_P(zv);
734	} else {
735		return NULL;
736	}
737}
738
739static zend_always_inline void *zend_symtable_str_find_ptr(HashTable *ht, const char *str, size_t len)
740{
741	zend_ulong idx;
742
743	if (ZEND_HANDLE_NUMERIC_STR(str, len, idx)) {
744		return zend_hash_index_find_ptr(ht, idx);
745	} else {
746		return zend_hash_str_find_ptr(ht, str, len);
747	}
748}
749
750static zend_always_inline void *zend_hash_get_current_data_ptr_ex(HashTable *ht, HashPosition *pos)
751{
752	zval *zv;
753
754	zv = zend_hash_get_current_data_ex(ht, pos);
755	if (zv) {
756		ZEND_ASSUME(Z_PTR_P(zv));
757		return Z_PTR_P(zv);
758	} else {
759		return NULL;
760	}
761}
762
763#define zend_hash_get_current_data_ptr(ht) \
764	zend_hash_get_current_data_ptr_ex(ht, &(ht)->nInternalPointer)
765
766#define ZEND_HASH_FOREACH(_ht, indirect) do { \
767		Bucket *_p = (_ht)->arData; \
768		Bucket *_end = _p + (_ht)->nNumUsed; \
769		for (; _p != _end; _p++) { \
770			zval *_z = &_p->val; \
771			if (indirect && Z_TYPE_P(_z) == IS_INDIRECT) { \
772				_z = Z_INDIRECT_P(_z); \
773			} \
774			if (UNEXPECTED(Z_TYPE_P(_z) == IS_UNDEF)) continue;
775
776#define ZEND_HASH_REVERSE_FOREACH(_ht, indirect) do { \
777		uint _idx; \
778		for (_idx = (_ht)->nNumUsed; _idx > 0; _idx--) { \
779			Bucket *_p = (_ht)->arData + _idx - 1; \
780			zval *_z = &_p->val; \
781			if (indirect && Z_TYPE_P(_z) == IS_INDIRECT) { \
782				_z = Z_INDIRECT_P(_z); \
783			} \
784			if (UNEXPECTED(Z_TYPE_P(_z) == IS_UNDEF)) continue;
785
786#define ZEND_HASH_FOREACH_END() \
787		} \
788	} while (0)
789
790#define ZEND_HASH_FOREACH_BUCKET(ht, _bucket) \
791	ZEND_HASH_FOREACH(ht, 0); \
792	_bucket = _p;
793
794#define ZEND_HASH_FOREACH_VAL(ht, _val) \
795	ZEND_HASH_FOREACH(ht, 0); \
796	_val = _z;
797
798#define ZEND_HASH_FOREACH_VAL_IND(ht, _val) \
799	ZEND_HASH_FOREACH(ht, 1); \
800	_val = _z;
801
802#define ZEND_HASH_FOREACH_PTR(ht, _ptr) \
803	ZEND_HASH_FOREACH(ht, 0); \
804	_ptr = Z_PTR_P(_z);
805
806#define ZEND_HASH_FOREACH_NUM_KEY(ht, _h) \
807	ZEND_HASH_FOREACH(ht, 0); \
808	_h = _p->h;
809
810#define ZEND_HASH_FOREACH_STR_KEY(ht, _key) \
811	ZEND_HASH_FOREACH(ht, 0); \
812	_key = _p->key;
813
814#define ZEND_HASH_FOREACH_KEY(ht, _h, _key) \
815	ZEND_HASH_FOREACH(ht, 0); \
816	_h = _p->h; \
817	_key = _p->key;
818
819#define ZEND_HASH_FOREACH_NUM_KEY_VAL(ht, _h, _val) \
820	ZEND_HASH_FOREACH(ht, 0); \
821	_h = _p->h; \
822	_val = _z;
823
824#define ZEND_HASH_FOREACH_STR_KEY_VAL(ht, _key, _val) \
825	ZEND_HASH_FOREACH(ht, 0); \
826	_key = _p->key; \
827	_val = _z;
828
829#define ZEND_HASH_FOREACH_KEY_VAL(ht, _h, _key, _val) \
830	ZEND_HASH_FOREACH(ht, 0); \
831	_h = _p->h; \
832	_key = _p->key; \
833	_val = _z;
834
835#define ZEND_HASH_FOREACH_STR_KEY_VAL_IND(ht, _key, _val) \
836	ZEND_HASH_FOREACH(ht, 1); \
837	_key = _p->key; \
838	_val = _z;
839
840#define ZEND_HASH_FOREACH_KEY_VAL_IND(ht, _h, _key, _val) \
841	ZEND_HASH_FOREACH(ht, 1); \
842	_h = _p->h; \
843	_key = _p->key; \
844	_val = _z;
845
846#define ZEND_HASH_FOREACH_NUM_KEY_PTR(ht, _h, _ptr) \
847	ZEND_HASH_FOREACH(ht, 0); \
848	_h = _p->h; \
849	_ptr = Z_PTR_P(_z);
850
851#define ZEND_HASH_FOREACH_STR_KEY_PTR(ht, _key, _ptr) \
852	ZEND_HASH_FOREACH(ht, 0); \
853	_key = _p->key; \
854	_ptr = Z_PTR_P(_z);
855
856#define ZEND_HASH_FOREACH_KEY_PTR(ht, _h, _key, _ptr) \
857	ZEND_HASH_FOREACH(ht, 0); \
858	_h = _p->h; \
859	_key = _p->key; \
860	_ptr = Z_PTR_P(_z);
861
862#define ZEND_HASH_REVERSE_FOREACH_BUCKET(ht, _bucket) \
863	ZEND_HASH_REVERSE_FOREACH(ht, 0); \
864	_bucket = _p;
865
866#define ZEND_HASH_REVERSE_FOREACH_VAL(ht, _val) \
867	ZEND_HASH_REVERSE_FOREACH(ht, 0); \
868	_val = _z;
869
870#define ZEND_HASH_REVERSE_FOREACH_PTR(ht, _ptr) \
871	ZEND_HASH_REVERSE_FOREACH(ht, 0); \
872	_ptr = Z_PTR_P(_z);
873
874#define ZEND_HASH_REVERSE_FOREACH_VAL_IND(ht, _val) \
875	ZEND_HASH_REVERSE_FOREACH(ht, 1); \
876	_val = _z;
877
878#define ZEND_HASH_REVERSE_FOREACH_KEY_VAL(ht, _h, _key, _val) \
879	ZEND_HASH_REVERSE_FOREACH(ht, 0); \
880	_h = _p->h; \
881	_key = _p->key; \
882	_val = _z;
883
884#define ZEND_HASH_REVERSE_FOREACH_KEY_VAL_IND(ht, _h, _key, _val) \
885	ZEND_HASH_REVERSE_FOREACH(ht, 1); \
886	_h = _p->h; \
887	_key = _p->key; \
888	_val = _z;
889
890#define ZEND_HASH_APPLY_PROTECTION(ht) \
891	((ht)->u.flags & HASH_FLAG_APPLY_PROTECTION)
892
893#define ZEND_HASH_APPLY_SHIFT         8
894#define ZEND_HASH_APPLY_COUNT_MASK    0xff00
895#define ZEND_HASH_GET_APPLY_COUNT(ht) (((ht)->u.flags & ZEND_HASH_APPLY_COUNT_MASK) >> ZEND_HASH_APPLY_SHIFT)
896#define ZEND_HASH_INC_APPLY_COUNT(ht) ((ht)->u.flags += (1 << ZEND_HASH_APPLY_SHIFT))
897#define ZEND_HASH_DEC_APPLY_COUNT(ht) ((ht)->u.flags -= (1 << ZEND_HASH_APPLY_SHIFT))
898
899
900/* The following macros are useful to insert a sequence of new elements
901 * of packed array. They may be use insted of series of
902 * zend_hash_next_index_insert_new()
903 * (HashTable must have enough free buckets).
904 */
905#define ZEND_HASH_FILL_PACKED(ht) do { \
906		HashTable *__fill_ht = (ht); \
907		Bucket *__fill_bkt = __fill_ht->arData + __fill_ht->nNumUsed; \
908		uint32_t __fill_idx = __fill_ht->nNumUsed; \
909		ZEND_ASSERT(__fill_ht->u.flags & HASH_FLAG_PACKED);
910
911#define ZEND_HASH_FILL_ADD(_val) do { \
912		ZVAL_COPY_VALUE(&__fill_bkt->val, _val); \
913		__fill_bkt->h = (__fill_idx); \
914		__fill_bkt->key = NULL; \
915		__fill_bkt++; \
916		__fill_idx++; \
917	} while (0)
918
919#define ZEND_HASH_FILL_END() \
920		__fill_ht->nNumUsed = __fill_idx; \
921		__fill_ht->nNumOfElements = __fill_idx; \
922		__fill_ht->nNextFreeElement = __fill_idx; \
923		__fill_ht->nInternalPointer = __fill_idx ? 0 : HT_INVALID_IDX; \
924	} while (0)
925
926static zend_always_inline zval *_zend_hash_append(HashTable *ht, zend_string *key, zval *zv)
927{
928	uint32_t idx = ht->nNumUsed++;
929	uint32_t nIndex;
930	Bucket *p = ht->arData + idx;
931
932	ZVAL_COPY_VALUE(&p->val, zv);
933	if (!ZSTR_IS_INTERNED(key)) {
934		ht->u.flags &= ~HASH_FLAG_STATIC_KEYS;
935		zend_string_addref(key);
936		zend_string_hash_val(key);
937	}
938	p->key = key;
939	p->h = ZSTR_H(key);
940	nIndex = (uint32_t)p->h | ht->nTableMask;
941	Z_NEXT(p->val) = HT_HASH(ht, nIndex);
942	HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);
943	ht->nNumUsed = idx + 1;
944	ht->nNumOfElements++;
945	return &p->val;
946}
947
948static zend_always_inline zval *_zend_hash_append_ptr(HashTable *ht, zend_string *key, void *ptr)
949{
950	uint32_t idx = ht->nNumUsed++;
951	uint32_t nIndex;
952	Bucket *p = ht->arData + idx;
953
954	ZVAL_PTR(&p->val, ptr);
955	if (!ZSTR_IS_INTERNED(key)) {
956		ht->u.flags &= ~HASH_FLAG_STATIC_KEYS;
957		zend_string_addref(key);
958		zend_string_hash_val(key);
959	}
960	p->key = key;
961	p->h = ZSTR_H(key);
962	nIndex = (uint32_t)p->h | ht->nTableMask;
963	Z_NEXT(p->val) = HT_HASH(ht, nIndex);
964	HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);
965	ht->nNumUsed = idx + 1;
966	ht->nNumOfElements++;
967	return &p->val;
968}
969
970static zend_always_inline void _zend_hash_append_ind(HashTable *ht, zend_string *key, zval *ptr)
971{
972	uint32_t idx = ht->nNumUsed++;
973	uint32_t nIndex;
974	Bucket *p = ht->arData + idx;
975
976	ZVAL_INDIRECT(&p->val, ptr);
977	if (!ZSTR_IS_INTERNED(key)) {
978		ht->u.flags &= ~HASH_FLAG_STATIC_KEYS;
979		zend_string_addref(key);
980		zend_string_hash_val(key);
981	}
982	p->key = key;
983	p->h = ZSTR_H(key);
984	nIndex = (uint32_t)p->h | ht->nTableMask;
985	Z_NEXT(p->val) = HT_HASH(ht, nIndex);
986	HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);
987	ht->nNumUsed = idx + 1;
988	ht->nNumOfElements++;
989}
990
991#endif							/* ZEND_HASH_H */
992
993/*
994 * Local variables:
995 * tab-width: 4
996 * c-basic-offset: 4
997 * indent-tabs-mode: t
998 * End:
999 */
1000