/src/samba/third_party/ngtcp2/lib/ngtcp2_ksl.h

Source
/*
 * ngtcp2
 *
 * 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 NGTCP2_KSL_H
#define NGTCP2_KSL_H

#ifdef HAVE_CONFIG_H
#  include <config.h>
#endif /* defined(HAVE_CONFIG_H) */

#include <stdlib.h>

#include <ngtcp2/ngtcp2.h>

#include "ngtcp2_objalloc.h"
#include "ngtcp2_range.h"

#define NGTCP2_KSL_DEGR 16
/* NGTCP2_KSL_MAX_NBLK is the maximum number of nodes which a single
   block can contain. */
#define NGTCP2_KSL_MAX_NBLK (2 * NGTCP2_KSL_DEGR)
/* NGTCP2_KSL_MIN_NBLK is the minimum number of nodes which a single
   block other than root must contain. */
#define NGTCP2_KSL_MIN_NBLK NGTCP2_KSL_DEGR

/*
 * ngtcp2_ksl_key represents key in ngtcp2_ksl.
 */
typedef void ngtcp2_ksl_key;

typedef struct ngtcp2_ksl_node ngtcp2_ksl_node;

typedef struct ngtcp2_ksl_blk ngtcp2_ksl_blk;

/*
 * ngtcp2_ksl_node is a node which contains either ngtcp2_ksl_blk or
 * opaque data.  If a node is an internal node, it contains
 * ngtcp2_ksl_blk.  Otherwise, it has data.
 */
struct ngtcp2_ksl_node {
  union {
    ngtcp2_ksl_blk *blk;
    void *data;
  };
};

/*
 * ngtcp2_ksl_blk contains ngtcp2_ksl_node objects.
 */
struct ngtcp2_ksl_blk {
  union {
    struct {
      /* next points to the next block if leaf field is nonzero. */
      ngtcp2_ksl_blk *next;
      /* prev points to the previous block if leaf field is
         nonzero. */
      ngtcp2_ksl_blk *prev;
      ngtcp2_ksl_node nodes[NGTCP2_KSL_MAX_NBLK];
      /* keys is a pointer to the buffer to include
         NGTCP2_KSL_MAX_NBLK keys.  Because the length of key is
         unknown until ngtcp2_ksl_init is called, the actual buffer
         will be allocated after this object. */
      uint8_t *keys;
      /* n is the number of nodes this object contains in nodes. */
      uint32_t n;
      /* aligned_keylen is the length of the single key including
         alignment. */
      uint16_t aligned_keylen;
      /* leaf is nonzero if this block contains leaf nodes. */
      uint8_t leaf;
    };

    ngtcp2_opl_entry oplent;
  };
};

ngtcp2_objalloc_decl(ksl_blk, ngtcp2_ksl_blk, oplent)

/*
 * ngtcp2_ksl_compar is a function type which returns nonzero if key
 * |lhs| should be placed before |rhs|.  It returns 0 otherwise.
 */
typedef int (*ngtcp2_ksl_compar)(const ngtcp2_ksl_key *lhs,
                                 const ngtcp2_ksl_key *rhs);

typedef struct ngtcp2_ksl ngtcp2_ksl;

/*
 * ngtcp2_ksl_search is a function to search for the first element in
 * |blk|->nodes which is not ordered before |key|.  It returns the
 * index of such element.  It returns |blk|->n if there is no such
 * element.
 */
typedef size_t (*ngtcp2_ksl_search)(const ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk,
                                    const ngtcp2_ksl_key *key);

/*
 * ngtcp2_ksl_search_def is a macro to implement ngtcp2_ksl_search
 * with COMPAR which is supposed to be ngtcp2_ksl_compar.
 */
#define ngtcp2_ksl_search_def(NAME, COMPAR)                                    \
  static size_t ksl_##NAME##_search(                                           \
    const ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, const ngtcp2_ksl_key *key) {   \
    size_t i;                                                                  \
    uint8_t *node_key;                                                         \
                                                                               \
    for (i = 0, node_key = blk->keys; i < blk->n && COMPAR(node_key, key);     \
         ++i, node_key += ksl->aligned_keylen)                                 \
      ;                                                                        \
                                                                               \
    return i;                                                                  \
  }

typedef struct ngtcp2_ksl_it ngtcp2_ksl_it;

/*
 * ngtcp2_ksl_it is a bidirectional iterator to iterate nodes.
 */
struct ngtcp2_ksl_it {
  ngtcp2_ksl_blk *blk;
  size_t i;
};

/*
 * ngtcp2_ksl is a deterministic paged skip list.
 */
struct ngtcp2_ksl {
  ngtcp2_objalloc blkalloc;
  /* root points to the root block. */
  ngtcp2_ksl_blk *root;
  /* front points to the first leaf block. */
  ngtcp2_ksl_blk *front;
  /* back points to the last leaf block. */
  ngtcp2_ksl_blk *back;
  ngtcp2_ksl_compar compar;
  ngtcp2_ksl_search search;
  /* n is the number of elements stored. */
  size_t n;
  /* keylen is the size of key */
  size_t keylen;
  size_t aligned_keylen;
};

/*
 * ngtcp2_ksl_init initializes |ksl|.  |compar| specifies compare
 * function.  |search| is a search function which must use |compar|.
 * |keylen| is the length of key and must be at least
 * sizeof(uint64_t).
 */
void ngtcp2_ksl_init(ngtcp2_ksl *ksl, ngtcp2_ksl_compar compar,
                     ngtcp2_ksl_search search, size_t keylen,
                     const ngtcp2_mem *mem);

