Line data Source code
1 : /**
2 : * @file napr_hash.c
3 : * @brief Implementation of the high-performance hash table.
4 : * @ingroup DataStructures
5 : */
6 : /*
7 : * Copyright (C) 2007 François Pesce : francois.pesce (at) gmail (dot) com
8 : *
9 : * Licensed under the Apache License, Version 2.0 (the "License");
10 : * you may not use this file except in compliance with the License.
11 : * You may obtain a copy of the License at
12 : *
13 : * http://www.apache.org/licenses/LICENSE-2.0
14 : *
15 : * Unless required by applicable law or agreed to in writing, software
16 : * distributed under the License is distributed on an "AS IS" BASIS,
17 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 : * See the License for the specific language governing permissions and
19 : * limitations under the License.
20 : */
21 :
22 : #include "debug.h"
23 : #include "napr_hash.h"
24 :
25 : #define XXH_STATIC_LINKING_ONLY
26 : #include "xxhash.h"
27 :
28 : #define hashsize(n) ((apr_size_t)1<<(n))
29 : #define hashmask(n) (hashsize(n)-1)
30 :
31 226 : static const void *str_get_key(const void *opaque)
32 : {
33 226 : return opaque;
34 : }
35 :
36 235 : static apr_size_t str_get_key_len(const void *opaque)
37 : {
38 235 : const char *str = opaque;
39 235 : return strlen(str);
40 : }
41 :
42 126 : static int str_key_cmp(const void *opaque1, const void *opaque2, apr_size_t len)
43 : {
44 126 : const char *str1 = opaque1;
45 126 : const char *str2 = opaque2;
46 :
47 126 : return memcmp(str1, str2, len);
48 : }
49 :
50 388 : static apr_uint32_t str_hash(register const void *opaque, register apr_size_t len)
51 : {
52 : /* Use XXH32 for string hashing - faster and more consistent with file hashing */
53 388 : return XXH32(opaque, len, 0x1337cafe);
54 : }
55 :
56 : struct napr_hash_index_t
57 : {
58 : napr_hash_t *hash;
59 : apr_size_t bucket;
60 : apr_size_t element; /* of a bucket */
61 : };
62 :
63 : struct napr_hash_t
64 : {
65 : /* void *table[size][ffactor] */
66 : void ***table;
67 : /* apr_size_t table[size] contain the number of element for each bucket */
68 : apr_size_t *filling_table;
69 : /* parent pool */
70 : apr_pool_t *pool;
71 : /* own pool that will be cleaned if a grow of the table occured */
72 : apr_pool_t *own_pool;
73 : /* Function to get the key from the datum */
74 : get_key_callback_fn_t *get_key;
75 : /* Function to get the key len from the datum */
76 : get_key_len_callback_fn_t *get_key_len;
77 : /* Function to compare two keys */
78 : key_cmp_callback_fn_t *key_cmp;
79 : /* hash function */
80 : hash_callback_fn_t *hash;
81 :
82 : /* the number of element contained in all the buckets of the table */
83 : apr_size_t nel;
84 : /* the number of buckets */
85 : apr_size_t size;
86 : /* desired density */
87 : apr_size_t ffactor;
88 : /* the binary mask to apply to the result of a hash function that return a
89 : * number < size */
90 : apr_uint32_t mask;
91 : /* size of the hash is hashsize(power) as mask is hashmask(power) */
92 : unsigned char power;
93 : };
94 :
95 23 : extern napr_hash_t *napr_hash_str_make(apr_pool_t *pool, apr_size_t nel, apr_size_t ffactor)
96 : {
97 23 : return napr_hash_make(pool, nel, ffactor, str_get_key, str_get_key_len, str_key_cmp, str_hash);
98 : }
99 :
100 67 : extern napr_hash_t *napr_hash_make(apr_pool_t *pool, apr_size_t nel, apr_size_t ffactor, get_key_callback_fn_t get_key,
101 : get_key_len_callback_fn_t get_key_len, key_cmp_callback_fn_t key_cmp,
102 : hash_callback_fn_t hash)
103 : {
104 : napr_hash_t *result;
105 : apr_status_t status;
106 :
107 67 : if (NULL == (result = apr_pcalloc(pool, sizeof(struct napr_hash_t)))) {
108 0 : DEBUG_ERR("allocation error");
109 0 : return NULL;
110 : }
111 :
112 633 : while (hashsize(result->power) < nel)
113 566 : result->power++;
114 :
115 67 : result->size = hashsize(result->power);
116 67 : result->mask = hashmask(result->power);
117 67 : result->ffactor = ffactor;
118 67 : result->get_key = get_key;
119 67 : result->get_key_len = get_key_len;
120 67 : result->key_cmp = key_cmp;
121 67 : result->hash = hash;
122 67 : result->pool = pool;
123 :
124 67 : if (APR_SUCCESS != (status = apr_pool_create(&(result->own_pool), pool))) {
125 : char errbuf[128];
126 0 : DEBUG_ERR("error calling apr_pool_create: %s", apr_strerror(status, errbuf, 128));
127 0 : return NULL;
128 : }
129 : /*DEBUG_DBG("readjusting size to %" APR_SIZE_T_FMT " to store %" APR_SIZE_T_FMT " elements", result->size, nel); */
130 : /*DEBUG_DBG("bit mask will be 0x%x", result->mask); */
131 :
132 67 : if (NULL == (result->table = apr_pcalloc(result->own_pool, result->size * sizeof(void **)))) {
133 0 : DEBUG_ERR("allocation error");
134 0 : return NULL;
135 : }
136 :
137 67 : if (NULL == (result->filling_table = apr_pcalloc(result->own_pool, result->size * sizeof(apr_size_t)))) {
138 0 : DEBUG_ERR("allocation error");
139 0 : return NULL;
140 : }
141 :
142 67 : return result;
143 : }
144 :
145 656 : extern void *napr_hash_search(napr_hash_t *hash, const void *key, apr_size_t key_len, apr_uint32_t *hash_value)
146 : {
147 : apr_uint32_t key_hash;
148 : apr_size_t i, nel, bucket;
149 :
150 656 : key_hash = hash->hash(key, key_len);
151 :
152 656 : if (NULL != hash_value)
153 459 : *hash_value = key_hash;
154 :
155 656 : bucket = key_hash & hash->mask;
156 656 : if (0 != (nel = hash->filling_table[bucket])) {
157 387 : for (i = 0; i < nel; i++) {
158 : /*DEBUG_DBG( "key[%p] bucket[%"APR_SIZE_T_FMT"][%"APR_SIZE_T_FMT"]=[%p]", key, bucket, i, hash->get_key(hash->table[bucket][i])); */
159 364 : if (key_len == hash->get_key_len(hash->table[bucket][i]))
160 355 : if (0 == (hash->key_cmp(key, hash->get_key(hash->table[bucket][i]), key_len)))
161 320 : return hash->table[bucket][i];
162 : }
163 : }
164 :
165 336 : return NULL;
166 : }
167 :
168 10 : static inline apr_status_t napr_hash_rebuild(napr_hash_t *hash)
169 : {
170 : napr_hash_t *tmp;
171 : apr_size_t i, j;
172 : apr_status_t status;
173 :
174 10 : if (NULL ==
175 : (tmp =
176 10 : napr_hash_make(hash->pool, hashsize(hash->power + 1), hash->ffactor, hash->get_key, hash->get_key_len,
177 : hash->key_cmp, hash->hash))) {
178 0 : DEBUG_ERR("error calling napr_hash_init");
179 0 : return APR_EGENERAL;
180 : }
181 :
182 1034 : for (i = 0; i < hash->size; i++) {
183 1114 : for (j = 0; j < hash->filling_table[i]; j++) {
184 : /*
185 : * no need to do doublon test here as we take data directly from a
186 : * hash table
187 : */
188 90 : if (APR_SUCCESS !=
189 : (status =
190 90 : napr_hash_set(tmp, hash->table[i][j],
191 90 : hash->hash(hash->get_key(hash->table[i][j]), hash->get_key_len(hash->table[i][j]))))) {
192 : char errbuf[128];
193 0 : DEBUG_ERR("error calling napr_hash_set: %s", apr_strerror(status, errbuf, 128));
194 0 : return status;
195 : }
196 : }
197 : }
198 10 : hash->table = tmp->table;
199 10 : hash->filling_table = tmp->filling_table;
200 10 : hash->nel = tmp->nel;
201 10 : hash->size = tmp->size;
202 10 : hash->mask = tmp->mask;
203 10 : hash->power = tmp->power;
204 10 : apr_pool_destroy(hash->own_pool);
205 10 : hash->own_pool = tmp->own_pool;
206 :
207 10 : return APR_SUCCESS;
208 : }
209 :
210 6 : extern void napr_hash_remove(napr_hash_t *hash, void *data, apr_uint32_t hash_value)
211 : {
212 : apr_size_t nel, bucket, i, key_len;
213 : const void *key;
214 :
215 6 : bucket = hash_value & hash->mask;
216 6 : key = hash->get_key(data);
217 6 : key_len = hash->get_key_len(data);
218 6 : if (0 != (nel = hash->filling_table[bucket])) {
219 8 : for (i = 0; i < nel; i++) {
220 : //DEBUG_DBG( "key[%.*s] bucket[%i]=[%.*s]", key_len, key, i, hash->get_key_len(hash->table[bucket][i]), hash->get_key(hash->table[bucket][i]));
221 8 : if (key_len == hash->get_key_len(hash->table[bucket][i]))
222 8 : if (0 == (hash->key_cmp(key, hash->get_key(hash->table[bucket][i]), key_len))) {
223 : /* Remove it, by replacing with the last element if present */
224 6 : if (i != nel - 1) {
225 2 : hash->table[bucket][i] = hash->table[bucket][nel - 1];
226 2 : hash->table[bucket][nel - 1] = NULL;
227 : }
228 : else {
229 4 : hash->table[bucket][i] = NULL;
230 : }
231 6 : hash->filling_table[bucket]--;
232 6 : hash->nel--;
233 6 : break;
234 : }
235 : }
236 : }
237 : else {
238 0 : DEBUG_DBG("try to remove something that is not here");
239 : }
240 6 : }
241 :
242 316 : extern apr_status_t napr_hash_set(napr_hash_t *hash, void *data, apr_uint32_t hash_value)
243 : {
244 : apr_size_t nel, bucket;
245 : apr_status_t status;
246 :
247 316 : bucket = hash_value & hash->mask;
248 :
249 316 : if ((0 == (nel = hash->filling_table[bucket])) && (NULL == hash->table[bucket])) {
250 293 : hash->table[bucket] = (void **) apr_pcalloc(hash->own_pool, hash->ffactor * sizeof(void *));
251 : }
252 : // DEBUG_DBG( "set data %.*s in bucket %u at nel %u", hash->datum_get_key_len(data), hash->datum_get_key(data), bucket, nel);
253 316 : hash->table[bucket][nel] = data;
254 316 : hash->filling_table[bucket]++;
255 316 : hash->nel++;
256 :
257 316 : if (hash->ffactor <= hash->filling_table[bucket]) {
258 : // int i;
259 : // DEBUG_DBG( "rebuilding hash table, because there's %u element in bucket %u ffactor is %u (total element = %u)",
260 : // hash->filling_table[bucket], bucket, hash->ffactor, hash->nel);
261 : // for(i = 0; i < hash->ffactor; i++) {
262 : // DEBUG_DBG( "%.*s", hash->datum_get_key_len(hash->table[bucket][i]), hash->datum_get_key(hash->table[bucket][i]));
263 : // }
264 :
265 10 : if (APR_SUCCESS != (status = napr_hash_rebuild(hash))) {
266 : char errbuf[128];
267 0 : DEBUG_ERR("error calling napr_hash_rebuild: %s", apr_strerror(status, errbuf, 128));
268 0 : return status;
269 : }
270 : }
271 :
272 316 : return APR_SUCCESS;
273 : }
274 :
275 1 : apr_pool_t *napr_hash_pool_get(const napr_hash_t *thehash)
276 : {
277 1 : return thehash->pool;
278 : }
279 :
280 24 : napr_hash_index_t *napr_hash_first(apr_pool_t *pool, napr_hash_t *hash)
281 : {
282 : napr_hash_index_t *hash_index;
283 24 : hash_index = apr_palloc(pool, sizeof(struct napr_hash_index_t));
284 24 : hash_index->hash = hash;
285 24 : hash_index->bucket = 0;
286 24 : hash_index->element = 0;
287 :
288 24 : if (hash->filling_table[0] > 0)
289 1 : return hash_index;
290 :
291 23 : return napr_hash_next(hash_index);
292 : }
293 :
294 93 : napr_hash_index_t *napr_hash_next(napr_hash_index_t *index)
295 : {
296 93 : if ((0 != index->hash->filling_table[index->bucket])
297 70 : && (index->element < (index->hash->filling_table[index->bucket] - 1))) {
298 4 : index->element++;
299 4 : return index;
300 : }
301 : else {
302 89 : index->element = 0;
303 90244 : for (index->bucket += 1; index->bucket < index->hash->size; index->bucket++) {
304 90220 : if (0 != index->hash->filling_table[index->bucket])
305 65 : break;
306 : }
307 89 : if (index->bucket < index->hash->size)
308 65 : return index;
309 : }
310 :
311 24 : return NULL;
312 : }
313 :
314 70 : void napr_hash_this(napr_hash_index_t *hi, const void **key, apr_size_t *klen, void **val)
315 : {
316 70 : if (key)
317 8 : *key = hi->hash->get_key(hi->hash->table[hi->bucket][hi->element]);
318 70 : if (klen)
319 8 : *klen = hi->hash->get_key_len(hi->hash->table[hi->bucket][hi->element]);
320 70 : if (val)
321 70 : *val = hi->hash->table[hi->bucket][hi->element];
322 70 : }
|
