diff options
Diffstat (limited to 'src/build/skiplist.h')
| -rw-r--r-- | src/build/skiplist.h | 205 |
1 files changed, 205 insertions, 0 deletions
diff --git a/src/build/skiplist.h b/src/build/skiplist.h new file mode 100644 index 0000000..b747d89 --- /dev/null +++ b/src/build/skiplist.h @@ -0,0 +1,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 |