diff options
author | Nicholas Noll <nnoll523@gmail.com> | 2021-10-23 11:17:25 -0700 |
---|---|---|
committer | Nicholas Noll <nnoll523@gmail.com> | 2021-10-26 11:11:57 -0700 |
commit | c8e1e71eb526475dd431443345262c2e5a627831 (patch) | |
tree | ea9f7bcbba18a13f7ba8b32fcb1433ac2f4dd8b4 /include/base/macro/map.h | |
parent | 40f4c7305a041d4214df117491593898d04d0134 (diff) |
chore(rename): libn -> base
Diffstat (limited to 'include/base/macro/map.h')
-rw-r--r-- | include/base/macro/map.h | 400 |
1 files changed, 400 insertions, 0 deletions
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; \ + } |