1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
|
/*
* 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);
typedef void (*nxt_lvlhsh_free_t)(void *ctx, void *p);
#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];
nxt_lvlhsh_test_t test;
nxt_lvlhsh_alloc_t alloc;
nxt_lvlhsh_free_t free;
} nxt_lvlhsh_proto_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;
};
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;
#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);
/*
* nxt_lvlhsh_each_init() initializes iterator.
* It must be called before the first nxt_lvlhsh_each() call.
*/
#define nxt_lvlhsh_each_init(lhe, _proto) \
do { \
(lhe)->proto = _proto; \
(lhe)->bucket = NULL; \
} while (0)
/*
* nxt_lvlhsh_each() iterates over a lvlhsh.
* It returns NULL if there is no more elements.
*/
NXT_EXPORT void *nxt_lvlhsh_each(nxt_lvlhsh_t *lh, nxt_lvlhsh_each_t *lhe);
/*
* nxt_lvlhsh_peek() is used to iterate over a lvlhsh during the lvlhsh
* destruction. The returned hash element should be deleted from the lvlhsh,
* otherwise it will be returned again by the next nxt_lvlhsh_peek() call.
* The function returns NULL if there is no more elements in the lvlhsh.
*/
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);
#endif /* _NXT_LEVEL_HASH_H_INCLUDED_ */
|
