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