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