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#include "nghttp3_objalloc.h"
38
39/*
40 * Skip List using single key instead of range.
41 */
42
43#define NGHTTP3_KSL_DEGR 16
44/* NGHTTP3_KSL_MAX_NBLK is the maximum number of nodes which a single
45   block can contain. */
46#define NGHTTP3_KSL_MAX_NBLK (2 * NGHTTP3_KSL_DEGR - 1)
47/* NGHTTP3_KSL_MIN_NBLK is the minimum number of nodes which a single
48   block other than root must contains. */
49#define NGHTTP3_KSL_MIN_NBLK (NGHTTP3_KSL_DEGR - 1)
50
51/*
52 * nghttp3_ksl_key represents key in nghttp3_ksl.
53 */
54typedef void nghttp3_ksl_key;
55
56typedef struct nghttp3_ksl_node nghttp3_ksl_node;
57
58typedef struct nghttp3_ksl_blk nghttp3_ksl_blk;
59
60/*
61 * nghttp3_ksl_node is a node which contains either nghttp3_ksl_blk or
62 * opaque data.  If a node is an internal node, it contains
63 * nghttp3_ksl_blk.  Otherwise, it has data.  The key is stored at the
64 * location starting at key.
65 */
66struct nghttp3_ksl_node {
67  union {
68    nghttp3_ksl_blk *blk;
69    void *data;
70  };
71  union {
72    uint64_t align;
73    /* key is a buffer to include key associated to this node.
74       Because the length of key is unknown until nghttp3_ksl_init is
75       called, the actual buffer will be allocated after this
76       field. */
77    uint8_t key[1];
78  };
79};
80
81/*
82 * nghttp3_ksl_blk contains nghttp3_ksl_node objects.
83 */
84struct nghttp3_ksl_blk {
85  union {
86    struct {
87      /* next points to the next block if leaf field is nonzero. */
88      nghttp3_ksl_blk *next;
89      /* prev points to the previous block if leaf field is
90         nonzero. */
91      nghttp3_ksl_blk *prev;
92      /* n is the number of nodes this object contains in nodes. */
93      uint32_t n;
94      /* leaf is nonzero if this block contains leaf nodes. */
95      uint32_t leaf;
96      union {
97        uint64_t align;
98        /* nodes is a buffer to contain NGHTTP3_KSL_MAX_NBLK
99           nghttp3_ksl_node objects.  Because nghttp3_ksl_node object
100           is allocated along with the additional variable length key
101           storage, the size of buffer is unknown until
102           nghttp3_ksl_init is called. */
103        uint8_t nodes[1];
104      };
105    };
106
107    nghttp3_opl_entry oplent;
108  };
109};
110
111nghttp3_objalloc_def(ksl_blk, nghttp3_ksl_blk, oplent);
112
113/*
114 * nghttp3_ksl_compar is a function type which returns nonzero if key
115 * |lhs| should be placed before |rhs|.  It returns 0 otherwise.
116 */
117typedef int (*nghttp3_ksl_compar)(const nghttp3_ksl_key *lhs,
118                                  const nghttp3_ksl_key *rhs);
119
120typedef struct nghttp3_ksl nghttp3_ksl;
121
122typedef struct nghttp3_ksl_it nghttp3_ksl_it;
123
124/*
125 * nghttp3_ksl_it is a forward iterator to iterate nodes.
126 */
127struct nghttp3_ksl_it {
128  const nghttp3_ksl *ksl;
129  nghttp3_ksl_blk *blk;
130  size_t i;
131};
132
133/*
134 * nghttp3_ksl is a deterministic paged skip list.
135 */
136struct nghttp3_ksl {
137  nghttp3_objalloc blkalloc;
138  /* head points to the root block. */
139  nghttp3_ksl_blk *head;
140  /* front points to the first leaf block. */
141  nghttp3_ksl_blk *front;
142  /* back points to the last leaf block. */
143  nghttp3_ksl_blk *back;
144  nghttp3_ksl_compar compar;
145  size_t n;
146  /* keylen is the size of key */
147  size_t keylen;
148  /* nodelen is the actual size of nghttp3_ksl_node including key
149     storage. */
150  size_t nodelen;
151};
152
153/*
154 * nghttp3_ksl_init initializes |ksl|.  |compar| specifies compare
155 * function.  |keylen| is the length of key.
156 */
157void nghttp3_ksl_init(nghttp3_ksl *ksl, nghttp3_ksl_compar compar,
158                      size_t keylen, const nghttp3_mem *mem);
159
160/*
161 * nghttp3_ksl_free frees resources allocated for |ksl|.  If |ksl| is
162 * NULL, this function does nothing.  It does not free the memory
163 * region pointed by |ksl| itself.
164 */
165void nghttp3_ksl_free(nghttp3_ksl *ksl);
166
167/*
168 * nghttp3_ksl_insert inserts |key| with its associated |data|.  On
169 * successful insertion, the iterator points to the inserted node is
170 * stored in |*it|.
171 *
172 * This function returns 0 if it succeeds, or one of the following
173 * negative error codes:
174 *
175 * NGHTTP3_ERR_NOMEM
176 *   Out of memory.
177 * NGHTTP3_ERR_INVALID_ARGUMENT
178 *   |key| already exists.
179 */
180int nghttp3_ksl_insert(nghttp3_ksl *ksl, nghttp3_ksl_it *it,
181                       const nghttp3_ksl_key *key, void *data);
182
183/*
184 * nghttp3_ksl_remove removes the |key| from |ksl|.
185 *
186 * This function assigns the iterator to |*it|, which points to the
187 * node which is located at the right next of the removed node if |it|
188 * is not NULL.  If |key| is not found, no deletion takes place and
189 * the return value of nghttp3_ksl_end(ksl) is assigned to |*it|.
190 *
191 * This function returns 0 if it succeeds, or one of the following
192 * negative error codes:
193 *
194 * NGHTTP3_ERR_INVALID_ARGUMENT
195 *   |key| does not exist.
196 */
197int nghttp3_ksl_remove(nghttp3_ksl *ksl, nghttp3_ksl_it *it,
198                       const nghttp3_ksl_key *key);
199
200/*
201 * nghttp3_ksl_remove_hint removes the |key| from |ksl|.  |hint| must
202 * point to the same node denoted by |key|.  |hint| is used to remove
203 * a node efficiently in some cases.  Other than that, it behaves
204 * exactly like nghttp3_ksl_remove.  |it| and |hint| can point to the
205 * same object.
206 */
207int nghttp3_ksl_remove_hint(nghttp3_ksl *ksl, nghttp3_ksl_it *it,
208                            const nghttp3_ksl_it *hint,
209                            const nghttp3_ksl_key *key);
210
211/*
212 * nghttp3_ksl_lower_bound returns the iterator which points to the
213 * first node which has the key which is equal to |key| or the last
214 * node which satisfies !compar(&node->key, key).  If there is no such
215 * node, it returns the iterator which satisfies nghttp3_ksl_it_end(it)
216 * != 0.
217 */
218nghttp3_ksl_it nghttp3_ksl_lower_bound(nghttp3_ksl *ksl,
219                                       const nghttp3_ksl_key *key);
220
221/*
222 * nghttp3_ksl_lower_bound_compar works like nghttp3_ksl_lower_bound,
223 * but it takes custom function |compar| to do lower bound search.
224 */
225nghttp3_ksl_it nghttp3_ksl_lower_bound_compar(nghttp3_ksl *ksl,
226                                              const nghttp3_ksl_key *key,
227                                              nghttp3_ksl_compar compar);
228
229/*
230 * nghttp3_ksl_update_key replaces the key of nodes which has |old_key|
231 * with |new_key|.  |new_key| must be strictly greater than the
232 * previous node and strictly smaller than the next node.
233 */
234void nghttp3_ksl_update_key(nghttp3_ksl *ksl, const nghttp3_ksl_key *old_key,
235                            const nghttp3_ksl_key *new_key);
236
237/*
238 * nghttp3_ksl_begin returns the iterator which points to the first
239 * node.  If there is no node in |ksl|, it returns the iterator which
240 * satisfies nghttp3_ksl_it_end(it) != 0.
241 */
242nghttp3_ksl_it nghttp3_ksl_begin(const nghttp3_ksl *ksl);
243
244/*
245 * nghttp3_ksl_end returns the iterator which points to the node
246 * following the last node.  The returned object satisfies
247 * nghttp3_ksl_it_end().  If there is no node in |ksl|, it returns the
248 * iterator which satisfies nghttp3_ksl_it_begin(it) != 0.
249 */
250nghttp3_ksl_it nghttp3_ksl_end(const nghttp3_ksl *ksl);
251
252/*
253 * nghttp3_ksl_len returns the number of elements stored in |ksl|.
254 */
255size_t nghttp3_ksl_len(nghttp3_ksl *ksl);
256
257/*
258 * nghttp3_ksl_clear removes all elements stored in |ksl|.
259 */
260void nghttp3_ksl_clear(nghttp3_ksl *ksl);
261
262/*
263 * nghttp3_ksl_nth_node returns the |n|th node under |blk|.
264 */
265#define nghttp3_ksl_nth_node(KSL, BLK, N)                                      \
266  ((nghttp3_ksl_node *)(void *)((BLK)->nodes + (KSL)->nodelen * (N)))
267
268/*
269 * nghttp3_ksl_print prints its internal state in stderr.  It assumes
270 * that the key is of type int64_t.  This function should be used for
271 * the debugging purpose only.
272 */
273void nghttp3_ksl_print(nghttp3_ksl *ksl);
274
275/*
276 * nghttp3_ksl_it_init initializes |it|.
277 */
278void nghttp3_ksl_it_init(nghttp3_ksl_it *it, const nghttp3_ksl *ksl,
279                         nghttp3_ksl_blk *blk, size_t i);
280
281/*
282 * nghttp3_ksl_it_get returns the data associated to the node which
283 * |it| points to.  It is undefined to call this function when
284 * nghttp3_ksl_it_end(it) returns nonzero.
285 */
286#define nghttp3_ksl_it_get(IT)                                                 \
287  nghttp3_ksl_nth_node((IT)->ksl, (IT)->blk, (IT)->i)->data
288
289/*
290 * nghttp3_ksl_it_next advances the iterator by one.  It is undefined
291 * if this function is called when nghttp3_ksl_it_end(it) returns
292 * nonzero.
293 */
294#define nghttp3_ksl_it_next(IT)                                                \
295  (++(IT)->i == (IT)->blk->n && (IT)->blk->next                                \
296       ? ((IT)->blk = (IT)->blk->next, (IT)->i = 0)                            \
297       : 0)
298
299/*
300 * nghttp3_ksl_it_prev moves backward the iterator by one.  It is
301 * undefined if this function is called when nghttp3_ksl_it_begin(it)
302 * returns nonzero.
303 */
304void nghttp3_ksl_it_prev(nghttp3_ksl_it *it);
305
306/*
307 * nghttp3_ksl_it_end returns nonzero if |it| points to the beyond the
308 * last node.
309 */
310#define nghttp3_ksl_it_end(IT)                                                 \
311  ((IT)->blk->n == (IT)->i && (IT)->blk->next == NULL)
312
313/*
314 * nghttp3_ksl_it_begin returns nonzero if |it| points to the first
315 * node.  |it| might satisfy both nghttp3_ksl_it_begin(&it) and
316 * nghttp3_ksl_it_end(&it) if the skip list has no node.
317 */
318int nghttp3_ksl_it_begin(const nghttp3_ksl_it *it);
319
320/*
321 * nghttp3_ksl_key returns the key of the node which |it| points to.
322 * It is undefined to call this function when nghttp3_ksl_it_end(it)
323 * returns nonzero.
324 */
325#define nghttp3_ksl_it_key(IT)                                                 \
326  ((nghttp3_ksl_key *)nghttp3_ksl_nth_node((IT)->ksl, (IT)->blk, (IT)->i)->key)
327
328/*
329 * nghttp3_ksl_range_compar is an implementation of
330 * nghttp3_ksl_compar.  lhs->ptr and rhs->ptr must point to
331 * nghttp3_range object and the function returns nonzero if (const
332 * nghttp3_range *)(lhs->ptr)->begin < (const nghttp3_range
333 * *)(rhs->ptr)->begin.
334 */
335int nghttp3_ksl_range_compar(const nghttp3_ksl_key *lhs,
336                             const nghttp3_ksl_key *rhs);
337
338/*
339 * nghttp3_ksl_range_exclusive_compar is an implementation of
340 * nghttp3_ksl_compar.  lhs->ptr and rhs->ptr must point to
341 * nghttp3_range object and the function returns nonzero if (const
342 * nghttp3_range *)(lhs->ptr)->begin < (const nghttp3_range
343 * *)(rhs->ptr)->begin and the 2 ranges do not intersect.
344 */
345int nghttp3_ksl_range_exclusive_compar(const nghttp3_ksl_key *lhs,
346                                       const nghttp3_ksl_key *rhs);
347
348#endif /* NGHTTP3_KSL_H */
349