Coverage Report

Created: 2025-06-13 06:43

/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
}