1 files changed, 153 insertions, 0 deletions
diff --git a/src/nxt_lvlhsh_pool.c b/src/nxt_lvlhsh_pool.c
new file mode 100644
index 00000000..5de319f9
--- /dev/null
+++ b/src/nxt_lvlhsh_pool.c
@@ -0,0 +1,153 @@
+
+/*
+ * Copyright (C) Igor Sysoev
+ * Copyright (C) NGINX, Inc.
+ */
+
+#include <nxt_main.h>
+
+
+typedef struct nxt_lvlhsh_pool_cache_s  nxt_lvlhsh_pool_cache_t;
+
+struct nxt_lvlhsh_pool_cache_s {
+    uint32_t                 size;
+    uint32_t                 nalloc;
+    void                     *free;
+    nxt_lvlhsh_pool_cache_t  *next;
+};
+
+
+typedef struct {
+    nxt_mem_pool_t           *mem_pool;
+    void                     *free;
+    nxt_lvlhsh_pool_cache_t  *next;
+} nxt_lvlhsh_pool_t;
+
+
+/*
+ * lvlhsh requires allocations aligned to a size of the allocations.
+ * This is not issue for slab-like allocators, but glibc allocator may
+ * waste memory on such aligned allocations.  So nxt_lvlhsh_pool_alloc()
+ * allocates memory in chunks specified by the "nalloc" parameter
+ * except the first allocation.  The first lvlhsh allocation is a bucket
+ * allocation and it is enough for a small hash or for early stage of
+ * a large hash.  By default lvlhsh uses 128-bytes or 64-bytes buckets
+ * and levels on 64-bit and 32-bit platforms respectively.
+ * This allows to search up to 10 entries in one memory access and
+ * up to 160 entries in two memory accesses on 64-bit platform.
+ * And on 32-bit platform up to 7 entries and up to 112 entries
+ * respectively.
+ *
+ * After the bucket has been filled up with 10 64-bit entries
+ * or 7 32-bit entries, lvlhsh expands it to a level and spreads
+ * content of the first bucket to the level's new buckets.
+ * Number of the new allocations may be up to 11 on 64-bit or
+ * 8 on 32-bit platforms.  It's better to allocate them together
+ * to eliminate wasting memory and CPU time.
+ *
+ * The "nalloc" should be 16.
+ */
+
+
+static void *nxt_lvlhsh_pool_alloc_chunk(nxt_mem_pool_cache_t *cache,
+    size_t size, nxt_uint_t nalloc);
+
+
+/* Allocation of lvlhsh level or bucket with specified size. */
+
+void *
+nxt_lvlhsh_pool_alloc(void *ctx, size_t size, nxt_uint_t nalloc)
+{
+    void                  *p, **pp;
+    nxt_mem_pool_t        *mp;
+    nxt_mem_pool_cache_t  *cache;
+
+    mp = ctx;
+
+    for (cache = mp->cache; cache != NULL; cache = cache->next) {
+
+        if (cache->size == size && cache->nalloc != 0) {
+
+            if (cache->free != NULL) {
+                pp = cache->free;
+                cache->free = *pp;
+                return pp;
+            }
+
+            return nxt_lvlhsh_pool_alloc_chunk(cache, size, nalloc);
+        }
+    }
+
+    cache = nxt_mem_alloc(mp, sizeof(nxt_mem_pool_cache_t));
+
+    if (nxt_fast_path(cache != NULL)) {
+
+        p = nxt_memalign(size, size);
+
+        if (nxt_fast_path(p != NULL)) {
+            cache->size = size;
+            cache->nalloc = nalloc;
+            cache->free = NULL;
+            cache->next = mp->cache;
+            mp->cache = cache;
+            return p;
+        }
+    }
+
+    return NULL;
+}
+
+
+static void *
+nxt_lvlhsh_pool_alloc_chunk(nxt_mem_pool_cache_t *cache, size_t size,
+    nxt_uint_t nalloc)
+{
+    char    *m, *p, *end;
+    void    **pp;
+    size_t  n;
+
+    n = (nalloc == 0) ? 1 : nalloc;
+    n *= size;
+
+    m = nxt_memalign(size, n);
+
+    if (nxt_fast_path(m != NULL)) {
+
+        pp = &cache->free;
+        end = m + n;
+
+        for (p = m + size; p < end; p = p + size) {
+            *pp = p;
+            pp = (void **) p;
+        }
+
+        *pp = NULL;
+    }
+
+    return m;
+}
+
+
+
+/* Deallocation of lvlhsh level or bucket with specified size. */
+
+void
+nxt_lvlhsh_pool_free(void *ctx, void *p, size_t size)
+{
+    void                  **pp;
+    nxt_mem_pool_t        *mp;
+    nxt_mem_pool_cache_t  *cache;
+
+    mp = ctx;
+
+    pp = p;
+
+    for (cache = mp->cache; cache != NULL; cache = cache->next) {
+
+        if (cache->size == size && cache->nalloc != 0) {
+            *pp = cache->free;
+            cache->free = p;
+            return;
+        }
+    }
+}