nxt_lvlhsh_peek().

3 files changed, 101 insertions, 2 deletions

diff --git a/src/nxt_lvlhsh.c b/src/nxt_lvlhsh.c
index bf730ada..07dcf1e9 100644
--- a/src/nxt_lvlhsh.c
+++ b/src/nxt_lvlhsh.c
@@ -188,6 +188,10 @@ static nxt_int_t nxt_lvlhsh_bucket_delete(nxt_lvlhsh_query_t *lhq, void **bkt);
 static void *nxt_lvlhsh_level_each(nxt_lvlhsh_each_t *lhe, void **level,
     nxt_uint_t nlvl, nxt_uint_t shift);
 static void *nxt_lvlhsh_bucket_each(nxt_lvlhsh_each_t *lhe);
+static void *nxt_lvlhsh_level_peek(const nxt_lvlhsh_proto_t *proto,
+    void **level, nxt_uint_t nlvl);
+static void *nxt_lvlhsh_bucket_peek(const nxt_lvlhsh_proto_t *proto,
+    void **bkt);
 
 
 nxt_int_t
@@ -870,6 +874,80 @@ nxt_lvlhsh_bucket_each(nxt_lvlhsh_each_t *lhe)
 
 
 void *
+nxt_lvlhsh_peek(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto)
+{
+    void  **slot;
+
+    slot = lh->slot;
+
+    if (slot != NULL) {
+
+        if (nxt_lvlhsh_is_bucket(slot)) {
+            return nxt_lvlhsh_bucket_peek(proto, slot);
+        }
+
+        return nxt_lvlhsh_level_peek(proto, slot, 0);
+    }
+
+    return NULL;
+}
+
+
+static void *
+nxt_lvlhsh_level_peek(const nxt_lvlhsh_proto_t *proto, void **level,
+    nxt_uint_t nlvl)
+{
+    void        **slot;
+    uintptr_t   mask;
+    nxt_uint_t  n, shift;
+
+    shift = proto->shift[nlvl];
+    mask = ((uintptr_t) 1 << shift) - 1;
+
+    level = nxt_lvlhsh_level(level, mask);
+
+    n = 0;
+
+    /* At least one valid level slot must present here. */
+
+    for ( ;; ) {
+        slot = level[n];
+
+        if (slot != NULL) {
+
+            if (nxt_lvlhsh_is_bucket(slot)) {
+                return nxt_lvlhsh_bucket_peek(proto, slot);
+            }
+
+            return nxt_lvlhsh_level_peek(proto, slot, nlvl + 1);
+        }
+
+        n++;
+    }
+}
+
+
+static void *
+nxt_lvlhsh_bucket_peek(const nxt_lvlhsh_proto_t *proto, void **bkt)
+{
+    void      *value;
+    uint32_t  *entry;
+
+    /* At least one valid entry must present here. */
+
+    for (entry = nxt_lvlhsh_bucket(proto, bkt);
+         nxt_lvlhsh_free_entry(entry);
+         entry += NXT_LVLHSH_ENTRY_SIZE)
+    {
+        /* void */
+    }
+
+    value = nxt_lvlhsh_entry_value(entry);
+    return value;
+}
+
+
+void *
 nxt_lvlhsh_alloc(void *data, size_t size)
 {
     return nxt_memalign(size, size);
diff --git a/src/nxt_lvlhsh.h b/src/nxt_lvlhsh.h
index 01014124..5f180797 100644
--- a/src/nxt_lvlhsh.h
+++ b/src/nxt_lvlhsh.h
@@ -164,6 +164,15 @@ typedef struct {
 
 NXT_EXPORT void *nxt_lvlhsh_each(nxt_lvlhsh_t *lh, nxt_lvlhsh_each_t *le);
 
+/*
+ * nxt_lvlhsh_peek() is used to iterate over a lvlhsh during the lvlhsh
+ * destruction.  The returned hash element should be deleted from the lvlhsh,
+ * otherwise it will be returned again by the next nxt_lvlhsh_peek() call.
+ * The function returns NULL if there is no more elements in the lvlhsh.
+ */
+NXT_EXPORT void *nxt_lvlhsh_peek(nxt_lvlhsh_t *lh,
+    const nxt_lvlhsh_proto_t *proto);
+
 
 NXT_EXPORT void *nxt_lvlhsh_alloc(void *data, size_t size);
 NXT_EXPORT void nxt_lvlhsh_free(void *data, void *p);
diff --git a/src/test/nxt_lvlhsh_test.c b/src/test/nxt_lvlhsh_test.c
index 62139fe6..c808192c 100644
--- a/src/test/nxt_lvlhsh_test.c
+++ b/src/test/nxt_lvlhsh_test.c
@@ -130,6 +130,7 @@ nxt_lvlhsh_test_delete(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
 nxt_int_t
 nxt_lvlhsh_test(nxt_thread_t *thr, nxt_uint_t n, nxt_bool_t use_pool)
 {
+    void                      *value;
     uintptr_t                 key;
     nxt_mp_t                  *mp;
     nxt_nsec_t                start, end;
@@ -201,15 +202,26 @@ nxt_lvlhsh_test(nxt_thread_t *thr, nxt_uint_t n, nxt_bool_t use_pool)
         return NXT_ERROR;
     }
 
-    key = 0;
     for (i = 0; i < n; i++) {
-        key = nxt_murmur_hash2(&key, sizeof(uint32_t));
+        value = nxt_lvlhsh_peek(&lh, proto);
+
+        if (value == NULL) {
+            break;
+        }
+
+        key = (uintptr_t) value;
 
         if (nxt_lvlhsh_test_delete(&lh, proto, mp, key) != NXT_OK) {
             return NXT_ERROR;
         }
     }
 
+    if (i != n) {
+        nxt_log_error(NXT_LOG_NOTICE, thr->log,
+                      "lvlhsh peek test failed at %ui of %ui", i, n);
+        return NXT_ERROR;
+    }
+
     if (mp != NULL) {
         if (!nxt_mp_is_empty(mp)) {
             nxt_log_error(NXT_LOG_NOTICE, thr->log, "mem pool is not empty");