Removed remnants of level hash.HEADmaster

Level hash has not been compiled since e64a376 (0.8.1) when flat hash was
introduced. However, the compatibility layer remained to reduce the diff.

1 files changed, 0 insertions, 854 deletions

diff --git a/src/njs_lvlhsh.c b/src/njs_lvlhsh.c
deleted file mode 100644
index 8443a08c..00000000
--- a/src/njs_lvlhsh.c
+++ /dev/null
@@ -1,854 +0,0 @@
-
-/*
- * Copyright (C) Igor Sysoev
- * Copyright (C) NGINX, Inc.
- */
-
-
-#include <njs_main.h>
-
-
-/*
- * The level hash consists of hierarchical levels of arrays of pointers.
- * The pointers may point to another level, a bucket, or NULL.
- * The levels and buckets must be allocated in manner alike posix_memalign()
- * to bookkeep additional information in pointer low bits.
- *
- * A level is an array of pointers.  Its size is a power of 2.  Levels
- * may be different sizes, but on the same level the sizes are the same.
- * Level sizes are specified by number of bits per level in lvlhsh->shift
- * array.  A hash may have up to 7 levels.  There are two predefined
- * shift arrays given by the first two shift array values:
- *
- * 1) [0, 0]:  [4, 4, 4, 4, 4, 4, 4] on a 64-bit platform or
- *             [5, 5, 5, 5, 5, 5, 0] on a 32-bit platform,
- *    so default size of levels is 128 bytes.
- *
- * 2) [0, 10]: [10, 4, 4, 4, 4, 4, 0] on a 64-bit platform or
- *             [10, 5, 5, 5, 5, 0, 0] on a 32-bit platform,
- *    so default size of levels is 128 bytes on all levels except
- *    the first level.  The first level is 8K or 4K on 64-bit or 32-bit
- *    platforms respectively.
- *
- * All buckets in a hash are the same size which is a power of 2.
- * A bucket contains several entries stored and tested sequentially.
- * The bucket size should be one or two CPU cache line size, a minimum
- * allowed size is 32 bytes.  A default 128-byte bucket contains 10 64-bit
- * entries or 15 32-bit entries.  Each entry consists of pointer to value
- * data and 32-bit key.  If an entry value pointer is NULL, the entry is free.
- * On a 64-bit platform entry value pointers are no aligned, therefore they
- * are accessed as two 32-bit integers.  The rest trailing space in a bucket
- * is used as pointer to next bucket and this pointer is always aligned.
- * Although the level hash allows to store a lot of values in a bucket chain,
- * this is non optimal way.  The large data set should be stored using
- * several levels.
- */
-
-#define njs_lvlhsh_is_bucket(p)                                               \
-    ((uintptr_t) (p) & 1)
-
-
-#define njs_lvlhsh_count_inc(n)                                               \
-    n = (void *) ((uintptr_t) (n) + 2)
-
-
-#define njs_lvlhsh_count_dec(n)                                               \
-    n = (void *) ((uintptr_t) (n) - 2)
-
-
-#define njs_lvlhsh_level_size(proto, nlvl)                                    \
-    ((uintptr_t) 1 << proto->shift[nlvl])
-
-
-#define njs_lvlhsh_level(lvl, mask)                                           \
-    (void **) ((uintptr_t) lvl & (~mask << 2))
-
-
-#define njs_lvlhsh_level_entries(lvl, mask)                                   \
-    ((uintptr_t) lvl & (mask << 1))
-
-
-#define njs_lvlhsh_store_bucket(slot, bkt)                                    \
-    slot = (void **) ((uintptr_t) bkt | 2 | 1)
-
-
-#define njs_lvlhsh_bucket_size(proto)                                         \
-    proto->bucket_size
-
-
-#define njs_lvlhsh_bucket(proto, bkt)                                         \
-    (uint32_t *) ((uintptr_t) bkt & ~(uintptr_t) proto->bucket_mask)
-
-
-#define njs_lvlhsh_bucket_entries(proto, bkt)                                 \
-    (((uintptr_t) bkt & (uintptr_t) proto->bucket_mask) >> 1)
-
-
-#define njs_lvlhsh_bucket_end(proto, bkt)                                     \
-    &bkt[proto->bucket_end]
-
-
-#define njs_lvlhsh_free_entry(e)                                              \
-    (!(njs_lvlhsh_valid_entry(e)))
-
-
-#define njs_lvlhsh_next_bucket(proto, bkt)                                    \
-    ((void **) &bkt[proto->bucket_end])
-
-#if (NJS_64BIT)
-
-#define njs_lvlhsh_valid_entry(e)                                             \
-    (((e)[0] | (e)[1]) != 0)
-
-
-#define njs_lvlhsh_entry_value(e)                                             \
-    (void *) (((uintptr_t) (e)[1] << 32) + (e)[0])
-
-
-#define njs_lvlhsh_set_entry_value(e, n)                                      \
-    (e)[0] = (uint32_t)  (uintptr_t) n;                                       \
-    (e)[1] = (uint32_t) ((uintptr_t) n >> 32)
-
-
-#define njs_lvlhsh_entry_key(e)                                               \
-    (e)[2]
-
-
-#define njs_lvlhsh_set_entry_key(e, n)                                        \
-    (e)[2] = n
-
-#else
-
-#define njs_lvlhsh_valid_entry(e)                                             \
-    ((e)[0] != 0)
-
-
-#define njs_lvlhsh_entry_value(e)                                             \
-    (void *) (e)[0]
-
-
-#define njs_lvlhsh_set_entry_value(e, n)                                      \
-    (e)[0] = (uint32_t) n
-
-
-#define njs_lvlhsh_entry_key(e)                                               \
-    (e)[1]
-
-
-#define njs_lvlhsh_set_entry_key(e, n)                                        \
-    (e)[1] = n
-
-#endif
-
-
-#define NJS_LVLHSH_BUCKET_DONE  ((void *) -1)
-
-
-static njs_int_t njs_lvlhsh_level_find(njs_lvlhsh_query_t *lhq, void **lvl,
-    uint32_t key, njs_uint_t nlvl);
-static njs_int_t njs_lvlhsh_bucket_find(njs_lvlhsh_query_t *lhq, void **bkt);
-static njs_int_t njs_lvlhsh_new_bucket(njs_lvlhsh_query_t *lhq, void **slot);
-static njs_int_t njs_lvlhsh_level_insert(njs_lvlhsh_query_t *lhq,
-    void **slot, uint32_t key, njs_uint_t nlvl);
-static njs_int_t njs_lvlhsh_bucket_insert(njs_lvlhsh_query_t *lhq,
-    void **slot, uint32_t key, njs_int_t nlvl);
-static njs_int_t njs_lvlhsh_convert_bucket_to_level(njs_lvlhsh_query_t *lhq,
-    void **slot, njs_uint_t nlvl, uint32_t *bucket);
-static njs_int_t njs_lvlhsh_level_convertion_insert(njs_lvlhsh_query_t *lhq,
-    void **parent, uint32_t key, njs_uint_t nlvl);
-static njs_int_t njs_lvlhsh_bucket_convertion_insert(njs_lvlhsh_query_t *lhq,
-    void **slot, uint32_t key, njs_int_t nlvl);
-static njs_int_t njs_lvlhsh_free_level(njs_lvlhsh_query_t *lhq, void **level,
-    njs_uint_t size);
-static njs_int_t njs_lvlhsh_level_delete(njs_lvlhsh_query_t *lhq, void **slot,
-    uint32_t key, njs_uint_t nlvl);
-static njs_int_t njs_lvlhsh_bucket_delete(njs_lvlhsh_query_t *lhq, void **bkt);
-static void *njs_lvlhsh_level_each(njs_lvlhsh_each_t *lhe, void **level,
-    njs_uint_t nlvl, njs_uint_t shift);
-static void *njs_lvlhsh_bucket_each(njs_lvlhsh_each_t *lhe);
-
-
-njs_int_t
-njs_lvlhsh_find(const njs_lvlhsh_t *lh, njs_lvlhsh_query_t *lhq)
-{
-    void  *slot;
-
-    slot = lh->slot;
-
-    if (njs_fast_path(slot != NULL)) {
-
-        if (njs_lvlhsh_is_bucket(slot)) {
-            return njs_lvlhsh_bucket_find(lhq, slot);
-        }
-
-        return njs_lvlhsh_level_find(lhq, slot, lhq->key_hash, 0);
-    }
-
-    return NJS_DECLINED;
-}
-
-
-static njs_int_t
-njs_lvlhsh_level_find(njs_lvlhsh_query_t *lhq, void **lvl, uint32_t key,
-    njs_uint_t nlvl)
-{
-    void        **slot;
-    uintptr_t   mask;
-    njs_uint_t  shift;
-
-    shift = lhq->proto->shift[nlvl];
-    mask = ((uintptr_t) 1 << shift) - 1;
-
-    lvl = njs_lvlhsh_level(lvl, mask);
-    slot = lvl[key & mask];
-
-    if (slot != NULL) {
-
-        if (njs_lvlhsh_is_bucket(slot)) {
-            return njs_lvlhsh_bucket_find(lhq, slot);
-        }
-
-        return njs_lvlhsh_level_find(lhq, slot, key >> shift, nlvl + 1);
-    }
-
-    return NJS_DECLINED;
-}
-
-
-static njs_int_t
-njs_lvlhsh_bucket_find(njs_lvlhsh_query_t *lhq, void **bkt)
-{
-    void        *value;
-    uint32_t    *bucket, *e;
-    njs_uint_t  n;
-
-    do {
-        bucket = njs_lvlhsh_bucket(lhq->proto, bkt);
-        n = njs_lvlhsh_bucket_entries(lhq->proto, bkt);
-        e = bucket;
-
-        do {
-            if (njs_lvlhsh_valid_entry(e)) {
-                n--;
-
-                if (njs_lvlhsh_entry_key(e) == lhq->key_hash) {
-
-                    value = njs_lvlhsh_entry_value(e);
-
-                    if (lhq->proto->test(lhq, value) == NJS_OK) {
-                        lhq->value = value;
-
-                        return NJS_OK;
-                    }
-                }
-            }
-
-            e += NJS_LVLHSH_ENTRY_SIZE;
-
-        } while (n != 0);
-
-        bkt = *njs_lvlhsh_next_bucket(lhq->proto, bucket);
-
-    } while (bkt != NULL);
-
-    return NJS_DECLINED;
-}
-
-
-njs_int_t
-njs_lvlhsh_insert(njs_lvlhsh_t *lh, njs_lvlhsh_query_t *lhq)
-{
-    uint32_t  key;
-
-    if (njs_fast_path(lh->slot != NULL)) {
-
-        key = lhq->key_hash;
-
-        if (njs_lvlhsh_is_bucket(lh->slot)) {
-            return njs_lvlhsh_bucket_insert(lhq, &lh->slot, key, -1);
-        }
-
-        return njs_lvlhsh_level_insert(lhq, &lh->slot, key, 0);
-    }
-
-    return njs_lvlhsh_new_bucket(lhq, &lh->slot);
-}
-
-
-static njs_int_t
-njs_lvlhsh_new_bucket(njs_lvlhsh_query_t *lhq, void **slot)
-{
-    uint32_t  *bucket;
-
-    bucket = lhq->proto->alloc(lhq->pool, njs_lvlhsh_bucket_size(lhq->proto));
-
-    if (njs_fast_path(bucket != NULL)) {
-
-        njs_lvlhsh_set_entry_value(bucket, lhq->value);
-        njs_lvlhsh_set_entry_key(bucket, lhq->key_hash);
-
-        *njs_lvlhsh_next_bucket(lhq->proto, bucket) = NULL;
-
-        njs_lvlhsh_store_bucket(*slot, bucket);
-
-        return NJS_OK;
-    }
-
-    return NJS_ERROR;
-}
-
-
-static njs_int_t
-njs_lvlhsh_level_insert(njs_lvlhsh_query_t *lhq, void **parent, uint32_t key,
-    njs_uint_t nlvl)
-{
-    void        **slot, **lvl;
-    njs_int_t   ret;
-    uintptr_t   mask;
-    njs_uint_t  shift;
-
-    shift = lhq->proto->shift[nlvl];
-    mask = ((uintptr_t) 1 << shift) - 1;
-
-    lvl = njs_lvlhsh_level(*parent, mask);
-    slot = &lvl[key & mask];
-
-    if (*slot != NULL) {
-        key >>= shift;
-
-        if (njs_lvlhsh_is_bucket(*slot)) {
-            return njs_lvlhsh_bucket_insert(lhq, slot, key, nlvl);
-        }
-
-        return njs_lvlhsh_level_insert(lhq, slot, key, nlvl + 1);
-    }
-
-    ret = njs_lvlhsh_new_bucket(lhq, slot);
-
-    if (njs_fast_path(ret == NJS_OK)) {
-        njs_lvlhsh_count_inc(*parent);
-    }
-
-    return ret;
-}
-
-
-static njs_int_t
-njs_lvlhsh_bucket_insert(njs_lvlhsh_query_t *lhq, void **slot, uint32_t key,
-    njs_int_t nlvl)
-{
-    void                      **bkt, **vacant_bucket, *value;
-    uint32_t                  *bucket, *e, *vacant_entry;
-    njs_int_t                 ret;
-    uintptr_t                 n;
-    const void                *new_value;
-    const njs_lvlhsh_proto_t  *proto;
-
-    bkt = slot;
-    vacant_entry = NULL;
-    vacant_bucket = NULL;
-    proto = lhq->proto;
-
-    /* Search for duplicate entry in bucket chain. */
-
-    do {
-        bucket = njs_lvlhsh_bucket(proto, *bkt);
-        n = njs_lvlhsh_bucket_entries(proto, *bkt);
-        e = bucket;
-
-        do {
-            if (njs_lvlhsh_valid_entry(e)) {
-
-                if (njs_lvlhsh_entry_key(e) == lhq->key_hash) {
-
-                    value = njs_lvlhsh_entry_value(e);
-
-                    if (proto->test(lhq, value) == NJS_OK) {
-
-                        new_value = lhq->value;
-                        lhq->value = value;
-
-                        if (lhq->replace) {
-                            njs_lvlhsh_set_entry_value(e, new_value);
-
-                            return NJS_OK;
-                        }
-
-                        return NJS_DECLINED;
-                    }
-                }
-
-                n--;
-
-            } else {
-                /*
-                 * Save a hole vacant position in bucket
-                 * and continue to search for duplicate entry.
-                 */
-                if (vacant_entry == NULL) {
-                    vacant_entry = e;
-                    vacant_bucket = bkt;
-                }
-            }
-
-            e += NJS_LVLHSH_ENTRY_SIZE;
-
-        } while (n != 0);
-
-        if (e < njs_lvlhsh_bucket_end(proto, bucket)) {
-            /*
-             * Save a vacant position on incomplete bucket's end
-             * and continue to search for duplicate entry.
-             */
-            if (vacant_entry == NULL) {
-                vacant_entry = e;
-                vacant_bucket = bkt;
-            }
-        }
-
-        bkt = njs_lvlhsh_next_bucket(proto, bucket);
-
-    } while (*bkt != NULL);
-
-    if (vacant_entry != NULL) {
-        njs_lvlhsh_set_entry_value(vacant_entry, lhq->value);
-        njs_lvlhsh_set_entry_key(vacant_entry, lhq->key_hash);
-        njs_lvlhsh_count_inc(*vacant_bucket);
-
-        return NJS_OK;
-    }
-
-    /* All buckets are full. */
-
-    nlvl++;
-
-    if (njs_fast_path(proto->shift[nlvl] != 0)) {
-
-        ret = njs_lvlhsh_convert_bucket_to_level(lhq, slot, nlvl, bucket);
-
-        if (njs_fast_path(ret == NJS_OK)) {
-            return njs_lvlhsh_level_insert(lhq, slot, key, nlvl);
-        }
-
-        return ret;
-    }
-
-    /* The last allowed level, only buckets may be allocated here. */
-
-    return njs_lvlhsh_new_bucket(lhq, bkt);
-}
-
-
-static njs_int_t
-njs_lvlhsh_convert_bucket_to_level(njs_lvlhsh_query_t *lhq, void **slot,
-    njs_uint_t nlvl, uint32_t *bucket)
-{
-    void                      *lvl, **level;
-    uint32_t                  *e, *end, key;
-    njs_int_t                 ret;
-    njs_uint_t                i, shift, size;
-    njs_lvlhsh_query_t        q;
-    const njs_lvlhsh_proto_t  *proto;
-
-    proto = lhq->proto;
-    size = njs_lvlhsh_level_size(proto, nlvl);
-
-    lvl = proto->alloc(lhq->pool, size * (sizeof(void *)));
-
-    if (njs_slow_path(lvl == NULL)) {
-        return NJS_ERROR;
-    }
-
-    njs_memzero(lvl, size * (sizeof(void *)));
-
-    level = lvl;
-    shift = 0;
-
-    for (i = 0; i < nlvl; i++) {
-        /*
-         * Using SIMD operations in this trivial loop with maximum
-         * 8 iterations may increase code size by 170 bytes.
-         */
-        njs_pragma_loop_disable_vectorization;
-
-        shift += proto->shift[i];
-    }
-
-    end = njs_lvlhsh_bucket_end(proto, bucket);
-
-    for (e = bucket; e < end; e += NJS_LVLHSH_ENTRY_SIZE) {
-
-        q.proto = proto;
-        q.pool = lhq->pool;
-        q.value = njs_lvlhsh_entry_value(e);
-        key = njs_lvlhsh_entry_key(e);
-        q.key_hash = key;
-
-        ret = njs_lvlhsh_level_convertion_insert(&q, &lvl, key >> shift, nlvl);
-
-        if (njs_slow_path(ret != NJS_OK)) {
-            return njs_lvlhsh_free_level(lhq, level, size);
-        }
-    }
-
-    *slot = lvl;
-
-    proto->free(lhq->pool, bucket, njs_lvlhsh_bucket_size(proto));
-
-    return NJS_OK;
-}
-
-
-static njs_int_t
-njs_lvlhsh_level_convertion_insert(njs_lvlhsh_query_t *lhq, void **parent,
-    uint32_t key, njs_uint_t nlvl)
-{
-    void        **slot, **lvl;
-    njs_int_t   ret;
-    uintptr_t   mask;
-    njs_uint_t  shift;
-
-    shift = lhq->proto->shift[nlvl];
-    mask = ((uintptr_t) 1 << shift) - 1;
-
-    lvl = njs_lvlhsh_level(*parent, mask);
-    slot = &lvl[key & mask];
-
-    if (*slot == NULL) {
-        ret = njs_lvlhsh_new_bucket(lhq, slot);
-
-        if (njs_fast_path(ret == NJS_OK)) {
-            njs_lvlhsh_count_inc(*parent);
-        }
-
-        return ret;
-    }
-
-    /* Only backets can be here. */
-
-    return njs_lvlhsh_bucket_convertion_insert(lhq, slot, key >> shift, nlvl);
-}
-
-
-/*
- * The special bucket insertion procedure is required because during
- * convertion lhq->key contains garbage values and the test function
- * cannot be called.  Besides, the procedure can be simpler because
- * a new entry is inserted just after occupied entries.
- */
-
-static njs_int_t
-njs_lvlhsh_bucket_convertion_insert(njs_lvlhsh_query_t *lhq, void **slot,
-    uint32_t key, njs_int_t nlvl)
-{
-    void                      **bkt;
-    uint32_t                  *bucket, *e;
-    njs_int_t                 ret;
-    uintptr_t                 n;
-    const njs_lvlhsh_proto_t  *proto;
-
-    bkt = slot;
-    proto = lhq->proto;
-
-    do {
-        bucket = njs_lvlhsh_bucket(proto, *bkt);
-        n = njs_lvlhsh_bucket_entries(proto, *bkt);
-        e = bucket + n * NJS_LVLHSH_ENTRY_SIZE;
-
-        if (njs_fast_path(e < njs_lvlhsh_bucket_end(proto, bucket))) {
-
-            njs_lvlhsh_set_entry_value(e, lhq->value);
-            njs_lvlhsh_set_entry_key(e, lhq->key_hash);
-            njs_lvlhsh_count_inc(*bkt);
-
-            return NJS_OK;
-        }
-
-        bkt = njs_lvlhsh_next_bucket(proto, bucket);
-
-    } while (*bkt != NULL);
-
-    /* All buckets are full. */
-
-    nlvl++;
-
-    if (njs_fast_path(proto->shift[nlvl] != 0)) {
-
-        ret = njs_lvlhsh_convert_bucket_to_level(lhq, slot, nlvl, bucket);
-
-        if (njs_fast_path(ret == NJS_OK)) {
-            return njs_lvlhsh_level_insert(lhq, slot, key, nlvl);
-        }
-
-        return ret;
-    }
-
-    /* The last allowed level, only buckets may be allocated here. */
-
-    return njs_lvlhsh_new_bucket(lhq, bkt);
-}
-
-
-static njs_int_t
-njs_lvlhsh_free_level(njs_lvlhsh_query_t *lhq, void **level, njs_uint_t size)
-{
-    size_t                    bsize;
-    njs_uint_t                i;
-    const njs_lvlhsh_proto_t  *proto;
-
-    proto = lhq->proto;
-    bsize = njs_lvlhsh_bucket_size(proto);
-
-    for (i = 0; i < size; i++) {
-
-        if (level[i] != NULL) {
-            /*
-             * Chained buckets are not possible here, since even
-             * in the worst case one bucket cannot be converted
-             * in two chained buckets but remains the same bucket.
-             */
-            proto->free(lhq->pool, njs_lvlhsh_bucket(proto, level[i]), bsize);
-        }
-    }
-
-    proto->free(lhq->pool, level, size * (sizeof(void *)));
-
-    return NJS_ERROR;
-}
-
-
-njs_int_t
-njs_lvlhsh_delete(njs_lvlhsh_t *lh, njs_lvlhsh_query_t *lhq)
-{
-    if (njs_fast_path(lh->slot != NULL)) {
-
-        if (njs_lvlhsh_is_bucket(lh->slot)) {
-            return njs_lvlhsh_bucket_delete(lhq, &lh->slot);
-        }
-
-        return njs_lvlhsh_level_delete(lhq, &lh->slot, lhq->key_hash, 0);
-    }
-
-    return NJS_DECLINED;
-}
-
-
-static njs_int_t
-njs_lvlhsh_level_delete(njs_lvlhsh_query_t *lhq, void **parent, uint32_t key,
-    njs_uint_t nlvl)
-{
-    size_t      size;
-    void        **slot, **lvl;
-    uintptr_t   mask;
-    njs_int_t   ret;
-    njs_uint_t  shift;
-
-    shift = lhq->proto->shift[nlvl];
-    mask = ((uintptr_t) 1 << shift) - 1;
-
-    lvl = njs_lvlhsh_level(*parent, mask);
-    slot = &lvl[key & mask];
-
-    if (*slot != NULL) {
-
-        if (njs_lvlhsh_is_bucket(*slot)) {
-            ret = njs_lvlhsh_bucket_delete(lhq, slot);
-
-        } else {
-            key >>= shift;
-            ret = njs_lvlhsh_level_delete(lhq, slot, key, nlvl + 1);
-        }
-
-        if (*slot == NULL) {
-            njs_lvlhsh_count_dec(*parent);
-
-            if (njs_lvlhsh_level_entries(*parent, mask) == 0) {
-                *parent = NULL;
-                size = njs_lvlhsh_level_size(lhq->proto, nlvl);
-                lhq->proto->free(lhq->pool, lvl, size * sizeof(void *));
-            }
-        }
-
-        return ret;
-    }
-
-    return NJS_DECLINED;
-}
-
-
-static njs_int_t
-njs_lvlhsh_bucket_delete(njs_lvlhsh_query_t *lhq, void **bkt)
-{
-    void                      *value;
-    size_t                    size;
-    uint32_t                  *bucket, *e;
-    uintptr_t                 n;
-    const njs_lvlhsh_proto_t  *proto;
-
-    proto = lhq->proto;
-
-    do {
-        bucket = njs_lvlhsh_bucket(proto, *bkt);
-        n = njs_lvlhsh_bucket_entries(proto, *bkt);
-        e = bucket;
-
-        do {
-            if (njs_lvlhsh_valid_entry(e)) {
-
-                if (njs_lvlhsh_entry_key(e) == lhq->key_hash) {
-
-                    value = njs_lvlhsh_entry_value(e);
-
-                    if (proto->test(lhq, value) == NJS_OK) {
-
-                        if (njs_lvlhsh_bucket_entries(proto, *bkt) == 1) {
-                            *bkt = *njs_lvlhsh_next_bucket(proto, bucket);
-                            size = njs_lvlhsh_bucket_size(proto);
-                            proto->free(lhq->pool, bucket, size);
-
-                        } else {
-                            njs_lvlhsh_count_dec(*bkt);
-                            njs_lvlhsh_set_entry_value(e, NULL);
-                        }
-
-                        lhq->value = value;
-
-                        return NJS_OK;
-                    }
-                }
-
-                n--;
-            }
-
-            e += NJS_LVLHSH_ENTRY_SIZE;
-
-        } while (n != 0);
-
-        bkt = njs_lvlhsh_next_bucket(proto, bucket);
-
-    } while (*bkt != NULL);
-
-    return NJS_DECLINED;
-}
-
-
-void *
-njs_lvlhsh_each(const njs_lvlhsh_t *lh, njs_lvlhsh_each_t *lhe)
-{
-    void  **slot;
-
-    if (lhe->bucket == NJS_LVLHSH_BUCKET_DONE) {
-        slot = lh->slot;
-
-        if (njs_lvlhsh_is_bucket(slot)) {
-            return NULL;
-        }
-
-    } else {
-        if (njs_slow_path(lhe->bucket == NULL)) {
-
-            /* The first iteration only. */
-
-            slot = lh->slot;
-
-            if (slot == NULL) {
-                return NULL;
-            }
-
-            if (!njs_lvlhsh_is_bucket(slot)) {
-                goto level;
-            }
-
-            lhe->bucket = njs_lvlhsh_bucket(lhe->proto, slot);
-            lhe->entries = njs_lvlhsh_bucket_entries(lhe->proto, slot);
-        }
-
-        return njs_lvlhsh_bucket_each(lhe);
-    }
-
-level:
-
-    return njs_lvlhsh_level_each(lhe, slot, 0, 0);
-}
-
-
-static void *
-njs_lvlhsh_level_each(njs_lvlhsh_each_t *lhe, void **level, njs_uint_t nlvl,
-    njs_uint_t shift)
-{
-    void        **slot, *value;
-    uintptr_t   mask;
-    njs_uint_t  n, level_shift;
-
-    level_shift = lhe->proto->shift[nlvl];
-    mask = ((uintptr_t) 1 << level_shift) - 1;
-
-    level = njs_lvlhsh_level(level, mask);
-
-    do {
-        n = (lhe->current >> shift) & mask;
-        slot = level[n];
-
-        if (slot != NULL) {
-            if (njs_lvlhsh_is_bucket(slot)) {
-
-                if (lhe->bucket != NJS_LVLHSH_BUCKET_DONE) {
-
-                    lhe->bucket = njs_lvlhsh_bucket(lhe->proto, slot);
-                    lhe->entries = njs_lvlhsh_bucket_entries(lhe->proto, slot);
-                    lhe->entry = 0;
-
-                    return njs_lvlhsh_bucket_each(lhe);
-                }
-
-                lhe->bucket = NULL;
-
-            } else {
-                value = njs_lvlhsh_level_each(lhe, slot, nlvl + 1,
-                                              shift + level_shift);
-                if (value != NULL) {
-                    return value;
-                }
-            }
-        }
-
-        lhe->current &= ~(mask << shift);
-        n = ((n + 1) & mask) << shift;
-        lhe->current |= n;
-
-    } while (n != 0);
-
-    return NULL;
-}
-
-
-static void *
-njs_lvlhsh_bucket_each(njs_lvlhsh_each_t *lhe)
-{
-    void      *value, **next;
-    uint32_t  *bucket;
-
-    /* At least one valid entry must present here. */
-    do {
-        bucket = &lhe->bucket[lhe->entry];
-        lhe->entry += NJS_LVLHSH_ENTRY_SIZE;
-
-    } while (njs_lvlhsh_free_entry(bucket));
-
-    value = njs_lvlhsh_entry_value(bucket);
-    lhe->key_hash = njs_lvlhsh_entry_key(bucket);
-
-    lhe->entries--;
-
-    if (lhe->entries == 0) {
-        next = *njs_lvlhsh_next_bucket(lhe->proto, lhe->bucket);
-
-        lhe->bucket = (next == NULL) ? NJS_LVLHSH_BUCKET_DONE
-                                     : njs_lvlhsh_bucket(lhe->proto, next);
-
-        lhe->entries = njs_lvlhsh_bucket_entries(lhe->proto, next);
-        lhe->entry = 0;
-    }
-
-    return value;
-}