From c8e1e71eb526475dd431443345262c2e5a627831 Mon Sep 17 00:00:00 2001 From: Nicholas Noll Date: Sat, 23 Oct 2021 11:17:25 -0700 Subject: chore(rename): libn -> base --- include/base/macro/map.h | 400 +++++++++++++++++++++++++++++++++++++++++++++ include/base/macro/qsort.h | 91 +++++++++++ 2 files changed, 491 insertions(+) create mode 100644 include/base/macro/map.h create mode 100644 include/base/macro/qsort.h (limited to 'include/base') diff --git a/include/base/macro/map.h b/include/base/macro/map.h new file mode 100644 index 0000000..7c2f7ae --- /dev/null +++ b/include/base/macro/map.h @@ -0,0 +1,400 @@ +#pragma once + +/* + * Based on khash.h + * Modified to make control more granular and similar to QSORT + */ + +static const double __ac_HASH_UPPER = 0.77; + +#define _roundup32(x) \ + (--(x), (x) |= (x) >> 1, (x) |= (x) >> 2, (x) |= (x) >> 4, (x) |= (x) >> 8, \ + (x) |= (x) >> 16, ++(x)) + +#define __ac_isempty(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 2) +#define __ac_isdel(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 1) +#define __ac_iseither(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 3) +#define __ac_set_isdel_false(flag, i) \ + (flag[i >> 4] &= ~(1ul << ((i & 0xfU) << 1))) +#define __ac_set_isempty_false(flag, i) \ + (flag[i >> 4] &= ~(2ul << ((i & 0xfU) << 1))) +#define __ac_set_isboth_false(flag, i) \ + (flag[i >> 4] &= ~(3ul << ((i & 0xfU) << 1))) +#define __ac_set_isdel_true(flag, i) (flag[i >> 4] |= 1ul << ((i & 0xfU) << 1)) + +#define __ac_fsize(m) ((m) < 16 ? 1 : (m) >> 4) + +#define MAP_STRUCT_BODY(key_t, val_t) \ + int32 n_buckets, size, n_occupied, upper_bound; \ + int32 *flags; \ + key_t *keys; \ + val_t *vals; + +#define MAP_MAKE(type, h, alloc) \ + type *map; \ + map = alloc((h), 1, sizeof(*map)); \ + return map + +#define MAP_FREE(map, mem, heap) \ + mem.free(heap, map->keys); \ + mem.free(heap, map->flags); \ + mem.free(heap, map->vals); \ + mem.free(heap, map); + +#define MAP_RESET(map) \ + if (map && map->flags) { \ + memset(map->flags, 0xaa, __ac_fsize(map->n_buckets) * sizeof(int32)); \ + map->size = map->n_occupied = 0; \ + } + +#define MAP_GET(i, map, key, hashfunc, equalfunc ) \ + int32 k, last, mask, step; \ + if (map->n_buckets) { \ + k = 0; \ + i = 0; \ + last = 0; \ + mask = 0; \ + step = 0; \ + mask = map->n_buckets - 1; \ + k = hashfunc(key); \ + i = k & mask; \ + last = i; \ + while (!__ac_isempty(map->flags, i) && \ + (__ac_isdel(map->flags, i) || !equalfunc(map->keys[i], key))) { \ + i = (i + (++step)) & mask; \ + if (i == last) { \ + i = map->n_buckets; \ + break; \ + } \ + } \ + if (i < map->n_buckets && __ac_iseither(map->flags, i)) \ + i = map->n_buckets; \ + } else \ + i = 0; + +#define MAP_GROW(map, key_t, val_t, new_n_buckets, hashfunc, mem, heap) \ + int32 *new_flags = nil; \ + int32 j = 1; \ + { \ + _roundup32(new_n_buckets); \ + if (new_n_buckets < 4) \ + new_n_buckets = 4; \ + if (map->size >= (int32)(new_n_buckets * __ac_HASH_UPPER + 0.5)) \ + j = 0; \ + else { \ + new_flags = mem.alloc(heap, __ac_fsize(new_n_buckets), sizeof(int32)); \ + if (!new_flags) return -1; \ + memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(int32)); \ + if (map->n_buckets < new_n_buckets) { /* expand */ \ + key_t *new_keys = mem.alloc(heap, new_n_buckets, sizeof(key_t)); \ + if (!new_keys) { \ + mem.free(heap, new_flags); \ + return -1; \ + } \ + memcpy(new_keys, map->keys, sizeof(key_t) * map->n_buckets); \ + mem.free(heap, map->keys); \ + map->keys = new_keys; \ + val_t *new_vals = mem.alloc(heap, new_n_buckets, sizeof(val_t)); \ + if (!new_vals) { \ + mem.free(heap, new_flags); \ + return -1; \ + } \ + memcpy(new_vals, map->vals, sizeof(val_t) * map->n_buckets); \ + mem.free(heap, map->vals); \ + map->vals = new_vals; \ + } \ + } \ + } \ + if (j) { /* rehashing is needed */ \ + for (j = 0; j != map->n_buckets; ++j) { \ + if (__ac_iseither(map->flags, j) == 0) { \ + key_t key = map->keys[j]; \ + val_t val; \ + int32 new_mask; \ + new_mask = new_n_buckets - 1; \ + val = map->vals[j]; \ + __ac_set_isdel_true(map->flags, j); \ + while (1) { \ + int32 k, i, step = 0; \ + k = hashfunc(key); \ + i = k & new_mask; \ + while (!__ac_isempty(new_flags, i)) \ + i = (i + (++step)) & new_mask; \ + __ac_set_isempty_false(new_flags, i); \ + if (i < map->n_buckets && __ac_iseither(map->flags, i) == 0) { \ + { \ + key_t tmp = map->keys[i]; \ + map->keys[i] = key; \ + key = tmp; \ + } \ + { \ + val_t tmp = map->vals[i]; \ + map->vals[i] = val; \ + val = tmp; \ + } \ + __ac_set_isdel_true(map->flags, i); \ + } else { \ + map->keys[i] = key; \ + map->vals[i] = val; \ + break; \ + } \ + } \ + } \ + } \ + if (map->n_buckets > new_n_buckets) { /* shrink the hash table */ \ + key_t *new_keys = mem.alloc(heap, new_n_buckets, sizeof(key_t)); \ + memcpy(new_keys, map->keys, sizeof(key_t) * map->n_buckets); \ + mem.free(heap, map->keys); \ + map->keys = new_keys; \ + \ + val_t *new_vals = mem.alloc(heap, new_n_buckets, sizeof(val_t)); \ + memcpy(new_vals, map->vals, sizeof(val_t) * map->n_buckets); \ + mem.free(heap, map->vals); \ + map->vals = new_vals; \ + } \ + mem.free(heap, map->flags); /* free the working space */ \ + map->flags = new_flags; \ + map->n_buckets = new_n_buckets; \ + map->n_occupied = map->size; \ + map->upper_bound = (int32)(map->n_buckets * __ac_HASH_UPPER + 0.5); \ + } \ + return 0; + +#define MAP_PUT(map, key, val, hashfunc, equalfunc, resizefunc, err) \ + int32 x = 0; \ + if (map->n_occupied >= map->upper_bound) { \ + if (map->n_buckets > (map->size << 1)) { \ + if (resizefunc(map, map->n_buckets - 1) < 0) { \ + *err = -1; \ + return map->n_buckets; \ + } \ + } else if (resizefunc(map, map->n_buckets + 1) < 0) { \ + *err = -1; \ + return map->n_buckets; \ + } \ + } \ + \ + { \ + int32 k, i, site, last, mask = map->n_buckets - 1, step = 0; \ + x = site = map->n_buckets; \ + k = hashfunc(key); \ + i = k & mask; \ + if (__ac_isempty(map->flags, i)) \ + x = i; /* for speed up */ \ + else { \ + last = i; \ + while (!__ac_isempty(map->flags, i) && \ + (__ac_isdel(map->flags, i) || !equalfunc(map->keys[i], key))) { \ + if (__ac_isdel(map->flags, i)) \ + site = i; \ + i = (i + (++step)) & mask; \ + if (i == last) { \ + x = site; \ + break; \ + } \ + } \ + if (x == map->n_buckets) { \ + if (__ac_isempty(map->flags, i) && site != map->n_buckets) \ + x = site; \ + else \ + x = i; \ + } \ + } \ + } \ + if (__ac_isempty(map->flags, x)) { /* not present at all */ \ + map->keys[x] = key; \ + __ac_set_isboth_false(map->flags, x); \ + ++map->size; \ + ++map->n_occupied; \ + *err = 1; \ + } else if (__ac_isdel(map->flags, x)) { /* deleted */ \ + map->keys[x] = key; \ + __ac_set_isboth_false(map->flags, x); \ + ++map->size; \ + } else \ + *err = 0; \ + return x; + +#define MAP_DEL(map, x) \ + if (x != map->n_buckets && !__ac_iseither(map->flags, x)) { \ + __ac_set_isdel_true(map->flags, x); \ + --map->size; \ + } + +#define KEY_EXIST(m, x) (!__ac_iseither((m)->flags, (x))) + +/* set macro */ + +#define SET_STRUCT_BODY(key_t) \ + int32 n_buckets, size, n_occupied, upper_bound; \ + int32 *flags; \ + key_t *keys \ + +#define SET_MAKE(type, h, alloc) \ + type *set; \ + set = alloc((h), 1, sizeof(*set)); \ + return set + +#define SET_FREE(set, mem, heap) \ + mem.free(heap, set->keys); \ + mem.free(heap, set->flags); \ + mem.free(heap, set) + +#define SET_RESET(set) \ + if (set && set->flags) { \ + memset(set->flags, 0xaa, __ac_fsize(set->n_buckets) * sizeof(int32)); \ + set->size = set->n_occupied = 0; \ + } + +#define SET_GET(i, set, key, hashfunc, equalfunc ) \ + int32 k, last, mask, step; \ + if (set->n_buckets) { \ + k = 0; \ + i = 0; \ + last = 0; \ + mask = 0; \ + step = 0; \ + mask = set->n_buckets - 1; \ + k = hashfunc(key); \ + i = k & mask; \ + last = i; \ + while (!__ac_isempty(set->flags, i) && \ + (__ac_isdel(set->flags, i) || !equalfunc(set->keys[i], key))) { \ + i = (i + (++step)) & mask; \ + if (i == last) { \ + i = set->n_buckets; \ + break; \ + } \ + } \ + if (i < set->n_buckets && __ac_iseither(set->flags, i)) \ + i = set->n_buckets; \ + } else \ + i = 0; + +#define SET_GROW(set, key_t, new_n_buckets, hashfunc, mem, heap) \ + int32 *new_flags = nil; \ + int32 j = 1; \ + { \ + _roundup32(new_n_buckets); \ + if (new_n_buckets < 4) \ + new_n_buckets = 4; \ + if (set->size >= (int32)(new_n_buckets * __ac_HASH_UPPER + 0.5)) \ + j = 0; \ + else { \ + new_flags = mem.alloc(heap, __ac_fsize(new_n_buckets), sizeof(int32)); \ + if (!new_flags) return -1; \ + memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(int32)); \ + if (set->n_buckets < new_n_buckets) { /* expand */ \ + key_t *new_keys = mem.alloc(heap, new_n_buckets, sizeof(key_t)); \ + if (!new_keys) { \ + mem.free(heap, new_flags); \ + return -1; \ + } \ + memcpy(new_keys, set->keys, sizeof(key_t) * set->n_buckets); \ + mem.free(heap, set->keys); \ + set->keys = new_keys; \ + } \ + } \ + } \ + if (j) { /* rehashing is needed */ \ + for (j = 0; j != set->n_buckets; ++j) { \ + if (__ac_iseither(set->flags, j) == 0) { \ + key_t key = set->keys[j]; \ + int32 new_mask; \ + new_mask = new_n_buckets - 1; \ + __ac_set_isdel_true(set->flags, j); \ + while (1) { \ + int32 k, i, step = 0; \ + k = hashfunc(key); \ + i = k & new_mask; \ + while (!__ac_isempty(new_flags, i)) \ + i = (i + (++step)) & new_mask; \ + __ac_set_isempty_false(new_flags, i); \ + if (i < set->n_buckets && __ac_iseither(set->flags, i) == 0) { \ + { \ + key_t tmp = set->keys[i]; \ + set->keys[i] = key; \ + key = tmp; \ + } \ + __ac_set_isdel_true(set->flags, i); \ + } else { \ + set->keys[i] = key; \ + break; \ + } \ + } \ + } \ + } \ + if (set->n_buckets > new_n_buckets) { /* shrink the hash table */ \ + key_t *new_keys = mem.alloc(heap, new_n_buckets, sizeof(key_t)); \ + memcpy(new_keys, set->keys, sizeof(key_t) * set->n_buckets); \ + mem.free(heap, set->keys); \ + set->keys = new_keys; \ + } \ + mem.free(heap, set->flags); /* free the working space */ \ + set->flags = new_flags; \ + set->n_buckets = new_n_buckets; \ + set->n_occupied = set->size; \ + set->upper_bound = (int32)(set->n_buckets * __ac_HASH_UPPER + 0.5); \ + } \ + return 0; + +#define SET_PUT(set, key, hashfunc, equalfunc, resizefunc, err) \ + int32 x = 0; \ + if (set->n_occupied >= set->upper_bound) { \ + if (set->n_buckets > (set->size << 1)) { \ + if (resizefunc(set, set->n_buckets - 1) < 0) { \ + *err = -1; \ + return set->n_buckets; \ + } \ + } else if (resizefunc(set, set->n_buckets + 1) < 0) { \ + *err = -1; \ + return set->n_buckets; \ + } \ + } \ + \ + { \ + int32 k, i, site, last, mask = set->n_buckets - 1, step = 0; \ + x = site = set->n_buckets; \ + k = hashfunc(key); \ + i = k & mask; \ + if (__ac_isempty(set->flags, i)) \ + x = i; /* for speed up */ \ + else { \ + last = i; \ + while (!__ac_isempty(set->flags, i) && \ + (__ac_isdel(set->flags, i) || !equalfunc(set->keys[i], key))) { \ + if (__ac_isdel(set->flags, i)) \ + site = i; \ + i = (i + (++step)) & mask; \ + if (i == last) { \ + x = site; \ + break; \ + } \ + } \ + if (x == set->n_buckets) { \ + if (__ac_isempty(set->flags, i) && site != set->n_buckets) \ + x = site; \ + else \ + x = i; \ + } \ + } \ + } \ + if (__ac_isempty(set->flags, x)) { /* not present at all */ \ + set->keys[x] = key; \ + __ac_set_isboth_false(set->flags, x); \ + ++set->size; \ + ++set->n_occupied; \ + *err = 1; \ + } else if (__ac_isdel(set->flags, x)) { /* deleted */ \ + set->keys[x] = key; \ + __ac_set_isboth_false(set->flags, x); \ + ++set->size; \ + } else \ + *err = 0; \ + return x + +#define SET_DEL(set, x) \ + if (x != set->n_buckets && !__ac_iseither(set->flags, x)) { \ + __ac_set_isdel_true(set->flags, x); \ + --set->size; \ + } diff --git a/include/base/macro/qsort.h b/include/base/macro/qsort.h new file mode 100644 index 0000000..6d0acaa --- /dev/null +++ b/include/base/macro/qsort.h @@ -0,0 +1,91 @@ +#pragma once + +/* + * Nicholas Noll (2020) + * Straight implementation of Sedgewick's median qsort + * #ref: "Implementing Quicksort Programs" (1978) + * + * @LEN: name of parameter length + * @QLESS: name of function that computes array[i] < array[j] + * should return a boolean + * @QSWAP: name of function that swaps array[i] <-> array[j] + * this could swap multiple arrays + * + * NOTE: This can perform on strided arrays. + * Make sure to use parens liberally to ensure hygeine! + */ + +#define QSORT(LEN, QLESS, QSWAP) \ + int i, j, m, r, l; \ + struct { \ + int i, j; \ + } *sp, base[48]; \ + sp = base; \ + \ + l = 1; \ + r = LEN-1; \ + \ + if (LEN <= 14) goto ENDOUTER; \ +OUTERLOOP: \ + SWAP((l+r)/2, l+1); \ + \ + if (QLESS(r, l+1)) QSWAP(r, l+1); \ + if (QLESS(r, l)) QSWAP(r, l); \ + if (QLESS(l, l+1)) QSWAP(l, l+1); \ + \ + i = l+1; \ + j = r; \ + \ +INNERLOOP: \ + do ++i; while(QLESS(i, l)); \ + do --j; while(QLESS(l, j)); \ + if (j < i) goto ENDINNER; \ + QSWAP(i, j); \ + goto INNERLOOP; \ + \ +ENDINNER: \ + QSWAP(l, j); \ + \ + if (MAX(j-l, r-i+1) <= 14) { \ + if (sp == base) { \ + goto ENDOUTER; \ + } else { \ + l = sp[-1].i; \ + r = sp[-1].j; \ + sp--; \ + } \ + } else { \ + if (MIN(j-l, r-i+1) <= 14) { \ + if (j-l > r-i+1) { \ + l = l; \ + r = j-1; \ + } else { \ + l = i; \ + r = r; \ + } \ + } else { \ + if (j-l > r-i+1) { \ + sp->i = l; \ + sp->j = j-1; \ + sp++; \ + \ + l = i; \ + r = r; \ + } else { \ + sp->i = i; \ + sp->j = r; \ + sp++; \ + \ + l = l; \ + r = j-1; \ + } \ + } \ + } \ + goto OUTERLOOP; \ + \ +ENDOUTER: \ + for (i = 1; i < LEN; i++) { \ + for (j = i; j > 0 && QLESS(j, j-1); j--) { \ + QSWAP(j, j-1); \ + } \ + } -- cgit v1.2.1