nxt_lvlhsh_retrieve().

3 files changed, 136 insertions, 22 deletions

diff --git a/src/nxt_lvlhsh.c b/src/nxt_lvlhsh.c
index 07dcf1e9..864d3007 100644
--- a/src/nxt_lvlhsh.c
+++ b/src/nxt_lvlhsh.c
@@ -166,6 +166,13 @@ nxt_lvlhsh_set_entry_key(e, n)                                                \
 #define NXT_LVLHSH_BUCKET_DONE  ((void *) -1)
 
 
+typedef struct {
+    const nxt_lvlhsh_proto_t  *proto;
+    void                      *pool;
+    uint32_t                  retrieve;  /* 1 bit */
+} nxt_lvlhsh_peek_t;
+
+
 static nxt_int_t nxt_lvlhsh_level_find(nxt_lvlhsh_query_t *lhq, void **lvl,
     uint32_t key, nxt_uint_t nlvl);
 static nxt_int_t nxt_lvlhsh_bucket_find(nxt_lvlhsh_query_t *lhq, void **bkt);
@@ -188,10 +195,9 @@ 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);
+static void *nxt_lvlhsh_level_peek(nxt_lvlhsh_peek_t *peek, void **level,
+    nxt_uint_t nlvl);
+static void *nxt_lvlhsh_bucket_peek(nxt_lvlhsh_peek_t *peek, void **bkt);
 
 
 nxt_int_t
@@ -876,17 +882,21 @@ 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;
+    void               **slot;
+    nxt_lvlhsh_peek_t  peek;
 
     slot = lh->slot;
 
     if (slot != NULL) {
 
+        peek.proto = proto;
+        peek.retrieve = 0;
+
         if (nxt_lvlhsh_is_bucket(slot)) {
-            return nxt_lvlhsh_bucket_peek(proto, slot);
+            return nxt_lvlhsh_bucket_peek(&peek, &lh->slot);
         }
 
-        return nxt_lvlhsh_level_peek(proto, slot, 0);
+        return nxt_lvlhsh_level_peek(&peek, &lh->slot, 0);
     }
 
     return NULL;
@@ -894,32 +904,47 @@ nxt_lvlhsh_peek(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto)
 
 
 static void *
