xref: /unit/src/nxt_lvlhsh.c (revision 0:a63ceefd6ab0)
1 
2 /*
3  * Copyright (C) Igor Sysoev
4  * Copyright (C) NGINX, Inc.
5  */
6 
7 #include <nxt_main.h>
8 
9 
10 /*
11  * The level hash consists of hierarchical levels of arrays of pointers.
12  * The pointers may point to another level, a bucket, or NULL.
13  * The levels and buckets must be allocated in manner alike posix_memalign()
14  * to bookkeep additional information in pointer low bits.
15  *
16  * A level is an array of pointers.  Its size is a power of 2.  Levels
17  * may be different sizes, but on the same level the sizes are the same.
18  * Level sizes are specified by number of bits per level in lvlhsh->shift
19  * array.  A hash may have up to 7 levels.  There are two predefined
20  * shift arrays given by the first two shift array values:
21  *
22  * 1) [0, 0]:  [4, 4, 4, 4, 4, 4, 4] on a 64-bit platform or
23  *             [5, 5, 5, 5, 5, 5, 0] on a 32-bit platform,
24  *    so default size of levels is 128 bytes.
25  *
26  * 2) [0, 10]: [10, 4, 4, 4, 4, 4, 0] on a 64-bit platform or
27  *             [10, 5, 5, 5, 5, 0, 0] on a 32-bit platform,
28  *    so default size of levels is 128 bytes on all levels except
29  *    the first level.  The first level is 8K or 4K on 64-bit or 32-bit
30  *    platforms respectively.
31  *
32  * All buckets in a hash are the same size which is a power of 2.
33  * A bucket contains several entries stored and tested sequentially.
34  * The bucket size should be one or two CPU cache line size, a minimum
35  * allowed size is 32 bytes.  A default 128-byte bucket contains 10 64-bit
36  * entries or 15 32-bit entries.  Each entry consists of pointer to value
37  * data and 32-bit key.  If an entry value pointer is NULL, the entry is free.
38  * On a 64-bit platform entry value pointers are no aligned, therefore they
39  * are accessed as two 32-bit integers.  The rest trailing space in a bucket
40  * is used as pointer to next bucket and this pointer is always aligned.
41  * Although the level hash allows to store a lot of values in a bucket chain,
42  * this is non optimal way.  The large data set should be stored using
43  * several levels.
44  */
45 
46 #define                                                                       \
47 nxt_lvlhsh_is_bucket(p)                                                       \
48     ((uintptr_t) (p) & 1)
49 
50 
51 #define                                                                       \
52 nxt_lvlhsh_count_inc(n)                                                       \
53     n = (void *) ((uintptr_t) (n) + 2)
54 
55 
56 #define                                                                       \
57 nxt_lvlhsh_count_dec(n)                                                       \
58     n = (void *) ((uintptr_t) (n) - 2)
59 
60 
61 #define                                                                       \
62 nxt_lvlhsh_level_size(proto, nlvl)                                            \
63     ((uintptr_t) 1 << proto->shift[nlvl])
64 
65 
66 #define                                                                       \
67 nxt_lvlhsh_level(lvl, mask)                                                   \
68     (void **) ((uintptr_t) lvl & (~mask << 2))
69 
70 
71 #define                                                                       \
72 nxt_lvlhsh_level_entries(lvl, mask)                                           \
73     ((uintptr_t) lvl & (mask << 1))
74 
75 
76 #define                                                                       \
77 nxt_lvlhsh_store_bucket(slot, bkt)                                            \
78     slot = (void **) ((uintptr_t) bkt | 2 | 1)
79 
80 
81 #define                                                                       \
82 nxt_lvlhsh_bucket_size(proto)                                                 \
83     proto->bucket_size
84 
85 
86 #define                                                                       \
87 nxt_lvlhsh_bucket(proto, bkt)                                                 \
88     (uint32_t *) ((uintptr_t) bkt & ~(uintptr_t) proto->bucket_mask)
89 
90 
91 #define                                                                       \
92 nxt_lvlhsh_bucket_entries(proto, bkt)                                         \
93     (((uintptr_t) bkt & (uintptr_t) proto->bucket_mask) >> 1)
94 
95 
96 #define                                                                       \
97 nxt_lvlhsh_bucket_end(proto, bkt)                                             \
98     &bkt[proto->bucket_end]
99 
100 
101 #define                                                                       \
102 nxt_lvlhsh_free_entry(e)                                                      \
103     (!(nxt_lvlhsh_valid_entry(e)))
104 
105 
106 #define                                                                       \
107 nxt_lvlhsh_next_bucket(proto, bkt)                                            \
108     ((void **) &bkt[proto->bucket_end])
109 
110 #if (NXT_64BIT)
111 
112 #define                                                                       \
113 nxt_lvlhsh_valid_entry(e)                                                     \
114     (((e)[0] | (e)[1]) != 0)
115 
116 
117 #define                                                                       \
118 nxt_lvlhsh_entry_value(e)                                                     \
119     (void *) (((uintptr_t) (e)[1] << 32) + (e)[0])
120 
121 
122 #define                                                                       \
123 nxt_lvlhsh_set_entry_value(e, n)                                              \
124     (e)[0] = (uint32_t)  (uintptr_t) n;                                       \
125     (e)[1] = (uint32_t) ((uintptr_t) n >> 32)
126 
127 
128 #define                                                                       \
129 nxt_lvlhsh_entry_key(e)                                                       \
130     (e)[2]
131 
132 
133 #define                                                                       \
134 nxt_lvlhsh_set_entry_key(e, n)                                                \
135     (e)[2] = n
136 
137 #else
138 
139 #define                                                                       \
140 nxt_lvlhsh_valid_entry(e)                                                     \
141     ((e)[0] != 0)
142 
143 
144 #define                                                                       \
145 nxt_lvlhsh_entry_value(e)                                                     \
146     (void *) (e)[0]
147 
148 
149 #define                                                                       \
150 nxt_lvlhsh_set_entry_value(e, n)                                              \
151     (e)[0] = (uint32_t) n
152 
153 
154 #define                                                                       \
155 nxt_lvlhsh_entry_key(e)                                                       \
156     (e)[1]
157 
158 
159 #define                                                                       \
160 nxt_lvlhsh_set_entry_key(e, n)                                                \
161     (e)[1] = n
162 
163 #endif
164 
165 
166 #define NXT_LVLHSH_BUCKET_DONE  ((void *) -1)
167 
168 
169 static nxt_int_t nxt_lvlhsh_level_find(nxt_lvlhsh_query_t *lhq, void **lvl,
170     uint32_t key, nxt_uint_t nlvl);
171 static nxt_int_t nxt_lvlhsh_bucket_find(nxt_lvlhsh_query_t *lhq, void **bkt);
172 static nxt_int_t nxt_lvlhsh_new_bucket(nxt_lvlhsh_query_t *lhq, void **slot);
173 static nxt_int_t nxt_lvlhsh_level_insert(nxt_lvlhsh_query_t *lhq,
174     void **slot, uint32_t key, nxt_uint_t nlvl);
175 static nxt_int_t nxt_lvlhsh_bucket_insert(nxt_lvlhsh_query_t *lhq,
176     void **slot, uint32_t key, nxt_int_t nlvl);
177 static nxt_int_t nxt_lvlhsh_convert_bucket_to_level(nxt_lvlhsh_query_t *lhq,
178     void **slot, nxt_uint_t nlvl, uint32_t *bucket);
179 static nxt_int_t nxt_lvlhsh_level_convertion_insert(nxt_lvlhsh_query_t *lhq,
180     void **parent, uint32_t key, nxt_uint_t nlvl);
181 static nxt_int_t nxt_lvlhsh_bucket_convertion_insert(nxt_lvlhsh_query_t *lhq,
182     void **slot, uint32_t key, nxt_int_t nlvl);
183 static nxt_int_t nxt_lvlhsh_free_level(nxt_lvlhsh_query_t *lhq, void **level,
184     nxt_uint_t size);
185 static nxt_int_t nxt_lvlhsh_level_delete(nxt_lvlhsh_query_t *lhq, void **slot,
186     uint32_t key, nxt_uint_t nlvl);
187 static nxt_int_t nxt_lvlhsh_bucket_delete(nxt_lvlhsh_query_t *lhq, void **bkt);
188 static void *nxt_lvlhsh_level_each(nxt_lvlhsh_each_t *lhe, void **level,
189     nxt_uint_t nlvl, nxt_uint_t shift);
190 static void *nxt_lvlhsh_bucket_each(nxt_lvlhsh_each_t *lhe);
191 
192 
193 nxt_int_t
194 nxt_lvlhsh_find(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq)
195 {
196     void  *slot;
197 
198     slot = lh->slot;
199 
200     if (nxt_fast_path(slot != NULL)) {
201 
202         if (nxt_lvlhsh_is_bucket(slot)) {
203             return nxt_lvlhsh_bucket_find(lhq, slot);
204         }
205 
206         return nxt_lvlhsh_level_find(lhq, slot, lhq->key_hash, 0);
207     }
208 
209     return NXT_DECLINED;
210 }
211 
212 
213 static nxt_int_t
214 nxt_lvlhsh_level_find(nxt_lvlhsh_query_t *lhq, void **lvl, uint32_t key,
215     nxt_uint_t nlvl)
216 {
217     void        **slot;
218     uintptr_t   mask;
219     nxt_uint_t  shift;
220 
221     shift = lhq->proto->shift[nlvl];
222     mask = ((uintptr_t) 1 << shift) - 1;
223 
224     lvl = nxt_lvlhsh_level(lvl, mask);
225     slot = lvl[key & mask];
226 
227     if (slot != NULL) {
228 
229         if (nxt_lvlhsh_is_bucket(slot)) {
230             return nxt_lvlhsh_bucket_find(lhq, slot);
231         }
232 
233         return nxt_lvlhsh_level_find(lhq, slot, key >> shift, nlvl + 1);
234     }
235 
236     return NXT_DECLINED;
237 }
238 
239 
240 static nxt_int_t
241 nxt_lvlhsh_bucket_find(nxt_lvlhsh_query_t *lhq, void **bkt)
242 {
243     void        *value;
244     uint32_t    *bucket, *e;
245     nxt_uint_t  n;
246 
247     do {
248         bucket = nxt_lvlhsh_bucket(lhq->proto, bkt);
249         n = nxt_lvlhsh_bucket_entries(lhq->proto, bkt);
250         e = bucket;
251 
252         do {
253             if (nxt_lvlhsh_valid_entry(e)) {
254                 n--;
255 
256                 if (nxt_lvlhsh_entry_key(e) == lhq->key_hash) {
257 
258                     value = nxt_lvlhsh_entry_value(e);
259 
260                     if (lhq->proto->test(lhq, value) == NXT_OK) {
261                         lhq->value = value;
262 
263                         return NXT_OK;
264                     }
265                 }
266             }
267 
268             e += NXT_LVLHSH_ENTRY_SIZE;
269 
270         } while (n != 0);
271 
272         bkt = *nxt_lvlhsh_next_bucket(lhq->proto, bucket);
273 
274     } while (bkt != NULL);
275 
276     return NXT_DECLINED;
277 }
278 
279 
280 nxt_int_t
281 nxt_lvlhsh_insert(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq)
282 {
283     uint32_t  key;
284 
285     if (nxt_fast_path(lh->slot != NULL)) {
286 
287         key = lhq->key_hash;
288 
289         if (nxt_lvlhsh_is_bucket(lh->slot)) {
290             return nxt_lvlhsh_bucket_insert(lhq, &lh->slot, key, -1);
291         }
292 
293         return nxt_lvlhsh_level_insert(lhq, &lh->slot, key, 0);
294     }
295 
296     return nxt_lvlhsh_new_bucket(lhq, &lh->slot);
297 }
298 
299 
300 static nxt_int_t
301 nxt_lvlhsh_new_bucket(nxt_lvlhsh_query_t *lhq, void **slot)
302 {
303     uint32_t  *bucket;
304 
305     bucket = lhq->proto->alloc(lhq->pool, nxt_lvlhsh_bucket_size(lhq->proto),
306                                lhq->proto->nalloc);
307 
308     if (nxt_fast_path(bucket != NULL)) {
309 
310         nxt_lvlhsh_set_entry_value(bucket, lhq->value);
311         nxt_lvlhsh_set_entry_key(bucket, lhq->key_hash);
312 
313         *nxt_lvlhsh_next_bucket(lhq->proto, bucket) = NULL;
314 
315         nxt_lvlhsh_store_bucket(*slot, bucket);
316 
317         return NXT_OK;
318     }
319 
320     return NXT_ERROR;
321 }
322 
323 
324 static nxt_int_t
325 nxt_lvlhsh_level_insert(nxt_lvlhsh_query_t *lhq, void **parent, uint32_t key,
326     nxt_uint_t nlvl)
327 {
328     void        **slot, **lvl;
329     nxt_int_t   ret;
330     uintptr_t   mask;
331     nxt_uint_t  shift;
332 
333     shift = lhq->proto->shift[nlvl];
334     mask = ((uintptr_t) 1 << shift) - 1;
335 
336     lvl = nxt_lvlhsh_level(*parent, mask);
337     slot = &lvl[key & mask];
338 
339     if (*slot != NULL) {
340         key >>= shift;
341 
342         if (nxt_lvlhsh_is_bucket(*slot)) {
343             return nxt_lvlhsh_bucket_insert(lhq, slot, key, nlvl);
344         }
345 
346         return nxt_lvlhsh_level_insert(lhq, slot, key, nlvl + 1);
347     }
348 
349     ret = nxt_lvlhsh_new_bucket(lhq, slot);
350 
351     if (nxt_fast_path(ret == NXT_OK)) {
352         nxt_lvlhsh_count_inc(*parent);
353     }
354 
355     return ret;
356 }
357 
358 
359 static nxt_int_t
360 nxt_lvlhsh_bucket_insert(nxt_lvlhsh_query_t *lhq, void **slot, uint32_t key,
361     nxt_int_t nlvl)
362 {
363     void                      **bkt, **vacant_bucket, *value;
364     uint32_t                  *bucket, *e, *vacant_entry;
365     nxt_int_t                 ret;
366     uintptr_t                 n;
367     const void                *new_value;
368     const nxt_lvlhsh_proto_t  *proto;
369 
370     bkt = slot;
371     vacant_entry = NULL;
372     vacant_bucket = NULL;
373     proto = lhq->proto;
374 
375     /* Search for duplicate entry in bucket chain. */
376 
377     do {
378         bucket = nxt_lvlhsh_bucket(proto, *bkt);
379         n = nxt_lvlhsh_bucket_entries(proto, *bkt);
380         e = bucket;
381 
382         do {
383             if (nxt_lvlhsh_valid_entry(e)) {
384 
385                 if (nxt_lvlhsh_entry_key(e) == lhq->key_hash) {
386 
387                     value = nxt_lvlhsh_entry_value(e);
388 
389                     if (proto->test(lhq, value) == NXT_OK) {
390 
391                         new_value = lhq->value;
392                         lhq->value = value;
393 
394                         if (lhq->replace) {
395                             nxt_lvlhsh_set_entry_value(e, new_value);
396 
397                             return NXT_OK;
398                         }
399 
400                         return NXT_DECLINED;
401                     }
402                 }
403 
404                 n--;
405 
406             } else {
407                 /*
408                  * Save a hole vacant position in bucket
409                  * and continue to search for duplicate entry.
410                  */
411                 if (vacant_entry == NULL) {
412                     vacant_entry = e;
413                     vacant_bucket = bkt;
414                 }
415             }
416 
417             e += NXT_LVLHSH_ENTRY_SIZE;
418 
419         } while (n != 0);
420 
421         if (e < nxt_lvlhsh_bucket_end(proto, bucket)) {
422             /*
423              * Save a vacant position on incomplete bucket's end
424              * and continue to search for duplicate entry.
425              */
426             if (vacant_entry == NULL) {
427                 vacant_entry = e;
428                 vacant_bucket = bkt;
429             }
430         }
431 
432         bkt = nxt_lvlhsh_next_bucket(proto, bucket);
433 
434     } while (*bkt != NULL);
435 
436     if (vacant_entry != NULL) {
437         nxt_lvlhsh_set_entry_value(vacant_entry, lhq->value);
438         nxt_lvlhsh_set_entry_key(vacant_entry, lhq->key_hash);
439         nxt_lvlhsh_count_inc(*vacant_bucket);
440 
441         return NXT_OK;
442     }
443 
444     /* All buckets are full. */
445 
446     nlvl++;
447 
448     if (nxt_fast_path(proto->shift[nlvl] != 0)) {
449 
450         ret = nxt_lvlhsh_convert_bucket_to_level(lhq, slot, nlvl, bucket);
451 
452         if (nxt_fast_path(ret == NXT_OK)) {
453             return nxt_lvlhsh_level_insert(lhq, slot, key, nlvl);
454         }
455 
456         return ret;
457     }
458 
459     /* The last allowed level, only buckets may be allocated here. */
460 
461     return nxt_lvlhsh_new_bucket(lhq, bkt);
462 }
463 
464 
465 static nxt_int_t
466 nxt_lvlhsh_convert_bucket_to_level(nxt_lvlhsh_query_t *lhq, void **slot,
467     nxt_uint_t nlvl, uint32_t *bucket)
468 {
469     void                      *lvl, **level;
470     uint32_t                  *e, *end, key;
471     nxt_int_t                 ret;
472     nxt_uint_t                i, shift, size;
473     nxt_lvlhsh_query_t        q;
474     const nxt_lvlhsh_proto_t  *proto;
475 
476     proto = lhq->proto;
477     size = nxt_lvlhsh_level_size(proto, nlvl);
478 
479     lvl = proto->alloc(lhq->pool, size * (sizeof(void *)), proto->nalloc);
480 
481     if (nxt_slow_path(lvl == NULL)) {
482         return NXT_ERROR;
483     }
484 
485     nxt_memzero(lvl, size * (sizeof(void *)));
486 
487     level = lvl;
488     shift = 0;
489 
490     for (i = 0; i < nlvl; i++) {
491         /*
492          * Using SIMD operations in this trivial loop with maximum
493          * 8 iterations may increase code size by 170 bytes.
494          */
495         nxt_pragma_loop_disable_vectorization;
496 
497         shift += proto->shift[i];
498     }
499 
500     end = nxt_lvlhsh_bucket_end(proto, bucket);
501 
502     for (e = bucket; e < end; e += NXT_LVLHSH_ENTRY_SIZE) {
503 
504         q.proto = proto;
505         q.pool = lhq->pool;
506         q.value = nxt_lvlhsh_entry_value(e);
507         key = nxt_lvlhsh_entry_key(e);
508         q.key_hash = key;
509 
510         ret = nxt_lvlhsh_level_convertion_insert(&q, &lvl, key >> shift, nlvl);
511 
512         if (nxt_slow_path(ret != NXT_OK)) {
513             return nxt_lvlhsh_free_level(lhq, level, size);
514         }
515     }
516 
517     *slot = lvl;
518 
519     proto->free(lhq->pool, bucket, nxt_lvlhsh_bucket_size(proto));
520 
521     return NXT_OK;
522 }
523 
524 
525 static nxt_int_t
526 nxt_lvlhsh_level_convertion_insert(nxt_lvlhsh_query_t *lhq, void **parent,
527     uint32_t key, nxt_uint_t nlvl)
528 {
529     void        **slot, **lvl;
530     nxt_int_t   ret;
531     uintptr_t   mask;
532     nxt_uint_t  shift;
533 
534     shift = lhq->proto->shift[nlvl];
535     mask = ((uintptr_t) 1 << shift) - 1;
536 
537     lvl = nxt_lvlhsh_level(*parent, mask);
538     slot = &lvl[key & mask];
539 
540     if (*slot == NULL) {
541         ret = nxt_lvlhsh_new_bucket(lhq, slot);
542 
543         if (nxt_fast_path(ret == NXT_OK)) {
544             nxt_lvlhsh_count_inc(*parent);
545         }
546 
547         return ret;
548     }
549 
550     /* Only backets can be here. */
551 
552     return nxt_lvlhsh_bucket_convertion_insert(lhq, slot, key >> shift, nlvl);
553 }
554 
555 
556 /*
557  * The special bucket insertion procedure is required because during
558  * convertion lhq->key contains garbage values and the test function
559  * cannot be called.  Besides, the procedure can be simpler because
560  * a new entry is inserted just after occupied entries.
561  */
562 
563 static nxt_int_t
564 nxt_lvlhsh_bucket_convertion_insert(nxt_lvlhsh_query_t *lhq, void **slot,
565     uint32_t key, nxt_int_t nlvl)
566 {
567     void                      **bkt;
568     uint32_t                  *bucket, *e;
569     nxt_int_t                 ret;
570     uintptr_t                 n;
571     const nxt_lvlhsh_proto_t  *proto;
572 
573     bkt = slot;
574     proto = lhq->proto;
575 
576     do {
577         bucket = nxt_lvlhsh_bucket(proto, *bkt);
578         n = nxt_lvlhsh_bucket_entries(proto, *bkt);
579         e = bucket + n * NXT_LVLHSH_ENTRY_SIZE;
580 
581         if (nxt_fast_path(e < nxt_lvlhsh_bucket_end(proto, bucket))) {
582 
583             nxt_lvlhsh_set_entry_value(e, lhq->value);
584             nxt_lvlhsh_set_entry_key(e, lhq->key_hash);
585             nxt_lvlhsh_count_inc(*bkt);
586 
587             return NXT_OK;
588         }
589 
590         bkt = nxt_lvlhsh_next_bucket(proto, bucket);
591 
592     } while (*bkt != NULL);
593 
594     /* All buckets are full. */
595 
596     nlvl++;
597 
598     if (nxt_fast_path(proto->shift[nlvl] != 0)) {
599 
600         ret = nxt_lvlhsh_convert_bucket_to_level(lhq, slot, nlvl, bucket);
601 
602         if (nxt_fast_path(ret == NXT_OK)) {
603             return nxt_lvlhsh_level_insert(lhq, slot, key, nlvl);
604         }
605 
606         return ret;
607     }
608 
609     /* The last allowed level, only buckets may be allocated here. */
610 
611     return nxt_lvlhsh_new_bucket(lhq, bkt);
612 }
613 
614 
615 static nxt_int_t
616 nxt_lvlhsh_free_level(nxt_lvlhsh_query_t *lhq, void **level, nxt_uint_t size)
617 {
618     size_t                    bsize;
619     nxt_uint_t                i;
620     const nxt_lvlhsh_proto_t  *proto;
621 
622     proto = lhq->proto;
623     bsize = nxt_lvlhsh_bucket_size(proto);
624 
625     for (i = 0; i < size; i++) {
626 
627         if (level[i] != NULL) {
628             /*
629              * Chained buckets are not possible here, since even
630              * in the worst case one bucket cannot be converted
631              * in two chained buckets but remains the same bucket.
632              */
633             proto->free(lhq->pool, nxt_lvlhsh_bucket(proto, level[i]), bsize);
634         }
635     }
636 
637     proto->free(lhq->pool, level, size * (sizeof(void *)));
638 
639     return NXT_ERROR;
640 }
641 
642 
643 nxt_int_t
644 nxt_lvlhsh_delete(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq)
645 {
646     if (nxt_fast_path(lh->slot != NULL)) {
647 
648         if (nxt_lvlhsh_is_bucket(lh->slot)) {
649             return nxt_lvlhsh_bucket_delete(lhq, &lh->slot);
650         }
651 
652         return nxt_lvlhsh_level_delete(lhq, &lh->slot, lhq->key_hash, 0);
653     }
654 
655     return NXT_DECLINED;
656 }
657 
658 
659 static nxt_int_t
660 nxt_lvlhsh_level_delete(nxt_lvlhsh_query_t *lhq, void **parent, uint32_t key,
661     nxt_uint_t nlvl)
662 {
663     size_t      size;
664     void        **slot, **lvl;
665     uintptr_t   mask;
666     nxt_int_t   ret;
667     nxt_uint_t  shift;
668 
669     shift = lhq->proto->shift[nlvl];
670     mask = ((uintptr_t) 1 << shift) - 1;
671 
672     lvl = nxt_lvlhsh_level(*parent, mask);
673     slot = &lvl[key & mask];
674 
675     if (*slot != NULL) {
676 
677         if (nxt_lvlhsh_is_bucket(*slot)) {
678             ret = nxt_lvlhsh_bucket_delete(lhq, slot);
679 
680         } else {
681             key >>= shift;
682             ret = nxt_lvlhsh_level_delete(lhq, slot, key, nlvl + 1);
683         }
684 
685         if (*slot == NULL) {
686             nxt_lvlhsh_count_dec(*parent);
687 
688             if (nxt_lvlhsh_level_entries(*parent, mask) == 0) {
689                 *parent = NULL;
690                 size = nxt_lvlhsh_level_size(lhq->proto, nlvl);
691                 lhq->proto->free(lhq->pool, lvl, size * sizeof(void *));
692             }
693         }
694 
695         return ret;
696     }
697 
698     return NXT_DECLINED;
699 }
700 
701 
702 static nxt_int_t
703 nxt_lvlhsh_bucket_delete(nxt_lvlhsh_query_t *lhq, void **bkt)
704 {
705     void                      *value;
706     size_t                    size;
707     uint32_t                  *bucket, *e;
708     uintptr_t                 n;
709     const nxt_lvlhsh_proto_t  *proto;
710 
711     proto = lhq->proto;
712 
713     do {
714         bucket = nxt_lvlhsh_bucket(proto, *bkt);
715         n = nxt_lvlhsh_bucket_entries(proto, *bkt);
716         e = bucket;
717 
718         do {
719             if (nxt_lvlhsh_valid_entry(e)) {
720 
721                 if (nxt_lvlhsh_entry_key(e) == lhq->key_hash) {
722 
723                     value = nxt_lvlhsh_entry_value(e);
724 
725                     if (proto->test(lhq, value) == NXT_OK) {
726 
727                         if (nxt_lvlhsh_bucket_entries(proto, *bkt) == 1) {
728                             *bkt = *nxt_lvlhsh_next_bucket(proto, bucket);
729                             size = nxt_lvlhsh_bucket_size(proto);
730                             proto->free(lhq->pool, bucket, size);
731 
732                         } else {
733                             nxt_lvlhsh_count_dec(*bkt);
734                             nxt_lvlhsh_set_entry_value(e, NULL);
735                         }
736 
737                         lhq->value = value;
738 
739                         return NXT_OK;
740                     }
741                 }
742 
743                 n--;
744             }
745 
746             e += NXT_LVLHSH_ENTRY_SIZE;
747 
748         } while (n != 0);
749 
750         bkt = nxt_lvlhsh_next_bucket(proto, bucket);
751 
752     } while (*bkt != NULL);
753 
754     return NXT_DECLINED;
755 }
756 
757 
758 void *
759 nxt_lvlhsh_each(nxt_lvlhsh_t *lh, nxt_lvlhsh_each_t *lhe)
760 {
761     void  **slot;
762 
763     if (lhe->bucket == NXT_LVLHSH_BUCKET_DONE) {
764         slot = lh->slot;
765 
766         if (nxt_lvlhsh_is_bucket(slot)) {
767             return NULL;
768         }
769 
770     } else {
771         if (nxt_slow_path(lhe->bucket == NULL)) {
772 
773             /* The first iteration only. */
774 
775             slot = lh->slot;
776 
777             if (slot == NULL) {
778                 return NULL;
779             }
780 
781             if (!nxt_lvlhsh_is_bucket(slot)) {
782                 goto level;
783             }
784 
785             lhe->bucket = nxt_lvlhsh_bucket(lhe->proto, slot);
786             lhe->entries = nxt_lvlhsh_bucket_entries(lhe->proto, slot);
787         }
788 
789         return nxt_lvlhsh_bucket_each(lhe);
790     }
791 
792 level:
793 
794     return nxt_lvlhsh_level_each(lhe, slot, 0, 0);
795 }
796 
797 
798 static void *
799 nxt_lvlhsh_level_each(nxt_lvlhsh_each_t *lhe, void **level, nxt_uint_t nlvl,
800     nxt_uint_t shift)
801 {
802     void        **slot, *value;
803     uintptr_t   mask;
804     nxt_uint_t  n, level_shift;
805 
806     level_shift = lhe->proto->shift[nlvl];
807     mask = ((uintptr_t) 1 << level_shift) - 1;
808 
809     level = nxt_lvlhsh_level(level, mask);
810 
811     do {
812         n = (lhe->current >> shift) & mask;
813         slot = level[n];
814 
815         if (slot != NULL) {
816             if (nxt_lvlhsh_is_bucket(slot)) {
817 
818                 if (lhe->bucket != NXT_LVLHSH_BUCKET_DONE) {
819 
820                     lhe->bucket = nxt_lvlhsh_bucket(lhe->proto, slot);
821                     lhe->entries = nxt_lvlhsh_bucket_entries(lhe->proto, slot);
822                     lhe->entry = 0;
823 
824                     return nxt_lvlhsh_bucket_each(lhe);
825                 }
826 
827                 lhe->bucket = NULL;
828 
829             } else {
830                 value = nxt_lvlhsh_level_each(lhe, slot, nlvl + 1,
831                                               shift + level_shift);
832                 if (value != NULL) {
833                     return value;
834                 }
835             }
836         }
837 
838         lhe->current &= ~(mask << shift);
839         n = ((n + 1) & mask) << shift;
840         lhe->current |= n;
841 
842     } while (n != 0);
843 
844     return NULL;
845 }
846 
847 
848 static nxt_noinline void *
849 nxt_lvlhsh_bucket_each(nxt_lvlhsh_each_t *lhe)
850 {
851     void      *value, **next;
852     uint32_t  *bucket;
853 
854     /* At least one valid entry must present here. */
855     do {
856         bucket = &lhe->bucket[lhe->entry];
857         lhe->entry += NXT_LVLHSH_ENTRY_SIZE;
858 
859     } while (nxt_lvlhsh_free_entry(bucket));
860 
861     value = nxt_lvlhsh_entry_value(bucket);
862 
863     lhe->entries--;
864 
865     if (lhe->entries == 0) {
866         next = *nxt_lvlhsh_next_bucket(lhe->proto, lhe->bucket);
867 
868         lhe->bucket = (next == NULL) ? NXT_LVLHSH_BUCKET_DONE:
869                                        nxt_lvlhsh_bucket(lhe->proto, next);
870 
871         lhe->entries = nxt_lvlhsh_bucket_entries(lhe->proto, next);
872         lhe->entry = 0;
873     }
874 
875     return value;
876 }
877 
878 
879 void *
880 nxt_lvlhsh_alloc(void *data, size_t size, nxt_uint_t nalloc)
881 {
882     return nxt_memalign(size, size);
883 }
884 
885 
886 void
887 nxt_lvlhsh_free(void *data, void *p, size_t size)
888 {
889     nxt_free(p);
890 }
891