xref: /unit/src/nxt_lvlhsh.h (revision 598:70677ad404c1)
1 
2 /*
3  * Copyright (C) Igor Sysoev
4  * Copyright (C) NGINX, Inc.
5  */
6 
7 #ifndef _NXT_LEVEL_HASH_H_INCLUDED_
8 #define _NXT_LEVEL_HASH_H_INCLUDED_
9 
10 
11 typedef struct nxt_lvlhsh_query_s  nxt_lvlhsh_query_t;
12 
13 typedef nxt_int_t (*nxt_lvlhsh_test_t)(nxt_lvlhsh_query_t *lhq, void *data);
14 typedef void *(*nxt_lvlhsh_alloc_t)(void *ctx, size_t size);
15 typedef void (*nxt_lvlhsh_free_t)(void *ctx, void *p);
16 
17 
18 #if (NXT_64BIT)
19 
20 #define NXT_LVLHSH_DEFAULT_BUCKET_SIZE  128
21 #define NXT_LVLHSH_ENTRY_SIZE           3
22 #define NXT_LVLHSH_BATCH_ALLOC          16
23 
24 /* 3 is shift of 64-bit pointer. */
25 #define NXT_LVLHSH_MEMALIGN_SHIFT       (NXT_MAX_MEMALIGN_SHIFT - 3)
26 
27 #else
28 
29 #define NXT_LVLHSH_DEFAULT_BUCKET_SIZE  64
30 #define NXT_LVLHSH_ENTRY_SIZE           2
31 #define NXT_LVLHSH_BATCH_ALLOC          8
32 
33 /* 2 is shift of 32-bit pointer. */
34 #define NXT_LVLHSH_MEMALIGN_SHIFT       (NXT_MAX_MEMALIGN_SHIFT - 2)
35 
36 #endif
37 
38 
39 #if (NXT_LVLHSH_MEMALIGN_SHIFT < 10)
40 #define NXT_LVLHSH_MAX_MEMALIGN_SHIFT   NXT_LVLHSH_MEMALIGN_SHIFT
41 #else
42 #define NXT_LVLHSH_MAX_MEMALIGN_SHIFT   10
43 #endif
44 
45 
46 #define NXT_LVLHSH_BUCKET_END(bucket_size)                                    \
47     (((bucket_size) - sizeof(void *))                                         \
48         / (NXT_LVLHSH_ENTRY_SIZE * sizeof(uint32_t))                          \
49      * NXT_LVLHSH_ENTRY_SIZE)
50 
51 
52 #define NXT_LVLHSH_BUCKET_SIZE(bucket_size)                                   \
53     NXT_LVLHSH_BUCKET_END(bucket_size), bucket_size, (bucket_size - 1)
54 
55 
56 #define NXT_LVLHSH_DEFAULT                                                    \
57     NXT_LVLHSH_BUCKET_SIZE(NXT_LVLHSH_DEFAULT_BUCKET_SIZE),                   \
58     { 4, 4, 4, 4, 4, 4, 4, 0 }
59 
60 
61 #define NXT_LVLHSH_LARGE_SLAB                                                 \
62     NXT_LVLHSH_BUCKET_SIZE(NXT_LVLHSH_DEFAULT_BUCKET_SIZE),                   \
63     { 10, 4, 4, 4, 4, 4, 4, 0 }
64 
65 
66 #define NXT_LVLHSH_LARGE_MEMALIGN                                             \
67     NXT_LVLHSH_BUCKET_SIZE(NXT_LVLHSH_DEFAULT_BUCKET_SIZE),                   \
68     { NXT_LVLHSH_MAX_MEMALIGN_SHIFT, 4, 4, 4, 4, 0, 0, 0 }
69 
70 
71 typedef struct {
72     uint32_t                  bucket_end;
73     uint32_t                  bucket_size;
74     uint32_t                  bucket_mask;
75     uint8_t                   shift[8];
76 
77     nxt_lvlhsh_test_t         test;
78     nxt_lvlhsh_alloc_t        alloc;
79     nxt_lvlhsh_free_t         free;
80 } nxt_lvlhsh_proto_t;
81 
82 
83 typedef struct {
84     void                      *slot;
85 } nxt_lvlhsh_t;
86 
87 
88 struct nxt_lvlhsh_query_s {
89     uint32_t                  key_hash;
90     uint32_t                  replace;   /* 1 bit */
91     nxt_str_t                 key;
92     void                      *value;
93 
94     const nxt_lvlhsh_proto_t  *proto;
95     void                      *pool;
96 
97     /* Opaque data passed for the test function. */
98     void                      *data;
99 };
100 
101 
102 typedef struct {
103     const nxt_lvlhsh_proto_t  *proto;
104     /*
105      * Fields to store current bucket entry position.  They cannot be
106      * combined in a single bucket pointer with number of entries in low
107      * bits, because entry positions are not aligned.  A current level is
108      * stored as key bit path from the root.
109      */
110     uint32_t                  *bucket;
111     uint32_t                  current;
112     uint32_t                  entry;
113     uint32_t                  entries;
114 } nxt_lvlhsh_each_t;
115 
116 
117 #define                                                                       \
118 nxt_lvlhsh_is_empty(lh)                                                       \
119     ((lh)->slot == NULL)
120 
121 
122 #define                                                                       \
123 nxt_lvlhsh_init(lh)                                                           \
124     (lh)->slot = NULL
125 
126 /*
127  * nxt_lvlhsh_find() finds a hash element.  If the element has been
128  * found then it is stored in the lhq->value and nxt_lvlhsh_find()
129  * returns NXT_OK.  Otherwise NXT_DECLINED is returned.
130  *
131  * The required nxt_lvlhsh_query_t fields: key_hash, key, proto.
132  */
133 NXT_EXPORT nxt_int_t nxt_lvlhsh_find(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq);
134 
135 /*
136  * nxt_lvlhsh_insert() adds a hash element.  If the element already
137  * presents in lvlhsh and the lhq->replace flag is zero, then lhq->value
138  * is updated with the old element and NXT_DECLINED is returned.
139  * If the element already presents in lvlhsh and the lhq->replace flag
140  * is non-zero, then the old element is replaced with the new element.
141  * lhq->value is updated with the old element, and NXT_OK is returned.
142  * If the element is not present in lvlhsh, then it is inserted and
143  * NXT_OK is returned.  The lhq->value is not changed.
144  * On memory allocation failure NXT_ERROR is returned.
145  *
146  * The required nxt_lvlhsh_query_t fields: key_hash, key, proto, replace, value.
147  * The optional nxt_lvlhsh_query_t fields: pool.
148  */
149 NXT_EXPORT nxt_int_t nxt_lvlhsh_insert(nxt_lvlhsh_t *lh,
150     nxt_lvlhsh_query_t *lhq);
151 
152 /*
153  * nxt_lvlhsh_delete() deletes a hash element.  If the element has been
154  * found then it is removed from lvlhsh and is stored in the lhq->value,
155  * and NXT_OK is returned.  Otherwise NXT_DECLINED is returned.
156  *
157  * The required nxt_lvlhsh_query_t fields: key_hash, key, proto.
158  * The optional nxt_lvlhsh_query_t fields: pool.
159  */
160 NXT_EXPORT nxt_int_t nxt_lvlhsh_delete(nxt_lvlhsh_t *lh,
161     nxt_lvlhsh_query_t *lhq);
162 
163 /*
164  * nxt_lvlhsh_each_init() initializes iterator.
165  * It must be called before the first nxt_lvlhsh_each() call.
166  */
167 #define nxt_lvlhsh_each_init(lhe, _proto)                                     \
168     do {                                                                      \
169         (lhe)->proto = _proto;                                                \
170         (lhe)->bucket = NULL;                                                 \
171     } while (0)
172 
173 /*
174  * nxt_lvlhsh_each() iterates over a lvlhsh.
175  * It returns NULL if there is no more elements.
176  */
177 NXT_EXPORT void *nxt_lvlhsh_each(nxt_lvlhsh_t *lh, nxt_lvlhsh_each_t *lhe);
178 
179 /*
180  * nxt_lvlhsh_peek() is used to iterate over a lvlhsh during the lvlhsh
181  * destruction.  The returned hash element should be deleted from the lvlhsh,
182  * otherwise it will be returned again by the next nxt_lvlhsh_peek() call.
183  * The function returns NULL if there is no more elements in the lvlhsh.
184  */
185 NXT_EXPORT void *nxt_lvlhsh_peek(nxt_lvlhsh_t *lh,
186     const nxt_lvlhsh_proto_t *proto);
187 
188 /*
189  * nxt_lvlhsh_retrieve() is used to iterate over a lvlhsh during the lvlhsh
190  * destruction.  As opposed to nxt_lvlhsh_peek() the returned hash element
191  * is deleted from the lvlhsh.  The function returns NULL if there is no
192  * more elements in the lvlhsh.
193  */
194 NXT_EXPORT void *nxt_lvlhsh_retrieve(nxt_lvlhsh_t *lh,
195     const nxt_lvlhsh_proto_t *proto, void *pool);
196 
197 
198 NXT_EXPORT void *nxt_lvlhsh_alloc(void *data, size_t size);
199 NXT_EXPORT void nxt_lvlhsh_free(void *data, void *p);
200 
201 
202 #endif /* _NXT_LEVEL_HASH_H_INCLUDED_ */
203