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 */
53typedef void ngtcp2_ksl_key;
54
55typedef struct ngtcp2_ksl_node ngtcp2_ksl_node;
56
57typedef 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 */
65struct 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 */
83struct 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
109ngtcp2_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 */
115typedef int (*ngtcp2_ksl_compar)(const ngtcp2_ksl_key *lhs,
116                                 const ngtcp2_ksl_key *rhs);
117
118typedef struct ngtcp2_ksl ngtcp2_ksl;
119
120typedef struct ngtcp2_ksl_it ngtcp2_ksl_it;
121
122/*
123 * ngtcp2_ksl_it is a forward iterator to iterate nodes.
124 */
125struct 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 */
134struct 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 */
155void 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 */
163void 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 */
178int 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 */
195int 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 */
205int 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 */
216ngtcp2_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 */
223ngtcp2_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 */
232void 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 */
240ngtcp2_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 */
248ngtcp2_ksl_it ngtcp2_ksl_end(const ngtcp2_ksl *ksl);
249
250/*
251 * ngtcp2_ksl_len returns the number of elements stored in |ksl|.
252 */
253size_t ngtcp2_ksl_len(ngtcp2_ksl *ksl);
254
255/*
256 * ngtcp2_ksl_clear removes all elements stored in |ksl|.
257 */
258void 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 */
271void ngtcp2_ksl_print(ngtcp2_ksl *ksl);
272
273/*
274 * ngtcp2_ksl_it_init initializes |it|.
275 */
276void 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 */
302void 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 */
316int 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 */
332int 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 */
342int ngtcp2_ksl_range_exclusive_compar(const ngtcp2_ksl_key *lhs,
343                                      const ngtcp2_ksl_key *rhs);
344
345#endif /* NGTCP2_KSL_H */
346