diff options
Diffstat (limited to 'src/build/skiplist.h')
| -rw-r--r-- | src/build/skiplist.h | 206 |
1 files changed, 0 insertions, 206 deletions
diff --git a/src/build/skiplist.h b/src/build/skiplist.h deleted file mode 100644 index ab6a920..0000000 --- a/src/build/skiplist.h +++ /dev/null @@ -1,206 +0,0 @@ -/* - * Copyright © 2024 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) { - uchar _BitScanForward(ulong *idx, ulong mask); - 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 |