From 70148cca0463cc45408401a0f2d76ba805d0a157 Mon Sep 17 00:00:00 2001 From: Nicholas Noll Date: Sun, 24 May 2020 15:31:38 -0700 Subject: feat: added set data structure to libn macro --- include/libn/macro/map.h | 180 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 180 insertions(+) (limited to 'include') diff --git a/include/libn/macro/map.h b/include/libn/macro/map.h index bbd4a91..4724d1e 100644 --- a/include/libn/macro/map.h +++ b/include/libn/macro/map.h @@ -224,3 +224,183 @@ static const double __ac_HASH_UPPER = 0.77; --map->size; \ } \ } + +/* 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, free, h) \ + free(h, set->keys); \ + free(h, set->flags); \ + free(h, 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, alloc, free, h) \ + 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 = alloc(h, __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 = alloc(h, new_n_buckets, sizeof(key_t)); \ + if (!new_keys) { \ + free(h, new_flags); \ + return -1; \ + } \ + memcpy(new_keys, set->keys, sizeof(key_t) * set->n_buckets); \ + free(h, 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 = alloc(h, new_n_buckets, sizeof(key_t)); \ + memcpy(new_keys, set->keys, sizeof(key_t) * set->n_buckets); \ + free(h, set->keys); \ + set->keys = new_keys; \ + } \ + free(h, 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; \ + } \ + } -- cgit v1.2.1