/*
 * ngtcp2_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 ngtcp2_ksl_free(ngtcp2_ksl *ksl);

/*
 * ngtcp2_ksl_insert inserts |key| with its associated |data|.  On
 * successful insertion, the iterator points to the inserted node is
 * stored in |*it| if |it| is not NULL.
 *
 * This function returns 0 if it succeeds, or one of the following
 * negative error codes:
 *
 * NGTCP2_ERR_NOMEM
 *     Out of memory.
 * NGTCP2_ERR_INVALID_ARGUMENT
 *     |key| already exists.
 */
int ngtcp2_ksl_insert(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it,
                      const ngtcp2_ksl_key *key, void *data);

/*
 * ngtcp2_ksl_remove removes the |key| from |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.  If |key| is not found, no deletion takes place and
 * the return value of ngtcp2_ksl_end(ksl) is assigned to |*it| if
 * |it| is not NULL.
 *
 * This function returns 0 if it succeeds, or one of the following
 * negative error codes:
 *
 * NGTCP2_ERR_INVALID_ARGUMENT
 *     |key| does not exist.
 */
int ngtcp2_ksl_remove(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it,
                      const ngtcp2_ksl_key *key);

/*
 * ngtcp2_ksl_remove_hint removes the |key| from |ksl|.  |hint| must
 * point to the same node denoted by |key|.  |hint| is used to remove
 * a node efficiently in some cases.  Other than that, it behaves
 * exactly like ngtcp2_ksl_remove.  |it| and |hint| can point to the
 * same object.
 */
int ngtcp2_ksl_remove_hint(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it,
                           const ngtcp2_ksl_it *hint,
                           const ngtcp2_ksl_key *key);

/*
 * ngtcp2_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 ngtcp2_ksl_it_end(it)
 * != 0.
 */
ngtcp2_ksl_it ngtcp2_ksl_lower_bound(const ngtcp2_ksl *ksl,
                                     const ngtcp2_ksl_key *key);

/*
 * ngtcp2_ksl_lower_bound_search works like ngtcp2_ksl_lower_bound,
 * but it takes custom function |search| to do lower bound search.
 */
ngtcp2_ksl_it ngtcp2_ksl_lower_bound_search(const ngtcp2_ksl *ksl,
                                            const ngtcp2_ksl_key *key,
                                            ngtcp2_ksl_search search);

/*
 * ngtcp2_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 ngtcp2_ksl_update_key(ngtcp2_ksl *ksl, const ngtcp2_ksl_key *old_key,
                           const ngtcp2_ksl_key *new_key);

/*
 * ngtcp2_ksl_begin returns the iterator which points to the first
 * node.  If there is no node in |ksl|, it returns the iterator which
 * satisfies both ngtcp2_ksl_it_begin(it) != 0 and
 * ngtcp2_ksl_it_end(it) != 0.
 */
ngtcp2_ksl_it ngtcp2_ksl_begin(const ngtcp2_ksl *ksl);

/*
 * ngtcp2_ksl_end returns the iterator which points to the node
 * following the last node.  The returned object satisfies
 * ngtcp2_ksl_it_end().  If there is no node in |ksl|, it returns the
 * iterator which satisfies ngtcp2_ksl_it_begin(it) != 0 and
 * ngtcp2_ksl_it_end(it) != 0.
 */
ngtcp2_ksl_it ngtcp2_ksl_end(const ngtcp2_ksl *ksl);

/*
 * ngtcp2_ksl_len returns the number of elements stored in |ksl|.
 */
size_t ngtcp2_ksl_len(const ngtcp2_ksl *ksl);

/*
 * ngtcp2_ksl_clear removes all elements stored in |ksl|.
 */
void ngtcp2_ksl_clear(ngtcp2_ksl *ksl);

/*
 * ngtcp2_ksl_blk_nth_key returns the |n|th key under |blk|.
 */
static inline const ngtcp2_ksl_key *
ngtcp2_ksl_blk_nth_key(const ngtcp2_ksl_blk *blk, size_t n) {
  return blk->keys + n * blk->aligned_keylen;
}

#ifndef WIN32
/*
 * ngtcp2_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 ngtcp2_ksl_print(const ngtcp2_ksl *ksl);
#endif /* !defined(WIN32) */

/*
 * ngtcp2_ksl_it_init initializes |it|.
 */
void ngtcp2_ksl_it_init(ngtcp2_ksl_it *it, ngtcp2_ksl_blk *blk, size_t i);

/*
 * ngtcp2_ksl_it_get returns the data associated to the node which
 * |it| points to.  It is undefined to call this function when
 * ngtcp2_ksl_it_end(it) returns nonzero.
 */
static inline void *ngtcp2_ksl_it_get(const ngtcp2_ksl_it *it) {
  return it->blk->nodes[it->i].data;
}

/*
 * ngtcp2_ksl_it_next advances the iterator by one.  It is undefined
 * if this function is called when ngtcp2_ksl_it_end(it) returns
 * nonzero.
 */
static inline void ngtcp2_ksl_it_next(ngtcp2_ksl_it *it) {
  if (++it->i == it->blk->n && it->blk->next) {
    it->blk = it->blk->next;
    it->i = 0;
  }
}

/*
 * ngtcp2_ksl_it_prev moves backward the iterator by one.  It is
 * undefined if this function is called when ngtcp2_ksl_it_begin(it)
 * returns nonzero.
 */
