xref: /unit/src/nxt_lvlhsh.h (revision 2084:7d479274f334)
10Sigor@sysoev.ru 
20Sigor@sysoev.ru /*
30Sigor@sysoev.ru  * Copyright (C) Igor Sysoev
40Sigor@sysoev.ru  * Copyright (C) NGINX, Inc.
50Sigor@sysoev.ru  */
60Sigor@sysoev.ru 
70Sigor@sysoev.ru #ifndef _NXT_LEVEL_HASH_H_INCLUDED_
80Sigor@sysoev.ru #define _NXT_LEVEL_HASH_H_INCLUDED_
90Sigor@sysoev.ru 
100Sigor@sysoev.ru 
110Sigor@sysoev.ru typedef struct nxt_lvlhsh_query_s  nxt_lvlhsh_query_t;
120Sigor@sysoev.ru 
130Sigor@sysoev.ru typedef nxt_int_t (*nxt_lvlhsh_test_t)(nxt_lvlhsh_query_t *lhq, void *data);
1465Sigor@sysoev.ru typedef void *(*nxt_lvlhsh_alloc_t)(void *ctx, size_t size);
1565Sigor@sysoev.ru typedef void (*nxt_lvlhsh_free_t)(void *ctx, void *p);
160Sigor@sysoev.ru 
170Sigor@sysoev.ru 
180Sigor@sysoev.ru #if (NXT_64BIT)
190Sigor@sysoev.ru 
200Sigor@sysoev.ru #define NXT_LVLHSH_DEFAULT_BUCKET_SIZE  128
210Sigor@sysoev.ru #define NXT_LVLHSH_ENTRY_SIZE           3
220Sigor@sysoev.ru #define NXT_LVLHSH_BATCH_ALLOC          16
230Sigor@sysoev.ru 
240Sigor@sysoev.ru /* 3 is shift of 64-bit pointer. */
250Sigor@sysoev.ru #define NXT_LVLHSH_MEMALIGN_SHIFT       (NXT_MAX_MEMALIGN_SHIFT - 3)
260Sigor@sysoev.ru 
270Sigor@sysoev.ru #else
280Sigor@sysoev.ru 
290Sigor@sysoev.ru #define NXT_LVLHSH_DEFAULT_BUCKET_SIZE  64
300Sigor@sysoev.ru #define NXT_LVLHSH_ENTRY_SIZE           2
310Sigor@sysoev.ru #define NXT_LVLHSH_BATCH_ALLOC          8
320Sigor@sysoev.ru 
330Sigor@sysoev.ru /* 2 is shift of 32-bit pointer. */
340Sigor@sysoev.ru #define NXT_LVLHSH_MEMALIGN_SHIFT       (NXT_MAX_MEMALIGN_SHIFT - 2)
350Sigor@sysoev.ru 
360Sigor@sysoev.ru #endif
370Sigor@sysoev.ru 
380Sigor@sysoev.ru 
390Sigor@sysoev.ru #if (NXT_LVLHSH_MEMALIGN_SHIFT < 10)
400Sigor@sysoev.ru #define NXT_LVLHSH_MAX_MEMALIGN_SHIFT   NXT_LVLHSH_MEMALIGN_SHIFT
410Sigor@sysoev.ru #else
420Sigor@sysoev.ru #define NXT_LVLHSH_MAX_MEMALIGN_SHIFT   10
430Sigor@sysoev.ru #endif
440Sigor@sysoev.ru 
450Sigor@sysoev.ru 
460Sigor@sysoev.ru #define NXT_LVLHSH_BUCKET_END(bucket_size)                                    \
470Sigor@sysoev.ru     (((bucket_size) - sizeof(void *))                                         \
480Sigor@sysoev.ru         / (NXT_LVLHSH_ENTRY_SIZE * sizeof(uint32_t))                          \
490Sigor@sysoev.ru      * NXT_LVLHSH_ENTRY_SIZE)
500Sigor@sysoev.ru 
510Sigor@sysoev.ru 
520Sigor@sysoev.ru #define NXT_LVLHSH_BUCKET_SIZE(bucket_size)                                   \
530Sigor@sysoev.ru     NXT_LVLHSH_BUCKET_END(bucket_size), bucket_size, (bucket_size - 1)
540Sigor@sysoev.ru 
550Sigor@sysoev.ru 
560Sigor@sysoev.ru #define NXT_LVLHSH_DEFAULT                                                    \
570Sigor@sysoev.ru     NXT_LVLHSH_BUCKET_SIZE(NXT_LVLHSH_DEFAULT_BUCKET_SIZE),                   \
580Sigor@sysoev.ru     { 4, 4, 4, 4, 4, 4, 4, 0 }
590Sigor@sysoev.ru 
600Sigor@sysoev.ru 
610Sigor@sysoev.ru #define NXT_LVLHSH_LARGE_SLAB                                                 \
620Sigor@sysoev.ru     NXT_LVLHSH_BUCKET_SIZE(NXT_LVLHSH_DEFAULT_BUCKET_SIZE),                   \
630Sigor@sysoev.ru     { 10, 4, 4, 4, 4, 4, 4, 0 }
640Sigor@sysoev.ru 
650Sigor@sysoev.ru 
660Sigor@sysoev.ru #define NXT_LVLHSH_LARGE_MEMALIGN                                             \
670Sigor@sysoev.ru     NXT_LVLHSH_BUCKET_SIZE(NXT_LVLHSH_DEFAULT_BUCKET_SIZE),                   \
680Sigor@sysoev.ru     { NXT_LVLHSH_MAX_MEMALIGN_SHIFT, 4, 4, 4, 4, 0, 0, 0 }
690Sigor@sysoev.ru 
700Sigor@sysoev.ru 
710Sigor@sysoev.ru typedef struct {
720Sigor@sysoev.ru     uint32_t                  bucket_end;
730Sigor@sysoev.ru     uint32_t                  bucket_size;
740Sigor@sysoev.ru     uint32_t                  bucket_mask;
750Sigor@sysoev.ru     uint8_t                   shift[8];
760Sigor@sysoev.ru 
770Sigor@sysoev.ru     nxt_lvlhsh_test_t         test;
780Sigor@sysoev.ru     nxt_lvlhsh_alloc_t        alloc;
790Sigor@sysoev.ru     nxt_lvlhsh_free_t         free;
800Sigor@sysoev.ru } nxt_lvlhsh_proto_t;
810Sigor@sysoev.ru 
820Sigor@sysoev.ru 
830Sigor@sysoev.ru typedef struct {
840Sigor@sysoev.ru     void                      *slot;
850Sigor@sysoev.ru } nxt_lvlhsh_t;
860Sigor@sysoev.ru 
870Sigor@sysoev.ru 
880Sigor@sysoev.ru struct nxt_lvlhsh_query_s {
890Sigor@sysoev.ru     uint32_t                  key_hash;
900Sigor@sysoev.ru     uint32_t                  replace;   /* 1 bit */
910Sigor@sysoev.ru     nxt_str_t                 key;
920Sigor@sysoev.ru     void                      *value;
930Sigor@sysoev.ru 
940Sigor@sysoev.ru     const nxt_lvlhsh_proto_t  *proto;
950Sigor@sysoev.ru     void                      *pool;
960Sigor@sysoev.ru 
970Sigor@sysoev.ru     /* Opaque data passed for the test function. */
980Sigor@sysoev.ru     void                      *data;
990Sigor@sysoev.ru };
1000Sigor@sysoev.ru 
1010Sigor@sysoev.ru 
102598Sigor@sysoev.ru typedef struct {
103598Sigor@sysoev.ru     const nxt_lvlhsh_proto_t  *proto;
104598Sigor@sysoev.ru     /*
105598Sigor@sysoev.ru      * Fields to store current bucket entry position.  They cannot be
106598Sigor@sysoev.ru      * combined in a single bucket pointer with number of entries in low
107598Sigor@sysoev.ru      * bits, because entry positions are not aligned.  A current level is
108598Sigor@sysoev.ru      * stored as key bit path from the root.
109598Sigor@sysoev.ru      */
110598Sigor@sysoev.ru     uint32_t                  *bucket;
111598Sigor@sysoev.ru     uint32_t                  current;
112598Sigor@sysoev.ru     uint32_t                  entry;
113598Sigor@sysoev.ru     uint32_t                  entries;
114598Sigor@sysoev.ru } nxt_lvlhsh_each_t;
115598Sigor@sysoev.ru 
116598Sigor@sysoev.ru 
117*2084Salx.manpages@gmail.com #define nxt_lvlhsh_is_empty(lh)                                               \
1180Sigor@sysoev.ru     ((lh)->slot == NULL)
1190Sigor@sysoev.ru 
1200Sigor@sysoev.ru 
121*2084Salx.manpages@gmail.com #define nxt_lvlhsh_init(lh)                                                   \
1220Sigor@sysoev.ru     (lh)->slot = NULL
1230Sigor@sysoev.ru 
1240Sigor@sysoev.ru /*
1250Sigor@sysoev.ru  * nxt_lvlhsh_find() finds a hash element.  If the element has been
1260Sigor@sysoev.ru  * found then it is stored in the lhq->value and nxt_lvlhsh_find()
1270Sigor@sysoev.ru  * returns NXT_OK.  Otherwise NXT_DECLINED is returned.
1280Sigor@sysoev.ru  *
1290Sigor@sysoev.ru  * The required nxt_lvlhsh_query_t fields: key_hash, key, proto.
1300Sigor@sysoev.ru  */
1310Sigor@sysoev.ru NXT_EXPORT nxt_int_t nxt_lvlhsh_find(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq);
1320Sigor@sysoev.ru 
1330Sigor@sysoev.ru /*
1340Sigor@sysoev.ru  * nxt_lvlhsh_insert() adds a hash element.  If the element already
1350Sigor@sysoev.ru  * presents in lvlhsh and the lhq->replace flag is zero, then lhq->value
1360Sigor@sysoev.ru  * is updated with the old element and NXT_DECLINED is returned.
1370Sigor@sysoev.ru  * If the element already presents in lvlhsh and the lhq->replace flag
1380Sigor@sysoev.ru  * is non-zero, then the old element is replaced with the new element.
1390Sigor@sysoev.ru  * lhq->value is updated with the old element, and NXT_OK is returned.
1400Sigor@sysoev.ru  * If the element is not present in lvlhsh, then it is inserted and
1410Sigor@sysoev.ru  * NXT_OK is returned.  The lhq->value is not changed.
1420Sigor@sysoev.ru  * On memory allocation failure NXT_ERROR is returned.
1430Sigor@sysoev.ru  *
1440Sigor@sysoev.ru  * The required nxt_lvlhsh_query_t fields: key_hash, key, proto, replace, value.
1450Sigor@sysoev.ru  * The optional nxt_lvlhsh_query_t fields: pool.
1460Sigor@sysoev.ru  */
1470Sigor@sysoev.ru NXT_EXPORT nxt_int_t nxt_lvlhsh_insert(nxt_lvlhsh_t *lh,
1480Sigor@sysoev.ru     nxt_lvlhsh_query_t *lhq);
1490Sigor@sysoev.ru 
1500Sigor@sysoev.ru /*
1510Sigor@sysoev.ru  * nxt_lvlhsh_delete() deletes a hash element.  If the element has been
1520Sigor@sysoev.ru  * found then it is removed from lvlhsh and is stored in the lhq->value,
1530Sigor@sysoev.ru  * and NXT_OK is returned.  Otherwise NXT_DECLINED is returned.
1540Sigor@sysoev.ru  *
1550Sigor@sysoev.ru  * The required nxt_lvlhsh_query_t fields: key_hash, key, proto.
1560Sigor@sysoev.ru  * The optional nxt_lvlhsh_query_t fields: pool.
1570Sigor@sysoev.ru  */
1580Sigor@sysoev.ru NXT_EXPORT nxt_int_t nxt_lvlhsh_delete(nxt_lvlhsh_t *lh,
1590Sigor@sysoev.ru     nxt_lvlhsh_query_t *lhq);
1600Sigor@sysoev.ru 
161598Sigor@sysoev.ru /*
162598Sigor@sysoev.ru  * nxt_lvlhsh_each_init() initializes iterator.
163598Sigor@sysoev.ru  * It must be called before the first nxt_lvlhsh_each() call.
164598Sigor@sysoev.ru  */
165598Sigor@sysoev.ru #define nxt_lvlhsh_each_init(lhe, _proto)                                     \
166598Sigor@sysoev.ru     do {                                                                      \
167598Sigor@sysoev.ru         (lhe)->proto = _proto;                                                \
168598Sigor@sysoev.ru         (lhe)->bucket = NULL;                                                 \
169598Sigor@sysoev.ru     } while (0)
1700Sigor@sysoev.ru 
171598Sigor@sysoev.ru /*
172598Sigor@sysoev.ru  * nxt_lvlhsh_each() iterates over a lvlhsh.
173598Sigor@sysoev.ru  * It returns NULL if there is no more elements.
174598Sigor@sysoev.ru  */
175598Sigor@sysoev.ru NXT_EXPORT void *nxt_lvlhsh_each(nxt_lvlhsh_t *lh, nxt_lvlhsh_each_t *lhe);
1760Sigor@sysoev.ru 
177594Sigor@sysoev.ru /*
178594Sigor@sysoev.ru  * nxt_lvlhsh_peek() is used to iterate over a lvlhsh during the lvlhsh
179594Sigor@sysoev.ru  * destruction.  The returned hash element should be deleted from the lvlhsh,
180594Sigor@sysoev.ru  * otherwise it will be returned again by the next nxt_lvlhsh_peek() call.
181594Sigor@sysoev.ru  * The function returns NULL if there is no more elements in the lvlhsh.
182594Sigor@sysoev.ru  */
183594Sigor@sysoev.ru NXT_EXPORT void *nxt_lvlhsh_peek(nxt_lvlhsh_t *lh,
184594Sigor@sysoev.ru     const nxt_lvlhsh_proto_t *proto);
185594Sigor@sysoev.ru 
186595Sigor@sysoev.ru /*
187595Sigor@sysoev.ru  * nxt_lvlhsh_retrieve() is used to iterate over a lvlhsh during the lvlhsh
188595Sigor@sysoev.ru  * destruction.  As opposed to nxt_lvlhsh_peek() the returned hash element
189595Sigor@sysoev.ru  * is deleted from the lvlhsh.  The function returns NULL if there is no
190595Sigor@sysoev.ru  * more elements in the lvlhsh.
191595Sigor@sysoev.ru  */
192595Sigor@sysoev.ru NXT_EXPORT void *nxt_lvlhsh_retrieve(nxt_lvlhsh_t *lh,
193595Sigor@sysoev.ru     const nxt_lvlhsh_proto_t *proto, void *pool);
194595Sigor@sysoev.ru 
1950Sigor@sysoev.ru 
19665Sigor@sysoev.ru NXT_EXPORT void *nxt_lvlhsh_alloc(void *data, size_t size);
19765Sigor@sysoev.ru NXT_EXPORT void nxt_lvlhsh_free(void *data, void *p);
1980Sigor@sysoev.ru 
1990Sigor@sysoev.ru 
2000Sigor@sysoev.ru #endif /* _NXT_LEVEL_HASH_H_INCLUDED_ */
201