1 /* 2 * nghttp3 3 * 4 * Copyright (c) 2019 nghttp3 contributors 5 * Copyright (c) 2018 ngtcp2 contributors 6 * 7 * Permission is hereby granted, free of charge, to any person obtaining 8 * a copy of this software and associated documentation files (the 9 * "Software"), to deal in the Software without restriction, including 10 * without limitation the rights to use, copy, modify, merge, publish, 11 * distribute, sublicense, and/or sell copies of the Software, and to 12 * permit persons to whom the Software is furnished to do so, subject to 13 * the following conditions: 14 * 15 * The above copyright notice and this permission notice shall be 16 * included in all copies or substantial portions of the Software. 17 * 18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 22 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 23 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 24 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 25 */ 26 #ifndef NGHTTP3_KSL_H 27 #define NGHTTP3_KSL_H 28 29 #ifdef HAVE_CONFIG_H 30 # include <config.h> 31 #endif /* HAVE_CONFIG_H */ 32 33 #include <stdlib.h> 34 35 #include <nghttp3/nghttp3.h> 36 37 /* 38 * Skip List using single key instead of range. 39 */ 40 41 #define NGHTTP3_KSL_DEGR 16 42 /* NGHTTP3_KSL_MAX_NBLK is the maximum number of nodes which a single 43 block can contain. */ 44 #define NGHTTP3_KSL_MAX_NBLK (2 * NGHTTP3_KSL_DEGR - 1) 45 /* NGHTTP3_KSL_MIN_NBLK is the minimum number of nodes which a single 46 block other than root must contains. */ 47 #define NGHTTP3_KSL_MIN_NBLK (NGHTTP3_KSL_DEGR - 1) 48 49 /* 50 * nghttp3_ksl_key represents key in nghttp3_ksl. 51 */ 52 typedef void nghttp3_ksl_key; 53 54 typedef struct nghttp3_ksl_node nghttp3_ksl_node; 55 56 typedef struct nghttp3_ksl_blk nghttp3_ksl_blk; 57 58 /* 59 * nghttp3_ksl_node is a node which contains either nghttp3_ksl_blk or 60 * opaque data. If a node is an internal node, it contains 61 * nghttp3_ksl_blk. Otherwise, it has data. The key is stored at the 62 * location starting at key. 63 */ 64 struct nghttp3_ksl_node { 65 union { 66 nghttp3_ksl_blk *blk; 67 void *data; 68 }; 69 union { 70 uint64_t align; 71 /* key is a buffer to include key associated to this node. 72 Because the length of key is unknown until nghttp3_ksl_init is 73 called, the actual buffer will be allocated after this 74 field. */ 75 uint8_t key[1]; 76 }; 77 }; 78 79 /* 80 * nghttp3_ksl_blk contains nghttp3_ksl_node objects. 81 */ 82 struct nghttp3_ksl_blk { 83 /* next points to the next block if leaf field is nonzero. */ 84 nghttp3_ksl_blk *next; 85 /* prev points to the previous block if leaf field is nonzero. */ 86 nghttp3_ksl_blk *prev; 87 /* n is the number of nodes this object contains in nodes. */ 88 uint32_t n; 89 /* leaf is nonzero if this block contains leaf nodes. */ 90 uint32_t leaf; 91 union { 92 uint64_t align; 93 /* nodes is a buffer to contain NGHTTP3_KSL_MAX_NBLK 94 nghttp3_ksl_node objects. Because nghttp3_ksl_node object is 95 allocated along with the additional variable length key 96 storage, the size of buffer is unknown until nghttp3_ksl_init 97 is called. */ 98 uint8_t nodes[1]; 99 }; 100 }; 101 102 /* 103 * nghttp3_ksl_compar is a function type which returns nonzero if key 104 * |lhs| should be placed before |rhs|. It returns 0 otherwise. 105 */ 106 typedef int (*nghttp3_ksl_compar)(const nghttp3_ksl_key *lhs, 107 const nghttp3_ksl_key *rhs); 108 109 typedef struct nghttp3_ksl nghttp3_ksl; 110 111 typedef struct nghttp3_ksl_it nghttp3_ksl_it; 112 113 /* 114 * nghttp3_ksl_it is a forward iterator to iterate nodes. 115 */ 116 struct nghttp3_ksl_it { 117 const nghttp3_ksl *ksl; 118 nghttp3_ksl_blk *blk; 119 size_t i; 120 }; 121 122 /* 123 * nghttp3_ksl is a deterministic paged skip list. 124 */ 125 struct nghttp3_ksl { 126 /* head points to the root block. */ 127 nghttp3_ksl_blk *head; 128 /* front points to the first leaf block. */ 129 nghttp3_ksl_blk *front; 130 /* back points to the last leaf block. */ 131 nghttp3_ksl_blk *back; 132 nghttp3_ksl_compar compar; 133 size_t n; 134 /* keylen is the size of key */ 135 size_t keylen; 136 /* nodelen is the actual size of nghttp3_ksl_node including key 137 storage. */ 138 size_t nodelen; 139 const nghttp3_mem *mem; 140 }; 141 142 /* 143 * nghttp3_ksl_init initializes |ksl|. |compar| specifies compare 144 * function. |keylen| is the length of key. 145 * 146 * It returns 0 if it succeeds, or one of the following negative error 147 * codes: 148 * 149 * NGHTTP3_ERR_NOMEM 150 * Out of memory. 151 */ 152 int nghttp3_ksl_init(nghttp3_ksl *ksl, nghttp3_ksl_compar compar, size_t keylen, 153 const nghttp3_mem *mem); 154 155 /* 156 * nghttp3_ksl_free frees resources allocated for |ksl|. If |ksl| is 157 * NULL, this function does nothing. It does not free the memory 158 * region pointed by |ksl| itself. 159 */ 160 void nghttp3_ksl_free(nghttp3_ksl *ksl); 161 162 /* 163 * nghttp3_ksl_insert inserts |key| with its associated |data|. On 164 * successful insertion, the iterator points to the inserted node is 165 * stored in |*it|. 166 * 167 * This function returns 0 if it succeeds, or one of the following 168 * negative error codes: 169 * 170 * NGHTTP3_ERR_NOMEM 171 * Out of memory. 172 * NGHTTP3_ERR_INVALID_ARGUMENT 173 * |key| already exists. 174 */ 175 int nghttp3_ksl_insert(nghttp3_ksl *ksl, nghttp3_ksl_it *it, 176 const nghttp3_ksl_key *key, void *data); 177 178 /* 179 * nghttp3_ksl_remove removes the |key| from |ksl|. 180 * 181 * This function assigns the iterator to |*it|, which points to the 182 * node which is located at the right next of the removed node if |it| 183 * is not NULL. If |key| is not found, no deletion takes place and 184 * the return value of nghttp3_ksl_end(ksl) is assigned to |*it|. 185 * 186 * This function returns 0 if it succeeds, or one of the following 187 * negative error codes: 188 * 189 * NGHTTP3_ERR_INVALID_ARGUMENT 190 * |key| does not exist. 191 */ 192 int nghttp3_ksl_remove(nghttp3_ksl *ksl, nghttp3_ksl_it *it, 193 const nghttp3_ksl_key *key); 194 195 /* 196 * nghttp3_ksl_remove_hint removes the |key| from |ksl|. |hint| must 197 * point to the same node denoted by |key|. |hint| is used to remove 198 * a node efficiently in some cases. Other than that, it behaves 199 * exactly like nghttp3_ksl_remove. |it| and |hint| can point to the 200 * same object. 201 */ 202 int nghttp3_ksl_remove_hint(nghttp3_ksl *ksl, nghttp3_ksl_it *it, 203 const nghttp3_ksl_it *hint, 204 const nghttp3_ksl_key *key); 205 206 /* 207 * nghttp3_ksl_lower_bound returns the iterator which points to the 208 * first node which has the key which is equal to |key| or the last 209 * node which satisfies !compar(&node->key, key). If there is no such 210 * node, it returns the iterator which satisfies nghttp3_ksl_it_end(it) 211 * != 0. 212 */ 213 nghttp3_ksl_it nghttp3_ksl_lower_bound(nghttp3_ksl *ksl, 214 const nghttp3_ksl_key *key); 215 216 /* 217 * nghttp3_ksl_lower_bound_compar works like nghttp3_ksl_lower_bound, 218 * but it takes custom function |compar| to do lower bound search. 219 */ 220 nghttp3_ksl_it nghttp3_ksl_lower_bound_compar(nghttp3_ksl *ksl, 221 const nghttp3_ksl_key *key, 222 nghttp3_ksl_compar compar); 223 224 /* 225 * nghttp3_ksl_update_key replaces the key of nodes which has |old_key| 226 * with |new_key|. |new_key| must be strictly greater than the 227 * previous node and strictly smaller than the next node. 228 */ 229 void nghttp3_ksl_update_key(nghttp3_ksl *ksl, const nghttp3_ksl_key *old_key, 230 const nghttp3_ksl_key *new_key); 231 232 /* 233 * nghttp3_ksl_begin returns the iterator which points to the first 234 * node. If there is no node in |ksl|, it returns the iterator which 235 * satisfies nghttp3_ksl_it_end(it) != 0. 236 */ 237 nghttp3_ksl_it nghttp3_ksl_begin(const nghttp3_ksl *ksl); 238 239 /* 240 * nghttp3_ksl_end returns the iterator which points to the node 241 * following the last node. The returned object satisfies 242 * nghttp3_ksl_it_end(). If there is no node in |ksl|, it returns the 243 * iterator which satisfies nghttp3_ksl_it_begin(it) != 0. 244 */ 245 nghttp3_ksl_it nghttp3_ksl_end(const nghttp3_ksl *ksl); 246 247 /* 248 * nghttp3_ksl_len returns the number of elements stored in |ksl|. 249 */ 250 size_t nghttp3_ksl_len(nghttp3_ksl *ksl); 251 252 /* 253 * nghttp3_ksl_clear removes all elements stored in |ksl|. 254 */ 255 void nghttp3_ksl_clear(nghttp3_ksl *ksl); 256 257 /* 258 * nghttp3_ksl_nth_node returns the |n|th node under |blk|. 259 */ 260 #define nghttp3_ksl_nth_node(KSL, BLK, N) \ 261 ((nghttp3_ksl_node *)(void *)((BLK)->nodes + (KSL)->nodelen * (N))) 262 263 /* 264 * nghttp3_ksl_print prints its internal state in stderr. It assumes 265 * that the key is of type int64_t. This function should be used for 266 * the debugging purpose only. 267 */ 268 void nghttp3_ksl_print(nghttp3_ksl *ksl); 269 270 /* 271 * nghttp3_ksl_it_init initializes |it|. 272 */ 273 void nghttp3_ksl_it_init(nghttp3_ksl_it *it, const nghttp3_ksl *ksl, 274 nghttp3_ksl_blk *blk, size_t i); 275 276 /* 277 * nghttp3_ksl_it_get returns the data associated to the node which 278 * |it| points to. It is undefined to call this function when 279 * nghttp3_ksl_it_end(it) returns nonzero. 280 */ 281 #define nghttp3_ksl_it_get(IT) \ 282 nghttp3_ksl_nth_node((IT)->ksl, (IT)->blk, (IT)->i)->data 283 284 /* 285 * nghttp3_ksl_it_next advances the iterator by one. It is undefined 286 * if this function is called when nghttp3_ksl_it_end(it) returns 287 * nonzero. 288 */ 289 #define nghttp3_ksl_it_next(IT) \ 290 (++(IT)->i == (IT)->blk->n && (IT)->blk->next \ 291 ? ((IT)->blk = (IT)->blk->next, (IT)->i = 0) \ 292 : 0) 293 294 /* 295 * nghttp3_ksl_it_prev moves backward the iterator by one. It is 296 * undefined if this function is called when nghttp3_ksl_it_begin(it) 297 * returns nonzero. 298 */ 299 void nghttp3_ksl_it_prev(nghttp3_ksl_it *it); 300 301 /* 302 * nghttp3_ksl_it_end returns nonzero if |it| points to the beyond the 303 * last node. 304 */ 305 #define nghttp3_ksl_it_end(IT) \ 306 ((IT)->blk->n == (IT)->i && (IT)->blk->next == NULL) 307 308 /* 309 * nghttp3_ksl_it_begin returns nonzero if |it| points to the first 310 * node. |it| might satisfy both nghttp3_ksl_it_begin(&it) and 311 * nghttp3_ksl_it_end(&it) if the skip list has no node. 312 */ 313 int nghttp3_ksl_it_begin(const nghttp3_ksl_it *it); 314 315 /* 316 * nghttp3_ksl_key returns the key of the node which |it| points to. 317 * It is undefined to call this function when nghttp3_ksl_it_end(it) 318 * returns nonzero. 319 */ 320 #define nghttp3_ksl_it_key(IT) \ 321 ((nghttp3_ksl_key *)nghttp3_ksl_nth_node((IT)->ksl, (IT)->blk, (IT)->i)->key) 322 323 /* 324 * nghttp3_ksl_range_compar is an implementation of 325 * nghttp3_ksl_compar. lhs->ptr and rhs->ptr must point to 326 * nghttp3_range object and the function returns nonzero if (const 327 * nghttp3_range *)(lhs->ptr)->begin < (const nghttp3_range 328 * *)(rhs->ptr)->begin. 329 */ 330 int nghttp3_ksl_range_compar(const nghttp3_ksl_key *lhs, 331 const nghttp3_ksl_key *rhs); 332 333 /* 334 * nghttp3_ksl_range_exclusive_compar is an implementation of 335 * nghttp3_ksl_compar. lhs->ptr and rhs->ptr must point to 336 * nghttp3_range object and the function returns nonzero if (const 337 * nghttp3_range *)(lhs->ptr)->begin < (const nghttp3_range 338 * *)(rhs->ptr)->begin and the 2 ranges do not intersect. 339 */ 340 int nghttp3_ksl_range_exclusive_compar(const nghttp3_ksl_key *lhs, 341 const nghttp3_ksl_key *rhs); 342 343 #endif /* NGHTTP3_KSL_H */ 344