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 1020Sigor@sysoev.ru #define \ 1030Sigor@sysoev.ru nxt_lvlhsh_is_empty(lh) \ 1040Sigor@sysoev.ru ((lh)->slot == NULL) 1050Sigor@sysoev.ru 1060Sigor@sysoev.ru 1070Sigor@sysoev.ru #define \ 1080Sigor@sysoev.ru nxt_lvlhsh_init(lh) \ 1090Sigor@sysoev.ru (lh)->slot = NULL 1100Sigor@sysoev.ru 1110Sigor@sysoev.ru /* 1120Sigor@sysoev.ru * nxt_lvlhsh_find() finds a hash element. If the element has been 1130Sigor@sysoev.ru * found then it is stored in the lhq->value and nxt_lvlhsh_find() 1140Sigor@sysoev.ru * returns NXT_OK. Otherwise NXT_DECLINED is returned. 1150Sigor@sysoev.ru * 1160Sigor@sysoev.ru * The required nxt_lvlhsh_query_t fields: key_hash, key, proto. 1170Sigor@sysoev.ru */ 1180Sigor@sysoev.ru NXT_EXPORT nxt_int_t nxt_lvlhsh_find(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq); 1190Sigor@sysoev.ru 1200Sigor@sysoev.ru /* 1210Sigor@sysoev.ru * nxt_lvlhsh_insert() adds a hash element. If the element already 1220Sigor@sysoev.ru * presents in lvlhsh and the lhq->replace flag is zero, then lhq->value 1230Sigor@sysoev.ru * is updated with the old element and NXT_DECLINED is returned. 1240Sigor@sysoev.ru * If the element already presents in lvlhsh and the lhq->replace flag 1250Sigor@sysoev.ru * is non-zero, then the old element is replaced with the new element. 1260Sigor@sysoev.ru * lhq->value is updated with the old element, and NXT_OK is returned. 1270Sigor@sysoev.ru * If the element is not present in lvlhsh, then it is inserted and 1280Sigor@sysoev.ru * NXT_OK is returned. The lhq->value is not changed. 1290Sigor@sysoev.ru * On memory allocation failure NXT_ERROR is returned. 1300Sigor@sysoev.ru * 1310Sigor@sysoev.ru * The required nxt_lvlhsh_query_t fields: key_hash, key, proto, replace, value. 1320Sigor@sysoev.ru * The optional nxt_lvlhsh_query_t fields: pool. 1330Sigor@sysoev.ru */ 1340Sigor@sysoev.ru NXT_EXPORT nxt_int_t nxt_lvlhsh_insert(nxt_lvlhsh_t *lh, 1350Sigor@sysoev.ru nxt_lvlhsh_query_t *lhq); 1360Sigor@sysoev.ru 1370Sigor@sysoev.ru /* 1380Sigor@sysoev.ru * nxt_lvlhsh_delete() deletes a hash element. If the element has been 1390Sigor@sysoev.ru * found then it is removed from lvlhsh and is stored in the lhq->value, 1400Sigor@sysoev.ru * and NXT_OK is returned. Otherwise NXT_DECLINED is returned. 1410Sigor@sysoev.ru * 1420Sigor@sysoev.ru * The required nxt_lvlhsh_query_t fields: key_hash, key, proto. 1430Sigor@sysoev.ru * The optional nxt_lvlhsh_query_t fields: pool. 1440Sigor@sysoev.ru */ 1450Sigor@sysoev.ru NXT_EXPORT nxt_int_t nxt_lvlhsh_delete(nxt_lvlhsh_t *lh, 1460Sigor@sysoev.ru nxt_lvlhsh_query_t *lhq); 1470Sigor@sysoev.ru 1480Sigor@sysoev.ru 1490Sigor@sysoev.ru typedef struct { 1500Sigor@sysoev.ru const nxt_lvlhsh_proto_t *proto; 1510Sigor@sysoev.ru 1520Sigor@sysoev.ru /* 1530Sigor@sysoev.ru * Fields to store current bucket entry position. They cannot be 1540Sigor@sysoev.ru * combined in a single bucket pointer with number of entries in low 1550Sigor@sysoev.ru * bits, because entry positions are not aligned. A current level is 1560Sigor@sysoev.ru * stored as key bit path from the root. 1570Sigor@sysoev.ru */ 1580Sigor@sysoev.ru uint32_t *bucket; 1590Sigor@sysoev.ru uint32_t current; 1600Sigor@sysoev.ru uint32_t entry; 1610Sigor@sysoev.ru uint32_t entries; 1620Sigor@sysoev.ru } nxt_lvlhsh_each_t; 1630Sigor@sysoev.ru 1640Sigor@sysoev.ru 1650Sigor@sysoev.ru NXT_EXPORT void *nxt_lvlhsh_each(nxt_lvlhsh_t *lh, nxt_lvlhsh_each_t *le); 1660Sigor@sysoev.ru 167594Sigor@sysoev.ru /* 168594Sigor@sysoev.ru * nxt_lvlhsh_peek() is used to iterate over a lvlhsh during the lvlhsh 169594Sigor@sysoev.ru * destruction. The returned hash element should be deleted from the lvlhsh, 170594Sigor@sysoev.ru * otherwise it will be returned again by the next nxt_lvlhsh_peek() call. 171594Sigor@sysoev.ru * The function returns NULL if there is no more elements in the lvlhsh. 172594Sigor@sysoev.ru */ 173594Sigor@sysoev.ru NXT_EXPORT void *nxt_lvlhsh_peek(nxt_lvlhsh_t *lh, 174594Sigor@sysoev.ru const nxt_lvlhsh_proto_t *proto); 175594Sigor@sysoev.ru 176*595Sigor@sysoev.ru /* 177*595Sigor@sysoev.ru * nxt_lvlhsh_retrieve() is used to iterate over a lvlhsh during the lvlhsh 178*595Sigor@sysoev.ru * destruction. As opposed to nxt_lvlhsh_peek() the returned hash element 179*595Sigor@sysoev.ru * is deleted from the lvlhsh. The function returns NULL if there is no 180*595Sigor@sysoev.ru * more elements in the lvlhsh. 181*595Sigor@sysoev.ru */ 182*595Sigor@sysoev.ru NXT_EXPORT void *nxt_lvlhsh_retrieve(nxt_lvlhsh_t *lh, 183*595Sigor@sysoev.ru const nxt_lvlhsh_proto_t *proto, void *pool); 184*595Sigor@sysoev.ru 1850Sigor@sysoev.ru 18665Sigor@sysoev.ru NXT_EXPORT void *nxt_lvlhsh_alloc(void *data, size_t size); 18765Sigor@sysoev.ru NXT_EXPORT void nxt_lvlhsh_free(void *data, void *p); 1880Sigor@sysoev.ru 1890Sigor@sysoev.ru 1900Sigor@sysoev.ru #endif /* _NXT_LEVEL_HASH_H_INCLUDED_ */ 191