1
2 /*
3 * Copyright (C) Igor Sysoev
4 * Copyright (C) NGINX, Inc.
5 */
6
7 #include <nxt_main.h>
8
9
10 /*
11 * The level hash consists of hierarchical levels of arrays of pointers.
12 * The pointers may point to another level, a bucket, or NULL.
13 * The levels and buckets must be allocated in manner alike posix_memalign()
14 * to bookkeep additional information in pointer low bits.
15 *
16 * A level is an array of pointers. Its size is a power of 2. Levels
17 * may be different sizes, but on the same level the sizes are the same.
18 * Level sizes are specified by number of bits per level in lvlhsh->shift
19 * array. A hash may have up to 7 levels. There are two predefined
20 * shift arrays given by the first two shift array values:
21 *
22 * 1) [0, 0]: [4, 4, 4, 4, 4, 4, 4] on a 64-bit platform or
23 * [5, 5, 5, 5, 5, 5, 0] on a 32-bit platform,
24 * so default size of levels is 128 bytes.
25 *
26 * 2) [0, 10]: [10, 4, 4, 4, 4, 4, 0] on a 64-bit platform or
27 * [10, 5, 5, 5, 5, 0, 0] on a 32-bit platform,
28 * so default size of levels is 128 bytes on all levels except
29 * the first level. The first level is 8K or 4K on 64-bit or 32-bit
30 * platforms respectively.
31 *
32 * All buckets in a hash are the same size which is a power of 2.
33 * A bucket contains several entries stored and tested sequentially.
34 * The bucket size should be one or two CPU cache line size, a minimum
35 * allowed size is 32 bytes. A default 128-byte bucket contains 10 64-bit
36 * entries or 15 32-bit entries. Each entry consists of pointer to value
37 * data and 32-bit key. If an entry value pointer is NULL, the entry is free.
38 * On a 64-bit platform entry value pointers are no aligned, therefore they
39 * are accessed as two 32-bit integers. The rest trailing space in a bucket
40 * is used as pointer to next bucket and this pointer is always aligned.
41 * Although the level hash allows to store a lot of values in a bucket chain,
42 * this is non optimal way. The large data set should be stored using
43 * several levels.
44 */
45
46 #define nxt_lvlhsh_is_bucket(p) \
47 ((uintptr_t) (p) & 1)
48
49
50 #define nxt_lvlhsh_count_inc(n) \
51 n = (void *) ((uintptr_t) (n) + 2)
52
53
54 #define nxt_lvlhsh_count_dec(n) \
55 n = (void *) ((uintptr_t) (n) - 2)
56
57
58 #define nxt_lvlhsh_level_size(proto, nlvl) \
59 ((uintptr_t) 1 << proto->shift[nlvl])
60
61
62 #define nxt_lvlhsh_level(lvl, mask) \
63 (void **) ((uintptr_t) lvl & (~mask << 2))
64
65
66 #define nxt_lvlhsh_level_entries(lvl, mask) \
67 ((uintptr_t) lvl & (mask << 1))
68
69
70 #define nxt_lvlhsh_store_bucket(slot, bkt) \
71 slot = (void **) ((uintptr_t) bkt | 2 | 1)
72
73
74 #define nxt_lvlhsh_bucket_size(proto) \
75 proto->bucket_size
76
77
78 #define nxt_lvlhsh_bucket(proto, bkt) \
79 (uint32_t *) ((uintptr_t) bkt & ~(uintptr_t) proto->bucket_mask)
80
81
82 #define nxt_lvlhsh_bucket_entries(proto, bkt) \
83 (((uintptr_t) bkt & (uintptr_t) proto->bucket_mask) >> 1)
84
85
86 #define nxt_lvlhsh_bucket_end(proto, bkt) \
87 &bkt[proto->bucket_end]
88
89
90 #define nxt_lvlhsh_free_entry(e) \
91 (!(nxt_lvlhsh_valid_entry(e)))
92
93
94 #define nxt_lvlhsh_next_bucket(proto, bkt) \
95 ((void **) &bkt[proto->bucket_end])
96
97 #if (NXT_64BIT)
98
99 #define nxt_lvlhsh_valid_entry(e) \
100 (((e)[0] | (e)[1]) != 0)
101
102
103 #define nxt_lvlhsh_entry_value(e) \
104 (void *) (((uintptr_t) (e)[1] << 32) + (e)[0])
105
106
107 #define nxt_lvlhsh_set_entry_value(e, n) \
108 (e)[0] = (uint32_t) (uintptr_t) n; \
109 (e)[1] = (uint32_t) ((uintptr_t) n >> 32)
110
111
112 #define nxt_lvlhsh_entry_key(e) \
113 (e)[2]
114
115
116 #define nxt_lvlhsh_set_entry_key(e, n) \
117 (e)[2] = n
118
119 #else
120
121 #define nxt_lvlhsh_valid_entry(e) \
122 ((e)[0] != 0)
123
124
125 #define nxt_lvlhsh_entry_value(e) \
126 (void *) (e)[0]
127
128
129 #define nxt_lvlhsh_set_entry_value(e, n) \
130 (e)[0] = (uint32_t) n
131
132
133 #define nxt_lvlhsh_entry_key(e) \
134 (e)[1]
135
136
137 #define nxt_lvlhsh_set_entry_key(e, n) \
138 (e)[1] = n
139
140 #endif
141
142
143 #define NXT_LVLHSH_BUCKET_DONE ((void *) -1)
144
145
146 typedef struct {
147 const nxt_lvlhsh_proto_t *proto;
148 void *pool;
149 uint32_t retrieve; /* 1 bit */
150 } nxt_lvlhsh_peek_t;
151
152
153 static nxt_int_t nxt_lvlhsh_level_find(nxt_lvlhsh_query_t *lhq, void **lvl,
154 uint32_t key, nxt_uint_t nlvl);
155 static nxt_int_t nxt_lvlhsh_bucket_find(nxt_lvlhsh_query_t *lhq, void **bkt);
156 static nxt_int_t nxt_lvlhsh_new_bucket(nxt_lvlhsh_query_t *lhq, void **slot);
157 static nxt_int_t nxt_lvlhsh_level_insert(nxt_lvlhsh_query_t *lhq,
158 void **slot, uint32_t key, nxt_uint_t nlvl);
159 static nxt_int_t nxt_lvlhsh_bucket_insert(nxt_lvlhsh_query_t *lhq,
160 void **slot, uint32_t key, nxt_int_t nlvl);
161 static nxt_int_t nxt_lvlhsh_convert_bucket_to_level(nxt_lvlhsh_query_t *lhq,
162 void **slot, nxt_uint_t nlvl, uint32_t *bucket);
163 static nxt_int_t nxt_lvlhsh_level_convertion_insert(nxt_lvlhsh_query_t *lhq,
164 void **parent, uint32_t key, nxt_uint_t nlvl);
165 static nxt_int_t nxt_lvlhsh_bucket_convertion_insert(nxt_lvlhsh_query_t *lhq,
166 void **slot, uint32_t key, nxt_int_t nlvl);
167 static nxt_int_t nxt_lvlhsh_free_level(nxt_lvlhsh_query_t *lhq, void **level,
168 nxt_uint_t size);
169 static nxt_int_t nxt_lvlhsh_level_delete(nxt_lvlhsh_query_t *lhq, void **slot,
170 uint32_t key, nxt_uint_t nlvl);
171 static nxt_int_t nxt_lvlhsh_bucket_delete(nxt_lvlhsh_query_t *lhq, void **bkt);
172 static void *nxt_lvlhsh_level_each(nxt_lvlhsh_each_t *lhe, void **level,
173 nxt_uint_t nlvl, nxt_uint_t shift);
174 static void *nxt_lvlhsh_bucket_each(nxt_lvlhsh_each_t *lhe);
175 static void *nxt_lvlhsh_level_peek(nxt_lvlhsh_peek_t *peek, void **level,
176 nxt_uint_t nlvl);
177 static void *nxt_lvlhsh_bucket_peek(nxt_lvlhsh_peek_t *peek, void **bkt);
178
179
180 nxt_int_t
nxt_lvlhsh_find(nxt_lvlhsh_t * lh,nxt_lvlhsh_query_t * lhq)181 nxt_lvlhsh_find(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq)
182 {
183 void *slot;
184
185 slot = lh->slot;
186
187 if (nxt_fast_path(slot != NULL)) {
188
189 if (nxt_lvlhsh_is_bucket(slot)) {
190 return nxt_lvlhsh_bucket_find(lhq, slot);
191 }
192
193 return nxt_lvlhsh_level_find(lhq, slot, lhq->key_hash, 0);
194 }
195
196 return NXT_DECLINED;
197 }
198
199
200 static nxt_int_t
nxt_lvlhsh_level_find(nxt_lvlhsh_query_t * lhq,void ** lvl,uint32_t key,nxt_uint_t nlvl)201 nxt_lvlhsh_level_find(nxt_lvlhsh_query_t *lhq, void **lvl, uint32_t key,
202 nxt_uint_t nlvl)
203 {
204 void **slot;
205 uintptr_t mask;
206 nxt_uint_t shift;
207
208 shift = lhq->proto->shift[nlvl];
209 mask = ((uintptr_t) 1 << shift) - 1;
210
211 lvl = nxt_lvlhsh_level(lvl, mask);
212 slot = lvl[key & mask];
213
214 if (slot != NULL) {
215
216 if (nxt_lvlhsh_is_bucket(slot)) {
217 return nxt_lvlhsh_bucket_find(lhq, slot);
218 }
219
220 return nxt_lvlhsh_level_find(lhq, slot, key >> shift, nlvl + 1);
221 }
222
223 return NXT_DECLINED;
224 }
225
226
227 static nxt_int_t
nxt_lvlhsh_bucket_find(nxt_lvlhsh_query_t * lhq,void ** bkt)228 nxt_lvlhsh_bucket_find(nxt_lvlhsh_query_t *lhq, void **bkt)
229 {
230 void *value;
231 uint32_t *bucket, *e;
232 nxt_uint_t n;
233
234 do {
235 bucket = nxt_lvlhsh_bucket(lhq->proto, bkt);
236 n = nxt_lvlhsh_bucket_entries(lhq->proto, bkt);
237 e = bucket;
238
239 do {
240 if (nxt_lvlhsh_valid_entry(e)) {
241 n--;
242
243 if (nxt_lvlhsh_entry_key(e) == lhq->key_hash) {
244
245 value = nxt_lvlhsh_entry_value(e);
246
247 if (lhq->proto->test(lhq, value) == NXT_OK) {
248 lhq->value = value;
249
250 return NXT_OK;
251 }
252 }
253 }
254
255 e += NXT_LVLHSH_ENTRY_SIZE;
256
257 } while (n != 0);
258
259 bkt = *nxt_lvlhsh_next_bucket(lhq->proto, bucket);
260
261 } while (bkt != NULL);
262
263 return NXT_DECLINED;
264 }
265
266
267 nxt_int_t
nxt_lvlhsh_insert(nxt_lvlhsh_t * lh,nxt_lvlhsh_query_t * lhq)268 nxt_lvlhsh_insert(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq)
269 {
270 uint32_t key;
271
272 if (nxt_fast_path(lh->slot != NULL)) {
273
274 key = lhq->key_hash;
275
276 if (nxt_lvlhsh_is_bucket(lh->slot)) {
277 return nxt_lvlhsh_bucket_insert(lhq, &lh->slot, key, -1);
278 }
279
280 return nxt_lvlhsh_level_insert(lhq, &lh->slot, key, 0);
281 }
282
283 return nxt_lvlhsh_new_bucket(lhq, &lh->slot);
284 }
285
286
287 static nxt_int_t
nxt_lvlhsh_new_bucket(nxt_lvlhsh_query_t * lhq,void ** slot)288 nxt_lvlhsh_new_bucket(nxt_lvlhsh_query_t *lhq, void **slot)
289 {
290 uint32_t *bucket;
291
292 bucket = lhq->proto->alloc(lhq->pool, nxt_lvlhsh_bucket_size(lhq->proto));
293
294 if (nxt_fast_path(bucket != NULL)) {
295
296 nxt_lvlhsh_set_entry_value(bucket, lhq->value);
297 nxt_lvlhsh_set_entry_key(bucket, lhq->key_hash);
298
299 *nxt_lvlhsh_next_bucket(lhq->proto, bucket) = NULL;
300
301 nxt_lvlhsh_store_bucket(*slot, bucket);
302
303 return NXT_OK;
304 }
305
306 return NXT_ERROR;
307 }
308
309
310 static nxt_int_t
nxt_lvlhsh_level_insert(nxt_lvlhsh_query_t * lhq,void ** parent,uint32_t key,nxt_uint_t nlvl)311 nxt_lvlhsh_level_insert(nxt_lvlhsh_query_t *lhq, void **parent, uint32_t key,
312 nxt_uint_t nlvl)
313 {
314 void **slot, **lvl;
315 nxt_int_t ret;
316 uintptr_t mask;
317 nxt_uint_t shift;
318
319 shift = lhq->proto->shift[nlvl];
320 mask = ((uintptr_t) 1 << shift) - 1;
321
322 lvl = nxt_lvlhsh_level(*parent, mask);
323 slot = &lvl[key & mask];
324
325 if (*slot != NULL) {
326 key >>= shift;
327
328 if (nxt_lvlhsh_is_bucket(*slot)) {
329 return nxt_lvlhsh_bucket_insert(lhq, slot, key, nlvl);
330 }
331
332 return nxt_lvlhsh_level_insert(lhq, slot, key, nlvl + 1);
333 }
334
335 ret = nxt_lvlhsh_new_bucket(lhq, slot);
336
337 if (nxt_fast_path(ret == NXT_OK)) {
338 nxt_lvlhsh_count_inc(*parent);
339 }
340
341 return ret;
342 }
343
344
345 static nxt_int_t
nxt_lvlhsh_bucket_insert(nxt_lvlhsh_query_t * lhq,void ** slot,uint32_t key,nxt_int_t nlvl)346 nxt_lvlhsh_bucket_insert(nxt_lvlhsh_query_t *lhq, void **slot, uint32_t key,
347 nxt_int_t nlvl)
348 {
349 void **bkt, **vacant_bucket, *value;
350 uint32_t *bucket, *e, *vacant_entry;
351 nxt_int_t ret;
352 uintptr_t n;
353 const void *new_value;
354 const nxt_lvlhsh_proto_t *proto;
355
356 bkt = slot;
357 vacant_entry = NULL;
358 vacant_bucket = NULL;
359 proto = lhq->proto;
360
361 /* Search for duplicate entry in bucket chain. */
362
363 do {
364 bucket = nxt_lvlhsh_bucket(proto, *bkt);
365 n = nxt_lvlhsh_bucket_entries(proto, *bkt);
366 e = bucket;
367
368 do {
369 if (nxt_lvlhsh_valid_entry(e)) {
370
371 if (nxt_lvlhsh_entry_key(e) == lhq->key_hash) {
372
373 value = nxt_lvlhsh_entry_value(e);
374
375 if (proto->test(lhq, value) == NXT_OK) {
376
377 new_value = lhq->value;
378 lhq->value = value;
379
380 if (lhq->replace) {
381 nxt_lvlhsh_set_entry_value(e, new_value);
382
383 return NXT_OK;
384 }
385
386 return NXT_DECLINED;
387 }
388 }
389
390 n--;
391
392 } else {
393 /*
394 * Save a hole vacant position in bucket
395 * and continue to search for duplicate entry.
396 */
397 if (vacant_entry == NULL) {
398 vacant_entry = e;
399 vacant_bucket = bkt;
400 }
401 }
402
403 e += NXT_LVLHSH_ENTRY_SIZE;
404
405 } while (n != 0);
406
407 if (e < nxt_lvlhsh_bucket_end(proto, bucket)) {
408 /*
409 * Save a vacant position on incomplete bucket's end
410 * and continue to search for duplicate entry.
411 */
412 if (vacant_entry == NULL) {
413 vacant_entry = e;
414 vacant_bucket = bkt;
415 }
416 }
417
418 bkt = nxt_lvlhsh_next_bucket(proto, bucket);
419
420 } while (*bkt != NULL);
421
422 if (vacant_entry != NULL) {
423 nxt_lvlhsh_set_entry_value(vacant_entry, lhq->value);
424 nxt_lvlhsh_set_entry_key(vacant_entry, lhq->key_hash);
425 nxt_lvlhsh_count_inc(*vacant_bucket);
426
427 return NXT_OK;
428 }
429
430 /* All buckets are full. */
431
432 nlvl++;
433
434 if (nxt_fast_path(proto->shift[nlvl] != 0)) {
435
436 ret = nxt_lvlhsh_convert_bucket_to_level(lhq, slot, nlvl, bucket);
437
438 if (nxt_fast_path(ret == NXT_OK)) {
439 return nxt_lvlhsh_level_insert(lhq, slot, key, nlvl);
440 }
441
442 return ret;
443 }
444
445 /* The last allowed level, only buckets may be allocated here. */
446
447 return nxt_lvlhsh_new_bucket(lhq, bkt);
448 }
449
450
451 static nxt_int_t
nxt_lvlhsh_convert_bucket_to_level(nxt_lvlhsh_query_t * lhq,void ** slot,nxt_uint_t nlvl,uint32_t * bucket)452 nxt_lvlhsh_convert_bucket_to_level(nxt_lvlhsh_query_t *lhq, void **slot,
453 nxt_uint_t nlvl, uint32_t *bucket)
454 {
455 void *lvl, **level;
456 uint32_t *e, *end, key;
457 nxt_int_t ret;
458 nxt_uint_t i, shift, size;
459 nxt_lvlhsh_query_t q;
460 const nxt_lvlhsh_proto_t *proto;
461
462 proto = lhq->proto;
463 size = nxt_lvlhsh_level_size(proto, nlvl);
464
465 lvl = proto->alloc(lhq->pool, size * (sizeof(void *)));
466
467 if (nxt_slow_path(lvl == NULL)) {
468 return NXT_ERROR;
469 }
470
471 nxt_memzero(lvl, size * (sizeof(void *)));
472
473 level = lvl;
474 shift = 0;
475
476 for (i = 0; i < nlvl; i++) {
477 /*
478 * Using SIMD operations in this trivial loop with maximum
479 * 8 iterations may increase code size by 170 bytes.
480 */
481 nxt_pragma_loop_disable_vectorization;
482
483 shift += proto->shift[i];
484 }
485
486 end = nxt_lvlhsh_bucket_end(proto, bucket);
487
488 for (e = bucket; e < end; e += NXT_LVLHSH_ENTRY_SIZE) {
489
490 q.proto = proto;
491 q.pool = lhq->pool;
492 q.value = nxt_lvlhsh_entry_value(e);
493 key = nxt_lvlhsh_entry_key(e);
494 q.key_hash = key;
495
496 ret = nxt_lvlhsh_level_convertion_insert(&q, &lvl, key >> shift, nlvl);
497
498 if (nxt_slow_path(ret != NXT_OK)) {
499 return nxt_lvlhsh_free_level(lhq, level, size);
500 }
501 }
502
503 *slot = lvl;
504
505 proto->free(lhq->pool, bucket);
506
507 return NXT_OK;
508 }
509
510
511 static nxt_int_t
nxt_lvlhsh_level_convertion_insert(nxt_lvlhsh_query_t * lhq,void ** parent,uint32_t key,nxt_uint_t nlvl)512 nxt_lvlhsh_level_convertion_insert(nxt_lvlhsh_query_t *lhq, void **parent,
513 uint32_t key, nxt_uint_t nlvl)
514 {
515 void **slot, **lvl;
516 nxt_int_t ret;
517 uintptr_t mask;
518 nxt_uint_t shift;
519
520 shift = lhq->proto->shift[nlvl];
521 mask = ((uintptr_t) 1 << shift) - 1;
522
523 lvl = nxt_lvlhsh_level(*parent, mask);
524 slot = &lvl[key & mask];
525
526 if (*slot == NULL) {
527 ret = nxt_lvlhsh_new_bucket(lhq, slot);
528
529 if (nxt_fast_path(ret == NXT_OK)) {
530 nxt_lvlhsh_count_inc(*parent);
531 }
532
533 return ret;
534 }
535
536 /* Only backets can be here. */
537
538 return nxt_lvlhsh_bucket_convertion_insert(lhq, slot, key >> shift, nlvl);
539 }
540
541
542 /*
543 * The special bucket insertion procedure is required because during
544 * convertion lhq->key contains garbage values and the test function
545 * cannot be called. Besides, the procedure can be simpler because
546 * a new entry is inserted just after occupied entries.
547 */
548
549 static nxt_int_t
nxt_lvlhsh_bucket_convertion_insert(nxt_lvlhsh_query_t * lhq,void ** slot,uint32_t key,nxt_int_t nlvl)550 nxt_lvlhsh_bucket_convertion_insert(nxt_lvlhsh_query_t *lhq, void **slot,
551 uint32_t key, nxt_int_t nlvl)
552 {
553 void **bkt;
554 uint32_t *bucket, *e;
555 nxt_int_t ret;
556 uintptr_t n;
557 const nxt_lvlhsh_proto_t *proto;
558
559 bkt = slot;
560 proto = lhq->proto;
561
562 do {
563 bucket = nxt_lvlhsh_bucket(proto, *bkt);
564 n = nxt_lvlhsh_bucket_entries(proto, *bkt);
565 e = bucket + n * NXT_LVLHSH_ENTRY_SIZE;
566
567 if (nxt_fast_path(e < nxt_lvlhsh_bucket_end(proto, bucket))) {
568
569 nxt_lvlhsh_set_entry_value(e, lhq->value);
570 nxt_lvlhsh_set_entry_key(e, lhq->key_hash);
571 nxt_lvlhsh_count_inc(*bkt);
572
573 return NXT_OK;
574 }
575
576 bkt = nxt_lvlhsh_next_bucket(proto, bucket);
577
578 } while (*bkt != NULL);
579
580 /* All buckets are full. */
581
582 nlvl++;
583
584 if (nxt_fast_path(proto->shift[nlvl] != 0)) {
585
586 ret = nxt_lvlhsh_convert_bucket_to_level(lhq, slot, nlvl, bucket);
587
588 if (nxt_fast_path(ret == NXT_OK)) {
589 return nxt_lvlhsh_level_insert(lhq, slot, key, nlvl);
590 }
591
592 return ret;
593 }
594
595 /* The last allowed level, only buckets may be allocated here. */
596
597 return nxt_lvlhsh_new_bucket(lhq, bkt);
598 }
599
600
601 static nxt_int_t
nxt_lvlhsh_free_level(nxt_lvlhsh_query_t * lhq,void ** level,nxt_uint_t size)602 nxt_lvlhsh_free_level(nxt_lvlhsh_query_t *lhq, void **level, nxt_uint_t size)
603 {
604 nxt_uint_t i;
605 const nxt_lvlhsh_proto_t *proto;
606
607 proto = lhq->proto;
608
609 for (i = 0; i < size; i++) {
610
611 if (level[i] != NULL) {
612 /*
613 * Chained buckets are not possible here, since even
614 * in the worst case one bucket cannot be converted
615 * in two chained buckets but remains the same bucket.
616 */
617 proto->free(lhq->pool, nxt_lvlhsh_bucket(proto, level[i]));
618 }
619 }
620
621 proto->free(lhq->pool, level);
622
623 return NXT_ERROR;
624 }
625
626
627 nxt_int_t
nxt_lvlhsh_delete(nxt_lvlhsh_t * lh,nxt_lvlhsh_query_t * lhq)628 nxt_lvlhsh_delete(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq)
629 {
630 if (nxt_fast_path(lh->slot != NULL)) {
631
632 if (nxt_lvlhsh_is_bucket(lh->slot)) {
633 return nxt_lvlhsh_bucket_delete(lhq, &lh->slot);
634 }
635
636 return nxt_lvlhsh_level_delete(lhq, &lh->slot, lhq->key_hash, 0);
637 }
638
639 return NXT_DECLINED;
640 }
641
642
643 static nxt_int_t
nxt_lvlhsh_level_delete(nxt_lvlhsh_query_t * lhq,void ** parent,uint32_t key,nxt_uint_t nlvl)644 nxt_lvlhsh_level_delete(nxt_lvlhsh_query_t *lhq, void **parent, uint32_t key,
645 nxt_uint_t nlvl)
646 {
647 void **slot, **lvl;
648 uintptr_t mask;
649 nxt_int_t ret;
650 nxt_uint_t shift;
651
652 shift = lhq->proto->shift[nlvl];
653 mask = ((uintptr_t) 1 << shift) - 1;
654
655 lvl = nxt_lvlhsh_level(*parent, mask);
656 slot = &lvl[key & mask];
657
658 if (*slot != NULL) {
659
660 if (nxt_lvlhsh_is_bucket(*slot)) {
661 ret = nxt_lvlhsh_bucket_delete(lhq, slot);
662
663 } else {
664 key >>= shift;
665 ret = nxt_lvlhsh_level_delete(lhq, slot, key, nlvl + 1);
666 }
667
668 if (*slot == NULL) {
669 nxt_lvlhsh_count_dec(*parent);
670
671 if (nxt_lvlhsh_level_entries(*parent, mask) == 0) {
672 *parent = NULL;
673 lhq->proto->free(lhq->pool, lvl);
674 }
675 }
676
677 return ret;
678 }
679
680 return NXT_DECLINED;
681 }
682
683
684 static nxt_int_t
nxt_lvlhsh_bucket_delete(nxt_lvlhsh_query_t * lhq,void ** bkt)685 nxt_lvlhsh_bucket_delete(nxt_lvlhsh_query_t *lhq, void **bkt)
686 {
687 void *value;
688 uint32_t *bucket, *e;
689 uintptr_t n;
690 const nxt_lvlhsh_proto_t *proto;
691
692 proto = lhq->proto;
693
694 do {
695 bucket = nxt_lvlhsh_bucket(proto, *bkt);
696 n = nxt_lvlhsh_bucket_entries(proto, *bkt);
697 e = bucket;
698
699 do {
700 if (nxt_lvlhsh_valid_entry(e)) {
701
702 if (nxt_lvlhsh_entry_key(e) == lhq->key_hash) {
703
704 value = nxt_lvlhsh_entry_value(e);
705
706 if (proto->test(lhq, value) == NXT_OK) {
707
708 if (nxt_lvlhsh_bucket_entries(proto, *bkt) == 1) {
709 *bkt = *nxt_lvlhsh_next_bucket(proto, bucket);
710 proto->free(lhq->pool, bucket);
711
712 } else {
713 nxt_lvlhsh_count_dec(*bkt);
714 nxt_lvlhsh_set_entry_value(e, NULL);
715 }
716
717 lhq->value = value;
718
719 return NXT_OK;
720 }
721 }
722
723 n--;
724 }
725
726 e += NXT_LVLHSH_ENTRY_SIZE;
727
728 } while (n != 0);
729
730 bkt = nxt_lvlhsh_next_bucket(proto, bucket);
731
732 } while (*bkt != NULL);
733
734 return NXT_DECLINED;
735 }
736
737
738 void *
nxt_lvlhsh_each(nxt_lvlhsh_t * lh,nxt_lvlhsh_each_t * lhe)739 nxt_lvlhsh_each(nxt_lvlhsh_t *lh, nxt_lvlhsh_each_t *lhe)
740 {
741 void **slot;
742
743 if (lhe->bucket == NXT_LVLHSH_BUCKET_DONE) {
744 slot = lh->slot;
745
746 if (nxt_lvlhsh_is_bucket(slot)) {
747 return NULL;
748 }
749
750 } else {
751 if (nxt_slow_path(lhe->bucket == NULL)) {
752
753 /* The first iteration only. */
754
755 slot = lh->slot;
756
757 if (slot == NULL) {
758 return NULL;
759 }
760
761 if (!nxt_lvlhsh_is_bucket(slot)) {
762 lhe->current = 0;
763 goto level;
764 }
765
766 lhe->bucket = nxt_lvlhsh_bucket(lhe->proto, slot);
767 lhe->entries = nxt_lvlhsh_bucket_entries(lhe->proto, slot);
768 lhe->entry = 0;
769 }
770
771 return nxt_lvlhsh_bucket_each(lhe);
772 }
773
774 level:
775
776 return nxt_lvlhsh_level_each(lhe, slot, 0, 0);
777 }
778
779
780 static void *
nxt_lvlhsh_level_each(nxt_lvlhsh_each_t * lhe,void ** level,nxt_uint_t nlvl,nxt_uint_t shift)781 nxt_lvlhsh_level_each(nxt_lvlhsh_each_t *lhe, void **level, nxt_uint_t nlvl,
782 nxt_uint_t shift)
783 {
784 void **slot, *value;
785 uintptr_t mask;
786 nxt_uint_t n, level_shift;
787
788 level_shift = lhe->proto->shift[nlvl];
789 mask = ((uintptr_t) 1 << level_shift) - 1;
790
791 level = nxt_lvlhsh_level(level, mask);
792
793 do {
794 n = (lhe->current >> shift) & mask;
795 slot = level[n];
796
797 if (slot != NULL) {
798 if (nxt_lvlhsh_is_bucket(slot)) {
799
800 if (lhe->bucket != NXT_LVLHSH_BUCKET_DONE) {
801
802 lhe->bucket = nxt_lvlhsh_bucket(lhe->proto, slot);
803 lhe->entries = nxt_lvlhsh_bucket_entries(lhe->proto, slot);
804 lhe->entry = 0;
805
806 return nxt_lvlhsh_bucket_each(lhe);
807 }
808
809 lhe->bucket = NULL;
810
811 } else {
812 value = nxt_lvlhsh_level_each(lhe, slot, nlvl + 1,
813 shift + level_shift);
814 if (value != NULL) {
815 return value;
816 }
817 }
818 }
819
820 lhe->current &= ~(mask << shift);
821 n = ((n + 1) & mask) << shift;
822 lhe->current |= n;
823
824 } while (n != 0);
825
826 return NULL;
827 }
828
829
830 static nxt_noinline void *
nxt_lvlhsh_bucket_each(nxt_lvlhsh_each_t * lhe)831 nxt_lvlhsh_bucket_each(nxt_lvlhsh_each_t *lhe)
832 {
833 void *value, **next;
834 uint32_t *bucket;
835
836 /* At least one valid entry must present here. */
837 do {
838 bucket = &lhe->bucket[lhe->entry];
839 lhe->entry += NXT_LVLHSH_ENTRY_SIZE;
840
841 } while (nxt_lvlhsh_free_entry(bucket));
842
843 value = nxt_lvlhsh_entry_value(bucket);
844
845 lhe->entries--;
846
847 if (lhe->entries == 0) {
848 next = *nxt_lvlhsh_next_bucket(lhe->proto, lhe->bucket);
849
850 lhe->bucket = (next == NULL) ? NXT_LVLHSH_BUCKET_DONE
851 : nxt_lvlhsh_bucket(lhe->proto, next);
852
853 lhe->entries = nxt_lvlhsh_bucket_entries(lhe->proto, next);
854 lhe->entry = 0;
855 }
856
857 return value;
858 }
859
860
861 void *
nxt_lvlhsh_peek(nxt_lvlhsh_t * lh,const nxt_lvlhsh_proto_t * proto)862 nxt_lvlhsh_peek(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto)
863 {
864 void **slot;
865 nxt_lvlhsh_peek_t peek;
866
867 slot = lh->slot;
868
869 if (slot != NULL) {
870
871 peek.proto = proto;
872 peek.retrieve = 0;
873
874 if (nxt_lvlhsh_is_bucket(slot)) {
875 return nxt_lvlhsh_bucket_peek(&peek, &lh->slot);
876 }
877
878 return nxt_lvlhsh_level_peek(&peek, &lh->slot, 0);
879 }
880
881 return NULL;
882 }
883
884
885 static void *
nxt_lvlhsh_level_peek(nxt_lvlhsh_peek_t * peek,void ** parent,nxt_uint_t nlvl)886 nxt_lvlhsh_level_peek(nxt_lvlhsh_peek_t *peek, void **parent, nxt_uint_t nlvl)
887 {
888 void **slot, **level, *value;
889 uintptr_t mask;
890 nxt_uint_t n, shift;
891
892 shift = peek->proto->shift[nlvl];
893 mask = ((uintptr_t) 1 << shift) - 1;
894
895 level = nxt_lvlhsh_level(*parent, mask);
896
897 n = 0;
898
899 /* At least one valid level slot must present here. */
900
901 for ( ;; ) {
902 slot = &level[n];
903
904 if (*slot != NULL) {
905
906 if (nxt_lvlhsh_is_bucket(*slot)) {
907 value = nxt_lvlhsh_bucket_peek(peek, slot);
908
909 } else {
910 value = nxt_lvlhsh_level_peek(peek, slot, nlvl + 1);
911 }
912
913 /*
914 * Checking peek->retrieve is not required here because
915 * there can not be empty slots during peeking.
916 */
917 if (*slot == NULL) {
918 nxt_lvlhsh_count_dec(*parent);
919
920 if (nxt_lvlhsh_level_entries(*parent, mask) == 0) {
921 *parent = NULL;
922 peek->proto->free(peek->pool, level);
923 }
924 }
925
926 return value;
927 }
928
929 n++;
930 }
931 }
932
933
934 static nxt_noinline void *
nxt_lvlhsh_bucket_peek(nxt_lvlhsh_peek_t * peek,void ** bkt)935 nxt_lvlhsh_bucket_peek(nxt_lvlhsh_peek_t *peek, void **bkt)
936 {
937 void *value;
938 uint32_t *bucket, *entry;
939 const nxt_lvlhsh_proto_t *proto;
940
941 bucket = nxt_lvlhsh_bucket(peek->proto, *bkt);
942
943 /* At least one valid entry must present here. */
944
945 for (entry = bucket;
946 nxt_lvlhsh_free_entry(entry);
947 entry += NXT_LVLHSH_ENTRY_SIZE)
948 {
949 /* void */
950 }
951
952 value = nxt_lvlhsh_entry_value(entry);
953
954 if (peek->retrieve) {
955 proto = peek->proto;
956
957 if (nxt_lvlhsh_bucket_entries(proto, *bkt) == 1) {
958 *bkt = *nxt_lvlhsh_next_bucket(proto, bucket);
959 proto->free(peek->pool, bucket);
960
961 } else {
962 nxt_lvlhsh_count_dec(*bkt);
963 nxt_lvlhsh_set_entry_value(entry, NULL);
964 }
965 }
966
967 return value;
968 }
969
970
971 void *
nxt_lvlhsh_retrieve(nxt_lvlhsh_t * lh,const nxt_lvlhsh_proto_t * proto,void * pool)972 nxt_lvlhsh_retrieve(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
973 void *pool)
974 {
975 void **slot;
976 nxt_lvlhsh_peek_t peek;
977
978 slot = lh->slot;
979
980 if (slot != NULL) {
981
982 peek.proto = proto;
983 peek.pool = pool;
984 peek.retrieve = 1;
985
986 if (nxt_lvlhsh_is_bucket(slot)) {
987 return nxt_lvlhsh_bucket_peek(&peek, &lh->slot);
988 }
989
990 return nxt_lvlhsh_level_peek(&peek, &lh->slot, 0);
991 }
992
993 return NULL;
994 }
995