xref: /unit/src/nxt_lvlhsh.c (revision 2084:7d479274f334)
10Sigor@sysoev.ru 
20Sigor@sysoev.ru /*
30Sigor@sysoev.ru  * Copyright (C) Igor Sysoev
40Sigor@sysoev.ru  * Copyright (C) NGINX, Inc.
50Sigor@sysoev.ru  */
60Sigor@sysoev.ru 
70Sigor@sysoev.ru #include <nxt_main.h>
80Sigor@sysoev.ru 
90Sigor@sysoev.ru 
100Sigor@sysoev.ru /*
110Sigor@sysoev.ru  * The level hash consists of hierarchical levels of arrays of pointers.
120Sigor@sysoev.ru  * The pointers may point to another level, a bucket, or NULL.
130Sigor@sysoev.ru  * The levels and buckets must be allocated in manner alike posix_memalign()
140Sigor@sysoev.ru  * to bookkeep additional information in pointer low bits.
150Sigor@sysoev.ru  *
160Sigor@sysoev.ru  * A level is an array of pointers.  Its size is a power of 2.  Levels
170Sigor@sysoev.ru  * may be different sizes, but on the same level the sizes are the same.
180Sigor@sysoev.ru  * Level sizes are specified by number of bits per level in lvlhsh->shift
190Sigor@sysoev.ru  * array.  A hash may have up to 7 levels.  There are two predefined
200Sigor@sysoev.ru  * shift arrays given by the first two shift array values:
210Sigor@sysoev.ru  *
220Sigor@sysoev.ru  * 1) [0, 0]:  [4, 4, 4, 4, 4, 4, 4] on a 64-bit platform or
230Sigor@sysoev.ru  *             [5, 5, 5, 5, 5, 5, 0] on a 32-bit platform,
240Sigor@sysoev.ru  *    so default size of levels is 128 bytes.
250Sigor@sysoev.ru  *
260Sigor@sysoev.ru  * 2) [0, 10]: [10, 4, 4, 4, 4, 4, 0] on a 64-bit platform or
270Sigor@sysoev.ru  *             [10, 5, 5, 5, 5, 0, 0] on a 32-bit platform,
280Sigor@sysoev.ru  *    so default size of levels is 128 bytes on all levels except
290Sigor@sysoev.ru  *    the first level.  The first level is 8K or 4K on 64-bit or 32-bit
300Sigor@sysoev.ru  *    platforms respectively.
310Sigor@sysoev.ru  *
320Sigor@sysoev.ru  * All buckets in a hash are the same size which is a power of 2.
330Sigor@sysoev.ru  * A bucket contains several entries stored and tested sequentially.
340Sigor@sysoev.ru  * The bucket size should be one or two CPU cache line size, a minimum
350Sigor@sysoev.ru  * allowed size is 32 bytes.  A default 128-byte bucket contains 10 64-bit
360Sigor@sysoev.ru  * entries or 15 32-bit entries.  Each entry consists of pointer to value
370Sigor@sysoev.ru  * data and 32-bit key.  If an entry value pointer is NULL, the entry is free.
380Sigor@sysoev.ru  * On a 64-bit platform entry value pointers are no aligned, therefore they
390Sigor@sysoev.ru  * are accessed as two 32-bit integers.  The rest trailing space in a bucket
400Sigor@sysoev.ru  * is used as pointer to next bucket and this pointer is always aligned.
410Sigor@sysoev.ru  * Although the level hash allows to store a lot of values in a bucket chain,
420Sigor@sysoev.ru  * this is non optimal way.  The large data set should be stored using
430Sigor@sysoev.ru  * several levels.
440Sigor@sysoev.ru  */
450Sigor@sysoev.ru 
46*2084Salx.manpages@gmail.com #define nxt_lvlhsh_is_bucket(p)                                               \
470Sigor@sysoev.ru     ((uintptr_t) (p) & 1)
480Sigor@sysoev.ru 
490Sigor@sysoev.ru 
50*2084Salx.manpages@gmail.com #define nxt_lvlhsh_count_inc(n)                                               \
510Sigor@sysoev.ru     n = (void *) ((uintptr_t) (n) + 2)
520Sigor@sysoev.ru 
530Sigor@sysoev.ru 
54*2084Salx.manpages@gmail.com #define nxt_lvlhsh_count_dec(n)                                               \
550Sigor@sysoev.ru     n = (void *) ((uintptr_t) (n) - 2)
560Sigor@sysoev.ru 
570Sigor@sysoev.ru 
58*2084Salx.manpages@gmail.com #define nxt_lvlhsh_level_size(proto, nlvl)                                    \
590Sigor@sysoev.ru     ((uintptr_t) 1 << proto->shift[nlvl])
600Sigor@sysoev.ru 
610Sigor@sysoev.ru 
62*2084Salx.manpages@gmail.com #define nxt_lvlhsh_level(lvl, mask)                                           \
630Sigor@sysoev.ru     (void **) ((uintptr_t) lvl & (~mask << 2))
640Sigor@sysoev.ru 
650Sigor@sysoev.ru 
66*2084Salx.manpages@gmail.com #define nxt_lvlhsh_level_entries(lvl, mask)                                   \
670Sigor@sysoev.ru     ((uintptr_t) lvl & (mask << 1))
680Sigor@sysoev.ru 
690Sigor@sysoev.ru 
70*2084Salx.manpages@gmail.com #define nxt_lvlhsh_store_bucket(slot, bkt)                                    \
710Sigor@sysoev.ru     slot = (void **) ((uintptr_t) bkt | 2 | 1)
720Sigor@sysoev.ru 
730Sigor@sysoev.ru 
74*2084Salx.manpages@gmail.com #define nxt_lvlhsh_bucket_size(proto)                                         \
750Sigor@sysoev.ru     proto->bucket_size
760Sigor@sysoev.ru 
770Sigor@sysoev.ru 
78*2084Salx.manpages@gmail.com #define nxt_lvlhsh_bucket(proto, bkt)                                         \
790Sigor@sysoev.ru     (uint32_t *) ((uintptr_t) bkt & ~(uintptr_t) proto->bucket_mask)
800Sigor@sysoev.ru 
810Sigor@sysoev.ru 
82*2084Salx.manpages@gmail.com #define nxt_lvlhsh_bucket_entries(proto, bkt)                                 \
830Sigor@sysoev.ru     (((uintptr_t) bkt & (uintptr_t) proto->bucket_mask) >> 1)
840Sigor@sysoev.ru 
850Sigor@sysoev.ru 
86*2084Salx.manpages@gmail.com #define nxt_lvlhsh_bucket_end(proto, bkt)                                     \
870Sigor@sysoev.ru     &bkt[proto->bucket_end]
880Sigor@sysoev.ru 
890Sigor@sysoev.ru 
90*2084Salx.manpages@gmail.com #define nxt_lvlhsh_free_entry(e)                                              \
910Sigor@sysoev.ru     (!(nxt_lvlhsh_valid_entry(e)))
920Sigor@sysoev.ru 
930Sigor@sysoev.ru 
94*2084Salx.manpages@gmail.com #define nxt_lvlhsh_next_bucket(proto, bkt)                                    \
950Sigor@sysoev.ru     ((void **) &bkt[proto->bucket_end])
960Sigor@sysoev.ru 
970Sigor@sysoev.ru #if (NXT_64BIT)
980Sigor@sysoev.ru 
99*2084Salx.manpages@gmail.com #define nxt_lvlhsh_valid_entry(e)                                             \
1000Sigor@sysoev.ru     (((e)[0] | (e)[1]) != 0)
1010Sigor@sysoev.ru 
1020Sigor@sysoev.ru 
103*2084Salx.manpages@gmail.com #define nxt_lvlhsh_entry_value(e)                                             \
1040Sigor@sysoev.ru     (void *) (((uintptr_t) (e)[1] << 32) + (e)[0])
1050Sigor@sysoev.ru 
1060Sigor@sysoev.ru 
107*2084Salx.manpages@gmail.com #define nxt_lvlhsh_set_entry_value(e, n)                                      \
1080Sigor@sysoev.ru     (e)[0] = (uint32_t)  (uintptr_t) n;                                       \
1090Sigor@sysoev.ru     (e)[1] = (uint32_t) ((uintptr_t) n >> 32)
1100Sigor@sysoev.ru 
1110Sigor@sysoev.ru 
112*2084Salx.manpages@gmail.com #define nxt_lvlhsh_entry_key(e)                                               \
1130Sigor@sysoev.ru     (e)[2]
1140Sigor@sysoev.ru 
1150Sigor@sysoev.ru 
116*2084Salx.manpages@gmail.com #define nxt_lvlhsh_set_entry_key(e, n)                                        \
1170Sigor@sysoev.ru     (e)[2] = n
1180Sigor@sysoev.ru 
1190Sigor@sysoev.ru #else
1200Sigor@sysoev.ru 
121*2084Salx.manpages@gmail.com #define nxt_lvlhsh_valid_entry(e)                                             \
1220Sigor@sysoev.ru     ((e)[0] != 0)
1230Sigor@sysoev.ru 
1240Sigor@sysoev.ru 
125*2084Salx.manpages@gmail.com #define nxt_lvlhsh_entry_value(e)                                             \
1260Sigor@sysoev.ru     (void *) (e)[0]
1270Sigor@sysoev.ru 
1280Sigor@sysoev.ru 
129*2084Salx.manpages@gmail.com #define nxt_lvlhsh_set_entry_value(e, n)                                      \
1300Sigor@sysoev.ru     (e)[0] = (uint32_t) n
1310Sigor@sysoev.ru 
1320Sigor@sysoev.ru 
133*2084Salx.manpages@gmail.com #define nxt_lvlhsh_entry_key(e)                                               \
1340Sigor@sysoev.ru     (e)[1]
1350Sigor@sysoev.ru 
1360Sigor@sysoev.ru 
137*2084Salx.manpages@gmail.com #define nxt_lvlhsh_set_entry_key(e, n)                                        \
1380Sigor@sysoev.ru     (e)[1] = n
1390Sigor@sysoev.ru 
1400Sigor@sysoev.ru #endif
1410Sigor@sysoev.ru 
1420Sigor@sysoev.ru 
1430Sigor@sysoev.ru #define NXT_LVLHSH_BUCKET_DONE  ((void *) -1)
1440Sigor@sysoev.ru 
1450Sigor@sysoev.ru 
146595Sigor@sysoev.ru typedef struct {
147595Sigor@sysoev.ru     const nxt_lvlhsh_proto_t  *proto;
148595Sigor@sysoev.ru     void                      *pool;
149595Sigor@sysoev.ru     uint32_t                  retrieve;  /* 1 bit */
150595Sigor@sysoev.ru } nxt_lvlhsh_peek_t;
151595Sigor@sysoev.ru 
152595Sigor@sysoev.ru 
1530Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_level_find(nxt_lvlhsh_query_t *lhq, void **lvl,
1540Sigor@sysoev.ru     uint32_t key, nxt_uint_t nlvl);
1550Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_bucket_find(nxt_lvlhsh_query_t *lhq, void **bkt);
1560Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_new_bucket(nxt_lvlhsh_query_t *lhq, void **slot);
1570Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_level_insert(nxt_lvlhsh_query_t *lhq,
1580Sigor@sysoev.ru     void **slot, uint32_t key, nxt_uint_t nlvl);
1590Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_bucket_insert(nxt_lvlhsh_query_t *lhq,
1600Sigor@sysoev.ru     void **slot, uint32_t key, nxt_int_t nlvl);
1610Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_convert_bucket_to_level(nxt_lvlhsh_query_t *lhq,
1620Sigor@sysoev.ru     void **slot, nxt_uint_t nlvl, uint32_t *bucket);
1630Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_level_convertion_insert(nxt_lvlhsh_query_t *lhq,
1640Sigor@sysoev.ru     void **parent, uint32_t key, nxt_uint_t nlvl);
1650Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_bucket_convertion_insert(nxt_lvlhsh_query_t *lhq,
1660Sigor@sysoev.ru     void **slot, uint32_t key, nxt_int_t nlvl);
1670Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_free_level(nxt_lvlhsh_query_t *lhq, void **level,
1680Sigor@sysoev.ru     nxt_uint_t size);
1690Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_level_delete(nxt_lvlhsh_query_t *lhq, void **slot,
1700Sigor@sysoev.ru     uint32_t key, nxt_uint_t nlvl);
1710Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_bucket_delete(nxt_lvlhsh_query_t *lhq, void **bkt);
1720Sigor@sysoev.ru static void *nxt_lvlhsh_level_each(nxt_lvlhsh_each_t *lhe, void **level,
1730Sigor@sysoev.ru     nxt_uint_t nlvl, nxt_uint_t shift);
1740Sigor@sysoev.ru static void *nxt_lvlhsh_bucket_each(nxt_lvlhsh_each_t *lhe);
175595Sigor@sysoev.ru static void *nxt_lvlhsh_level_peek(nxt_lvlhsh_peek_t *peek, void **level,
176595Sigor@sysoev.ru     nxt_uint_t nlvl);
177595Sigor@sysoev.ru static void *nxt_lvlhsh_bucket_peek(nxt_lvlhsh_peek_t *peek, void **bkt);
1780Sigor@sysoev.ru 
1790Sigor@sysoev.ru 
1800Sigor@sysoev.ru nxt_int_t
nxt_lvlhsh_find(nxt_lvlhsh_t * lh,nxt_lvlhsh_query_t * lhq)1810Sigor@sysoev.ru nxt_lvlhsh_find(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq)
1820Sigor@sysoev.ru {
1830Sigor@sysoev.ru     void  *slot;
1840Sigor@sysoev.ru 
1850Sigor@sysoev.ru     slot = lh->slot;
1860Sigor@sysoev.ru 
1870Sigor@sysoev.ru     if (nxt_fast_path(slot != NULL)) {
1880Sigor@sysoev.ru 
1890Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(slot)) {
1900Sigor@sysoev.ru             return nxt_lvlhsh_bucket_find(lhq, slot);
1910Sigor@sysoev.ru         }
1920Sigor@sysoev.ru 
1930Sigor@sysoev.ru         return nxt_lvlhsh_level_find(lhq, slot, lhq->key_hash, 0);
1940Sigor@sysoev.ru     }
1950Sigor@sysoev.ru 
1960Sigor@sysoev.ru     return NXT_DECLINED;
1970Sigor@sysoev.ru }
1980Sigor@sysoev.ru 
1990Sigor@sysoev.ru 
2000Sigor@sysoev.ru static nxt_int_t
nxt_lvlhsh_level_find(nxt_lvlhsh_query_t * lhq,void ** lvl,uint32_t key,nxt_uint_t nlvl)2010Sigor@sysoev.ru nxt_lvlhsh_level_find(nxt_lvlhsh_query_t *lhq, void **lvl, uint32_t key,
2020Sigor@sysoev.ru     nxt_uint_t nlvl)
2030Sigor@sysoev.ru {
2040Sigor@sysoev.ru     void        **slot;
2050Sigor@sysoev.ru     uintptr_t   mask;
2060Sigor@sysoev.ru     nxt_uint_t  shift;
2070Sigor@sysoev.ru 
2080Sigor@sysoev.ru     shift = lhq->proto->shift[nlvl];
2090Sigor@sysoev.ru     mask = ((uintptr_t) 1 << shift) - 1;
2100Sigor@sysoev.ru 
2110Sigor@sysoev.ru     lvl = nxt_lvlhsh_level(lvl, mask);
2120Sigor@sysoev.ru     slot = lvl[key & mask];
2130Sigor@sysoev.ru 
2140Sigor@sysoev.ru     if (slot != NULL) {
2150Sigor@sysoev.ru 
2160Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(slot)) {
2170Sigor@sysoev.ru             return nxt_lvlhsh_bucket_find(lhq, slot);
2180Sigor@sysoev.ru         }
2190Sigor@sysoev.ru 
2200Sigor@sysoev.ru         return nxt_lvlhsh_level_find(lhq, slot, key >> shift, nlvl + 1);
2210Sigor@sysoev.ru     }
2220Sigor@sysoev.ru 
2230Sigor@sysoev.ru     return NXT_DECLINED;
2240Sigor@sysoev.ru }
2250Sigor@sysoev.ru 
2260Sigor@sysoev.ru 
2270Sigor@sysoev.ru static nxt_int_t
nxt_lvlhsh_bucket_find(nxt_lvlhsh_query_t * lhq,void ** bkt)2280Sigor@sysoev.ru nxt_lvlhsh_bucket_find(nxt_lvlhsh_query_t *lhq, void **bkt)
2290Sigor@sysoev.ru {
2300Sigor@sysoev.ru     void        *value;
2310Sigor@sysoev.ru     uint32_t    *bucket, *e;
2320Sigor@sysoev.ru     nxt_uint_t  n;
2330Sigor@sysoev.ru 
2340Sigor@sysoev.ru     do {
2350Sigor@sysoev.ru         bucket = nxt_lvlhsh_bucket(lhq->proto, bkt);
2360Sigor@sysoev.ru         n = nxt_lvlhsh_bucket_entries(lhq->proto, bkt);
2370Sigor@sysoev.ru         e = bucket;
2380Sigor@sysoev.ru 
2390Sigor@sysoev.ru         do {
2400Sigor@sysoev.ru             if (nxt_lvlhsh_valid_entry(e)) {
2410Sigor@sysoev.ru                 n--;
2420Sigor@sysoev.ru 
2430Sigor@sysoev.ru                 if (nxt_lvlhsh_entry_key(e) == lhq->key_hash) {
2440Sigor@sysoev.ru 
2450Sigor@sysoev.ru                     value = nxt_lvlhsh_entry_value(e);
2460Sigor@sysoev.ru 
2470Sigor@sysoev.ru                     if (lhq->proto->test(lhq, value) == NXT_OK) {
2480Sigor@sysoev.ru                         lhq->value = value;
2490Sigor@sysoev.ru 
2500Sigor@sysoev.ru                         return NXT_OK;
2510Sigor@sysoev.ru                     }
2520Sigor@sysoev.ru                 }
2530Sigor@sysoev.ru             }
2540Sigor@sysoev.ru 
2550Sigor@sysoev.ru             e += NXT_LVLHSH_ENTRY_SIZE;
2560Sigor@sysoev.ru 
2570Sigor@sysoev.ru         } while (n != 0);
2580Sigor@sysoev.ru 
2590Sigor@sysoev.ru         bkt = *nxt_lvlhsh_next_bucket(lhq->proto, bucket);
2600Sigor@sysoev.ru 
2610Sigor@sysoev.ru     } while (bkt != NULL);
2620Sigor@sysoev.ru 
2630Sigor@sysoev.ru     return NXT_DECLINED;
2640Sigor@sysoev.ru }
2650Sigor@sysoev.ru 
2660Sigor@sysoev.ru 
2670Sigor@sysoev.ru nxt_int_t
nxt_lvlhsh_insert(nxt_lvlhsh_t * lh,nxt_lvlhsh_query_t * lhq)2680Sigor@sysoev.ru nxt_lvlhsh_insert(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq)
2690Sigor@sysoev.ru {
2700Sigor@sysoev.ru     uint32_t  key;
2710Sigor@sysoev.ru 
2720Sigor@sysoev.ru     if (nxt_fast_path(lh->slot != NULL)) {
2730Sigor@sysoev.ru 
2740Sigor@sysoev.ru         key = lhq->key_hash;
2750Sigor@sysoev.ru 
2760Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(lh->slot)) {
2770Sigor@sysoev.ru             return nxt_lvlhsh_bucket_insert(lhq, &lh->slot, key, -1);
2780Sigor@sysoev.ru         }
2790Sigor@sysoev.ru 
2800Sigor@sysoev.ru         return nxt_lvlhsh_level_insert(lhq, &lh->slot, key, 0);
2810Sigor@sysoev.ru     }
2820Sigor@sysoev.ru 
2830Sigor@sysoev.ru     return nxt_lvlhsh_new_bucket(lhq, &lh->slot);
2840Sigor@sysoev.ru }
2850Sigor@sysoev.ru 
2860Sigor@sysoev.ru 
2870Sigor@sysoev.ru static nxt_int_t
nxt_lvlhsh_new_bucket(nxt_lvlhsh_query_t * lhq,void ** slot)2880Sigor@sysoev.ru nxt_lvlhsh_new_bucket(nxt_lvlhsh_query_t *lhq, void **slot)
2890Sigor@sysoev.ru {
2900Sigor@sysoev.ru     uint32_t  *bucket;
2910Sigor@sysoev.ru 
29265Sigor@sysoev.ru     bucket = lhq->proto->alloc(lhq->pool, nxt_lvlhsh_bucket_size(lhq->proto));
2930Sigor@sysoev.ru 
2940Sigor@sysoev.ru     if (nxt_fast_path(bucket != NULL)) {
2950Sigor@sysoev.ru 
2960Sigor@sysoev.ru         nxt_lvlhsh_set_entry_value(bucket, lhq->value);
2970Sigor@sysoev.ru         nxt_lvlhsh_set_entry_key(bucket, lhq->key_hash);
2980Sigor@sysoev.ru 
2990Sigor@sysoev.ru         *nxt_lvlhsh_next_bucket(lhq->proto, bucket) = NULL;
3000Sigor@sysoev.ru 
3010Sigor@sysoev.ru         nxt_lvlhsh_store_bucket(*slot, bucket);
3020Sigor@sysoev.ru 
3030Sigor@sysoev.ru         return NXT_OK;
3040Sigor@sysoev.ru     }
3050Sigor@sysoev.ru 
3060Sigor@sysoev.ru     return NXT_ERROR;
3070Sigor@sysoev.ru }
3080Sigor@sysoev.ru 
3090Sigor@sysoev.ru 
3100Sigor@sysoev.ru static nxt_int_t
nxt_lvlhsh_level_insert(nxt_lvlhsh_query_t * lhq,void ** parent,uint32_t key,nxt_uint_t nlvl)3110Sigor@sysoev.ru nxt_lvlhsh_level_insert(nxt_lvlhsh_query_t *lhq, void **parent, uint32_t key,
3120Sigor@sysoev.ru     nxt_uint_t nlvl)
3130Sigor@sysoev.ru {
3140Sigor@sysoev.ru     void        **slot, **lvl;
3150Sigor@sysoev.ru     nxt_int_t   ret;
3160Sigor@sysoev.ru     uintptr_t   mask;
3170Sigor@sysoev.ru     nxt_uint_t  shift;
3180Sigor@sysoev.ru 
3190Sigor@sysoev.ru     shift = lhq->proto->shift[nlvl];
3200Sigor@sysoev.ru     mask = ((uintptr_t) 1 << shift) - 1;
3210Sigor@sysoev.ru 
3220Sigor@sysoev.ru     lvl = nxt_lvlhsh_level(*parent, mask);
3230Sigor@sysoev.ru     slot = &lvl[key & mask];
3240Sigor@sysoev.ru 
3250Sigor@sysoev.ru     if (*slot != NULL) {
3260Sigor@sysoev.ru         key >>= shift;
3270Sigor@sysoev.ru 
3280Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(*slot)) {
3290Sigor@sysoev.ru             return nxt_lvlhsh_bucket_insert(lhq, slot, key, nlvl);
3300Sigor@sysoev.ru         }
3310Sigor@sysoev.ru 
3320Sigor@sysoev.ru         return nxt_lvlhsh_level_insert(lhq, slot, key, nlvl + 1);
3330Sigor@sysoev.ru     }
3340Sigor@sysoev.ru 
3350Sigor@sysoev.ru     ret = nxt_lvlhsh_new_bucket(lhq, slot);
3360Sigor@sysoev.ru 
3370Sigor@sysoev.ru     if (nxt_fast_path(ret == NXT_OK)) {
3380Sigor@sysoev.ru         nxt_lvlhsh_count_inc(*parent);
3390Sigor@sysoev.ru     }
3400Sigor@sysoev.ru 
3410Sigor@sysoev.ru     return ret;
3420Sigor@sysoev.ru }
3430Sigor@sysoev.ru 
3440Sigor@sysoev.ru 
3450Sigor@sysoev.ru static nxt_int_t
nxt_lvlhsh_bucket_insert(nxt_lvlhsh_query_t * lhq,void ** slot,uint32_t key,nxt_int_t nlvl)3460Sigor@sysoev.ru nxt_lvlhsh_bucket_insert(nxt_lvlhsh_query_t *lhq, void **slot, uint32_t key,
3470Sigor@sysoev.ru     nxt_int_t nlvl)
3480Sigor@sysoev.ru {
3490Sigor@sysoev.ru     void                      **bkt, **vacant_bucket, *value;
3500Sigor@sysoev.ru     uint32_t                  *bucket, *e, *vacant_entry;
3510Sigor@sysoev.ru     nxt_int_t                 ret;
3520Sigor@sysoev.ru     uintptr_t                 n;
3530Sigor@sysoev.ru     const void                *new_value;
3540Sigor@sysoev.ru     const nxt_lvlhsh_proto_t  *proto;
3550Sigor@sysoev.ru 
3560Sigor@sysoev.ru     bkt = slot;
3570Sigor@sysoev.ru     vacant_entry = NULL;
3580Sigor@sysoev.ru     vacant_bucket = NULL;
3590Sigor@sysoev.ru     proto = lhq->proto;
3600Sigor@sysoev.ru 
3610Sigor@sysoev.ru     /* Search for duplicate entry in bucket chain. */
3620Sigor@sysoev.ru 
3630Sigor@sysoev.ru     do {
3640Sigor@sysoev.ru         bucket = nxt_lvlhsh_bucket(proto, *bkt);
3650Sigor@sysoev.ru         n = nxt_lvlhsh_bucket_entries(proto, *bkt);
3660Sigor@sysoev.ru         e = bucket;
3670Sigor@sysoev.ru 
3680Sigor@sysoev.ru         do {
3690Sigor@sysoev.ru             if (nxt_lvlhsh_valid_entry(e)) {
3700Sigor@sysoev.ru 
3710Sigor@sysoev.ru                 if (nxt_lvlhsh_entry_key(e) == lhq->key_hash) {
3720Sigor@sysoev.ru 
3730Sigor@sysoev.ru                     value = nxt_lvlhsh_entry_value(e);
3740Sigor@sysoev.ru 
3750Sigor@sysoev.ru                     if (proto->test(lhq, value) == NXT_OK) {
3760Sigor@sysoev.ru 
3770Sigor@sysoev.ru                         new_value = lhq->value;
3780Sigor@sysoev.ru                         lhq->value = value;
3790Sigor@sysoev.ru 
3800Sigor@sysoev.ru                         if (lhq->replace) {
3810Sigor@sysoev.ru                             nxt_lvlhsh_set_entry_value(e, new_value);
3820Sigor@sysoev.ru 
3830Sigor@sysoev.ru                             return NXT_OK;
3840Sigor@sysoev.ru                         }
3850Sigor@sysoev.ru 
3860Sigor@sysoev.ru                         return NXT_DECLINED;
3870Sigor@sysoev.ru                     }
3880Sigor@sysoev.ru                 }
3890Sigor@sysoev.ru 
3900Sigor@sysoev.ru                 n--;
3910Sigor@sysoev.ru 
3920Sigor@sysoev.ru             } else {
3930Sigor@sysoev.ru                 /*
3940Sigor@sysoev.ru                  * Save a hole vacant position in bucket
3950Sigor@sysoev.ru                  * and continue to search for duplicate entry.
3960Sigor@sysoev.ru                  */
3970Sigor@sysoev.ru                 if (vacant_entry == NULL) {
3980Sigor@sysoev.ru                     vacant_entry = e;
3990Sigor@sysoev.ru                     vacant_bucket = bkt;
4000Sigor@sysoev.ru                 }
4010Sigor@sysoev.ru             }
4020Sigor@sysoev.ru 
4030Sigor@sysoev.ru             e += NXT_LVLHSH_ENTRY_SIZE;
4040Sigor@sysoev.ru 
4050Sigor@sysoev.ru         } while (n != 0);
4060Sigor@sysoev.ru 
4070Sigor@sysoev.ru         if (e < nxt_lvlhsh_bucket_end(proto, bucket)) {
4080Sigor@sysoev.ru             /*
4090Sigor@sysoev.ru              * Save a vacant position on incomplete bucket's end
4100Sigor@sysoev.ru              * and continue to search for duplicate entry.
4110Sigor@sysoev.ru              */
4120Sigor@sysoev.ru             if (vacant_entry == NULL) {
4130Sigor@sysoev.ru                 vacant_entry = e;
4140Sigor@sysoev.ru                 vacant_bucket = bkt;
4150Sigor@sysoev.ru             }
4160Sigor@sysoev.ru         }
4170Sigor@sysoev.ru 
4180Sigor@sysoev.ru         bkt = nxt_lvlhsh_next_bucket(proto, bucket);
4190Sigor@sysoev.ru 
4200Sigor@sysoev.ru     } while (*bkt != NULL);
4210Sigor@sysoev.ru 
4220Sigor@sysoev.ru     if (vacant_entry != NULL) {
4230Sigor@sysoev.ru         nxt_lvlhsh_set_entry_value(vacant_entry, lhq->value);
4240Sigor@sysoev.ru         nxt_lvlhsh_set_entry_key(vacant_entry, lhq->key_hash);
4250Sigor@sysoev.ru         nxt_lvlhsh_count_inc(*vacant_bucket);
4260Sigor@sysoev.ru 
4270Sigor@sysoev.ru         return NXT_OK;
4280Sigor@sysoev.ru     }
4290Sigor@sysoev.ru 
4300Sigor@sysoev.ru     /* All buckets are full. */
4310Sigor@sysoev.ru 
4320Sigor@sysoev.ru     nlvl++;
4330Sigor@sysoev.ru 
4340Sigor@sysoev.ru     if (nxt_fast_path(proto->shift[nlvl] != 0)) {
4350Sigor@sysoev.ru 
4360Sigor@sysoev.ru         ret = nxt_lvlhsh_convert_bucket_to_level(lhq, slot, nlvl, bucket);
4370Sigor@sysoev.ru 
4380Sigor@sysoev.ru         if (nxt_fast_path(ret == NXT_OK)) {
4390Sigor@sysoev.ru             return nxt_lvlhsh_level_insert(lhq, slot, key, nlvl);
4400Sigor@sysoev.ru         }
4410Sigor@sysoev.ru 
4420Sigor@sysoev.ru         return ret;
4430Sigor@sysoev.ru     }
4440Sigor@sysoev.ru 
4450Sigor@sysoev.ru     /* The last allowed level, only buckets may be allocated here. */
4460Sigor@sysoev.ru 
4470Sigor@sysoev.ru     return nxt_lvlhsh_new_bucket(lhq, bkt);
4480Sigor@sysoev.ru }
4490Sigor@sysoev.ru 
4500Sigor@sysoev.ru 
4510Sigor@sysoev.ru static nxt_int_t
nxt_lvlhsh_convert_bucket_to_level(nxt_lvlhsh_query_t * lhq,void ** slot,nxt_uint_t nlvl,uint32_t * bucket)4520Sigor@sysoev.ru nxt_lvlhsh_convert_bucket_to_level(nxt_lvlhsh_query_t *lhq, void **slot,
4530Sigor@sysoev.ru     nxt_uint_t nlvl, uint32_t *bucket)
4540Sigor@sysoev.ru {
4550Sigor@sysoev.ru     void                      *lvl, **level;
4560Sigor@sysoev.ru     uint32_t                  *e, *end, key;
4570Sigor@sysoev.ru     nxt_int_t                 ret;
4580Sigor@sysoev.ru     nxt_uint_t                i, shift, size;
4590Sigor@sysoev.ru     nxt_lvlhsh_query_t        q;
4600Sigor@sysoev.ru     const nxt_lvlhsh_proto_t  *proto;
4610Sigor@sysoev.ru 
4620Sigor@sysoev.ru     proto = lhq->proto;
4630Sigor@sysoev.ru     size = nxt_lvlhsh_level_size(proto, nlvl);
4640Sigor@sysoev.ru 
46565Sigor@sysoev.ru     lvl = proto->alloc(lhq->pool, size * (sizeof(void *)));
4660Sigor@sysoev.ru 
4670Sigor@sysoev.ru     if (nxt_slow_path(lvl == NULL)) {
4680Sigor@sysoev.ru         return NXT_ERROR;
4690Sigor@sysoev.ru     }
4700Sigor@sysoev.ru 
4710Sigor@sysoev.ru     nxt_memzero(lvl, size * (sizeof(void *)));
4720Sigor@sysoev.ru 
4730Sigor@sysoev.ru     level = lvl;
4740Sigor@sysoev.ru     shift = 0;
4750Sigor@sysoev.ru 
4760Sigor@sysoev.ru     for (i = 0; i < nlvl; i++) {
4770Sigor@sysoev.ru         /*
4780Sigor@sysoev.ru          * Using SIMD operations in this trivial loop with maximum
4790Sigor@sysoev.ru          * 8 iterations may increase code size by 170 bytes.
4800Sigor@sysoev.ru          */
4810Sigor@sysoev.ru         nxt_pragma_loop_disable_vectorization;
4820Sigor@sysoev.ru 
4830Sigor@sysoev.ru         shift += proto->shift[i];
4840Sigor@sysoev.ru     }
4850Sigor@sysoev.ru 
4860Sigor@sysoev.ru     end = nxt_lvlhsh_bucket_end(proto, bucket);
4870Sigor@sysoev.ru 
4880Sigor@sysoev.ru     for (e = bucket; e < end; e += NXT_LVLHSH_ENTRY_SIZE) {
4890Sigor@sysoev.ru 
4900Sigor@sysoev.ru         q.proto = proto;
4910Sigor@sysoev.ru         q.pool = lhq->pool;
4920Sigor@sysoev.ru         q.value = nxt_lvlhsh_entry_value(e);
4930Sigor@sysoev.ru         key = nxt_lvlhsh_entry_key(e);
4940Sigor@sysoev.ru         q.key_hash = key;
4950Sigor@sysoev.ru 
4960Sigor@sysoev.ru         ret = nxt_lvlhsh_level_convertion_insert(&q, &lvl, key >> shift, nlvl);
4970Sigor@sysoev.ru 
4980Sigor@sysoev.ru         if (nxt_slow_path(ret != NXT_OK)) {
4990Sigor@sysoev.ru             return nxt_lvlhsh_free_level(lhq, level, size);
5000Sigor@sysoev.ru         }
5010Sigor@sysoev.ru     }
5020Sigor@sysoev.ru 
5030Sigor@sysoev.ru     *slot = lvl;
5040Sigor@sysoev.ru 
50565Sigor@sysoev.ru     proto->free(lhq->pool, bucket);
5060Sigor@sysoev.ru 
5070Sigor@sysoev.ru     return NXT_OK;
5080Sigor@sysoev.ru }
5090Sigor@sysoev.ru 
5100Sigor@sysoev.ru 
5110Sigor@sysoev.ru static nxt_int_t
nxt_lvlhsh_level_convertion_insert(nxt_lvlhsh_query_t * lhq,void ** parent,uint32_t key,nxt_uint_t nlvl)5120Sigor@sysoev.ru nxt_lvlhsh_level_convertion_insert(nxt_lvlhsh_query_t *lhq, void **parent,
5130Sigor@sysoev.ru     uint32_t key, nxt_uint_t nlvl)
5140Sigor@sysoev.ru {
5150Sigor@sysoev.ru     void        **slot, **lvl;
5160Sigor@sysoev.ru     nxt_int_t   ret;
5170Sigor@sysoev.ru     uintptr_t   mask;
5180Sigor@sysoev.ru     nxt_uint_t  shift;
5190Sigor@sysoev.ru 
5200Sigor@sysoev.ru     shift = lhq->proto->shift[nlvl];
5210Sigor@sysoev.ru     mask = ((uintptr_t) 1 << shift) - 1;
5220Sigor@sysoev.ru 
5230Sigor@sysoev.ru     lvl = nxt_lvlhsh_level(*parent, mask);
5240Sigor@sysoev.ru     slot = &lvl[key & mask];
5250Sigor@sysoev.ru 
5260Sigor@sysoev.ru     if (*slot == NULL) {
5270Sigor@sysoev.ru         ret = nxt_lvlhsh_new_bucket(lhq, slot);
5280Sigor@sysoev.ru 
5290Sigor@sysoev.ru         if (nxt_fast_path(ret == NXT_OK)) {
5300Sigor@sysoev.ru             nxt_lvlhsh_count_inc(*parent);
5310Sigor@sysoev.ru         }
5320Sigor@sysoev.ru 
5330Sigor@sysoev.ru         return ret;
5340Sigor@sysoev.ru     }
5350Sigor@sysoev.ru 
5360Sigor@sysoev.ru     /* Only backets can be here. */
5370Sigor@sysoev.ru 
5380Sigor@sysoev.ru     return nxt_lvlhsh_bucket_convertion_insert(lhq, slot, key >> shift, nlvl);
5390Sigor@sysoev.ru }
5400Sigor@sysoev.ru 
5410Sigor@sysoev.ru 
5420Sigor@sysoev.ru /*
5430Sigor@sysoev.ru  * The special bucket insertion procedure is required because during
5440Sigor@sysoev.ru  * convertion lhq->key contains garbage values and the test function
5450Sigor@sysoev.ru  * cannot be called.  Besides, the procedure can be simpler because
5460Sigor@sysoev.ru  * a new entry is inserted just after occupied entries.
5470Sigor@sysoev.ru  */
5480Sigor@sysoev.ru 
5490Sigor@sysoev.ru static nxt_int_t
nxt_lvlhsh_bucket_convertion_insert(nxt_lvlhsh_query_t * lhq,void ** slot,uint32_t key,nxt_int_t nlvl)5500Sigor@sysoev.ru nxt_lvlhsh_bucket_convertion_insert(nxt_lvlhsh_query_t *lhq, void **slot,
5510Sigor@sysoev.ru     uint32_t key, nxt_int_t nlvl)
5520Sigor@sysoev.ru {
5530Sigor@sysoev.ru     void                      **bkt;
5540Sigor@sysoev.ru     uint32_t                  *bucket, *e;
5550Sigor@sysoev.ru     nxt_int_t                 ret;
5560Sigor@sysoev.ru     uintptr_t                 n;
5570Sigor@sysoev.ru     const nxt_lvlhsh_proto_t  *proto;
5580Sigor@sysoev.ru 
5590Sigor@sysoev.ru     bkt = slot;
5600Sigor@sysoev.ru     proto = lhq->proto;
5610Sigor@sysoev.ru 
5620Sigor@sysoev.ru     do {
5630Sigor@sysoev.ru         bucket = nxt_lvlhsh_bucket(proto, *bkt);
5640Sigor@sysoev.ru         n = nxt_lvlhsh_bucket_entries(proto, *bkt);
5650Sigor@sysoev.ru         e = bucket + n * NXT_LVLHSH_ENTRY_SIZE;
5660Sigor@sysoev.ru 
5670Sigor@sysoev.ru         if (nxt_fast_path(e < nxt_lvlhsh_bucket_end(proto, bucket))) {
5680Sigor@sysoev.ru 
5690Sigor@sysoev.ru             nxt_lvlhsh_set_entry_value(e, lhq->value);
5700Sigor@sysoev.ru             nxt_lvlhsh_set_entry_key(e, lhq->key_hash);
5710Sigor@sysoev.ru             nxt_lvlhsh_count_inc(*bkt);
5720Sigor@sysoev.ru 
5730Sigor@sysoev.ru             return NXT_OK;
5740Sigor@sysoev.ru         }
5750Sigor@sysoev.ru 
5760Sigor@sysoev.ru         bkt = nxt_lvlhsh_next_bucket(proto, bucket);
5770Sigor@sysoev.ru 
5780Sigor@sysoev.ru     } while (*bkt != NULL);
5790Sigor@sysoev.ru 
5800Sigor@sysoev.ru     /* All buckets are full. */
5810Sigor@sysoev.ru 
5820Sigor@sysoev.ru     nlvl++;
5830Sigor@sysoev.ru 
5840Sigor@sysoev.ru     if (nxt_fast_path(proto->shift[nlvl] != 0)) {
5850Sigor@sysoev.ru 
5860Sigor@sysoev.ru         ret = nxt_lvlhsh_convert_bucket_to_level(lhq, slot, nlvl, bucket);
5870Sigor@sysoev.ru 
5880Sigor@sysoev.ru         if (nxt_fast_path(ret == NXT_OK)) {
5890Sigor@sysoev.ru             return nxt_lvlhsh_level_insert(lhq, slot, key, nlvl);
5900Sigor@sysoev.ru         }
5910Sigor@sysoev.ru 
5920Sigor@sysoev.ru         return ret;
5930Sigor@sysoev.ru     }
5940Sigor@sysoev.ru 
5950Sigor@sysoev.ru     /* The last allowed level, only buckets may be allocated here. */
5960Sigor@sysoev.ru 
5970Sigor@sysoev.ru     return nxt_lvlhsh_new_bucket(lhq, bkt);
5980Sigor@sysoev.ru }
5990Sigor@sysoev.ru 
6000Sigor@sysoev.ru 
6010Sigor@sysoev.ru static nxt_int_t
nxt_lvlhsh_free_level(nxt_lvlhsh_query_t * lhq,void ** level,nxt_uint_t size)6020Sigor@sysoev.ru nxt_lvlhsh_free_level(nxt_lvlhsh_query_t *lhq, void **level, nxt_uint_t size)
6030Sigor@sysoev.ru {
6040Sigor@sysoev.ru     nxt_uint_t                i;
6050Sigor@sysoev.ru     const nxt_lvlhsh_proto_t  *proto;
6060Sigor@sysoev.ru 
6070Sigor@sysoev.ru     proto = lhq->proto;
6080Sigor@sysoev.ru 
6090Sigor@sysoev.ru     for (i = 0; i < size; i++) {
6100Sigor@sysoev.ru 
6110Sigor@sysoev.ru         if (level[i] != NULL) {
6120Sigor@sysoev.ru             /*
6130Sigor@sysoev.ru              * Chained buckets are not possible here, since even
6140Sigor@sysoev.ru              * in the worst case one bucket cannot be converted
6150Sigor@sysoev.ru              * in two chained buckets but remains the same bucket.
6160Sigor@sysoev.ru              */
61765Sigor@sysoev.ru             proto->free(lhq->pool, nxt_lvlhsh_bucket(proto, level[i]));
6180Sigor@sysoev.ru         }
6190Sigor@sysoev.ru     }
6200Sigor@sysoev.ru 
62165Sigor@sysoev.ru     proto->free(lhq->pool, level);
6220Sigor@sysoev.ru 
6230Sigor@sysoev.ru     return NXT_ERROR;
6240Sigor@sysoev.ru }
6250Sigor@sysoev.ru 
6260Sigor@sysoev.ru 
6270Sigor@sysoev.ru nxt_int_t
nxt_lvlhsh_delete(nxt_lvlhsh_t * lh,nxt_lvlhsh_query_t * lhq)6280Sigor@sysoev.ru nxt_lvlhsh_delete(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq)
6290Sigor@sysoev.ru {
6300Sigor@sysoev.ru     if (nxt_fast_path(lh->slot != NULL)) {
6310Sigor@sysoev.ru 
6320Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(lh->slot)) {
6330Sigor@sysoev.ru             return nxt_lvlhsh_bucket_delete(lhq, &lh->slot);
6340Sigor@sysoev.ru         }
6350Sigor@sysoev.ru 
6360Sigor@sysoev.ru         return nxt_lvlhsh_level_delete(lhq, &lh->slot, lhq->key_hash, 0);
6370Sigor@sysoev.ru     }
6380Sigor@sysoev.ru 
6390Sigor@sysoev.ru     return NXT_DECLINED;
6400Sigor@sysoev.ru }
6410Sigor@sysoev.ru 
6420Sigor@sysoev.ru 
6430Sigor@sysoev.ru static nxt_int_t
nxt_lvlhsh_level_delete(nxt_lvlhsh_query_t * lhq,void ** parent,uint32_t key,nxt_uint_t nlvl)6440Sigor@sysoev.ru nxt_lvlhsh_level_delete(nxt_lvlhsh_query_t *lhq, void **parent, uint32_t key,
6450Sigor@sysoev.ru     nxt_uint_t nlvl)
6460Sigor@sysoev.ru {
6470Sigor@sysoev.ru     void        **slot, **lvl;
6480Sigor@sysoev.ru     uintptr_t   mask;
6490Sigor@sysoev.ru     nxt_int_t   ret;
6500Sigor@sysoev.ru     nxt_uint_t  shift;
6510Sigor@sysoev.ru 
6520Sigor@sysoev.ru     shift = lhq->proto->shift[nlvl];
6530Sigor@sysoev.ru     mask = ((uintptr_t) 1 << shift) - 1;
6540Sigor@sysoev.ru 
6550Sigor@sysoev.ru     lvl = nxt_lvlhsh_level(*parent, mask);
6560Sigor@sysoev.ru     slot = &lvl[key & mask];
6570Sigor@sysoev.ru 
6580Sigor@sysoev.ru     if (*slot != NULL) {
6590Sigor@sysoev.ru 
6600Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(*slot)) {
6610Sigor@sysoev.ru             ret = nxt_lvlhsh_bucket_delete(lhq, slot);
6620Sigor@sysoev.ru 
6630Sigor@sysoev.ru         } else {
6640Sigor@sysoev.ru             key >>= shift;
6650Sigor@sysoev.ru             ret = nxt_lvlhsh_level_delete(lhq, slot, key, nlvl + 1);
6660Sigor@sysoev.ru         }
6670Sigor@sysoev.ru 
6680Sigor@sysoev.ru         if (*slot == NULL) {
6690Sigor@sysoev.ru             nxt_lvlhsh_count_dec(*parent);
6700Sigor@sysoev.ru 
6710Sigor@sysoev.ru             if (nxt_lvlhsh_level_entries(*parent, mask) == 0) {
6720Sigor@sysoev.ru                 *parent = NULL;
67365Sigor@sysoev.ru                 lhq->proto->free(lhq->pool, lvl);
6740Sigor@sysoev.ru             }
6750Sigor@sysoev.ru         }
6760Sigor@sysoev.ru 
6770Sigor@sysoev.ru         return ret;
6780Sigor@sysoev.ru     }
6790Sigor@sysoev.ru 
6800Sigor@sysoev.ru     return NXT_DECLINED;
6810Sigor@sysoev.ru }
6820Sigor@sysoev.ru 
6830Sigor@sysoev.ru 
6840Sigor@sysoev.ru static nxt_int_t
nxt_lvlhsh_bucket_delete(nxt_lvlhsh_query_t * lhq,void ** bkt)6850Sigor@sysoev.ru nxt_lvlhsh_bucket_delete(nxt_lvlhsh_query_t *lhq, void **bkt)
6860Sigor@sysoev.ru {
6870Sigor@sysoev.ru     void                      *value;
6880Sigor@sysoev.ru     uint32_t                  *bucket, *e;
6890Sigor@sysoev.ru     uintptr_t                 n;
6900Sigor@sysoev.ru     const nxt_lvlhsh_proto_t  *proto;
6910Sigor@sysoev.ru 
6920Sigor@sysoev.ru     proto = lhq->proto;
6930Sigor@sysoev.ru 
6940Sigor@sysoev.ru     do {
6950Sigor@sysoev.ru         bucket = nxt_lvlhsh_bucket(proto, *bkt);
6960Sigor@sysoev.ru         n = nxt_lvlhsh_bucket_entries(proto, *bkt);
6970Sigor@sysoev.ru         e = bucket;
6980Sigor@sysoev.ru 
6990Sigor@sysoev.ru         do {
7000Sigor@sysoev.ru             if (nxt_lvlhsh_valid_entry(e)) {
7010Sigor@sysoev.ru 
7020Sigor@sysoev.ru                 if (nxt_lvlhsh_entry_key(e) == lhq->key_hash) {
7030Sigor@sysoev.ru 
7040Sigor@sysoev.ru                     value = nxt_lvlhsh_entry_value(e);
7050Sigor@sysoev.ru 
7060Sigor@sysoev.ru                     if (proto->test(lhq, value) == NXT_OK) {
7070Sigor@sysoev.ru 
7080Sigor@sysoev.ru                         if (nxt_lvlhsh_bucket_entries(proto, *bkt) == 1) {
7090Sigor@sysoev.ru                             *bkt = *nxt_lvlhsh_next_bucket(proto, bucket);
71065Sigor@sysoev.ru                             proto->free(lhq->pool, bucket);
7110Sigor@sysoev.ru 
7120Sigor@sysoev.ru                         } else {
7130Sigor@sysoev.ru                             nxt_lvlhsh_count_dec(*bkt);
7140Sigor@sysoev.ru                             nxt_lvlhsh_set_entry_value(e, NULL);
7150Sigor@sysoev.ru                         }
7160Sigor@sysoev.ru 
7170Sigor@sysoev.ru                         lhq->value = value;
7180Sigor@sysoev.ru 
7190Sigor@sysoev.ru                         return NXT_OK;
7200Sigor@sysoev.ru                     }
7210Sigor@sysoev.ru                 }
7220Sigor@sysoev.ru 
7230Sigor@sysoev.ru                 n--;
7240Sigor@sysoev.ru             }
7250Sigor@sysoev.ru 
7260Sigor@sysoev.ru             e += NXT_LVLHSH_ENTRY_SIZE;
7270Sigor@sysoev.ru 
7280Sigor@sysoev.ru         } while (n != 0);
7290Sigor@sysoev.ru 
7300Sigor@sysoev.ru         bkt = nxt_lvlhsh_next_bucket(proto, bucket);
7310Sigor@sysoev.ru 
7320Sigor@sysoev.ru     } while (*bkt != NULL);
7330Sigor@sysoev.ru 
7340Sigor@sysoev.ru     return NXT_DECLINED;
7350Sigor@sysoev.ru }
7360Sigor@sysoev.ru 
7370Sigor@sysoev.ru 
7380Sigor@sysoev.ru void *
nxt_lvlhsh_each(nxt_lvlhsh_t * lh,nxt_lvlhsh_each_t * lhe)7390Sigor@sysoev.ru nxt_lvlhsh_each(nxt_lvlhsh_t *lh, nxt_lvlhsh_each_t *lhe)
7400Sigor@sysoev.ru {
7410Sigor@sysoev.ru     void  **slot;
7420Sigor@sysoev.ru 
7430Sigor@sysoev.ru     if (lhe->bucket == NXT_LVLHSH_BUCKET_DONE) {
7440Sigor@sysoev.ru         slot = lh->slot;
7450Sigor@sysoev.ru 
7460Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(slot)) {
7470Sigor@sysoev.ru             return NULL;
7480Sigor@sysoev.ru         }
7490Sigor@sysoev.ru 
7500Sigor@sysoev.ru     } else {
7510Sigor@sysoev.ru         if (nxt_slow_path(lhe->bucket == NULL)) {
7520Sigor@sysoev.ru 
7530Sigor@sysoev.ru             /* The first iteration only. */
7540Sigor@sysoev.ru 
7550Sigor@sysoev.ru             slot = lh->slot;
7560Sigor@sysoev.ru 
7570Sigor@sysoev.ru             if (slot == NULL) {
7580Sigor@sysoev.ru                 return NULL;
7590Sigor@sysoev.ru             }
7600Sigor@sysoev.ru 
7610Sigor@sysoev.ru             if (!nxt_lvlhsh_is_bucket(slot)) {
762598Sigor@sysoev.ru                 lhe->current = 0;
7630Sigor@sysoev.ru                 goto level;
7640Sigor@sysoev.ru             }
7650Sigor@sysoev.ru 
7660Sigor@sysoev.ru             lhe->bucket = nxt_lvlhsh_bucket(lhe->proto, slot);
7670Sigor@sysoev.ru             lhe->entries = nxt_lvlhsh_bucket_entries(lhe->proto, slot);
768598Sigor@sysoev.ru             lhe->entry = 0;
7690Sigor@sysoev.ru         }
7700Sigor@sysoev.ru 
7710Sigor@sysoev.ru         return nxt_lvlhsh_bucket_each(lhe);
7720Sigor@sysoev.ru     }
7730Sigor@sysoev.ru 
7740Sigor@sysoev.ru level:
7750Sigor@sysoev.ru 
7760Sigor@sysoev.ru     return nxt_lvlhsh_level_each(lhe, slot, 0, 0);
7770Sigor@sysoev.ru }
7780Sigor@sysoev.ru 
7790Sigor@sysoev.ru 
7800Sigor@sysoev.ru static void *
nxt_lvlhsh_level_each(nxt_lvlhsh_each_t * lhe,void ** level,nxt_uint_t nlvl,nxt_uint_t shift)7810Sigor@sysoev.ru nxt_lvlhsh_level_each(nxt_lvlhsh_each_t *lhe, void **level, nxt_uint_t nlvl,
7820Sigor@sysoev.ru     nxt_uint_t shift)
7830Sigor@sysoev.ru {
7840Sigor@sysoev.ru     void        **slot, *value;
7850Sigor@sysoev.ru     uintptr_t   mask;
7860Sigor@sysoev.ru     nxt_uint_t  n, level_shift;
7870Sigor@sysoev.ru 
7880Sigor@sysoev.ru     level_shift = lhe->proto->shift[nlvl];
7890Sigor@sysoev.ru     mask = ((uintptr_t) 1 << level_shift) - 1;
7900Sigor@sysoev.ru 
7910Sigor@sysoev.ru     level = nxt_lvlhsh_level(level, mask);
7920Sigor@sysoev.ru 
7930Sigor@sysoev.ru     do {
7940Sigor@sysoev.ru         n = (lhe->current >> shift) & mask;
7950Sigor@sysoev.ru         slot = level[n];
7960Sigor@sysoev.ru 
7970Sigor@sysoev.ru         if (slot != NULL) {
7980Sigor@sysoev.ru             if (nxt_lvlhsh_is_bucket(slot)) {
7990Sigor@sysoev.ru 
8000Sigor@sysoev.ru                 if (lhe->bucket != NXT_LVLHSH_BUCKET_DONE) {
8010Sigor@sysoev.ru 
8020Sigor@sysoev.ru                     lhe->bucket = nxt_lvlhsh_bucket(lhe->proto, slot);
8030Sigor@sysoev.ru                     lhe->entries = nxt_lvlhsh_bucket_entries(lhe->proto, slot);
8040Sigor@sysoev.ru                     lhe->entry = 0;
8050Sigor@sysoev.ru 
8060Sigor@sysoev.ru                     return nxt_lvlhsh_bucket_each(lhe);
8070Sigor@sysoev.ru                 }
8080Sigor@sysoev.ru 
8090Sigor@sysoev.ru                 lhe->bucket = NULL;
8100Sigor@sysoev.ru 
8110Sigor@sysoev.ru             } else {
8120Sigor@sysoev.ru                 value = nxt_lvlhsh_level_each(lhe, slot, nlvl + 1,
8130Sigor@sysoev.ru                                               shift + level_shift);
8140Sigor@sysoev.ru                 if (value != NULL) {
8150Sigor@sysoev.ru                     return value;
8160Sigor@sysoev.ru                 }
8170Sigor@sysoev.ru             }
8180Sigor@sysoev.ru         }
8190Sigor@sysoev.ru 
8200Sigor@sysoev.ru         lhe->current &= ~(mask << shift);
8210Sigor@sysoev.ru         n = ((n + 1) & mask) << shift;
8220Sigor@sysoev.ru         lhe->current |= n;
8230Sigor@sysoev.ru 
8240Sigor@sysoev.ru     } while (n != 0);
8250Sigor@sysoev.ru 
8260Sigor@sysoev.ru     return NULL;
8270Sigor@sysoev.ru }
8280Sigor@sysoev.ru 
8290Sigor@sysoev.ru 
8300Sigor@sysoev.ru static nxt_noinline void *
nxt_lvlhsh_bucket_each(nxt_lvlhsh_each_t * lhe)8310Sigor@sysoev.ru nxt_lvlhsh_bucket_each(nxt_lvlhsh_each_t *lhe)
8320Sigor@sysoev.ru {
8330Sigor@sysoev.ru     void      *value, **next;
8340Sigor@sysoev.ru     uint32_t  *bucket;
8350Sigor@sysoev.ru 
8360Sigor@sysoev.ru     /* At least one valid entry must present here. */
8370Sigor@sysoev.ru     do {
8380Sigor@sysoev.ru         bucket = &lhe->bucket[lhe->entry];
8390Sigor@sysoev.ru         lhe->entry += NXT_LVLHSH_ENTRY_SIZE;
8400Sigor@sysoev.ru 
8410Sigor@sysoev.ru     } while (nxt_lvlhsh_free_entry(bucket));
8420Sigor@sysoev.ru 
8430Sigor@sysoev.ru     value = nxt_lvlhsh_entry_value(bucket);
8440Sigor@sysoev.ru 
8450Sigor@sysoev.ru     lhe->entries--;
8460Sigor@sysoev.ru 
8470Sigor@sysoev.ru     if (lhe->entries == 0) {
8480Sigor@sysoev.ru         next = *nxt_lvlhsh_next_bucket(lhe->proto, lhe->bucket);
8490Sigor@sysoev.ru 
85072Sigor@sysoev.ru         lhe->bucket = (next == NULL) ? NXT_LVLHSH_BUCKET_DONE
85172Sigor@sysoev.ru                                      : nxt_lvlhsh_bucket(lhe->proto, next);
8520Sigor@sysoev.ru 
8530Sigor@sysoev.ru         lhe->entries = nxt_lvlhsh_bucket_entries(lhe->proto, next);
8540Sigor@sysoev.ru         lhe->entry = 0;
8550Sigor@sysoev.ru     }
8560Sigor@sysoev.ru 
8570Sigor@sysoev.ru     return value;
8580Sigor@sysoev.ru }
8590Sigor@sysoev.ru 
8600Sigor@sysoev.ru 
8610Sigor@sysoev.ru void *
nxt_lvlhsh_peek(nxt_lvlhsh_t * lh,const nxt_lvlhsh_proto_t * proto)862594Sigor@sysoev.ru nxt_lvlhsh_peek(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto)
863594Sigor@sysoev.ru {
864595Sigor@sysoev.ru     void               **slot;
865595Sigor@sysoev.ru     nxt_lvlhsh_peek_t  peek;
866594Sigor@sysoev.ru 
867594Sigor@sysoev.ru     slot = lh->slot;
868594Sigor@sysoev.ru 
869594Sigor@sysoev.ru     if (slot != NULL) {
870594Sigor@sysoev.ru 
871595Sigor@sysoev.ru         peek.proto = proto;
872595Sigor@sysoev.ru         peek.retrieve = 0;
873595Sigor@sysoev.ru 
874594Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(slot)) {
875595Sigor@sysoev.ru             return nxt_lvlhsh_bucket_peek(&peek, &lh->slot);
876594Sigor@sysoev.ru         }
877594Sigor@sysoev.ru 
878595Sigor@sysoev.ru         return nxt_lvlhsh_level_peek(&peek, &lh->slot, 0);
879594Sigor@sysoev.ru     }
880594Sigor@sysoev.ru 
881594Sigor@sysoev.ru     return NULL;
882594Sigor@sysoev.ru }
883594Sigor@sysoev.ru 
884594Sigor@sysoev.ru 
885594Sigor@sysoev.ru static void *
nxt_lvlhsh_level_peek(nxt_lvlhsh_peek_t * peek,void ** parent,nxt_uint_t nlvl)886595Sigor@sysoev.ru nxt_lvlhsh_level_peek(nxt_lvlhsh_peek_t *peek, void **parent, nxt_uint_t nlvl)
887594Sigor@sysoev.ru {
888595Sigor@sysoev.ru     void        **slot, **level, *value;
889594Sigor@sysoev.ru     uintptr_t   mask;
890594Sigor@sysoev.ru     nxt_uint_t  n, shift;
891594Sigor@sysoev.ru 
892595Sigor@sysoev.ru     shift = peek->proto->shift[nlvl];
893594Sigor@sysoev.ru     mask = ((uintptr_t) 1 << shift) - 1;
894594Sigor@sysoev.ru 
895595Sigor@sysoev.ru     level = nxt_lvlhsh_level(*parent, mask);
896594Sigor@sysoev.ru 
897594Sigor@sysoev.ru     n = 0;
898594Sigor@sysoev.ru 
899594Sigor@sysoev.ru     /* At least one valid level slot must present here. */
900594Sigor@sysoev.ru 
901594Sigor@sysoev.ru     for ( ;; ) {
902595Sigor@sysoev.ru         slot = &level[n];
903595Sigor@sysoev.ru 
904595Sigor@sysoev.ru         if (*slot != NULL) {
905594Sigor@sysoev.ru 
906595Sigor@sysoev.ru             if (nxt_lvlhsh_is_bucket(*slot)) {
907595Sigor@sysoev.ru                 value = nxt_lvlhsh_bucket_peek(peek, slot);
908594Sigor@sysoev.ru 
909595Sigor@sysoev.ru             } else {
910595Sigor@sysoev.ru                 value = nxt_lvlhsh_level_peek(peek, slot, nlvl + 1);
911594Sigor@sysoev.ru             }
912594Sigor@sysoev.ru 
913595Sigor@sysoev.ru             /*
914595Sigor@sysoev.ru              * Checking peek->retrieve is not required here because
915595Sigor@sysoev.ru              * there can not be empty slots during peeking.
916595Sigor@sysoev.ru              */
917595Sigor@sysoev.ru             if (*slot == NULL) {
918595Sigor@sysoev.ru                 nxt_lvlhsh_count_dec(*parent);
919595Sigor@sysoev.ru 
920595Sigor@sysoev.ru                 if (nxt_lvlhsh_level_entries(*parent, mask) == 0) {
921595Sigor@sysoev.ru                     *parent = NULL;
922595Sigor@sysoev.ru                     peek->proto->free(peek->pool, level);
923595Sigor@sysoev.ru                 }
924595Sigor@sysoev.ru             }
925595Sigor@sysoev.ru 
926595Sigor@sysoev.ru             return value;
927