Initial version.

1 files changed, 188 insertions, 0 deletions

diff --git a/src/nxt_lvlhsh.h b/src/nxt_lvlhsh.h
new file mode 100644
index 00000000..554e958b
--- /dev/null
+++ b/src/nxt_lvlhsh.h
@@ -0,0 +1,188 @@
+
+/*
+ * Copyright (C) Igor Sysoev
+ * Copyright (C) NGINX, Inc.
+ */
+
+#ifndef _NXT_LEVEL_HASH_H_INCLUDED_
+#define _NXT_LEVEL_HASH_H_INCLUDED_
+
+
+typedef struct nxt_lvlhsh_query_s  nxt_lvlhsh_query_t;
+
+typedef nxt_int_t (*nxt_lvlhsh_test_t)(nxt_lvlhsh_query_t *lhq, void *data);
+typedef void *(*nxt_lvlhsh_alloc_t)(void *ctx, size_t size, nxt_uint_t nalloc);
+typedef void (*nxt_lvlhsh_free_t)(void *ctx, void *p, size_t size);
+
+
+#if (NXT_64BIT)
+
+#define NXT_LVLHSH_DEFAULT_BUCKET_SIZE  128
+#define NXT_LVLHSH_ENTRY_SIZE           3
+#define NXT_LVLHSH_BATCH_ALLOC          16
+
+/* 3 is shift of 64-bit pointer. */
+#define NXT_LVLHSH_MEMALIGN_SHIFT       (NXT_MAX_MEMALIGN_SHIFT - 3)
+
+#else
+
+#define NXT_LVLHSH_DEFAULT_BUCKET_SIZE  64
+#define NXT_LVLHSH_ENTRY_SIZE           2
+#define NXT_LVLHSH_BATCH_ALLOC          8
+
+/* 2 is shift of 32-bit pointer. */
+#define NXT_LVLHSH_MEMALIGN_SHIFT       (NXT_MAX_MEMALIGN_SHIFT - 2)
+
+#endif
+
+
+#if (NXT_LVLHSH_MEMALIGN_SHIFT < 10)
+#define NXT_LVLHSH_MAX_MEMALIGN_SHIFT   NXT_LVLHSH_MEMALIGN_SHIFT
+#else
+#define NXT_LVLHSH_MAX_MEMALIGN_SHIFT   10
+#endif
+
+
+#define NXT_LVLHSH_BUCKET_END(bucket_size)                                    \
+    (((bucket_size) - sizeof(void *))                                         \
+        / (NXT_LVLHSH_ENTRY_SIZE * sizeof(uint32_t))                          \
+     * NXT_LVLHSH_ENTRY_SIZE)
+
+
+#define NXT_LVLHSH_BUCKET_SIZE(bucket_size)                                   \
+    NXT_LVLHSH_BUCKET_END(bucket_size), bucket_size, (bucket_size - 1)
+
+
+#define NXT_LVLHSH_DEFAULT                                                    \
+    NXT_LVLHSH_BUCKET_SIZE(NXT_LVLHSH_DEFAULT_BUCKET_SIZE),                   \
+    { 4, 4, 4, 4, 4, 4, 4, 0 }
+
+
+#define NXT_LVLHSH_LARGE_SLAB                                                 \
+    NXT_LVLHSH_BUCKET_SIZE(NXT_LVLHSH_DEFAULT_BUCKET_SIZE),                   \
+    { 10, 4, 4, 4, 4, 4, 4, 0 }
+
+
+#define NXT_LVLHSH_LARGE_MEMALIGN                                             \
+    NXT_LVLHSH_BUCKET_SIZE(NXT_LVLHSH_DEFAULT_BUCKET_SIZE),                   \
+    { NXT_LVLHSH_MAX_MEMALIGN_SHIFT, 4, 4, 4, 4, 0, 0, 0 }
+
+
+typedef struct {
+    uint32_t                  bucket_end;
+    uint32_t                  bucket_size;
+    uint32_t                  bucket_mask;
+    uint8_t                   shift[8];
+    uint32_t                  nalloc;
+
+    nxt_lvlhsh_test_t         test;
+    nxt_lvlhsh_alloc_t        alloc;
+    nxt_lvlhsh_free_t         free;
+} nxt_lvlhsh_proto_t;
+
+
+typedef struct {
+    nxt_lvlhsh_test_t         test;
+    nxt_lvlhsh_alloc_t        alloc;
+    nxt_lvlhsh_free_t         free;
+
+    /* The maximum allowed aligned shift. */
+    uint32_t                  max_shift;
+    uint32_t                  nalloc;
+} nxt_lvlhsh_ctx_t;
+
+
+typedef struct {
+    void                      *slot;
+} nxt_lvlhsh_t;
+
+
+struct nxt_lvlhsh_query_s {
+    uint32_t                  key_hash;
+    uint32_t                  replace;   /* 1 bit */
+    nxt_str_t                 key;
+    void                      *value;
+
+    const nxt_lvlhsh_proto_t  *proto;
+    void                      *pool;
+
+    /* Opaque data passed for the test function. */
+    void                      *data;
+};
+
+
+#define                                                                       \
+nxt_lvlhsh_is_empty(lh)                                                       \
+    ((lh)->slot == NULL)
+
+
+#define                                                                       \
+nxt_lvlhsh_init(lh)                                                           \
+    (lh)->slot = NULL
+
+/*
+ * nxt_lvlhsh_find() finds a hash element.  If the element has been
+ * found then it is stored in the lhq->value and nxt_lvlhsh_find()
+ * returns NXT_OK.  Otherwise NXT_DECLINED is returned.
+ *
+ * The required nxt_lvlhsh_query_t fields: key_hash, key, proto.
+ */
+NXT_EXPORT nxt_int_t nxt_lvlhsh_find(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq);
+
+/*
+ * nxt_lvlhsh_insert() adds a hash element.  If the element already
+ * presents in lvlhsh and the lhq->replace flag is zero, then lhq->value
+ * is updated with the old element and NXT_DECLINED is returned.
+ * If the element already presents in lvlhsh and the lhq->replace flag
+ * is non-zero, then the old element is replaced with the new element.
+ * lhq->value is updated with the old element, and NXT_OK is returned.
+ * If the element is not present in lvlhsh, then it is inserted and
+ * NXT_OK is returned.  The lhq->value is not changed.
+ * On memory allocation failure NXT_ERROR is returned.
+ *
+ * The required nxt_lvlhsh_query_t fields: key_hash, key, proto, replace, value.
+ * The optional nxt_lvlhsh_query_t fields: pool.
+ */
+NXT_EXPORT nxt_int_t nxt_lvlhsh_insert(nxt_lvlhsh_t *lh,
+    nxt_lvlhsh_query_t *lhq);
+
+/*
+ * nxt_lvlhsh_delete() deletes a hash element.  If the element has been
+ * found then it is removed from lvlhsh and is stored in the lhq->value,
+ * and NXT_OK is returned.  Otherwise NXT_DECLINED is returned.
+ *
+ * The required nxt_lvlhsh_query_t fields: key_hash, key, proto.
+ * The optional nxt_lvlhsh_query_t fields: pool.
+ */
+NXT_EXPORT nxt_int_t nxt_lvlhsh_delete(nxt_lvlhsh_t *lh,
+    nxt_lvlhsh_query_t *lhq);
+
+
+typedef struct {
+    const nxt_lvlhsh_proto_t  *proto;
+
+    /*
+     * Fields to store current bucket entry position.  They cannot be
+     * combined in a single bucket pointer with number of entries in low
+     * bits, because entry positions are not aligned.  A current level is
+     * stored as key bit path from the root.
+     */
+    uint32_t                  *bucket;
+    uint32_t                  current;
+    uint32_t                  entry;
+    uint32_t                  entries;
+} nxt_lvlhsh_each_t;
+
+
+NXT_EXPORT void *nxt_lvlhsh_each(nxt_lvlhsh_t *lh, nxt_lvlhsh_each_t *le);
+
+
+NXT_EXPORT void *nxt_lvlhsh_alloc(void *data, size_t size, nxt_uint_t nalloc);
+NXT_EXPORT void nxt_lvlhsh_free(void *data, void *p, size_t size);
+
+NXT_EXPORT void *nxt_lvlhsh_pool_alloc(void *ctx, size_t size,
+    nxt_uint_t nalloc);
+NXT_EXPORT void nxt_lvlhsh_pool_free(void *ctx, void *p, size_t size);
+
+
+#endif /* _NXT_LEVEL_HASH_H_INCLUDED_ */