xref: /unit/src/nxt_lvlhsh.c (revision 598)
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 
460Sigor@sysoev.ru #define                                                                       \
470Sigor@sysoev.ru nxt_lvlhsh_is_bucket(p)                                                       \
480Sigor@sysoev.ru     ((uintptr_t) (p) & 1)
490Sigor@sysoev.ru 
500Sigor@sysoev.ru 
510Sigor@sysoev.ru #define                                                                       \
520Sigor@sysoev.ru nxt_lvlhsh_count_inc(n)                                                       \
530Sigor@sysoev.ru     n = (void *) ((uintptr_t) (n) + 2)
540Sigor@sysoev.ru 
550Sigor@sysoev.ru 
560Sigor@sysoev.ru #define                                                                       \
570Sigor@sysoev.ru nxt_lvlhsh_count_dec(n)                                                       \
580Sigor@sysoev.ru     n = (void *) ((uintptr_t) (n) - 2)
590Sigor@sysoev.ru 
600Sigor@sysoev.ru 
610Sigor@sysoev.ru #define                                                                       \
620Sigor@sysoev.ru nxt_lvlhsh_level_size(proto, nlvl)                                            \
630Sigor@sysoev.ru     ((uintptr_t) 1 << proto->shift[nlvl])
640Sigor@sysoev.ru 
650Sigor@sysoev.ru 
660Sigor@sysoev.ru #define                                                                       \
670Sigor@sysoev.ru nxt_lvlhsh_level(lvl, mask)                                                   \
680Sigor@sysoev.ru     (void **) ((uintptr_t) lvl & (~mask << 2))
690Sigor@sysoev.ru 
700Sigor@sysoev.ru 
710Sigor@sysoev.ru #define                                                                       \
720Sigor@sysoev.ru nxt_lvlhsh_level_entries(lvl, mask)                                           \
730Sigor@sysoev.ru     ((uintptr_t) lvl & (mask << 1))
740Sigor@sysoev.ru 
750Sigor@sysoev.ru 
760Sigor@sysoev.ru #define                                                                       \
770Sigor@sysoev.ru nxt_lvlhsh_store_bucket(slot, bkt)                                            \
780Sigor@sysoev.ru     slot = (void **) ((uintptr_t) bkt | 2 | 1)
790Sigor@sysoev.ru 
800Sigor@sysoev.ru 
810Sigor@sysoev.ru #define                                                                       \
820Sigor@sysoev.ru nxt_lvlhsh_bucket_size(proto)                                                 \
830Sigor@sysoev.ru     proto->bucket_size
840Sigor@sysoev.ru 
850Sigor@sysoev.ru 
860Sigor@sysoev.ru #define                                                                       \
870Sigor@sysoev.ru nxt_lvlhsh_bucket(proto, bkt)                                                 \
880Sigor@sysoev.ru     (uint32_t *) ((uintptr_t) bkt & ~(uintptr_t) proto->bucket_mask)
890Sigor@sysoev.ru 
900Sigor@sysoev.ru 
910Sigor@sysoev.ru #define                                                                       \
920Sigor@sysoev.ru nxt_lvlhsh_bucket_entries(proto, bkt)                                         \
930Sigor@sysoev.ru     (((uintptr_t) bkt & (uintptr_t) proto->bucket_mask) >> 1)
940Sigor@sysoev.ru 
950Sigor@sysoev.ru 
960Sigor@sysoev.ru #define                                                                       \
970Sigor@sysoev.ru nxt_lvlhsh_bucket_end(proto, bkt)                                             \
980Sigor@sysoev.ru     &bkt[proto->bucket_end]
990Sigor@sysoev.ru 
1000Sigor@sysoev.ru 
1010Sigor@sysoev.ru #define                                                                       \
1020Sigor@sysoev.ru nxt_lvlhsh_free_entry(e)                                                      \
1030Sigor@sysoev.ru     (!(nxt_lvlhsh_valid_entry(e)))
1040Sigor@sysoev.ru 
1050Sigor@sysoev.ru 
1060Sigor@sysoev.ru #define                                                                       \
1070Sigor@sysoev.ru nxt_lvlhsh_next_bucket(proto, bkt)                                            \
1080Sigor@sysoev.ru     ((void **) &bkt[proto->bucket_end])
1090Sigor@sysoev.ru 
1100Sigor@sysoev.ru #if (NXT_64BIT)
1110Sigor@sysoev.ru 
1120Sigor@sysoev.ru #define                                                                       \
1130Sigor@sysoev.ru nxt_lvlhsh_valid_entry(e)                                                     \
1140Sigor@sysoev.ru     (((e)[0] | (e)[1]) != 0)
1150Sigor@sysoev.ru 
1160Sigor@sysoev.ru 
1170Sigor@sysoev.ru #define                                                                       \
1180Sigor@sysoev.ru nxt_lvlhsh_entry_value(e)                                                     \
1190Sigor@sysoev.ru     (void *) (((uintptr_t) (e)[1] << 32) + (e)[0])
1200Sigor@sysoev.ru 
1210Sigor@sysoev.ru 
1220Sigor@sysoev.ru #define                                                                       \
1230Sigor@sysoev.ru nxt_lvlhsh_set_entry_value(e, n)                                              \
1240Sigor@sysoev.ru     (e)[0] = (uint32_t)  (uintptr_t) n;                                       \
1250Sigor@sysoev.ru     (e)[1] = (uint32_t) ((uintptr_t) n >> 32)
1260Sigor@sysoev.ru 
1270Sigor@sysoev.ru 
1280Sigor@sysoev.ru #define                                                                       \
1290Sigor@sysoev.ru nxt_lvlhsh_entry_key(e)                                                       \
1300Sigor@sysoev.ru     (e)[2]
1310Sigor@sysoev.ru 
1320Sigor@sysoev.ru 
1330Sigor@sysoev.ru #define                                                                       \
1340Sigor@sysoev.ru nxt_lvlhsh_set_entry_key(e, n)                                                \
1350Sigor@sysoev.ru     (e)[2] = n
1360Sigor@sysoev.ru 
1370Sigor@sysoev.ru #else
1380Sigor@sysoev.ru 
1390Sigor@sysoev.ru #define                                                                       \
1400Sigor@sysoev.ru nxt_lvlhsh_valid_entry(e)                                                     \
1410Sigor@sysoev.ru     ((e)[0] != 0)
1420Sigor@sysoev.ru 
1430Sigor@sysoev.ru 
1440Sigor@sysoev.ru #define                                                                       \
1450Sigor@sysoev.ru nxt_lvlhsh_entry_value(e)                                                     \
1460Sigor@sysoev.ru     (void *) (e)[0]
1470Sigor@sysoev.ru 
1480Sigor@sysoev.ru 
1490Sigor@sysoev.ru #define                                                                       \
1500Sigor@sysoev.ru nxt_lvlhsh_set_entry_value(e, n)                                              \
1510Sigor@sysoev.ru     (e)[0] = (uint32_t) n
1520Sigor@sysoev.ru 
1530Sigor@sysoev.ru 
1540Sigor@sysoev.ru #define                                                                       \
1550Sigor@sysoev.ru nxt_lvlhsh_entry_key(e)                                                       \
1560Sigor@sysoev.ru     (e)[1]
1570Sigor@sysoev.ru 
1580Sigor@sysoev.ru 
1590Sigor@sysoev.ru #define                                                                       \
1600Sigor@sysoev.ru nxt_lvlhsh_set_entry_key(e, n)                                                \
1610Sigor@sysoev.ru     (e)[1] = n
1620Sigor@sysoev.ru 
1630Sigor@sysoev.ru #endif
1640Sigor@sysoev.ru 
1650Sigor@sysoev.ru 
1660Sigor@sysoev.ru #define NXT_LVLHSH_BUCKET_DONE  ((void *) -1)
1670Sigor@sysoev.ru 
1680Sigor@sysoev.ru 
169595Sigor@sysoev.ru typedef struct {
170595Sigor@sysoev.ru     const nxt_lvlhsh_proto_t  *proto;
171595Sigor@sysoev.ru     void                      *pool;
172595Sigor@sysoev.ru     uint32_t                  retrieve;  /* 1 bit */
173595Sigor@sysoev.ru } nxt_lvlhsh_peek_t;
174595Sigor@sysoev.ru 
175595Sigor@sysoev.ru 
1760Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_level_find(nxt_lvlhsh_query_t *lhq, void **lvl,
1770Sigor@sysoev.ru     uint32_t key, nxt_uint_t nlvl);
1780Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_bucket_find(nxt_lvlhsh_query_t *lhq, void **bkt);
1790Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_new_bucket(nxt_lvlhsh_query_t *lhq, void **slot);
1800Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_level_insert(nxt_lvlhsh_query_t *lhq,
1810Sigor@sysoev.ru     void **slot, uint32_t key, nxt_uint_t nlvl);
1820Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_bucket_insert(nxt_lvlhsh_query_t *lhq,
1830Sigor@sysoev.ru     void **slot, uint32_t key, nxt_int_t nlvl);
1840Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_convert_bucket_to_level(nxt_lvlhsh_query_t *lhq,
1850Sigor@sysoev.ru     void **slot, nxt_uint_t nlvl, uint32_t *bucket);
1860Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_level_convertion_insert(nxt_lvlhsh_query_t *lhq,
1870Sigor@sysoev.ru     void **parent, uint32_t key, nxt_uint_t nlvl);
1880Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_bucket_convertion_insert(nxt_lvlhsh_query_t *lhq,
1890Sigor@sysoev.ru     void **slot, uint32_t key, nxt_int_t nlvl);
1900Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_free_level(nxt_lvlhsh_query_t *lhq, void **level,
1910Sigor@sysoev.ru     nxt_uint_t size);
1920Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_level_delete(nxt_lvlhsh_query_t *lhq, void **slot,
1930Sigor@sysoev.ru     uint32_t key, nxt_uint_t nlvl);
1940Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_bucket_delete(nxt_lvlhsh_query_t *lhq, void **bkt);
1950Sigor@sysoev.ru static void *nxt_lvlhsh_level_each(nxt_lvlhsh_each_t *lhe, void **level,
1960Sigor@sysoev.ru     nxt_uint_t nlvl, nxt_uint_t shift);
1970Sigor@sysoev.ru static void *nxt_lvlhsh_bucket_each(nxt_lvlhsh_each_t *lhe);
198595Sigor@sysoev.ru static void *nxt_lvlhsh_level_peek(nxt_lvlhsh_peek_t *peek, void **level,
199595Sigor@sysoev.ru     nxt_uint_t nlvl);
200595Sigor@sysoev.ru static void *nxt_lvlhsh_bucket_peek(nxt_lvlhsh_peek_t *peek, void **bkt);
2010Sigor@sysoev.ru 
2020Sigor@sysoev.ru 
2030Sigor@sysoev.ru nxt_int_t
2040Sigor@sysoev.ru nxt_lvlhsh_find(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq)
2050Sigor@sysoev.ru {
2060Sigor@sysoev.ru     void  *slot;
2070Sigor@sysoev.ru 
2080Sigor@sysoev.ru     slot = lh->slot;
2090Sigor@sysoev.ru 
2100Sigor@sysoev.ru     if (nxt_fast_path(slot != NULL)) {
2110Sigor@sysoev.ru 
2120Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(slot)) {
2130Sigor@sysoev.ru             return nxt_lvlhsh_bucket_find(lhq, slot);
2140Sigor@sysoev.ru         }
2150Sigor@sysoev.ru 
2160Sigor@sysoev.ru         return nxt_lvlhsh_level_find(lhq, slot, lhq->key_hash, 0);
2170Sigor@sysoev.ru     }
2180Sigor@sysoev.ru 
2190Sigor@sysoev.ru     return NXT_DECLINED;
2200Sigor@sysoev.ru }
2210Sigor@sysoev.ru 
2220Sigor@sysoev.ru 
2230Sigor@sysoev.ru static nxt_int_t
2240Sigor@sysoev.ru nxt_lvlhsh_level_find(nxt_lvlhsh_query_t *lhq, void **lvl, uint32_t key,
2250Sigor@sysoev.ru     nxt_uint_t nlvl)
2260Sigor@sysoev.ru {
2270Sigor@sysoev.ru     void        **slot;
2280Sigor@sysoev.ru     uintptr_t   mask;
2290Sigor@sysoev.ru     nxt_uint_t  shift;
2300Sigor@sysoev.ru 
2310Sigor@sysoev.ru     shift = lhq->proto->shift[nlvl];
2320Sigor@sysoev.ru     mask = ((uintptr_t) 1 << shift) - 1;
2330Sigor@sysoev.ru 
2340Sigor@sysoev.ru     lvl = nxt_lvlhsh_level(lvl, mask);
2350Sigor@sysoev.ru     slot = lvl[key & mask];
2360Sigor@sysoev.ru 
2370Sigor@sysoev.ru     if (slot != NULL) {
2380Sigor@sysoev.ru 
2390Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(slot)) {
2400Sigor@sysoev.ru             return nxt_lvlhsh_bucket_find(lhq, slot);
2410Sigor@sysoev.ru         }
2420Sigor@sysoev.ru 
2430Sigor@sysoev.ru         return nxt_lvlhsh_level_find(lhq, slot, key >> shift, nlvl + 1);
2440Sigor@sysoev.ru     }
2450Sigor@sysoev.ru 
2460Sigor@sysoev.ru     return NXT_DECLINED;
2470Sigor@sysoev.ru }
2480Sigor@sysoev.ru 
2490Sigor@sysoev.ru 
2500Sigor@sysoev.ru static nxt_int_t
2510Sigor@sysoev.ru nxt_lvlhsh_bucket_find(nxt_lvlhsh_query_t *lhq, void **bkt)
2520Sigor@sysoev.ru {
2530Sigor@sysoev.ru     void        *value;
2540Sigor@sysoev.ru     uint32_t    *bucket, *e;
2550Sigor@sysoev.ru     nxt_uint_t  n;
2560Sigor@sysoev.ru 
2570Sigor@sysoev.ru     do {
2580Sigor@sysoev.ru         bucket = nxt_lvlhsh_bucket(lhq->proto, bkt);
2590Sigor@sysoev.ru         n = nxt_lvlhsh_bucket_entries(lhq->proto, bkt);
2600Sigor@sysoev.ru         e = bucket;
2610Sigor@sysoev.ru 
2620Sigor@sysoev.ru         do {
2630Sigor@sysoev.ru             if (nxt_lvlhsh_valid_entry(e)) {
2640Sigor@sysoev.ru                 n--;
2650Sigor@sysoev.ru 
2660Sigor@sysoev.ru                 if (nxt_lvlhsh_entry_key(e) == lhq->key_hash) {
2670Sigor@sysoev.ru 
2680Sigor@sysoev.ru                     value = nxt_lvlhsh_entry_value(e);
2690Sigor@sysoev.ru 
2700Sigor@sysoev.ru                     if (lhq->proto->test(lhq, value) == NXT_OK) {
2710Sigor@sysoev.ru                         lhq->value = value;
2720Sigor@sysoev.ru 
2730Sigor@sysoev.ru                         return NXT_OK;
2740Sigor@sysoev.ru                     }
2750Sigor@sysoev.ru                 }
2760Sigor@sysoev.ru             }
2770Sigor@sysoev.ru 
2780Sigor@sysoev.ru             e += NXT_LVLHSH_ENTRY_SIZE;
2790Sigor@sysoev.ru 
2800Sigor@sysoev.ru         } while (n != 0);
2810Sigor@sysoev.ru 
2820Sigor@sysoev.ru         bkt = *nxt_lvlhsh_next_bucket(lhq->proto, bucket);
2830Sigor@sysoev.ru 
2840Sigor@sysoev.ru     } while (bkt != NULL);
2850Sigor@sysoev.ru 
2860Sigor@sysoev.ru     return NXT_DECLINED;
2870Sigor@sysoev.ru }
2880Sigor@sysoev.ru 
2890Sigor@sysoev.ru 
2900Sigor@sysoev.ru nxt_int_t
2910Sigor@sysoev.ru nxt_lvlhsh_insert(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq)
2920Sigor@sysoev.ru {
2930Sigor@sysoev.ru     uint32_t  key;
2940Sigor@sysoev.ru 
2950Sigor@sysoev.ru     if (nxt_fast_path(lh->slot != NULL)) {
2960Sigor@sysoev.ru 
2970Sigor@sysoev.ru         key = lhq->key_hash;
2980Sigor@sysoev.ru 
2990Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(lh->slot)) {
3000Sigor@sysoev.ru             return nxt_lvlhsh_bucket_insert(lhq, &lh->slot, key, -1);
3010Sigor@sysoev.ru         }
3020Sigor@sysoev.ru 
3030Sigor@sysoev.ru         return nxt_lvlhsh_level_insert(lhq, &lh->slot, key, 0);
3040Sigor@sysoev.ru     }
3050Sigor@sysoev.ru 
3060Sigor@sysoev.ru     return nxt_lvlhsh_new_bucket(lhq, &lh->slot);
3070Sigor@sysoev.ru }
3080Sigor@sysoev.ru 
3090Sigor@sysoev.ru 
3100Sigor@sysoev.ru static nxt_int_t
3110Sigor@sysoev.ru nxt_lvlhsh_new_bucket(nxt_lvlhsh_query_t *lhq, void **slot)
3120Sigor@sysoev.ru {
3130Sigor@sysoev.ru     uint32_t  *bucket;
3140Sigor@sysoev.ru 
31565Sigor@sysoev.ru     bucket = lhq->proto->alloc(lhq->pool, nxt_lvlhsh_bucket_size(lhq->proto));
3160Sigor@sysoev.ru 
3170Sigor@sysoev.ru     if (nxt_fast_path(bucket != NULL)) {
3180Sigor@sysoev.ru 
3190Sigor@sysoev.ru         nxt_lvlhsh_set_entry_value(bucket, lhq->value);
3200Sigor@sysoev.ru         nxt_lvlhsh_set_entry_key(bucket, lhq->key_hash);
3210Sigor@sysoev.ru 
3220Sigor@sysoev.ru         *nxt_lvlhsh_next_bucket(lhq->proto, bucket) = NULL;
3230Sigor@sysoev.ru 
3240Sigor@sysoev.ru         nxt_lvlhsh_store_bucket(*slot, bucket);
3250Sigor@sysoev.ru 
3260Sigor@sysoev.ru         return NXT_OK;
3270Sigor@sysoev.ru     }
3280Sigor@sysoev.ru 
3290Sigor@sysoev.ru     return NXT_ERROR;
3300Sigor@sysoev.ru }
3310Sigor@sysoev.ru 
3320Sigor@sysoev.ru 
3330Sigor@sysoev.ru static nxt_int_t
3340Sigor@sysoev.ru nxt_lvlhsh_level_insert(nxt_lvlhsh_query_t *lhq, void **parent, uint32_t key,
3350Sigor@sysoev.ru     nxt_uint_t nlvl)
3360Sigor@sysoev.ru {
3370Sigor@sysoev.ru     void        **slot, **lvl;
3380Sigor@sysoev.ru     nxt_int_t   ret;
3390Sigor@sysoev.ru     uintptr_t   mask;
3400Sigor@sysoev.ru     nxt_uint_t  shift;
3410Sigor@sysoev.ru 
3420Sigor@sysoev.ru     shift = lhq->proto->shift[nlvl];
3430Sigor@sysoev.ru     mask = ((uintptr_t) 1 << shift) - 1;
3440Sigor@sysoev.ru 
3450Sigor@sysoev.ru     lvl = nxt_lvlhsh_level(*parent, mask);
3460Sigor@sysoev.ru     slot = &lvl[key & mask];
3470Sigor@sysoev.ru 
3480Sigor@sysoev.ru     if (*slot != NULL) {
3490Sigor@sysoev.ru         key >>= shift;
3500Sigor@sysoev.ru 
3510Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(*slot)) {
3520Sigor@sysoev.ru             return nxt_lvlhsh_bucket_insert(lhq, slot, key, nlvl);
3530Sigor@sysoev.ru         }
3540Sigor@sysoev.ru 
3550Sigor@sysoev.ru         return nxt_lvlhsh_level_insert(lhq, slot, key, nlvl + 1);
3560Sigor@sysoev.ru     }
3570Sigor@sysoev.ru 
3580Sigor@sysoev.ru     ret = nxt_lvlhsh_new_bucket(lhq, slot);
3590Sigor@sysoev.ru 
3600Sigor@sysoev.ru     if (nxt_fast_path(ret == NXT_OK)) {
3610Sigor@sysoev.ru         nxt_lvlhsh_count_inc(*parent);
3620Sigor@sysoev.ru     }
3630Sigor@sysoev.ru 
3640Sigor@sysoev.ru     return ret;
3650Sigor@sysoev.ru }
3660Sigor@sysoev.ru 
3670Sigor@sysoev.ru 
3680Sigor@sysoev.ru static nxt_int_t
3690Sigor@sysoev.ru nxt_lvlhsh_bucket_insert(nxt_lvlhsh_query_t *lhq, void **slot, uint32_t key,
3700Sigor@sysoev.ru     nxt_int_t nlvl)
3710Sigor@sysoev.ru {
3720Sigor@sysoev.ru     void                      **bkt, **vacant_bucket, *value;
3730Sigor@sysoev.ru     uint32_t                  *bucket, *e, *vacant_entry;
3740Sigor@sysoev.ru     nxt_int_t                 ret;
3750Sigor@sysoev.ru     uintptr_t                 n;
3760Sigor@sysoev.ru     const void                *new_value;
3770Sigor@sysoev.ru     const nxt_lvlhsh_proto_t  *proto;
3780Sigor@sysoev.ru 
3790Sigor@sysoev.ru     bkt = slot;
3800Sigor@sysoev.ru     vacant_entry = NULL;
3810Sigor@sysoev.ru     vacant_bucket = NULL;
3820Sigor@sysoev.ru     proto = lhq->proto;
3830Sigor@sysoev.ru 
3840Sigor@sysoev.ru     /* Search for duplicate entry in bucket chain. */
3850Sigor@sysoev.ru 
3860Sigor@sysoev.ru     do {
3870Sigor@sysoev.ru         bucket = nxt_lvlhsh_bucket(proto, *bkt);
3880Sigor@sysoev.ru         n = nxt_lvlhsh_bucket_entries(proto, *bkt);
3890Sigor@sysoev.ru         e = bucket;
3900Sigor@sysoev.ru 
3910Sigor@sysoev.ru         do {
3920Sigor@sysoev.ru             if (nxt_lvlhsh_valid_entry(e)) {
3930Sigor@sysoev.ru 
3940Sigor@sysoev.ru                 if (nxt_lvlhsh_entry_key(e) == lhq->key_hash) {
3950Sigor@sysoev.ru 
3960Sigor@sysoev.ru                     value = nxt_lvlhsh_entry_value(e);
3970Sigor@sysoev.ru 
3980Sigor@sysoev.ru                     if (proto->test(lhq, value) == NXT_OK) {
3990Sigor@sysoev.ru 
4000Sigor@sysoev.ru                         new_value = lhq->value;
4010Sigor@sysoev.ru                         lhq->value = value;
4020Sigor@sysoev.ru 
4030Sigor@sysoev.ru                         if (lhq->replace) {
4040Sigor@sysoev.ru                             nxt_lvlhsh_set_entry_value(e, new_value);
4050Sigor@sysoev.ru 
4060Sigor@sysoev.ru                             return NXT_OK;
4070Sigor@sysoev.ru                         }
4080Sigor@sysoev.ru 
4090Sigor@sysoev.ru                         return NXT_DECLINED;
4100Sigor@sysoev.ru                     }
4110Sigor@sysoev.ru                 }
4120Sigor@sysoev.ru 
4130Sigor@sysoev.ru                 n--;
4140Sigor@sysoev.ru 
4150Sigor@sysoev.ru             } else {
4160Sigor@sysoev.ru                 /*
4170Sigor@sysoev.ru                  * Save a hole vacant position in bucket
4180Sigor@sysoev.ru                  * and continue to search for duplicate entry.
4190Sigor@sysoev.ru                  */
4200Sigor@sysoev.ru                 if (vacant_entry == NULL) {
4210Sigor@sysoev.ru                     vacant_entry = e;
4220Sigor@sysoev.ru                     vacant_bucket = bkt;
4230Sigor@sysoev.ru                 }
4240Sigor@sysoev.ru             }
4250Sigor@sysoev.ru 
4260Sigor@sysoev.ru             e += NXT_LVLHSH_ENTRY_SIZE;
4270Sigor@sysoev.ru 
4280Sigor@sysoev.ru         } while (n != 0);
4290Sigor@sysoev.ru 
4300Sigor@sysoev.ru         if (e < nxt_lvlhsh_bucket_end(proto, bucket)) {
4310Sigor@sysoev.ru             /*
4320Sigor@sysoev.ru              * Save a vacant position on incomplete bucket's end
4330Sigor@sysoev.ru              * and continue to search for duplicate entry.
4340Sigor@sysoev.ru              */
4350Sigor@sysoev.ru             if (vacant_entry == NULL) {
4360Sigor@sysoev.ru                 vacant_entry = e;
4370Sigor@sysoev.ru                 vacant_bucket = bkt;
4380Sigor@sysoev.ru             }
4390Sigor@sysoev.ru         }
4400Sigor@sysoev.ru 
4410Sigor@sysoev.ru         bkt = nxt_lvlhsh_next_bucket(proto, bucket);
4420Sigor@sysoev.ru 
4430Sigor@sysoev.ru     } while (*bkt != NULL);
4440Sigor@sysoev.ru 
4450Sigor@sysoev.ru     if (vacant_entry != NULL) {
4460Sigor@sysoev.ru         nxt_lvlhsh_set_entry_value(vacant_entry, lhq->value);
4470Sigor@sysoev.ru         nxt_lvlhsh_set_entry_key(vacant_entry, lhq->key_hash);
4480Sigor@sysoev.ru         nxt_lvlhsh_count_inc(*vacant_bucket);
4490Sigor@sysoev.ru 
4500Sigor@sysoev.ru         return NXT_OK;
4510Sigor@sysoev.ru     }
4520Sigor@sysoev.ru 
4530Sigor@sysoev.ru     /* All buckets are full. */
4540Sigor@sysoev.ru 
4550Sigor@sysoev.ru     nlvl++;
4560Sigor@sysoev.ru 
4570Sigor@sysoev.ru     if (nxt_fast_path(proto->shift[nlvl] != 0)) {
4580Sigor@sysoev.ru 
4590Sigor@sysoev.ru         ret = nxt_lvlhsh_convert_bucket_to_level(lhq, slot, nlvl, bucket);
4600Sigor@sysoev.ru 
4610Sigor@sysoev.ru         if (nxt_fast_path(ret == NXT_OK)) {
4620Sigor@sysoev.ru             return nxt_lvlhsh_level_insert(lhq, slot, key, nlvl);
4630Sigor@sysoev.ru         }
4640Sigor@sysoev.ru 
4650Sigor@sysoev.ru         return ret;
4660Sigor@sysoev.ru     }
4670Sigor@sysoev.ru 
4680Sigor@sysoev.ru     /* The last allowed level, only buckets may be allocated here. */
4690Sigor@sysoev.ru 
4700Sigor@sysoev.ru     return nxt_lvlhsh_new_bucket(lhq, bkt);
4710Sigor@sysoev.ru }
4720Sigor@sysoev.ru 
4730Sigor@sysoev.ru 
4740Sigor@sysoev.ru static nxt_int_t
4750Sigor@sysoev.ru nxt_lvlhsh_convert_bucket_to_level(nxt_lvlhsh_query_t *lhq, void **slot,
4760Sigor@sysoev.ru     nxt_uint_t nlvl, uint32_t *bucket)
4770Sigor@sysoev.ru {
4780Sigor@sysoev.ru     void                      *lvl, **level;
4790Sigor@sysoev.ru     uint32_t                  *e, *end, key;
4800Sigor@sysoev.ru     nxt_int_t                 ret;
4810Sigor@sysoev.ru     nxt_uint_t                i, shift, size;
4820Sigor@sysoev.ru     nxt_lvlhsh_query_t        q;
4830Sigor@sysoev.ru     const nxt_lvlhsh_proto_t  *proto;
4840Sigor@sysoev.ru 
4850Sigor@sysoev.ru     proto = lhq->proto;
4860Sigor@sysoev.ru     size = nxt_lvlhsh_level_size(proto, nlvl);
4870Sigor@sysoev.ru 
48865Sigor@sysoev.ru     lvl = proto->alloc(lhq->pool, size * (sizeof(void *)));
4890Sigor@sysoev.ru 
4900Sigor@sysoev.ru     if (nxt_slow_path(lvl == NULL)) {
4910Sigor@sysoev.ru         return NXT_ERROR;
4920Sigor@sysoev.ru     }
4930Sigor@sysoev.ru 
4940Sigor@sysoev.ru     nxt_memzero(lvl, size * (sizeof(void *)));
4950Sigor@sysoev.ru 
4960Sigor@sysoev.ru     level = lvl;
4970Sigor@sysoev.ru     shift = 0;
4980Sigor@sysoev.ru 
4990Sigor@sysoev.ru     for (i = 0; i < nlvl; i++) {
5000Sigor@sysoev.ru         /*
5010Sigor@sysoev.ru          * Using SIMD operations in this trivial loop with maximum
5020Sigor@sysoev.ru          * 8 iterations may increase code size by 170 bytes.
5030Sigor@sysoev.ru          */
5040Sigor@sysoev.ru         nxt_pragma_loop_disable_vectorization;
5050Sigor@sysoev.ru 
5060Sigor@sysoev.ru         shift += proto->shift[i];
5070Sigor@sysoev.ru     }
5080Sigor@sysoev.ru 
5090Sigor@sysoev.ru     end = nxt_lvlhsh_bucket_end(proto, bucket);
5100Sigor@sysoev.ru 
5110Sigor@sysoev.ru     for (e = bucket; e < end; e += NXT_LVLHSH_ENTRY_SIZE) {
5120Sigor@sysoev.ru 
5130Sigor@sysoev.ru         q.proto = proto;
5140Sigor@sysoev.ru         q.pool = lhq->pool;
5150Sigor@sysoev.ru         q.value = nxt_lvlhsh_entry_value(e);
5160Sigor@sysoev.ru         key = nxt_lvlhsh_entry_key(e);
5170Sigor@sysoev.ru         q.key_hash = key;
5180Sigor@sysoev.ru 
5190Sigor@sysoev.ru         ret = nxt_lvlhsh_level_convertion_insert(&q, &lvl, key >> shift, nlvl);
5200Sigor@sysoev.ru 
5210Sigor@sysoev.ru         if (nxt_slow_path(ret != NXT_OK)) {
5220Sigor@sysoev.ru             return nxt_lvlhsh_free_level(lhq, level, size);
5230Sigor@sysoev.ru         }
5240Sigor@sysoev.ru     }
5250Sigor@sysoev.ru 
5260Sigor@sysoev.ru     *slot = lvl;
5270Sigor@sysoev.ru 
52865Sigor@sysoev.ru     proto->free(lhq->pool, bucket);
5290Sigor@sysoev.ru 
5300Sigor@sysoev.ru     return NXT_OK;
5310Sigor@sysoev.ru }
5320Sigor@sysoev.ru 
5330Sigor@sysoev.ru 
5340Sigor@sysoev.ru static nxt_int_t
5350Sigor@sysoev.ru nxt_lvlhsh_level_convertion_insert(nxt_lvlhsh_query_t *lhq, void **parent,
5360Sigor@sysoev.ru     uint32_t key, nxt_uint_t nlvl)
5370Sigor@sysoev.ru {
5380Sigor@sysoev.ru     void        **slot, **lvl;
5390Sigor@sysoev.ru     nxt_int_t   ret;
5400Sigor@sysoev.ru     uintptr_t   mask;
5410Sigor@sysoev.ru     nxt_uint_t  shift;
5420Sigor@sysoev.ru 
5430Sigor@sysoev.ru     shift = lhq->proto->shift[nlvl];
5440Sigor@sysoev.ru     mask = ((uintptr_t) 1 << shift) - 1;
5450Sigor@sysoev.ru 
5460Sigor@sysoev.ru     lvl = nxt_lvlhsh_level(*parent, mask);
5470Sigor@sysoev.ru     slot = &lvl[key & mask];
5480Sigor@sysoev.ru 
5490Sigor@sysoev.ru     if (*slot == NULL) {
5500Sigor@sysoev.ru         ret = nxt_lvlhsh_new_bucket(lhq, slot);
5510Sigor@sysoev.ru 
5520Sigor@sysoev.ru         if (nxt_fast_path(ret == NXT_OK)) {
5530Sigor@sysoev.ru             nxt_lvlhsh_count_inc(*parent);
5540Sigor@sysoev.ru         }
5550Sigor@sysoev.ru 
5560Sigor@sysoev.ru         return ret;
5570Sigor@sysoev.ru     }
5580Sigor@sysoev.ru 
5590Sigor@sysoev.ru     /* Only backets can be here. */
5600Sigor@sysoev.ru 
5610Sigor@sysoev.ru     return nxt_lvlhsh_bucket_convertion_insert(lhq, slot, key >> shift, nlvl);
5620Sigor@sysoev.ru }
5630Sigor@sysoev.ru 
5640Sigor@sysoev.ru 
5650Sigor@sysoev.ru /*
5660Sigor@sysoev.ru  * The special bucket insertion procedure is required because during
5670Sigor@sysoev.ru  * convertion lhq->key contains garbage values and the test function
5680Sigor@sysoev.ru  * cannot be called.  Besides, the procedure can be simpler because
5690Sigor@sysoev.ru  * a new entry is inserted just after occupied entries.
5700Sigor@sysoev.ru  */
5710Sigor@sysoev.ru 
5720Sigor@sysoev.ru static nxt_int_t
5730Sigor@sysoev.ru nxt_lvlhsh_bucket_convertion_insert(nxt_lvlhsh_query_t *lhq, void **slot,
5740Sigor@sysoev.ru     uint32_t key, nxt_int_t nlvl)
5750Sigor@sysoev.ru {
5760Sigor@sysoev.ru     void                      **bkt;
5770Sigor@sysoev.ru     uint32_t                  *bucket, *e;
5780Sigor@sysoev.ru     nxt_int_t                 ret;
5790Sigor@sysoev.ru     uintptr_t                 n;
5800Sigor@sysoev.ru     const nxt_lvlhsh_proto_t  *proto;
5810Sigor@sysoev.ru 
5820Sigor@sysoev.ru     bkt = slot;
5830Sigor@sysoev.ru     proto = lhq->proto;
5840Sigor@sysoev.ru 
5850Sigor@sysoev.ru     do {
5860Sigor@sysoev.ru         bucket = nxt_lvlhsh_bucket(proto, *bkt);
5870Sigor@sysoev.ru         n = nxt_lvlhsh_bucket_entries(proto, *bkt);
5880Sigor@sysoev.ru         e = bucket + n * NXT_LVLHSH_ENTRY_SIZE;
5890Sigor@sysoev.ru 
5900Sigor@sysoev.ru         if (nxt_fast_path(e < nxt_lvlhsh_bucket_end(proto, bucket))) {
5910Sigor@sysoev.ru 
5920Sigor@sysoev.ru             nxt_lvlhsh_set_entry_value(e, lhq->value);
5930Sigor@sysoev.ru             nxt_lvlhsh_set_entry_key(e, lhq->key_hash);
5940Sigor@sysoev.ru             nxt_lvlhsh_count_inc(*bkt);
5950Sigor@sysoev.ru 
5960Sigor@sysoev.ru             return NXT_OK;
5970Sigor@sysoev.ru         }
5980Sigor@sysoev.ru 
5990Sigor@sysoev.ru         bkt = nxt_lvlhsh_next_bucket(proto, bucket);
6000Sigor@sysoev.ru 
6010Sigor@sysoev.ru     } while (*bkt != NULL);
6020Sigor@sysoev.ru 
6030Sigor@sysoev.ru     /* All buckets are full. */
6040Sigor@sysoev.ru 
6050Sigor@sysoev.ru     nlvl++;
6060Sigor@sysoev.ru 
6070Sigor@sysoev.ru     if (nxt_fast_path(proto->shift[nlvl] != 0)) {
6080Sigor@sysoev.ru 
6090Sigor@sysoev.ru         ret = nxt_lvlhsh_convert_bucket_to_level(lhq, slot, nlvl, bucket);
6100Sigor@sysoev.ru 
6110Sigor@sysoev.ru         if (nxt_fast_path(ret == NXT_OK)) {
6120Sigor@sysoev.ru             return nxt_lvlhsh_level_insert(lhq, slot, key, nlvl);
6130Sigor@sysoev.ru         }
6140Sigor@sysoev.ru 
6150Sigor@sysoev.ru         return ret;
6160Sigor@sysoev.ru     }
6170Sigor@sysoev.ru 
6180Sigor@sysoev.ru     /* The last allowed level, only buckets may be allocated here. */
6190Sigor@sysoev.ru 
6200Sigor@sysoev.ru     return nxt_lvlhsh_new_bucket(lhq, bkt);
6210Sigor@sysoev.ru }
6220Sigor@sysoev.ru 
6230Sigor@sysoev.ru 
6240Sigor@sysoev.ru static nxt_int_t
6250Sigor@sysoev.ru nxt_lvlhsh_free_level(nxt_lvlhsh_query_t *lhq, void **level, nxt_uint_t size)
6260Sigor@sysoev.ru {
6270Sigor@sysoev.ru     nxt_uint_t                i;
6280Sigor@sysoev.ru     const nxt_lvlhsh_proto_t  *proto;
6290Sigor@sysoev.ru 
6300Sigor@sysoev.ru     proto = lhq->proto;
6310Sigor@sysoev.ru 
6320Sigor@sysoev.ru     for (i = 0; i < size; i++) {
6330Sigor@sysoev.ru 
6340Sigor@sysoev.ru         if (level[i] != NULL) {
6350Sigor@sysoev.ru             /*
6360Sigor@sysoev.ru              * Chained buckets are not possible here, since even
6370Sigor@sysoev.ru              * in the worst case one bucket cannot be converted
6380Sigor@sysoev.ru              * in two chained buckets but remains the same bucket.
6390Sigor@sysoev.ru              */
64065Sigor@sysoev.ru             proto->free(lhq->pool, nxt_lvlhsh_bucket(proto, level[i]));
6410Sigor@sysoev.ru         }
6420Sigor@sysoev.ru     }
6430Sigor@sysoev.ru 
64465Sigor@sysoev.ru     proto->free(lhq->pool, level);
6450Sigor@sysoev.ru 
6460Sigor@sysoev.ru     return NXT_ERROR;
6470Sigor@sysoev.ru }
6480Sigor@sysoev.ru 
6490Sigor@sysoev.ru 
6500Sigor@sysoev.ru nxt_int_t
6510Sigor@sysoev.ru nxt_lvlhsh_delete(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq)
6520Sigor@sysoev.ru {
6530Sigor@sysoev.ru     if (nxt_fast_path(lh->slot != NULL)) {
6540Sigor@sysoev.ru 
6550Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(lh->slot)) {
6560Sigor@sysoev.ru             return nxt_lvlhsh_bucket_delete(lhq, &lh->slot);
6570Sigor@sysoev.ru         }
6580Sigor@sysoev.ru 
6590Sigor@sysoev.ru         return nxt_lvlhsh_level_delete(lhq, &lh->slot, lhq->key_hash, 0);
6600Sigor@sysoev.ru     }
6610Sigor@sysoev.ru 
6620Sigor@sysoev.ru     return NXT_DECLINED;
6630Sigor@sysoev.ru }
6640Sigor@sysoev.ru 
6650Sigor@sysoev.ru 
6660Sigor@sysoev.ru static nxt_int_t
6670Sigor@sysoev.ru nxt_lvlhsh_level_delete(nxt_lvlhsh_query_t *lhq, void **parent, uint32_t key,
6680Sigor@sysoev.ru     nxt_uint_t nlvl)
6690Sigor@sysoev.ru {
6700Sigor@sysoev.ru     void        **slot, **lvl;
6710Sigor@sysoev.ru     uintptr_t   mask;
6720Sigor@sysoev.ru     nxt_int_t   ret;
6730Sigor@sysoev.ru     nxt_uint_t  shift;
6740Sigor@sysoev.ru 
6750Sigor@sysoev.ru     shift = lhq->proto->shift[nlvl];
6760Sigor@sysoev.ru     mask = ((uintptr_t) 1 << shift) - 1;
6770Sigor@sysoev.ru 
6780Sigor@sysoev.ru     lvl = nxt_lvlhsh_level(*parent, mask);
6790Sigor@sysoev.ru     slot = &lvl[key & mask];
6800Sigor@sysoev.ru 
6810Sigor@sysoev.ru     if (*slot != NULL) {
6820Sigor@sysoev.ru 
6830Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(*slot)) {
6840Sigor@sysoev.ru             ret = nxt_lvlhsh_bucket_delete(lhq, slot);
6850Sigor@sysoev.ru 
6860Sigor@sysoev.ru         } else {
6870Sigor@sysoev.ru             key >>= shift;
6880Sigor@sysoev.ru             ret = nxt_lvlhsh_level_delete(lhq, slot, key, nlvl + 1);
6890Sigor@sysoev.ru         }
6900Sigor@sysoev.ru 
6910Sigor@sysoev.ru         if (*slot == NULL) {
6920Sigor@sysoev.ru             nxt_lvlhsh_count_dec(*parent);
6930Sigor@sysoev.ru 
6940Sigor@sysoev.ru             if (nxt_lvlhsh_level_entries(*parent, mask) == 0) {
6950Sigor@sysoev.ru                 *parent = NULL;
69665Sigor@sysoev.ru                 lhq->proto->free(lhq->pool, lvl);
6970Sigor@sysoev.ru             }
6980Sigor@sysoev.ru         }
6990Sigor@sysoev.ru 
7000Sigor@sysoev.ru         return ret;
7010Sigor@sysoev.ru     }
7020Sigor@sysoev.ru 
7030Sigor@sysoev.ru     return NXT_DECLINED;
7040Sigor@sysoev.ru }
7050Sigor@sysoev.ru 
7060Sigor@sysoev.ru 
7070Sigor@sysoev.ru static nxt_int_t
7080Sigor@sysoev.ru nxt_lvlhsh_bucket_delete(nxt_lvlhsh_query_t *lhq, void **bkt)
7090Sigor@sysoev.ru {
7100Sigor@sysoev.ru     void                      *value;
7110Sigor@sysoev.ru     uint32_t                  *bucket, *e;
7120Sigor@sysoev.ru     uintptr_t                 n;
7130Sigor@sysoev.ru     const nxt_lvlhsh_proto_t  *proto;
7140Sigor@sysoev.ru 
7150Sigor@sysoev.ru     proto = lhq->proto;
7160Sigor@sysoev.ru 
7170Sigor@sysoev.ru     do {
7180Sigor@sysoev.ru         bucket = nxt_lvlhsh_bucket(proto, *bkt);
7190Sigor@sysoev.ru         n = nxt_lvlhsh_bucket_entries(proto, *bkt);
7200Sigor@sysoev.ru         e = bucket;
7210Sigor@sysoev.ru 
7220Sigor@sysoev.ru         do {
7230Sigor@sysoev.ru             if (nxt_lvlhsh_valid_entry(e)) {
7240Sigor@sysoev.ru 
7250Sigor@sysoev.ru                 if (nxt_lvlhsh_entry_key(e) == lhq->key_hash) {
7260Sigor@sysoev.ru 
7270Sigor@sysoev.ru                     value = nxt_lvlhsh_entry_value(e);
7280Sigor@sysoev.ru 
7290Sigor@sysoev.ru                     if (proto->test(lhq, value) == NXT_OK) {
7300Sigor@sysoev.ru 
7310Sigor@sysoev.ru                         if (nxt_lvlhsh_bucket_entries(proto, *bkt) == 1) {
7320Sigor@sysoev.ru                             *bkt = *nxt_lvlhsh_next_bucket(proto, bucket);
73365Sigor@sysoev.ru                             proto->free(lhq->pool, bucket);
7340Sigor@sysoev.ru 
7350Sigor@sysoev.ru                         } else {
7360Sigor@sysoev.ru                             nxt_lvlhsh_count_dec(*bkt);
7370Sigor@sysoev.ru                             nxt_lvlhsh_set_entry_value(e, NULL);
7380Sigor@sysoev.ru                         }
7390Sigor@sysoev.ru 
7400Sigor@sysoev.ru                         lhq->value = value;
7410Sigor@sysoev.ru 
7420Sigor@sysoev.ru                         return NXT_OK;
7430Sigor@sysoev.ru                     }
7440Sigor@sysoev.ru                 }
7450Sigor@sysoev.ru 
7460Sigor@sysoev.ru                 n--;
7470Sigor@sysoev.ru             }
7480Sigor@sysoev.ru 
7490Sigor@sysoev.ru             e += NXT_LVLHSH_ENTRY_SIZE;
7500Sigor@sysoev.ru 
7510Sigor@sysoev.ru         } while (n != 0);
7520Sigor@sysoev.ru 
7530Sigor@sysoev.ru         bkt = nxt_lvlhsh_next_bucket(proto, bucket);
7540Sigor@sysoev.ru 
7550Sigor@sysoev.ru     } while (*bkt != NULL);
7560Sigor@sysoev.ru 
7570Sigor@sysoev.ru     return NXT_DECLINED;
7580Sigor@sysoev.ru }
7590Sigor@sysoev.ru 
7600Sigor@sysoev.ru 
7610Sigor@sysoev.ru void *
7620Sigor@sysoev.ru nxt_lvlhsh_each(nxt_lvlhsh_t *lh, nxt_lvlhsh_each_t *lhe)
7630Sigor@sysoev.ru {
7640Sigor@sysoev.ru     void  **slot;
7650Sigor@sysoev.ru 
7660Sigor@sysoev.ru     if (lhe->bucket == NXT_LVLHSH_BUCKET_DONE) {
7670Sigor@sysoev.ru         slot = lh->slot;
7680Sigor@sysoev.ru 
7690Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(slot)) {
7700Sigor@sysoev.ru             return NULL;
7710Sigor@sysoev.ru         }
7720Sigor@sysoev.ru 
7730Sigor@sysoev.ru     } else {
7740Sigor@sysoev.ru         if (nxt_slow_path(lhe->bucket == NULL)) {
7750Sigor@sysoev.ru 
7760Sigor@sysoev.ru             /* The first iteration only. */
7770Sigor@sysoev.ru 
7780Sigor@sysoev.ru             slot = lh->slot;
7790Sigor@sysoev.ru 
7800Sigor@sysoev.ru             if (slot == NULL) {
7810Sigor@sysoev.ru                 return NULL;
7820Sigor@sysoev.ru             }
7830Sigor@sysoev.ru 
7840Sigor@sysoev.ru             if (!nxt_lvlhsh_is_bucket(slot)) {
785*598Sigor@sysoev.ru                 lhe->current = 0;
7860Sigor@sysoev.ru                 goto level;
7870Sigor@sysoev.ru             }
7880Sigor@sysoev.ru 
7890Sigor@sysoev.ru             lhe->bucket = nxt_lvlhsh_bucket(lhe->proto, slot);
7900Sigor@sysoev.ru             lhe->entries = nxt_lvlhsh_bucket_entries(lhe->proto, slot);
791*598Sigor@sysoev.ru             lhe->entry = 0;
7920Sigor@sysoev.ru         }
7930Sigor@sysoev.ru 
7940Sigor@sysoev.ru         return nxt_lvlhsh_bucket_each(lhe);
7950Sigor@sysoev.ru     }
7960Sigor@sysoev.ru 
7970Sigor@sysoev.ru level:
7980Sigor@sysoev.ru 
7990Sigor@sysoev.ru     return nxt_lvlhsh_level_each(lhe, slot, 0, 0);
8000Sigor@sysoev.ru }
8010Sigor@sysoev.ru 
8020Sigor@sysoev.ru 
8030Sigor@sysoev.ru static void *
8040Sigor@sysoev.ru nxt_lvlhsh_level_each(nxt_lvlhsh_each_t *lhe, void **level, nxt_uint_t nlvl,
8050Sigor@sysoev.ru     nxt_uint_t shift)
8060Sigor@sysoev.ru {
8070Sigor@sysoev.ru     void        **slot, *value;
8080Sigor@sysoev.ru     uintptr_t   mask;
8090Sigor@sysoev.ru     nxt_uint_t  n, level_shift;
8100Sigor@sysoev.ru 
8110Sigor@sysoev.ru     level_shift = lhe->proto->shift[nlvl];
8120Sigor@sysoev.ru     mask = ((uintptr_t) 1 << level_shift) - 1;
8130Sigor@sysoev.ru 
8140Sigor@sysoev.ru     level = nxt_lvlhsh_level(level, mask);
8150Sigor@sysoev.ru 
8160Sigor@sysoev.ru     do {
8170Sigor@sysoev.ru         n = (lhe->current >> shift) & mask;
8180Sigor@sysoev.ru         slot = level[n];
8190Sigor@sysoev.ru 
8200Sigor@sysoev.ru         if (slot != NULL) {
8210Sigor@sysoev.ru             if (nxt_lvlhsh_is_bucket(slot)) {
8220Sigor@sysoev.ru 
8230Sigor@sysoev.ru                 if (lhe->bucket != NXT_LVLHSH_BUCKET_DONE) {
8240Sigor@sysoev.ru 
8250Sigor@sysoev.ru                     lhe->bucket = nxt_lvlhsh_bucket(lhe->proto, slot);
8260Sigor@sysoev.ru                     lhe->entries = nxt_lvlhsh_bucket_entries(lhe->proto, slot);
8270Sigor@sysoev.ru                     lhe->entry = 0;
8280Sigor@sysoev.ru 
8290Sigor@sysoev.ru                     return nxt_lvlhsh_bucket_each(lhe);
8300Sigor@sysoev.ru                 }
8310Sigor@sysoev.ru 
8320Sigor@sysoev.ru                 lhe->bucket = NULL;
8330Sigor@sysoev.ru 
8340Sigor@sysoev.ru             } else {
8350Sigor@sysoev.ru                 value = nxt_lvlhsh_level_each(lhe, slot, nlvl + 1,
8360Sigor@sysoev.ru                                               shift + level_shift);
8370Sigor@sysoev.ru                 if (value != NULL) {
8380Sigor@sysoev.ru                     return value;
8390Sigor@sysoev.ru                 }
8400Sigor@sysoev.ru             }
8410Sigor@sysoev.ru         }
8420Sigor@sysoev.ru 
8430Sigor@sysoev.ru         lhe->current &= ~(mask << shift);
8440Sigor@sysoev.ru         n = ((n + 1) & mask) << shift;
8450Sigor@sysoev.ru         lhe->current |= n;
8460Sigor@sysoev.ru 
8470Sigor@sysoev.ru     } while (n != 0);
8480Sigor@sysoev.ru 
8490Sigor@sysoev.ru     return NULL;
8500Sigor@sysoev.ru }
8510Sigor@sysoev.ru 
8520Sigor@sysoev.ru 
8530Sigor@sysoev.ru static nxt_noinline void *
8540Sigor@sysoev.ru nxt_lvlhsh_bucket_each(nxt_lvlhsh_each_t *lhe)
8550Sigor@sysoev.ru {
8560Sigor@sysoev.ru     void      *value, **next;
8570Sigor@sysoev.ru     uint32_t  *bucket;
8580Sigor@sysoev.ru 
8590Sigor@sysoev.ru     /* At least one valid entry must present here. */
8600Sigor@sysoev.ru     do {
8610Sigor@sysoev.ru         bucket = &lhe->bucket[lhe->entry];
8620Sigor@sysoev.ru         lhe->entry += NXT_LVLHSH_ENTRY_SIZE;
8630Sigor@sysoev.ru 
8640Sigor@sysoev.ru     } while (nxt_lvlhsh_free_entry(bucket));
8650Sigor@sysoev.ru 
8660Sigor@sysoev.ru     value = nxt_lvlhsh_entry_value(bucket);
8670Sigor@sysoev.ru 
8680Sigor@sysoev.ru     lhe->entries--;
8690Sigor@sysoev.ru 
8700Sigor@sysoev.ru     if (lhe->entries == 0) {
8710Sigor@sysoev.ru         next = *nxt_lvlhsh_next_bucket(lhe->proto, lhe->bucket);
8720Sigor@sysoev.ru 
87372Sigor@sysoev.ru         lhe->bucket = (next == NULL) ? NXT_LVLHSH_BUCKET_DONE
87472Sigor@sysoev.ru                                      : nxt_lvlhsh_bucket(lhe->proto, next);
8750Sigor@sysoev.ru 
8760Sigor@sysoev.ru         lhe->entries = nxt_lvlhsh_bucket_entries(lhe->proto, next);
8770Sigor@sysoev.ru         lhe->entry = 0;
8780Sigor@sysoev.ru     }
8790Sigor@sysoev.ru 
8800Sigor@sysoev.ru     return value;
8810Sigor@sysoev.ru }
8820Sigor@sysoev.ru 
8830Sigor@sysoev.ru 
8840Sigor@sysoev.ru void *
885594Sigor@sysoev.ru nxt_lvlhsh_peek(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto)
886594Sigor@sysoev.ru {
887595Sigor@sysoev.ru     void               **slot;
888595Sigor@sysoev.ru     nxt_lvlhsh_peek_t  peek;
889594Sigor@sysoev.ru 
890594Sigor@sysoev.ru     slot = lh->slot;
891594Sigor@sysoev.ru 
892594Sigor@sysoev.ru     if (slot != NULL) {
893594Sigor@sysoev.ru 
894595Sigor@sysoev.ru         peek.proto = proto;
895595Sigor@sysoev.ru         peek.retrieve = 0;
896595Sigor@sysoev.ru 
897594Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(slot)) {
898595Sigor@sysoev.ru             return nxt_lvlhsh_bucket_peek(&peek, &lh->slot);
899594Sigor@sysoev.ru         }
900594Sigor@sysoev.ru 
901595Sigor@sysoev.ru         return nxt_lvlhsh_level_peek(&peek, &lh->slot, 0);
902594Sigor@sysoev.ru     }
903594Sigor@sysoev.ru 
904594Sigor@sysoev.ru     return NULL;
905594Sigor@sysoev.ru }
906594Sigor@sysoev.ru 
907594Sigor@sysoev.ru 
908594Sigor@sysoev.ru static void *
909595Sigor@sysoev.ru nxt_lvlhsh_level_peek(nxt_lvlhsh_peek_t *peek, void **parent, nxt_uint_t nlvl)
910594Sigor@sysoev.ru {
911595Sigor@sysoev.ru     void        **slot, **level, *value;
912594Sigor@sysoev.ru     uintptr_t   mask;
913594Sigor@sysoev.ru     nxt_uint_t  n, shift;
914594Sigor@sysoev.ru 
915595Sigor@sysoev.ru     shift = peek->proto->shift[nlvl];
916594Sigor@sysoev.ru     mask = ((uintptr_t) 1 << shift) - 1;
917594Sigor@sysoev.ru 
918595Sigor@sysoev.ru     level = nxt_lvlhsh_level(*parent, mask);
919594Sigor@sysoev.ru 
920594Sigor@sysoev.ru     n = 0;
921594Sigor@sysoev.ru 
922594Sigor@sysoev.ru     /* At least one valid level slot must present here. */
923594Sigor@sysoev.ru 
924594Sigor@sysoev.ru     for ( ;; ) {
925595Sigor@sysoev.ru         slot = &level[n];
926595Sigor@sysoev.ru 
927595Sigor@sysoev.ru         if (*slot != NULL) {
928594Sigor@sysoev.ru 
929595Sigor@sysoev.ru             if (nxt_lvlhsh_is_bucket(*slot)) {
930595Sigor@sysoev.ru                 value = nxt_lvlhsh_bucket_peek(peek, slot);
931594Sigor@sysoev.ru 
932595Sigor@sysoev.ru             } else {
933595Sigor@sysoev.ru                 value = nxt_lvlhsh_level_peek(peek, slot, nlvl + 1);
934594Sigor@sysoev.ru             }
935594Sigor@sysoev.ru 
936595Sigor@sysoev.ru             /*
937595Sigor@sysoev.ru              * Checking peek->retrieve is not required here because
938595Sigor@sysoev.ru              * there can not be empty slots during peeking.
939595Sigor@sysoev.ru              */
940595Sigor@sysoev.ru             if (*slot == NULL) {
941595Sigor@sysoev.ru                 nxt_lvlhsh_count_dec(*parent);
942595Sigor@sysoev.ru 
943595Sigor@sysoev.ru                 if (nxt_lvlhsh_level_entries(*parent, mask) == 0) {
944595Sigor@sysoev.ru                     *parent = NULL;
945595Sigor@sysoev.ru                     peek->proto->free(peek->pool, level);
946595Sigor@sysoev.ru                 }
947595Sigor@sysoev.ru             }
948595Sigor@sysoev.ru 
949595Sigor@sysoev.ru             return value;
950594Sigor@sysoev.ru         }
951594Sigor@sysoev.ru 
952594Sigor@sysoev.ru         n++;
953594Sigor@sysoev.ru     }
954594Sigor@sysoev.ru }
955594Sigor@sysoev.ru 
956594Sigor@sysoev.ru 
957595Sigor@sysoev.ru static nxt_noinline void *
958595Sigor@sysoev.ru nxt_lvlhsh_bucket_peek(nxt_lvlhsh_peek_t *peek, void **bkt)
959594Sigor@sysoev.ru {
960595Sigor@sysoev.ru     void                      *value;
961595Sigor@sysoev.ru     uint32_t                  *bucket, *entry;
962595Sigor@sysoev.ru     const nxt_lvlhsh_proto_t  *proto;
963595Sigor@sysoev.ru 
964595Sigor@sysoev.ru     bucket = nxt_lvlhsh_bucket(peek->proto, *bkt);
965594Sigor@sysoev.ru 
966594Sigor@sysoev.ru     /* At least one valid entry must present here. */
967594Sigor@sysoev.ru 
968595Sigor@sysoev.ru     for (entry = bucket;
969594Sigor@sysoev.ru          nxt_lvlhsh_free_entry(entry);
970594Sigor@sysoev.ru          entry += NXT_LVLHSH_ENTRY_SIZE)
971594Sigor@sysoev.ru     {
972594Sigor@sysoev.ru         /* void */
973594Sigor@sysoev.ru     }
974594Sigor@sysoev.ru 
975594Sigor@sysoev.ru     value = nxt_lvlhsh_entry_value(entry);
976595Sigor@sysoev.ru 
977595Sigor@sysoev.ru     if (peek->retrieve) {
978595Sigor@sysoev.ru         proto = peek->proto;
979595Sigor@sysoev.ru 
980595Sigor@sysoev.ru         if (nxt_lvlhsh_bucket_entries(proto, *bkt) == 1) {
981595Sigor@sysoev.ru             *bkt = *nxt_lvlhsh_next_bucket(proto, bucket);
982595Sigor@sysoev.ru             proto->free(peek->pool, bucket);
983595Sigor@sysoev.ru 
984595Sigor@sysoev.ru         } else {
985595Sigor@sysoev.ru             nxt_lvlhsh_count_dec(*bkt);
986595Sigor@sysoev.ru             nxt_lvlhsh_set_entry_value(entry, NULL);
987595Sigor@sysoev.ru         }
988595Sigor@sysoev.ru     }
989595Sigor@sysoev.ru 
990594Sigor@sysoev.ru     return value;
991594Sigor@sysoev.ru }
992594Sigor@sysoev.ru 
993594Sigor@sysoev.ru 
994594Sigor@sysoev.ru void *
995595Sigor@sysoev.ru nxt_lvlhsh_retrieve(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
996595Sigor@sysoev.ru     void *pool)
997595Sigor@sysoev.ru {
998595Sigor@sysoev.ru     void               **slot;
999595Sigor@sysoev.ru     nxt_lvlhsh_peek_t  peek;
1000595Sigor@sysoev.ru 
1001595Sigor@sysoev.ru     slot = lh->slot;
1002595Sigor@sysoev.ru 
1003595Sigor@sysoev.ru     if (slot != NULL) {
1004595Sigor@sysoev.ru 
1005595Sigor@sysoev.ru         peek.proto = proto;
1006595Sigor@sysoev.ru         peek.pool = pool;
1007595Sigor@sysoev.ru         peek.retrieve = 1;
1008595Sigor@sysoev.ru 
1009595Sigor@sysoev.ru         if (nxt_lvlhsh_is_bucket(slot)) {
1010595Sigor@sysoev.ru             return nxt_lvlhsh_bucket_peek(&peek, &lh->slot);
1011595Sigor@sysoev.ru         }
1012595Sigor@sysoev.ru 
1013595Sigor@sysoev.ru         return nxt_lvlhsh_level_peek(&peek, &lh->slot, 0);
1014595Sigor@sysoev.ru     }
1015595Sigor@sysoev.ru 
1016595Sigor@sysoev.ru     return NULL;
1017595Sigor@sysoev.ru }
1018595Sigor@sysoev.ru 
1019595Sigor@sysoev.ru 
1020595Sigor@sysoev.ru void *
102165Sigor@sysoev.ru nxt_lvlhsh_alloc(void *data, size_t size)
10220Sigor@sysoev.ru {
10230Sigor@sysoev.ru     return nxt_memalign(size, size);
10240Sigor@sysoev.ru }
10250Sigor@sysoev.ru 
10260Sigor@sysoev.ru 
10270Sigor@sysoev.ru void
102865Sigor@sysoev.ru nxt_lvlhsh_free(void *data, void *p)
10290Sigor@sysoev.ru {
10300Sigor@sysoev.ru     nxt_free(p);
10310Sigor@sysoev.ru }
1032