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
|
/*
* Copyright © 2022 Michael Smith <mikesmiffy128@gmail.com>
*
* Permission to use, copy, modify, and/or distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED “AS IS” AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
* REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
* AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
* INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
* LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
* OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
* PERFORMANCE OF THIS SOFTWARE.
*/
#ifndef INC_SKIPLIST_H
#define INC_SKIPLIST_H
#include <stdlib.h>
#include "../intdefs.h"
#include "../os.h"
#ifdef _WIN32
static inline int _skiplist_ffs(uint x) {
uint ret;
// on Windows, sizeof(ulong) == sizeof(uint)
if (_BitScanForward((ulong *)&ret, x)) return ret + 1; else return 0;
}
#else
#include <strings.h>
#define _skiplist_ffs ffs
#endif
// WARNING: this is a really hacked-up version of the skiplist.h from cbits in
// order to support windows. It probably isn't a good idea to plop straight into
// your own use case.
#if defined(__GNUC__) || defined(__clang__)
#define _skiplist_unused __attribute__((unused)) // heck off gcc
#else
#define _skiplist_unused
#endif
// NOTE: using xoroshiro128++, a comparatively bad (i.e. non-cryptographic) prng
// for the sake of simplicity; original cbits skiplist.h relies on libcpoly to
// get arc4random() everywhere but since we're only using this at build time
// that seemed like a silly dependency to bother with.
//#define _skiplist_rng arc4random
// ALSO NOTE: the PRNG code here is *decidedly not* thread safe. again, this
// isn't a problem for our use case. just keep it in mind if reusing this header
// for something else. or ideally, don't reuse this header for something else...
static inline uvlong _skiplist_rotl(const uvlong x, int k) {
return (x << k) | (x >> (64 - k));
}
_skiplist_unused static uvlong _skiplist_rng(void) {
static uvlong s[2];
static bool init = false;
if (!init) { os_randombytes(s, sizeof(s)); init = true; }
uvlong s0 = s[0], s1 = s[1];
uvlong ret = _skiplist_rotl(s0 * 5, 7) * 9;
s1 ^= s0;
s[0] = _skiplist_rotl(s0, 24) ^ s1 ^ (s1 << 16);
s[1] = _skiplist_rotl(s1, 37);
return ret;
}
/*
* Declares the skiplist header struct skiplist_hdr##name, but none of the
* associated functions. Use when the structure needs to be passed around in
* some way but actual operations on the list are a private implementation
* detail. Otherwise, see DECL_SKIPLIST below.
*/
#define DECL_SKIPLIST_TYPE(name, dtype, ktype, levels) \
typedef dtype _skiplist_dt_##name; \
typedef ktype _skiplist_kt_##name; \
enum { skiplist_lvls_##name = (levels) }; \
struct skiplist_hdr_##name { dtype *x[levels]; };
/*
* Declares the skiplist header struct skiplist_hdr_##name, with functions
* skiplist_{get,del,pop,insert}_##name for operating on the list. A single
* occurrence of DEF_SKIPLIST is required to actually implement the
* functions.
*
* This macro implies DECL_SKIPLIST_TYPE (both should not be used).
*
* mod should be either static or extern.
*
* dtype should be the struct type that the skiplist header will be embedded in,
* forming the linked structure.
*
* ktype should be the type of the struct member used for comparisons, for
* example int or char *.
*
* levels should be the number of levels in each node. 4 is probably a
* reasonable number, depending on the size of the structure and how many
* entries need to be stored and looked up.
*
* The resulting get, del, pop and insert functions are hopefully self-
* explanatory - get and del return the relevant node or a null pointer if
* no such node is found.
*/
#define DECL_SKIPLIST(mod, name, dtype, ktype, levels) \
DECL_SKIPLIST_TYPE(name, dtype, ktype, levels) \
\
_skiplist_unused mod dtype *skiplist_get_##name(struct skiplist_hdr_##name *l, \
ktype k); \
_skiplist_unused mod dtype *skiplist_del_##name(struct skiplist_hdr_##name *l, \
ktype k); \
_skiplist_unused mod dtype *skiplist_pop_##name(struct skiplist_hdr_##name *l); \
_skiplist_unused mod void skiplist_insert_##name(struct skiplist_hdr_##name *l, \
ktype k, dtype *node);
/*
* Implements the functions corresponding to a skiplist - must come after
* DECL_SKIPLIST with the same modifier and name.
*
* compfunc should be a function declared as follows (or an equivalent macro):
* int cf(dtype *x, ktype y);
*
* hdrfunc should be a function declared as follows (or an equivalent macro):
* struct skiplist_hdr_##name *hf(dtype *l);
*/
#define DEF_SKIPLIST(mod, name, compfunc, hdrfunc) \
static inline int _skiplist_lvl_##name(void) { \
int i; \
/* for 2 levels we get 1 50% of the time, 2 25% of the time, 0 25% of the
time. loop if 0 to distribute this evenly (this gets less likely the more
levels there are: at 4 levels, only loops 6% of the time) */ \
while (!(i = _skiplist_ffs(_skiplist_rng() & \
((1 << skiplist_lvls_##name) - 1)))); \
/* ffs gives bit positions as 1-N but we actually want an array index */ \
return i - 1; \
} \
\
_skiplist_unused \
mod _skiplist_dt_##name *skiplist_get_##name(struct skiplist_hdr_##name *l, \
_skiplist_kt_##name k) { \
for (int cmp, lvl = skiplist_lvls_##name - 1; lvl > -1; --lvl) { \
while (l->x[lvl] && (cmp = compfunc(l->x[lvl], k)) < 0) { \
l = hdrfunc(l->x[lvl]); \
} \
/* NOTE: cmp can be uninitialised here, but only if the list is
completely empty, in which case we'd return 0 anyway - so it doesn't
actually matter! */ \
if (cmp == 0) return l->x[lvl]; \
} \
/* reached the end, no match */ \
return 0; \
} \
\
_skiplist_unused \
_skiplist_dt_##name *skiplist_del_##name(struct skiplist_hdr_##name *l, \
_skiplist_kt_##name k) { \
_skiplist_dt_##name *ret = 0; \
/* ALSO NOTE: in *this* case, cmp DOES need to be initialised to prevent a
possible null-deref via hdrfunc(l->x[lvl])->x */ \
for (int cmp = 1, lvl = skiplist_lvls_##name - 1; lvl > -1; --lvl) { \
while (l->x[lvl] && (cmp = compfunc(l->x[lvl], k)) < 0) { \
l = hdrfunc(l->x[lvl]); \
} \
if (cmp == 0) { \
ret = l->x[lvl]; \
/* just shift each link by 1 */ \
l->x[lvl] = hdrfunc(l->x[lvl])->x[0]; \
/* ... and update every level of links via loop */ \
} \
} \
/* reached the end, return whatever was found */ \
return ret; \
} \
\
_skiplist_unused \
mod _skiplist_dt_##name *skiplist_pop_##name(struct skiplist_hdr_##name *l) { \
_skiplist_dt_##name *cur = l->x[0]; \
if (!cur) return 0; \
l->x[0] = hdrfunc(cur)->x[0]; \
for (int lvl = 1; lvl < skiplist_lvls_##name; ++lvl) { \
if (l->x[lvl]) l->x[lvl] = hdrfunc(l->x[lvl])->x[lvl]; \
} \
return cur; \
} \
\
_skiplist_unused \
mod void skiplist_insert_##name(struct skiplist_hdr_##name *l, \
_skiplist_kt_##name k, _skiplist_dt_##name *node) { \
/* note: higher levels are unset but also skipped in other searches */ \
int inslvl = _skiplist_lvl_##name(); \
for (int lvl = skiplist_lvls_##name - 1; lvl > -1; --lvl) { \
while (l->x[lvl] && compfunc(l->x[lvl], k) < 0) { \
l = hdrfunc(l->x[lvl]); \
} \
if (lvl <= inslvl) { \
hdrfunc(node)->x[lvl] = l->x[lvl]; \
l->x[lvl] = node; \
} \
} \
} \
#endif
// vi: sw=4 ts=4 noet tw=80 cc=80
|
