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