diff options
Diffstat (limited to '')
| -rw-r--r-- | src/nxt_lvlhsh.c | 112 | ||||
| -rw-r--r-- | src/nxt_lvlhsh.h | 9 | ||||
| -rw-r--r-- | src/test/nxt_lvlhsh_test.c | 37 |
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"); |