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