void ngtcp2_ksl_it_prev(ngtcp2_ksl_it *it);

/*
 * ngtcp2_ksl_it_end returns nonzero if |it| points to the one beyond
 * the last node.
 */
static inline int ngtcp2_ksl_it_end(const ngtcp2_ksl_it *it) {
  return it->blk->n == it->i && it->blk->next == NULL;
}

/*
 * ngtcp2_ksl_it_begin returns nonzero if |it| points to the first
 * node.  |it| might satisfy both ngtcp2_ksl_it_begin(it) != 0 and
 * ngtcp2_ksl_it_end(it) != 0 if the skip list has no node.
 */
int ngtcp2_ksl_it_begin(const ngtcp2_ksl_it *it);

/*
 * ngtcp2_ksl_key returns the key of the node which |it| points to.
 * It is undefined to call this function when ngtcp2_ksl_it_end(it)
 * returns nonzero.
 */
static inline const ngtcp2_ksl_key *ngtcp2_ksl_it_key(const ngtcp2_ksl_it *it) {
  return ngtcp2_ksl_blk_nth_key(it->blk, it->i);
}

/*
 * ngtcp2_ksl_range_compar is an implementation of ngtcp2_ksl_compar.
 * |lhs| and |rhs| must point to ngtcp2_range object, and the function
 * returns nonzero if ((const ngtcp2_range *)lhs)->begin < ((const
 * ngtcp2_range *)rhs)->begin.
 */
static inline int ngtcp2_ksl_range_compar(const ngtcp2_ksl_key *lhs,
                                          const ngtcp2_ksl_key *rhs) {
  const ngtcp2_range *a = (const ngtcp2_range *)lhs,
                     *b = (const ngtcp2_range *)rhs;
  return a->begin < b->begin;
}

/*
 * ngtcp2_ksl_range_search is an implementation of ngtcp2_ksl_search
 * that uses ngtcp2_ksl_range_compar.
 */
size_t ngtcp2_ksl_range_search(const ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk,
                               const ngtcp2_ksl_key *key);

/*
 * ngtcp2_ksl_range_exclusive_compar is an implementation of
 * ngtcp2_ksl_compar.  |lhs| and |rhs| must point to ngtcp2_range
 * object, and the function returns nonzero if ((const ngtcp2_range
 * *)lhs)->begin < ((const ngtcp2_range *)rhs)->begin, and the 2
 * ranges do not intersect.
 */
static inline int ngtcp2_ksl_range_exclusive_compar(const ngtcp2_ksl_key *lhs,
                                                    const ngtcp2_ksl_key *rhs) {
  const ngtcp2_range *a = (const ngtcp2_range *)lhs,
                     *b = (const ngtcp2_range *)rhs;
  return a->begin < b->begin && !(ngtcp2_max_uint64(a->begin, b->begin) <
                                  ngtcp2_min_uint64(a->end, b->end));
}

/*
 * ngtcp2_ksl_range_exclusive_search is an implementation of
 * ngtcp2_ksl_search that uses ngtcp2_ksl_range_exclusive_compar.
 */
size_t ngtcp2_ksl_range_exclusive_search(const ngtcp2_ksl *ksl,
                                         ngtcp2_ksl_blk *blk,
                                         const ngtcp2_ksl_key *key);

/*
 * ngtcp2_ksl_uint64_less is an implementation of ngtcp2_ksl_compar.
 * |lhs| and |rhs| must point to uint64_t objects, and the function
 * returns nonzero if *(uint64_t *)|lhs| < *(uint64_t *)|rhs|.
 */
static inline int ngtcp2_ksl_uint64_less(const ngtcp2_ksl_key *lhs,
                                         const ngtcp2_ksl_key *rhs) {
  return *(const uint64_t *)lhs < *(const uint64_t *)rhs;
}

/*
 * ngtcp2_ksl_uint64_less_search is an implementation of
 * ngtcp2_ksl_search that uses ngtcp2_ksl_uint64_less.
 */
size_t ngtcp2_ksl_uint64_less_search(const ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk,
                                     const ngtcp2_ksl_key *key);

/*
 * ngtcp2_ksl_int64_greater is an implementation of ngtcp2_ksl_compar.
 * |lhs| and |rhs| must point to int64_t objects, and the function
 * returns nonzero if *(int64_t *)|lhs| > *(int64_t *)|rhs|.
 */
static inline int ngtcp2_ksl_int64_greater(const ngtcp2_ksl_key *lhs,
                                           const ngtcp2_ksl_key *rhs) {
  return *(const int64_t *)lhs > *(const int64_t *)rhs;
}

/*
 * ngtcp2_ksl_int64_greater_search is an implementation of
 * ngtcp2_ksl_search that uses ngtcp2_ksl_int64_greater.
 */
size_t ngtcp2_ksl_int64_greater_search(const ngtcp2_ksl *ksl,
                                       ngtcp2_ksl_blk *blk,
                                       const ngtcp2_ksl_key *key);

#endif /* !defined(NGTCP2_KSL_H) */

Coverage Report

Created: 2026-05-24 06:47