-nxt_lvlhsh_level_peek(const nxt_lvlhsh_proto_t *proto, void **level,
-    nxt_uint_t nlvl)
+nxt_lvlhsh_level_peek(nxt_lvlhsh_peek_t *peek, void **parent, nxt_uint_t nlvl)
 {
-    void        **slot;
+    void        **slot, **level, *value;
     uintptr_t   mask;
     nxt_uint_t  n, shift;
 
-    shift = proto->shift[nlvl];
+    shift = peek->proto->shift[nlvl];
     mask = ((uintptr_t) 1 << shift) - 1;
 
-    level = nxt_lvlhsh_level(level, mask);
+    level = nxt_lvlhsh_level(*parent, mask);
 
     n = 0;
 
     /* At least one valid level slot must present here. */
 
     for ( ;; ) {
-        slot = level[n];
+        slot = &level[n];
 
-        if (slot != NULL) {
+        if (*slot != NULL) {
 
-            if (nxt_lvlhsh_is_bucket(slot)) {
-                return nxt_lvlhsh_bucket_peek(proto, slot);
+            if (nxt_lvlhsh_is_bucket(*slot)) {
+                value = nxt_lvlhsh_bucket_peek(peek, slot);
+
+            } else {
+                value = nxt_lvlhsh_level_peek(peek, slot, nlvl + 1);
+            }
+
+            /*
+             * Checking peek->retrieve is not required here because
+             * there can not be empty slots during peeking.
+             */
+            if (*slot == NULL) {
+                nxt_lvlhsh_count_dec(*parent);
+
+                if (nxt_lvlhsh_level_entries(*parent, mask) == 0) {
+                    *parent = NULL;
+                    peek->proto->free(peek->pool, level);
+                }
             }
 
-            return nxt_lvlhsh_level_peek(proto, slot, nlvl + 1);
+            return value;
         }
 
         n++;
@@ -927,15 +952,18 @@ nxt_lvlhsh_level_peek(const nxt_lvlhsh_proto_t *proto, void **level,
 }
 
 
-static void *
-nxt_lvlhsh_bucket_peek(const nxt_lvlhsh_proto_t *proto, void **bkt)
+static nxt_noinline void *
+nxt_lvlhsh_bucket_peek(nxt_lvlhsh_peek_t *peek, void **bkt)
 {
-    void      *value;
-    uint32_t  *entry;
+    void                      *value;
+    uint32_t                  *bucket, *entry;
+    const nxt_lvlhsh_proto_t  *proto;
+
+    bucket = nxt_lvlhsh_bucket(peek->proto, *bkt);
 
     /* At least one valid entry must present here. */
 
-    for (entry = nxt_lvlhsh_bucket(proto, bkt);
+    for (entry = bucket;
          nxt_lvlhsh_free_entry(entry);
          entry += NXT_LVLHSH_ENTRY_SIZE)
     {
@@ -943,11 +971,51 @@ nxt_lvlhsh_bucket_peek(const nxt_lvlhsh_proto_t *proto, void **bkt)
     }
 
     value = nxt_lvlhsh_entry_value(entry);
+
+    if (peek->retrieve) {
+        proto = peek->proto;
+
+        if (nxt_lvlhsh_bucket_entries(proto, *bkt) == 1) {
+            *bkt = *nxt_lvlhsh_next_bucket(proto, bucket);
+            proto->free(peek->pool, bucket);
+
+        } else {
+            nxt_lvlhsh_count_dec(*bkt);
+            nxt_lvlhsh_set_entry_value(entry, NULL);
+        }
+    }
+
     return value;
 }
 
 
 void *
+nxt_lvlhsh_retrieve(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
+    void *pool)
+{
+    void               **slot;
+    nxt_lvlhsh_peek_t  peek;
+
+    slot = lh->slot;
+
+    if (slot != NULL) {
+
+        peek.proto = proto;
+        peek.pool = pool;
+        peek.retrieve = 1;
+
+        if (nxt_lvlhsh_is_bucket(slot)) {
+            return nxt_lvlhsh_bucket_peek(&peek, &lh->slot);
+        }
+
+        return nxt_lvlhsh_level_peek(&peek, &lh->slot, 0);
+    }
+
+    return NULL;
+}
+
+
+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 5f180797..07342d44 100644
--- a/src/nxt_lvlhsh.h
+++ b/src/nxt_lvlhsh.h
@@ -173,6 +173,15 @@ NXT_EXPORT void *nxt_lvlhsh_each(nxt_lvlhsh_t *lh, nxt_lvlhsh_each_t *le);
 NXT_EXPORT void *nxt_lvlhsh_peek(nxt_lvlhsh_t *lh,
     const nxt_lvlhsh_proto_t *proto);
 
+/*
+ * nxt_lvlhsh_retrieve() is used to iterate over a lvlhsh during the lvlhsh
+ * destruction.  As opposed to nxt_lvlhsh_peek() the returned hash element
+ * is deleted from the lvlhsh.  The function returns NULL if there is no
+ * more elements in the lvlhsh.
+ */
+NXT_EXPORT void *nxt_lvlhsh_retrieve(nxt_lvlhsh_t *lh,
+    const nxt_lvlhsh_proto_t *proto, void *pool);
+
 
 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 c808192c..fca6ed30 100644
--- a/src/test/nxt_lvlhsh_test.c
+++ b/src/test/nxt_lvlhsh_test.c
@@ -222,6 +222,43 @@ nxt_lvlhsh_test(nxt_thread_t *thr, nxt_uint_t n, nxt_bool_t use_pool)
         return NXT_ERROR;
     }
 
+    if (!nxt_lvlhsh_is_empty(&lh)) {
+        nxt_log_error(NXT_LOG_NOTICE, thr->log,
+                      "lvlhsh is not empty after deletion");
+        return NXT_ERROR;
+    }
+
+    key = 0;
+    for (i = 0; i < n; i++) {
+        key = nxt_murmur_hash2(&key, sizeof(uint32_t));
+
+        if (nxt_lvlhsh_test_add(&lh, proto, mp, key) != NXT_OK) {
+            nxt_log_error(NXT_LOG_NOTICE, thr->log,
+                          "lvlhsh add test failed at %ui", i);
+            return NXT_ERROR;
+        }
+    }
+
+    for (i = 0; i < n; i++) {
+        value = nxt_lvlhsh_retrieve(&lh, proto, mp);
+
+        if (value == NULL) {
+            break;
+        }
+    }
+
+    if (i != n) {
+        nxt_log_error(NXT_LOG_NOTICE, thr->log,
+                      "lvlhsh retrieve test failed at %ui of %ui", i, n);
+        return NXT_ERROR;
+    }
+
+    if (!nxt_lvlhsh_is_empty(&lh)) {
+        nxt_log_error(NXT_LOG_NOTICE, thr->log,
+                      "lvlhsh is not empty after retrieving");
+        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");