From da4d127cbd65c35fee03411df66eadd34e7a999b Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 17 Jul 2020 11:51:07 +0200 Subject: Renamed chash.h to cmap.h and added cset.h --- examples/advanced.c | 2 +- examples/benchmark.c | 6 +- examples/complex.c | 8 +- examples/demos.c | 10 +- examples/geek1.c | 2 +- examples/geek2.c | 2 +- examples/geek3.c | 2 +- examples/geek4.c | 2 +- examples/geek5.c | 2 +- examples/geek6.c | 2 +- examples/mapmap.c | 2 +- examples/rngtest.c | 2 +- stc/chash.h | 376 --------------------------------------------------- stc/cmap.h | 376 +++++++++++++++++++++++++++++++++++++++++++++++++++ stc/crandom.h | 23 ++++ stc/cset.h | 28 ++++ 16 files changed, 448 insertions(+), 397 deletions(-) delete mode 100644 stc/chash.h create mode 100644 stc/cmap.h create mode 100644 stc/cset.h diff --git a/examples/advanced.c b/examples/advanced.c index e6b4ad2a..bd06c95d 100644 --- a/examples/advanced.c +++ b/examples/advanced.c @@ -11,7 +11,7 @@ * of the Viking struct first. */ #include -#include +#include #include // Viking view struct ----------------------- diff --git a/examples/benchmark.c b/examples/benchmark.c index 31b36b1a..cadb220c 100644 --- a/examples/benchmark.c +++ b/examples/benchmark.c @@ -1,6 +1,6 @@ -#include "../stc/crandom.h" -#include "../stc/cstr.h" -#include "../stc/chash.h" +#include +#include +#include #include "others/khash.h" #include diff --git a/examples/complex.c b/examples/complex.c index feb01db2..6cfed90c 100644 --- a/examples/complex.c +++ b/examples/complex.c @@ -1,7 +1,7 @@ -#include "../stc/cstr.h" -#include "../stc/chash.h" -#include "../stc/clist.h" -#include "../stc/carray.h" +#include +#include +#include +#include void check_destroy(float* v) {printf("destroy %g\n", *v);} diff --git a/examples/demos.c b/examples/demos.c index 037983e0..c10cace9 100644 --- a/examples/demos.c +++ b/examples/demos.c @@ -1,8 +1,8 @@ -#include "../stc/cvec.h" -#include "../stc/clist.h" -#include "../stc/carray.h" -#include "../stc/chash.h" -#include "../stc/cstr.h" +#include +#include +#include +#include +#include void stringdemo1() diff --git a/examples/geek1.c b/examples/geek1.c index 2aecaa8d..a8cf5b7b 100644 --- a/examples/geek1.c +++ b/examples/geek1.c @@ -10,7 +10,7 @@ int a[] = { 1, 2, 2, 3, 2, 4, 10 }; #ifndef __cplusplus // C program to implement the above approach #include -#include +#include declare_CMap(ii, int, int); diff --git a/examples/geek2.c b/examples/geek2.c index 7ce4fd2d..38916243 100644 --- a/examples/geek2.c +++ b/examples/geek2.c @@ -1,6 +1,6 @@ #ifndef __cplusplus -#include +#include #include declare_CMap_str(ss, CStr, cstr_destroy); diff --git a/examples/geek3.c b/examples/geek3.c index 4db84d13..3ea93fe5 100644 --- a/examples/geek3.c +++ b/examples/geek3.c @@ -1,6 +1,6 @@ // xx3.c -#include +#include #include declare_CMap_str(si, int); diff --git a/examples/geek4.c b/examples/geek4.c index 3f0f7f79..243301f9 100644 --- a/examples/geek4.c +++ b/examples/geek4.c @@ -33,7 +33,7 @@ Efficient Approach: For all the words of the first sentence, we can check if it #ifndef __cplusplus // C implementation of the approach -#include +#include #include #include diff --git a/examples/geek5.c b/examples/geek5.c index 0af114b7..2dbd0adb 100644 --- a/examples/geek5.c +++ b/examples/geek5.c @@ -17,7 +17,7 @@ Output: 0 #ifndef __cplusplus -#include +#include #include #include diff --git a/examples/geek6.c b/examples/geek6.c index 369867e9..ef86c3e8 100644 --- a/examples/geek6.c +++ b/examples/geek6.c @@ -29,7 +29,7 @@ operation in almost O(1) time complexity. // positive missing number #include -#include +#include declare_CSet(i, int); // Function to find the smallest positive diff --git a/examples/mapmap.c b/examples/mapmap.c index 77c71fe9..35b5f510 100644 --- a/examples/mapmap.c +++ b/examples/mapmap.c @@ -1,6 +1,6 @@ #include -#include +#include static void test_destr(int* x) { printf("destroy int: %d\n", *x); diff --git a/examples/rngtest.c b/examples/rngtest.c index ed3bed08..c465b5c3 100644 --- a/examples/rngtest.c +++ b/examples/rngtest.c @@ -1,6 +1,6 @@ #include #include -#include "../stc/crandom.h" +#include #ifdef __cplusplus #include #endif diff --git a/stc/chash.h b/stc/chash.h deleted file mode 100644 index dc18d77d..00000000 --- a/stc/chash.h +++ /dev/null @@ -1,376 +0,0 @@ -/* MIT License - * - * Copyright (c) 2020 Tyge Løvset, NORCE, www.norceresearch.no - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in all - * copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ - -/* // Example: -#include -#include -declare_CSet(sx, int); // Set of int -declare_CMap(mx, int, char); // Map of int -> char - -int main(void) { - CSet_sx s = cset_init; - cset_sx_put(&s, 5); - cset_sx_put(&s, 8); - c_foreach (i, cset_sx, s) printf("set %d\n", i.item->key); - cset_sx_destroy(&s); - - CMap_mx m = cmap_init; - cmap_mx_put(&m, 5, 'a'); - cmap_mx_put(&m, 8, 'b'); - cmap_mx_put(&m, 12, 'c'); - CMapEntry_mx *e = cmap_mx_get(&m, 10); // = NULL - char val = cmap_mx_get(&m, 5)->value; - cmap_mx_put(&m, 5, 'd'); // update - cmap_mx_erase(&m, 8); - c_foreach (i, cmap_mx, m) printf("map %d: %c\n", i.item->key, i.item->value); - cmap_mx_destroy(&m); -} -*/ -#ifndef CHASH__H__ -#define CHASH__H__ - -#include -#include "cdefs.h" - -#define cmap_init {NULL, NULL, 0, 0, 0.85f, 0.15f} -#define cmap_size(m) ((size_t) (m).size) -#define cmap_bucketCount(m) ((size_t) (m).buckets) -#define cset_init cmap_init -#define cset_size(s) cmap_size(s) -#define cset_bucketCount(s) cmap_bucketCount(s) - -/* https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction */ -#define chash_reduce(x, N) ((uint32_t) (((uint64_t) (x) * (N)) >> 32)) -#define chash_entryIndex(h, entryPtr) ((entryPtr) - (h).table) - -enum {chash_HASH = 0x7f, chash_USED = 0x80}; - -#define declare_CMap(...) \ - c_MACRO_OVERLOAD(declare_CMap, __VA_ARGS__) - -#define declare_CMap_3(tag, Key, Value) \ - declare_CMap_4(tag, Key, Value, c_emptyDestroy) - -#define declare_CMap_4(tag, Key, Value, valueDestroy) \ - declare_CMap_5(tag, Key, Value, valueDestroy, c_defaultHash) - -#define declare_CMap_5(tag, Key, Value, valueDestroy, keyHash) \ - declare_CMap_6(tag, Key, Value, valueDestroy, keyHash, c_defaultEquals) - -#define declare_CMap_6(tag, Key, Value, valueDestroy, keyHash, keyEquals) \ - declare_CMap_10(tag, Key, Value, valueDestroy, keyHash, keyEquals, \ - c_emptyDestroy, Key, c_defaultGetRaw, c_defaultInitRaw) - -#define declare_CMap_10(tag, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ - keyDestroy, RawKey, keyGetRaw, keyInitRaw) \ - declare_CHASH(tag, CMap, cmap, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ - keyDestroy, RawKey, keyGetRaw, keyInitRaw) - -/* CSet: */ -#define declare_CSet(...) \ - c_MACRO_OVERLOAD(declare_CSet, __VA_ARGS__) - -#define declare_CSet_2(tag, Key) \ - declare_CSet_3(tag, Key, c_emptyDestroy) - -#define declare_CSet_3(tag, Key, keyDestroy) \ - declare_CSet_4(tag, Key, keyDestroy, c_defaultHash) - -#define declare_CSet_4(tag, Key, keyDestroy, keyHash) \ - declare_CSet_5(tag, Key, keyDestroy, keyHash, c_defaultEquals) - -#define declare_CSet_5(tag, Key, keyDestroy, keyHash, keyEquals) \ - declare_CSet_8(tag, Key, keyDestroy, keyHash, keyEquals, \ - Key, c_defaultGetRaw, c_defaultInitRaw) - -#define declare_CSet_8(tag, Key, keyDestroy, keyHashRaw, keyEqualsRaw, \ - RawKey, keyGetRaw, keyInitRaw) \ - declare_CHASH(tag, CSet, cset, Key, void, void, keyHashRaw, keyEqualsRaw, \ - keyDestroy, RawKey, keyGetRaw, keyInitRaw) - -/* CSet_str, CMap_str: */ -#define declare_CSet_str() \ - declare_CMAPSTR(str, CSet, cset, void, void) - -#define declare_CMap_str(...) \ - c_MACRO_OVERLOAD(declare_CMap_str, __VA_ARGS__) - -#define declare_CMap_str_2(tag, Value) \ - declare_CMAPSTR(tag, CMap, cmap, Value, c_emptyDestroy) - -#define declare_CMap_str_3(tag, Value, ValueDestroy) \ - declare_CMAPSTR(tag, CMap, cmap, Value, ValueDestroy) - -#define declare_CMAPSTR(tag, CType, ctype, Value, valueDestroy) \ - declare_CHASH(tag, CType, ctype, CStr, Value, valueDestroy, cstr_hashRaw, \ - cstr_equalsRaw, cstr_destroy, const char*, cstr_getRaw, cstr_make) - -#define OPT_1_cset(x) -#define OPT_2_cset(x, y) x -#define OPT_1_cmap(x) x -#define OPT_2_cmap(x, y) x, y - -/* CHASH full: use 'void' for Value if is */ -#define declare_CHASH(tag, CType, ctype, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ - keyDestroy, RawKey, keyGetRaw, keyInitRaw) \ -typedef struct CType##Entry_##tag { \ - Key key; \ - OPT_1_##ctype(Value value;) \ -} CType##Entry_##tag; \ - \ -STC_INLINE void \ -ctype##entry_##tag##_destroy(CType##Entry_##tag* e) { \ - keyDestroy(&e->key); \ - OPT_1_##ctype(valueDestroy(&e->value);) \ -} \ - \ -typedef RawKey CType##RawKey_##tag; \ - \ -typedef struct CType##_##tag { \ - CType##Entry_##tag* table; \ - uint8_t* _hashx; \ - uint32_t size, buckets; \ - float maxLoadFactor; \ - float shrinkLimitFactor; \ -} CType##_##tag; \ - \ -typedef struct { \ - CType##Entry_##tag *item, *_end; \ - uint8_t* _hx; \ -} CType##Iter_##tag, ctype##_##tag##_iter_t; \ - \ -STC_API CType##_##tag \ -ctype##_##tag##_make(size_t initialSize); \ -STC_API void \ -ctype##_##tag##_destroy(CType##_##tag* self); \ -STC_API void \ -ctype##_##tag##_clear(CType##_##tag* self); \ -STC_API void \ -ctype##_##tag##_setLoadFactors(CType##_##tag* self, float maxLoadFactor, float shrinkLimitFactor); \ -STC_API CType##Entry_##tag* \ -ctype##_##tag##_get(const CType##_##tag* self, CType##RawKey_##tag rawKey); \ -STC_API CType##Entry_##tag* \ -ctype##_##tag##_put(CType##_##tag* self, OPT_2_##ctype(CType##RawKey_##tag rawKey, Value value)); \ -OPT_1_##ctype(STC_API CType##Entry_##tag* \ -ctype##_##tag##_at(CType##_##tag* self, CType##RawKey_##tag rawKey, Value initValue);) \ -STC_INLINE void \ -ctype##_##tag##_swap(CType##_##tag* a, CType##_##tag* b) { c_swap(CType##_##tag, *a, *b); } \ -STC_API size_t \ -ctype##_##tag##_reserve(CType##_##tag* self, size_t size); \ -STC_API bool \ -ctype##_##tag##_eraseEntry(CType##_##tag* self, CType##Entry_##tag* entry); \ -STC_API bool \ -ctype##_##tag##_erase(CType##_##tag* self, CType##RawKey_##tag rawKey); \ -STC_API ctype##_##tag##_iter_t \ -ctype##_##tag##_begin(CType##_##tag* map); \ -STC_API ctype##_##tag##_iter_t \ -ctype##_##tag##_next(ctype##_##tag##_iter_t it); \ - \ -implement_CHASH(tag, CType, ctype, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ - keyDestroy, RawKey, keyGetRaw, keyInitRaw) \ -typedef Key CType##Key_##tag; \ -typedef Value CType##Value_##tag - -/* -------------------------- IMPLEMENTATION ------------------------- */ - -#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -#define implement_CHASH(tag, CType, ctype, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ - keyDestroy, RawKey, keyGetRaw, keyInitRaw) \ - \ -STC_API CType##_##tag \ -ctype##_##tag##_make(size_t initialSize) { \ - CType##_##tag h = ctype##_init; \ - ctype##_##tag##_reserve(&h, initialSize); \ - return h; \ -} \ - \ -STC_API void \ -ctype##_##tag##_destroy(CType##_##tag* self) { \ - if (ctype##_size(*self)) { \ - size_t cap = ctype##_bucketCount(*self); \ - CType##Entry_##tag* e = self->table, *end = e + cap; \ - uint8_t *hashx = self->_hashx; \ - for (; e != end; ++e) if (*hashx++) ctype##entry_##tag##_destroy(e); \ - } \ - free(self->_hashx); \ - free(self->table); \ -} \ - \ -STC_API void ctype##_##tag##_clear(CType##_##tag* self) { \ - ctype##_##tag##_destroy(self); \ - self->buckets = self->size = 0; \ -} \ - \ -STC_API void \ -ctype##_##tag##_setLoadFactors(CType##_##tag* self, float maxLoadFactor, float shrinkLimitFactor) { \ - self->maxLoadFactor = maxLoadFactor; \ - self->shrinkLimitFactor = shrinkLimitFactor; \ -} \ - \ -STC_API size_t \ -ctype##_##tag##_bucket(const CType##_##tag* self, const CType##RawKey_##tag* rawKeyPtr, uint32_t* hxPtr) { \ - uint32_t hash = keyHashRaw(rawKeyPtr, sizeof(CType##RawKey_##tag)); \ - uint32_t sx, hx = (hash & chash_HASH) | chash_USED; \ - size_t cap = ctype##_bucketCount(*self); \ - size_t idx = chash_reduce(hash, cap); \ - uint8_t* hashx = self->_hashx; \ - while ((sx = hashx[idx])) { \ - if (sx == hx) { \ - CType##RawKey_##tag r = keyGetRaw(&self->table[idx].key); \ - if (keyEqualsRaw(&r, rawKeyPtr)) break; \ - } \ - if (++idx == cap) idx = 0; \ - } \ - *hxPtr = hx; \ - return idx; \ -} \ - \ -STC_API CType##Entry_##tag* \ -ctype##_##tag##_get(const CType##_##tag* self, CType##RawKey_##tag rawKey) { \ - if (ctype##_size(*self) == 0) return NULL; \ - uint32_t hx; \ - size_t idx = ctype##_##tag##_bucket(self, &rawKey, &hx); \ - return self->_hashx[idx] ? &self->table[idx] : NULL; \ -} \ - \ -static inline void ctype##_##tag##_reserveExpand_(CType##_##tag* self) { \ - if (ctype##_size(*self) + 1 >= ctype##_bucketCount(*self) * self->maxLoadFactor) \ - ctype##_##tag##_reserve(self, (size_t) 7 + (1.6 * ctype##_bucketCount(*self))); \ -} \ - \ -STC_API CType##Entry_##tag* \ -ctype##_##tag##_put(CType##_##tag* self, OPT_2_##ctype(CType##RawKey_##tag rawKey, Value value)) { \ - ctype##_##tag##_reserveExpand_(self); \ - uint32_t hx; \ - size_t idx = ctype##_##tag##_bucket(self, &rawKey, &hx); \ - CType##Entry_##tag* e = &self->table[idx]; \ - if (self->_hashx[idx]) \ - OPT_1_##ctype(valueDestroy(&e->value)) ; \ - else { \ - e->key = keyInitRaw(rawKey); \ - self->_hashx[idx] = (uint8_t) hx; \ - ++self->size; \ - } \ - OPT_1_##ctype(e->value = value;) \ - return e; \ -} \ - \ -OPT_1_##ctype( \ -STC_API CType##Entry_##tag* \ -ctype##_##tag##_at(CType##_##tag* self, CType##RawKey_##tag rawKey, Value initValue) { \ - ctype##_##tag##_reserveExpand_(self); \ - uint32_t hx; \ - size_t idx = ctype##_##tag##_bucket(self, &rawKey, &hx); \ - CType##Entry_##tag* e = &self->table[idx]; \ - if (! self->_hashx[idx]) { \ - e->key = keyInitRaw(rawKey); \ - self->_hashx[idx] = (uint8_t) hx; \ - ++self->size; \ - e->value = initValue; \ - } \ - return e; \ -}) \ - \ -STC_API size_t \ -ctype##_##tag##_reserve(CType##_##tag* self, size_t newcap) { \ - size_t oldcap = ctype##_bucketCount(*self); newcap |= 1; \ - if (ctype##_size(*self) >= newcap * self->maxLoadFactor) return oldcap; \ - CType##_##tag tmp = { \ - c_new_N(CType##Entry_##tag, newcap), \ - (uint8_t *) calloc(newcap, sizeof(uint8_t)), \ - self->size, (uint32_t) newcap, \ - self->maxLoadFactor, self->shrinkLimitFactor \ - }; \ - ctype##_##tag##_swap(self, &tmp); \ - \ - CType##Entry_##tag* e = tmp.table, *slot = self->table; \ - uint8_t* hashx = self->_hashx; \ - uint32_t hx; \ - for (size_t i = 0; i < oldcap; ++i, ++e) \ - if (tmp._hashx[i]) { \ - CType##RawKey_##tag r = keyGetRaw(&e->key); \ - size_t idx = ctype##_##tag##_bucket(self, &r, &hx); \ - slot[idx] = *e, \ - hashx[idx] = (uint8_t) hx; \ - } \ - free(tmp._hashx); \ - free(tmp.table); \ - return newcap; \ -} \ - \ -STC_API bool \ -ctype##_##tag##_eraseEntry(CType##_##tag* self, CType##Entry_##tag* entry) { \ - size_t i = chash_entryIndex(*self, entry), j = i, k, cap = ctype##_bucketCount(*self); \ - CType##Entry_##tag* slot = self->table; \ - uint8_t* hashx = self->_hashx; \ - CType##RawKey_##tag r; \ - if (! hashx[i]) \ - return false; \ - do { /* deletion from hash table without tombstone */ \ - if (++j == cap) j = 0; /* ++j; j %= cap; is slow */ \ - if (! hashx[j]) \ - break; \ - r = keyGetRaw(&slot[j].key); \ - k = chash_reduce(keyHashRaw(&r, sizeof(CType##RawKey_##tag)), cap); \ - if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ \ - slot[i] = slot[j], hashx[i] = hashx[j], i = j; \ - } while (true); \ - hashx[i] = 0; \ - ctype##entry_##tag##_destroy(&slot[i]); \ - --self->size; \ - return true; \ -} \ - \ -STC_API bool \ -ctype##_##tag##_erase(CType##_##tag* self, CType##RawKey_##tag rawKey) { \ - if (ctype##_size(*self) == 0) \ - return false; \ - size_t cap = ctype##_bucketCount(*self); \ - if (ctype##_size(*self) < cap * self->shrinkLimitFactor && cap * sizeof(CType##Entry_##tag) > 1024) \ - ctype##_##tag##_reserve(self, (size_t) (ctype##_size(*self) * 1.2f / self->maxLoadFactor)); \ - uint32_t hx; \ - size_t i = ctype##_##tag##_bucket(self, &rawKey, &hx); \ - return ctype##_##tag##_eraseEntry(self, self->table + i); \ -} \ - \ -STC_API ctype##_##tag##_iter_t \ -ctype##_##tag##_begin(CType##_##tag* map) { \ - uint8_t* hx = map->_hashx; \ - CType##Entry_##tag* e = map->table, *end = e + ctype##_bucketCount(*map); \ - while (e != end && !*hx) ++e, ++hx; \ - ctype##_##tag##_iter_t it = {e == end ? NULL : e, end, hx}; return it; \ -} \ - \ -STC_API ctype##_##tag##_iter_t \ -ctype##_##tag##_next(ctype##_##tag##_iter_t it) { \ - do { ++it.item, ++it._hx; } while (it.item != it._end && !*it._hx); \ - if (it.item == it._end) it.item = NULL; \ - return it; \ -} - -#else -#define implement_CHASH(tag, CType, ctype, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ - keyDestroy, RawKey, keyGetRaw, keyInitRaw) -#endif - -#endif diff --git a/stc/cmap.h b/stc/cmap.h new file mode 100644 index 00000000..a823b9ff --- /dev/null +++ b/stc/cmap.h @@ -0,0 +1,376 @@ +/* MIT License + * + * Copyright (c) 2020 Tyge Løvset, NORCE, www.norceresearch.no + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +/* // Example: +#include +#include +declare_CSet(sx, int); // Set of int +declare_CMap(mx, int, char); // Map of int -> char + +int main(void) { + CSet_sx s = cset_init; + cset_sx_put(&s, 5); + cset_sx_put(&s, 8); + c_foreach (i, cset_sx, s) printf("set %d\n", i.item->key); + cset_sx_destroy(&s); + + CMap_mx m = cmap_init; + cmap_mx_put(&m, 5, 'a'); + cmap_mx_put(&m, 8, 'b'); + cmap_mx_put(&m, 12, 'c'); + CMapEntry_mx *e = cmap_mx_get(&m, 10); // = NULL + char val = cmap_mx_get(&m, 5)->value; + cmap_mx_put(&m, 5, 'd'); // update + cmap_mx_erase(&m, 8); + c_foreach (i, cmap_mx, m) printf("map %d: %c\n", i.item->key, i.item->value); + cmap_mx_destroy(&m); +} +*/ +#ifndef CMAP__H__ +#define CMAP__H__ + +#include +#include "cdefs.h" + +#define cmap_init {NULL, NULL, 0, 0, 0.85f, 0.15f} +#define cmap_size(m) ((size_t) (m).size) +#define cmap_bucketCount(m) ((size_t) (m).buckets) +#define cset_init cmap_init +#define cset_size(s) cmap_size(s) +#define cset_bucketCount(s) cmap_bucketCount(s) + +/* https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction */ +#define chash_reduce(x, N) ((uint32_t) (((uint64_t) (x) * (N)) >> 32)) +#define chash_entryIndex(h, entryPtr) ((entryPtr) - (h).table) + +enum {chash_HASH = 0x7f, chash_USED = 0x80}; + +#define declare_CMap(...) \ + c_MACRO_OVERLOAD(declare_CMap, __VA_ARGS__) + +#define declare_CMap_3(tag, Key, Value) \ + declare_CMap_4(tag, Key, Value, c_emptyDestroy) + +#define declare_CMap_4(tag, Key, Value, valueDestroy) \ + declare_CMap_5(tag, Key, Value, valueDestroy, c_defaultHash) + +#define declare_CMap_5(tag, Key, Value, valueDestroy, keyHash) \ + declare_CMap_6(tag, Key, Value, valueDestroy, keyHash, c_defaultEquals) + +#define declare_CMap_6(tag, Key, Value, valueDestroy, keyHash, keyEquals) \ + declare_CMap_10(tag, Key, Value, valueDestroy, keyHash, keyEquals, \ + c_emptyDestroy, Key, c_defaultGetRaw, c_defaultInitRaw) + +#define declare_CMap_10(tag, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ + keyDestroy, RawKey, keyGetRaw, keyInitRaw) \ + declare_CHASH(tag, CMap, cmap, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ + keyDestroy, RawKey, keyGetRaw, keyInitRaw) + +/* CSet: */ +#define declare_CSet(...) \ + c_MACRO_OVERLOAD(declare_CSet, __VA_ARGS__) + +#define declare_CSet_2(tag, Key) \ + declare_CSet_3(tag, Key, c_emptyDestroy) + +#define declare_CSet_3(tag, Key, keyDestroy) \ + declare_CSet_4(tag, Key, keyDestroy, c_defaultHash) + +#define declare_CSet_4(tag, Key, keyDestroy, keyHash) \ + declare_CSet_5(tag, Key, keyDestroy, keyHash, c_defaultEquals) + +#define declare_CSet_5(tag, Key, keyDestroy, keyHash, keyEquals) \ + declare_CSet_8(tag, Key, keyDestroy, keyHash, keyEquals, \ + Key, c_defaultGetRaw, c_defaultInitRaw) + +#define declare_CSet_8(tag, Key, keyDestroy, keyHashRaw, keyEqualsRaw, \ + RawKey, keyGetRaw, keyInitRaw) \ + declare_CHASH(tag, CSet, cset, Key, void, void, keyHashRaw, keyEqualsRaw, \ + keyDestroy, RawKey, keyGetRaw, keyInitRaw) + +/* CSet_str, CMap_str: */ +#define declare_CSet_str() \ + declare_CMAPSTR(str, CSet, cset, void, void) + +#define declare_CMap_str(...) \ + c_MACRO_OVERLOAD(declare_CMap_str, __VA_ARGS__) + +#define declare_CMap_str_2(tag, Value) \ + declare_CMAPSTR(tag, CMap, cmap, Value, c_emptyDestroy) + +#define declare_CMap_str_3(tag, Value, ValueDestroy) \ + declare_CMAPSTR(tag, CMap, cmap, Value, ValueDestroy) + +#define declare_CMAPSTR(tag, CType, ctype, Value, valueDestroy) \ + declare_CHASH(tag, CType, ctype, CStr, Value, valueDestroy, cstr_hashRaw, \ + cstr_equalsRaw, cstr_destroy, const char*, cstr_getRaw, cstr_make) + +#define OPT_1_cset(x) +#define OPT_2_cset(x, y) x +#define OPT_1_cmap(x) x +#define OPT_2_cmap(x, y) x, y + +/* CHASH full: use 'void' for Value if is */ +#define declare_CHASH(tag, CType, ctype, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ + keyDestroy, RawKey, keyGetRaw, keyInitRaw) \ +typedef struct CType##Entry_##tag { \ + Key key; \ + OPT_1_##ctype(Value value;) \ +} CType##Entry_##tag; \ + \ +STC_INLINE void \ +ctype##entry_##tag##_destroy(CType##Entry_##tag* e) { \ + keyDestroy(&e->key); \ + OPT_1_##ctype(valueDestroy(&e->value);) \ +} \ + \ +typedef RawKey CType##RawKey_##tag; \ + \ +typedef struct CType##_##tag { \ + CType##Entry_##tag* table; \ + uint8_t* _hashx; \ + uint32_t size, buckets; \ + float maxLoadFactor; \ + float shrinkLimitFactor; \ +} CType##_##tag; \ + \ +typedef struct { \ + CType##Entry_##tag *item, *_end; \ + uint8_t* _hx; \ +} CType##Iter_##tag, ctype##_##tag##_iter_t; \ + \ +STC_API CType##_##tag \ +ctype##_##tag##_make(size_t initialSize); \ +STC_API void \ +ctype##_##tag##_destroy(CType##_##tag* self); \ +STC_API void \ +ctype##_##tag##_clear(CType##_##tag* self); \ +STC_API void \ +ctype##_##tag##_setLoadFactors(CType##_##tag* self, float maxLoadFactor, float shrinkLimitFactor); \ +STC_API CType##Entry_##tag* \ +ctype##_##tag##_get(const CType##_##tag* self, CType##RawKey_##tag rawKey); \ +STC_API CType##Entry_##tag* \ +ctype##_##tag##_put(CType##_##tag* self, OPT_2_##ctype(CType##RawKey_##tag rawKey, Value value)); \ +OPT_1_##ctype(STC_API CType##Entry_##tag* \ +ctype##_##tag##_at(CType##_##tag* self, CType##RawKey_##tag rawKey, Value initValue);) \ +STC_INLINE void \ +ctype##_##tag##_swap(CType##_##tag* a, CType##_##tag* b) { c_swap(CType##_##tag, *a, *b); } \ +STC_API size_t \ +ctype##_##tag##_reserve(CType##_##tag* self, size_t size); \ +STC_API bool \ +ctype##_##tag##_eraseEntry(CType##_##tag* self, CType##Entry_##tag* entry); \ +STC_API bool \ +ctype##_##tag##_erase(CType##_##tag* self, CType##RawKey_##tag rawKey); \ +STC_API ctype##_##tag##_iter_t \ +ctype##_##tag##_begin(CType##_##tag* map); \ +STC_API ctype##_##tag##_iter_t \ +ctype##_##tag##_next(ctype##_##tag##_iter_t it); \ + \ +implement_CHASH(tag, CType, ctype, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ + keyDestroy, RawKey, keyGetRaw, keyInitRaw) \ +typedef Key CType##Key_##tag; \ +typedef Value CType##Value_##tag + +/* -------------------------- IMPLEMENTATION ------------------------- */ + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) +#define implement_CHASH(tag, CType, ctype, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ + keyDestroy, RawKey, keyGetRaw, keyInitRaw) \ + \ +STC_API CType##_##tag \ +ctype##_##tag##_make(size_t initialSize) { \ + CType##_##tag h = ctype##_init; \ + ctype##_##tag##_reserve(&h, initialSize); \ + return h; \ +} \ + \ +STC_API void \ +ctype##_##tag##_destroy(CType##_##tag* self) { \ + if (ctype##_size(*self)) { \ + size_t cap = ctype##_bucketCount(*self); \ + CType##Entry_##tag* e = self->table, *end = e + cap; \ + uint8_t *hashx = self->_hashx; \ + for (; e != end; ++e) if (*hashx++) ctype##entry_##tag##_destroy(e); \ + } \ + free(self->_hashx); \ + free(self->table); \ +} \ + \ +STC_API void ctype##_##tag##_clear(CType##_##tag* self) { \ + ctype##_##tag##_destroy(self); \ + self->buckets = self->size = 0; \ +} \ + \ +STC_API void \ +ctype##_##tag##_setLoadFactors(CType##_##tag* self, float maxLoadFactor, float shrinkLimitFactor) { \ + self->maxLoadFactor = maxLoadFactor; \ + self->shrinkLimitFactor = shrinkLimitFactor; \ +} \ + \ +STC_API size_t \ +ctype##_##tag##_bucket(const CType##_##tag* self, const CType##RawKey_##tag* rawKeyPtr, uint32_t* hxPtr) { \ + uint32_t hash = keyHashRaw(rawKeyPtr, sizeof(CType##RawKey_##tag)); \ + uint32_t sx, hx = (hash & chash_HASH) | chash_USED; \ + size_t cap = ctype##_bucketCount(*self); \ + size_t idx = chash_reduce(hash, cap); \ + uint8_t* hashx = self->_hashx; \ + while ((sx = hashx[idx])) { \ + if (sx == hx) { \ + CType##RawKey_##tag r = keyGetRaw(&self->table[idx].key); \ + if (keyEqualsRaw(&r, rawKeyPtr)) break; \ + } \ + if (++idx == cap) idx = 0; \ + } \ + *hxPtr = hx; \ + return idx; \ +} \ + \ +STC_API CType##Entry_##tag* \ +ctype##_##tag##_get(const CType##_##tag* self, CType##RawKey_##tag rawKey) { \ + if (ctype##_size(*self) == 0) return NULL; \ + uint32_t hx; \ + size_t idx = ctype##_##tag##_bucket(self, &rawKey, &hx); \ + return self->_hashx[idx] ? &self->table[idx] : NULL; \ +} \ + \ +static inline void ctype##_##tag##_reserveExpand_(CType##_##tag* self) { \ + if (ctype##_size(*self) + 1 >= ctype##_bucketCount(*self) * self->maxLoadFactor) \ + ctype##_##tag##_reserve(self, (size_t) 7 + (1.6 * ctype##_bucketCount(*self))); \ +} \ + \ +STC_API CType##Entry_##tag* \ +ctype##_##tag##_put(CType##_##tag* self, OPT_2_##ctype(CType##RawKey_##tag rawKey, Value value)) { \ + ctype##_##tag##_reserveExpand_(self); \ + uint32_t hx; \ + size_t idx = ctype##_##tag##_bucket(self, &rawKey, &hx); \ + CType##Entry_##tag* e = &self->table[idx]; \ + if (self->_hashx[idx]) \ + OPT_1_##ctype(valueDestroy(&e->value)) ; \ + else { \ + e->key = keyInitRaw(rawKey); \ + self->_hashx[idx] = (uint8_t) hx; \ + ++self->size; \ + } \ + OPT_1_##ctype(e->value = value;) \ + return e; \ +} \ + \ +OPT_1_##ctype( \ +STC_API CType##Entry_##tag* \ +ctype##_##tag##_at(CType##_##tag* self, CType##RawKey_##tag rawKey, Value initValue) { \ + ctype##_##tag##_reserveExpand_(self); \ + uint32_t hx; \ + size_t idx = ctype##_##tag##_bucket(self, &rawKey, &hx); \ + CType##Entry_##tag* e = &self->table[idx]; \ + if (! self->_hashx[idx]) { \ + e->key = keyInitRaw(rawKey); \ + self->_hashx[idx] = (uint8_t) hx; \ + ++self->size; \ + e->value = initValue; \ + } \ + return e; \ +}) \ + \ +STC_API size_t \ +ctype##_##tag##_reserve(CType##_##tag* self, size_t newcap) { \ + size_t oldcap = ctype##_bucketCount(*self); newcap |= 1; \ + if (ctype##_size(*self) >= newcap * self->maxLoadFactor) return oldcap; \ + CType##_##tag tmp = { \ + c_new_N(CType##Entry_##tag, newcap), \ + (uint8_t *) calloc(newcap, sizeof(uint8_t)), \ + self->size, (uint32_t) newcap, \ + self->maxLoadFactor, self->shrinkLimitFactor \ + }; \ + ctype##_##tag##_swap(self, &tmp); \ + \ + CType##Entry_##tag* e = tmp.table, *slot = self->table; \ + uint8_t* hashx = self->_hashx; \ + uint32_t hx; \ + for (size_t i = 0; i < oldcap; ++i, ++e) \ + if (tmp._hashx[i]) { \ + CType##RawKey_##tag r = keyGetRaw(&e->key); \ + size_t idx = ctype##_##tag##_bucket(self, &r, &hx); \ + slot[idx] = *e, \ + hashx[idx] = (uint8_t) hx; \ + } \ + free(tmp._hashx); \ + free(tmp.table); \ + return newcap; \ +} \ + \ +STC_API bool \ +ctype##_##tag##_eraseEntry(CType##_##tag* self, CType##Entry_##tag* entry) { \ + size_t i = chash_entryIndex(*self, entry), j = i, k, cap = ctype##_bucketCount(*self); \ + CType##Entry_##tag* slot = self->table; \ + uint8_t* hashx = self->_hashx; \ + CType##RawKey_##tag r; \ + if (! hashx[i]) \ + return false; \ + do { /* deletion from hash table without tombstone */ \ + if (++j == cap) j = 0; /* ++j; j %= cap; is slow */ \ + if (! hashx[j]) \ + break; \ + r = keyGetRaw(&slot[j].key); \ + k = chash_reduce(keyHashRaw(&r, sizeof(CType##RawKey_##tag)), cap); \ + if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ \ + slot[i] = slot[j], hashx[i] = hashx[j], i = j; \ + } while (true); \ + hashx[i] = 0; \ + ctype##entry_##tag##_destroy(&slot[i]); \ + --self->size; \ + return true; \ +} \ + \ +STC_API bool \ +ctype##_##tag##_erase(CType##_##tag* self, CType##RawKey_##tag rawKey) { \ + if (ctype##_size(*self) == 0) \ + return false; \ + size_t cap = ctype##_bucketCount(*self); \ + if (ctype##_size(*self) < cap * self->shrinkLimitFactor && cap * sizeof(CType##Entry_##tag) > 1024) \ + ctype##_##tag##_reserve(self, (size_t) (ctype##_size(*self) * 1.2f / self->maxLoadFactor)); \ + uint32_t hx; \ + size_t i = ctype##_##tag##_bucket(self, &rawKey, &hx); \ + return ctype##_##tag##_eraseEntry(self, self->table + i); \ +} \ + \ +STC_API ctype##_##tag##_iter_t \ +ctype##_##tag##_begin(CType##_##tag* map) { \ + uint8_t* hx = map->_hashx; \ + CType##Entry_##tag* e = map->table, *end = e + ctype##_bucketCount(*map); \ + while (e != end && !*hx) ++e, ++hx; \ + ctype##_##tag##_iter_t it = {e == end ? NULL : e, end, hx}; return it; \ +} \ + \ +STC_API ctype##_##tag##_iter_t \ +ctype##_##tag##_next(ctype##_##tag##_iter_t it) { \ + do { ++it.item, ++it._hx; } while (it.item != it._end && !*it._hx); \ + if (it.item == it._end) it.item = NULL; \ + return it; \ +} + +#else +#define implement_CHASH(tag, CType, ctype, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ + keyDestroy, RawKey, keyGetRaw, keyInitRaw) +#endif + +#endif diff --git a/stc/crandom.h b/stc/crandom.h index ff2e03d3..1cf3fb2d 100644 --- a/stc/crandom.h +++ b/stc/crandom.h @@ -1,3 +1,26 @@ +/* MIT License + * + * Copyright (c) 2020 Tyge Løvset, NORCE, www.norceresearch.no + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + #ifndef CRANDOM__H__ #define CRANDOM__H__ diff --git a/stc/cset.h b/stc/cset.h new file mode 100644 index 00000000..630771c7 --- /dev/null +++ b/stc/cset.h @@ -0,0 +1,28 @@ +/* MIT License + * + * Copyright (c) 2020 Tyge Løvset, NORCE, www.norceresearch.no + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ +#ifndef CSET__H__ +#define CSET__H__ + +#include "cmap.h" + +#endif -- cgit v1.2.3