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 #include <nxt_main.h> 80Sigor@sysoev.ru 90Sigor@sysoev.ru 100Sigor@sysoev.ru /* 110Sigor@sysoev.ru * The level hash consists of hierarchical levels of arrays of pointers. 120Sigor@sysoev.ru * The pointers may point to another level, a bucket, or NULL. 130Sigor@sysoev.ru * The levels and buckets must be allocated in manner alike posix_memalign() 140Sigor@sysoev.ru * to bookkeep additional information in pointer low bits. 150Sigor@sysoev.ru * 160Sigor@sysoev.ru * A level is an array of pointers. Its size is a power of 2. Levels 170Sigor@sysoev.ru * may be different sizes, but on the same level the sizes are the same. 180Sigor@sysoev.ru * Level sizes are specified by number of bits per level in lvlhsh->shift 190Sigor@sysoev.ru * array. A hash may have up to 7 levels. There are two predefined 200Sigor@sysoev.ru * shift arrays given by the first two shift array values: 210Sigor@sysoev.ru * 220Sigor@sysoev.ru * 1) [0, 0]: [4, 4, 4, 4, 4, 4, 4] on a 64-bit platform or 230Sigor@sysoev.ru * [5, 5, 5, 5, 5, 5, 0] on a 32-bit platform, 240Sigor@sysoev.ru * so default size of levels is 128 bytes. 250Sigor@sysoev.ru * 260Sigor@sysoev.ru * 2) [0, 10]: [10, 4, 4, 4, 4, 4, 0] on a 64-bit platform or 270Sigor@sysoev.ru * [10, 5, 5, 5, 5, 0, 0] on a 32-bit platform, 280Sigor@sysoev.ru * so default size of levels is 128 bytes on all levels except 290Sigor@sysoev.ru * the first level. The first level is 8K or 4K on 64-bit or 32-bit 300Sigor@sysoev.ru * platforms respectively. 310Sigor@sysoev.ru * 320Sigor@sysoev.ru * All buckets in a hash are the same size which is a power of 2. 330Sigor@sysoev.ru * A bucket contains several entries stored and tested sequentially. 340Sigor@sysoev.ru * The bucket size should be one or two CPU cache line size, a minimum 350Sigor@sysoev.ru * allowed size is 32 bytes. A default 128-byte bucket contains 10 64-bit 360Sigor@sysoev.ru * entries or 15 32-bit entries. Each entry consists of pointer to value 370Sigor@sysoev.ru * data and 32-bit key. If an entry value pointer is NULL, the entry is free. 380Sigor@sysoev.ru * On a 64-bit platform entry value pointers are no aligned, therefore they 390Sigor@sysoev.ru * are accessed as two 32-bit integers. The rest trailing space in a bucket 400Sigor@sysoev.ru * is used as pointer to next bucket and this pointer is always aligned. 410Sigor@sysoev.ru * Although the level hash allows to store a lot of values in a bucket chain, 420Sigor@sysoev.ru * this is non optimal way. The large data set should be stored using 430Sigor@sysoev.ru * several levels. 440Sigor@sysoev.ru */ 450Sigor@sysoev.ru 460Sigor@sysoev.ru #define \ 470Sigor@sysoev.ru nxt_lvlhsh_is_bucket(p) \ 480Sigor@sysoev.ru ((uintptr_t) (p) & 1) 490Sigor@sysoev.ru 500Sigor@sysoev.ru 510Sigor@sysoev.ru #define \ 520Sigor@sysoev.ru nxt_lvlhsh_count_inc(n) \ 530Sigor@sysoev.ru n = (void *) ((uintptr_t) (n) + 2) 540Sigor@sysoev.ru 550Sigor@sysoev.ru 560Sigor@sysoev.ru #define \ 570Sigor@sysoev.ru nxt_lvlhsh_count_dec(n) \ 580Sigor@sysoev.ru n = (void *) ((uintptr_t) (n) - 2) 590Sigor@sysoev.ru 600Sigor@sysoev.ru 610Sigor@sysoev.ru #define \ 620Sigor@sysoev.ru nxt_lvlhsh_level_size(proto, nlvl) \ 630Sigor@sysoev.ru ((uintptr_t) 1 << proto->shift[nlvl]) 640Sigor@sysoev.ru 650Sigor@sysoev.ru 660Sigor@sysoev.ru #define \ 670Sigor@sysoev.ru nxt_lvlhsh_level(lvl, mask) \ 680Sigor@sysoev.ru (void **) ((uintptr_t) lvl & (~mask << 2)) 690Sigor@sysoev.ru 700Sigor@sysoev.ru 710Sigor@sysoev.ru #define \ 720Sigor@sysoev.ru nxt_lvlhsh_level_entries(lvl, mask) \ 730Sigor@sysoev.ru ((uintptr_t) lvl & (mask << 1)) 740Sigor@sysoev.ru 750Sigor@sysoev.ru 760Sigor@sysoev.ru #define \ 770Sigor@sysoev.ru nxt_lvlhsh_store_bucket(slot, bkt) \ 780Sigor@sysoev.ru slot = (void **) ((uintptr_t) bkt | 2 | 1) 790Sigor@sysoev.ru 800Sigor@sysoev.ru 810Sigor@sysoev.ru #define \ 820Sigor@sysoev.ru nxt_lvlhsh_bucket_size(proto) \ 830Sigor@sysoev.ru proto->bucket_size 840Sigor@sysoev.ru 850Sigor@sysoev.ru 860Sigor@sysoev.ru #define \ 870Sigor@sysoev.ru nxt_lvlhsh_bucket(proto, bkt) \ 880Sigor@sysoev.ru (uint32_t *) ((uintptr_t) bkt & ~(uintptr_t) proto->bucket_mask) 890Sigor@sysoev.ru 900Sigor@sysoev.ru 910Sigor@sysoev.ru #define \ 920Sigor@sysoev.ru nxt_lvlhsh_bucket_entries(proto, bkt) \ 930Sigor@sysoev.ru (((uintptr_t) bkt & (uintptr_t) proto->bucket_mask) >> 1) 940Sigor@sysoev.ru 950Sigor@sysoev.ru 960Sigor@sysoev.ru #define \ 970Sigor@sysoev.ru nxt_lvlhsh_bucket_end(proto, bkt) \ 980Sigor@sysoev.ru &bkt[proto->bucket_end] 990Sigor@sysoev.ru 1000Sigor@sysoev.ru 1010Sigor@sysoev.ru #define \ 1020Sigor@sysoev.ru nxt_lvlhsh_free_entry(e) \ 1030Sigor@sysoev.ru (!(nxt_lvlhsh_valid_entry(e))) 1040Sigor@sysoev.ru 1050Sigor@sysoev.ru 1060Sigor@sysoev.ru #define \ 1070Sigor@sysoev.ru nxt_lvlhsh_next_bucket(proto, bkt) \ 1080Sigor@sysoev.ru ((void **) &bkt[proto->bucket_end]) 1090Sigor@sysoev.ru 1100Sigor@sysoev.ru #if (NXT_64BIT) 1110Sigor@sysoev.ru 1120Sigor@sysoev.ru #define \ 1130Sigor@sysoev.ru nxt_lvlhsh_valid_entry(e) \ 1140Sigor@sysoev.ru (((e)[0] | (e)[1]) != 0) 1150Sigor@sysoev.ru 1160Sigor@sysoev.ru 1170Sigor@sysoev.ru #define \ 1180Sigor@sysoev.ru nxt_lvlhsh_entry_value(e) \ 1190Sigor@sysoev.ru (void *) (((uintptr_t) (e)[1] << 32) + (e)[0]) 1200Sigor@sysoev.ru 1210Sigor@sysoev.ru 1220Sigor@sysoev.ru #define \ 1230Sigor@sysoev.ru nxt_lvlhsh_set_entry_value(e, n) \ 1240Sigor@sysoev.ru (e)[0] = (uint32_t) (uintptr_t) n; \ 1250Sigor@sysoev.ru (e)[1] = (uint32_t) ((uintptr_t) n >> 32) 1260Sigor@sysoev.ru 1270Sigor@sysoev.ru 1280Sigor@sysoev.ru #define \ 1290Sigor@sysoev.ru nxt_lvlhsh_entry_key(e) \ 1300Sigor@sysoev.ru (e)[2] 1310Sigor@sysoev.ru 1320Sigor@sysoev.ru 1330Sigor@sysoev.ru #define \ 1340Sigor@sysoev.ru nxt_lvlhsh_set_entry_key(e, n) \ 1350Sigor@sysoev.ru (e)[2] = n 1360Sigor@sysoev.ru 1370Sigor@sysoev.ru #else 1380Sigor@sysoev.ru 1390Sigor@sysoev.ru #define \ 1400Sigor@sysoev.ru nxt_lvlhsh_valid_entry(e) \ 1410Sigor@sysoev.ru ((e)[0] != 0) 1420Sigor@sysoev.ru 1430Sigor@sysoev.ru 1440Sigor@sysoev.ru #define \ 1450Sigor@sysoev.ru nxt_lvlhsh_entry_value(e) \ 1460Sigor@sysoev.ru (void *) (e)[0] 1470Sigor@sysoev.ru 1480Sigor@sysoev.ru 1490Sigor@sysoev.ru #define \ 1500Sigor@sysoev.ru nxt_lvlhsh_set_entry_value(e, n) \ 1510Sigor@sysoev.ru (e)[0] = (uint32_t) n 1520Sigor@sysoev.ru 1530Sigor@sysoev.ru 1540Sigor@sysoev.ru #define \ 1550Sigor@sysoev.ru nxt_lvlhsh_entry_key(e) \ 1560Sigor@sysoev.ru (e)[1] 1570Sigor@sysoev.ru 1580Sigor@sysoev.ru 1590Sigor@sysoev.ru #define \ 1600Sigor@sysoev.ru nxt_lvlhsh_set_entry_key(e, n) \ 1610Sigor@sysoev.ru (e)[1] = n 1620Sigor@sysoev.ru 1630Sigor@sysoev.ru #endif 1640Sigor@sysoev.ru 1650Sigor@sysoev.ru 1660Sigor@sysoev.ru #define NXT_LVLHSH_BUCKET_DONE ((void *) -1) 1670Sigor@sysoev.ru 1680Sigor@sysoev.ru 169595Sigor@sysoev.ru typedef struct { 170595Sigor@sysoev.ru const nxt_lvlhsh_proto_t *proto; 171595Sigor@sysoev.ru void *pool; 172595Sigor@sysoev.ru uint32_t retrieve; /* 1 bit */ 173595Sigor@sysoev.ru } nxt_lvlhsh_peek_t; 174595Sigor@sysoev.ru 175595Sigor@sysoev.ru 1760Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_level_find(nxt_lvlhsh_query_t *lhq, void **lvl, 1770Sigor@sysoev.ru uint32_t key, nxt_uint_t nlvl); 1780Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_bucket_find(nxt_lvlhsh_query_t *lhq, void **bkt); 1790Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_new_bucket(nxt_lvlhsh_query_t *lhq, void **slot); 1800Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_level_insert(nxt_lvlhsh_query_t *lhq, 1810Sigor@sysoev.ru void **slot, uint32_t key, nxt_uint_t nlvl); 1820Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_bucket_insert(nxt_lvlhsh_query_t *lhq, 1830Sigor@sysoev.ru void **slot, uint32_t key, nxt_int_t nlvl); 1840Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_convert_bucket_to_level(nxt_lvlhsh_query_t *lhq, 1850Sigor@sysoev.ru void **slot, nxt_uint_t nlvl, uint32_t *bucket); 1860Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_level_convertion_insert(nxt_lvlhsh_query_t *lhq, 1870Sigor@sysoev.ru void **parent, uint32_t key, nxt_uint_t nlvl); 1880Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_bucket_convertion_insert(nxt_lvlhsh_query_t *lhq, 1890Sigor@sysoev.ru void **slot, uint32_t key, nxt_int_t nlvl); 1900Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_free_level(nxt_lvlhsh_query_t *lhq, void **level, 1910Sigor@sysoev.ru nxt_uint_t size); 1920Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_level_delete(nxt_lvlhsh_query_t *lhq, void **slot, 1930Sigor@sysoev.ru uint32_t key, nxt_uint_t nlvl); 1940Sigor@sysoev.ru static nxt_int_t nxt_lvlhsh_bucket_delete(nxt_lvlhsh_query_t *lhq, void **bkt); 1950Sigor@sysoev.ru static void *nxt_lvlhsh_level_each(nxt_lvlhsh_each_t *lhe, void **level, 1960Sigor@sysoev.ru nxt_uint_t nlvl, nxt_uint_t shift); 1970Sigor@sysoev.ru static void *nxt_lvlhsh_bucket_each(nxt_lvlhsh_each_t *lhe); 198595Sigor@sysoev.ru static void *nxt_lvlhsh_level_peek(nxt_lvlhsh_peek_t *peek, void **level, 199595Sigor@sysoev.ru nxt_uint_t nlvl); 200595Sigor@sysoev.ru static void *nxt_lvlhsh_bucket_peek(nxt_lvlhsh_peek_t *peek, void **bkt); 2010Sigor@sysoev.ru 2020Sigor@sysoev.ru 2030Sigor@sysoev.ru nxt_int_t 2040Sigor@sysoev.ru nxt_lvlhsh_find(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq) 2050Sigor@sysoev.ru { 2060Sigor@sysoev.ru void *slot; 2070Sigor@sysoev.ru 2080Sigor@sysoev.ru slot = lh->slot; 2090Sigor@sysoev.ru 2100Sigor@sysoev.ru if (nxt_fast_path(slot != NULL)) { 2110Sigor@sysoev.ru 2120Sigor@sysoev.ru if (nxt_lvlhsh_is_bucket(slot)) { 2130Sigor@sysoev.ru return nxt_lvlhsh_bucket_find(lhq, slot); 2140Sigor@sysoev.ru } 2150Sigor@sysoev.ru 2160Sigor@sysoev.ru return nxt_lvlhsh_level_find(lhq, slot, lhq->key_hash, 0); 2170Sigor@sysoev.ru } 2180Sigor@sysoev.ru 2190Sigor@sysoev.ru return NXT_DECLINED; 2200Sigor@sysoev.ru } 2210Sigor@sysoev.ru 2220Sigor@sysoev.ru 2230Sigor@sysoev.ru static nxt_int_t 2240Sigor@sysoev.ru nxt_lvlhsh_level_find(nxt_lvlhsh_query_t *lhq, void **lvl, uint32_t key, 2250Sigor@sysoev.ru nxt_uint_t nlvl) 2260Sigor@sysoev.ru { 2270Sigor@sysoev.ru void **slot; 2280Sigor@sysoev.ru uintptr_t mask; 2290Sigor@sysoev.ru nxt_uint_t shift; 2300Sigor@sysoev.ru 2310Sigor@sysoev.ru shift = lhq->proto->shift[nlvl]; 2320Sigor@sysoev.ru mask = ((uintptr_t) 1 << shift) - 1; 2330Sigor@sysoev.ru 2340Sigor@sysoev.ru lvl = nxt_lvlhsh_level(lvl, mask); 2350Sigor@sysoev.ru slot = lvl[key & mask]; 2360Sigor@sysoev.ru 2370Sigor@sysoev.ru if (slot != NULL) { 2380Sigor@sysoev.ru 2390Sigor@sysoev.ru if (nxt_lvlhsh_is_bucket(slot)) { 2400Sigor@sysoev.ru return nxt_lvlhsh_bucket_find(lhq, slot); 2410Sigor@sysoev.ru } 2420Sigor@sysoev.ru 2430Sigor@sysoev.ru return nxt_lvlhsh_level_find(lhq, slot, key >> shift, nlvl + 1); 2440Sigor@sysoev.ru } 2450Sigor@sysoev.ru 2460Sigor@sysoev.ru return NXT_DECLINED; 2470Sigor@sysoev.ru } 2480Sigor@sysoev.ru 2490Sigor@sysoev.ru 2500Sigor@sysoev.ru static nxt_int_t 2510Sigor@sysoev.ru nxt_lvlhsh_bucket_find(nxt_lvlhsh_query_t *lhq, void **bkt) 2520Sigor@sysoev.ru { 2530Sigor@sysoev.ru void *value; 2540Sigor@sysoev.ru uint32_t *bucket, *e; 2550Sigor@sysoev.ru nxt_uint_t n; 2560Sigor@sysoev.ru 2570Sigor@sysoev.ru do { 2580Sigor@sysoev.ru bucket = nxt_lvlhsh_bucket(lhq->proto, bkt); 2590Sigor@sysoev.ru n = nxt_lvlhsh_bucket_entries(lhq->proto, bkt); 2600Sigor@sysoev.ru e = bucket; 2610Sigor@sysoev.ru 2620Sigor@sysoev.ru do { 2630Sigor@sysoev.ru if (nxt_lvlhsh_valid_entry(e)) { 2640Sigor@sysoev.ru n--; 2650Sigor@sysoev.ru 2660Sigor@sysoev.ru if (nxt_lvlhsh_entry_key(e) == lhq->key_hash) { 2670Sigor@sysoev.ru 2680Sigor@sysoev.ru value = nxt_lvlhsh_entry_value(e); 2690Sigor@sysoev.ru 2700Sigor@sysoev.ru if (lhq->proto->test(lhq, value) == NXT_OK) { 2710Sigor@sysoev.ru lhq->value = value; 2720Sigor@sysoev.ru 2730Sigor@sysoev.ru return NXT_OK; 2740Sigor@sysoev.ru } 2750Sigor@sysoev.ru } 2760Sigor@sysoev.ru } 2770Sigor@sysoev.ru 2780Sigor@sysoev.ru e += NXT_LVLHSH_ENTRY_SIZE; 2790Sigor@sysoev.ru 2800Sigor@sysoev.ru } while (n != 0); 2810Sigor@sysoev.ru 2820Sigor@sysoev.ru bkt = *nxt_lvlhsh_next_bucket(lhq->proto, bucket); 2830Sigor@sysoev.ru 2840Sigor@sysoev.ru } while (bkt != NULL); 2850Sigor@sysoev.ru 2860Sigor@sysoev.ru return NXT_DECLINED; 2870Sigor@sysoev.ru } 2880Sigor@sysoev.ru 2890Sigor@sysoev.ru 2900Sigor@sysoev.ru nxt_int_t 2910Sigor@sysoev.ru nxt_lvlhsh_insert(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq) 2920Sigor@sysoev.ru { 2930Sigor@sysoev.ru uint32_t key; 2940Sigor@sysoev.ru 2950Sigor@sysoev.ru if (nxt_fast_path(lh->slot != NULL)) { 2960Sigor@sysoev.ru 2970Sigor@sysoev.ru key = lhq->key_hash; 2980Sigor@sysoev.ru 2990Sigor@sysoev.ru if (nxt_lvlhsh_is_bucket(lh->slot)) { 3000Sigor@sysoev.ru return nxt_lvlhsh_bucket_insert(lhq, &lh->slot, key, -1); 3010Sigor@sysoev.ru } 3020Sigor@sysoev.ru 3030Sigor@sysoev.ru return nxt_lvlhsh_level_insert(lhq, &lh->slot, key, 0); 3040Sigor@sysoev.ru } 3050Sigor@sysoev.ru 3060Sigor@sysoev.ru return nxt_lvlhsh_new_bucket(lhq, &lh->slot); 3070Sigor@sysoev.ru } 3080Sigor@sysoev.ru 3090Sigor@sysoev.ru 3100Sigor@sysoev.ru static nxt_int_t 3110Sigor@sysoev.ru nxt_lvlhsh_new_bucket(nxt_lvlhsh_query_t *lhq, void **slot) 3120Sigor@sysoev.ru { 3130Sigor@sysoev.ru uint32_t *bucket; 3140Sigor@sysoev.ru 31565Sigor@sysoev.ru bucket = lhq->proto->alloc(lhq->pool, nxt_lvlhsh_bucket_size(lhq->proto)); 3160Sigor@sysoev.ru 3170Sigor@sysoev.ru if (nxt_fast_path(bucket != NULL)) { 3180Sigor@sysoev.ru 3190Sigor@sysoev.ru nxt_lvlhsh_set_entry_value(bucket, lhq->value); 3200Sigor@sysoev.ru nxt_lvlhsh_set_entry_key(bucket, lhq->key_hash); 3210Sigor@sysoev.ru 3220Sigor@sysoev.ru *nxt_lvlhsh_next_bucket(lhq->proto, bucket) = NULL; 3230Sigor@sysoev.ru 3240Sigor@sysoev.ru nxt_lvlhsh_store_bucket(*slot, bucket); 3250Sigor@sysoev.ru 3260Sigor@sysoev.ru return NXT_OK; 3270Sigor@sysoev.ru } 3280Sigor@sysoev.ru 3290Sigor@sysoev.ru return NXT_ERROR; 3300Sigor@sysoev.ru } 3310Sigor@sysoev.ru 3320Sigor@sysoev.ru 3330Sigor@sysoev.ru static nxt_int_t 3340Sigor@sysoev.ru nxt_lvlhsh_level_insert(nxt_lvlhsh_query_t *lhq, void **parent, uint32_t key, 3350Sigor@sysoev.ru nxt_uint_t nlvl) 3360Sigor@sysoev.ru { 3370Sigor@sysoev.ru void **slot, **lvl; 3380Sigor@sysoev.ru nxt_int_t ret; 3390Sigor@sysoev.ru uintptr_t mask; 3400Sigor@sysoev.ru nxt_uint_t shift; 3410Sigor@sysoev.ru 3420Sigor@sysoev.ru shift = lhq->proto->shift[nlvl]; 3430Sigor@sysoev.ru mask = ((uintptr_t) 1 << shift) - 1; 3440Sigor@sysoev.ru 3450Sigor@sysoev.ru lvl = nxt_lvlhsh_level(*parent, mask); 3460Sigor@sysoev.ru slot = &lvl[key & mask]; 3470Sigor@sysoev.ru 3480Sigor@sysoev.ru if (*slot != NULL) { 3490Sigor@sysoev.ru key >>= shift; 3500Sigor@sysoev.ru 3510Sigor@sysoev.ru if (nxt_lvlhsh_is_bucket(*slot)) { 3520Sigor@sysoev.ru return nxt_lvlhsh_bucket_insert(lhq, slot, key, nlvl); 3530Sigor@sysoev.ru } 3540Sigor@sysoev.ru 3550Sigor@sysoev.ru return nxt_lvlhsh_level_insert(lhq, slot, key, nlvl + 1); 3560Sigor@sysoev.ru } 3570Sigor@sysoev.ru 3580Sigor@sysoev.ru ret = nxt_lvlhsh_new_bucket(lhq, slot); 3590Sigor@sysoev.ru 3600Sigor@sysoev.ru if (nxt_fast_path(ret == NXT_OK)) { 3610Sigor@sysoev.ru nxt_lvlhsh_count_inc(*parent); 3620Sigor@sysoev.ru } 3630Sigor@sysoev.ru 3640Sigor@sysoev.ru return ret; 3650Sigor@sysoev.ru } 3660Sigor@sysoev.ru 3670Sigor@sysoev.ru 3680Sigor@sysoev.ru static nxt_int_t 3690Sigor@sysoev.ru nxt_lvlhsh_bucket_insert(nxt_lvlhsh_query_t *lhq, void **slot, uint32_t key, 3700Sigor@sysoev.ru nxt_int_t nlvl) 3710Sigor@sysoev.ru { 3720Sigor@sysoev.ru void **bkt, **vacant_bucket, *value; 3730Sigor@sysoev.ru uint32_t *bucket, *e, *vacant_entry; 3740Sigor@sysoev.ru nxt_int_t ret; 3750Sigor@sysoev.ru uintptr_t n; 3760Sigor@sysoev.ru const void *new_value; 3770Sigor@sysoev.ru const nxt_lvlhsh_proto_t *proto; 3780Sigor@sysoev.ru 3790Sigor@sysoev.ru bkt = slot; 3800Sigor@sysoev.ru vacant_entry = NULL; 3810Sigor@sysoev.ru vacant_bucket = NULL; 3820Sigor@sysoev.ru proto = lhq->proto; 3830Sigor@sysoev.ru 3840Sigor@sysoev.ru /* Search for duplicate entry in bucket chain. */ 3850Sigor@sysoev.ru 3860Sigor@sysoev.ru do { 3870Sigor@sysoev.ru bucket = nxt_lvlhsh_bucket(proto, *bkt); 3880Sigor@sysoev.ru n = nxt_lvlhsh_bucket_entries(proto, *bkt); 3890Sigor@sysoev.ru e = bucket; 3900Sigor@sysoev.ru 3910Sigor@sysoev.ru do { 3920Sigor@sysoev.ru if (nxt_lvlhsh_valid_entry(e)) { 3930Sigor@sysoev.ru 3940Sigor@sysoev.ru if (nxt_lvlhsh_entry_key(e) == lhq->key_hash) { 3950Sigor@sysoev.ru 3960Sigor@sysoev.ru value = nxt_lvlhsh_entry_value(e); 3970Sigor@sysoev.ru 3980Sigor@sysoev.ru if (proto->test(lhq, value) == NXT_OK) { 3990Sigor@sysoev.ru 4000Sigor@sysoev.ru new_value = lhq->value; 4010Sigor@sysoev.ru lhq->value = value; 4020Sigor@sysoev.ru 4030Sigor@sysoev.ru if (lhq->replace) { 4040Sigor@sysoev.ru nxt_lvlhsh_set_entry_value(e, new_value); 4050Sigor@sysoev.ru 4060Sigor@sysoev.ru return NXT_OK; 4070Sigor@sysoev.ru } 4080Sigor@sysoev.ru 4090Sigor@sysoev.ru return NXT_DECLINED; 4100Sigor@sysoev.ru } 4110Sigor@sysoev.ru } 4120Sigor@sysoev.ru 4130Sigor@sysoev.ru n--; 4140Sigor@sysoev.ru 4150Sigor@sysoev.ru } else { 4160Sigor@sysoev.ru /* 4170Sigor@sysoev.ru * Save a hole vacant position in bucket 4180Sigor@sysoev.ru * and continue to search for duplicate entry. 4190Sigor@sysoev.ru */ 4200Sigor@sysoev.ru if (vacant_entry == NULL) { 4210Sigor@sysoev.ru vacant_entry = e; 4220Sigor@sysoev.ru vacant_bucket = bkt; 4230Sigor@sysoev.ru } 4240Sigor@sysoev.ru } 4250Sigor@sysoev.ru 4260Sigor@sysoev.ru e += NXT_LVLHSH_ENTRY_SIZE; 4270Sigor@sysoev.ru 4280Sigor@sysoev.ru } while (n != 0); 4290Sigor@sysoev.ru 4300Sigor@sysoev.ru if (e < nxt_lvlhsh_bucket_end(proto, bucket)) { 4310Sigor@sysoev.ru /* 4320Sigor@sysoev.ru * Save a vacant position on incomplete bucket's end 4330Sigor@sysoev.ru * and continue to search for duplicate entry. 4340Sigor@sysoev.ru */ 4350Sigor@sysoev.ru if (vacant_entry == NULL) { 4360Sigor@sysoev.ru vacant_entry = e; 4370Sigor@sysoev.ru vacant_bucket = bkt; 4380Sigor@sysoev.ru } 4390Sigor@sysoev.ru } 4400Sigor@sysoev.ru 4410Sigor@sysoev.ru bkt = nxt_lvlhsh_next_bucket(proto, bucket); 4420Sigor@sysoev.ru 4430Sigor@sysoev.ru } while (*bkt != NULL); 4440Sigor@sysoev.ru 4450Sigor@sysoev.ru if (vacant_entry != NULL) { 4460Sigor@sysoev.ru nxt_lvlhsh_set_entry_value(vacant_entry, lhq->value); 4470Sigor@sysoev.ru nxt_lvlhsh_set_entry_key(vacant_entry, lhq->key_hash); 4480Sigor@sysoev.ru nxt_lvlhsh_count_inc(*vacant_bucket); 4490Sigor@sysoev.ru 4500Sigor@sysoev.ru return NXT_OK; 4510Sigor@sysoev.ru } 4520Sigor@sysoev.ru 4530Sigor@sysoev.ru /* All buckets are full. */ 4540Sigor@sysoev.ru 4550Sigor@sysoev.ru nlvl++; 4560Sigor@sysoev.ru 4570Sigor@sysoev.ru if (nxt_fast_path(proto->shift[nlvl] != 0)) { 4580Sigor@sysoev.ru 4590Sigor@sysoev.ru ret = nxt_lvlhsh_convert_bucket_to_level(lhq, slot, nlvl, bucket); 4600Sigor@sysoev.ru 4610Sigor@sysoev.ru if (nxt_fast_path(ret == NXT_OK)) { 4620Sigor@sysoev.ru return nxt_lvlhsh_level_insert(lhq, slot, key, nlvl); 4630Sigor@sysoev.ru } 4640Sigor@sysoev.ru 4650Sigor@sysoev.ru return ret; 4660Sigor@sysoev.ru } 4670Sigor@sysoev.ru 4680Sigor@sysoev.ru /* The last allowed level, only buckets may be allocated here. */ 4690Sigor@sysoev.ru 4700Sigor@sysoev.ru return nxt_lvlhsh_new_bucket(lhq, bkt); 4710Sigor@sysoev.ru } 4720Sigor@sysoev.ru 4730Sigor@sysoev.ru 4740Sigor@sysoev.ru static nxt_int_t 4750Sigor@sysoev.ru nxt_lvlhsh_convert_bucket_to_level(nxt_lvlhsh_query_t *lhq, void **slot, 4760Sigor@sysoev.ru nxt_uint_t nlvl, uint32_t *bucket) 4770Sigor@sysoev.ru { 4780Sigor@sysoev.ru void *lvl, **level; 4790Sigor@sysoev.ru uint32_t *e, *end, key; 4800Sigor@sysoev.ru nxt_int_t ret; 4810Sigor@sysoev.ru nxt_uint_t i, shift, size; 4820Sigor@sysoev.ru nxt_lvlhsh_query_t q; 4830Sigor@sysoev.ru const nxt_lvlhsh_proto_t *proto; 4840Sigor@sysoev.ru 4850Sigor@sysoev.ru proto = lhq->proto; 4860Sigor@sysoev.ru size = nxt_lvlhsh_level_size(proto, nlvl); 4870Sigor@sysoev.ru 48865Sigor@sysoev.ru lvl = proto->alloc(lhq->pool, size * (sizeof(void *))); 4890Sigor@sysoev.ru 4900Sigor@sysoev.ru if (nxt_slow_path(lvl == NULL)) { 4910Sigor@sysoev.ru return NXT_ERROR; 4920Sigor@sysoev.ru } 4930Sigor@sysoev.ru 4940Sigor@sysoev.ru nxt_memzero(lvl, size * (sizeof(void *))); 4950Sigor@sysoev.ru 4960Sigor@sysoev.ru level = lvl; 4970Sigor@sysoev.ru shift = 0; 4980Sigor@sysoev.ru 4990Sigor@sysoev.ru for (i = 0; i < nlvl; i++) { 5000Sigor@sysoev.ru /* 5010Sigor@sysoev.ru * Using SIMD operations in this trivial loop with maximum 5020Sigor@sysoev.ru * 8 iterations may increase code size by 170 bytes. 5030Sigor@sysoev.ru */ 5040Sigor@sysoev.ru nxt_pragma_loop_disable_vectorization; 5050Sigor@sysoev.ru 5060Sigor@sysoev.ru shift += proto->shift[i]; 5070Sigor@sysoev.ru } 5080Sigor@sysoev.ru 5090Sigor@sysoev.ru end = nxt_lvlhsh_bucket_end(proto, bucket); 5100Sigor@sysoev.ru 5110Sigor@sysoev.ru for (e = bucket; e < end; e += NXT_LVLHSH_ENTRY_SIZE) { 5120Sigor@sysoev.ru 5130Sigor@sysoev.ru q.proto = proto; 5140Sigor@sysoev.ru q.pool = lhq->pool; 5150Sigor@sysoev.ru q.value = nxt_lvlhsh_entry_value(e); 5160Sigor@sysoev.ru key = nxt_lvlhsh_entry_key(e); 5170Sigor@sysoev.ru q.key_hash = key; 5180Sigor@sysoev.ru 5190Sigor@sysoev.ru ret = nxt_lvlhsh_level_convertion_insert(&q, &lvl, key >> shift, nlvl); 5200Sigor@sysoev.ru 5210Sigor@sysoev.ru if (nxt_slow_path(ret != NXT_OK)) { 5220Sigor@sysoev.ru return nxt_lvlhsh_free_level(lhq, level, size); 5230Sigor@sysoev.ru } 5240Sigor@sysoev.ru } 5250Sigor@sysoev.ru 5260Sigor@sysoev.ru *slot = lvl; 5270Sigor@sysoev.ru 52865Sigor@sysoev.ru proto->free(lhq->pool, bucket); 5290Sigor@sysoev.ru 5300Sigor@sysoev.ru return NXT_OK; 5310Sigor@sysoev.ru } 5320Sigor@sysoev.ru 5330Sigor@sysoev.ru 5340Sigor@sysoev.ru static nxt_int_t 5350Sigor@sysoev.ru nxt_lvlhsh_level_convertion_insert(nxt_lvlhsh_query_t *lhq, void **parent, 5360Sigor@sysoev.ru uint32_t key, nxt_uint_t nlvl) 5370Sigor@sysoev.ru { 5380Sigor@sysoev.ru void **slot, **lvl; 5390Sigor@sysoev.ru nxt_int_t ret; 5400Sigor@sysoev.ru uintptr_t mask; 5410Sigor@sysoev.ru nxt_uint_t shift; 5420Sigor@sysoev.ru 5430Sigor@sysoev.ru shift = lhq->proto->shift[nlvl]; 5440Sigor@sysoev.ru mask = ((uintptr_t) 1 << shift) - 1; 5450Sigor@sysoev.ru 5460Sigor@sysoev.ru lvl = nxt_lvlhsh_level(*parent, mask); 5470Sigor@sysoev.ru slot = &lvl[key & mask]; 5480Sigor@sysoev.ru 5490Sigor@sysoev.ru if (*slot == NULL) { 5500Sigor@sysoev.ru ret = nxt_lvlhsh_new_bucket(lhq, slot); 5510Sigor@sysoev.ru 5520Sigor@sysoev.ru if (nxt_fast_path(ret == NXT_OK)) { 5530Sigor@sysoev.ru nxt_lvlhsh_count_inc(*parent); 5540Sigor@sysoev.ru } 5550Sigor@sysoev.ru 5560Sigor@sysoev.ru return ret; 5570Sigor@sysoev.ru } 5580Sigor@sysoev.ru 5590Sigor@sysoev.ru /* Only backets can be here. */ 5600Sigor@sysoev.ru 5610Sigor@sysoev.ru return nxt_lvlhsh_bucket_convertion_insert(lhq, slot, key >> shift, nlvl); 5620Sigor@sysoev.ru } 5630Sigor@sysoev.ru 5640Sigor@sysoev.ru 5650Sigor@sysoev.ru /* 5660Sigor@sysoev.ru * The special bucket insertion procedure is required because during 5670Sigor@sysoev.ru * convertion lhq->key contains garbage values and the test function 5680Sigor@sysoev.ru * cannot be called. Besides, the procedure can be simpler because 5690Sigor@sysoev.ru * a new entry is inserted just after occupied entries. 5700Sigor@sysoev.ru */ 5710Sigor@sysoev.ru 5720Sigor@sysoev.ru static nxt_int_t 5730Sigor@sysoev.ru nxt_lvlhsh_bucket_convertion_insert(nxt_lvlhsh_query_t *lhq, void **slot, 5740Sigor@sysoev.ru uint32_t key, nxt_int_t nlvl) 5750Sigor@sysoev.ru { 5760Sigor@sysoev.ru void **bkt; 5770Sigor@sysoev.ru uint32_t *bucket, *e; 5780Sigor@sysoev.ru nxt_int_t ret; 5790Sigor@sysoev.ru uintptr_t n; 5800Sigor@sysoev.ru const nxt_lvlhsh_proto_t *proto; 5810Sigor@sysoev.ru 5820Sigor@sysoev.ru bkt = slot; 5830Sigor@sysoev.ru proto = lhq->proto; 5840Sigor@sysoev.ru 5850Sigor@sysoev.ru do { 5860Sigor@sysoev.ru bucket = nxt_lvlhsh_bucket(proto, *bkt); 5870Sigor@sysoev.ru n = nxt_lvlhsh_bucket_entries(proto, *bkt); 5880Sigor@sysoev.ru e = bucket + n * NXT_LVLHSH_ENTRY_SIZE; 5890Sigor@sysoev.ru 5900Sigor@sysoev.ru if (nxt_fast_path(e < nxt_lvlhsh_bucket_end(proto, bucket))) { 5910Sigor@sysoev.ru 5920Sigor@sysoev.ru nxt_lvlhsh_set_entry_value(e, lhq->value); 5930Sigor@sysoev.ru nxt_lvlhsh_set_entry_key(e, lhq->key_hash); 5940Sigor@sysoev.ru nxt_lvlhsh_count_inc(*bkt); 5950Sigor@sysoev.ru 5960Sigor@sysoev.ru return NXT_OK; 5970Sigor@sysoev.ru } 5980Sigor@sysoev.ru 5990Sigor@sysoev.ru bkt = nxt_lvlhsh_next_bucket(proto, bucket); 6000Sigor@sysoev.ru 6010Sigor@sysoev.ru } while (*bkt != NULL); 6020Sigor@sysoev.ru 6030Sigor@sysoev.ru /* All buckets are full. */ 6040Sigor@sysoev.ru 6050Sigor@sysoev.ru nlvl++; 6060Sigor@sysoev.ru 6070Sigor@sysoev.ru if (nxt_fast_path(proto->shift[nlvl] != 0)) { 6080Sigor@sysoev.ru 6090Sigor@sysoev.ru ret = nxt_lvlhsh_convert_bucket_to_level(lhq, slot, nlvl, bucket); 6100Sigor@sysoev.ru 6110Sigor@sysoev.ru if (nxt_fast_path(ret == NXT_OK)) { 6120Sigor@sysoev.ru return nxt_lvlhsh_level_insert(lhq, slot, key, nlvl); 6130Sigor@sysoev.ru } 6140Sigor@sysoev.ru 6150Sigor@sysoev.ru return ret; 6160Sigor@sysoev.ru } 6170Sigor@sysoev.ru 6180Sigor@sysoev.ru /* The last allowed level, only buckets may be allocated here. */ 6190Sigor@sysoev.ru 6200Sigor@sysoev.ru return nxt_lvlhsh_new_bucket(lhq, bkt); 6210Sigor@sysoev.ru } 6220Sigor@sysoev.ru 6230Sigor@sysoev.ru 6240Sigor@sysoev.ru static nxt_int_t 6250Sigor@sysoev.ru nxt_lvlhsh_free_level(nxt_lvlhsh_query_t *lhq, void **level, nxt_uint_t size) 6260Sigor@sysoev.ru { 6270Sigor@sysoev.ru nxt_uint_t i; 6280Sigor@sysoev.ru const nxt_lvlhsh_proto_t *proto; 6290Sigor@sysoev.ru 6300Sigor@sysoev.ru proto = lhq->proto; 6310Sigor@sysoev.ru 6320Sigor@sysoev.ru for (i = 0; i < size; i++) { 6330Sigor@sysoev.ru 6340Sigor@sysoev.ru if (level[i] != NULL) { 6350Sigor@sysoev.ru /* 6360Sigor@sysoev.ru * Chained buckets are not possible here, since even 6370Sigor@sysoev.ru * in the worst case one bucket cannot be converted 6380Sigor@sysoev.ru * in two chained buckets but remains the same bucket. 6390Sigor@sysoev.ru */ 64065Sigor@sysoev.ru proto->free(lhq->pool, nxt_lvlhsh_bucket(proto, level[i])); 6410Sigor@sysoev.ru } 6420Sigor@sysoev.ru } 6430Sigor@sysoev.ru 64465Sigor@sysoev.ru proto->free(lhq->pool, level); 6450Sigor@sysoev.ru 6460Sigor@sysoev.ru return NXT_ERROR; 6470Sigor@sysoev.ru } 6480Sigor@sysoev.ru 6490Sigor@sysoev.ru 6500Sigor@sysoev.ru nxt_int_t 6510Sigor@sysoev.ru nxt_lvlhsh_delete(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq) 6520Sigor@sysoev.ru { 6530Sigor@sysoev.ru if (nxt_fast_path(lh->slot != NULL)) { 6540Sigor@sysoev.ru 6550Sigor@sysoev.ru if (nxt_lvlhsh_is_bucket(lh->slot)) { 6560Sigor@sysoev.ru return nxt_lvlhsh_bucket_delete(lhq, &lh->slot); 6570Sigor@sysoev.ru } 6580Sigor@sysoev.ru 6590Sigor@sysoev.ru return nxt_lvlhsh_level_delete(lhq, &lh->slot, lhq->key_hash, 0); 6600Sigor@sysoev.ru } 6610Sigor@sysoev.ru 6620Sigor@sysoev.ru return NXT_DECLINED; 6630Sigor@sysoev.ru } 6640Sigor@sysoev.ru 6650Sigor@sysoev.ru 6660Sigor@sysoev.ru static nxt_int_t 6670Sigor@sysoev.ru nxt_lvlhsh_level_delete(nxt_lvlhsh_query_t *lhq, void **parent, uint32_t key, 6680Sigor@sysoev.ru nxt_uint_t nlvl) 6690Sigor@sysoev.ru { 6700Sigor@sysoev.ru void **slot, **lvl; 6710Sigor@sysoev.ru uintptr_t mask; 6720Sigor@sysoev.ru nxt_int_t ret; 6730Sigor@sysoev.ru nxt_uint_t shift; 6740Sigor@sysoev.ru 6750Sigor@sysoev.ru shift = lhq->proto->shift[nlvl]; 6760Sigor@sysoev.ru mask = ((uintptr_t) 1 << shift) - 1; 6770Sigor@sysoev.ru 6780Sigor@sysoev.ru lvl = nxt_lvlhsh_level(*parent, mask); 6790Sigor@sysoev.ru slot = &lvl[key & mask]; 6800Sigor@sysoev.ru 6810Sigor@sysoev.ru if (*slot != NULL) { 6820Sigor@sysoev.ru 6830Sigor@sysoev.ru if (nxt_lvlhsh_is_bucket(*slot)) { 6840Sigor@sysoev.ru ret = nxt_lvlhsh_bucket_delete(lhq, slot); 6850Sigor@sysoev.ru 6860Sigor@sysoev.ru } else { 6870Sigor@sysoev.ru key >>= shift; 6880Sigor@sysoev.ru ret = nxt_lvlhsh_level_delete(lhq, slot, key, nlvl + 1); 6890Sigor@sysoev.ru } 6900Sigor@sysoev.ru 6910Sigor@sysoev.ru if (*slot == NULL) { 6920Sigor@sysoev.ru nxt_lvlhsh_count_dec(*parent); 6930Sigor@sysoev.ru 6940Sigor@sysoev.ru if (nxt_lvlhsh_level_entries(*parent, mask) == 0) { 6950Sigor@sysoev.ru *parent = NULL; 69665Sigor@sysoev.ru lhq->proto->free(lhq->pool, lvl); 6970Sigor@sysoev.ru } 6980Sigor@sysoev.ru } 6990Sigor@sysoev.ru 7000Sigor@sysoev.ru return ret; 7010Sigor@sysoev.ru } 7020Sigor@sysoev.ru 7030Sigor@sysoev.ru return NXT_DECLINED; 7040Sigor@sysoev.ru } 7050Sigor@sysoev.ru 7060Sigor@sysoev.ru 7070Sigor@sysoev.ru static nxt_int_t 7080Sigor@sysoev.ru nxt_lvlhsh_bucket_delete(nxt_lvlhsh_query_t *lhq, void **bkt) 7090Sigor@sysoev.ru { 7100Sigor@sysoev.ru void *value; 7110Sigor@sysoev.ru uint32_t *bucket, *e; 7120Sigor@sysoev.ru uintptr_t n; 7130Sigor@sysoev.ru const nxt_lvlhsh_proto_t *proto; 7140Sigor@sysoev.ru 7150Sigor@sysoev.ru proto = lhq->proto; 7160Sigor@sysoev.ru 7170Sigor@sysoev.ru do { 7180Sigor@sysoev.ru bucket = nxt_lvlhsh_bucket(proto, *bkt); 7190Sigor@sysoev.ru n = nxt_lvlhsh_bucket_entries(proto, *bkt); 7200Sigor@sysoev.ru e = bucket; 7210Sigor@sysoev.ru 7220Sigor@sysoev.ru do { 7230Sigor@sysoev.ru if (nxt_lvlhsh_valid_entry(e)) { 7240Sigor@sysoev.ru 7250Sigor@sysoev.ru if (nxt_lvlhsh_entry_key(e) == lhq->key_hash) { 7260Sigor@sysoev.ru 7270Sigor@sysoev.ru value = nxt_lvlhsh_entry_value(e); 7280Sigor@sysoev.ru 7290Sigor@sysoev.ru if (proto->test(lhq, value) == NXT_OK) { 7300Sigor@sysoev.ru 7310Sigor@sysoev.ru if (nxt_lvlhsh_bucket_entries(proto, *bkt) == 1) { 7320Sigor@sysoev.ru *bkt = *nxt_lvlhsh_next_bucket(proto, bucket); 73365Sigor@sysoev.ru proto->free(lhq->pool, bucket); 7340Sigor@sysoev.ru 7350Sigor@sysoev.ru } else { 7360Sigor@sysoev.ru nxt_lvlhsh_count_dec(*bkt); 7370Sigor@sysoev.ru nxt_lvlhsh_set_entry_value(e, NULL); 7380Sigor@sysoev.ru } 7390Sigor@sysoev.ru 7400Sigor@sysoev.ru lhq->value = value; 7410Sigor@sysoev.ru 7420Sigor@sysoev.ru return NXT_OK; 7430Sigor@sysoev.ru } 7440Sigor@sysoev.ru } 7450Sigor@sysoev.ru 7460Sigor@sysoev.ru n--; 7470Sigor@sysoev.ru } 7480Sigor@sysoev.ru 7490Sigor@sysoev.ru e += NXT_LVLHSH_ENTRY_SIZE; 7500Sigor@sysoev.ru 7510Sigor@sysoev.ru } while (n != 0); 7520Sigor@sysoev.ru 7530Sigor@sysoev.ru bkt = nxt_lvlhsh_next_bucket(proto, bucket); 7540Sigor@sysoev.ru 7550Sigor@sysoev.ru } while (*bkt != NULL); 7560Sigor@sysoev.ru 7570Sigor@sysoev.ru return NXT_DECLINED; 7580Sigor@sysoev.ru } 7590Sigor@sysoev.ru 7600Sigor@sysoev.ru 7610Sigor@sysoev.ru void * 7620Sigor@sysoev.ru nxt_lvlhsh_each(nxt_lvlhsh_t *lh, nxt_lvlhsh_each_t *lhe) 7630Sigor@sysoev.ru { 7640Sigor@sysoev.ru void **slot; 7650Sigor@sysoev.ru 7660Sigor@sysoev.ru if (lhe->bucket == NXT_LVLHSH_BUCKET_DONE) { 7670Sigor@sysoev.ru slot = lh->slot; 7680Sigor@sysoev.ru 7690Sigor@sysoev.ru if (nxt_lvlhsh_is_bucket(slot)) { 7700Sigor@sysoev.ru return NULL; 7710Sigor@sysoev.ru } 7720Sigor@sysoev.ru 7730Sigor@sysoev.ru } else { 7740Sigor@sysoev.ru if (nxt_slow_path(lhe->bucket == NULL)) { 7750Sigor@sysoev.ru 7760Sigor@sysoev.ru /* The first iteration only. */ 7770Sigor@sysoev.ru 7780Sigor@sysoev.ru slot = lh->slot; 7790Sigor@sysoev.ru 7800Sigor@sysoev.ru if (slot == NULL) { 7810Sigor@sysoev.ru return NULL; 7820Sigor@sysoev.ru } 7830Sigor@sysoev.ru 7840Sigor@sysoev.ru if (!nxt_lvlhsh_is_bucket(slot)) { 785*598Sigor@sysoev.ru lhe->current = 0; 7860Sigor@sysoev.ru goto level; 7870Sigor@sysoev.ru } 7880Sigor@sysoev.ru 7890Sigor@sysoev.ru lhe->bucket = nxt_lvlhsh_bucket(lhe->proto, slot); 7900Sigor@sysoev.ru lhe->entries = nxt_lvlhsh_bucket_entries(lhe->proto, slot); 791*598Sigor@sysoev.ru lhe->entry = 0; 7920Sigor@sysoev.ru } 7930Sigor@sysoev.ru 7940Sigor@sysoev.ru return nxt_lvlhsh_bucket_each(lhe); 7950Sigor@sysoev.ru } 7960Sigor@sysoev.ru 7970Sigor@sysoev.ru level: 7980Sigor@sysoev.ru 7990Sigor@sysoev.ru return nxt_lvlhsh_level_each(lhe, slot, 0, 0); 8000Sigor@sysoev.ru } 8010Sigor@sysoev.ru 8020Sigor@sysoev.ru 8030Sigor@sysoev.ru static void * 8040Sigor@sysoev.ru nxt_lvlhsh_level_each(nxt_lvlhsh_each_t *lhe, void **level, nxt_uint_t nlvl, 8050Sigor@sysoev.ru nxt_uint_t shift) 8060Sigor@sysoev.ru { 8070Sigor@sysoev.ru void **slot, *value; 8080Sigor@sysoev.ru uintptr_t mask; 8090Sigor@sysoev.ru nxt_uint_t n, level_shift; 8100Sigor@sysoev.ru 8110Sigor@sysoev.ru level_shift = lhe->proto->shift[nlvl]; 8120Sigor@sysoev.ru mask = ((uintptr_t) 1 << level_shift) - 1; 8130Sigor@sysoev.ru 8140Sigor@sysoev.ru level = nxt_lvlhsh_level(level, mask); 8150Sigor@sysoev.ru 8160Sigor@sysoev.ru do { 8170Sigor@sysoev.ru n = (lhe->current >> shift) & mask; 8180Sigor@sysoev.ru slot = level[n]; 8190Sigor@sysoev.ru 8200Sigor@sysoev.ru if (slot != NULL) { 8210Sigor@sysoev.ru if (nxt_lvlhsh_is_bucket(slot)) { 8220Sigor@sysoev.ru 8230Sigor@sysoev.ru if (lhe->bucket != NXT_LVLHSH_BUCKET_DONE) { 8240Sigor@sysoev.ru 8250Sigor@sysoev.ru lhe->bucket = nxt_lvlhsh_bucket(lhe->proto, slot); 8260Sigor@sysoev.ru lhe->entries = nxt_lvlhsh_bucket_entries(lhe->proto, slot); 8270Sigor@sysoev.ru lhe->entry = 0; 8280Sigor@sysoev.ru 8290Sigor@sysoev.ru return nxt_lvlhsh_bucket_each(lhe); 8300Sigor@sysoev.ru } 8310Sigor@sysoev.ru 8320Sigor@sysoev.ru lhe->bucket = NULL; 8330Sigor@sysoev.ru 8340Sigor@sysoev.ru } else { 8350Sigor@sysoev.ru value = nxt_lvlhsh_level_each(lhe, slot, nlvl + 1, 8360Sigor@sysoev.ru shift + level_shift); 8370Sigor@sysoev.ru if (value != NULL) { 8380Sigor@sysoev.ru return value; 8390Sigor@sysoev.ru } 8400Sigor@sysoev.ru } 8410Sigor@sysoev.ru } 8420Sigor@sysoev.ru 8430Sigor@sysoev.ru lhe->current &= ~(mask << shift); 8440Sigor@sysoev.ru n = ((n + 1) & mask) << shift; 8450Sigor@sysoev.ru lhe->current |= n; 8460Sigor@sysoev.ru 8470Sigor@sysoev.ru } while (n != 0); 8480Sigor@sysoev.ru 8490Sigor@sysoev.ru return NULL; 8500Sigor@sysoev.ru } 8510Sigor@sysoev.ru 8520Sigor@sysoev.ru 8530Sigor@sysoev.ru static nxt_noinline void * 8540Sigor@sysoev.ru nxt_lvlhsh_bucket_each(nxt_lvlhsh_each_t *lhe) 8550Sigor@sysoev.ru { 8560Sigor@sysoev.ru void *value, **next; 8570Sigor@sysoev.ru uint32_t *bucket; 8580Sigor@sysoev.ru 8590Sigor@sysoev.ru /* At least one valid entry must present here. */ 8600Sigor@sysoev.ru do { 8610Sigor@sysoev.ru bucket = &lhe->bucket[lhe->entry]; 8620Sigor@sysoev.ru lhe->entry += NXT_LVLHSH_ENTRY_SIZE; 8630Sigor@sysoev.ru 8640Sigor@sysoev.ru } while (nxt_lvlhsh_free_entry(bucket)); 8650Sigor@sysoev.ru 8660Sigor@sysoev.ru value = nxt_lvlhsh_entry_value(bucket); 8670Sigor@sysoev.ru 8680Sigor@sysoev.ru lhe->entries--; 8690Sigor@sysoev.ru 8700Sigor@sysoev.ru if (lhe->entries == 0) { 8710Sigor@sysoev.ru next = *nxt_lvlhsh_next_bucket(lhe->proto, lhe->bucket); 8720Sigor@sysoev.ru 87372Sigor@sysoev.ru lhe->bucket = (next == NULL) ? NXT_LVLHSH_BUCKET_DONE 87472Sigor@sysoev.ru : nxt_lvlhsh_bucket(lhe->proto, next); 8750Sigor@sysoev.ru 8760Sigor@sysoev.ru lhe->entries = nxt_lvlhsh_bucket_entries(lhe->proto, next); 8770Sigor@sysoev.ru lhe->entry = 0; 8780Sigor@sysoev.ru } 8790Sigor@sysoev.ru 8800Sigor@sysoev.ru return value; 8810Sigor@sysoev.ru } 8820Sigor@sysoev.ru 8830Sigor@sysoev.ru 8840Sigor@sysoev.ru void * 885594Sigor@sysoev.ru nxt_lvlhsh_peek(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto) 886594Sigor@sysoev.ru { 887595Sigor@sysoev.ru void **slot; 888595Sigor@sysoev.ru nxt_lvlhsh_peek_t peek; 889594Sigor@sysoev.ru 890594Sigor@sysoev.ru slot = lh->slot; 891594Sigor@sysoev.ru 892594Sigor@sysoev.ru if (slot != NULL) { 893594Sigor@sysoev.ru 894595Sigor@sysoev.ru peek.proto = proto; 895595Sigor@sysoev.ru peek.retrieve = 0; 896595Sigor@sysoev.ru 897594Sigor@sysoev.ru if (nxt_lvlhsh_is_bucket(slot)) { 898595Sigor@sysoev.ru return nxt_lvlhsh_bucket_peek(&peek, &lh->slot); 899594Sigor@sysoev.ru } 900594Sigor@sysoev.ru 901595Sigor@sysoev.ru return nxt_lvlhsh_level_peek(&peek, &lh->slot, 0); 902594Sigor@sysoev.ru } 903594Sigor@sysoev.ru 904594Sigor@sysoev.ru return NULL; 905594Sigor@sysoev.ru } 906594Sigor@sysoev.ru 907594Sigor@sysoev.ru 908594Sigor@sysoev.ru static void * 909595Sigor@sysoev.ru nxt_lvlhsh_level_peek(nxt_lvlhsh_peek_t *peek, void **parent, nxt_uint_t nlvl) 910594Sigor@sysoev.ru { 911595Sigor@sysoev.ru void **slot, **level, *value; 912594Sigor@sysoev.ru uintptr_t mask; 913594Sigor@sysoev.ru nxt_uint_t n, shift; 914594Sigor@sysoev.ru 915595Sigor@sysoev.ru shift = peek->proto->shift[nlvl]; 916594Sigor@sysoev.ru mask = ((uintptr_t) 1 << shift) - 1; 917594Sigor@sysoev.ru 918595Sigor@sysoev.ru level = nxt_lvlhsh_level(*parent, mask); 919594Sigor@sysoev.ru 920594Sigor@sysoev.ru n = 0; 921594Sigor@sysoev.ru 922594Sigor@sysoev.ru /* At least one valid level slot must present here. */ 923594Sigor@sysoev.ru 924594Sigor@sysoev.ru for ( ;; ) { 925595Sigor@sysoev.ru slot = &level[n]; 926595Sigor@sysoev.ru 927595Sigor@sysoev.ru if (*slot != NULL) { 928594Sigor@sysoev.ru 929595Sigor@sysoev.ru if (nxt_lvlhsh_is_bucket(*slot)) { 930595Sigor@sysoev.ru value = nxt_lvlhsh_bucket_peek(peek, slot); 931594Sigor@sysoev.ru 932595Sigor@sysoev.ru } else { 933595Sigor@sysoev.ru value = nxt_lvlhsh_level_peek(peek, slot, nlvl + 1); 934594Sigor@sysoev.ru } 935594Sigor@sysoev.ru 936595Sigor@sysoev.ru /* 937595Sigor@sysoev.ru * Checking peek->retrieve is not required here because 938595Sigor@sysoev.ru * there can not be empty slots during peeking. 939595Sigor@sysoev.ru */ 940595Sigor@sysoev.ru if (*slot == NULL) { 941595Sigor@sysoev.ru nxt_lvlhsh_count_dec(*parent); 942595Sigor@sysoev.ru 943595Sigor@sysoev.ru if (nxt_lvlhsh_level_entries(*parent, mask) == 0) { 944595Sigor@sysoev.ru *parent = NULL; 945595Sigor@sysoev.ru peek->proto->free(peek->pool, level); 946595Sigor@sysoev.ru } 947595Sigor@sysoev.ru } 948595Sigor@sysoev.ru 949595Sigor@sysoev.ru return value; 950594Sigor@sysoev.ru } 951594Sigor@sysoev.ru 952594Sigor@sysoev.ru n++; 953594Sigor@sysoev.ru } 954594Sigor@sysoev.ru } 955594Sigor@sysoev.ru 956594Sigor@sysoev.ru 957595Sigor@sysoev.ru static nxt_noinline void * 958595Sigor@sysoev.ru nxt_lvlhsh_bucket_peek(nxt_lvlhsh_peek_t *peek, void **bkt) 959594Sigor@sysoev.ru { 960595Sigor@sysoev.ru void *value; 961595Sigor@sysoev.ru uint32_t *bucket, *entry; 962595Sigor@sysoev.ru const nxt_lvlhsh_proto_t *proto; 963595Sigor@sysoev.ru 964595Sigor@sysoev.ru bucket = nxt_lvlhsh_bucket(peek->proto, *bkt); 965594Sigor@sysoev.ru 966594Sigor@sysoev.ru /* At least one valid entry must present here. */ 967594Sigor@sysoev.ru 968595Sigor@sysoev.ru for (entry = bucket; 969594Sigor@sysoev.ru nxt_lvlhsh_free_entry(entry); 970594Sigor@sysoev.ru entry += NXT_LVLHSH_ENTRY_SIZE) 971594Sigor@sysoev.ru { 972594Sigor@sysoev.ru /* void */ 973594Sigor@sysoev.ru } 974594Sigor@sysoev.ru 975594Sigor@sysoev.ru value = nxt_lvlhsh_entry_value(entry); 976595Sigor@sysoev.ru 977595Sigor@sysoev.ru if (peek->retrieve) { 978595Sigor@sysoev.ru proto = peek->proto; 979595Sigor@sysoev.ru 980595Sigor@sysoev.ru if (nxt_lvlhsh_bucket_entries(proto, *bkt) == 1) { 981595Sigor@sysoev.ru *bkt = *nxt_lvlhsh_next_bucket(proto, bucket); 982595Sigor@sysoev.ru proto->free(peek->pool, bucket); 983595Sigor@sysoev.ru 984595Sigor@sysoev.ru } else { 985595Sigor@sysoev.ru nxt_lvlhsh_count_dec(*bkt); 986595Sigor@sysoev.ru nxt_lvlhsh_set_entry_value(entry, NULL); 987595Sigor@sysoev.ru } 988595Sigor@sysoev.ru } 989595Sigor@sysoev.ru 990594Sigor@sysoev.ru return value; 991594Sigor@sysoev.ru } 992594Sigor@sysoev.ru 993594Sigor@sysoev.ru 994594Sigor@sysoev.ru void * 995595Sigor@sysoev.ru nxt_lvlhsh_retrieve(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto, 996595Sigor@sysoev.ru void *pool) 997595Sigor@sysoev.ru { 998595Sigor@sysoev.ru void **slot; 999595Sigor@sysoev.ru nxt_lvlhsh_peek_t peek; 1000595Sigor@sysoev.ru 1001595Sigor@sysoev.ru slot = lh->slot; 1002595Sigor@sysoev.ru 1003595Sigor@sysoev.ru if (slot != NULL) { 1004595Sigor@sysoev.ru 1005595Sigor@sysoev.ru peek.proto = proto; 1006595Sigor@sysoev.ru peek.pool = pool; 1007595Sigor@sysoev.ru peek.retrieve = 1; 1008595Sigor@sysoev.ru 1009595Sigor@sysoev.ru if (nxt_lvlhsh_is_bucket(slot)) { 1010595Sigor@sysoev.ru return nxt_lvlhsh_bucket_peek(&peek, &lh->slot); 1011595Sigor@sysoev.ru } 1012595Sigor@sysoev.ru 1013595Sigor@sysoev.ru return nxt_lvlhsh_level_peek(&peek, &lh->slot, 0); 1014595Sigor@sysoev.ru } 1015595Sigor@sysoev.ru 1016595Sigor@sysoev.ru return NULL; 1017595Sigor@sysoev.ru } 1018595Sigor@sysoev.ru 1019595Sigor@sysoev.ru 1020595Sigor@sysoev.ru void * 102165Sigor@sysoev.ru nxt_lvlhsh_alloc(void *data, size_t size) 10220Sigor@sysoev.ru { 10230Sigor@sysoev.ru return nxt_memalign(size, size); 10240Sigor@sysoev.ru } 10250Sigor@sysoev.ru 10260Sigor@sysoev.ru 10270Sigor@sysoev.ru void 102865Sigor@sysoev.ru nxt_lvlhsh_free(void *data, void *p) 10290Sigor@sysoev.ru { 10300Sigor@sysoev.ru nxt_free(p); 10310Sigor@sysoev.ru } 1032