summaryrefslogtreecommitdiffhomepage
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/nxt_lvlhsh.c112
-rw-r--r--src/nxt_lvlhsh.h9
-rw-r--r--src/test/nxt_lvlhsh_test.c37
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");
generated by cgit (git 2.34.1) at 2024-11-17 16:50:10 +0000