1 #ifndef IGBINARY_ZEND_HASH
2 #define IGBINARY_ZEND_HASH
3 /*
4 +----------------------------------------------------------------------+
5 | igbinary optimizations for find_or_insert adapted from Zend Engine. |
6 | Adaptations written by Tyson Andre for igbinary. |
7 | original license of php-src/Zend/zend_hash.c is below. |
8 +----------------------------------------------------------------------+
9 | Zend Engine |
10 +----------------------------------------------------------------------+
11 | Copyright (c) 1998-2018 Zend Technologies Ltd. (http://www.zend.com) |
12 +----------------------------------------------------------------------+
13 | This source file is subject to version 2.00 of the Zend license, |
14 | that is bundled with this package in the file LICENSE, and is |
15 | available through the world-wide-web at the following url: |
16 | http://www.zend.com/license/2_00.txt. |
17 | If you did not receive a copy of the Zend license and are unable to |
18 | obtain it through the world-wide-web, please send a note to |
19 | license@zend.com so we can mail you a copy immediately. |
20 +----------------------------------------------------------------------+
21 | Authors: Andi Gutmans <andi@zend.com> |
22 | Zeev Suraski <zeev@zend.com> |
23 | Dmitry Stogov <dmitry@zend.com> |
24 +----------------------------------------------------------------------+
25 */
26
27 /* See https://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html for an overview of PHP's hash table information */
28
29 #if PHP_VERSION_ID < 70200 || PHP_VERSION_ID >= 80100 || IGBINARY_FORCE_REFERENCE_HASH_TABLE_FUNCTIONS
30 /* {{{ igbinary_zend_hash_add_or_find(HashTable *ht, zend_string *key) unoptimized reference implementation. */
31 /* This will either return the pointer to the existing value, or add a brand new entry to the hash table with a PHP IS_NULL value. */
igbinary_zend_hash_add_or_find(HashTable * ht,zend_string * key)32 static zend_always_inline zval *igbinary_zend_hash_add_or_find(HashTable *ht, zend_string *key) {
33 zval *vp;
34 zval val;
35 if (UNEXPECTED((vp = zend_hash_find(ht, key)) != NULL)) {
36 return vp;
37 }
38 ZVAL_NULL(&val);
39 return zend_hash_add_new(ht, key, &val);
40 }
41 /* }}} */
42 /* {{{ igbinary_zend_hash_add_or_find(HashTable *ht, zend_long key) unoptimized reference implementation. */
43 /* This will either return the pointer to the existing value, or add a brand new entry to the hash table with a PHP IS_NULL value. */
igbinary_zend_hash_index_add_or_find(HashTable * ht,zend_long key)44 static zend_always_inline zval *igbinary_zend_hash_index_add_or_find(HashTable *ht, zend_long key) {
45 zval *vp;
46 zval val;
47 if (UNEXPECTED((vp = zend_hash_index_find(ht, key)) != NULL)) {
48 return vp;
49 }
50 ZVAL_NULL(&val);
51 return zend_hash_index_add_new(ht, key, &val);
52 }
53 /* }}} */
54
55 /* This is either too old to bother implementing specializations for, or too new for the HashTable implementation to be finalized and tested */
56
57 #else
58 /* PHP 7.2 to 8.0 */
59
60 #if PHP_VERSION_ID < 70300
61 # define IS_ARRAY_PERSISTENT HASH_FLAG_PERSISTENT
62 # define zend_hash_real_init_mixed(ht) zend_hash_real_init((ht), 0)
63 # define zend_hash_real_init_packed(ht) zend_hash_real_init((ht), 1)
64 # define HT_SIZE_TO_MASK(size) (-(size))
65 # define HT_FLAGS(ht) ((ht)->u.flags)
zend_string_equal_content(zend_string * s1,zend_string * s2)66 static zend_always_inline zend_bool zend_string_equal_content(zend_string *s1, zend_string *s2)
67 {
68 return ZSTR_LEN(s1) == ZSTR_LEN(s2) && !memcmp(ZSTR_VAL(s1), ZSTR_VAL(s2), ZSTR_LEN(s1));
69 }
70 #endif /* PHP_VERSION_ID < 70300 */
71
72 /* {{{ igbinary_zend_hash_find_bucket(const HashTable *ht, zend_string *key, zend_bool known_hash) */
igbinary_zend_hash_find_bucket(const HashTable * ht,zend_string * key,zend_bool known_hash)73 static zend_always_inline Bucket *igbinary_zend_hash_find_bucket(const HashTable *ht, zend_string *key, zend_bool known_hash)
74 {
75 zend_ulong h;
76 uint32_t nIndex;
77 uint32_t idx;
78 Bucket *p, *arData;
79
80 if (known_hash) {
81 h = ZSTR_H(key);
82 } else {
83 h = zend_string_hash_val(key);
84 }
85 arData = ht->arData;
86 nIndex = h | ht->nTableMask;
87 idx = HT_HASH_EX(arData, nIndex);
88
89 if (UNEXPECTED(idx == HT_INVALID_IDX)) {
90 return NULL;
91 }
92 p = HT_HASH_TO_BUCKET_EX(arData, idx);
93 if (p->key == key) { /* check for the same interned string */
94 return p;
95 }
96
97 while (1) {
98 if (p->h == ZSTR_H(key) &&
99 EXPECTED(p->key) &&
100 zend_string_equal_content(p->key, key)) {
101 return p;
102 }
103 idx = Z_NEXT(p->val);
104 if (idx == HT_INVALID_IDX) {
105 return NULL;
106 }
107 p = HT_HASH_TO_BUCKET_EX(arData, idx);
108 if (p->key == key) { /* check for the same interned string */
109 return p;
110 }
111 }
112 }
113 /* }}} */
114 /* {{{ void igbinary_zend_hash_do_resize(HashTable *ht) */
igbinary_zend_hash_do_resize(HashTable * ht)115 static void ZEND_FASTCALL igbinary_zend_hash_do_resize(HashTable *ht)
116 {
117
118 // IS_CONSISTENT(ht);
119 // HT_ASSERT_RC1(ht);
120
121 if (ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)) { /* additional term is there to amortize the cost of compaction */
122 zend_hash_rehash(ht);
123 } else if (ht->nTableSize < HT_MAX_SIZE) { /* Let's double the table size */
124 void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
125 uint32_t nSize = ht->nTableSize + ht->nTableSize;
126 Bucket *old_buckets = ht->arData;
127
128 ht->nTableSize = nSize;
129 #if PHP_VERSION_ID >= 70300
130 new_data = pemalloc(HT_SIZE_EX(nSize, HT_SIZE_TO_MASK(nSize)), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT);
131 #else
132 new_data = pemalloc(HT_SIZE(ht), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT);
133 #endif
134 ht->nTableMask = HT_SIZE_TO_MASK(ht->nTableSize);
135 HT_SET_DATA_ADDR(ht, new_data);
136 memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
137 pefree(old_data, GC_FLAGS(ht) & IS_ARRAY_PERSISTENT);
138 zend_hash_rehash(ht);
139 } else {
140 zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%u * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket) + sizeof(uint32_t), sizeof(Bucket));
141 }
142 }
143 /* }}} */
zend_hash_packed_grow(HashTable * ht)144 static void ZEND_FASTCALL zend_hash_packed_grow(HashTable *ht) /* {{{ */
145 {
146 // HT_ASSERT_RC1(ht);
147 if (ht->nTableSize >= HT_MAX_SIZE) {
148 zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%u * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket), sizeof(Bucket));
149 }
150 ht->nTableSize += ht->nTableSize;
151 HT_SET_DATA_ADDR(ht, perealloc2(HT_GET_DATA_ADDR(ht), HT_SIZE_EX(ht->nTableSize, HT_MIN_MASK), HT_USED_SIZE(ht), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT));
152 }
153 /* }}} */
zend_hash_index_find_bucket(const HashTable * ht,zend_ulong h)154 static zend_always_inline Bucket *zend_hash_index_find_bucket(const HashTable *ht, zend_ulong h) /* {{{ */
155 {
156 uint32_t nIndex;
157 uint32_t idx;
158 Bucket *p, *arData;
159
160 arData = ht->arData;
161 nIndex = h | ht->nTableMask;
162 idx = HT_HASH_EX(arData, nIndex);
163 while (idx != HT_INVALID_IDX) {
164 ZEND_ASSERT(idx < HT_IDX_TO_HASH(ht->nTableSize));
165 p = HT_HASH_TO_BUCKET_EX(arData, idx);
166 if (p->h == h && !p->key) {
167 return p;
168 }
169 idx = Z_NEXT(p->val);
170 }
171 return NULL;
172 } /* }}} */
173
174 /* Methods used by igbinary.c */
175 /* {{{ zval *igbinary_zend_hash_add_or_find(HashTable *ht, zend_string *key) */
176 /* Source: zend_hash_add_or_update_i with adaptions */
igbinary_zend_hash_add_or_find(HashTable * ht,zend_string * key)177 static zend_always_inline zval *igbinary_zend_hash_add_or_find(HashTable *ht, zend_string *key)
178 {
179 zend_ulong h;
180 uint32_t nIndex;
181 uint32_t idx;
182 Bucket *p, *arData;
183
184 // IS_CONSISTENT(ht);
185 // HT_ASSERT_RC1(ht);
186
187 #if PHP_VERSION_ID >= 70400
188 if (UNEXPECTED(HT_FLAGS(ht) & (HASH_FLAG_UNINITIALIZED|HASH_FLAG_PACKED)))
189 #else
190 if (UNEXPECTED(((HT_FLAGS(ht) ^ HASH_FLAG_INITIALIZED) & (HASH_FLAG_INITIALIZED|HASH_FLAG_PACKED))))
191 #endif
192 {
193 #if PHP_VERSION_ID >= 70400
194 if (EXPECTED(HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED))
195 #else
196 if (EXPECTED(!(HT_FLAGS(ht) & HASH_FLAG_INITIALIZED)))
197 #endif
198 {
199 zend_hash_real_init_mixed(ht);
200 if (!ZSTR_IS_INTERNED(key)) {
201 zend_string_addref(key);
202 HT_FLAGS(ht) &= ~HASH_FLAG_STATIC_KEYS;
203 zend_string_hash_val(key);
204 }
205 goto add_to_hash;
206 } else {
207 zend_hash_packed_to_hash(ht);
208 if (!ZSTR_IS_INTERNED(key)) {
209 zend_string_addref(key);
210 HT_FLAGS(ht) &= ~HASH_FLAG_STATIC_KEYS;
211 zend_string_hash_val(key);
212 }
213 }
214 } else {
215 p = igbinary_zend_hash_find_bucket(ht, key, 0);
216
217 if (p) {
218 return &p->val;
219 }
220 if (!ZSTR_IS_INTERNED(key)) {
221 zend_string_addref(key);
222 HT_FLAGS(ht) &= ~HASH_FLAG_STATIC_KEYS;
223 }
224 }
225
226 /* If the Hash table is full, resize it */
227 if ((ht)->nNumUsed >= (ht)->nTableSize) {
228 igbinary_zend_hash_do_resize(ht);
229 }
230
231 add_to_hash:
232 idx = ht->nNumUsed++;
233 ht->nNumOfElements++;
234 #if PHP_VERSION_ID < 70300
235 if (ht->nInternalPointer == HT_INVALID_IDX) {
236 ht->nInternalPointer = idx;
237 }
238 zend_hash_iterators_update(ht, HT_INVALID_IDX, idx);
239 #endif
240 arData = ht->arData;
241 p = arData + idx;
242 p->key = key;
243 p->h = h = ZSTR_H(key);
244 nIndex = h | ht->nTableMask;
245 Z_NEXT(p->val) = HT_HASH_EX(arData, nIndex);
246 HT_HASH_EX(arData, nIndex) = HT_IDX_TO_HASH(idx);
247 ZVAL_NULL(&p->val);
248
249 return &p->val;
250 }
251 /* }}} */
igbinary_zend_hash_index_add_or_find(HashTable * ht,zend_ulong h)252 static zend_always_inline zval *igbinary_zend_hash_index_add_or_find(HashTable *ht, zend_ulong h) /* {{{ */
253 {
254 uint32_t nIndex;
255 uint32_t idx;
256 Bucket *p;
257
258 // IS_CONSISTENT(ht);
259 // HT_ASSERT_RC1(ht);
260
261 if (HT_FLAGS(ht) & HASH_FLAG_PACKED) {
262 if (h < ht->nNumUsed) {
263 p = ht->arData + h;
264 if (Z_TYPE(p->val) != IS_UNDEF) {
265 replace:
266 return &p->val;
267 } else { /* we have to keep the order :( */
268 goto convert_to_hash;
269 }
270 } else if (EXPECTED(h < ht->nTableSize)) {
271 add_to_packed:
272 p = ht->arData + h;
273 /* incremental initialization of empty Buckets */
274 if (h > ht->nNumUsed) {
275 Bucket *q = ht->arData + ht->nNumUsed;
276 while (q != p) {
277 ZVAL_UNDEF(&q->val);
278 q++;
279 }
280 }
281 ht->nNextFreeElement = ht->nNumUsed = h + 1;
282 goto add;
283 } else if ((h >> 1) < ht->nTableSize &&
284 (ht->nTableSize >> 1) < ht->nNumOfElements) {
285 zend_hash_packed_grow(ht);
286 goto add_to_packed;
287 } else {
288 if (ht->nNumUsed >= ht->nTableSize) {
289 ht->nTableSize += ht->nTableSize;
290 }
291 convert_to_hash:
292 zend_hash_packed_to_hash(ht);
293 }
294 #if PHP_VERSION_ID >= 70400
295 } else if (HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED) {
296 #else
297 } else if (!(HT_FLAGS(ht) & HASH_FLAG_INITIALIZED)) {
298 #endif
299 if (h < ht->nTableSize) {
300 zend_hash_real_init_packed(ht);
301 goto add_to_packed;
302 }
303 zend_hash_real_init_mixed(ht);
304 } else {
305 p = zend_hash_index_find_bucket(ht, h);
306 if (p) {
307 goto replace;
308 }
309 /* If the Hash table is full, resize it */
310 if ((ht)->nNumUsed >= (ht)->nTableSize) {
311 igbinary_zend_hash_do_resize(ht);
312 }
313 }
314
315 idx = ht->nNumUsed++;
316 nIndex = h | ht->nTableMask;
317 p = ht->arData + idx;
318 Z_NEXT(p->val) = HT_HASH(ht, nIndex);
319 HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);
320 if ((zend_long)h >= ht->nNextFreeElement) {
321 ht->nNextFreeElement = (zend_long)h < ZEND_LONG_MAX ? h + 1 : ZEND_LONG_MAX;
322 }
323 add:
324 ht->nNumOfElements++;
325 #if PHP_VERSION_ID < 70300
326 if (ht->nInternalPointer == HT_INVALID_IDX) {
327 ht->nInternalPointer = ht->nNumUsed - 1;
328 }
329 zend_hash_iterators_update(ht, HT_INVALID_IDX, ht->nNumUsed - 1);
330 #endif
331 p->h = h;
332 p->key = NULL;
333 ZVAL_NULL(&p->val);
334
335 return &p->val;
336 }
337 /* }}} */
338
339 #endif /* PHP 7.2 to 8.0 */
340 /*
341 * Local variables:
342 * tab-width: 2
343 * c-basic-offset: 4
344 * End:
345 * vim600: noet sw=4 ts=4 fdm=marker
346 * vim<600: noet sw=4 ts=4
347 */
348 #endif /* IGBINARY_ZEND_HASH */
349