Line	Count	Source
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 /* defined(HAVE_CONFIG_H) */
31
32		#include <stdlib.h>
33
34		#include <ngtcp2/ngtcp2.h>
35
36		#include "ngtcp2_objalloc.h"
37		#include "ngtcp2_range.h"
38
39	0	#define NGTCP2_KSL_DEGR 16
40		/* NGTCP2_KSL_MAX_NBLK is the maximum number of nodes which a single
41		block can contain. */
42	0	#define NGTCP2_KSL_MAX_NBLK (2 * NGTCP2_KSL_DEGR)
43		/* NGTCP2_KSL_MIN_NBLK is the minimum number of nodes which a single
44		block other than root must contain. */
45	0	#define NGTCP2_KSL_MIN_NBLK NGTCP2_KSL_DEGR
46
47		/*
48		* ngtcp2_ksl_key represents key in ngtcp2_ksl.
49		*/
50		typedef void ngtcp2_ksl_key;
51
52		typedef struct ngtcp2_ksl_node ngtcp2_ksl_node;
53
54		typedef struct ngtcp2_ksl_blk ngtcp2_ksl_blk;
55
56		/*
57		* ngtcp2_ksl_node is a node which contains either ngtcp2_ksl_blk or
58		* opaque data. If a node is an internal node, it contains
59		* ngtcp2_ksl_blk. Otherwise, it has data.
60		*/
61		struct ngtcp2_ksl_node {
62		union {
63		ngtcp2_ksl_blk *blk;
64		void *data;
65		};
66		};
67
68		/*
69		* ngtcp2_ksl_blk contains ngtcp2_ksl_node objects.
70		*/
71		struct ngtcp2_ksl_blk {
72		union {
73		struct {
74		/* next points to the next block if leaf field is nonzero. */
75		ngtcp2_ksl_blk *next;
76		/* prev points to the previous block if leaf field is
77		nonzero. */
78		ngtcp2_ksl_blk *prev;
79		ngtcp2_ksl_node nodes[NGTCP2_KSL_MAX_NBLK];
80		/* keys is a pointer to the buffer to include
81		NGTCP2_KSL_MAX_NBLK keys. Because the length of key is
82		unknown until ngtcp2_ksl_init is called, the actual buffer
83		will be allocated after this object. */
84		uint8_t *keys;
85		/* n is the number of nodes this object contains in nodes. */
86		uint32_t n;
87		/* aligned_keylen is the length of the single key including
88		alignment. */
89		uint16_t aligned_keylen;
90		/* leaf is nonzero if this block contains leaf nodes. */
91		uint8_t leaf;
92		};
93
94		ngtcp2_opl_entry oplent;
95		};
96		};
97
98		ngtcp2_objalloc_decl(ksl_blk, ngtcp2_ksl_blk, oplent)
99
100		/*
101		* ngtcp2_ksl_compar is a function type which returns nonzero if key
102		* \|lhs\| should be placed before \|rhs\|. It returns 0 otherwise.
103		*/
104		typedef int (ngtcp2_ksl_compar)(const ngtcp2_ksl_key lhs,
105		const ngtcp2_ksl_key *rhs);
106
107		typedef struct ngtcp2_ksl ngtcp2_ksl;
108
109		/*
110		* ngtcp2_ksl_search is a function to search for the first element in
111		* \|blk\|->nodes which is not ordered before \|key\|. It returns the
112		* index of such element. It returns \|blk\|->n if there is no such
113		* element.
114		*/
115		typedef size_t (ngtcp2_ksl_search)(const ngtcp2_ksl ksl, ngtcp2_ksl_blk *blk,
116		const ngtcp2_ksl_key *key);
117
118		/*
119		* ngtcp2_ksl_search_def is a macro to implement ngtcp2_ksl_search
120		* with COMPAR which is supposed to be ngtcp2_ksl_compar.
121		*/
122		#define ngtcp2_ksl_search_def(NAME, COMPAR) \
123		static size_t ksl_##NAME##_search( \
124	0	const ngtcp2_ksl ksl, ngtcp2_ksl_blk blk, const ngtcp2_ksl_key *key) { \
125	0	size_t i; \
126	0	uint8_t *node_key; \
127	0	\
128	0	for (i = 0, node_key = blk->keys; i < blk->n && COMPAR(node_key, key); \
129	0	++i, node_key += ksl->aligned_keylen) \
130	0	; \
131	0	\
132	0	return i; \
133	0	} Unexecuted instantiation: ngtcp2_conn.c:ksl_cid_less_search Unexecuted instantiation: ngtcp2_ksl.c:ksl_range_search Unexecuted instantiation: ngtcp2_ksl.c:ksl_range_exclusive_search Unexecuted instantiation: ngtcp2_ksl.c:ksl_uint64_less_search Unexecuted instantiation: ngtcp2_ksl.c:ksl_int64_greater_search
134
135		typedef struct ngtcp2_ksl_it ngtcp2_ksl_it;
136
137		/*
138		* ngtcp2_ksl_it is a bidirectional iterator to iterate nodes.
139		*/
140		struct ngtcp2_ksl_it {
141		ngtcp2_ksl_blk *blk;
142		size_t i;
143		};
144
145		/*
146		* ngtcp2_ksl is a deterministic paged skip list.
147		*/
148		struct ngtcp2_ksl {
149		ngtcp2_objalloc blkalloc;
150		/* root points to the root block. */
151		ngtcp2_ksl_blk *root;
152		/* front points to the first leaf block. */
153		ngtcp2_ksl_blk *front;
154		/* back points to the last leaf block. */
155		ngtcp2_ksl_blk *back;
156		ngtcp2_ksl_compar compar;
157		ngtcp2_ksl_search search;
158		/* n is the number of elements stored. */
159		size_t n;
160		/* keylen is the size of key */
161		size_t keylen;
162		size_t aligned_keylen;
163		};
164
165		/*
166		* ngtcp2_ksl_init initializes \|ksl\|. \|compar\| specifies compare
167		* function. \|search\| is a search function which must use \|compar\|.
168		* \|keylen\| is the length of key and must be at least
169		* sizeof(uint64_t).
170		*/
171		void ngtcp2_ksl_init(ngtcp2_ksl *ksl, ngtcp2_ksl_compar compar,
172		ngtcp2_ksl_search search, size_t keylen,
173		const ngtcp2_mem *mem);
174
175		/*
176		* ngtcp2_ksl_free frees resources allocated for \|ksl\|. If \|ksl\| is
177		* NULL, this function does nothing. It does not free the memory
178		* region pointed by \|ksl\| itself.
179		*/
180		void ngtcp2_ksl_free(ngtcp2_ksl *ksl);
181
182		/*
183		* ngtcp2_ksl_insert inserts \|key\| with its associated \|data\|. On
184		* successful insertion, the iterator points to the inserted node is
185		* stored in \|*it\| if \|it\| is not NULL.
186		*
187		* This function returns 0 if it succeeds, or one of the following
188		* negative error codes:
189		*
190		* NGTCP2_ERR_NOMEM
191		* Out of memory.
192		* NGTCP2_ERR_INVALID_ARGUMENT
193		* \|key\| already exists.
194		*/
195		int ngtcp2_ksl_insert(ngtcp2_ksl ksl, ngtcp2_ksl_it it,
196		const ngtcp2_ksl_key key, void data);
197
198		/*
199		* ngtcp2_ksl_remove removes the \|key\| from \|ksl\|.
200		*
201		* This function assigns the iterator to \|*it\|, which points to the
202		* node which is located at the right next of the removed node if \|it\|
203		* is not NULL. If \|key\| is not found, no deletion takes place and
204		* the return value of ngtcp2_ksl_end(ksl) is assigned to \|*it\| if
205		* \|it\| is not NULL.
206		*
207		* This function returns 0 if it succeeds, or one of the following
208		* negative error codes:
209		*
210		* NGTCP2_ERR_INVALID_ARGUMENT
211		* \|key\| does not exist.
212		*/
213		int ngtcp2_ksl_remove(ngtcp2_ksl ksl, ngtcp2_ksl_it it,
214		const ngtcp2_ksl_key *key);
215
216		/*
217		* ngtcp2_ksl_remove_hint removes the \|key\| from \|ksl\|. \|hint\| must
218		* point to the same node denoted by \|key\|. \|hint\| is used to remove
219		* a node efficiently in some cases. Other than that, it behaves
220		* exactly like ngtcp2_ksl_remove. \|it\| and \|hint\| can point to the
221		* same object.
222		*/
223		int ngtcp2_ksl_remove_hint(ngtcp2_ksl ksl, ngtcp2_ksl_it it,
224		const ngtcp2_ksl_it *hint,
225		const ngtcp2_ksl_key *key);
226
227		/*
228		* ngtcp2_ksl_lower_bound returns the iterator which points to the
229		* first node which has the key which is equal to \|key\| or the last
230		* node which satisfies !compar(&node->key, key). If there is no such
231		* node, it returns the iterator which satisfies ngtcp2_ksl_it_end(it)
232		* != 0.
233		*/
234		ngtcp2_ksl_it ngtcp2_ksl_lower_bound(const ngtcp2_ksl *ksl,
235		const ngtcp2_ksl_key *key);
236
237		/*
238		* ngtcp2_ksl_lower_bound_search works like ngtcp2_ksl_lower_bound,
239		* but it takes custom function \|search\| to do lower bound search.
240		*/
241		ngtcp2_ksl_it ngtcp2_ksl_lower_bound_search(const ngtcp2_ksl *ksl,
242		const ngtcp2_ksl_key *key,
243		ngtcp2_ksl_search search);
244
245		/*
246		* ngtcp2_ksl_update_key replaces the key of nodes which has \|old_key\|
247		* with \|new_key\|. \|new_key\| must be strictly greater than the
248		* previous node and strictly smaller than the next node.
249		*/
250		void ngtcp2_ksl_update_key(ngtcp2_ksl ksl, const ngtcp2_ksl_key old_key,
251		const ngtcp2_ksl_key *new_key);
252
253		/*
254		* ngtcp2_ksl_begin returns the iterator which points to the first
255		* node. If there is no node in \|ksl\|, it returns the iterator which
256		* satisfies both ngtcp2_ksl_it_begin(it) != 0 and
257		* ngtcp2_ksl_it_end(it) != 0.
258		*/
259		ngtcp2_ksl_it ngtcp2_ksl_begin(const ngtcp2_ksl *ksl);
260
261		/*
262		* ngtcp2_ksl_end returns the iterator which points to the node
263		* following the last node. The returned object satisfies
264		* ngtcp2_ksl_it_end(). If there is no node in \|ksl\|, it returns the
265		* iterator which satisfies ngtcp2_ksl_it_begin(it) != 0 and
266		* ngtcp2_ksl_it_end(it) != 0.
267		*/
268		ngtcp2_ksl_it ngtcp2_ksl_end(const ngtcp2_ksl *ksl);
269
270		/*
271		* ngtcp2_ksl_len returns the number of elements stored in \|ksl\|.
272		*/
273		size_t ngtcp2_ksl_len(const ngtcp2_ksl *ksl);
274
275		/*
276		* ngtcp2_ksl_clear removes all elements stored in \|ksl\|.
277		*/
278		void ngtcp2_ksl_clear(ngtcp2_ksl *ksl);
279
280		/*
281		* ngtcp2_ksl_blk_nth_key returns the \|n\|th key under \|blk\|.
282		*/
283		static inline const ngtcp2_ksl_key *
284	0	ngtcp2_ksl_blk_nth_key(const ngtcp2_ksl_blk *blk, size_t n) {
285	0	return blk->keys + n * blk->aligned_keylen;
286	0	} Unexecuted instantiation: ngtcp2_acktr.c:ngtcp2_ksl_blk_nth_key Unexecuted instantiation: ngtcp2_conn.c:ngtcp2_ksl_blk_nth_key Unexecuted instantiation: ngtcp2_gaptr.c:ngtcp2_ksl_blk_nth_key Unexecuted instantiation: ngtcp2_idtr.c:ngtcp2_ksl_blk_nth_key Unexecuted instantiation: ngtcp2_ksl.c:ngtcp2_ksl_blk_nth_key Unexecuted instantiation: ngtcp2_qlog.c:ngtcp2_ksl_blk_nth_key Unexecuted instantiation: ngtcp2_rob.c:ngtcp2_ksl_blk_nth_key Unexecuted instantiation: ngtcp2_rst.c:ngtcp2_ksl_blk_nth_key Unexecuted instantiation: ngtcp2_rtb.c:ngtcp2_ksl_blk_nth_key Unexecuted instantiation: ngtcp2_strm.c:ngtcp2_ksl_blk_nth_key
287
288		#ifndef WIN32
289		/*
290		* ngtcp2_ksl_print prints its internal state in stderr. It assumes
291		* that the key is of type int64_t. This function should be used for
292		* the debugging purpose only.
293		*/
294		void ngtcp2_ksl_print(const ngtcp2_ksl *ksl);
295		#endif /* !defined(WIN32) */
296
297		/*
298		* ngtcp2_ksl_it_init initializes \|it\|.
299		*/
300		void ngtcp2_ksl_it_init(ngtcp2_ksl_it it, ngtcp2_ksl_blk blk, size_t i);
301
302		/*
303		* ngtcp2_ksl_it_get returns the data associated to the node which
304		* \|it\| points to. It is undefined to call this function when
305		* ngtcp2_ksl_it_end(it) returns nonzero.
306		*/
307	0	static inline void ngtcp2_ksl_it_get(const ngtcp2_ksl_it it) {
308	0	return it->blk->nodes[it->i].data;
309	0	} Unexecuted instantiation: ngtcp2_acktr.c:ngtcp2_ksl_it_get Unexecuted instantiation: ngtcp2_conn.c:ngtcp2_ksl_it_get Unexecuted instantiation: ngtcp2_gaptr.c:ngtcp2_ksl_it_get Unexecuted instantiation: ngtcp2_idtr.c:ngtcp2_ksl_it_get Unexecuted instantiation: ngtcp2_ksl.c:ngtcp2_ksl_it_get Unexecuted instantiation: ngtcp2_qlog.c:ngtcp2_ksl_it_get Unexecuted instantiation: ngtcp2_rob.c:ngtcp2_ksl_it_get Unexecuted instantiation: ngtcp2_rst.c:ngtcp2_ksl_it_get Unexecuted instantiation: ngtcp2_rtb.c:ngtcp2_ksl_it_get Unexecuted instantiation: ngtcp2_strm.c:ngtcp2_ksl_it_get
310
311		/*
312		* ngtcp2_ksl_it_next advances the iterator by one. It is undefined
313		* if this function is called when ngtcp2_ksl_it_end(it) returns
314		* nonzero.
315		*/
316	0	static inline void ngtcp2_ksl_it_next(ngtcp2_ksl_it *it) {
317	0	if (++it->i == it->blk->n && it->blk->next) {
318	0	it->blk = it->blk->next;
319	0	it->i = 0;
320	0	}
321	0	} Unexecuted instantiation: ngtcp2_acktr.c:ngtcp2_ksl_it_next Unexecuted instantiation: ngtcp2_conn.c:ngtcp2_ksl_it_next Unexecuted instantiation: ngtcp2_gaptr.c:ngtcp2_ksl_it_next Unexecuted instantiation: ngtcp2_idtr.c:ngtcp2_ksl_it_next Unexecuted instantiation: ngtcp2_ksl.c:ngtcp2_ksl_it_next Unexecuted instantiation: ngtcp2_qlog.c:ngtcp2_ksl_it_next Unexecuted instantiation: ngtcp2_rob.c:ngtcp2_ksl_it_next Unexecuted instantiation: ngtcp2_rst.c:ngtcp2_ksl_it_next Unexecuted instantiation: ngtcp2_rtb.c:ngtcp2_ksl_it_next Unexecuted instantiation: ngtcp2_strm.c:ngtcp2_ksl_it_next
322
323		/*
324		* ngtcp2_ksl_it_prev moves backward the iterator by one. It is
325		* undefined if this function is called when ngtcp2_ksl_it_begin(it)
326		* returns nonzero.
327		*/
328		void ngtcp2_ksl_it_prev(ngtcp2_ksl_it *it);
329
330		/*
331		* ngtcp2_ksl_it_end returns nonzero if \|it\| points to the one beyond
332		* the last node.
333		*/
334	0	static inline int ngtcp2_ksl_it_end(const ngtcp2_ksl_it *it) {
335	0	return it->blk->n == it->i && it->blk->next == NULL;
336	0	} Unexecuted instantiation: ngtcp2_acktr.c:ngtcp2_ksl_it_end Unexecuted instantiation: ngtcp2_conn.c:ngtcp2_ksl_it_end Unexecuted instantiation: ngtcp2_gaptr.c:ngtcp2_ksl_it_end Unexecuted instantiation: ngtcp2_idtr.c:ngtcp2_ksl_it_end Unexecuted instantiation: ngtcp2_ksl.c:ngtcp2_ksl_it_end Unexecuted instantiation: ngtcp2_qlog.c:ngtcp2_ksl_it_end Unexecuted instantiation: ngtcp2_rob.c:ngtcp2_ksl_it_end Unexecuted instantiation: ngtcp2_rst.c:ngtcp2_ksl_it_end Unexecuted instantiation: ngtcp2_rtb.c:ngtcp2_ksl_it_end Unexecuted instantiation: ngtcp2_strm.c:ngtcp2_ksl_it_end
337
338		/*
339		* ngtcp2_ksl_it_begin returns nonzero if \|it\| points to the first
340		* node. \|it\| might satisfy both ngtcp2_ksl_it_begin(it) != 0 and
341		* ngtcp2_ksl_it_end(it) != 0 if the skip list has no node.
342		*/
343		int ngtcp2_ksl_it_begin(const ngtcp2_ksl_it *it);
344
345		/*
346		* ngtcp2_ksl_key returns the key of the node which \|it\| points to.
347		* It is undefined to call this function when ngtcp2_ksl_it_end(it)
348		* returns nonzero.
349		*/
350	0	static inline const ngtcp2_ksl_key ngtcp2_ksl_it_key(const ngtcp2_ksl_it it) {
351	0	return ngtcp2_ksl_blk_nth_key(it->blk, it->i);
352	0	} Unexecuted instantiation: ngtcp2_acktr.c:ngtcp2_ksl_it_key Unexecuted instantiation: ngtcp2_conn.c:ngtcp2_ksl_it_key Unexecuted instantiation: ngtcp2_gaptr.c:ngtcp2_ksl_it_key Unexecuted instantiation: ngtcp2_idtr.c:ngtcp2_ksl_it_key Unexecuted instantiation: ngtcp2_ksl.c:ngtcp2_ksl_it_key Unexecuted instantiation: ngtcp2_qlog.c:ngtcp2_ksl_it_key Unexecuted instantiation: ngtcp2_rob.c:ngtcp2_ksl_it_key Unexecuted instantiation: ngtcp2_rst.c:ngtcp2_ksl_it_key Unexecuted instantiation: ngtcp2_rtb.c:ngtcp2_ksl_it_key Unexecuted instantiation: ngtcp2_strm.c:ngtcp2_ksl_it_key
353
354		/*
355		* ngtcp2_ksl_range_compar is an implementation of ngtcp2_ksl_compar.
356		* \|lhs\| and \|rhs\| must point to ngtcp2_range object, and the function
357		* returns nonzero if ((const ngtcp2_range *)lhs)->begin < ((const
358		* ngtcp2_range *)rhs)->begin.
359		*/
360		static inline int ngtcp2_ksl_range_compar(const ngtcp2_ksl_key *lhs,
361	0	const ngtcp2_ksl_key *rhs) {
362	0	const ngtcp2_range a = (const ngtcp2_range )lhs,
363	0	b = (const ngtcp2_range )rhs;
364	0	return a->begin < b->begin;
365	0	} Unexecuted instantiation: ngtcp2_acktr.c:ngtcp2_ksl_range_compar Unexecuted instantiation: ngtcp2_conn.c:ngtcp2_ksl_range_compar Unexecuted instantiation: ngtcp2_gaptr.c:ngtcp2_ksl_range_compar Unexecuted instantiation: ngtcp2_idtr.c:ngtcp2_ksl_range_compar Unexecuted instantiation: ngtcp2_ksl.c:ngtcp2_ksl_range_compar Unexecuted instantiation: ngtcp2_qlog.c:ngtcp2_ksl_range_compar Unexecuted instantiation: ngtcp2_rob.c:ngtcp2_ksl_range_compar Unexecuted instantiation: ngtcp2_rst.c:ngtcp2_ksl_range_compar Unexecuted instantiation: ngtcp2_rtb.c:ngtcp2_ksl_range_compar Unexecuted instantiation: ngtcp2_strm.c:ngtcp2_ksl_range_compar
366
367		/*
368		* ngtcp2_ksl_range_search is an implementation of ngtcp2_ksl_search
369		* that uses ngtcp2_ksl_range_compar.
370		*/
371		size_t ngtcp2_ksl_range_search(const ngtcp2_ksl ksl, ngtcp2_ksl_blk blk,
372		const ngtcp2_ksl_key *key);
373
374		/*
375		* ngtcp2_ksl_range_exclusive_compar is an implementation of
376		* ngtcp2_ksl_compar. \|lhs\| and \|rhs\| must point to ngtcp2_range
377		* object, and the function returns nonzero if ((const ngtcp2_range
378		* )lhs)->begin < ((const ngtcp2_range )rhs)->begin, and the 2
379		* ranges do not intersect.
380		*/
381		static inline int ngtcp2_ksl_range_exclusive_compar(const ngtcp2_ksl_key *lhs,
382	0	const ngtcp2_ksl_key *rhs) {
383	0	const ngtcp2_range a = (const ngtcp2_range )lhs,
384	0	b = (const ngtcp2_range )rhs;
385	0	return a->begin < b->begin && !(ngtcp2_max_uint64(a->begin, b->begin) <
386	0	ngtcp2_min_uint64(a->end, b->end));
387	0	} Unexecuted instantiation: ngtcp2_acktr.c:ngtcp2_ksl_range_exclusive_compar Unexecuted instantiation: ngtcp2_conn.c:ngtcp2_ksl_range_exclusive_compar Unexecuted instantiation: ngtcp2_gaptr.c:ngtcp2_ksl_range_exclusive_compar Unexecuted instantiation: ngtcp2_idtr.c:ngtcp2_ksl_range_exclusive_compar Unexecuted instantiation: ngtcp2_ksl.c:ngtcp2_ksl_range_exclusive_compar Unexecuted instantiation: ngtcp2_qlog.c:ngtcp2_ksl_range_exclusive_compar Unexecuted instantiation: ngtcp2_rob.c:ngtcp2_ksl_range_exclusive_compar Unexecuted instantiation: ngtcp2_rst.c:ngtcp2_ksl_range_exclusive_compar Unexecuted instantiation: ngtcp2_rtb.c:ngtcp2_ksl_range_exclusive_compar Unexecuted instantiation: ngtcp2_strm.c:ngtcp2_ksl_range_exclusive_compar
388
389		/*
390		* ngtcp2_ksl_range_exclusive_search is an implementation of
391		* ngtcp2_ksl_search that uses ngtcp2_ksl_range_exclusive_compar.
392		*/
393		size_t ngtcp2_ksl_range_exclusive_search(const ngtcp2_ksl *ksl,
394		ngtcp2_ksl_blk *blk,
395		const ngtcp2_ksl_key *key);
396
397		/*
398		* ngtcp2_ksl_uint64_less is an implementation of ngtcp2_ksl_compar.
399		* \|lhs\| and \|rhs\| must point to uint64_t objects, and the function
400		* returns nonzero if (uint64_t )\|lhs\| < (uint64_t )\|rhs\|.
401		*/
402		static inline int ngtcp2_ksl_uint64_less(const ngtcp2_ksl_key *lhs,
403	0	const ngtcp2_ksl_key *rhs) {
404	0	return (const uint64_t )lhs < (const uint64_t )rhs;
405	0	} Unexecuted instantiation: ngtcp2_acktr.c:ngtcp2_ksl_uint64_less Unexecuted instantiation: ngtcp2_conn.c:ngtcp2_ksl_uint64_less Unexecuted instantiation: ngtcp2_gaptr.c:ngtcp2_ksl_uint64_less Unexecuted instantiation: ngtcp2_idtr.c:ngtcp2_ksl_uint64_less Unexecuted instantiation: ngtcp2_ksl.c:ngtcp2_ksl_uint64_less Unexecuted instantiation: ngtcp2_qlog.c:ngtcp2_ksl_uint64_less Unexecuted instantiation: ngtcp2_rob.c:ngtcp2_ksl_uint64_less Unexecuted instantiation: ngtcp2_rst.c:ngtcp2_ksl_uint64_less Unexecuted instantiation: ngtcp2_rtb.c:ngtcp2_ksl_uint64_less Unexecuted instantiation: ngtcp2_strm.c:ngtcp2_ksl_uint64_less
406
407		/*
408		* ngtcp2_ksl_uint64_less_search is an implementation of
409		* ngtcp2_ksl_search that uses ngtcp2_ksl_uint64_less.
410		*/
411		size_t ngtcp2_ksl_uint64_less_search(const ngtcp2_ksl ksl, ngtcp2_ksl_blk blk,
412		const ngtcp2_ksl_key *key);
413
414		/*
415		* ngtcp2_ksl_int64_greater is an implementation of ngtcp2_ksl_compar.
416		* \|lhs\| and \|rhs\| must point to int64_t objects, and the function
417		* returns nonzero if (int64_t )\|lhs\| > (int64_t )\|rhs\|.
418		*/
419		static inline int ngtcp2_ksl_int64_greater(const ngtcp2_ksl_key *lhs,
420	0	const ngtcp2_ksl_key *rhs) {
421	0	return (const int64_t )lhs > (const int64_t )rhs;
422	0	} Unexecuted instantiation: ngtcp2_acktr.c:ngtcp2_ksl_int64_greater Unexecuted instantiation: ngtcp2_conn.c:ngtcp2_ksl_int64_greater Unexecuted instantiation: ngtcp2_gaptr.c:ngtcp2_ksl_int64_greater Unexecuted instantiation: ngtcp2_idtr.c:ngtcp2_ksl_int64_greater Unexecuted instantiation: ngtcp2_ksl.c:ngtcp2_ksl_int64_greater Unexecuted instantiation: ngtcp2_qlog.c:ngtcp2_ksl_int64_greater Unexecuted instantiation: ngtcp2_rob.c:ngtcp2_ksl_int64_greater Unexecuted instantiation: ngtcp2_rst.c:ngtcp2_ksl_int64_greater Unexecuted instantiation: ngtcp2_rtb.c:ngtcp2_ksl_int64_greater Unexecuted instantiation: ngtcp2_strm.c:ngtcp2_ksl_int64_greater
423
424		/*
425		* ngtcp2_ksl_int64_greater_search is an implementation of
426		* ngtcp2_ksl_search that uses ngtcp2_ksl_int64_greater.
427		*/
428		size_t ngtcp2_ksl_int64_greater_search(const ngtcp2_ksl *ksl,
429		ngtcp2_ksl_blk *blk,
430		const ngtcp2_ksl_key *key);
431
432		#endif /* !defined(NGTCP2_KSL_H) */