/src/php-src/Zend/zend_hash.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | +----------------------------------------------------------------------+ |
3 | | | Zend Engine | |
4 | | +----------------------------------------------------------------------+ |
5 | | | Copyright (c) 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@php.net> | |
16 | | | Zeev Suraski <zeev@php.net> | |
17 | | | Dmitry Stogov <dmitry@php.net> | |
18 | | +----------------------------------------------------------------------+ |
19 | | */ |
20 | | |
21 | | #include "zend.h" |
22 | | #include "zend_globals.h" |
23 | | #include "zend_variables.h" |
24 | | |
25 | | #if defined(__aarch64__) || defined(_M_ARM64) |
26 | | # include <arm_neon.h> |
27 | | #endif |
28 | | |
29 | | /* Prefer to use AVX2 instructions for better latency and throughput */ |
30 | | #if defined(__AVX2__) |
31 | | # include <immintrin.h> |
32 | | #elif defined( __SSE2__) |
33 | | # include <emmintrin.h> |
34 | | #endif |
35 | | |
36 | | #if ZEND_DEBUG |
37 | | # define HT_ASSERT(ht, expr) \ |
38 | 2.97G | ZEND_ASSERT((expr) || (HT_FLAGS(ht) & HASH_FLAG_ALLOW_COW_VIOLATION)) |
39 | | #else |
40 | | # define HT_ASSERT(ht, expr) |
41 | | #endif |
42 | | |
43 | 2.96G | #define HT_ASSERT_RC1(ht) HT_ASSERT(ht, GC_REFCOUNT(ht) == 1) |
44 | | |
45 | 130 | #define HT_POISONED_PTR ((HashTable *) (intptr_t) -1) |
46 | | |
47 | | #if ZEND_DEBUG |
48 | | |
49 | 4.52G | #define HT_OK 0x00 |
50 | 0 | #define HT_IS_DESTROYING 0x01 |
51 | 0 | #define HT_DESTROYED 0x02 |
52 | 0 | #define HT_CLEANING 0x03 |
53 | | |
54 | | static void _zend_is_inconsistent(const HashTable *ht, const char *file, int line) |
55 | 4.52G | { |
56 | 4.52G | if ((HT_FLAGS(ht) & HASH_FLAG_CONSISTENCY) == HT_OK) { |
57 | 4.52G | return; |
58 | 4.52G | } |
59 | 0 | switch (HT_FLAGS(ht) & HASH_FLAG_CONSISTENCY) { |
60 | 0 | case HT_IS_DESTROYING: |
61 | 0 | zend_output_debug_string(1, "%s(%d) : ht=%p is being destroyed", file, line, ht); |
62 | 0 | break; |
63 | 0 | case HT_DESTROYED: |
64 | 0 | zend_output_debug_string(1, "%s(%d) : ht=%p is already destroyed", file, line, ht); |
65 | 0 | break; |
66 | 0 | case HT_CLEANING: |
67 | 0 | zend_output_debug_string(1, "%s(%d) : ht=%p is being cleaned", file, line, ht); |
68 | 0 | break; |
69 | 0 | default: |
70 | 0 | zend_output_debug_string(1, "%s(%d) : ht=%p is inconsistent", file, line, ht); |
71 | 0 | break; |
72 | 0 | } |
73 | 0 | ZEND_UNREACHABLE(); |
74 | 0 | } |
75 | 4.52G | #define IS_CONSISTENT(a) _zend_is_inconsistent(a, __FILE__, __LINE__); |
76 | 15.5M | #define SET_INCONSISTENT(n) do { \ |
77 | 15.5M | HT_FLAGS(ht) = (HT_FLAGS(ht) & ~HASH_FLAG_CONSISTENCY) | (n); \ |
78 | 15.5M | } while (0) |
79 | | #else |
80 | | #define IS_CONSISTENT(a) |
81 | | #define SET_INCONSISTENT(n) |
82 | | #endif |
83 | | |
84 | | #define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \ |
85 | 1.47G | if ((ht)->nNumUsed >= (ht)->nTableSize) { \ |
86 | 81.8k | zend_hash_do_resize(ht); \ |
87 | 81.8k | } |
88 | | |
89 | 284k | ZEND_API void *zend_hash_str_find_ptr_lc(const HashTable *ht, const char *str, size_t len) { |
90 | 284k | void *result; |
91 | 284k | char *lc_str; |
92 | | |
93 | | /* Stack allocate small strings to improve performance */ |
94 | 284k | ALLOCA_FLAG(use_heap) |
95 | | |
96 | 284k | lc_str = zend_str_tolower_copy(do_alloca(len + 1, use_heap), str, len); |
97 | 284k | result = zend_hash_str_find_ptr(ht, lc_str, len); |
98 | 284k | free_alloca(lc_str, use_heap); |
99 | | |
100 | 284k | return result; |
101 | 284k | } |
102 | | |
103 | 6.18k | ZEND_API void *zend_hash_find_ptr_lc(const HashTable *ht, zend_string *key) { |
104 | 6.18k | void *result; |
105 | 6.18k | zend_string *lc_key = zend_string_tolower(key); |
106 | 6.18k | result = zend_hash_find_ptr(ht, lc_key); |
107 | 6.18k | zend_string_release(lc_key); |
108 | 6.18k | return result; |
109 | 6.18k | } |
110 | | |
111 | | static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht); |
112 | | |
113 | | static zend_always_inline uint32_t zend_hash_check_size(uint32_t nSize) |
114 | 13.2M | { |
115 | | #ifdef ZEND_WIN32 |
116 | | unsigned long index; |
117 | | #endif |
118 | | |
119 | | /* Use big enough power of 2 */ |
120 | | /* size should be between HT_MIN_SIZE and HT_MAX_SIZE */ |
121 | 13.2M | if (nSize <= HT_MIN_SIZE) { |
122 | 12.0M | return HT_MIN_SIZE; |
123 | 12.0M | } else if (UNEXPECTED(nSize > HT_MAX_SIZE)) { |
124 | 0 | zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%u * %zu + %zu)", nSize, sizeof(Bucket), sizeof(Bucket)); |
125 | 0 | } |
126 | | |
127 | | #ifdef ZEND_WIN32 |
128 | | if (BitScanReverse(&index, nSize - 1)) { |
129 | | return 0x2u << ((31 - index) ^ 0x1f); |
130 | | } else { |
131 | | /* nSize is ensured to be in the valid range, fall back to it |
132 | | rather than using an undefined bis scan result. */ |
133 | | return nSize; |
134 | | } |
135 | | #elif (defined(__GNUC__) || __has_builtin(__builtin_clz)) && defined(PHP_HAVE_BUILTIN_CLZ) |
136 | 1.24M | return 0x2u << (__builtin_clz(nSize - 1) ^ 0x1f); |
137 | | #else |
138 | | nSize -= 1; |
139 | | nSize |= (nSize >> 1); |
140 | | nSize |= (nSize >> 2); |
141 | | nSize |= (nSize >> 4); |
142 | | nSize |= (nSize >> 8); |
143 | | nSize |= (nSize >> 16); |
144 | | return nSize + 1; |
145 | | #endif |
146 | 13.2M | } |
147 | | |
148 | | static zend_always_inline void zend_hash_real_init_packed_ex(HashTable *ht) |
149 | 3.18M | { |
150 | 3.18M | void *data; |
151 | | |
152 | 3.18M | if (UNEXPECTED(GC_FLAGS(ht) & IS_ARRAY_PERSISTENT)) { |
153 | 734 | data = pemalloc(HT_PACKED_SIZE_EX(ht->nTableSize, HT_MIN_MASK), 1); |
154 | 3.18M | } else if (EXPECTED(ht->nTableSize == HT_MIN_SIZE)) { |
155 | | /* Use specialized API with constant allocation amount for a particularly common case. */ |
156 | 3.16M | data = emalloc(HT_PACKED_SIZE_EX(HT_MIN_SIZE, HT_MIN_MASK)); |
157 | 3.16M | } else { |
158 | 18.6k | data = emalloc(HT_PACKED_SIZE_EX(ht->nTableSize, HT_MIN_MASK)); |
159 | 18.6k | } |
160 | 3.18M | HT_SET_DATA_ADDR(ht, data); |
161 | | /* Don't overwrite iterator count. */ |
162 | 3.18M | ht->u.v.flags = HASH_FLAG_PACKED | HASH_FLAG_STATIC_KEYS; |
163 | 3.18M | HT_HASH_RESET_PACKED(ht); |
164 | 3.18M | } |
165 | | |
166 | | static zend_always_inline void zend_hash_real_init_mixed_ex(HashTable *ht) |
167 | 5.37M | { |
168 | 5.37M | void *data; |
169 | 5.37M | uint32_t nSize = ht->nTableSize; |
170 | | |
171 | 5.37M | ZEND_ASSERT(HT_SIZE_TO_MASK(nSize)); |
172 | | |
173 | 5.37M | if (UNEXPECTED(GC_FLAGS(ht) & IS_ARRAY_PERSISTENT)) { |
174 | 4.74k | data = pemalloc(HT_SIZE_EX(nSize, HT_SIZE_TO_MASK(nSize)), 1); |
175 | 5.36M | } else if (EXPECTED(nSize == HT_MIN_SIZE)) { |
176 | 4.64M | data = emalloc(HT_SIZE_EX(HT_MIN_SIZE, HT_SIZE_TO_MASK(HT_MIN_SIZE))); |
177 | 4.64M | ht->nTableMask = HT_SIZE_TO_MASK(HT_MIN_SIZE); |
178 | 4.64M | HT_SET_DATA_ADDR(ht, data); |
179 | | /* Don't overwrite iterator count. */ |
180 | 4.64M | ht->u.v.flags = HASH_FLAG_STATIC_KEYS; |
181 | | #if defined(__AVX2__) |
182 | | do { |
183 | | __m256i ymm0 = _mm256_setzero_si256(); |
184 | | ymm0 = _mm256_cmpeq_epi64(ymm0, ymm0); |
185 | | _mm256_storeu_si256((__m256i*)&HT_HASH_EX(data, 0), ymm0); |
186 | | _mm256_storeu_si256((__m256i*)&HT_HASH_EX(data, 8), ymm0); |
187 | | } while(0); |
188 | | #elif defined (__SSE2__) |
189 | 4.64M | do { |
190 | 4.64M | __m128i xmm0 = _mm_setzero_si128(); |
191 | 4.64M | xmm0 = _mm_cmpeq_epi8(xmm0, xmm0); |
192 | 4.64M | _mm_storeu_si128((__m128i*)&HT_HASH_EX(data, 0), xmm0); |
193 | 4.64M | _mm_storeu_si128((__m128i*)&HT_HASH_EX(data, 4), xmm0); |
194 | 4.64M | _mm_storeu_si128((__m128i*)&HT_HASH_EX(data, 8), xmm0); |
195 | 4.64M | _mm_storeu_si128((__m128i*)&HT_HASH_EX(data, 12), xmm0); |
196 | 4.64M | } while (0); |
197 | | #elif defined(__aarch64__) || defined(_M_ARM64) |
198 | | do { |
199 | | int32x4_t t = vdupq_n_s32(-1); |
200 | | vst1q_s32((int32_t*)&HT_HASH_EX(data, 0), t); |
201 | | vst1q_s32((int32_t*)&HT_HASH_EX(data, 4), t); |
202 | | vst1q_s32((int32_t*)&HT_HASH_EX(data, 8), t); |
203 | | vst1q_s32((int32_t*)&HT_HASH_EX(data, 12), t); |
204 | | } while (0); |
205 | | #else |
206 | | HT_HASH_EX(data, 0) = -1; |
207 | | HT_HASH_EX(data, 1) = -1; |
208 | | HT_HASH_EX(data, 2) = -1; |
209 | | HT_HASH_EX(data, 3) = -1; |
210 | | HT_HASH_EX(data, 4) = -1; |
211 | | HT_HASH_EX(data, 5) = -1; |
212 | | HT_HASH_EX(data, 6) = -1; |
213 | | HT_HASH_EX(data, 7) = -1; |
214 | | HT_HASH_EX(data, 8) = -1; |
215 | | HT_HASH_EX(data, 9) = -1; |
216 | | HT_HASH_EX(data, 10) = -1; |
217 | | HT_HASH_EX(data, 11) = -1; |
218 | | HT_HASH_EX(data, 12) = -1; |
219 | | HT_HASH_EX(data, 13) = -1; |
220 | | HT_HASH_EX(data, 14) = -1; |
221 | | HT_HASH_EX(data, 15) = -1; |
222 | | #endif |
223 | 4.64M | return; |
224 | 4.64M | } else { |
225 | 723k | data = emalloc(HT_SIZE_EX(nSize, HT_SIZE_TO_MASK(nSize))); |
226 | 723k | } |
227 | 728k | ht->nTableMask = HT_SIZE_TO_MASK(nSize); |
228 | 728k | HT_SET_DATA_ADDR(ht, data); |
229 | 728k | HT_FLAGS(ht) = HASH_FLAG_STATIC_KEYS; |
230 | 728k | HT_HASH_RESET(ht); |
231 | 728k | } |
232 | | |
233 | | static zend_always_inline void zend_hash_real_init_ex(HashTable *ht, bool packed) |
234 | 30.0k | { |
235 | 30.0k | HT_ASSERT_RC1(ht); |
236 | 30.0k | ZEND_ASSERT(HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED); |
237 | 30.0k | if (packed) { |
238 | 81 | zend_hash_real_init_packed_ex(ht); |
239 | 29.9k | } else { |
240 | 29.9k | zend_hash_real_init_mixed_ex(ht); |
241 | 29.9k | } |
242 | 30.0k | } |
243 | | |
244 | | static const uint32_t uninitialized_bucket[-HT_MIN_MASK] = |
245 | | {HT_INVALID_IDX, HT_INVALID_IDX}; |
246 | | |
247 | | ZEND_API const HashTable zend_empty_array = { |
248 | | .gc.refcount = 2, |
249 | | .gc.u.type_info = IS_ARRAY | (GC_IMMUTABLE << GC_FLAGS_SHIFT), |
250 | | .u.flags = HASH_FLAG_UNINITIALIZED, |
251 | | .nTableMask = HT_MIN_MASK, |
252 | | {.arData = (Bucket*)&uninitialized_bucket[2]}, |
253 | | .nNumUsed = 0, |
254 | | .nNumOfElements = 0, |
255 | | .nTableSize = HT_MIN_SIZE, |
256 | | .nInternalPointer = 0, |
257 | | .nNextFreeElement = ZEND_LONG_MIN, |
258 | | .pDestructor = ZVAL_PTR_DTOR |
259 | | }; |
260 | | |
261 | | static zend_always_inline void _zend_hash_init_int(HashTable *ht, uint32_t nSize, dtor_func_t pDestructor, bool persistent) |
262 | 12.9M | { |
263 | 12.9M | GC_SET_REFCOUNT(ht, 1); |
264 | 12.9M | GC_TYPE_INFO(ht) = GC_ARRAY | (persistent ? ((GC_PERSISTENT|GC_NOT_COLLECTABLE) << GC_FLAGS_SHIFT) : 0); |
265 | 12.9M | HT_FLAGS(ht) = HASH_FLAG_UNINITIALIZED; |
266 | 12.9M | ht->nTableMask = HT_MIN_MASK; |
267 | 12.9M | HT_SET_DATA_ADDR(ht, &uninitialized_bucket); |
268 | 12.9M | ht->nNumUsed = 0; |
269 | 12.9M | ht->nNumOfElements = 0; |
270 | 12.9M | ht->nInternalPointer = 0; |
271 | 12.9M | ht->nNextFreeElement = ZEND_LONG_MIN; |
272 | 12.9M | ht->pDestructor = pDestructor; |
273 | 12.9M | ht->nTableSize = zend_hash_check_size(nSize); |
274 | 12.9M | } |
275 | | |
276 | | ZEND_API void ZEND_FASTCALL _zend_hash_init(HashTable *ht, uint32_t nSize, dtor_func_t pDestructor, bool persistent) |
277 | 2.94M | { |
278 | 2.94M | _zend_hash_init_int(ht, nSize, pDestructor, persistent); |
279 | 2.94M | } |
280 | | |
281 | | ZEND_API HashTable* ZEND_FASTCALL _zend_new_array_0(void) |
282 | 0 | { |
283 | 0 | HashTable *ht = emalloc(sizeof(HashTable)); |
284 | 0 | _zend_hash_init_int(ht, HT_MIN_SIZE, ZVAL_PTR_DTOR, 0); |
285 | 0 | return ht; |
286 | 0 | } |
287 | | |
288 | | ZEND_API HashTable* ZEND_FASTCALL _zend_new_array(uint32_t nSize) |
289 | 10.0M | { |
290 | 10.0M | HashTable *ht = emalloc(sizeof(HashTable)); |
291 | 10.0M | _zend_hash_init_int(ht, nSize, ZVAL_PTR_DTOR, 0); |
292 | 10.0M | return ht; |
293 | 10.0M | } |
294 | | |
295 | | ZEND_API HashTable* ZEND_FASTCALL zend_new_pair(const zval *val1, const zval *val2) |
296 | 0 | { |
297 | 0 | zval *zv; |
298 | 0 | HashTable *ht = emalloc(sizeof(HashTable)); |
299 | 0 | _zend_hash_init_int(ht, HT_MIN_SIZE, ZVAL_PTR_DTOR, 0); |
300 | 0 | ht->nNumUsed = ht->nNumOfElements = ht->nNextFreeElement = 2; |
301 | 0 | zend_hash_real_init_packed_ex(ht); |
302 | |
|
303 | 0 | zv = ht->arPacked; |
304 | 0 | ZVAL_COPY_VALUE(zv, val1); |
305 | 0 | zv++; |
306 | 0 | ZVAL_COPY_VALUE(zv, val2); |
307 | 0 | return ht; |
308 | 0 | } |
309 | | |
310 | | ZEND_API void ZEND_FASTCALL zend_hash_packed_grow(HashTable *ht) |
311 | 124k | { |
312 | 124k | HT_ASSERT_RC1(ht); |
313 | 124k | if (ht->nTableSize >= HT_MAX_SIZE) { |
314 | 0 | zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%u * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket), sizeof(Bucket)); |
315 | 0 | } |
316 | 124k | uint32_t newTableSize = ht->nTableSize * 2; |
317 | 124k | HT_SET_DATA_ADDR(ht, perealloc2(HT_GET_DATA_ADDR(ht), HT_PACKED_SIZE_EX(newTableSize, HT_MIN_MASK), HT_PACKED_USED_SIZE(ht), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT)); |
318 | 124k | ht->nTableSize = newTableSize; |
319 | 124k | } |
320 | | |
321 | | ZEND_API void ZEND_FASTCALL zend_hash_real_init(HashTable *ht, bool packed) |
322 | 30.0k | { |
323 | 30.0k | IS_CONSISTENT(ht); |
324 | | |
325 | 30.0k | HT_ASSERT_RC1(ht); |
326 | 30.0k | zend_hash_real_init_ex(ht, packed); |
327 | 30.0k | } |
328 | | |
329 | | ZEND_API void ZEND_FASTCALL zend_hash_real_init_packed(HashTable *ht) |
330 | 903k | { |
331 | 903k | IS_CONSISTENT(ht); |
332 | | |
333 | 903k | HT_ASSERT_RC1(ht); |
334 | 903k | zend_hash_real_init_packed_ex(ht); |
335 | 903k | } |
336 | | |
337 | | ZEND_API void ZEND_FASTCALL zend_hash_real_init_mixed(HashTable *ht) |
338 | 5.34M | { |
339 | 5.34M | IS_CONSISTENT(ht); |
340 | | |
341 | 5.34M | HT_ASSERT_RC1(ht); |
342 | 5.34M | zend_hash_real_init_mixed_ex(ht); |
343 | 5.34M | } |
344 | | |
345 | | ZEND_API void ZEND_FASTCALL zend_hash_packed_to_hash(HashTable *ht) |
346 | 15.8k | { |
347 | 15.8k | void *new_data, *old_data = HT_GET_DATA_ADDR(ht); |
348 | 15.8k | zval *src = ht->arPacked; |
349 | 15.8k | Bucket *dst; |
350 | 15.8k | uint32_t i; |
351 | 15.8k | uint32_t nSize = ht->nTableSize; |
352 | | |
353 | 15.8k | ZEND_ASSERT(HT_SIZE_TO_MASK(nSize)); |
354 | | |
355 | 15.8k | HT_ASSERT_RC1(ht); |
356 | | // Alloc before assign to avoid inconsistencies on OOM |
357 | 15.8k | new_data = pemalloc(HT_SIZE_EX(nSize, HT_SIZE_TO_MASK(nSize)), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT); |
358 | 15.8k | HT_FLAGS(ht) &= ~HASH_FLAG_PACKED; |
359 | 15.8k | ht->nTableMask = HT_SIZE_TO_MASK(ht->nTableSize); |
360 | 15.8k | HT_SET_DATA_ADDR(ht, new_data); |
361 | 15.8k | dst = ht->arData; |
362 | 206k | for (i = 0; i < ht->nNumUsed; i++) { |
363 | 190k | ZVAL_COPY_VALUE(&dst->val, src); |
364 | 190k | dst->h = i; |
365 | 190k | dst->key = NULL; |
366 | 190k | dst++; |
367 | 190k | src++; |
368 | 190k | } |
369 | 15.8k | pefree(old_data, GC_FLAGS(ht) & IS_ARRAY_PERSISTENT); |
370 | 15.8k | zend_hash_rehash(ht); |
371 | 15.8k | } |
372 | | |
373 | | ZEND_API void ZEND_FASTCALL zend_hash_to_packed(HashTable *ht) |
374 | 0 | { |
375 | 0 | void *new_data, *old_data = HT_GET_DATA_ADDR(ht); |
376 | 0 | Bucket *src = ht->arData; |
377 | 0 | zval *dst; |
378 | 0 | uint32_t i; |
379 | |
|
380 | 0 | HT_ASSERT_RC1(ht); |
381 | 0 | new_data = pemalloc(HT_PACKED_SIZE_EX(ht->nTableSize, HT_MIN_MASK), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT); |
382 | 0 | HT_FLAGS(ht) |= HASH_FLAG_PACKED | HASH_FLAG_STATIC_KEYS; |
383 | 0 | ht->nTableMask = HT_MIN_MASK; |
384 | 0 | HT_SET_DATA_ADDR(ht, new_data); |
385 | 0 | HT_HASH_RESET_PACKED(ht); |
386 | 0 | dst = ht->arPacked; |
387 | 0 | for (i = 0; i < ht->nNumUsed; i++) { |
388 | 0 | ZVAL_COPY_VALUE(dst, &src->val); |
389 | 0 | dst++; |
390 | 0 | src++; |
391 | 0 | } |
392 | 0 | pefree(old_data, GC_FLAGS(ht) & IS_ARRAY_PERSISTENT); |
393 | 0 | } |
394 | | |
395 | | ZEND_API void ZEND_FASTCALL zend_hash_extend(HashTable *ht, uint32_t nSize, bool packed) |
396 | 408k | { |
397 | 408k | HT_ASSERT_RC1(ht); |
398 | | |
399 | 408k | if (nSize == 0) return; |
400 | | |
401 | 405k | ZEND_ASSERT(HT_SIZE_TO_MASK(nSize)); |
402 | | |
403 | 405k | if (UNEXPECTED(HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED)) { |
404 | 30.0k | if (nSize > ht->nTableSize) { |
405 | 2.32k | ht->nTableSize = zend_hash_check_size(nSize); |
406 | 2.32k | } |
407 | 30.0k | zend_hash_real_init(ht, packed); |
408 | 375k | } else { |
409 | 375k | if (packed) { |
410 | 32 | ZEND_ASSERT(HT_IS_PACKED(ht)); |
411 | 32 | if (nSize > ht->nTableSize) { |
412 | 0 | uint32_t newTableSize = zend_hash_check_size(nSize); |
413 | 0 | HT_SET_DATA_ADDR(ht, perealloc2(HT_GET_DATA_ADDR(ht), HT_PACKED_SIZE_EX(newTableSize, HT_MIN_MASK), HT_PACKED_USED_SIZE(ht), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT)); |
414 | 0 | ht->nTableSize = newTableSize; |
415 | 0 | } |
416 | 375k | } else { |
417 | 375k | ZEND_ASSERT(!HT_IS_PACKED(ht)); |
418 | 375k | if (nSize > ht->nTableSize) { |
419 | 293k | void *new_data, *old_data = HT_GET_DATA_ADDR(ht); |
420 | 293k | Bucket *old_buckets = ht->arData; |
421 | 293k | nSize = zend_hash_check_size(nSize); |
422 | 293k | new_data = pemalloc(HT_SIZE_EX(nSize, HT_SIZE_TO_MASK(nSize)), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT); |
423 | 293k | ht->nTableSize = nSize; |
424 | 293k | ht->nTableMask = HT_SIZE_TO_MASK(ht->nTableSize); |
425 | 293k | HT_SET_DATA_ADDR(ht, new_data); |
426 | 293k | memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed); |
427 | 293k | pefree(old_data, GC_FLAGS(ht) & IS_ARRAY_PERSISTENT); |
428 | 293k | zend_hash_rehash(ht); |
429 | 293k | } |
430 | 375k | } |
431 | 375k | } |
432 | 405k | } |
433 | | |
434 | | ZEND_API void ZEND_FASTCALL zend_hash_discard(HashTable *ht, uint32_t nNumUsed) |
435 | 0 | { |
436 | 0 | Bucket *p, *end, *arData; |
437 | 0 | uint32_t nIndex; |
438 | |
|
439 | 0 | ZEND_ASSERT(!HT_IS_PACKED(ht)); |
440 | 0 | arData = ht->arData; |
441 | 0 | p = arData + ht->nNumUsed; |
442 | 0 | end = arData + nNumUsed; |
443 | 0 | ht->nNumUsed = nNumUsed; |
444 | 0 | while (p != end) { |
445 | 0 | p--; |
446 | 0 | if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) continue; |
447 | 0 | ht->nNumOfElements--; |
448 | | /* Collision pointers always directed from higher to lower buckets */ |
449 | | #if 0 |
450 | | if (!(Z_NEXT(p->val) == HT_INVALID_IDX || HT_HASH_TO_BUCKET_EX(arData, Z_NEXT(p->val)) < p)) { |
451 | | abort(); |
452 | | } |
453 | | #endif |
454 | 0 | nIndex = p->h | ht->nTableMask; |
455 | 0 | HT_HASH_EX(arData, nIndex) = Z_NEXT(p->val); |
456 | 0 | } |
457 | 0 | } |
458 | | |
459 | | static uint32_t zend_array_recalc_elements(const HashTable *ht) |
460 | 1.27k | { |
461 | 1.27k | zval *val; |
462 | 1.27k | uint32_t num = ht->nNumOfElements; |
463 | | |
464 | 7.24k | ZEND_HASH_MAP_FOREACH_VAL(ht, val) { |
465 | 7.24k | if (Z_TYPE_P(val) == IS_INDIRECT) { |
466 | 2.24k | if (UNEXPECTED(Z_TYPE_P(Z_INDIRECT_P(val)) == IS_UNDEF)) { |
467 | 1.24k | num--; |
468 | 1.24k | } |
469 | 2.24k | } |
470 | 7.24k | } ZEND_HASH_FOREACH_END(); |
471 | 1.27k | return num; |
472 | 1.27k | } |
473 | | /* }}} */ |
474 | | |
475 | | ZEND_API uint32_t zend_array_count(HashTable *ht) |
476 | 74.9k | { |
477 | 74.9k | uint32_t num; |
478 | 74.9k | if (UNEXPECTED(HT_FLAGS(ht) & HASH_FLAG_HAS_EMPTY_IND)) { |
479 | 1.27k | num = zend_array_recalc_elements(ht); |
480 | 1.27k | if (UNEXPECTED(ht->nNumOfElements == num)) { |
481 | 272 | HT_FLAGS(ht) &= ~HASH_FLAG_HAS_EMPTY_IND; |
482 | 272 | } |
483 | 73.6k | } else if (UNEXPECTED(ht == &EG(symbol_table))) { |
484 | 0 | num = zend_array_recalc_elements(ht); |
485 | 73.6k | } else { |
486 | 73.6k | num = zend_hash_num_elements(ht); |
487 | 73.6k | } |
488 | 74.9k | return num; |
489 | 74.9k | } |
490 | | /* }}} */ |
491 | | |
492 | | static zend_always_inline HashPosition _zend_hash_get_valid_pos(const HashTable *ht, HashPosition pos) |
493 | 10.6k | { |
494 | 10.6k | if (HT_IS_PACKED(ht)) { |
495 | 3.74k | while (pos < ht->nNumUsed && Z_ISUNDEF(ht->arPacked[pos])) { |
496 | 781 | pos++; |
497 | 781 | } |
498 | 7.68k | } else { |
499 | 7.90k | while (pos < ht->nNumUsed && Z_ISUNDEF(ht->arData[pos].val)) { |
500 | 216 | pos++; |
501 | 216 | } |
502 | 7.68k | } |
503 | 10.6k | return pos; |
504 | 10.6k | } |
505 | | |
506 | | static zend_always_inline HashPosition _zend_hash_get_current_pos(const HashTable *ht) |
507 | 281 | { |
508 | 281 | return _zend_hash_get_valid_pos(ht, ht->nInternalPointer); |
509 | 281 | } |
510 | | |
511 | | ZEND_API HashPosition ZEND_FASTCALL zend_hash_get_current_pos(const HashTable *ht) |
512 | 183 | { |
513 | 183 | return _zend_hash_get_current_pos(ht); |
514 | 183 | } |
515 | | |
516 | | ZEND_API HashPosition ZEND_FASTCALL zend_hash_get_current_pos_ex(const HashTable *ht, HashPosition pos) |
517 | 0 | { |
518 | 0 | return _zend_hash_get_valid_pos(ht, pos); |
519 | 0 | } |
520 | | |
521 | 52 | static void zend_hash_remove_iterator_copies(uint32_t idx) { |
522 | 52 | HashTableIterator *iterators = EG(ht_iterators); |
523 | | |
524 | 52 | HashTableIterator *iter = iterators + idx; |
525 | 52 | uint32_t next_idx = iter->next_copy; |
526 | 114 | while (next_idx != idx) { |
527 | 62 | uint32_t cur_idx = next_idx; |
528 | 62 | HashTableIterator *cur_iter = iterators + cur_idx; |
529 | 62 | next_idx = cur_iter->next_copy; |
530 | 62 | cur_iter->next_copy = cur_idx; // avoid recursion in zend_hash_iterator_del |
531 | 62 | zend_hash_iterator_del(cur_idx); |
532 | 62 | } |
533 | 52 | iter->next_copy = idx; |
534 | 52 | } |
535 | | |
536 | | ZEND_API uint32_t ZEND_FASTCALL zend_hash_iterator_add(HashTable *ht, HashPosition pos) |
537 | 1.78k | { |
538 | 1.78k | HashTableIterator *iter = EG(ht_iterators); |
539 | 1.78k | HashTableIterator *end = iter + EG(ht_iterators_count); |
540 | 1.78k | uint32_t idx; |
541 | | |
542 | 1.78k | if (EXPECTED(!HT_ITERATORS_OVERFLOW(ht))) { |
543 | 1.78k | HT_INC_ITERATORS_COUNT(ht); |
544 | 1.78k | } |
545 | 2.03k | while (iter != end) { |
546 | 2.03k | if (iter->ht == NULL) { |
547 | 1.78k | iter->ht = ht; |
548 | 1.78k | iter->pos = pos; |
549 | 1.78k | idx = iter - EG(ht_iterators); |
550 | 1.78k | iter->next_copy = idx; |
551 | 1.78k | if (idx + 1 > EG(ht_iterators_used)) { |
552 | 1.78k | EG(ht_iterators_used) = idx + 1; |
553 | 1.78k | } |
554 | 1.78k | return idx; |
555 | 1.78k | } |
556 | 252 | iter++; |
557 | 252 | } |
558 | 0 | if (EG(ht_iterators) == EG(ht_iterators_slots)) { |
559 | 0 | EG(ht_iterators) = emalloc(sizeof(HashTableIterator) * (EG(ht_iterators_count) + 8)); |
560 | 0 | memcpy(EG(ht_iterators), EG(ht_iterators_slots), sizeof(HashTableIterator) * EG(ht_iterators_count)); |
561 | 0 | } else { |
562 | 0 | EG(ht_iterators) = erealloc(EG(ht_iterators), sizeof(HashTableIterator) * (EG(ht_iterators_count) + 8)); |
563 | 0 | } |
564 | 0 | iter = EG(ht_iterators) + EG(ht_iterators_count); |
565 | 0 | EG(ht_iterators_count) += 8; |
566 | 0 | iter->ht = ht; |
567 | 0 | iter->pos = pos; |
568 | 0 | memset(iter + 1, 0, sizeof(HashTableIterator) * 7); |
569 | 0 | idx = iter - EG(ht_iterators); |
570 | 0 | iter->next_copy = idx; |
571 | 0 | EG(ht_iterators_used) = idx + 1; |
572 | 0 | return idx; |
573 | 1.78k | } |
574 | | |
575 | | // To avoid losing track of the HashTable when separating arrays, we track all copies at once. |
576 | 150 | static zend_always_inline bool zend_hash_iterator_find_copy_pos(uint32_t idx, HashTable *ht) { |
577 | 150 | HashTableIterator *iter = EG(ht_iterators) + idx; |
578 | | |
579 | 150 | uint32_t next_idx = iter->next_copy; |
580 | 150 | if (EXPECTED(next_idx != idx)) { |
581 | 52 | HashTableIterator *copy_iter; |
582 | 57 | while (next_idx != idx) { |
583 | 57 | copy_iter = EG(ht_iterators) + next_idx; |
584 | 57 | if (copy_iter->ht == ht) { |
585 | | // We have found the hashtable we are actually iterating over |
586 | | // Now clean any intermittent copies and replace the original index by the found one |
587 | 52 | if (EXPECTED(iter->ht) && EXPECTED(iter->ht != HT_POISONED_PTR) |
588 | 52 | && EXPECTED(!HT_ITERATORS_OVERFLOW(iter->ht))) { |
589 | 42 | HT_DEC_ITERATORS_COUNT(iter->ht); |
590 | 42 | } |
591 | 52 | if (EXPECTED(!HT_ITERATORS_OVERFLOW(ht))) { |
592 | 52 | HT_INC_ITERATORS_COUNT(ht); |
593 | 52 | } |
594 | 52 | iter->ht = copy_iter->ht; |
595 | 52 | iter->pos = copy_iter->pos; |
596 | 52 | zend_hash_remove_iterator_copies(idx); |
597 | 52 | return true; |
598 | 52 | } |
599 | 5 | next_idx = copy_iter->next_copy; |
600 | 5 | } |
601 | 0 | zend_hash_remove_iterator_copies(idx); |
602 | 0 | } |
603 | | |
604 | 98 | return false; |
605 | 150 | } |
606 | | |
607 | | ZEND_API HashPosition ZEND_FASTCALL zend_hash_iterator_pos(uint32_t idx, HashTable *ht) |
608 | 1.89k | { |
609 | 1.89k | HashTableIterator *iter = EG(ht_iterators) + idx; |
610 | | |
611 | 1.89k | ZEND_ASSERT(idx != (uint32_t)-1); |
612 | 1.89k | if (UNEXPECTED(iter->ht != ht) && !zend_hash_iterator_find_copy_pos(idx, ht)) { |
613 | 0 | if (EXPECTED(iter->ht) && EXPECTED(iter->ht != HT_POISONED_PTR) |
614 | 0 | && EXPECTED(!HT_ITERATORS_OVERFLOW(iter->ht))) { |
615 | 0 | HT_DEC_ITERATORS_COUNT(iter->ht); |
616 | 0 | } |
617 | 0 | if (EXPECTED(!HT_ITERATORS_OVERFLOW(ht))) { |
618 | 0 | HT_INC_ITERATORS_COUNT(ht); |
619 | 0 | } |
620 | 0 | iter->ht = ht; |
621 | 0 | iter->pos = _zend_hash_get_current_pos(ht); |
622 | 0 | } |
623 | 1.89k | return iter->pos; |
624 | 1.89k | } |
625 | | |
626 | | ZEND_API HashPosition ZEND_FASTCALL zend_hash_iterator_pos_ex(uint32_t idx, zval *array) |
627 | 5.44k | { |
628 | 5.44k | HashTable *ht = Z_ARRVAL_P(array); |
629 | 5.44k | HashTableIterator *iter = EG(ht_iterators) + idx; |
630 | | |
631 | 5.44k | ZEND_ASSERT(idx != (uint32_t)-1); |
632 | 5.44k | if (UNEXPECTED(iter->ht != ht) && !zend_hash_iterator_find_copy_pos(idx, ht)) { |
633 | 98 | if (EXPECTED(iter->ht) && EXPECTED(iter->ht != HT_POISONED_PTR) |
634 | 98 | && EXPECTED(!HT_ITERATORS_OVERFLOW(ht))) { |
635 | 0 | HT_DEC_ITERATORS_COUNT(iter->ht); |
636 | 0 | } |
637 | 98 | SEPARATE_ARRAY(array); |
638 | 98 | ht = Z_ARRVAL_P(array); |
639 | 98 | if (EXPECTED(!HT_ITERATORS_OVERFLOW(ht))) { |
640 | 98 | HT_INC_ITERATORS_COUNT(ht); |
641 | 98 | } |
642 | 98 | iter->ht = ht; |
643 | 98 | iter->pos = _zend_hash_get_current_pos(ht); |
644 | 98 | } |
645 | 5.44k | return iter->pos; |
646 | 5.44k | } |
647 | | |
648 | | ZEND_API void ZEND_FASTCALL zend_hash_iterator_del(uint32_t idx) |
649 | 1.77k | { |
650 | 1.77k | HashTableIterator *iter = EG(ht_iterators) + idx; |
651 | | |
652 | 1.77k | ZEND_ASSERT(idx != (uint32_t)-1); |
653 | | |
654 | 1.77k | if (EXPECTED(iter->ht) && EXPECTED(iter->ht != HT_POISONED_PTR) |
655 | 1.77k | && EXPECTED(!HT_ITERATORS_OVERFLOW(iter->ht))) { |
656 | 1.75k | ZEND_ASSERT(HT_ITERATORS_COUNT(iter->ht) != 0); |
657 | 1.75k | HT_DEC_ITERATORS_COUNT(iter->ht); |
658 | 1.75k | } |
659 | 1.77k | iter->ht = NULL; |
660 | | |
661 | 1.77k | if (UNEXPECTED(iter->next_copy != idx)) { |
662 | 0 | zend_hash_remove_iterator_copies(idx); |
663 | 0 | } |
664 | | |
665 | 1.77k | if (idx == EG(ht_iterators_used) - 1) { |
666 | 1.77k | while (idx > 0 && EG(ht_iterators)[idx - 1].ht == NULL) { |
667 | 12 | idx--; |
668 | 12 | } |
669 | 1.76k | EG(ht_iterators_used) = idx; |
670 | 1.76k | } |
671 | 1.77k | } |
672 | | |
673 | | static zend_never_inline void ZEND_FASTCALL _zend_hash_iterators_remove(const HashTable *ht) |
674 | 130 | { |
675 | 130 | HashTableIterator *iter = EG(ht_iterators); |
676 | 130 | const HashTableIterator *end = iter + EG(ht_iterators_used); |
677 | | |
678 | 270 | while (iter != end) { |
679 | 140 | if (iter->ht == ht) { |
680 | 130 | iter->ht = HT_POISONED_PTR; |
681 | 130 | } |
682 | 140 | iter++; |
683 | 140 | } |
684 | 130 | } |
685 | | |
686 | | static zend_always_inline void zend_hash_iterators_remove(const HashTable *ht) |
687 | 10.3M | { |
688 | 10.3M | if (UNEXPECTED(HT_HAS_ITERATORS(ht))) { |
689 | 130 | _zend_hash_iterators_remove(ht); |
690 | 130 | } |
691 | 10.3M | } |
692 | | |
693 | | ZEND_API HashPosition ZEND_FASTCALL zend_hash_iterators_lower_pos(const HashTable *ht, HashPosition start) |
694 | 1.09k | { |
695 | 1.09k | const HashTableIterator *iter = EG(ht_iterators); |
696 | 1.09k | const HashTableIterator *end = iter + EG(ht_iterators_used); |
697 | 1.09k | HashPosition res = ht->nNumUsed; |
698 | | |
699 | 1.73k | while (iter != end) { |
700 | 640 | if (iter->ht == ht) { |
701 | 625 | if (iter->pos >= start && iter->pos < res) { |
702 | 257 | res = iter->pos; |
703 | 257 | } |
704 | 625 | } |
705 | 640 | iter++; |
706 | 640 | } |
707 | 1.09k | return res; |
708 | 1.09k | } |
709 | | |
710 | | ZEND_API void ZEND_FASTCALL _zend_hash_iterators_update(const HashTable *ht, HashPosition from, HashPosition to) |
711 | 234 | { |
712 | 234 | HashTableIterator *iter = EG(ht_iterators); |
713 | 234 | const HashTableIterator *end = iter + EG(ht_iterators_used); |
714 | | |
715 | 518 | while (iter != end) { |
716 | 284 | if (iter->ht == ht && iter->pos == from) { |
717 | 207 | iter->pos = to; |
718 | 207 | } |
719 | 284 | iter++; |
720 | 284 | } |
721 | 234 | } |
722 | | |
723 | | ZEND_API void ZEND_FASTCALL zend_hash_iterators_advance(const HashTable *ht, HashPosition step) |
724 | 5 | { |
725 | 5 | HashTableIterator *iter = EG(ht_iterators); |
726 | 5 | const HashTableIterator *end = iter + EG(ht_iterators_used); |
727 | | |
728 | 10 | while (iter != end) { |
729 | 5 | if (iter->ht == ht) { |
730 | 5 | iter->pos += step; |
731 | 5 | } |
732 | 5 | iter++; |
733 | 5 | } |
734 | 5 | } |
735 | | |
736 | | /* Hash must be known and precomputed before */ |
737 | | static zend_always_inline Bucket *zend_hash_find_bucket(const HashTable *ht, const zend_string *key) |
738 | 46.0M | { |
739 | 46.0M | uint32_t nIndex; |
740 | 46.0M | uint32_t idx; |
741 | 46.0M | Bucket *p, *arData; |
742 | | |
743 | 46.0M | ZEND_ASSERT(ZSTR_H(key) != 0 && "Hash must be known"); |
744 | | |
745 | 46.0M | arData = ht->arData; |
746 | 46.0M | nIndex = ZSTR_H(key) | ht->nTableMask; |
747 | 46.0M | idx = HT_HASH_EX(arData, nIndex); |
748 | | |
749 | 46.0M | if (UNEXPECTED(idx == HT_INVALID_IDX)) { |
750 | 9.67M | return NULL; |
751 | 9.67M | } |
752 | 36.3M | p = HT_HASH_TO_BUCKET_EX(arData, idx); |
753 | 36.3M | if (EXPECTED(p->key == key)) { /* check for the same interned string */ |
754 | 32.0M | return p; |
755 | 32.0M | } |
756 | | |
757 | 4.79M | while (1) { |
758 | 4.79M | if (p->h == ZSTR_H(key) && |
759 | 4.79M | EXPECTED(p->key) && |
760 | 4.79M | zend_string_equal_content(p->key, key)) { |
761 | 1.79M | return p; |
762 | 1.79M | } |
763 | 2.99M | idx = Z_NEXT(p->val); |
764 | 2.99M | if (idx == HT_INVALID_IDX) { |
765 | 2.35M | return NULL; |
766 | 2.35M | } |
767 | 640k | p = HT_HASH_TO_BUCKET_EX(arData, idx); |
768 | 640k | if (p->key == key) { /* check for the same interned string */ |
769 | 160k | return p; |
770 | 160k | } |
771 | 640k | } |
772 | 4.31M | } |
773 | | |
774 | | static zend_always_inline Bucket *zend_hash_str_find_bucket(const HashTable *ht, const char *str, size_t len, zend_ulong h) |
775 | 5.61M | { |
776 | 5.61M | uint32_t nIndex; |
777 | 5.61M | uint32_t idx; |
778 | 5.61M | Bucket *p, *arData; |
779 | | |
780 | 5.61M | arData = ht->arData; |
781 | 5.61M | nIndex = h | ht->nTableMask; |
782 | 5.61M | idx = HT_HASH_EX(arData, nIndex); |
783 | 5.87M | while (idx != HT_INVALID_IDX) { |
784 | 1.19M | ZEND_ASSERT(idx < HT_IDX_TO_HASH(ht->nTableSize)); |
785 | 1.19M | p = HT_HASH_TO_BUCKET_EX(arData, idx); |
786 | 1.19M | if ((p->h == h) |
787 | 1.19M | && p->key |
788 | 1.19M | && zend_string_equals_cstr(p->key, str, len)) { |
789 | 936k | return p; |
790 | 936k | } |
791 | 257k | idx = Z_NEXT(p->val); |
792 | 257k | } |
793 | 4.67M | return NULL; |
794 | 5.61M | } |
795 | | |
796 | | static zend_always_inline Bucket *zend_hash_index_find_bucket(const HashTable *ht, zend_ulong h) |
797 | 2.97G | { |
798 | 2.97G | uint32_t nIndex; |
799 | 2.97G | uint32_t idx; |
800 | 2.97G | Bucket *p, *arData; |
801 | | |
802 | 2.97G | arData = ht->arData; |
803 | 2.97G | nIndex = h | ht->nTableMask; |
804 | 2.97G | idx = HT_HASH_EX(arData, nIndex); |
805 | 3.36G | while (idx != HT_INVALID_IDX) { |
806 | 1.88G | ZEND_ASSERT(idx < HT_IDX_TO_HASH(ht->nTableSize)); |
807 | 1.88G | p = HT_HASH_TO_BUCKET_EX(arData, idx); |
808 | 1.88G | if (p->h == h && !p->key) { |
809 | 1.48G | return p; |
810 | 1.48G | } |
811 | 397M | idx = Z_NEXT(p->val); |
812 | 397M | } |
813 | 1.48G | return NULL; |
814 | 2.97G | } |
815 | | |
816 | | static zend_always_inline zval *_zend_hash_add_or_update_i(HashTable *ht, zend_string *key, zval *pData, uint32_t flag) |
817 | 6.35M | { |
818 | 6.35M | zend_ulong h; |
819 | 6.35M | uint32_t nIndex; |
820 | 6.35M | uint32_t idx; |
821 | 6.35M | Bucket *p, *arData; |
822 | | |
823 | 6.35M | IS_CONSISTENT(ht); |
824 | 6.35M | HT_ASSERT_RC1(ht); |
825 | 6.35M | zend_string_hash_val(key); |
826 | | |
827 | 6.35M | if (UNEXPECTED(HT_FLAGS(ht) & (HASH_FLAG_UNINITIALIZED|HASH_FLAG_PACKED))) { |
828 | 875k | if (EXPECTED(HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED)) { |
829 | 868k | zend_hash_real_init_mixed(ht); |
830 | 868k | goto add_to_hash; |
831 | 868k | } else { |
832 | 6.78k | zend_hash_packed_to_hash(ht); |
833 | 6.78k | } |
834 | 5.48M | } else if ((flag & HASH_ADD_NEW) == 0 || ZEND_DEBUG) { |
835 | 5.48M | p = zend_hash_find_bucket(ht, key); |
836 | | |
837 | 5.48M | if (p) { |
838 | 915k | zval *data; |
839 | | |
840 | 915k | ZEND_ASSERT((flag & HASH_ADD_NEW) == 0); |
841 | 915k | if (flag & HASH_LOOKUP) { |
842 | 243k | return &p->val; |
843 | 672k | } else if (flag & HASH_ADD) { |
844 | 266k | if (!(flag & HASH_UPDATE_INDIRECT)) { |
845 | 265k | return NULL; |
846 | 265k | } |
847 | 1.20k | ZEND_ASSERT(&p->val != pData); |
848 | 1.20k | data = &p->val; |
849 | 1.20k | if (Z_TYPE_P(data) == IS_INDIRECT) { |
850 | 0 | data = Z_INDIRECT_P(data); |
851 | 0 | if (Z_TYPE_P(data) != IS_UNDEF) { |
852 | 0 | return NULL; |
853 | 0 | } |
854 | 1.20k | } else { |
855 | 1.20k | return NULL; |
856 | 1.20k | } |
857 | 405k | } else { |
858 | 405k | ZEND_ASSERT(&p->val != pData); |
859 | 405k | data = &p->val; |
860 | 405k | if ((flag & HASH_UPDATE_INDIRECT) && Z_TYPE_P(data) == IS_INDIRECT) { |
861 | 0 | data = Z_INDIRECT_P(data); |
862 | 0 | } |
863 | 405k | } |
864 | 405k | if (ht->pDestructor) { |
865 | 405k | ht->pDestructor(data); |
866 | 405k | } |
867 | 405k | ZVAL_COPY_VALUE(data, pData); |
868 | 405k | return data; |
869 | 915k | } |
870 | 5.48M | } |
871 | | |
872 | 4.57M | ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */ |
873 | | |
874 | 5.44M | add_to_hash: |
875 | 5.44M | if (!ZSTR_IS_INTERNED(key)) { |
876 | 1.40M | zend_string_addref(key); |
877 | 1.40M | HT_FLAGS(ht) &= ~HASH_FLAG_STATIC_KEYS; |
878 | 1.40M | } |
879 | 5.44M | idx = ht->nNumUsed++; |
880 | 5.44M | ht->nNumOfElements++; |
881 | 5.44M | arData = ht->arData; |
882 | 5.44M | p = arData + idx; |
883 | 5.44M | p->key = key; |
884 | 5.44M | p->h = h = ZSTR_H(key); |
885 | 5.44M | nIndex = h | ht->nTableMask; |
886 | 5.44M | Z_NEXT(p->val) = HT_HASH_EX(arData, nIndex); |
887 | 5.44M | HT_HASH_EX(arData, nIndex) = HT_IDX_TO_HASH(idx); |
888 | 5.44M | if (flag & HASH_LOOKUP) { |
889 | 454k | ZVAL_NULL(&p->val); |
890 | 4.98M | } else { |
891 | 4.98M | ZVAL_COPY_VALUE(&p->val, pData); |
892 | 4.98M | } |
893 | | |
894 | 5.44M | return &p->val; |
895 | 4.57M | } |
896 | | |
897 | | static zend_always_inline zval *_zend_hash_str_add_or_update_i(HashTable *ht, const char *str, size_t len, zend_ulong h, zval *pData, uint32_t flag) |
898 | 404k | { |
899 | 404k | zend_string *key; |
900 | 404k | uint32_t nIndex; |
901 | 404k | uint32_t idx; |
902 | 404k | Bucket *p; |
903 | | |
904 | 404k | IS_CONSISTENT(ht); |
905 | 404k | HT_ASSERT_RC1(ht); |
906 | | |
907 | 404k | if (UNEXPECTED(HT_FLAGS(ht) & (HASH_FLAG_UNINITIALIZED|HASH_FLAG_PACKED))) { |
908 | 253k | if (EXPECTED(HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED)) { |
909 | 253k | zend_hash_real_init_mixed(ht); |
910 | 253k | goto add_to_hash; |
911 | 253k | } else { |
912 | 56 | zend_hash_packed_to_hash(ht); |
913 | 56 | } |
914 | 253k | } else if ((flag & HASH_ADD_NEW) == 0) { |
915 | 150k | p = zend_hash_str_find_bucket(ht, str, len, h); |
916 | | |
917 | 150k | if (p) { |
918 | 107k | zval *data; |
919 | | |
920 | 107k | if (flag & HASH_LOOKUP) { |
921 | 0 | return &p->val; |
922 | 107k | } else if (flag & HASH_ADD) { |
923 | 0 | if (!(flag & HASH_UPDATE_INDIRECT)) { |
924 | 0 | return NULL; |
925 | 0 | } |
926 | 0 | ZEND_ASSERT(&p->val != pData); |
927 | 0 | data = &p->val; |
928 | 0 | if (Z_TYPE_P(data) == IS_INDIRECT) { |
929 | 0 | data = Z_INDIRECT_P(data); |
930 | 0 | if (Z_TYPE_P(data) != IS_UNDEF) { |
931 | 0 | return NULL; |
932 | 0 | } |
933 | 0 | } else { |
934 | 0 | return NULL; |
935 | 0 | } |
936 | 107k | } else { |
937 | 107k | ZEND_ASSERT(&p->val != pData); |
938 | 107k | data = &p->val; |
939 | 107k | if ((flag & HASH_UPDATE_INDIRECT) && Z_TYPE_P(data) == IS_INDIRECT) { |
940 | 0 | data = Z_INDIRECT_P(data); |
941 | 0 | } |
942 | 107k | } |
943 | 107k | if (ht->pDestructor) { |
944 | 107k | ht->pDestructor(data); |
945 | 107k | } |
946 | 107k | ZVAL_COPY_VALUE(data, pData); |
947 | 107k | return data; |
948 | 107k | } |
949 | 150k | } |
950 | | |
951 | 43.8k | ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */ |
952 | | |
953 | 297k | add_to_hash: |
954 | 297k | idx = ht->nNumUsed++; |
955 | 297k | ht->nNumOfElements++; |
956 | 297k | p = ht->arData + idx; |
957 | 297k | p->key = key = zend_string_init(str, len, GC_FLAGS(ht) & IS_ARRAY_PERSISTENT); |
958 | | #if ZEND_RC_DEBUG |
959 | | if (GC_FLAGS(ht) & GC_PERSISTENT_LOCAL) { |
960 | | GC_MAKE_PERSISTENT_LOCAL(key); |
961 | | } |
962 | | #endif |
963 | 297k | p->h = ZSTR_H(key) = h; |
964 | 297k | HT_FLAGS(ht) &= ~HASH_FLAG_STATIC_KEYS; |
965 | 297k | if (flag & HASH_LOOKUP) { |
966 | 0 | ZVAL_NULL(&p->val); |
967 | 297k | } else { |
968 | 297k | ZVAL_COPY_VALUE(&p->val, pData); |
969 | 297k | } |
970 | 297k | nIndex = h | ht->nTableMask; |
971 | 297k | Z_NEXT(p->val) = HT_HASH(ht, nIndex); |
972 | 297k | HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx); |
973 | | |
974 | 297k | return &p->val; |
975 | 43.8k | } |
976 | | |
977 | | ZEND_API zval* ZEND_FASTCALL zend_hash_add_or_update(HashTable *ht, zend_string *key, zval *pData, uint32_t flag) |
978 | 0 | { |
979 | 0 | if (flag == HASH_ADD) { |
980 | 0 | return zend_hash_add(ht, key, pData); |
981 | 0 | } else if (flag == HASH_ADD_NEW) { |
982 | 0 | return zend_hash_add_new(ht, key, pData); |
983 | 0 | } else if (flag == HASH_UPDATE) { |
984 | 0 | return zend_hash_update(ht, key, pData); |
985 | 0 | } else { |
986 | 0 | ZEND_ASSERT(flag == (HASH_UPDATE|HASH_UPDATE_INDIRECT)); |
987 | 0 | return zend_hash_update_ind(ht, key, pData); |
988 | 0 | } |
989 | 0 | } |
990 | | |
991 | | ZEND_API zval* ZEND_FASTCALL zend_hash_add(HashTable *ht, zend_string *key, zval *pData) |
992 | 990k | { |
993 | 990k | return _zend_hash_add_or_update_i(ht, key, pData, HASH_ADD); |
994 | 990k | } |
995 | | |
996 | | ZEND_API zval* ZEND_FASTCALL zend_hash_update(HashTable *ht, zend_string *key, zval *pData) |
997 | 2.03M | { |
998 | 2.03M | return _zend_hash_add_or_update_i(ht, key, pData, HASH_UPDATE); |
999 | 2.03M | } |
1000 | | |
1001 | | ZEND_API zval* ZEND_FASTCALL zend_hash_update_ind(HashTable *ht, zend_string *key, zval *pData) |
1002 | 8.70k | { |
1003 | 8.70k | return _zend_hash_add_or_update_i(ht, key, pData, HASH_UPDATE | HASH_UPDATE_INDIRECT); |
1004 | 8.70k | } |
1005 | | |
1006 | | ZEND_API zval* ZEND_FASTCALL zend_hash_add_new(HashTable *ht, zend_string *key, zval *pData) |
1007 | 2.62M | { |
1008 | 2.62M | return _zend_hash_add_or_update_i(ht, key, pData, HASH_ADD_NEW); |
1009 | 2.62M | } |
1010 | | |
1011 | | ZEND_API zval* ZEND_FASTCALL zend_hash_lookup(HashTable *ht, zend_string *key) |
1012 | 697k | { |
1013 | 697k | return _zend_hash_add_or_update_i(ht, key, NULL, HASH_LOOKUP); |
1014 | 697k | } |
1015 | | |
1016 | | ZEND_API zval* ZEND_FASTCALL zend_hash_str_add_or_update(HashTable *ht, const char *str, size_t len, zval *pData, uint32_t flag) |
1017 | 0 | { |
1018 | 0 | if (flag == HASH_ADD) { |
1019 | 0 | return zend_hash_str_add(ht, str, len, pData); |
1020 | 0 | } else if (flag == HASH_ADD_NEW) { |
1021 | 0 | return zend_hash_str_add_new(ht, str, len, pData); |
1022 | 0 | } else if (flag == HASH_UPDATE) { |
1023 | 0 | return zend_hash_str_update(ht, str, len, pData); |
1024 | 0 | } else { |
1025 | 0 | ZEND_ASSERT(flag == (HASH_UPDATE|HASH_UPDATE_INDIRECT)); |
1026 | 0 | return zend_hash_str_update_ind(ht, str, len, pData); |
1027 | 0 | } |
1028 | 0 | } |
1029 | | |
1030 | | ZEND_API zval* ZEND_FASTCALL zend_hash_str_update(HashTable *ht, const char *str, size_t len, zval *pData) |
1031 | 397k | { |
1032 | 397k | zend_ulong h = zend_hash_func(str, len); |
1033 | | |
1034 | 397k | return _zend_hash_str_add_or_update_i(ht, str, len, h, pData, HASH_UPDATE); |
1035 | 397k | } |
1036 | | |
1037 | | ZEND_API zval* ZEND_FASTCALL zend_hash_str_update_ind(HashTable *ht, const char *str, size_t len, zval *pData) |
1038 | 0 | { |
1039 | 0 | zend_ulong h = zend_hash_func(str, len); |
1040 | |
|
1041 | 0 | return _zend_hash_str_add_or_update_i(ht, str, len, h, pData, HASH_UPDATE | HASH_UPDATE_INDIRECT); |
1042 | 0 | } |
1043 | | |
1044 | | ZEND_API zval* ZEND_FASTCALL zend_hash_str_add(HashTable *ht, const char *str, size_t len, zval *pData) |
1045 | 7.46k | { |
1046 | 7.46k | zend_ulong h = zend_hash_func(str, len); |
1047 | | |
1048 | 7.46k | return _zend_hash_str_add_or_update_i(ht, str, len, h, pData, HASH_ADD); |
1049 | 7.46k | } |
1050 | | |
1051 | | ZEND_API zval* ZEND_FASTCALL zend_hash_str_add_new(HashTable *ht, const char *str, size_t len, zval *pData) |
1052 | 165 | { |
1053 | 165 | zend_ulong h = zend_hash_func(str, len); |
1054 | | |
1055 | 165 | return _zend_hash_str_add_or_update_i(ht, str, len, h, pData, HASH_ADD_NEW); |
1056 | 165 | } |
1057 | | |
1058 | | ZEND_API zval* ZEND_FASTCALL zend_hash_index_add_empty_element(HashTable *ht, zend_ulong h) |
1059 | 5.67k | { |
1060 | 5.67k | zval dummy; |
1061 | | |
1062 | 5.67k | ZVAL_NULL(&dummy); |
1063 | 5.67k | return zend_hash_index_add(ht, h, &dummy); |
1064 | 5.67k | } |
1065 | | |
1066 | | ZEND_API zval* ZEND_FASTCALL zend_hash_add_empty_element(HashTable *ht, zend_string *key) |
1067 | 610k | { |
1068 | 610k | zval dummy; |
1069 | | |
1070 | 610k | ZVAL_NULL(&dummy); |
1071 | 610k | return zend_hash_add(ht, key, &dummy); |
1072 | 610k | } |
1073 | | |
1074 | | ZEND_API zval* ZEND_FASTCALL zend_hash_str_add_empty_element(HashTable *ht, const char *str, size_t len) |
1075 | 0 | { |
1076 | 0 | zval dummy; |
1077 | |
|
1078 | 0 | ZVAL_NULL(&dummy); |
1079 | 0 | return zend_hash_str_add(ht, str, len, &dummy); |
1080 | 0 | } |
1081 | | |
1082 | | static zend_always_inline zval *_zend_hash_index_add_or_update_i(HashTable *ht, zend_ulong h, zval *pData, uint32_t flag) |
1083 | 1.48G | { |
1084 | 1.48G | uint32_t nIndex; |
1085 | 1.48G | uint32_t idx; |
1086 | 1.48G | Bucket *p; |
1087 | 1.48G | zval *zv; |
1088 | | |
1089 | 1.48G | IS_CONSISTENT(ht); |
1090 | 1.48G | HT_ASSERT_RC1(ht); |
1091 | | |
1092 | 1.48G | if ((flag & HASH_ADD_NEXT) && h == ZEND_LONG_MIN) { |
1093 | 2.19M | h = 0; |
1094 | 2.19M | } |
1095 | | |
1096 | 1.48G | if (HT_IS_PACKED(ht)) { |
1097 | 10.2M | if ((flag & (HASH_ADD_NEW|HASH_ADD_NEXT)) != (HASH_ADD_NEW|HASH_ADD_NEXT) |
1098 | 10.2M | && h < ht->nNumUsed) { |
1099 | 7.73k | zv = ht->arPacked + h; |
1100 | 7.73k | if (Z_TYPE_P(zv) != IS_UNDEF) { |
1101 | 4.86k | if (flag & HASH_LOOKUP) { |
1102 | 58 | return zv; |
1103 | 58 | } |
1104 | 13.9k | replace: |
1105 | 13.9k | if (flag & HASH_ADD) { |
1106 | 11.6k | return NULL; |
1107 | 11.6k | } |
1108 | 2.32k | if (ht->pDestructor) { |
1109 | 2.32k | ht->pDestructor(zv); |
1110 | 2.32k | } |
1111 | 2.32k | ZVAL_COPY_VALUE(zv, pData); |
1112 | 2.32k | return zv; |
1113 | 13.9k | } else { /* we have to keep the order :( */ |
1114 | 2.87k | goto convert_to_hash; |
1115 | 2.87k | } |
1116 | 10.2M | } else if (EXPECTED(h < ht->nTableSize)) { |
1117 | 12.5M | add_to_packed: |
1118 | 12.5M | zv = ht->arPacked + h; |
1119 | | /* incremental initialization of empty Buckets */ |
1120 | 12.5M | if ((flag & (HASH_ADD_NEW|HASH_ADD_NEXT)) != (HASH_ADD_NEW|HASH_ADD_NEXT)) { |
1121 | 8.89M | if (h > ht->nNumUsed) { |
1122 | 62.4k | zval *q = ht->arPacked + ht->nNumUsed; |
1123 | 226k | while (q != zv) { |
1124 | 163k | ZVAL_UNDEF(q); |
1125 | 163k | q++; |
1126 | 163k | } |
1127 | 62.4k | } |
1128 | 8.89M | } |
1129 | 12.5M | ht->nNextFreeElement = ht->nNumUsed = h + 1; |
1130 | 12.5M | ht->nNumOfElements++; |
1131 | 12.5M | if (flag & HASH_LOOKUP) { |
1132 | 11.3k | ZVAL_NULL(zv); |
1133 | 12.5M | } else { |
1134 | 12.5M | ZVAL_COPY_VALUE(zv, pData); |
1135 | 12.5M | } |
1136 | | |
1137 | 12.5M | return zv; |
1138 | 10.1M | } else if ((h >> 1) < ht->nTableSize && |
1139 | 129k | (ht->nTableSize >> 1) < ht->nNumOfElements) { |
1140 | 124k | zend_hash_packed_grow(ht); |
1141 | 124k | goto add_to_packed; |
1142 | 124k | } else { |
1143 | 5.10k | if (ht->nNumUsed >= ht->nTableSize) { |
1144 | 1.00k | ht->nTableSize += ht->nTableSize; |
1145 | 1.00k | } |
1146 | 7.97k | convert_to_hash: |
1147 | 7.97k | zend_hash_packed_to_hash(ht); |
1148 | 7.97k | } |
1149 | 1.47G | } else if (HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED) { |
1150 | 2.37M | if (h < ht->nTableSize) { |
1151 | 2.27M | zend_hash_real_init_packed_ex(ht); |
1152 | 2.27M | goto add_to_packed; |
1153 | 2.27M | } |
1154 | 92.5k | zend_hash_real_init_mixed(ht); |
1155 | 1.47G | } else { |
1156 | 1.47G | if ((flag & HASH_ADD_NEW) == 0 || ZEND_DEBUG) { |
1157 | 1.47G | p = zend_hash_index_find_bucket(ht, h); |
1158 | 1.47G | if (p) { |
1159 | 308k | if (flag & HASH_LOOKUP) { |
1160 | 299k | return &p->val; |
1161 | 299k | } |
1162 | 9.18k | ZEND_ASSERT((flag & HASH_ADD_NEW) == 0); |
1163 | 9.18k | zv = &p->val; |
1164 | 9.18k | goto replace; |
1165 | 9.18k | } |
1166 | 1.47G | } |
1167 | 1.47G | ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */ |
1168 | 1.47G | } |
1169 | | |
1170 | 1.47G | idx = ht->nNumUsed++; |
1171 | 1.47G | nIndex = h | ht->nTableMask; |
1172 | 1.47G | p = ht->arData + idx; |
1173 | 1.47G | Z_NEXT(p->val) = HT_HASH(ht, nIndex); |
1174 | 1.47G | HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx); |
1175 | 1.47G | if ((zend_long)h >= ht->nNextFreeElement) { |
1176 | 5.03M | ht->nNextFreeElement = (zend_long)h < ZEND_LONG_MAX ? h + 1 : ZEND_LONG_MAX; |
1177 | 5.03M | } |
1178 | 1.47G | ht->nNumOfElements++; |
1179 | 1.47G | p->h = h; |
1180 | 1.47G | p->key = NULL; |
1181 | 1.47G | if (flag & HASH_LOOKUP) { |
1182 | 1.30M | ZVAL_NULL(&p->val); |
1183 | 1.46G | } else { |
1184 | 1.46G | ZVAL_COPY_VALUE(&p->val, pData); |
1185 | 1.46G | } |
1186 | | |
1187 | 1.47G | return &p->val; |
1188 | 1.48G | } |
1189 | | |
1190 | | ZEND_API zval* ZEND_FASTCALL zend_hash_index_add_or_update(HashTable *ht, zend_ulong h, zval *pData, uint32_t flag) |
1191 | 0 | { |
1192 | 0 | if (flag == HASH_ADD) { |
1193 | 0 | return zend_hash_index_add(ht, h, pData); |
1194 | 0 | } else if (flag == (HASH_ADD|HASH_ADD_NEW)) { |
1195 | 0 | return zend_hash_index_add_new(ht, h, pData); |
1196 | 0 | } else if (flag == (HASH_ADD|HASH_ADD_NEXT)) { |
1197 | 0 | ZEND_ASSERT(h == ht->nNextFreeElement); |
1198 | 0 | return zend_hash_next_index_insert(ht, pData); |
1199 | 0 | } else if (flag == (HASH_ADD|HASH_ADD_NEW|HASH_ADD_NEXT)) { |
1200 | 0 | ZEND_ASSERT(h == ht->nNextFreeElement); |
1201 | 0 | return zend_hash_next_index_insert_new(ht, pData); |
1202 | 0 | } else { |
1203 | 0 | ZEND_ASSERT(flag == HASH_UPDATE); |
1204 | 0 | return zend_hash_index_update(ht, h, pData); |
1205 | 0 | } |
1206 | 0 | } |
1207 | | |
1208 | | ZEND_API zval* ZEND_FASTCALL zend_hash_index_add(HashTable *ht, zend_ulong h, zval *pData) |
1209 | 27.3k | { |
1210 | 27.3k | return _zend_hash_index_add_or_update_i(ht, h, pData, HASH_ADD); |
1211 | 27.3k | } |
1212 | | |
1213 | | ZEND_API zval* ZEND_FASTCALL zend_hash_index_add_new(HashTable *ht, zend_ulong h, zval *pData) |
1214 | 1.46G | { |
1215 | 1.46G | return _zend_hash_index_add_or_update_i(ht, h, pData, HASH_ADD | HASH_ADD_NEW); |
1216 | 1.46G | } |
1217 | | |
1218 | | ZEND_API zval* ZEND_FASTCALL zend_hash_index_update(HashTable *ht, zend_ulong h, zval *pData) |
1219 | 4.28M | { |
1220 | 4.28M | return _zend_hash_index_add_or_update_i(ht, h, pData, HASH_UPDATE); |
1221 | 4.28M | } |
1222 | | |
1223 | | ZEND_API zval* ZEND_FASTCALL zend_hash_next_index_insert(HashTable *ht, zval *pData) |
1224 | 5.01M | { |
1225 | 5.01M | return _zend_hash_index_add_or_update_i(ht, ht->nNextFreeElement, pData, HASH_ADD | HASH_ADD_NEXT); |
1226 | 5.01M | } |
1227 | | |
1228 | | ZEND_API zval* ZEND_FASTCALL zend_hash_next_index_insert_new(HashTable *ht, zval *pData) |
1229 | 3.65M | { |
1230 | 3.65M | return _zend_hash_index_add_or_update_i(ht, ht->nNextFreeElement, pData, HASH_ADD | HASH_ADD_NEW | HASH_ADD_NEXT); |
1231 | 3.65M | } |
1232 | | |
1233 | | ZEND_API zval* ZEND_FASTCALL zend_hash_index_lookup(HashTable *ht, zend_ulong h) |
1234 | 1.61M | { |
1235 | 1.61M | return _zend_hash_index_add_or_update_i(ht, h, NULL, HASH_LOOKUP); |
1236 | 1.61M | } |
1237 | | |
1238 | | ZEND_API zval* ZEND_FASTCALL zend_hash_set_bucket_key(HashTable *ht, Bucket *b, zend_string *key) |
1239 | 6.80k | { |
1240 | 6.80k | uint32_t nIndex; |
1241 | 6.80k | uint32_t idx, i; |
1242 | 6.80k | Bucket *p, *arData; |
1243 | | |
1244 | 6.80k | IS_CONSISTENT(ht); |
1245 | 6.80k | HT_ASSERT_RC1(ht); |
1246 | 6.80k | ZEND_ASSERT(!HT_IS_PACKED(ht)); |
1247 | | |
1248 | 6.80k | (void)zend_string_hash_val(key); |
1249 | 6.80k | p = zend_hash_find_bucket(ht, key); |
1250 | 6.80k | if (UNEXPECTED(p)) { |
1251 | 133 | return (p == b) ? &p->val : NULL; |
1252 | 133 | } |
1253 | | |
1254 | 6.67k | if (!ZSTR_IS_INTERNED(key)) { |
1255 | 21 | zend_string_addref(key); |
1256 | 21 | HT_FLAGS(ht) &= ~HASH_FLAG_STATIC_KEYS; |
1257 | 21 | } |
1258 | | |
1259 | 6.67k | arData = ht->arData; |
1260 | | |
1261 | | /* del from hash */ |
1262 | 6.67k | idx = HT_IDX_TO_HASH(b - arData); |
1263 | 6.67k | nIndex = b->h | ht->nTableMask; |
1264 | 6.67k | i = HT_HASH_EX(arData, nIndex); |
1265 | 6.67k | if (i == idx) { |
1266 | 6.66k | HT_HASH_EX(arData, nIndex) = Z_NEXT(b->val); |
1267 | 6.66k | } else { |
1268 | 5 | p = HT_HASH_TO_BUCKET_EX(arData, i); |
1269 | 5 | while (Z_NEXT(p->val) != idx) { |
1270 | 0 | i = Z_NEXT(p->val); |
1271 | 0 | p = HT_HASH_TO_BUCKET_EX(arData, i); |
1272 | 0 | } |
1273 | 5 | Z_NEXT(p->val) = Z_NEXT(b->val); |
1274 | 5 | } |
1275 | 6.67k | zend_string_release(b->key); |
1276 | | |
1277 | | /* add to hash */ |
1278 | 6.67k | idx = b - arData; |
1279 | 6.67k | b->key = key; |
1280 | 6.67k | b->h = ZSTR_H(key); |
1281 | 6.67k | nIndex = b->h | ht->nTableMask; |
1282 | 6.67k | idx = HT_IDX_TO_HASH(idx); |
1283 | 6.67k | i = HT_HASH_EX(arData, nIndex); |
1284 | 6.67k | if (i == HT_INVALID_IDX || i < idx) { |
1285 | 6.66k | Z_NEXT(b->val) = i; |
1286 | 6.66k | HT_HASH_EX(arData, nIndex) = idx; |
1287 | 6.66k | } else { |
1288 | 5 | p = HT_HASH_TO_BUCKET_EX(arData, i); |
1289 | 5 | while (Z_NEXT(p->val) != HT_INVALID_IDX && Z_NEXT(p->val) > idx) { |
1290 | 0 | i = Z_NEXT(p->val); |
1291 | 0 | p = HT_HASH_TO_BUCKET_EX(arData, i); |
1292 | 0 | } |
1293 | 5 | Z_NEXT(b->val) = Z_NEXT(p->val); |
1294 | 5 | Z_NEXT(p->val) = idx; |
1295 | 5 | } |
1296 | 6.67k | return &b->val; |
1297 | 6.80k | } |
1298 | | |
1299 | | static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht) |
1300 | 81.8k | { |
1301 | | |
1302 | 81.8k | IS_CONSISTENT(ht); |
1303 | 81.8k | HT_ASSERT_RC1(ht); |
1304 | | |
1305 | 81.8k | ZEND_ASSERT(!HT_IS_PACKED(ht)); |
1306 | 81.8k | if (ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)) { /* additional term is there to amortize the cost of compaction */ |
1307 | 59.1k | zend_hash_rehash(ht); |
1308 | 59.1k | } else if (ht->nTableSize < HT_MAX_SIZE) { /* Let's double the table size */ |
1309 | 22.6k | void *new_data, *old_data = HT_GET_DATA_ADDR(ht); |
1310 | 22.6k | uint32_t nSize = ht->nTableSize + ht->nTableSize; |
1311 | 22.6k | Bucket *old_buckets = ht->arData; |
1312 | | |
1313 | 22.6k | ZEND_ASSERT(HT_SIZE_TO_MASK(nSize)); |
1314 | | |
1315 | 22.6k | new_data = pemalloc(HT_SIZE_EX(nSize, HT_SIZE_TO_MASK(nSize)), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT); |
1316 | 22.6k | ht->nTableSize = nSize; |
1317 | 22.6k | ht->nTableMask = HT_SIZE_TO_MASK(ht->nTableSize); |
1318 | 22.6k | HT_SET_DATA_ADDR(ht, new_data); |
1319 | 22.6k | memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed); |
1320 | 22.6k | pefree(old_data, GC_FLAGS(ht) & IS_ARRAY_PERSISTENT); |
1321 | 22.6k | zend_hash_rehash(ht); |
1322 | 22.6k | } else { |
1323 | 0 | zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%u * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket) + sizeof(uint32_t), sizeof(Bucket)); |
1324 | 0 | } |
1325 | 81.8k | } |
1326 | | |
1327 | | ZEND_API void ZEND_FASTCALL zend_hash_rehash(HashTable *ht) |
1328 | 391k | { |
1329 | 391k | Bucket *p; |
1330 | 391k | uint32_t nIndex, i; |
1331 | | |
1332 | 391k | IS_CONSISTENT(ht); |
1333 | | |
1334 | 391k | if (UNEXPECTED(ht->nNumOfElements == 0)) { |
1335 | 18 | if (!(HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED)) { |
1336 | 18 | ht->nNumUsed = 0; |
1337 | 18 | HT_HASH_RESET(ht); |
1338 | | /* Even if the array is empty, we still need to reset the iterator positions. */ |
1339 | 18 | ht->nInternalPointer = 0; |
1340 | 18 | if (UNEXPECTED(HT_HAS_ITERATORS(ht))) { |
1341 | 7 | HashTableIterator *iter = EG(ht_iterators); |
1342 | 7 | HashTableIterator *end = iter + EG(ht_iterators_used); |
1343 | 14 | while (iter != end) { |
1344 | 7 | if (iter->ht == ht) { |
1345 | 7 | iter->pos = 0; |
1346 | 7 | } |
1347 | 7 | iter++; |
1348 | 7 | } |
1349 | 7 | } |
1350 | 18 | } |
1351 | 18 | return; |
1352 | 18 | } |
1353 | | |
1354 | 391k | HT_HASH_RESET(ht); |
1355 | 391k | i = 0; |
1356 | 391k | p = ht->arData; |
1357 | 391k | if (HT_IS_WITHOUT_HOLES(ht)) { |
1358 | 1.98M | do { |
1359 | 1.98M | nIndex = p->h | ht->nTableMask; |
1360 | 1.98M | Z_NEXT(p->val) = HT_HASH(ht, nIndex); |
1361 | 1.98M | HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i); |
1362 | 1.98M | p++; |
1363 | 1.98M | } while (++i < ht->nNumUsed); |
1364 | 323k | } else { |
1365 | 67.9k | uint32_t old_num_used = ht->nNumUsed; |
1366 | 11.6M | do { |
1367 | 11.6M | if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) { |
1368 | 67.9k | uint32_t j = i; |
1369 | 67.9k | Bucket *q = p; |
1370 | | |
1371 | 67.9k | if (EXPECTED(!HT_HAS_ITERATORS(ht))) { |
1372 | 1.16G | while (++i < ht->nNumUsed) { |
1373 | 1.16G | p++; |
1374 | 1.16G | if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) { |
1375 | 271M | ZVAL_COPY_VALUE(&q->val, &p->val); |
1376 | 271M | q->h = p->h; |
1377 | 271M | nIndex = q->h | ht->nTableMask; |
1378 | 271M | q->key = p->key; |
1379 | 271M | Z_NEXT(q->val) = HT_HASH(ht, nIndex); |
1380 | 271M | HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j); |
1381 | 271M | if (UNEXPECTED(ht->nInternalPointer == i)) { |
1382 | 0 | ht->nInternalPointer = j; |
1383 | 0 | } |
1384 | 271M | q++; |
1385 | 271M | j++; |
1386 | 271M | } |
1387 | 1.16G | } |
1388 | 67.9k | } else { |
1389 | 38 | uint32_t iter_pos = zend_hash_iterators_lower_pos(ht, i + 1); |
1390 | | |
1391 | 216 | while (++i < ht->nNumUsed) { |
1392 | 178 | p++; |
1393 | 178 | if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) { |
1394 | 104 | ZVAL_COPY_VALUE(&q->val, &p->val); |
1395 | 104 | q->h = p->h; |
1396 | 104 | nIndex = q->h | ht->nTableMask; |
1397 | 104 | q->key = p->key; |
1398 | 104 | Z_NEXT(q->val) = HT_HASH(ht, nIndex); |
1399 | 104 | HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j); |
1400 | 104 | if (UNEXPECTED(ht->nInternalPointer == i)) { |
1401 | 0 | ht->nInternalPointer = j; |
1402 | 0 | } |
1403 | 104 | if (UNEXPECTED(i >= iter_pos)) { |
1404 | 34 | do { |
1405 | 34 | zend_hash_iterators_update(ht, iter_pos, j); |
1406 | 34 | iter_pos = zend_hash_iterators_lower_pos(ht, iter_pos + 1); |
1407 | 34 | } while (iter_pos < i); |
1408 | 34 | } |
1409 | 104 | q++; |
1410 | 104 | j++; |
1411 | 104 | } |
1412 | 178 | } |
1413 | 38 | } |
1414 | 67.9k | ht->nNumUsed = j; |
1415 | 67.9k | break; |
1416 | 67.9k | } |
1417 | 11.5M | nIndex = p->h | ht->nTableMask; |
1418 | 11.5M | Z_NEXT(p->val) = HT_HASH(ht, nIndex); |
1419 | 11.5M | HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i); |
1420 | 11.5M | p++; |
1421 | 11.5M | } while (++i < ht->nNumUsed); |
1422 | | |
1423 | | /* Migrate pointer to one past the end of the array to the new one past the end, so that |
1424 | | * newly inserted elements are picked up correctly. */ |
1425 | 67.9k | if (UNEXPECTED(HT_HAS_ITERATORS(ht))) { |
1426 | 38 | _zend_hash_iterators_update(ht, old_num_used, ht->nNumUsed); |
1427 | 38 | } |
1428 | 67.9k | } |
1429 | 391k | } |
1430 | | |
1431 | | static zend_always_inline void zend_hash_iterators_clamp_max(const HashTable *ht, uint32_t max) |
1432 | 50.4M | { |
1433 | 50.4M | if (UNEXPECTED(HT_HAS_ITERATORS(ht))) { |
1434 | 507 | HashTableIterator *iter = EG(ht_iterators); |
1435 | 507 | const HashTableIterator *end = iter + EG(ht_iterators_used); |
1436 | 1.02k | while (iter != end) { |
1437 | 517 | if (iter->ht == ht) { |
1438 | 507 | iter->pos = MIN(iter->pos, max); |
1439 | 507 | } |
1440 | 517 | iter++; |
1441 | 517 | } |
1442 | 507 | } |
1443 | 50.4M | } |
1444 | | |
1445 | | static zend_always_inline void _zend_hash_packed_del_val(HashTable *ht, uint32_t idx, zval *zv) |
1446 | 10.1k | { |
1447 | 10.1k | idx = HT_HASH_TO_IDX(idx); |
1448 | 10.1k | ht->nNumOfElements--; |
1449 | 10.1k | if (ht->nNumUsed - 1 == idx) { |
1450 | 21.6k | do { |
1451 | 21.6k | ht->nNumUsed--; |
1452 | 21.6k | } while (ht->nNumUsed > 0 && (UNEXPECTED(Z_TYPE(ht->arPacked[ht->nNumUsed-1]) == IS_UNDEF))); |
1453 | 8.96k | ht->nInternalPointer = MIN(ht->nInternalPointer, ht->nNumUsed); |
1454 | 8.96k | zend_hash_iterators_clamp_max(ht, ht->nNumUsed); |
1455 | 8.96k | } |
1456 | 10.1k | if (ht->pDestructor) { |
1457 | 10.1k | zval tmp; |
1458 | 10.1k | ZVAL_COPY_VALUE(&tmp, zv); |
1459 | 10.1k | ZVAL_UNDEF(zv); |
1460 | 10.1k | ht->pDestructor(&tmp); |
1461 | 10.1k | } else { |
1462 | 0 | ZVAL_UNDEF(zv); |
1463 | 0 | } |
1464 | 10.1k | } |
1465 | | |
1466 | | static zend_always_inline void _zend_hash_del_el_ex(HashTable *ht, uint32_t idx, Bucket *p, Bucket *prev) |
1467 | 1.46G | { |
1468 | 1.46G | if (prev) { |
1469 | 119M | Z_NEXT(prev->val) = Z_NEXT(p->val); |
1470 | 1.34G | } else { |
1471 | 1.34G | HT_HASH(ht, p->h | ht->nTableMask) = Z_NEXT(p->val); |
1472 | 1.34G | } |
1473 | 1.46G | idx = HT_HASH_TO_IDX(idx); |
1474 | 1.46G | ht->nNumOfElements--; |
1475 | 1.46G | if (ht->nNumUsed - 1 == idx) { |
1476 | 227M | do { |
1477 | 227M | ht->nNumUsed--; |
1478 | 227M | } while (ht->nNumUsed > 0 && (UNEXPECTED(Z_TYPE(ht->arData[ht->nNumUsed-1].val) == IS_UNDEF))); |
1479 | 50.4M | ht->nInternalPointer = MIN(ht->nInternalPointer, ht->nNumUsed); |
1480 | 50.4M | zend_hash_iterators_clamp_max(ht, ht->nNumUsed); |
1481 | 50.4M | } |
1482 | 1.46G | if (ht->pDestructor) { |
1483 | 1.66M | zval tmp; |
1484 | 1.66M | ZVAL_COPY_VALUE(&tmp, &p->val); |
1485 | 1.66M | ZVAL_UNDEF(&p->val); |
1486 | 1.66M | ht->pDestructor(&tmp); |
1487 | 1.46G | } else { |
1488 | 1.46G | ZVAL_UNDEF(&p->val); |
1489 | 1.46G | } |
1490 | 1.46G | } |
1491 | | |
1492 | | static zend_always_inline void _zend_hash_del_el(HashTable *ht, uint32_t idx, Bucket *p) |
1493 | 1.46G | { |
1494 | 1.46G | Bucket *prev = NULL; |
1495 | 1.46G | uint32_t nIndex; |
1496 | 1.46G | uint32_t i; |
1497 | | |
1498 | 1.46G | nIndex = p->h | ht->nTableMask; |
1499 | 1.46G | i = HT_HASH(ht, nIndex); |
1500 | | |
1501 | 1.46G | if (i != idx) { |
1502 | 119M | prev = HT_HASH_TO_BUCKET(ht, i); |
1503 | 130M | while (Z_NEXT(prev->val) != idx) { |
1504 | 10.4M | i = Z_NEXT(prev->val); |
1505 | 10.4M | prev = HT_HASH_TO_BUCKET(ht, i); |
1506 | 10.4M | } |
1507 | 119M | } |
1508 | | |
1509 | 1.46G | if (p->key) { |
1510 | 1.63M | zend_string_release(p->key); |
1511 | 1.63M | p->key = NULL; |
1512 | 1.63M | } |
1513 | 1.46G | _zend_hash_del_el_ex(ht, idx, p, prev); |
1514 | 1.46G | } |
1515 | | |
1516 | | ZEND_API void ZEND_FASTCALL zend_hash_packed_del_val(HashTable *ht, zval *zv) |
1517 | 1.41k | { |
1518 | 1.41k | IS_CONSISTENT(ht); |
1519 | 1.41k | HT_ASSERT_RC1(ht); |
1520 | 1.41k | ZEND_ASSERT(HT_IS_PACKED(ht)); |
1521 | 1.41k | _zend_hash_packed_del_val(ht, HT_IDX_TO_HASH(zv - ht->arPacked), zv); |
1522 | 1.41k | } |
1523 | | |
1524 | | |
1525 | | ZEND_API void ZEND_FASTCALL zend_hash_del_bucket(HashTable *ht, Bucket *p) |
1526 | 1.46G | { |
1527 | 1.46G | IS_CONSISTENT(ht); |
1528 | 1.46G | HT_ASSERT_RC1(ht); |
1529 | 1.46G | ZEND_ASSERT(!HT_IS_PACKED(ht)); |
1530 | 1.46G | _zend_hash_del_el(ht, HT_IDX_TO_HASH(p - ht->arData), p); |
1531 | 1.46G | } |
1532 | | |
1533 | | ZEND_API zend_result ZEND_FASTCALL zend_hash_del(HashTable *ht, zend_string *key) |
1534 | 318k | { |
1535 | 318k | zend_ulong h; |
1536 | 318k | uint32_t nIndex; |
1537 | 318k | uint32_t idx; |
1538 | 318k | Bucket *p; |
1539 | 318k | Bucket *prev = NULL; |
1540 | | |
1541 | 318k | IS_CONSISTENT(ht); |
1542 | 318k | HT_ASSERT_RC1(ht); |
1543 | | |
1544 | 318k | h = zend_string_hash_val(key); |
1545 | 318k | nIndex = h | ht->nTableMask; |
1546 | | |
1547 | 318k | idx = HT_HASH(ht, nIndex); |
1548 | 322k | while (idx != HT_INVALID_IDX) { |
1549 | 311k | p = HT_HASH_TO_BUCKET(ht, idx); |
1550 | 311k | if ((p->key == key) || |
1551 | 311k | (p->h == h && |
1552 | 4.96k | p->key && |
1553 | 307k | zend_string_equal_content(p->key, key))) { |
1554 | 307k | zend_string_release(p->key); |
1555 | 307k | p->key = NULL; |
1556 | 307k | _zend_hash_del_el_ex(ht, idx, p, prev); |
1557 | 307k | return SUCCESS; |
1558 | 307k | } |
1559 | 4.21k | prev = p; |
1560 | 4.21k | idx = Z_NEXT(p->val); |
1561 | 4.21k | } |
1562 | 10.5k | return FAILURE; |
1563 | 318k | } |
1564 | | |
1565 | | ZEND_API zend_result ZEND_FASTCALL zend_hash_del_ind(HashTable *ht, zend_string *key) |
1566 | 419 | { |
1567 | 419 | zend_ulong h; |
1568 | 419 | uint32_t nIndex; |
1569 | 419 | uint32_t idx; |
1570 | 419 | Bucket *p; |
1571 | 419 | Bucket *prev = NULL; |
1572 | | |
1573 | 419 | IS_CONSISTENT(ht); |
1574 | 419 | HT_ASSERT_RC1(ht); |
1575 | | |
1576 | 419 | h = zend_string_hash_val(key); |
1577 | 419 | nIndex = h | ht->nTableMask; |
1578 | | |
1579 | 419 | idx = HT_HASH(ht, nIndex); |
1580 | 421 | while (idx != HT_INVALID_IDX) { |
1581 | 373 | p = HT_HASH_TO_BUCKET(ht, idx); |
1582 | 373 | if ((p->key == key) || |
1583 | 373 | (p->h == h && |
1584 | 2 | p->key && |
1585 | 371 | zend_string_equal_content(p->key, key))) { |
1586 | 371 | if (Z_TYPE(p->val) == IS_INDIRECT) { |
1587 | 297 | zval *data = Z_INDIRECT(p->val); |
1588 | | |
1589 | 297 | if (UNEXPECTED(Z_TYPE_P(data) == IS_UNDEF)) { |
1590 | 41 | return FAILURE; |
1591 | 256 | } else { |
1592 | 256 | if (ht->pDestructor) { |
1593 | 256 | zval tmp; |
1594 | 256 | ZVAL_COPY_VALUE(&tmp, data); |
1595 | 256 | ZVAL_UNDEF(data); |
1596 | 256 | ht->pDestructor(&tmp); |
1597 | 256 | } else { |
1598 | 0 | ZVAL_UNDEF(data); |
1599 | 0 | } |
1600 | 256 | HT_FLAGS(ht) |= HASH_FLAG_HAS_EMPTY_IND; |
1601 | 256 | } |
1602 | 297 | } else { |
1603 | 74 | zend_string_release(p->key); |
1604 | 74 | p->key = NULL; |
1605 | 74 | _zend_hash_del_el_ex(ht, idx, p, prev); |
1606 | 74 | } |
1607 | 330 | return SUCCESS; |
1608 | 371 | } |
1609 | 2 | prev = p; |
1610 | 2 | idx = Z_NEXT(p->val); |
1611 | 2 | } |
1612 | 48 | return FAILURE; |
1613 | 419 | } |
1614 | | |
1615 | | ZEND_API zend_result ZEND_FASTCALL zend_hash_str_del_ind(HashTable *ht, const char *str, size_t len) |
1616 | 0 | { |
1617 | 0 | zend_ulong h; |
1618 | 0 | uint32_t nIndex; |
1619 | 0 | uint32_t idx; |
1620 | 0 | Bucket *p; |
1621 | 0 | Bucket *prev = NULL; |
1622 | |
|
1623 | 0 | IS_CONSISTENT(ht); |
1624 | 0 | HT_ASSERT_RC1(ht); |
1625 | | |
1626 | 0 | h = zend_inline_hash_func(str, len); |
1627 | 0 | nIndex = h | ht->nTableMask; |
1628 | |
|
1629 | 0 | idx = HT_HASH(ht, nIndex); |
1630 | 0 | while (idx != HT_INVALID_IDX) { |
1631 | 0 | p = HT_HASH_TO_BUCKET(ht, idx); |
1632 | 0 | if ((p->h == h) |
1633 | 0 | && p->key |
1634 | 0 | && zend_string_equals_cstr(p->key, str, len)) { |
1635 | 0 | if (Z_TYPE(p->val) == IS_INDIRECT) { |
1636 | 0 | zval *data = Z_INDIRECT(p->val); |
1637 | |
|
1638 | 0 | if (UNEXPECTED(Z_TYPE_P(data) == IS_UNDEF)) { |
1639 | 0 | return FAILURE; |
1640 | 0 | } else { |
1641 | 0 | if (ht->pDestructor) { |
1642 | 0 | ht->pDestructor(data); |
1643 | 0 | } |
1644 | 0 | ZVAL_UNDEF(data); |
1645 | 0 | HT_FLAGS(ht) |= HASH_FLAG_HAS_EMPTY_IND; |
1646 | 0 | } |
1647 | 0 | } else { |
1648 | 0 | zend_string_release(p->key); |
1649 | 0 | p->key = NULL; |
1650 | 0 | _zend_hash_del_el_ex(ht, idx, p, prev); |
1651 | 0 | } |
1652 | 0 | return SUCCESS; |
1653 | 0 | } |
1654 | 0 | prev = p; |
1655 | 0 | idx = Z_NEXT(p->val); |
1656 | 0 | } |
1657 | 0 | return FAILURE; |
1658 | 0 | } |
1659 | | |
1660 | | ZEND_API zend_result ZEND_FASTCALL zend_hash_str_del(HashTable *ht, const char *str, size_t len) |
1661 | 579 | { |
1662 | 579 | zend_ulong h; |
1663 | 579 | uint32_t nIndex; |
1664 | 579 | uint32_t idx; |
1665 | 579 | Bucket *p; |
1666 | 579 | Bucket *prev = NULL; |
1667 | | |
1668 | 579 | IS_CONSISTENT(ht); |
1669 | 579 | HT_ASSERT_RC1(ht); |
1670 | | |
1671 | 579 | h = zend_inline_hash_func(str, len); |
1672 | 579 | nIndex = h | ht->nTableMask; |
1673 | | |
1674 | 579 | idx = HT_HASH(ht, nIndex); |
1675 | 675 | while (idx != HT_INVALID_IDX) { |
1676 | 611 | p = HT_HASH_TO_BUCKET(ht, idx); |
1677 | 611 | if ((p->h == h) |
1678 | 611 | && p->key |
1679 | 611 | && zend_string_equals_cstr(p->key, str, len)) { |
1680 | 515 | zend_string_release(p->key); |
1681 | 515 | p->key = NULL; |
1682 | 515 | _zend_hash_del_el_ex(ht, idx, p, prev); |
1683 | 515 | return SUCCESS; |
1684 | 515 | } |
1685 | 96 | prev = p; |
1686 | 96 | idx = Z_NEXT(p->val); |
1687 | 96 | } |
1688 | 64 | return FAILURE; |
1689 | 579 | } |
1690 | | |
1691 | | ZEND_API zend_result ZEND_FASTCALL zend_hash_index_del(HashTable *ht, zend_ulong h) |
1692 | 238k | { |
1693 | 238k | uint32_t nIndex; |
1694 | 238k | uint32_t idx; |
1695 | 238k | Bucket *p; |
1696 | 238k | Bucket *prev = NULL; |
1697 | | |
1698 | 238k | IS_CONSISTENT(ht); |
1699 | 238k | HT_ASSERT_RC1(ht); |
1700 | | |
1701 | 238k | if (HT_IS_PACKED(ht)) { |
1702 | 8.69k | if (h < ht->nNumUsed) { |
1703 | 8.64k | zval *zv = ht->arPacked + h; |
1704 | 8.64k | if (Z_TYPE_P(zv) != IS_UNDEF) { |
1705 | 8.63k | _zend_hash_packed_del_val(ht, HT_IDX_TO_HASH(h), zv); |
1706 | 8.63k | return SUCCESS; |
1707 | 8.63k | } |
1708 | 8.64k | } |
1709 | 57 | return FAILURE; |
1710 | 8.69k | } |
1711 | 229k | nIndex = h | ht->nTableMask; |
1712 | | |
1713 | 229k | idx = HT_HASH(ht, nIndex); |
1714 | 1.00M | while (idx != HT_INVALID_IDX) { |
1715 | 860k | p = HT_HASH_TO_BUCKET(ht, idx); |
1716 | 860k | if ((p->h == h) && (p->key == NULL)) { |
1717 | 84.1k | _zend_hash_del_el_ex(ht, idx, p, prev); |
1718 | 84.1k | return SUCCESS; |
1719 | 84.1k | } |
1720 | 776k | prev = p; |
1721 | 776k | idx = Z_NEXT(p->val); |
1722 | 776k | } |
1723 | 145k | return FAILURE; |
1724 | 229k | } |
1725 | | |
1726 | | ZEND_API void ZEND_FASTCALL zend_hash_destroy(HashTable *ht) |
1727 | 2.13M | { |
1728 | 2.13M | IS_CONSISTENT(ht); |
1729 | 2.13M | HT_ASSERT(ht, GC_REFCOUNT(ht) <= 1); |
1730 | | |
1731 | 2.13M | if (ht->nNumUsed) { |
1732 | 350k | if (HT_IS_PACKED(ht)) { |
1733 | 10.7k | if (ht->pDestructor) { |
1734 | 10.0k | zval *zv = ht->arPacked; |
1735 | 10.0k | zval *end = zv + ht->nNumUsed; |
1736 | | |
1737 | 10.0k | SET_INCONSISTENT(HT_IS_DESTROYING); |
1738 | 10.0k | if (HT_IS_WITHOUT_HOLES(ht)) { |
1739 | 31.0k | do { |
1740 | 31.0k | ht->pDestructor(zv); |
1741 | 31.0k | } while (++zv != end); |
1742 | 9.26k | } else { |
1743 | 3.18k | do { |
1744 | 3.18k | if (EXPECTED(Z_TYPE_P(zv) != IS_UNDEF)) { |
1745 | 1.00k | ht->pDestructor(zv); |
1746 | 1.00k | } |
1747 | 3.18k | } while (++zv != end); |
1748 | 807 | } |
1749 | 10.0k | SET_INCONSISTENT(HT_DESTROYED); |
1750 | 10.0k | } |
1751 | 10.7k | zend_hash_iterators_remove(ht); |
1752 | 339k | } else { |
1753 | 339k | Bucket *p = ht->arData; |
1754 | 339k | Bucket *end = p + ht->nNumUsed; |
1755 | | |
1756 | 339k | if (ht->pDestructor) { |
1757 | 134k | SET_INCONSISTENT(HT_IS_DESTROYING); |
1758 | | |
1759 | 134k | if (HT_HAS_STATIC_KEYS_ONLY(ht)) { |
1760 | 124k | if (HT_IS_WITHOUT_HOLES(ht)) { |
1761 | 487k | do { |
1762 | 487k | ht->pDestructor(&p->val); |
1763 | 487k | } while (++p != end); |
1764 | 124k | } else { |
1765 | 108 | do { |
1766 | 108 | if (EXPECTED(Z_TYPE(p->val) != IS_UNDEF)) { |
1767 | 83 | ht->pDestructor(&p->val); |
1768 | 83 | } |
1769 | 108 | } while (++p != end); |
1770 | 20 | } |
1771 | 124k | } else if (HT_IS_WITHOUT_HOLES(ht)) { |
1772 | 19.5k | do { |
1773 | 19.5k | ht->pDestructor(&p->val); |
1774 | 19.5k | if (EXPECTED(p->key)) { |
1775 | 17.7k | zend_string_release(p->key); |
1776 | 17.7k | } |
1777 | 19.5k | } while (++p != end); |
1778 | 9.80k | } else { |
1779 | 0 | do { |
1780 | 0 | if (EXPECTED(Z_TYPE(p->val) != IS_UNDEF)) { |
1781 | 0 | ht->pDestructor(&p->val); |
1782 | 0 | if (EXPECTED(p->key)) { |
1783 | 0 | zend_string_release(p->key); |
1784 | 0 | } |
1785 | 0 | } |
1786 | 0 | } while (++p != end); |
1787 | 0 | } |
1788 | | |
1789 | 134k | SET_INCONSISTENT(HT_DESTROYED); |
1790 | 205k | } else { |
1791 | 205k | if (!HT_HAS_STATIC_KEYS_ONLY(ht)) { |
1792 | 74.8k | do { |
1793 | 74.8k | if (EXPECTED(p->key)) { |
1794 | 73.8k | zend_string_release(p->key); |
1795 | 73.8k | } |
1796 | 74.8k | } while (++p != end); |
1797 | 12.6k | } |
1798 | 205k | } |
1799 | 339k | zend_hash_iterators_remove(ht); |
1800 | 339k | } |
1801 | 1.78M | } else if (EXPECTED(HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED)) { |
1802 | 1.64M | return; |
1803 | 1.64M | } |
1804 | 488k | pefree(HT_GET_DATA_ADDR(ht), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT); |
1805 | 488k | } |
1806 | | |
1807 | | ZEND_API void ZEND_FASTCALL zend_array_destroy(HashTable *ht) |
1808 | 9.99M | { |
1809 | 9.99M | IS_CONSISTENT(ht); |
1810 | 9.99M | HT_ASSERT(ht, GC_REFCOUNT(ht) <= 1); |
1811 | | |
1812 | | /* break possible cycles */ |
1813 | 9.99M | GC_REMOVE_FROM_BUFFER(ht); |
1814 | 9.99M | GC_TYPE_INFO(ht) = GC_NULL /*???| (GC_WHITE << 16)*/; |
1815 | | |
1816 | 9.99M | if (ht->nNumUsed) { |
1817 | | /* In some rare cases destructors of regular arrays may be changed */ |
1818 | 6.97M | if (UNEXPECTED(ht->pDestructor != ZVAL_PTR_DTOR)) { |
1819 | 1.26k | zend_hash_destroy(ht); |
1820 | 1.26k | goto free_ht; |
1821 | 1.26k | } |
1822 | | |
1823 | 6.97M | SET_INCONSISTENT(HT_IS_DESTROYING); |
1824 | | |
1825 | 6.97M | if (HT_IS_PACKED(ht)) { |
1826 | 3.10M | zval *zv = ht->arPacked; |
1827 | 3.10M | zval *end = zv + ht->nNumUsed; |
1828 | | |
1829 | 16.3M | do { |
1830 | 16.3M | i_zval_ptr_dtor(zv); |
1831 | 16.3M | } while (++zv != end); |
1832 | 3.86M | } else { |
1833 | 3.86M | Bucket *p = ht->arData; |
1834 | 3.86M | Bucket *end = p + ht->nNumUsed; |
1835 | | |
1836 | 3.86M | if (HT_HAS_STATIC_KEYS_ONLY(ht)) { |
1837 | 13.8M | do { |
1838 | 13.8M | i_zval_ptr_dtor(&p->val); |
1839 | 13.8M | } while (++p != end); |
1840 | 3.17M | } else if (HT_IS_WITHOUT_HOLES(ht)) { |
1841 | 2.80M | do { |
1842 | 2.80M | i_zval_ptr_dtor(&p->val); |
1843 | 2.80M | if (EXPECTED(p->key)) { |
1844 | 2.52M | zend_string_release_ex(p->key, 0); |
1845 | 2.52M | } |
1846 | 2.80M | } while (++p != end); |
1847 | 682k | } else { |
1848 | 10 | do { |
1849 | 10 | if (EXPECTED(Z_TYPE(p->val) != IS_UNDEF)) { |
1850 | 5 | i_zval_ptr_dtor(&p->val); |
1851 | 5 | if (EXPECTED(p->key)) { |
1852 | 5 | zend_string_release_ex(p->key, 0); |
1853 | 5 | } |
1854 | 5 | } |
1855 | 10 | } while (++p != end); |
1856 | 5 | } |
1857 | 3.86M | } |
1858 | 6.97M | } else if (EXPECTED(HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED)) { |
1859 | 2.33M | goto free_ht; |
1860 | 2.33M | } |
1861 | 7.65M | SET_INCONSISTENT(HT_DESTROYED); |
1862 | 7.65M | efree(HT_GET_DATA_ADDR(ht)); |
1863 | 9.99M | free_ht: |
1864 | 9.99M | zend_hash_iterators_remove(ht); |
1865 | 9.99M | FREE_HASHTABLE(ht); |
1866 | 9.99M | } |
1867 | | |
1868 | | ZEND_API void ZEND_FASTCALL zend_hash_clean(HashTable *ht) |
1869 | 441k | { |
1870 | 441k | IS_CONSISTENT(ht); |
1871 | 441k | HT_ASSERT_RC1(ht); |
1872 | | |
1873 | 441k | if (ht->nNumUsed) { |
1874 | 226k | if (HT_IS_PACKED(ht)) { |
1875 | 2.20k | zval *zv = ht->arPacked; |
1876 | 2.20k | zval *end = zv + ht->nNumUsed; |
1877 | | |
1878 | 2.20k | if (ht->pDestructor) { |
1879 | 0 | if (HT_HAS_STATIC_KEYS_ONLY(ht)) { |
1880 | 0 | if (HT_IS_WITHOUT_HOLES(ht)) { |
1881 | 0 | do { |
1882 | 0 | ht->pDestructor(zv); |
1883 | 0 | } while (++zv != end); |
1884 | 0 | } else { |
1885 | 0 | do { |
1886 | 0 | if (EXPECTED(Z_TYPE_P(zv) != IS_UNDEF)) { |
1887 | 0 | ht->pDestructor(zv); |
1888 | 0 | } |
1889 | 0 | } while (++zv != end); |
1890 | 0 | } |
1891 | 0 | } |
1892 | 0 | } |
1893 | 224k | } else { |
1894 | 224k | Bucket *p = ht->arData; |
1895 | 224k | Bucket *end = p + ht->nNumUsed; |
1896 | | |
1897 | 224k | if (ht->pDestructor) { |
1898 | 16 | if (HT_HAS_STATIC_KEYS_ONLY(ht)) { |
1899 | 16 | if (HT_IS_WITHOUT_HOLES(ht)) { |
1900 | 112 | do { |
1901 | 112 | ht->pDestructor(&p->val); |
1902 | 112 | } while (++p != end); |
1903 | 16 | } else { |
1904 | 0 | do { |
1905 | 0 | if (EXPECTED(Z_TYPE(p->val) != IS_UNDEF)) { |
1906 | 0 | ht->pDestructor(&p->val); |
1907 | 0 | } |
1908 | 0 | } while (++p != end); |
1909 | 0 | } |
1910 | 16 | } else if (HT_IS_WITHOUT_HOLES(ht)) { |
1911 | 0 | do { |
1912 | 0 | ht->pDestructor(&p->val); |
1913 | 0 | if (EXPECTED(p->key)) { |
1914 | 0 | zend_string_release(p->key); |
1915 | 0 | } |
1916 | 0 | } while (++p != end); |
1917 | 0 | } else { |
1918 | 0 | do { |
1919 | 0 | if (EXPECTED(Z_TYPE(p->val) != IS_UNDEF)) { |
1920 | 0 | ht->pDestructor(&p->val); |
1921 | 0 | if (EXPECTED(p->key)) { |
1922 | 0 | zend_string_release(p->key); |
1923 | 0 | } |
1924 | 0 | } |
1925 | 0 | } while (++p != end); |
1926 | 0 | } |
1927 | 224k | } else { |
1928 | 224k | if (!HT_HAS_STATIC_KEYS_ONLY(ht)) { |
1929 | 673k | do { |
1930 | 673k | if (EXPECTED(p->key)) { |
1931 | 573k | zend_string_release(p->key); |
1932 | 573k | } |
1933 | 673k | } while (++p != end); |
1934 | 98.1k | } |
1935 | 224k | } |
1936 | 224k | HT_HASH_RESET(ht); |
1937 | 224k | } |
1938 | 226k | } |
1939 | 441k | ht->nNumUsed = 0; |
1940 | 441k | ht->nNumOfElements = 0; |
1941 | 441k | ht->nNextFreeElement = ZEND_LONG_MIN; |
1942 | 441k | ht->nInternalPointer = 0; |
1943 | 441k | } |
1944 | | |
1945 | | ZEND_API void ZEND_FASTCALL zend_symtable_clean(HashTable *ht) |
1946 | 7.34k | { |
1947 | 7.34k | Bucket *p, *end; |
1948 | | |
1949 | 7.34k | IS_CONSISTENT(ht); |
1950 | 7.34k | HT_ASSERT_RC1(ht); |
1951 | | |
1952 | 7.34k | if (ht->nNumUsed) { |
1953 | 7.27k | ZEND_ASSERT(!HT_IS_PACKED(ht)); |
1954 | 7.27k | p = ht->arData; |
1955 | 7.27k | end = p + ht->nNumUsed; |
1956 | 7.27k | if (HT_HAS_STATIC_KEYS_ONLY(ht)) { |
1957 | 47.3k | do { |
1958 | 47.3k | i_zval_ptr_dtor(&p->val); |
1959 | 47.3k | } while (++p != end); |
1960 | 6.72k | } else if (HT_IS_WITHOUT_HOLES(ht)) { |
1961 | 5.94k | do { |
1962 | 5.94k | i_zval_ptr_dtor(&p->val); |
1963 | 5.94k | if (EXPECTED(p->key)) { |
1964 | 5.94k | zend_string_release(p->key); |
1965 | 5.94k | } |
1966 | 5.94k | } while (++p != end); |
1967 | 548 | } else { |
1968 | 0 | do { |
1969 | 0 | if (EXPECTED(Z_TYPE(p->val) != IS_UNDEF)) { |
1970 | 0 | i_zval_ptr_dtor(&p->val); |
1971 | 0 | if (EXPECTED(p->key)) { |
1972 | 0 | zend_string_release(p->key); |
1973 | 0 | } |
1974 | 0 | } |
1975 | 0 | } while (++p != end); |
1976 | 0 | } |
1977 | 7.27k | HT_HASH_RESET(ht); |
1978 | 7.27k | } |
1979 | 2.56k | ht->nNumUsed = 0; |
1980 | 2.56k | ht->nNumOfElements = 0; |
1981 | 2.56k | ht->nNextFreeElement = ZEND_LONG_MIN; |
1982 | 2.56k | ht->nInternalPointer = 0; |
1983 | 2.56k | } |
1984 | | |
1985 | | ZEND_API void ZEND_FASTCALL zend_hash_graceful_destroy(HashTable *ht) |
1986 | 0 | { |
1987 | 0 | uint32_t idx; |
1988 | |
|
1989 | 0 | IS_CONSISTENT(ht); |
1990 | 0 | HT_ASSERT_RC1(ht); |
1991 | | |
1992 | 0 | if (HT_IS_PACKED(ht)) { |
1993 | 0 | zval *zv = ht->arPacked; |
1994 | |
|
1995 | 0 | for (idx = 0; idx < ht->nNumUsed; idx++, zv++) { |
1996 | 0 | if (UNEXPECTED(Z_TYPE_P(zv) == IS_UNDEF)) continue; |
1997 | 0 | _zend_hash_packed_del_val(ht, HT_IDX_TO_HASH(idx), zv); |
1998 | 0 | } |
1999 | 0 | } else { |
2000 | 0 | Bucket *p = ht->arData; |
2001 | |
|
2002 | 0 | for (idx = 0; idx < ht->nNumUsed; idx++, p++) { |
2003 | 0 | if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) continue; |
2004 | 0 | _zend_hash_del_el(ht, HT_IDX_TO_HASH(idx), p); |
2005 | 0 | } |
2006 | 0 | } |
2007 | 0 | if (!(HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED)) { |
2008 | 0 | pefree(HT_GET_DATA_ADDR(ht), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT); |
2009 | 0 | } |
2010 | |
|
2011 | 0 | SET_INCONSISTENT(HT_DESTROYED); |
2012 | 0 | } |
2013 | | |
2014 | | ZEND_API void ZEND_FASTCALL zend_hash_graceful_reverse_destroy(HashTable *ht) |
2015 | 600k | { |
2016 | 600k | uint32_t idx; |
2017 | | |
2018 | 600k | IS_CONSISTENT(ht); |
2019 | 600k | HT_ASSERT_RC1(ht); |
2020 | | |
2021 | 600k | idx = ht->nNumUsed; |
2022 | 600k | if (HT_IS_PACKED(ht)) { |
2023 | 6.27k | zval *zv = ht->arPacked + ht->nNumUsed; |
2024 | | |
2025 | 6.50k | while (idx > 0) { |
2026 | 232 | idx--; |
2027 | 232 | zv--; |
2028 | 232 | if (UNEXPECTED(Z_TYPE_P(zv) == IS_UNDEF)) continue; |
2029 | 118 | _zend_hash_packed_del_val(ht, HT_IDX_TO_HASH(idx), zv); |
2030 | 118 | } |
2031 | 594k | } else { |
2032 | 594k | Bucket *p = ht->arData + ht->nNumUsed; |
2033 | | |
2034 | 2.17M | while (idx > 0) { |
2035 | 1.57M | idx--; |
2036 | 1.57M | p--; |
2037 | 1.57M | if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) continue; |
2038 | 1.55M | _zend_hash_del_el(ht, HT_IDX_TO_HASH(idx), p); |
2039 | 1.55M | } |
2040 | 594k | } |
2041 | | |
2042 | 600k | if (!(HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED)) { |
2043 | 306k | pefree(HT_GET_DATA_ADDR(ht), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT); |
2044 | 306k | } |
2045 | | |
2046 | 600k | SET_INCONSISTENT(HT_DESTROYED); |
2047 | 600k | } |
2048 | | |
2049 | | /* This is used to recurse elements and selectively delete certain entries |
2050 | | * from a hashtable. apply_func() receives the data and decides if the entry |
2051 | | * should be deleted or recursion should be stopped. The following three |
2052 | | * return codes are possible: |
2053 | | * ZEND_HASH_APPLY_KEEP - continue |
2054 | | * ZEND_HASH_APPLY_STOP - stop iteration |
2055 | | * ZEND_HASH_APPLY_REMOVE - delete the element, combinable with the former |
2056 | | */ |
2057 | | |
2058 | | ZEND_API void ZEND_FASTCALL zend_hash_apply(HashTable *ht, apply_func_t apply_func) |
2059 | 266 | { |
2060 | 266 | uint32_t idx; |
2061 | 266 | int result; |
2062 | | |
2063 | 266 | IS_CONSISTENT(ht); |
2064 | 266 | if (HT_IS_PACKED(ht)) { |
2065 | 920 | for (idx = 0; idx < ht->nNumUsed; idx++) { |
2066 | 670 | zval *zv = ht->arPacked + idx; |
2067 | | |
2068 | 670 | if (UNEXPECTED(Z_TYPE_P(zv) == IS_UNDEF)) continue; |
2069 | 670 | result = apply_func(zv); |
2070 | | |
2071 | 670 | if (result & ZEND_HASH_APPLY_REMOVE) { |
2072 | 0 | HT_ASSERT_RC1(ht); |
2073 | 0 | _zend_hash_packed_del_val(ht, HT_IDX_TO_HASH(idx), zv); |
2074 | 0 | } |
2075 | 670 | if (result & ZEND_HASH_APPLY_STOP) { |
2076 | 0 | break; |
2077 | 0 | } |
2078 | 670 | } |
2079 | 250 | } else { |
2080 | 208 | for (idx = 0; idx < ht->nNumUsed; idx++) { |
2081 | 192 | Bucket *p = ht->arData + idx; |
2082 | | |
2083 | 192 | if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) continue; |
2084 | 192 | result = apply_func(&p->val); |
2085 | | |
2086 | 192 | if (result & ZEND_HASH_APPLY_REMOVE) { |
2087 | 0 | HT_ASSERT_RC1(ht); |
2088 | 0 | _zend_hash_del_el(ht, HT_IDX_TO_HASH(idx), p); |
2089 | 0 | } |
2090 | 192 | if (result & ZEND_HASH_APPLY_STOP) { |
2091 | 0 | break; |
2092 | 0 | } |
2093 | 192 | } |
2094 | 16 | } |
2095 | 266 | } |
2096 | | |
2097 | | |
2098 | | ZEND_API void ZEND_FASTCALL zend_hash_apply_with_argument(HashTable *ht, apply_func_arg_t apply_func, void *argument) |
2099 | 0 | { |
2100 | 0 | uint32_t idx; |
2101 | 0 | int result; |
2102 | |
|
2103 | 0 | IS_CONSISTENT(ht); |
2104 | 0 | if (HT_IS_PACKED(ht)) { |
2105 | 0 | for (idx = 0; idx < ht->nNumUsed; idx++) { |
2106 | 0 | zval *zv = ht->arPacked + idx; |
2107 | 0 | if (UNEXPECTED(Z_TYPE_P(zv) == IS_UNDEF)) continue; |
2108 | 0 | result = apply_func(zv, argument); |
2109 | |
|
2110 | 0 | if (result & ZEND_HASH_APPLY_REMOVE) { |
2111 | 0 | HT_ASSERT_RC1(ht); |
2112 | 0 | _zend_hash_packed_del_val(ht, HT_IDX_TO_HASH(idx), zv); |
2113 | 0 | } |
2114 | 0 | if (result & ZEND_HASH_APPLY_STOP) { |
2115 | 0 | break; |
2116 | 0 | } |
2117 | 0 | } |
2118 | 0 | } else { |
2119 | 0 | for (idx = 0; idx < ht->nNumUsed; idx++) { |
2120 | 0 | Bucket *p = ht->arData + idx; |
2121 | 0 | if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) continue; |
2122 | 0 | result = apply_func(&p->val, argument); |
2123 | |
|
2124 | 0 | if (result & ZEND_HASH_APPLY_REMOVE) { |
2125 | 0 | HT_ASSERT_RC1(ht); |
2126 | 0 | _zend_hash_del_el(ht, HT_IDX_TO_HASH(idx), p); |
2127 | 0 | } |
2128 | 0 | if (result & ZEND_HASH_APPLY_STOP) { |
2129 | 0 | break; |
2130 | 0 | } |
2131 | 0 | } |
2132 | 0 | } |
2133 | 0 | } |
2134 | | |
2135 | | |
2136 | | ZEND_API void zend_hash_apply_with_arguments(HashTable *ht, apply_func_args_t apply_func, int num_args, ...) |
2137 | 0 | { |
2138 | 0 | uint32_t idx; |
2139 | 0 | va_list args; |
2140 | 0 | zend_hash_key hash_key; |
2141 | 0 | int result; |
2142 | |
|
2143 | 0 | IS_CONSISTENT(ht); |
2144 | |
|
2145 | 0 | if (HT_IS_PACKED(ht)) { |
2146 | 0 | for (idx = 0; idx < ht->nNumUsed; idx++) { |
2147 | 0 | zval *zv = ht->arPacked + idx; |
2148 | |
|
2149 | 0 | if (UNEXPECTED(Z_TYPE_P(zv) == IS_UNDEF)) continue; |
2150 | 0 | va_start(args, num_args); |
2151 | 0 | hash_key.h = idx; |
2152 | 0 | hash_key.key = NULL; |
2153 | |
|
2154 | 0 | result = apply_func(zv, num_args, args, &hash_key); |
2155 | |
|
2156 | 0 | if (result & ZEND_HASH_APPLY_REMOVE) { |
2157 | 0 | HT_ASSERT_RC1(ht); |
2158 | 0 | _zend_hash_packed_del_val(ht, HT_IDX_TO_HASH(idx), zv); |
2159 | 0 | } |
2160 | 0 | if (result & ZEND_HASH_APPLY_STOP) { |
2161 | 0 | va_end(args); |
2162 | 0 | break; |
2163 | 0 | } |
2164 | 0 | va_end(args); |
2165 | 0 | } |
2166 | 0 | } else { |
2167 | 0 | for (idx = 0; idx < ht->nNumUsed; idx++) { |
2168 | 0 | Bucket *p = ht->arData + idx; |
2169 | |
|
2170 | 0 | if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) continue; |
2171 | 0 | va_start(args, num_args); |
2172 | 0 | hash_key.h = p->h; |
2173 | 0 | hash_key.key = p->key; |
2174 | |
|
2175 | 0 | result = apply_func(&p->val, num_args, args, &hash_key); |
2176 | |
|
2177 | 0 | if (result & ZEND_HASH_APPLY_REMOVE) { |
2178 | 0 | HT_ASSERT_RC1(ht); |
2179 | 0 | _zend_hash_del_el(ht, HT_IDX_TO_HASH(idx), p); |
2180 | 0 | } |
2181 | 0 | if (result & ZEND_HASH_APPLY_STOP) { |
2182 | 0 | va_end(args); |
2183 | 0 | break; |
2184 | 0 | } |
2185 | 0 | va_end(args); |
2186 | 0 | } |
2187 | 0 | } |
2188 | 0 | } |
2189 | | |
2190 | | |
2191 | | ZEND_API void ZEND_FASTCALL zend_hash_reverse_apply(HashTable *ht, apply_func_t apply_func) |
2192 | 330k | { |
2193 | 330k | uint32_t idx; |
2194 | 330k | int result; |
2195 | | |
2196 | 330k | IS_CONSISTENT(ht); |
2197 | | |
2198 | 330k | idx = ht->nNumUsed; |
2199 | 330k | if (HT_IS_PACKED(ht)) { |
2200 | 0 | zval *zv; |
2201 | |
|
2202 | 0 | while (idx > 0) { |
2203 | 0 | idx--; |
2204 | 0 | zv = ht->arPacked + idx; |
2205 | 0 | if (UNEXPECTED(Z_TYPE_P(zv) == IS_UNDEF)) continue; |
2206 | | |
2207 | 0 | result = apply_func(zv); |
2208 | |
|
2209 | 0 | if (result & ZEND_HASH_APPLY_REMOVE) { |
2210 | 0 | HT_ASSERT_RC1(ht); |
2211 | 0 | _zend_hash_packed_del_val(ht, HT_IDX_TO_HASH(idx), zv); |
2212 | 0 | } |
2213 | 0 | if (result & ZEND_HASH_APPLY_STOP) { |
2214 | 0 | break; |
2215 | 0 | } |
2216 | 0 | } |
2217 | 330k | } else { |
2218 | 330k | Bucket *p; |
2219 | | |
2220 | 2.33M | while (idx > 0) { |
2221 | 2.00M | idx--; |
2222 | 2.00M | p = ht->arData + idx; |
2223 | 2.00M | if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) continue; |
2224 | | |
2225 | 1.95M | result = apply_func(&p->val); |
2226 | | |
2227 | 1.95M | if (result & ZEND_HASH_APPLY_REMOVE) { |
2228 | 42.8k | HT_ASSERT_RC1(ht); |
2229 | 42.8k | _zend_hash_del_el(ht, HT_IDX_TO_HASH(idx), p); |
2230 | 42.8k | } |
2231 | 1.95M | if (result & ZEND_HASH_APPLY_STOP) { |
2232 | 52 | break; |
2233 | 52 | } |
2234 | 1.95M | } |
2235 | 330k | } |
2236 | 330k | } |
2237 | | |
2238 | | |
2239 | | ZEND_API void ZEND_FASTCALL zend_hash_copy(HashTable *target, const HashTable *source, copy_ctor_func_t pCopyConstructor) |
2240 | 222 | { |
2241 | 222 | uint32_t idx; |
2242 | 222 | zval *new_entry, *data; |
2243 | | |
2244 | 222 | IS_CONSISTENT(source); |
2245 | 222 | IS_CONSISTENT(target); |
2246 | 222 | HT_ASSERT_RC1(target); |
2247 | | |
2248 | 222 | if (HT_IS_PACKED(source)) { |
2249 | 0 | for (idx = 0; idx < source->nNumUsed; idx++) { |
2250 | 0 | zval *zv = source->arPacked + idx; |
2251 | 0 | if (UNEXPECTED(Z_TYPE_P(zv) == IS_UNDEF)) continue; |
2252 | | |
2253 | 0 | new_entry = zend_hash_index_update(target, idx, zv); |
2254 | 0 | if (pCopyConstructor) { |
2255 | 0 | pCopyConstructor(new_entry); |
2256 | 0 | } |
2257 | 0 | } |
2258 | 0 | return; |
2259 | 0 | } |
2260 | | |
2261 | 1.11k | for (idx = 0; idx < source->nNumUsed; idx++) { |
2262 | 894 | Bucket *p = source->arData + idx; |
2263 | | |
2264 | 894 | if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) continue; |
2265 | | |
2266 | | /* INDIRECT element may point to UNDEF-ined slots */ |
2267 | 894 | data = &p->val; |
2268 | 894 | if (Z_TYPE_P(data) == IS_INDIRECT) { |
2269 | 0 | data = Z_INDIRECT_P(data); |
2270 | 0 | if (UNEXPECTED(Z_TYPE_P(data) == IS_UNDEF)) { |
2271 | 0 | continue; |
2272 | 0 | } |
2273 | 0 | } |
2274 | 894 | if (p->key) { |
2275 | 882 | new_entry = zend_hash_update(target, p->key, data); |
2276 | 882 | } else { |
2277 | 12 | new_entry = zend_hash_index_update(target, p->h, data); |
2278 | 12 | } |
2279 | 894 | if (pCopyConstructor) { |
2280 | 13 | pCopyConstructor(new_entry); |
2281 | 13 | } |
2282 | 894 | } |
2283 | 222 | } |
2284 | | |
2285 | | |
2286 | | static zend_always_inline bool zend_array_dup_value(const HashTable *source, zval *data, zval *dest, bool packed, bool with_holes) |
2287 | 66.5k | { |
2288 | 66.5k | if (with_holes) { |
2289 | 4.54k | if (!packed && Z_TYPE_INFO_P(data) == IS_INDIRECT) { |
2290 | 0 | data = Z_INDIRECT_P(data); |
2291 | 0 | } |
2292 | 4.54k | if (UNEXPECTED(Z_TYPE_INFO_P(data) == IS_UNDEF)) { |
2293 | 1.79k | return 0; |
2294 | 1.79k | } |
2295 | 62.0k | } else if (!packed) { |
2296 | | /* INDIRECT element may point to UNDEF-ined slots */ |
2297 | 31.6k | if (Z_TYPE_INFO_P(data) == IS_INDIRECT) { |
2298 | 6.48k | data = Z_INDIRECT_P(data); |
2299 | 6.48k | if (UNEXPECTED(Z_TYPE_INFO_P(data) == IS_UNDEF)) { |
2300 | 3.11k | return 0; |
2301 | 3.11k | } |
2302 | 6.48k | } |
2303 | 31.6k | } |
2304 | | |
2305 | 61.6k | do { |
2306 | 61.6k | if (Z_OPT_REFCOUNTED_P(data)) { |
2307 | 26.1k | if (Z_ISREF_P(data) && Z_REFCOUNT_P(data) == 1 && |
2308 | 26.1k | (Z_TYPE_P(Z_REFVAL_P(data)) != IS_ARRAY || |
2309 | 161 | Z_ARRVAL_P(Z_REFVAL_P(data)) != source)) { |
2310 | 143 | data = Z_REFVAL_P(data); |
2311 | 143 | if (!Z_OPT_REFCOUNTED_P(data)) { |
2312 | 80 | break; |
2313 | 80 | } |
2314 | 143 | } |
2315 | 26.0k | Z_ADDREF_P(data); |
2316 | 26.0k | } |
2317 | 61.6k | } while (0); |
2318 | 61.6k | ZVAL_COPY_VALUE(dest, data); |
2319 | | |
2320 | 61.6k | return 1; |
2321 | 66.5k | } |
2322 | | |
2323 | | static zend_always_inline bool zend_array_dup_element(const HashTable *source, HashTable *target, uint32_t idx, Bucket *p, Bucket *q, bool packed, bool static_keys, bool with_holes) |
2324 | 31.6k | { |
2325 | 31.6k | if (!zend_array_dup_value(source, &p->val, &q->val, packed, with_holes)) { |
2326 | 3.13k | return 0; |
2327 | 3.13k | } |
2328 | | |
2329 | 28.5k | if (!packed) { |
2330 | 28.5k | uint32_t nIndex; |
2331 | | |
2332 | 28.5k | q->h = p->h; |
2333 | 28.5k | q->key = p->key; |
2334 | 28.5k | if (!static_keys && q->key) { |
2335 | 7.09k | zend_string_addref(q->key); |
2336 | 7.09k | } |
2337 | | |
2338 | 28.5k | nIndex = q->h | target->nTableMask; |
2339 | 28.5k | Z_NEXT(q->val) = HT_HASH(target, nIndex); |
2340 | 28.5k | HT_HASH(target, nIndex) = HT_IDX_TO_HASH(idx); |
2341 | 28.5k | } |
2342 | 28.5k | return 1; |
2343 | 31.6k | } |
2344 | | |
2345 | | // We need to duplicate iterators to be able to search through all copy-on-write copies to find the actually iterated HashTable and position back |
2346 | 62 | static void zend_array_dup_ht_iterators(const HashTable *source, HashTable *target) { |
2347 | 62 | uint32_t iter_index = 0; |
2348 | 62 | uint32_t end_index = EG(ht_iterators_used); |
2349 | | |
2350 | 139 | while (iter_index != end_index) { |
2351 | 77 | HashTableIterator *iter = &EG(ht_iterators)[iter_index]; |
2352 | 77 | if (iter->ht == source) { |
2353 | 62 | uint32_t copy_idx = zend_hash_iterator_add(target, iter->pos); |
2354 | | /* Refetch iter because the memory may be reallocated. */ |
2355 | 62 | iter = &EG(ht_iterators)[iter_index]; |
2356 | 62 | HashTableIterator *copy_iter = EG(ht_iterators) + copy_idx; |
2357 | 62 | copy_iter->next_copy = iter->next_copy; |
2358 | 62 | iter->next_copy = copy_idx; |
2359 | 62 | } |
2360 | 77 | iter_index++; |
2361 | 77 | } |
2362 | 62 | } |
2363 | | |
2364 | | static zend_always_inline void zend_array_dup_packed_elements(const HashTable *source, HashTable *target, bool with_holes) |
2365 | 4.27k | { |
2366 | 4.27k | zval *p = source->arPacked; |
2367 | 4.27k | zval *q = target->arPacked; |
2368 | 4.27k | const zval *end = p + source->nNumUsed; |
2369 | | |
2370 | 34.9k | do { |
2371 | 34.9k | if (!zend_array_dup_value(source, p, q, 1, with_holes)) { |
2372 | 1.77k | if (with_holes) { |
2373 | 1.77k | ZVAL_UNDEF(q); |
2374 | 1.77k | } |
2375 | 1.77k | } |
2376 | 34.9k | p++; q++; |
2377 | 34.9k | } while (p != end); |
2378 | | |
2379 | 4.27k | if (UNEXPECTED(HT_HAS_ITERATORS(source))) { |
2380 | 27 | zend_array_dup_ht_iterators(source, target); |
2381 | 27 | } |
2382 | 4.27k | } |
2383 | | |
2384 | | static zend_always_inline uint32_t zend_array_dup_elements(const HashTable *source, HashTable *target, bool static_keys, bool with_holes) |
2385 | 5.39k | { |
2386 | 5.39k | uint32_t idx = 0; |
2387 | 5.39k | Bucket *p = source->arData; |
2388 | 5.39k | Bucket *q = target->arData; |
2389 | 5.39k | const Bucket *end = p + source->nNumUsed; |
2390 | | |
2391 | 5.39k | if (UNEXPECTED(HT_HAS_ITERATORS(source))) { |
2392 | 35 | zend_array_dup_ht_iterators(source, target); |
2393 | 35 | } |
2394 | | |
2395 | 28.5k | do { |
2396 | 28.5k | if (!zend_array_dup_element(source, target, idx, p, q, 0, static_keys, with_holes)) { |
2397 | 876 | uint32_t target_idx = idx; |
2398 | | |
2399 | 876 | idx++; p++; |
2400 | 876 | if (EXPECTED(!HT_HAS_ITERATORS(target))) { |
2401 | 3.97k | while (p != end) { |
2402 | 3.11k | if (zend_array_dup_element(source, target, target_idx, p, q, 0, static_keys, with_holes)) { |
2403 | 861 | if (source->nInternalPointer == idx) { |
2404 | 0 | target->nInternalPointer = target_idx; |
2405 | 0 | } |
2406 | 861 | target_idx++; q++; |
2407 | 861 | } |
2408 | 3.11k | idx++; p++; |
2409 | 3.11k | } |
2410 | 866 | } else { |
2411 | 10 | target->nNumUsed = source->nNumUsed; |
2412 | 10 | uint32_t iter_pos = zend_hash_iterators_lower_pos(target, idx); |
2413 | | |
2414 | 30 | while (p != end) { |
2415 | 20 | if (zend_array_dup_element(source, target, target_idx, p, q, 0, static_keys, with_holes)) { |
2416 | 15 | if (source->nInternalPointer == idx) { |
2417 | 0 | target->nInternalPointer = target_idx; |
2418 | 0 | } |
2419 | 15 | if (UNEXPECTED(idx >= iter_pos)) { |
2420 | 5 | do { |
2421 | 5 | zend_hash_iterators_update(target, iter_pos, target_idx); |
2422 | 5 | iter_pos = zend_hash_iterators_lower_pos(target, iter_pos + 1); |
2423 | 5 | } while (iter_pos < idx); |
2424 | 5 | } |
2425 | 15 | target_idx++; q++; |
2426 | 15 | } |
2427 | 20 | idx++; p++; |
2428 | 20 | } |
2429 | 10 | } |
2430 | 876 | return target_idx; |
2431 | 876 | } |
2432 | 27.6k | idx++; p++; q++; |
2433 | 27.6k | } while (p != end); |
2434 | 4.52k | return idx; |
2435 | 5.39k | } |
2436 | | |
2437 | | ZEND_API HashTable* ZEND_FASTCALL zend_array_dup(const HashTable *source) |
2438 | 24.8k | { |
2439 | 24.8k | uint32_t idx; |
2440 | 24.8k | HashTable *target; |
2441 | | |
2442 | 24.8k | IS_CONSISTENT(source); |
2443 | | |
2444 | 24.8k | ALLOC_HASHTABLE(target); |
2445 | 24.8k | GC_SET_REFCOUNT(target, 1); |
2446 | 24.8k | GC_TYPE_INFO(target) = GC_ARRAY; |
2447 | | |
2448 | 24.8k | target->pDestructor = ZVAL_PTR_DTOR; |
2449 | | |
2450 | 24.8k | if (source->nNumOfElements == 0) { |
2451 | 7.14k | HT_FLAGS(target) = HASH_FLAG_UNINITIALIZED; |
2452 | 7.14k | target->nTableMask = HT_MIN_MASK; |
2453 | 7.14k | target->nNumUsed = 0; |
2454 | 7.14k | target->nNumOfElements = 0; |
2455 | 7.14k | target->nNextFreeElement = source->nNextFreeElement; |
2456 | 7.14k | target->nInternalPointer = 0; |
2457 | 7.14k | target->nTableSize = HT_MIN_SIZE; |
2458 | 7.14k | HT_SET_DATA_ADDR(target, &uninitialized_bucket); |
2459 | 17.6k | } else if (GC_FLAGS(source) & IS_ARRAY_IMMUTABLE) { |
2460 | 7.99k | HT_FLAGS(target) = HT_FLAGS(source) & HASH_FLAG_MASK; |
2461 | 7.99k | target->nTableMask = source->nTableMask; |
2462 | 7.99k | target->nNumUsed = source->nNumUsed; |
2463 | 7.99k | target->nNumOfElements = source->nNumOfElements; |
2464 | 7.99k | target->nNextFreeElement = source->nNextFreeElement; |
2465 | 7.99k | target->nTableSize = source->nTableSize; |
2466 | 7.99k | if (HT_IS_PACKED(source)) { |
2467 | 3.75k | HT_SET_DATA_ADDR(target, emalloc(HT_PACKED_SIZE(target))); |
2468 | 3.75k | target->nInternalPointer = source->nInternalPointer; |
2469 | 3.75k | memcpy(HT_GET_DATA_ADDR(target), HT_GET_DATA_ADDR(source), HT_PACKED_USED_SIZE(source)); |
2470 | 4.23k | } else { |
2471 | 4.23k | HT_SET_DATA_ADDR(target, emalloc(HT_SIZE(target))); |
2472 | 4.23k | target->nInternalPointer = source->nInternalPointer; |
2473 | 4.23k | memcpy(HT_GET_DATA_ADDR(target), HT_GET_DATA_ADDR(source), HT_USED_SIZE(source)); |
2474 | 4.23k | } |
2475 | 9.67k | } else if (HT_IS_PACKED(source)) { |
2476 | 4.27k | HT_FLAGS(target) = HT_FLAGS(source) & HASH_FLAG_MASK; |
2477 | 4.27k | target->nTableMask = HT_MIN_MASK; |
2478 | 4.27k | target->nNumUsed = source->nNumUsed; |
2479 | 4.27k | target->nNumOfElements = source->nNumOfElements; |
2480 | 4.27k | target->nNextFreeElement = source->nNextFreeElement; |
2481 | 4.27k | target->nTableSize = source->nTableSize; |
2482 | 4.27k | HT_SET_DATA_ADDR(target, emalloc(HT_PACKED_SIZE_EX(target->nTableSize, HT_MIN_MASK))); |
2483 | 4.27k | target->nInternalPointer = |
2484 | 4.27k | (source->nInternalPointer < source->nNumUsed) ? |
2485 | 4.27k | source->nInternalPointer : 0; |
2486 | | |
2487 | 4.27k | HT_HASH_RESET_PACKED(target); |
2488 | | |
2489 | 4.27k | if (HT_IS_WITHOUT_HOLES(target)) { |
2490 | 3.69k | zend_array_dup_packed_elements(source, target, 0); |
2491 | 3.69k | } else { |
2492 | 580 | zend_array_dup_packed_elements(source, target, 1); |
2493 | 580 | } |
2494 | 5.39k | } else { |
2495 | 5.39k | HT_FLAGS(target) = HT_FLAGS(source) & HASH_FLAG_MASK; |
2496 | 5.39k | target->nTableMask = source->nTableMask; |
2497 | 5.39k | target->nNextFreeElement = source->nNextFreeElement; |
2498 | 5.39k | target->nInternalPointer = |
2499 | 5.39k | (source->nInternalPointer < source->nNumUsed) ? |
2500 | 5.39k | source->nInternalPointer : 0; |
2501 | | |
2502 | 5.39k | target->nTableSize = source->nTableSize; |
2503 | 5.39k | HT_SET_DATA_ADDR(target, emalloc(HT_SIZE(target))); |
2504 | 5.39k | HT_HASH_RESET(target); |
2505 | | |
2506 | 5.39k | if (HT_HAS_STATIC_KEYS_ONLY(target)) { |
2507 | 4.28k | if (HT_IS_WITHOUT_HOLES(source)) { |
2508 | 4.26k | idx = zend_array_dup_elements(source, target, 1, 0); |
2509 | 4.26k | } else { |
2510 | 12 | idx = zend_array_dup_elements(source, target, 1, 1); |
2511 | 12 | } |
2512 | 4.28k | } else { |
2513 | 1.11k | if (HT_IS_WITHOUT_HOLES(source)) { |
2514 | 1.11k | idx = zend_array_dup_elements(source, target, 0, 0); |
2515 | 1.11k | } else { |
2516 | 0 | idx = zend_array_dup_elements(source, target, 0, 1); |
2517 | 0 | } |
2518 | 1.11k | } |
2519 | 5.39k | target->nNumUsed = idx; |
2520 | 5.39k | target->nNumOfElements = idx; |
2521 | 5.39k | } |
2522 | 24.8k | return target; |
2523 | 24.8k | } |
2524 | | |
2525 | | ZEND_API HashTable* zend_array_to_list(const HashTable *source) |
2526 | 0 | { |
2527 | 0 | HashTable *result = _zend_new_array(zend_hash_num_elements(source)); |
2528 | 0 | zend_hash_real_init_packed(result); |
2529 | |
|
2530 | 0 | ZEND_HASH_FILL_PACKED(result) { |
2531 | 0 | zval *entry; |
2532 | |
|
2533 | 0 | ZEND_HASH_FOREACH_VAL(source, entry) { |
2534 | 0 | if (UNEXPECTED(Z_ISREF_P(entry) && Z_REFCOUNT_P(entry) == 1)) { |
2535 | 0 | entry = Z_REFVAL_P(entry); |
2536 | 0 | } |
2537 | 0 | Z_TRY_ADDREF_P(entry); |
2538 | 0 | ZEND_HASH_FILL_ADD(entry); |
2539 | 0 | } ZEND_HASH_FOREACH_END(); |
2540 | 0 | } ZEND_HASH_FILL_END(); |
2541 | | |
2542 | 0 | return result; |
2543 | 0 | } |
2544 | | |
2545 | | |
2546 | | ZEND_API void ZEND_FASTCALL zend_hash_merge(HashTable *target, const HashTable *source, copy_ctor_func_t pCopyConstructor, bool overwrite) |
2547 | 8.01k | { |
2548 | 8.01k | uint32_t idx; |
2549 | 8.01k | Bucket *p; |
2550 | 8.01k | zval *t, *s; |
2551 | | |
2552 | 8.01k | IS_CONSISTENT(source); |
2553 | 8.01k | IS_CONSISTENT(target); |
2554 | 8.01k | HT_ASSERT_RC1(target); |
2555 | | |
2556 | 8.01k | if (overwrite) { |
2557 | 0 | if (HT_IS_PACKED(source)) { |
2558 | 0 | for (idx = 0; idx < source->nNumUsed; idx++) { |
2559 | 0 | s = source->arPacked + idx; |
2560 | 0 | if (UNEXPECTED(Z_TYPE_P(s) == IS_UNDEF)) { |
2561 | 0 | continue; |
2562 | 0 | } |
2563 | 0 | t = zend_hash_index_update(target, idx, s); |
2564 | 0 | if (pCopyConstructor) { |
2565 | 0 | pCopyConstructor(t); |
2566 | 0 | } |
2567 | 0 | } |
2568 | 0 | return; |
2569 | 0 | } |
2570 | | |
2571 | 0 | for (idx = 0; idx < source->nNumUsed; idx++) { |
2572 | 0 | p = source->arData + idx; |
2573 | 0 | s = &p->val; |
2574 | 0 | if (UNEXPECTED(Z_TYPE_P(s) == IS_INDIRECT)) { |
2575 | 0 | s = Z_INDIRECT_P(s); |
2576 | 0 | } |
2577 | 0 | if (UNEXPECTED(Z_TYPE_P(s) == IS_UNDEF)) { |
2578 | 0 | continue; |
2579 | 0 | } |
2580 | 0 | if (p->key) { |
2581 | 0 | t = _zend_hash_add_or_update_i(target, p->key, s, HASH_UPDATE | HASH_UPDATE_INDIRECT); |
2582 | 0 | if (pCopyConstructor) { |
2583 | 0 | pCopyConstructor(t); |
2584 | 0 | } |
2585 | 0 | } else { |
2586 | 0 | t = zend_hash_index_update(target, p->h, s); |
2587 | 0 | if (pCopyConstructor) { |
2588 | 0 | pCopyConstructor(t); |
2589 | 0 | } |
2590 | 0 | } |
2591 | 0 | } |
2592 | 8.01k | } else { |
2593 | 8.01k | if (HT_IS_PACKED(source)) { |
2594 | 20.2k | for (idx = 0; idx < source->nNumUsed; idx++) { |
2595 | 16.8k | s = source->arPacked + idx; |
2596 | 16.8k | if (UNEXPECTED(Z_TYPE_P(s) == IS_UNDEF)) { |
2597 | 2.34k | continue; |
2598 | 2.34k | } |
2599 | 14.4k | t = zend_hash_index_add(target, idx, s); |
2600 | 14.4k | if (t && pCopyConstructor) { |
2601 | 9.72k | pCopyConstructor(t); |
2602 | 9.72k | } |
2603 | 14.4k | } |
2604 | 3.42k | return; |
2605 | 3.42k | } |
2606 | | |
2607 | 8.61k | for (idx = 0; idx < source->nNumUsed; idx++) { |
2608 | 4.02k | p = source->arData + idx; |
2609 | 4.02k | s = &p->val; |
2610 | 4.02k | if (UNEXPECTED(Z_TYPE_P(s) == IS_INDIRECT)) { |
2611 | 0 | s = Z_INDIRECT_P(s); |
2612 | 0 | } |
2613 | 4.02k | if (UNEXPECTED(Z_TYPE_P(s) == IS_UNDEF)) { |
2614 | 0 | continue; |
2615 | 0 | } |
2616 | 4.02k | if (p->key) { |
2617 | 1.39k | t = _zend_hash_add_or_update_i(target, p->key, s, HASH_ADD | HASH_UPDATE_INDIRECT); |
2618 | 1.39k | if (t && pCopyConstructor) { |
2619 | 194 | pCopyConstructor(t); |
2620 | 194 | } |
2621 | 2.63k | } else { |
2622 | 2.63k | t = zend_hash_index_add(target, p->h, s); |
2623 | 2.63k | if (t && pCopyConstructor) { |
2624 | 2.28k | pCopyConstructor(t); |
2625 | 2.28k | } |
2626 | 2.63k | } |
2627 | 4.02k | } |
2628 | 4.58k | } |
2629 | 8.01k | } |
2630 | | |
2631 | | |
2632 | | static bool ZEND_FASTCALL zend_hash_replace_checker_wrapper(HashTable *target, zval *source_data, zend_ulong h, zend_string *key, void *pParam, merge_checker_func_t merge_checker_func) |
2633 | 0 | { |
2634 | 0 | zend_hash_key hash_key; |
2635 | |
|
2636 | 0 | hash_key.h = h; |
2637 | 0 | hash_key.key = key; |
2638 | 0 | return merge_checker_func(target, source_data, &hash_key, pParam); |
2639 | 0 | } |
2640 | | |
2641 | | |
2642 | | ZEND_API void ZEND_FASTCALL zend_hash_merge_ex(HashTable *target, const HashTable *source, copy_ctor_func_t pCopyConstructor, merge_checker_func_t pMergeSource, void *pParam) |
2643 | 0 | { |
2644 | 0 | uint32_t idx; |
2645 | 0 | Bucket *p; |
2646 | 0 | zval *t; |
2647 | |
|
2648 | 0 | IS_CONSISTENT(source); |
2649 | 0 | IS_CONSISTENT(target); |
2650 | 0 | HT_ASSERT_RC1(target); |
2651 | | |
2652 | 0 | ZEND_ASSERT(!HT_IS_PACKED(source)); |
2653 | 0 | for (idx = 0; idx < source->nNumUsed; idx++) { |
2654 | 0 | p = source->arData + idx; |
2655 | 0 | if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) continue; |
2656 | 0 | if (zend_hash_replace_checker_wrapper(target, &p->val, p->h, p->key, pParam, pMergeSource)) { |
2657 | 0 | t = zend_hash_update(target, p->key, &p->val); |
2658 | 0 | if (pCopyConstructor) { |
2659 | 0 | pCopyConstructor(t); |
2660 | 0 | } |
2661 | 0 | } |
2662 | 0 | } |
2663 | 0 | } |
2664 | | |
2665 | | |
2666 | | /* Returns the hash table data if found and NULL if not. */ |
2667 | | ZEND_API zval* ZEND_FASTCALL zend_hash_find(const HashTable *ht, zend_string *key) |
2668 | 38.8M | { |
2669 | 38.8M | Bucket *p; |
2670 | | |
2671 | 38.8M | IS_CONSISTENT(ht); |
2672 | | |
2673 | 38.8M | (void)zend_string_hash_val(key); |
2674 | 38.8M | p = zend_hash_find_bucket(ht, key); |
2675 | 38.8M | return p ? &p->val : NULL; |
2676 | 38.8M | } |
2677 | | |
2678 | | ZEND_API zval* ZEND_FASTCALL zend_hash_find_known_hash(const HashTable *ht, const zend_string *key) |
2679 | 1.70M | { |
2680 | 1.70M | Bucket *p; |
2681 | | |
2682 | 1.70M | IS_CONSISTENT(ht); |
2683 | | |
2684 | 1.70M | p = zend_hash_find_bucket(ht, key); |
2685 | 1.70M | return p ? &p->val : NULL; |
2686 | 1.70M | } |
2687 | | |
2688 | | ZEND_API zval* ZEND_FASTCALL zend_hash_str_find(const HashTable *ht, const char *str, size_t len) |
2689 | 5.46M | { |
2690 | 5.46M | zend_ulong h; |
2691 | 5.46M | Bucket *p; |
2692 | | |
2693 | 5.46M | IS_CONSISTENT(ht); |
2694 | | |
2695 | 5.46M | h = zend_inline_hash_func(str, len); |
2696 | 5.46M | p = zend_hash_str_find_bucket(ht, str, len, h); |
2697 | 5.46M | return p ? &p->val : NULL; |
2698 | 5.46M | } |
2699 | | |
2700 | | ZEND_API zval* ZEND_FASTCALL zend_hash_index_find(const HashTable *ht, zend_ulong h) |
2701 | 1.50G | { |
2702 | 1.50G | Bucket *p; |
2703 | | |
2704 | 1.50G | IS_CONSISTENT(ht); |
2705 | | |
2706 | 1.50G | if (HT_IS_PACKED(ht)) { |
2707 | 27.2k | if (h < ht->nNumUsed) { |
2708 | 23.8k | zval *zv = ht->arPacked + h; |
2709 | | |
2710 | 23.8k | if (Z_TYPE_P(zv) != IS_UNDEF) { |
2711 | 23.4k | return zv; |
2712 | 23.4k | } |
2713 | 23.8k | } |
2714 | 3.75k | return NULL; |
2715 | 27.2k | } |
2716 | | |
2717 | 1.49G | p = zend_hash_index_find_bucket(ht, h); |
2718 | 1.49G | return p ? &p->val : NULL; |
2719 | 1.50G | } |
2720 | | |
2721 | | ZEND_API zval* ZEND_FASTCALL _zend_hash_index_find(const HashTable *ht, zend_ulong h) |
2722 | 2.86k | { |
2723 | 2.86k | Bucket *p; |
2724 | | |
2725 | 2.86k | IS_CONSISTENT(ht); |
2726 | 2.86k | ZEND_ASSERT(!HT_IS_PACKED(ht)); |
2727 | | |
2728 | 2.86k | p = zend_hash_index_find_bucket(ht, h); |
2729 | 2.86k | return p ? &p->val : NULL; |
2730 | 2.86k | } |
2731 | | |
2732 | | ZEND_API void ZEND_FASTCALL zend_hash_internal_pointer_reset_ex(const HashTable *ht, HashPosition *pos) |
2733 | 3.19k | { |
2734 | 3.19k | IS_CONSISTENT(ht); |
2735 | 3.19k | HT_ASSERT(ht, &ht->nInternalPointer != pos || GC_REFCOUNT(ht) == 1); |
2736 | 3.19k | *pos = _zend_hash_get_valid_pos(ht, 0); |
2737 | 3.19k | } |
2738 | | |
2739 | | |
2740 | | /* This function will be extremely optimized by remembering |
2741 | | * the end of the list |
2742 | | */ |
2743 | | ZEND_API void ZEND_FASTCALL zend_hash_internal_pointer_end_ex(const HashTable *ht, HashPosition *pos) |
2744 | 30 | { |
2745 | 30 | uint32_t idx; |
2746 | | |
2747 | 30 | IS_CONSISTENT(ht); |
2748 | 30 | HT_ASSERT(ht, &ht->nInternalPointer != pos || GC_REFCOUNT(ht) == 1); |
2749 | | |
2750 | 30 | idx = ht->nNumUsed; |
2751 | 30 | if (HT_IS_PACKED(ht)) { |
2752 | 15 | while (idx > 0) { |
2753 | 15 | idx--; |
2754 | 15 | if (Z_TYPE(ht->arPacked[idx]) != IS_UNDEF) { |
2755 | 15 | *pos = idx; |
2756 | 15 | return; |
2757 | 15 | } |
2758 | 15 | } |
2759 | 15 | } else { |
2760 | 15 | while (idx > 0) { |
2761 | 15 | idx--; |
2762 | 15 | if (Z_TYPE(ht->arData[idx].val) != IS_UNDEF) { |
2763 | 15 | *pos = idx; |
2764 | 15 | return; |
2765 | 15 | } |
2766 | 15 | } |
2767 | 15 | } |
2768 | 0 | *pos = ht->nNumUsed; |
2769 | 0 | } |
2770 | | |
2771 | | |
2772 | | ZEND_API zend_result ZEND_FASTCALL zend_hash_move_forward_ex(const HashTable *ht, HashPosition *pos) |
2773 | 1.52k | { |
2774 | 1.52k | uint32_t idx; |
2775 | | |
2776 | 1.52k | IS_CONSISTENT(ht); |
2777 | 1.52k | HT_ASSERT(ht, &ht->nInternalPointer != pos || GC_REFCOUNT(ht) == 1); |
2778 | | |
2779 | 1.52k | idx = _zend_hash_get_valid_pos(ht, *pos); |
2780 | 1.52k | if (idx < ht->nNumUsed) { |
2781 | 1.52k | if (HT_IS_PACKED(ht)) { |
2782 | 341 | while (1) { |
2783 | 341 | idx++; |
2784 | 341 | if (idx >= ht->nNumUsed) { |
2785 | 164 | *pos = ht->nNumUsed; |
2786 | 164 | return SUCCESS; |
2787 | 164 | } |
2788 | 177 | if (Z_TYPE(ht->arPacked[idx]) != IS_UNDEF) { |
2789 | 174 | *pos = idx; |
2790 | 174 | return SUCCESS; |
2791 | 174 | } |
2792 | 177 | } |
2793 | 1.18k | } else { |
2794 | 1.18k | while (1) { |
2795 | 1.18k | idx++; |
2796 | 1.18k | if (idx >= ht->nNumUsed) { |
2797 | 557 | *pos = ht->nNumUsed; |
2798 | 557 | return SUCCESS; |
2799 | 557 | } |
2800 | 631 | if (Z_TYPE(ht->arData[idx].val) != IS_UNDEF) { |
2801 | 626 | *pos = idx; |
2802 | 626 | return SUCCESS; |
2803 | 626 | } |
2804 | 631 | } |
2805 | 1.18k | } |
2806 | 1.52k | } else { |
2807 | 0 | return FAILURE; |
2808 | 0 | } |
2809 | 1.52k | } |
2810 | | |
2811 | | ZEND_API zend_result ZEND_FASTCALL zend_hash_move_backwards_ex(const HashTable *ht, HashPosition *pos) |
2812 | 20 | { |
2813 | 20 | uint32_t idx = *pos; |
2814 | | |
2815 | 20 | IS_CONSISTENT(ht); |
2816 | 20 | HT_ASSERT(ht, &ht->nInternalPointer != pos || GC_REFCOUNT(ht) == 1); |
2817 | | |
2818 | 20 | if (idx < ht->nNumUsed) { |
2819 | 20 | if (HT_IS_PACKED(ht)) { |
2820 | 5 | while (idx > 0) { |
2821 | 5 | idx--; |
2822 | 5 | if (Z_TYPE(ht->arPacked[idx]) != IS_UNDEF) { |
2823 | 5 | *pos = idx; |
2824 | 5 | return SUCCESS; |
2825 | 5 | } |
2826 | 5 | } |
2827 | 15 | } else { |
2828 | 15 | while (idx > 0) { |
2829 | 5 | idx--; |
2830 | 5 | if (Z_TYPE(ht->arData[idx].val) != IS_UNDEF) { |
2831 | 5 | *pos = idx; |
2832 | 5 | return SUCCESS; |
2833 | 5 | } |
2834 | 5 | } |
2835 | 15 | } |
2836 | 10 | *pos = ht->nNumUsed; |
2837 | 10 | return SUCCESS; |
2838 | 20 | } else { |
2839 | 0 | return FAILURE; |
2840 | 0 | } |
2841 | 20 | } |
2842 | | |
2843 | | |
2844 | | /* This function should be made binary safe */ |
2845 | | ZEND_API int ZEND_FASTCALL zend_hash_get_current_key_ex(const HashTable *ht, zend_string **str_index, zend_ulong *num_index, const HashPosition *pos) |
2846 | 737 | { |
2847 | 737 | uint32_t idx; |
2848 | 737 | Bucket *p; |
2849 | | |
2850 | 737 | IS_CONSISTENT(ht); |
2851 | 737 | idx = _zend_hash_get_valid_pos(ht, *pos); |
2852 | 737 | if (idx < ht->nNumUsed) { |
2853 | 478 | if (HT_IS_PACKED(ht)) { |
2854 | 0 | *num_index = idx; |
2855 | 0 | return HASH_KEY_IS_LONG; |
2856 | 0 | } |
2857 | 478 | p = ht->arData + idx; |
2858 | 478 | if (p->key) { |
2859 | 433 | *str_index = p->key; |
2860 | 433 | return HASH_KEY_IS_STRING; |
2861 | 433 | } else { |
2862 | 45 | *num_index = p->h; |
2863 | 45 | return HASH_KEY_IS_LONG; |
2864 | 45 | } |
2865 | 478 | } |
2866 | 259 | return HASH_KEY_NON_EXISTENT; |
2867 | 737 | } |
2868 | | |
2869 | | ZEND_API void ZEND_FASTCALL zend_hash_get_current_key_zval_ex(const HashTable *ht, zval *key, const HashPosition *pos) |
2870 | 633 | { |
2871 | 633 | uint32_t idx; |
2872 | 633 | Bucket *p; |
2873 | | |
2874 | 633 | IS_CONSISTENT(ht); |
2875 | 633 | idx = _zend_hash_get_valid_pos(ht, *pos); |
2876 | 633 | if (idx >= ht->nNumUsed) { |
2877 | 0 | ZVAL_NULL(key); |
2878 | 633 | } else { |
2879 | 633 | if (HT_IS_PACKED(ht)) { |
2880 | 265 | ZVAL_LONG(key, idx); |
2881 | 265 | return; |
2882 | 265 | } |
2883 | 368 | p = ht->arData + idx; |
2884 | 368 | if (p->key) { |
2885 | 238 | ZVAL_STR_COPY(key, p->key); |
2886 | 238 | } else { |
2887 | 130 | ZVAL_LONG(key, p->h); |
2888 | 130 | } |
2889 | 368 | } |
2890 | 633 | } |
2891 | | |
2892 | | ZEND_API int ZEND_FASTCALL zend_hash_get_current_key_type_ex(const HashTable *ht, const HashPosition *pos) |
2893 | 1.48k | { |
2894 | 1.48k | uint32_t idx; |
2895 | 1.48k | Bucket *p; |
2896 | | |
2897 | 1.48k | IS_CONSISTENT(ht); |
2898 | 1.48k | idx = _zend_hash_get_valid_pos(ht, *pos); |
2899 | 1.48k | if (idx < ht->nNumUsed) { |
2900 | 963 | if (HT_IS_PACKED(ht)) { |
2901 | 238 | return HASH_KEY_IS_LONG; |
2902 | 238 | } |
2903 | 725 | p = ht->arData + idx; |
2904 | 725 | if (p->key) { |
2905 | 618 | return HASH_KEY_IS_STRING; |
2906 | 618 | } else { |
2907 | 107 | return HASH_KEY_IS_LONG; |
2908 | 107 | } |
2909 | 725 | } |
2910 | 517 | return HASH_KEY_NON_EXISTENT; |
2911 | 1.48k | } |
2912 | | |
2913 | | |
2914 | | ZEND_API zval* ZEND_FASTCALL zend_hash_get_current_data_ex(const HashTable *ht, const HashPosition *pos) |
2915 | 2.81k | { |
2916 | 2.81k | uint32_t idx; |
2917 | 2.81k | Bucket *p; |
2918 | | |
2919 | 2.81k | IS_CONSISTENT(ht); |
2920 | 2.81k | idx = _zend_hash_get_valid_pos(ht, *pos); |
2921 | 2.81k | if (idx < ht->nNumUsed) { |
2922 | 2.62k | if (HT_IS_PACKED(ht)) { |
2923 | 463 | return &ht->arPacked[idx]; |
2924 | 463 | } |
2925 | 2.16k | p = ht->arData + idx; |
2926 | 2.16k | return &p->val; |
2927 | 2.62k | } else { |
2928 | 183 | return NULL; |
2929 | 183 | } |
2930 | 2.81k | } |
2931 | | |
2932 | | ZEND_API void zend_hash_bucket_swap(Bucket *p, Bucket *q) |
2933 | 27.0k | { |
2934 | 27.0k | zval val; |
2935 | 27.0k | zend_ulong h; |
2936 | 27.0k | zend_string *key; |
2937 | | |
2938 | 27.0k | val = p->val; |
2939 | 27.0k | h = p->h; |
2940 | 27.0k | key = p->key; |
2941 | | |
2942 | 27.0k | p->val = q->val; |
2943 | 27.0k | p->h = q->h; |
2944 | 27.0k | p->key = q->key; |
2945 | | |
2946 | 27.0k | q->val = val; |
2947 | 27.0k | q->h = h; |
2948 | 27.0k | q->key = key; |
2949 | 27.0k | } |
2950 | | |
2951 | | ZEND_API void zend_hash_bucket_renum_swap(Bucket *p, Bucket *q) |
2952 | 154k | { |
2953 | 154k | zval val; |
2954 | | |
2955 | 154k | val = p->val; |
2956 | 154k | p->val = q->val; |
2957 | 154k | q->val = val; |
2958 | 154k | } |
2959 | | |
2960 | | ZEND_API void zend_hash_bucket_packed_swap(Bucket *p, Bucket *q) |
2961 | 0 | { |
2962 | 0 | zval val; |
2963 | 0 | zend_ulong h; |
2964 | |
|
2965 | 0 | val = p->val; |
2966 | 0 | h = p->h; |
2967 | |
|
2968 | 0 | p->val = q->val; |
2969 | 0 | p->h = q->h; |
2970 | |
|
2971 | 0 | q->val = val; |
2972 | 0 | q->h = h; |
2973 | 0 | } |
2974 | | |
2975 | | static void zend_hash_sort_internal(HashTable *ht, sort_func_t sort, bucket_compare_func_t compar, bool renumber) |
2976 | 1.87k | { |
2977 | 1.87k | Bucket *p; |
2978 | 1.87k | uint32_t i, j; |
2979 | | |
2980 | 1.87k | IS_CONSISTENT(ht); |
2981 | | |
2982 | 1.87k | if (!(ht->nNumOfElements>1) && !(renumber && ht->nNumOfElements>0)) { |
2983 | | /* Doesn't require sorting */ |
2984 | 13 | return; |
2985 | 13 | } |
2986 | | |
2987 | 1.86k | if (HT_IS_PACKED(ht)) { |
2988 | 0 | zend_hash_packed_to_hash(ht); // TODO: ??? |
2989 | 0 | } |
2990 | | |
2991 | 1.86k | if (HT_IS_WITHOUT_HOLES(ht)) { |
2992 | | /* Store original order of elements in extra space to allow stable sorting. */ |
2993 | 65.3k | for (i = 0; i < ht->nNumUsed; i++) { |
2994 | 63.4k | Z_EXTRA(ht->arData[i].val) = i; |
2995 | 63.4k | } |
2996 | 1.86k | } else { |
2997 | | /* Remove holes and store original order. */ |
2998 | 0 | for (j = 0, i = 0; j < ht->nNumUsed; j++) { |
2999 | 0 | p = ht->arData + j; |
3000 | 0 | if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) continue; |
3001 | 0 | if (i != j) { |
3002 | 0 | ht->arData[i] = *p; |
3003 | 0 | } |
3004 | 0 | Z_EXTRA(ht->arData[i].val) = i; |
3005 | 0 | i++; |
3006 | 0 | } |
3007 | 0 | ht->nNumUsed = i; |
3008 | 0 | } |
3009 | | |
3010 | 1.86k | if (!HT_IS_PACKED(ht)) { |
3011 | | /* We broke the hash collisions chains overriding Z_NEXT() by Z_EXTRA(). |
3012 | | * Reset the hash headers table as well to avoid possible inconsistent |
3013 | | * access on recursive data structures. |
3014 | | * |
3015 | | * See Zend/tests/bug63882_2.phpt |
3016 | | */ |
3017 | 1.86k | HT_HASH_RESET(ht); |
3018 | 1.86k | } |
3019 | | |
3020 | 1.86k | sort((void *)ht->arData, ht->nNumUsed, sizeof(Bucket), (compare_func_t) compar, |
3021 | 1.86k | (swap_func_t)(renumber? zend_hash_bucket_renum_swap : |
3022 | 1.86k | (HT_IS_PACKED(ht) ? zend_hash_bucket_packed_swap : zend_hash_bucket_swap))); |
3023 | | |
3024 | 1.86k | ht->nInternalPointer = 0; |
3025 | | |
3026 | 1.86k | if (renumber) { |
3027 | 54.4k | for (j = 0; j < i; j++) { |
3028 | 53.2k | p = ht->arData + j; |
3029 | 53.2k | p->h = j; |
3030 | 53.2k | if (p->key) { |
3031 | 2.15k | zend_string_release(p->key); |
3032 | 2.15k | p->key = NULL; |
3033 | 2.15k | } |
3034 | 53.2k | } |
3035 | | |
3036 | 1.22k | ht->nNextFreeElement = i; |
3037 | 1.22k | } |
3038 | 1.86k | if (HT_IS_PACKED(ht)) { |
3039 | 0 | if (!renumber) { |
3040 | 0 | zend_hash_packed_to_hash(ht); |
3041 | 0 | } |
3042 | 1.86k | } else { |
3043 | 1.86k | if (renumber) { |
3044 | 1.22k | void *new_data, *old_data = HT_GET_DATA_ADDR(ht); |
3045 | 1.22k | Bucket *old_buckets = ht->arData; |
3046 | 1.22k | zval *zv; |
3047 | | |
3048 | 1.22k | new_data = pemalloc(HT_PACKED_SIZE_EX(ht->nTableSize, HT_MIN_MASK), (GC_FLAGS(ht) & IS_ARRAY_PERSISTENT)); |
3049 | 1.22k | HT_FLAGS(ht) |= HASH_FLAG_PACKED | HASH_FLAG_STATIC_KEYS; |
3050 | 1.22k | ht->nTableMask = HT_MIN_MASK; |
3051 | 1.22k | HT_SET_DATA_ADDR(ht, new_data); |
3052 | 1.22k | p = old_buckets; |
3053 | 1.22k | zv = ht->arPacked; |
3054 | 77.3k | for (i = 0; i < ht->nTableSize; i++) { |
3055 | 76.1k | ZVAL_COPY_VALUE(zv, &p->val); |
3056 | 76.1k | zv++; |
3057 | 76.1k | p++; |
3058 | 76.1k | } |
3059 | 1.22k | pefree(old_data, GC_FLAGS(ht) & IS_ARRAY_PERSISTENT); |
3060 | 1.22k | HT_HASH_RESET_PACKED(ht); |
3061 | 1.22k | } else { |
3062 | 641 | zend_hash_rehash(ht); |
3063 | 641 | } |
3064 | 1.86k | } |
3065 | 1.86k | } |
3066 | | |
3067 | | ZEND_API void ZEND_FASTCALL zend_hash_sort_ex(HashTable *ht, sort_func_t sort, bucket_compare_func_t compar, bool renumber) |
3068 | 26 | { |
3069 | 26 | HT_ASSERT_RC1(ht); |
3070 | 26 | zend_hash_sort_internal(ht, sort, compar, renumber); |
3071 | 26 | } |
3072 | | |
3073 | | ZEND_API void ZEND_FASTCALL zend_array_sort_ex(HashTable *ht, sort_func_t sort, bucket_compare_func_t compar, bool renumber) |
3074 | 1.85k | { |
3075 | 1.85k | HT_ASSERT_RC1(ht); |
3076 | | |
3077 | | /* Unpack the array early to avoid RCn assertion failures. */ |
3078 | 1.85k | if (HT_IS_PACKED(ht)) { |
3079 | 1.03k | zend_hash_packed_to_hash(ht); |
3080 | 1.03k | } |
3081 | | |
3082 | | /* Adding a refcount prevents the array from going away. */ |
3083 | 1.85k | GC_ADDREF(ht); |
3084 | | |
3085 | 1.85k | zend_hash_sort_internal(ht, sort, compar, renumber); |
3086 | | |
3087 | 1.85k | if (UNEXPECTED(GC_DELREF(ht) == 0)) { |
3088 | 5 | zend_array_destroy(ht); |
3089 | 1.84k | } else { |
3090 | 1.84k | gc_check_possible_root((zend_refcounted *)ht); |
3091 | 1.84k | } |
3092 | 1.85k | } |
3093 | | |
3094 | 12.1k | static zend_always_inline int zend_hash_compare_impl(const HashTable *ht1, const HashTable *ht2, compare_func_t compar, bool ordered) { |
3095 | 12.1k | uint32_t idx1, idx2; |
3096 | 12.1k | zend_string *key1, *key2; |
3097 | 12.1k | zend_ulong h1, h2; |
3098 | 12.1k | zval *pData1, *pData2;; |
3099 | 12.1k | int result; |
3100 | | |
3101 | 12.1k | if (ht1->nNumOfElements != ht2->nNumOfElements) { |
3102 | 8.84k | return ht1->nNumOfElements > ht2->nNumOfElements ? 1 : -1; |
3103 | 8.84k | } |
3104 | | |
3105 | 5.69k | for (idx1 = 0, idx2 = 0; idx1 < ht1->nNumUsed; idx1++) { |
3106 | 4.25k | if (HT_IS_PACKED(ht1)) { |
3107 | 1.82k | pData1 = ht1->arPacked + idx1; |
3108 | 1.82k | h1 = idx1; |
3109 | 1.82k | key1 = NULL; |
3110 | 2.43k | } else { |
3111 | 2.43k | Bucket *p = ht1->arData + idx1; |
3112 | 2.43k | pData1 = &p->val; |
3113 | 2.43k | h1 = p->h; |
3114 | 2.43k | key1 = p->key; |
3115 | 2.43k | } |
3116 | | |
3117 | 4.25k | if (Z_TYPE_P(pData1) == IS_UNDEF) continue; |
3118 | 3.62k | if (ordered) { |
3119 | 1.21k | if (HT_IS_PACKED(ht2)) { |
3120 | 740 | while (1) { |
3121 | 740 | ZEND_ASSERT(idx2 != ht2->nNumUsed); |
3122 | 740 | pData2 = ht2->arPacked + idx2; |
3123 | 740 | h2 = idx2; |
3124 | 740 | key2 = NULL; |
3125 | 740 | if (Z_TYPE_P(pData2) != IS_UNDEF) break; |
3126 | 45 | idx2++; |
3127 | 45 | } |
3128 | 695 | } else { |
3129 | 517 | while (1) { |
3130 | 517 | Bucket *p; |
3131 | 517 | ZEND_ASSERT(idx2 != ht2->nNumUsed); |
3132 | 517 | p = ht2->arData + idx2; |
3133 | 517 | pData2 = &p->val; |
3134 | 517 | h2 = p->h; |
3135 | 517 | key2 = p->key; |
3136 | 517 | if (Z_TYPE_P(pData2) != IS_UNDEF) break; |
3137 | 0 | idx2++; |
3138 | 0 | } |
3139 | 517 | } |
3140 | 1.21k | if (key1 == NULL && key2 == NULL) { /* numeric indices */ |
3141 | 772 | if (h1 != h2) { |
3142 | 310 | return h1 > h2 ? 1 : -1; |
3143 | 310 | } |
3144 | 772 | } else if (key1 != NULL && key2 != NULL) { /* string indices */ |
3145 | 296 | if (ZSTR_LEN(key1) != ZSTR_LEN(key2)) { |
3146 | 79 | return ZSTR_LEN(key1) > ZSTR_LEN(key2) ? 1 : -1; |
3147 | 79 | } |
3148 | | |
3149 | 217 | result = memcmp(ZSTR_VAL(key1), ZSTR_VAL(key2), ZSTR_LEN(key1)); |
3150 | 217 | if (result != 0) { |
3151 | 95 | return result; |
3152 | 95 | } |
3153 | 217 | } else { |
3154 | | /* Mixed key types: A string key is considered as larger */ |
3155 | 144 | return key1 != NULL ? 1 : -1; |
3156 | 144 | } |
3157 | 584 | idx2++; |
3158 | 2.41k | } else { |
3159 | 2.41k | if (key1 == NULL) { /* numeric index */ |
3160 | 1.28k | pData2 = zend_hash_index_find(ht2, h1); |
3161 | 1.28k | if (pData2 == NULL) { |
3162 | 448 | return 1; |
3163 | 448 | } |
3164 | 1.28k | } else { /* string index */ |
3165 | 1.13k | pData2 = zend_hash_find(ht2, key1); |
3166 | 1.13k | if (pData2 == NULL) { |
3167 | 126 | return 1; |
3168 | 126 | } |
3169 | 1.13k | } |
3170 | 2.41k | } |
3171 | | |
3172 | 2.42k | if (Z_TYPE_P(pData1) == IS_INDIRECT) { |
3173 | 39 | pData1 = Z_INDIRECT_P(pData1); |
3174 | 39 | } |
3175 | 2.42k | if (Z_TYPE_P(pData2) == IS_INDIRECT) { |
3176 | 39 | pData2 = Z_INDIRECT_P(pData2); |
3177 | 39 | } |
3178 | | |
3179 | 2.42k | if (Z_TYPE_P(pData1) == IS_UNDEF) { |
3180 | 17 | if (Z_TYPE_P(pData2) != IS_UNDEF) { |
3181 | 0 | return -1; |
3182 | 0 | } |
3183 | 2.40k | } else if (Z_TYPE_P(pData2) == IS_UNDEF) { |
3184 | 0 | return 1; |
3185 | 2.40k | } else { |
3186 | 2.40k | result = compar(pData1, pData2); |
3187 | 2.40k | if (result != 0) { |
3188 | 657 | return result; |
3189 | 657 | } |
3190 | 2.40k | } |
3191 | 2.42k | } |
3192 | | |
3193 | 1.44k | return 0; |
3194 | 3.30k | } |
3195 | | |
3196 | | ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, bool ordered) |
3197 | 12.1k | { |
3198 | 12.1k | int result; |
3199 | 12.1k | IS_CONSISTENT(ht1); |
3200 | 12.1k | IS_CONSISTENT(ht2); |
3201 | | |
3202 | 12.1k | if (ht1 == ht2) { |
3203 | 0 | return 0; |
3204 | 0 | } |
3205 | | |
3206 | | /* It's enough to protect only one of the arrays. |
3207 | | * The second one may be referenced from the first and this may cause |
3208 | | * false recursion detection. |
3209 | | */ |
3210 | 12.1k | if (UNEXPECTED(GC_IS_RECURSIVE(ht1))) { |
3211 | 15 | zend_throw_error(NULL, "Nesting level too deep - recursive dependency?"); |
3212 | 15 | return ZEND_UNCOMPARABLE; |
3213 | 15 | } |
3214 | | |
3215 | 12.1k | GC_TRY_PROTECT_RECURSION(ht1); |
3216 | 12.1k | result = zend_hash_compare_impl(ht1, ht2, compar, ordered); |
3217 | 12.1k | GC_TRY_UNPROTECT_RECURSION(ht1); |
3218 | | |
3219 | 12.1k | return result; |
3220 | 12.1k | } |
3221 | | |
3222 | | |
3223 | | ZEND_API zval* ZEND_FASTCALL zend_hash_minmax(const HashTable *ht, compare_func_t compar, uint32_t flag) |
3224 | 0 | { |
3225 | 0 | uint32_t idx; |
3226 | 0 | zval *res; |
3227 | |
|
3228 | 0 | IS_CONSISTENT(ht); |
3229 | |
|
3230 | 0 | if (ht->nNumOfElements == 0 ) { |
3231 | 0 | return NULL; |
3232 | 0 | } |
3233 | | |
3234 | 0 | if (HT_IS_PACKED(ht)) { |
3235 | 0 | zval *zv; |
3236 | |
|
3237 | 0 | idx = 0; |
3238 | 0 | while (1) { |
3239 | 0 | if (idx == ht->nNumUsed) { |
3240 | 0 | return NULL; |
3241 | 0 | } |
3242 | 0 | if (Z_TYPE(ht->arPacked[idx]) != IS_UNDEF) break; |
3243 | 0 | idx++; |
3244 | 0 | } |
3245 | 0 | res = ht->arPacked + idx; |
3246 | 0 | for (; idx < ht->nNumUsed; idx++) { |
3247 | 0 | zv = ht->arPacked + idx; |
3248 | 0 | if (UNEXPECTED(Z_TYPE_P(zv) == IS_UNDEF)) continue; |
3249 | | |
3250 | 0 | if (flag) { |
3251 | 0 | if (compar(res, zv) < 0) { /* max */ |
3252 | 0 | res = zv; |
3253 | 0 | } |
3254 | 0 | } else { |
3255 | 0 | if (compar(res, zv) > 0) { /* min */ |
3256 | 0 | res = zv; |
3257 | 0 | } |
3258 | 0 | } |
3259 | 0 | } |
3260 | 0 | } else { |
3261 | 0 | Bucket *p; |
3262 | |
|
3263 | 0 | idx = 0; |
3264 | 0 | while (1) { |
3265 | 0 | if (idx == ht->nNumUsed) { |
3266 | 0 | return NULL; |
3267 | 0 | } |
3268 | 0 | if (Z_TYPE(ht->arData[idx].val) != IS_UNDEF) break; |
3269 | 0 | idx++; |
3270 | 0 | } |
3271 | 0 | res = &ht->arData[idx].val; |
3272 | 0 | for (; idx < ht->nNumUsed; idx++) { |
3273 | 0 | p = ht->arData + idx; |
3274 | 0 | if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) continue; |
3275 | | |
3276 | 0 | if (flag) { |
3277 | 0 | if (compar(res, &p->val) < 0) { /* max */ |
3278 | 0 | res = &p->val; |
3279 | 0 | } |
3280 | 0 | } else { |
3281 | 0 | if (compar(res, &p->val) > 0) { /* min */ |
3282 | 0 | res = &p->val; |
3283 | 0 | } |
3284 | 0 | } |
3285 | 0 | } |
3286 | 0 | } |
3287 | 0 | return res; |
3288 | 0 | } |
3289 | | |
3290 | | ZEND_API bool ZEND_FASTCALL _zend_handle_numeric_str_ex(const char *key, size_t length, zend_ulong *idx) |
3291 | 37.4k | { |
3292 | 37.4k | const char *tmp = key; |
3293 | | |
3294 | 37.4k | const char *end = key + length; |
3295 | | |
3296 | 37.4k | if (*tmp == '-') { |
3297 | 8.82k | tmp++; |
3298 | 8.82k | } |
3299 | | |
3300 | 37.4k | if ((*tmp == '0' && length > 1) /* numbers with leading zeros */ |
3301 | 37.4k | || (end - tmp > MAX_LENGTH_OF_LONG - 1) /* number too long */ |
3302 | 37.4k | || (SIZEOF_ZEND_LONG == 4 && |
3303 | 0 | end - tmp == MAX_LENGTH_OF_LONG - 1 && |
3304 | 5.53k | *tmp > '2')) { /* overflow */ |
3305 | 5.53k | return 0; |
3306 | 5.53k | } |
3307 | 31.9k | *idx = (*tmp - '0'); |
3308 | 103k | while (1) { |
3309 | 103k | ++tmp; |
3310 | 103k | if (tmp == end) { |
3311 | 22.5k | if (*key == '-') { |
3312 | 4.27k | if (*idx-1 > ZEND_LONG_MAX) { /* overflow */ |
3313 | 527 | return 0; |
3314 | 527 | } |
3315 | 3.74k | *idx = 0 - *idx; |
3316 | 18.2k | } else if (*idx > ZEND_LONG_MAX) { /* overflow */ |
3317 | 382 | return 0; |
3318 | 382 | } |
3319 | 21.6k | return 1; |
3320 | 22.5k | } |
3321 | 80.9k | if (*tmp <= '9' && *tmp >= '0') { |
3322 | 71.6k | *idx = (*idx * 10) + (*tmp - '0'); |
3323 | 71.6k | } else { |
3324 | 9.37k | return 0; |
3325 | 9.37k | } |
3326 | 80.9k | } |
3327 | 31.9k | } |
3328 | | |
3329 | | /* Takes a "symtable" hashtable (contains integer and non-numeric string keys) |
3330 | | * and converts it to a "proptable" (contains only string keys). |
3331 | | * If the symtable didn't need duplicating, its refcount is incremented. |
3332 | | */ |
3333 | | ZEND_API HashTable* ZEND_FASTCALL zend_symtable_to_proptable(HashTable *ht) |
3334 | 245 | { |
3335 | 245 | zend_ulong num_key; |
3336 | 245 | zend_string *str_key; |
3337 | 245 | zval *zv; |
3338 | | |
3339 | 245 | if (UNEXPECTED(HT_IS_PACKED(ht))) { |
3340 | 21 | goto convert; |
3341 | 21 | } |
3342 | | |
3343 | 1.18k | ZEND_HASH_MAP_FOREACH_STR_KEY(ht, str_key) { |
3344 | 1.18k | if (!str_key) { |
3345 | 9 | goto convert; |
3346 | 9 | } |
3347 | 1.18k | } ZEND_HASH_FOREACH_END(); |
3348 | | |
3349 | 215 | if (!(GC_FLAGS(ht) & IS_ARRAY_IMMUTABLE)) { |
3350 | 33 | GC_ADDREF(ht); |
3351 | 33 | } |
3352 | | |
3353 | 215 | return ht; |
3354 | | |
3355 | 30 | convert: |
3356 | 30 | { |
3357 | 30 | HashTable *new_ht = zend_new_array(zend_hash_num_elements(ht)); |
3358 | | |
3359 | 192 | ZEND_HASH_FOREACH_KEY_VAL(ht, num_key, str_key, zv) { |
3360 | 192 | if (!str_key) { |
3361 | 72 | str_key = zend_long_to_str(num_key); |
3362 | 72 | zend_string_delref(str_key); |
3363 | 72 | } |
3364 | 192 | do { |
3365 | 81 | if (Z_OPT_REFCOUNTED_P(zv)) { |
3366 | 0 | if (Z_ISREF_P(zv) && Z_REFCOUNT_P(zv) == 1) { |
3367 | 0 | zv = Z_REFVAL_P(zv); |
3368 | 0 | if (!Z_OPT_REFCOUNTED_P(zv)) { |
3369 | 0 | break; |
3370 | 0 | } |
3371 | 0 | } |
3372 | 0 | Z_ADDREF_P(zv); |
3373 | 0 | } |
3374 | 81 | } while (0); |
3375 | 0 | zend_hash_update(new_ht, str_key, zv); |
3376 | 192 | } ZEND_HASH_FOREACH_END(); |
3377 | | |
3378 | 30 | return new_ht; |
3379 | 224 | } |
3380 | 224 | } |
3381 | | |
3382 | | /* Takes a "proptable" hashtable (contains only string keys) and converts it to |
3383 | | * a "symtable" (contains integer and non-numeric string keys). |
3384 | | * If the proptable didn't need duplicating, its refcount is incremented. |
3385 | | */ |
3386 | | ZEND_API HashTable* ZEND_FASTCALL zend_proptable_to_symtable(HashTable *ht, bool always_duplicate) |
3387 | 2.67k | { |
3388 | 2.67k | zend_ulong num_key; |
3389 | 2.67k | zend_string *str_key; |
3390 | 2.67k | zval *zv; |
3391 | | |
3392 | 2.67k | if (!HT_IS_PACKED(ht)) { |
3393 | 54.5k | ZEND_HASH_MAP_FOREACH_STR_KEY(ht, str_key) { |
3394 | | /* The `str_key &&` here might seem redundant: property tables should |
3395 | | * only have string keys. Unfortunately, this isn't true, at the very |
3396 | | * least because of ArrayObject, which stores a symtable where the |
3397 | | * property table should be. |
3398 | | */ |
3399 | 54.5k | if (str_key && ZEND_HANDLE_NUMERIC(str_key, num_key)) { |
3400 | 739 | goto convert; |
3401 | 739 | } |
3402 | 54.5k | } ZEND_HASH_FOREACH_END(); |
3403 | 2.67k | } |
3404 | | |
3405 | 1.93k | if (always_duplicate) { |
3406 | 1.92k | return zend_array_dup(ht); |
3407 | 1.92k | } |
3408 | | |
3409 | 5 | if (EXPECTED(!(GC_FLAGS(ht) & IS_ARRAY_IMMUTABLE))) { |
3410 | 5 | GC_ADDREF(ht); |
3411 | 5 | } |
3412 | | |
3413 | 5 | return ht; |
3414 | | |
3415 | 739 | convert: |
3416 | 739 | { |
3417 | 739 | HashTable *new_ht = zend_new_array(zend_hash_num_elements(ht)); |
3418 | | |
3419 | 24.8k | ZEND_HASH_MAP_FOREACH_KEY_VAL_IND(ht, num_key, str_key, zv) { |
3420 | 24.8k | do { |
3421 | 10.5k | if (Z_OPT_REFCOUNTED_P(zv)) { |
3422 | 5.98k | if (Z_ISREF_P(zv) && Z_REFCOUNT_P(zv) == 1) { |
3423 | 66 | zv = Z_REFVAL_P(zv); |
3424 | 66 | if (!Z_OPT_REFCOUNTED_P(zv)) { |
3425 | 3 | break; |
3426 | 3 | } |
3427 | 66 | } |
3428 | 5.97k | Z_ADDREF_P(zv); |
3429 | 5.97k | } |
3430 | 10.5k | } while (0); |
3431 | | /* Again, thank ArrayObject for `!str_key ||`. */ |
3432 | 10.5k | if (!str_key || ZEND_HANDLE_NUMERIC(str_key, num_key)) { |
3433 | 1.79k | zend_hash_index_update(new_ht, num_key, zv); |
3434 | 8.75k | } else { |
3435 | 8.75k | zend_hash_update(new_ht, str_key, zv); |
3436 | 8.75k | } |
3437 | 24.8k | } ZEND_HASH_FOREACH_END(); |
3438 | | |
3439 | 739 | return new_ht; |
3440 | 739 | } |
3441 | 739 | } |