1 2 /* 3 * Copyright (C) Igor Sysoev 4 * Copyright (C) NGINX, Inc. 5 */ 6 7 #ifndef _NXT_LEVEL_HASH_H_INCLUDED_ 8 #define _NXT_LEVEL_HASH_H_INCLUDED_ 9 10 11 typedef struct nxt_lvlhsh_query_s nxt_lvlhsh_query_t; 12 13 typedef nxt_int_t (*nxt_lvlhsh_test_t)(nxt_lvlhsh_query_t *lhq, void *data); 14 typedef void *(*nxt_lvlhsh_alloc_t)(void *ctx, size_t size); 15 typedef void (*nxt_lvlhsh_free_t)(void *ctx, void *p); 16 17 18 #if (NXT_64BIT) 19 20 #define NXT_LVLHSH_DEFAULT_BUCKET_SIZE 128 21 #define NXT_LVLHSH_ENTRY_SIZE 3 22 #define NXT_LVLHSH_BATCH_ALLOC 16 23 24 /* 3 is shift of 64-bit pointer. */ 25 #define NXT_LVLHSH_MEMALIGN_SHIFT (NXT_MAX_MEMALIGN_SHIFT - 3) 26 27 #else 28 29 #define NXT_LVLHSH_DEFAULT_BUCKET_SIZE 64 30 #define NXT_LVLHSH_ENTRY_SIZE 2 31 #define NXT_LVLHSH_BATCH_ALLOC 8 32 33 /* 2 is shift of 32-bit pointer. */ 34 #define NXT_LVLHSH_MEMALIGN_SHIFT (NXT_MAX_MEMALIGN_SHIFT - 2) 35 36 #endif 37 38 39 #if (NXT_LVLHSH_MEMALIGN_SHIFT < 10) 40 #define NXT_LVLHSH_MAX_MEMALIGN_SHIFT NXT_LVLHSH_MEMALIGN_SHIFT 41 #else 42 #define NXT_LVLHSH_MAX_MEMALIGN_SHIFT 10 43 #endif 44 45 46 #define NXT_LVLHSH_BUCKET_END(bucket_size) \ 47 (((bucket_size) - sizeof(void *)) \ 48 / (NXT_LVLHSH_ENTRY_SIZE * sizeof(uint32_t)) \ 49 * NXT_LVLHSH_ENTRY_SIZE) 50 51 52 #define NXT_LVLHSH_BUCKET_SIZE(bucket_size) \ 53 NXT_LVLHSH_BUCKET_END(bucket_size), bucket_size, (bucket_size - 1) 54 55 56 #define NXT_LVLHSH_DEFAULT \ 57 NXT_LVLHSH_BUCKET_SIZE(NXT_LVLHSH_DEFAULT_BUCKET_SIZE), \ 58 { 4, 4, 4, 4, 4, 4, 4, 0 } 59 60 61 #define NXT_LVLHSH_LARGE_SLAB \ 62 NXT_LVLHSH_BUCKET_SIZE(NXT_LVLHSH_DEFAULT_BUCKET_SIZE), \ 63 { 10, 4, 4, 4, 4, 4, 4, 0 } 64 65 66 #define NXT_LVLHSH_LARGE_MEMALIGN \ 67 NXT_LVLHSH_BUCKET_SIZE(NXT_LVLHSH_DEFAULT_BUCKET_SIZE), \ 68 { NXT_LVLHSH_MAX_MEMALIGN_SHIFT, 4, 4, 4, 4, 0, 0, 0 } 69 70 71 typedef struct { 72 uint32_t bucket_end; 73 uint32_t bucket_size; 74 uint32_t bucket_mask; 75 uint8_t shift[8]; 76 77 nxt_lvlhsh_test_t test; 78 nxt_lvlhsh_alloc_t alloc; 79 nxt_lvlhsh_free_t free; 80 } nxt_lvlhsh_proto_t; 81 82 83 typedef struct { 84 void *slot; 85 } nxt_lvlhsh_t; 86 87 88 struct nxt_lvlhsh_query_s { 89 uint32_t key_hash; 90 uint32_t replace; /* 1 bit */ 91 nxt_str_t key; 92 void *value; 93 94 const nxt_lvlhsh_proto_t *proto; 95 void *pool; 96 97 /* Opaque data passed for the test function. */ 98 void *data; 99 }; 100 101 102 typedef struct { 103 const nxt_lvlhsh_proto_t *proto; 104 /* 105 * Fields to store current bucket entry position. They cannot be 106 * combined in a single bucket pointer with number of entries in low 107 * bits, because entry positions are not aligned. A current level is 108 * stored as key bit path from the root. 109 */ 110 uint32_t *bucket; 111 uint32_t current; 112 uint32_t entry; 113 uint32_t entries; 114 } nxt_lvlhsh_each_t; 115 116 117 #define \ 118 nxt_lvlhsh_is_empty(lh) \ 119 ((lh)->slot == NULL) 120 121 122 #define \ 123 nxt_lvlhsh_init(lh) \ 124 (lh)->slot = NULL 125 126 /* 127 * nxt_lvlhsh_find() finds a hash element. If the element has been 128 * found then it is stored in the lhq->value and nxt_lvlhsh_find() 129 * returns NXT_OK. Otherwise NXT_DECLINED is returned. 130 * 131 * The required nxt_lvlhsh_query_t fields: key_hash, key, proto. 132 */ 133 NXT_EXPORT nxt_int_t nxt_lvlhsh_find(nxt_lvlhsh_t *lh, nxt_lvlhsh_query_t *lhq); 134 135 /* 136 * nxt_lvlhsh_insert() adds a hash element. If the element already 137 * presents in lvlhsh and the lhq->replace flag is zero, then lhq->value 138 * is updated with the old element and NXT_DECLINED is returned. 139 * If the element already presents in lvlhsh and the lhq->replace flag 140 * is non-zero, then the old element is replaced with the new element. 141 * lhq->value is updated with the old element, and NXT_OK is returned. 142 * If the element is not present in lvlhsh, then it is inserted and 143 * NXT_OK is returned. The lhq->value is not changed. 144 * On memory allocation failure NXT_ERROR is returned. 145 * 146 * The required nxt_lvlhsh_query_t fields: key_hash, key, proto, replace, value. 147 * The optional nxt_lvlhsh_query_t fields: pool. 148 */ 149 NXT_EXPORT nxt_int_t nxt_lvlhsh_insert(nxt_lvlhsh_t *lh, 150 nxt_lvlhsh_query_t *lhq); 151 152 /* 153 * nxt_lvlhsh_delete() deletes a hash element. If the element has been 154 * found then it is removed from lvlhsh and is stored in the lhq->value, 155 * and NXT_OK is returned. Otherwise NXT_DECLINED is returned. 156 * 157 * The required nxt_lvlhsh_query_t fields: key_hash, key, proto. 158 * The optional nxt_lvlhsh_query_t fields: pool. 159 */ 160 NXT_EXPORT nxt_int_t nxt_lvlhsh_delete(nxt_lvlhsh_t *lh, 161 nxt_lvlhsh_query_t *lhq); 162 163 /* 164 * nxt_lvlhsh_each_init() initializes iterator. 165 * It must be called before the first nxt_lvlhsh_each() call. 166 */ 167 #define nxt_lvlhsh_each_init(lhe, _proto) \ 168 do { \ 169 (lhe)->proto = _proto; \ 170 (lhe)->bucket = NULL; \ 171 } while (0) 172 173 /* 174 * nxt_lvlhsh_each() iterates over a lvlhsh. 175 * It returns NULL if there is no more elements. 176 */ 177 NXT_EXPORT void *nxt_lvlhsh_each(nxt_lvlhsh_t *lh, nxt_lvlhsh_each_t *lhe); 178 179 /* 180 * nxt_lvlhsh_peek() is used to iterate over a lvlhsh during the lvlhsh 181 * destruction. The returned hash element should be deleted from the lvlhsh, 182 * otherwise it will be returned again by the next nxt_lvlhsh_peek() call. 183 * The function returns NULL if there is no more elements in the lvlhsh. 184 */ 185 NXT_EXPORT void *nxt_lvlhsh_peek(nxt_lvlhsh_t *lh, 186 const nxt_lvlhsh_proto_t *proto); 187 188 /* 189 * nxt_lvlhsh_retrieve() is used to iterate over a lvlhsh during the lvlhsh 190 * destruction. As opposed to nxt_lvlhsh_peek() the returned hash element 191 * is deleted from the lvlhsh. The function returns NULL if there is no 192 * more elements in the lvlhsh. 193 */ 194 NXT_EXPORT void *nxt_lvlhsh_retrieve(nxt_lvlhsh_t *lh, 195 const nxt_lvlhsh_proto_t *proto, void *pool); 196 197 198 NXT_EXPORT void *nxt_lvlhsh_alloc(void *data, size_t size); 199 NXT_EXPORT void nxt_lvlhsh_free(void *data, void *p); 200 201 202 #endif /* _NXT_LEVEL_HASH_H_INCLUDED_ */ 203