From 7e8ee593834c1afa459639047b1e5bcfbfcf6196 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sat, 16 Jan 2021 16:27:34 +0100 Subject: Added csmap.c under dev. Internal renaming in cmap.h --- dev/csmap.c | 479 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ stc/cmap.h | 326 ++++++++++++++++++++--------------------- 2 files changed, 640 insertions(+), 165 deletions(-) create mode 100644 dev/csmap.c diff --git a/dev/csmap.c b/dev/csmap.c new file mode 100644 index 00000000..48d3fca9 --- /dev/null +++ b/dev/csmap.c @@ -0,0 +1,479 @@ +/* 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 CSMAP__H__ +#define CSMAP__H__ + +// Sorted/Ordered set and map - implemented as an AA-tree. +/* +#include +#include +using_csset(i, int); // Set of int +using_csmap(ic, int, char); // Map of int -> char + +int main(void) { + csset_sx s = csset_inits; + csset_sx_insert(&s, 5); + csset_sx_insert(&s, 8); + c_foreach (i, csset_sx, s) + printf("set %d\n", i.ref->second); + csset_sx_del(&s); +} +*/ +//#include "ccommon.h" +#include +#include +#include +#include + +#define csmap_inits {NULL, 0} +#define csset_inits csmap_inits + +#define using_csmap(...) \ + c_MACRO_OVERLOAD(using_csmap, __VA_ARGS__) + +#define using_csmap_3(X, Key, Mapped) \ + using_csmap_5(X, Key, Mapped, c_default_del, c_default_clone) + +#define using_csmap_5(X, Key, Mapped, mappedDel, mappedClone) \ + using_csmap_6(X, Key, Mapped, mappedDel, mappedClone, c_default_compare) + +#define using_csmap_6(X, Key, Mapped, mappedDel, mappedClone, keyCompare) \ + using_csmap_8(X, Key, Mapped, mappedDel, mappedClone, keyCompare, c_default_del, c_default_clone) + +#define using_csmap_8(X, Key, Mapped, mappedDel, mappedClone, keyCompare, keyDel, keyClone) \ + using_csmap_10(X, Key, Mapped, mappedDel, mappedClone, keyCompare, keyDel, \ + keyClone, c_default_to_raw, Key) + +#define using_csmap_10(X, Key, Mapped, mappedDel, mappedClone, keyCompareRaw, keyDel, \ + keyFromRaw, keyToRaw, RawKey) \ + _using_CBST(X, csmap, Key, Mapped, mappedDel, keyCompareRaw, keyDel, \ + keyFromRaw, keyToRaw, RawKey, mappedClone, c_default_to_raw, Mapped) + +/* csset: */ +#define using_csset(...) \ + c_MACRO_OVERLOAD(using_csset, __VA_ARGS__) + +#define using_csset_2(X, Key) \ + using_csset_3(X, Key, c_default_compare) + +#define using_csset_3(X, Key, keyCompare) \ + using_csset_5(X, Key, keyCompare, c_default_del, c_default_clone) + +#define using_csset_5(X, Key, keyCompare, keyDel, keyClone) \ + using_csset_7(X, Key, keyCompare, keyDel, keyClone, c_default_to_raw, Key) + +#define using_csset_7(X, Key, keyCompareRaw, keyDel, keyFromRaw, keyToRaw, RawKey) \ + _using_CBST(X, csset, Key, Key, _UNUSED_, keyCompareRaw, keyDel, \ + keyFromRaw, keyToRaw, RawKey, _UNUSED_, _UNUSED_, void) + +/* csset_str, csmap_str, csmap_strkey, csmap_strval: */ +#define using_csset_str() \ + _using_CBST_strkey(str, csset, cstr_t, _UNUSED_, _UNUSED_) +#define using_csmap_str() \ + _using_CBST(str, csmap, cstr_t, cstr_t, cstr_del, cstr_compare_raw, cstr_del, \ + cstr_from, cstr_to_raw, const char*, cstr_from, cstr_to_raw, const char*) + +#define using_csmap_strkey(...) \ + c_MACRO_OVERLOAD(using_csmap_strkey, __VA_ARGS__) + +#define using_csmap_strkey_2(X, Mapped) \ + _using_CBST_strkey(X, csmap, Mapped, c_default_del, c_default_clone) + +#define using_csmap_strkey_4(X, Mapped, mappedDel, mappedClone) \ + _using_CBST_strkey(X, csmap, Mapped, mappedDel, mappedClone) + +#define _using_CBST_strkey(X, C, Mapped, mappedDel, mappedClone) \ + _using_CBST(X, C, cstr_t, Mapped, mappedDel, cstr_compare_raw, cstr_del, \ + cstr_from, cstr_to_raw, const char*, mappedClone, c_default_to_raw, Mapped) + +#define using_csmap_strval(...) \ + c_MACRO_OVERLOAD(using_csmap_strval, __VA_ARGS__) + +#define using_csmap_strval_2(X, Key) \ + using_csmap_strval_3(X, Key, c_default_compare) + +#define using_csmap_strval_3(X, Key, keyCompare) \ + using_csmap_strval_5(X, Key, keyCompare, c_default_del, c_default_clone) + +#define using_csmap_strval_5(X, Key, keyCompare, keyDel, keyClone) \ + using_csmap_strval_7(X, Key, keyCompare, keyDel, keyClone, c_default_to_raw, Key) + +#define using_csmap_strval_7(X, Key, keyCompare, keyDel, keyFromRaw, keyToRaw, RawKey) \ + _using_CBST(X, csmap, Key, cstr_t, cstr_del, keyCompare, keyDel, \ + keyFromRaw, keyToRaw, RawKey, cstr_from, cstr_to_raw, const char*) + +#define SET_ONLY_csset(...) __VA_ARGS__ +#define SET_ONLY_csmap(...) +#define MAP_ONLY_csset(...) +#define MAP_ONLY_csmap(...) __VA_ARGS__ +#define KEY_REF_csset(vp) (vp) +#define KEY_REF_csmap(vp) (&(vp)->first) + +#define _using_CBST_types(X, C, Key, Mapped) \ + typedef Key C##_##X##_key_t; \ + typedef Mapped C##_##X##_mapped_t; \ +\ + typedef SET_ONLY_##C( C##_##X##_key_t ) \ + MAP_ONLY_##C( struct {C##_##X##_key_t first; \ + C##_##X##_mapped_t second;} ) \ + C##_##X##_value_t; \ +\ + typedef struct C##_##X##_node { \ + struct C##_##X##_node *link[2]; \ + int level; \ + C##_##X##_value_t value; \ + } C##_##X##_node_t; \ +\ + typedef struct { \ + C##_##X##_node_t* root; \ + size_t size; \ + } C##_##X; \ +\ + typedef struct { \ + C##_##X##_value_t *ref; \ + int top; \ + C##_##X##_node_t *tn, *stk[34]; \ + } C##_##X##_iter_t + + +#define _using_CBST(X, C, Key, Mapped, mappedDel, keyCompareRaw, keyDel, \ + keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ + _using_CBST_types(X, C, Key, Mapped); \ +\ + typedef RawKey C##_##X##_rawkey_t; \ + typedef RawMapped C##_##X##_rawmapped_t; \ + typedef SET_ONLY_##C( C##_##X##_rawkey_t ) \ + MAP_ONLY_##C( struct {C##_##X##_rawkey_t first; \ + C##_##X##_rawmapped_t second;} ) \ + C##_##X##_rawvalue_t; \ +\ + typedef struct { \ + C##_##X##_value_t *first; \ + bool second; \ + } C##_##X##_result_t; \ +\ + STC_INLINE C##_##X \ + C##_##X##_init(void) {C##_##X m = csmap_inits; return m;} \ + STC_INLINE bool \ + C##_##X##_empty(C##_##X m) {return m.size == 0;} \ + STC_INLINE size_t \ + C##_##X##_size(C##_##X m) {return m.size;} \ +\ + STC_API void \ + C##_##X##_del_priv_(C##_##X##_node_t* tn); \ +\ + STC_INLINE void \ + C##_##X##_del(C##_##X* self) {C##_##X##_del_priv_(self->root);} \ + STC_INLINE void \ + C##_##X##_clear(C##_##X* self) {C##_##X##_del(self); self->size = 0;} \ +\ + STC_INLINE void \ + C##_##X##_value_del(C##_##X##_value_t* val) { \ + keyDel(KEY_REF_##C(val)); \ + MAP_ONLY_##C( mappedDel(&val->second); ) \ + } \ + STC_INLINE C##_##X##_value_t \ + C##_##X##_value_clone(C##_##X##_value_t val) { \ + *KEY_REF_##C(&val) = keyFromRaw(keyToRaw(KEY_REF_##C(&val))); \ + MAP_ONLY_##C( val.second = mappedFromRaw(mappedToRaw(&val.second)); ) \ + return val; \ + } \ + STC_INLINE int \ + C##_##X##_node_compare_rkey(const C##_##X##_node_t* tn, const C##_##X##_rawkey_t* ry) { \ + C##_##X##_rawkey_t rx = keyToRaw(KEY_REF_##C(&tn->value)); \ + return keyCompareRaw(&rx, ry); \ + } \ +\ + STC_INLINE void \ + C##_##X##_swap(C##_##X* a, C##_##X* b) {c_swap(C##_##X, *a, *b);} \ + STC_API C##_##X \ + C##_##X##_clone(C##_##X m); \ + STC_API void \ + C##_##X##_push_n(C##_##X* self, const C##_##X##_rawvalue_t arr[], size_t size); \ +\ + STC_API C##_##X##_value_t* \ + C##_##X##_find_priv_(C##_##X##_node_t *tn, const C##_##X##_rawkey_t* rkey, C##_##X##_iter_t* it); \ +\ + STC_INLINE C##_##X##_value_t* \ + C##_##X##_find(const C##_##X* self, RawKey rkey, C##_##X##_iter_t* it) { \ + return C##_##X##_find_priv_(self->root, &rkey, it); \ + } \ + STC_INLINE bool \ + C##_##X##_contains(const C##_##X* self, RawKey rkey) { \ + C##_##X##_iter_t it; \ + return C##_##X##_find_priv_(self->root, &rkey, &it) != NULL; \ + } \ +\ + STC_API C##_##X##_result_t \ + C##_##X##_insert_key_(C##_##X* self, RawKey rkey); \ +\ + STC_INLINE C##_##X##_result_t \ + C##_##X##_emplace(C##_##X* self, RawKey rkey MAP_ONLY_##C(, RawMapped rmapped) ) { \ + C##_##X##_result_t res = C##_##X##_insert_key_(self, rkey); \ + MAP_ONLY_##C( if (res.second) res.first->second = mappedFromRaw(rmapped); ) \ + return res; \ + } \ + STC_INLINE C##_##X##_result_t \ + C##_##X##_insert(C##_##X* self, C##_##X##_rawvalue_t raw) { \ + return SET_ONLY_##C( C##_##X##_insert_key_(self, raw) ) \ + MAP_ONLY_##C( C##_##X##_emplace(self, raw.first, raw.second) ); \ + } \ +\ + MAP_ONLY_##C( \ + STC_INLINE C##_##X##_result_t \ + C##_##X##_put(C##_##X* self, RawKey rkey, RawMapped rmapped) { \ + C##_##X##_result_t res = C##_##X##_insert_key_(self, rkey); \ + if (!res.second) mappedDel(&res.first->second); \ + res.first->second = mappedFromRaw(rmapped); return res; \ + } \ + STC_INLINE C##_##X##_result_t \ + C##_##X##_insert_or_assign(C##_##X* self, RawKey rkey, RawMapped rmapped) { \ + return C##_##X##_put(self, rkey, rmapped); \ + } \ + STC_INLINE C##_##X##_result_t \ + C##_##X##_put_mapped(C##_##X* self, RawKey rkey, Mapped mapped) { \ + C##_##X##_result_t res = C##_##X##_insert_key_(self, rkey); \ + if (!res.second) mappedDel(&res.first->second); \ + res.first->second = mapped; return res; \ + } \ + STC_INLINE C##_##X##_mapped_t* \ + C##_##X##_at(const C##_##X* self, RawKey rkey) { \ + return NULL; \ + }) \ +\ + STC_INLINE C##_##X##_value_t* \ + C##_##X##_front(C##_##X* self) { \ + C##_##X##_node_t *tn = self->root; \ + while (tn->link[0]->level) tn = tn->link[0]; \ + return &tn->value; \ + } \ + STC_INLINE C##_##X##_value_t* \ + C##_##X##_back(C##_##X* self) { \ + C##_##X##_node_t *tn = self->root; \ + while (tn->link[1]->level) tn = tn->link[1]; \ + return &tn->value; \ + } \ +\ + STC_INLINE void \ + C##_##X##_next(C##_##X##_iter_t* it) { \ + cbst_next((csmap___iter_t*) it); \ + } \ + STC_INLINE C##_##X##_iter_t \ + C##_##X##_begin(C##_##X* self) { \ + C##_##X##_iter_t it = {NULL, 0, self->root}; \ + cbst_next((csmap___iter_t*) &it); \ + return it; \ + } \ + STC_INLINE C##_##X##_iter_t \ + C##_##X##_end(C##_##X* self) {\ + C##_##X##_iter_t it = {NULL}; return it; \ + } \ + STC_INLINE C##_##X##_mapped_t* \ + C##_##X##_itval(C##_##X##_iter_t it) {return MAP_ONLY_##C( &it.ref->second ) \ + SET_ONLY_##C( it.ref );} \ +\ + STC_INLINE size_t \ + C##_##X##_erase(C##_##X* self, RawKey rkey) { \ + return 0; \ + } \ + STC_INLINE C##_##X##_iter_t \ + C##_##X##_erase_at(C##_##X* self, C##_##X##_iter_t pos) { \ + /*C##_##X##_erase_entry(self, pos.ref);*/ \ + C##_##X##_next(&pos); return pos; \ + } \ +\ + _implement_CBST(X, C, Key, Mapped, mappedDel, keyCompareRaw, keyDel, \ + keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ + typedef C##_##X C##_##X##_t + +/* -------------------------- IMPLEMENTATION ------------------------- */ + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) +#define _implement_CBST(X, C, Key, Mapped, mappedDel, keyCompareRaw, keyDel, \ + keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ + STC_DEF void \ + C##_##X##_push_n(C##_##X* self, const C##_##X##_rawvalue_t arr[], size_t n) { \ + for (size_t i=0; ilevel != 0) { \ + C##_##X##_del_priv_(tn->link[0]); \ + C##_##X##_del_priv_(tn->link[1]); \ + C##_##X##_value_del(&tn->value); \ + c_free(tn); \ + } \ + } \ +\ + STC_DEF C##_##X##_node_t* \ + C##_##X##_insert_priv_(C##_##X##_node_t* tn, C##_##X##_rawvalue_t* rval, bool overwrite) { \ + if (tn->level == 0) { \ + tn = c_new_1(C##_##X##_node_t); \ + tn->link[0] = tn->link[1] = (C##_##X##_node_t*) &cbst_nil, tn->level = 1; \ + *KEY_REF_##C(&tn->value) = keyFromRaw(*KEY_REF_##C(rval)); \ + MAP_ONLY_##C( tn->value.second = mappedFromRaw(rval->second); ) \ + return tn; \ + } \ + C##_##X##_rawkey_t rkey = keyToRaw(KEY_REF_##C(&tn->value)); \ + int cmp = keyCompareRaw(&rkey, KEY_REF_##C(rval)); \ + if (cmp == 0) { \ + MAP_ONLY_##C( if (overwrite) { mappedDel(&tn->value.second); \ + tn->value.second = mappedFromRaw(rval->second); }) \ + } else { \ + tn->link[cmp == -1] = C##_##X##_insert_priv_(tn->link[cmp == -1], rval, overwrite); \ + tn = (C##_##X##_node_t*) cbst_skew((csmap___node_t*) tn); \ + tn = (C##_##X##_node_t*) cbst_split((csmap___node_t*) tn); \ + } \ + return tn; \ + } \ +\ + STC_DEF C##_##X##_value_t* \ + C##_##X##_find_priv_(C##_##X##_node_t *tn, const C##_##X##_rawkey_t* rkey, C##_##X##_iter_t* it) { \ + it->top = 0; \ + while (tn->level) \ + switch (C##_##X##_node_compare_rkey(tn, rkey)) { \ + case -1: tn = tn->link[1]; break; \ + case 1: it->stk[it->top++] = tn; tn = tn->link[0]; break; \ + case 0: it->ref = &tn->value; it->tn = tn->link[1]; return it->ref; \ + } \ + return (it->ref = NULL); \ + } \ +\ + STC_DEF C##_##X##_result_t \ + C##_##X##_insert_key_(C##_##X* self, RawKey rkey) { \ + C##_##X##_result_t res = {NULL, false}; \ + if (res.second) { \ + *KEY_REF_##C(res.first) = keyFromRaw(rkey); \ + ++self->size; \ + } \ + return res; \ + } \ +\ + STC_DEF C##_##X##_node_t * \ + C##_##X##_clone_nodes(C##_##X##_node_t *tn) { \ + if (! tn->level) return tn; \ + C##_##X##_node_t *x = c_new_1(C##_##X##_node_t); \ + x->link[0] = C##_##X##_clone_nodes(tn->link[0]); \ + x->link[1] = C##_##X##_clone_nodes(tn->link[1]); \ + x->level = tn->level; \ + x->value = C##_##X##_value_clone(tn->value); \ + return x; \ + } \ +\ + STC_DEF C##_##X \ + C##_##X##_clone(C##_##X bst) { \ + C##_##X clone = {C##_##X##_clone_nodes(bst.root), bst.size}; \ + return clone; \ + } + +_using_CBST_types(_, csmap, int, int); +static csmap___node_t cbst_nil = {&cbst_nil, &cbst_nil, 0}; + +/* +STC_DEF csmap___node_t * +cbst_remove(csmap___node_t *tn, csmap___value_t value) { + if (tn->level == 0) + return tn; + int cmp = c_default_compare(&tn->value, &value); + if (cmp != 0) + tn->link[cmp == -1] = cbst_remove(tn->link[cmp == -1], value); + else { // found + if (tn->link[0]->level && tn->link[1]->level) { + csmap___node_t *h = tn->link[0]; + while (h->link[1]->level) + h = h->link[1]; + tn->value = h->value; + tn->link[0] = cbst_remove(tn->link[0], tn->value); + } else { + csmap___node_t *tmp = tn; + tn = tn->link[tn->link[0]->level == 0]; + free(tmp); + } + } + if (tn->link[0]->level < tn->level - 1 || tn->link[1]->level < tn->level - 1) { + if (tn->link[1]->level > --tn->level) + tn->link[1]->level = tn->level; + tn = cbst_skew(tn); + tn = cbst_split(tn); + } + return tn; +} + +*/ + +STC_DEF csmap___node_t * +cbst_skew(csmap___node_t *tn) { + if (tn->link[0]->level == tn->level && tn->level) { + csmap___node_t *tmp = tn->link[0]; + tn->link[0] = tmp->link[1]; + tmp->link[1] = tn; + tn = tmp; + } + return tn; +} + +STC_DEF csmap___node_t * +cbst_split(csmap___node_t *tn) { + if (tn->link[1]->link[1]->level == tn->level && tn->level) { + csmap___node_t *tmp = tn->link[1]; + tn->link[1] = tmp->link[0]; + tmp->link[0] = tn; + tn = tmp; + ++tn->level; + } + return tn; +} + +STC_DEF void +cbst_next(csmap___iter_t *it) { + csmap___node_t *tn = it->tn; + if (tn->level == 0 && it->top == 0) + it->ref = NULL; + else { + while (tn->level) { + it->stk[it->top++] = tn; + tn = tn->link[0]; + } + tn = it->stk[--it->top]; + it->ref = &tn->value; + it->tn = tn->link[1]; + } +} + + +#else +#define _implement_CBST(X, C, Key, Mapped, mappedDel, keyCompareRaw, keyDel, \ + keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) +#endif + +#endif + +using_csset(i, int); +using_csmap(ii, int, int); +using_csmap(ss, cstr, cstr, cstr_del, cstr_clone, cstr_compare_ref, cstr_del, cstr_clone); + +int main() +{ + +} \ No newline at end of file diff --git a/stc/cmap.h b/stc/cmap.h index 210c7282..ea472e1d 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -23,6 +23,7 @@ #ifndef CMAP__H__ #define CMAP__H__ +// Unordered set/map - implemented as open hashing with linear probing and no tombstones. /* #include #include @@ -54,11 +55,11 @@ int main(void) { #include #include -#define cmap_inits {NULL, NULL, 0, 0, 0.15f, 0.85f} -#define cset_inits cmap_inits +#define cmap_inits {NULL, NULL, 0, 0, 0.15f, 0.85f} +#define cset_inits cmap_inits -#define c_try_emplace(self, ctype, key, val) do { \ - ctype##_result_t __r = ctype##_insert_key_(self, key); \ +#define c_try_emplace(self, C, key, val) do { \ + C##_result_t __r = C##_insert_key_(self, key); \ if (__r.second) __r.first->second = val; \ } while (0) @@ -90,11 +91,6 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; _using_CHASH(X, cmap, Key, Mapped, mappedDel, keyEqualsRaw, keyHashRaw, keyDel, \ keyFromRaw, keyToRaw, RawKey, mappedClone, c_default_to_raw, Mapped) -#define using_cmap_13(X, Key, Mapped, mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ - keyEqualsRaw, keyHashRaw, keyDel, keyFromRaw, keyToRaw, RawKey) \ - _using_CHASH(X, cmap, Key, Mapped, mappedDel, keyEqualsRaw, keyHashRaw, keyDel, \ - keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) - /* cset: */ #define using_cset(...) \ c_MACRO_OVERLOAD(using_cset, __VA_ARGS__) @@ -142,227 +138,227 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; _using_CHASH(X, cmap, Key, cstr_t, cstr_del, keyEquals, keyHash, keyDel, \ keyFromRaw, keyToRaw, RawKey, cstr_from, cstr_to_raw, const char*) -#define _using_CHASH_strkey(X, ctype, Mapped, mappedDel, mappedClone) \ - _using_CHASH(X, ctype, cstr_t, Mapped, mappedDel, cstr_equals_raw, cstr_hash_raw, cstr_del, \ +#define _using_CHASH_strkey(X, C, Mapped, mappedDel, mappedClone) \ + _using_CHASH(X, C, cstr_t, Mapped, mappedDel, cstr_equals_raw, cstr_hash_raw, cstr_del, \ cstr_from, cstr_to_raw, const char*, mappedClone, c_default_to_raw, Mapped) -#define CSET_ONLY_cset(...) __VA_ARGS__ -#define CSET_ONLY_cmap(...) -#define CMAP_ONLY_cset(...) -#define CMAP_ONLY_cmap(...) __VA_ARGS__ -#define KEY_REF_cset(e) (*(e)) -#define KEY_REF_cmap(e) (e)->first +#define SET_ONLY_cset(...) __VA_ARGS__ +#define SET_ONLY_cmap(...) +#define MAP_ONLY_cset(...) +#define MAP_ONLY_cmap(...) __VA_ARGS__ +#define KEY_REF_cset(vp) (vp) +#define KEY_REF_cmap(vp) (&(vp)->first) -#define _using_CHASH(X, ctype, Key, Mapped, mappedDel, keyEqualsRaw, keyHashRaw, keyDel, \ +#define _using_CHASH(X, C, Key, Mapped, mappedDel, keyEqualsRaw, keyHashRaw, keyDel, \ keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ - typedef Key ctype##_##X##_key_t; \ - typedef Mapped ctype##_##X##_mapped_t; \ - typedef RawKey ctype##_##X##_rawkey_t; \ - typedef RawMapped ctype##_##X##_rawmapped_t; \ + typedef Key C##_##X##_key_t; \ + typedef Mapped C##_##X##_mapped_t; \ + typedef RawKey C##_##X##_rawkey_t; \ + typedef RawMapped C##_##X##_rawmapped_t; \ \ - typedef CSET_ONLY_##ctype( ctype##_##X##_key_t ) \ - CMAP_ONLY_##ctype( struct {ctype##_##X##_key_t first; \ - ctype##_##X##_mapped_t second;} ) \ - ctype##_##X##_value_t; \ + typedef SET_ONLY_##C( C##_##X##_key_t ) \ + MAP_ONLY_##C( struct {C##_##X##_key_t first; \ + C##_##X##_mapped_t second;} ) \ + C##_##X##_value_t; \ \ STC_INLINE void \ - ctype##_##X##_entry_del(ctype##_##X##_value_t* e) { \ - keyDel(&KEY_REF_##ctype(e)); \ - CMAP_ONLY_##ctype(mappedDel(&e->second);) \ + C##_##X##_entry_del(C##_##X##_value_t* e) { \ + keyDel(KEY_REF_##C(e)); \ + MAP_ONLY_##C(mappedDel(&e->second);) \ } \ - typedef CSET_ONLY_##ctype( ctype##_##X##_rawkey_t ) \ - CMAP_ONLY_##ctype( struct {ctype##_##X##_rawkey_t first; \ - ctype##_##X##_rawmapped_t second;} ) \ - ctype##_##X##_rawvalue_t; \ + typedef SET_ONLY_##C( C##_##X##_rawkey_t ) \ + MAP_ONLY_##C( struct {C##_##X##_rawkey_t first; \ + C##_##X##_rawmapped_t second;} ) \ + C##_##X##_rawvalue_t; \ \ typedef struct { \ - ctype##_##X##_value_t *first; \ + C##_##X##_value_t *first; \ bool second; /* inserted */ \ - } ctype##_##X##_result_t; \ + } C##_##X##_result_t; \ \ typedef struct { \ - ctype##_##X##_value_t* table; \ + C##_##X##_value_t* table; \ uint8_t* _hashx; \ uint32_t size, bucket_count; \ float min_load_factor; \ float max_load_factor; \ - } ctype##_##X; \ + } C##_##X; \ \ typedef struct { \ - ctype##_##X##_value_t *ref; \ + C##_##X##_value_t *ref; \ uint8_t* _hx; \ - } ctype##_##X##_iter_t; \ + } C##_##X##_iter_t; \ \ - STC_INLINE ctype##_##X \ - ctype##_##X##_init(void) {ctype##_##X m = cmap_inits; return m;} \ + STC_INLINE C##_##X \ + C##_##X##_init(void) {C##_##X m = cmap_inits; return m;} \ STC_INLINE bool \ - ctype##_##X##_empty(ctype##_##X m) {return m.size == 0;} \ + C##_##X##_empty(C##_##X m) {return m.size == 0;} \ STC_INLINE size_t \ - ctype##_##X##_size(ctype##_##X m) {return (size_t) m.size;} \ - STC_INLINE ctype##_##X##_value_t \ - ctype##_##X##_value_clone(ctype##_##X##_value_t val) { \ - KEY_REF_##ctype(&val) = keyFromRaw(keyToRaw(&KEY_REF_##ctype(&val))); \ - CMAP_ONLY_##ctype( val.second = mappedFromRaw(mappedToRaw(&val.second)); ) \ + C##_##X##_size(C##_##X m) {return (size_t) m.size;} \ + STC_INLINE C##_##X##_value_t \ + C##_##X##_value_clone(C##_##X##_value_t val) { \ + *KEY_REF_##C(&val) = keyFromRaw(keyToRaw(KEY_REF_##C(&val))); \ + MAP_ONLY_##C( val.second = mappedFromRaw(mappedToRaw(&val.second)); ) \ return val; \ } \ STC_INLINE void \ - ctype##_##X##_value_del(ctype##_##X##_value_t* val) { \ - keyDel(&KEY_REF_##ctype(val)); \ - CMAP_ONLY_##ctype( mappedDel(&val->second); ) \ + C##_##X##_value_del(C##_##X##_value_t* val) { \ + keyDel(KEY_REF_##C(val)); \ + MAP_ONLY_##C( mappedDel(&val->second); ) \ } \ STC_INLINE size_t \ - ctype##_##X##_bucket_count(ctype##_##X m) {return (size_t) m.bucket_count;} \ + C##_##X##_bucket_count(C##_##X m) {return (size_t) m.bucket_count;} \ STC_INLINE size_t \ - ctype##_##X##_capacity(ctype##_##X m) {return (size_t) (m.bucket_count * m.max_load_factor);} \ + C##_##X##_capacity(C##_##X m) {return (size_t) (m.bucket_count * m.max_load_factor);} \ STC_INLINE void \ - ctype##_##X##_swap(ctype##_##X* a, ctype##_##X* b) {c_swap(ctype##_##X, *a, *b);} \ + C##_##X##_swap(C##_##X* a, C##_##X* b) {c_swap(C##_##X, *a, *b);} \ STC_INLINE void \ - ctype##_##X##_set_load_factors(ctype##_##X* self, float min_load, float max_load) { \ + C##_##X##_set_load_factors(C##_##X* self, float min_load, float max_load) { \ self->min_load_factor = min_load; \ self->max_load_factor = max_load; \ } \ - STC_API ctype##_##X \ - ctype##_##X##_with_capacity(size_t cap); \ - STC_API ctype##_##X \ - ctype##_##X##_clone(ctype##_##X m); \ + STC_API C##_##X \ + C##_##X##_with_capacity(size_t cap); \ + STC_API C##_##X \ + C##_##X##_clone(C##_##X m); \ STC_API void \ - ctype##_##X##_reserve(ctype##_##X* self, size_t size); \ + C##_##X##_reserve(C##_##X* self, size_t size); \ STC_API void \ - ctype##_##X##_push_n(ctype##_##X* self, const ctype##_##X##_rawvalue_t arr[], size_t size); \ + C##_##X##_push_n(C##_##X* self, const C##_##X##_rawvalue_t arr[], size_t size); \ STC_API void \ - ctype##_##X##_del(ctype##_##X* self); \ + C##_##X##_del(C##_##X* self); \ STC_API void \ - ctype##_##X##_clear(ctype##_##X* self); \ - STC_API ctype##_##X##_value_t* \ - ctype##_##X##_find(const ctype##_##X* self, RawKey rkey); \ + C##_##X##_clear(C##_##X* self); \ + STC_API C##_##X##_value_t* \ + C##_##X##_find(const C##_##X* self, RawKey rkey); \ STC_API bool \ - ctype##_##X##_contains(const ctype##_##X* self, RawKey rkey); \ + C##_##X##_contains(const C##_##X* self, RawKey rkey); \ \ - STC_API ctype##_##X##_result_t \ - ctype##_##X##_insert_key_(ctype##_##X* self, RawKey rkey); \ - STC_API ctype##_bucket_t \ - ctype##_##X##_bucket(const ctype##_##X* self, const ctype##_##X##_rawkey_t* rkeyptr); \ + STC_API C##_##X##_result_t \ + C##_##X##_insert_key_(C##_##X* self, RawKey rkey); \ + STC_API C##_bucket_t \ + C##_##X##_bucket(const C##_##X* self, const C##_##X##_rawkey_t* rkeyptr); \ \ - STC_INLINE ctype##_##X##_result_t \ - ctype##_##X##_emplace(ctype##_##X* self, RawKey rkey CMAP_ONLY_##ctype(, RawMapped rmapped)) { \ - ctype##_##X##_result_t res = ctype##_##X##_insert_key_(self, rkey); \ - CMAP_ONLY_##ctype( if (res.second) res.first->second = mappedFromRaw(rmapped); ) \ + STC_INLINE C##_##X##_result_t \ + C##_##X##_emplace(C##_##X* self, RawKey rkey MAP_ONLY_##C(, RawMapped rmapped)) { \ + C##_##X##_result_t res = C##_##X##_insert_key_(self, rkey); \ + MAP_ONLY_##C( if (res.second) res.first->second = mappedFromRaw(rmapped); ) \ return res; \ } \ - STC_INLINE ctype##_##X##_result_t \ - ctype##_##X##_insert(ctype##_##X* self, ctype##_##X##_rawvalue_t raw) { \ - return CSET_ONLY_##ctype(ctype##_##X##_insert_key_(self, raw)) \ - CMAP_ONLY_##ctype(ctype##_##X##_emplace(self, raw.first, raw.second)); \ + STC_INLINE C##_##X##_result_t \ + C##_##X##_insert(C##_##X* self, C##_##X##_rawvalue_t raw) { \ + return SET_ONLY_##C(C##_##X##_insert_key_(self, raw)) \ + MAP_ONLY_##C(C##_##X##_emplace(self, raw.first, raw.second)); \ } \ \ - CMAP_ONLY_##ctype( \ - STC_INLINE ctype##_##X##_result_t \ - ctype##_##X##_put(ctype##_##X* self, RawKey rkey, RawMapped rmapped) { \ - ctype##_##X##_result_t res = ctype##_##X##_insert_key_(self, rkey); \ + MAP_ONLY_##C( \ + STC_INLINE C##_##X##_result_t \ + C##_##X##_put(C##_##X* self, RawKey rkey, RawMapped rmapped) { \ + C##_##X##_result_t res = C##_##X##_insert_key_(self, rkey); \ if (!res.second) mappedDel(&res.first->second); \ res.first->second = mappedFromRaw(rmapped); return res; \ } \ - STC_INLINE ctype##_##X##_result_t \ - ctype##_##X##_insert_or_assign(ctype##_##X* self, RawKey rkey, RawMapped rmapped) { \ - return ctype##_##X##_put(self, rkey, rmapped); \ + STC_INLINE C##_##X##_result_t \ + C##_##X##_insert_or_assign(C##_##X* self, RawKey rkey, RawMapped rmapped) { \ + return C##_##X##_put(self, rkey, rmapped); \ } \ - STC_INLINE ctype##_##X##_result_t \ - ctype##_##X##_put_mapped(ctype##_##X* self, RawKey rkey, Mapped mapped) { \ - ctype##_##X##_result_t res = ctype##_##X##_insert_key_(self, rkey); \ + STC_INLINE C##_##X##_result_t \ + C##_##X##_put_mapped(C##_##X* self, RawKey rkey, Mapped mapped) { \ + C##_##X##_result_t res = C##_##X##_insert_key_(self, rkey); \ if (!res.second) mappedDel(&res.first->second); \ res.first->second = mapped; return res; \ } \ - STC_INLINE ctype##_##X##_mapped_t* \ - ctype##_##X##_at(const ctype##_##X* self, RawKey rkey) { \ - ctype##_bucket_t b = ctype##_##X##_bucket(self, &rkey); \ + STC_INLINE C##_##X##_mapped_t* \ + C##_##X##_at(const C##_##X* self, RawKey rkey) { \ + C##_bucket_t b = C##_##X##_bucket(self, &rkey); \ assert(self->_hashx[b.idx]); \ return &self->table[b.idx].second; \ }) \ \ - STC_INLINE ctype##_##X##_iter_t \ - ctype##_##X##_begin(ctype##_##X* self) { \ - ctype##_##X##_iter_t it = {self->table, self->_hashx}; \ + STC_INLINE C##_##X##_iter_t \ + C##_##X##_begin(C##_##X* self) { \ + C##_##X##_iter_t it = {self->table, self->_hashx}; \ if (it._hx) while (*it._hx == 0) ++it.ref, ++it._hx; \ return it; \ } \ - STC_INLINE ctype##_##X##_iter_t \ - ctype##_##X##_end(ctype##_##X* self) {\ - ctype##_##X##_iter_t it = {self->table + self->bucket_count}; return it; \ + STC_INLINE C##_##X##_iter_t \ + C##_##X##_end(C##_##X* self) {\ + C##_##X##_iter_t it = {self->table + self->bucket_count}; return it; \ } \ STC_INLINE void \ - ctype##_##X##_next(ctype##_##X##_iter_t* it) { \ + C##_##X##_next(C##_##X##_iter_t* it) { \ while ((++it->ref, *++it->_hx == 0)) ; \ } \ - STC_INLINE ctype##_##X##_mapped_t* \ - ctype##_##X##_itval(ctype##_##X##_iter_t it) {return CMAP_ONLY_##ctype(&it.ref->second) \ - CSET_ONLY_##ctype(it.ref);} \ + STC_INLINE C##_##X##_mapped_t* \ + C##_##X##_itval(C##_##X##_iter_t it) {return MAP_ONLY_##C(&it.ref->second) \ + SET_ONLY_##C(it.ref);} \ \ STC_API void \ - ctype##_##X##_erase_entry(ctype##_##X* self, ctype##_##X##_value_t* val); \ + C##_##X##_erase_entry(C##_##X* self, C##_##X##_value_t* val); \ STC_INLINE size_t \ - ctype##_##X##_erase(ctype##_##X* self, RawKey rkey) { \ + C##_##X##_erase(C##_##X* self, RawKey rkey) { \ if (self->size == 0) return 0; \ - ctype##_bucket_t b = ctype##_##X##_bucket(self, &rkey); \ - return self->_hashx[b.idx] ? ctype##_##X##_erase_entry(self, self->table + b.idx), 1 : 0; \ + C##_bucket_t b = C##_##X##_bucket(self, &rkey); \ + return self->_hashx[b.idx] ? C##_##X##_erase_entry(self, self->table + b.idx), 1 : 0; \ } \ - STC_INLINE ctype##_##X##_iter_t \ - ctype##_##X##_erase_at(ctype##_##X* self, ctype##_##X##_iter_t pos) { \ - ctype##_##X##_erase_entry(self, pos.ref); \ - ctype##_##X##_next(&pos); return pos; \ + STC_INLINE C##_##X##_iter_t \ + C##_##X##_erase_at(C##_##X* self, C##_##X##_iter_t pos) { \ + C##_##X##_erase_entry(self, pos.ref); \ + C##_##X##_next(&pos); return pos; \ } \ \ STC_API uint32_t c_default_hash(const void *data, size_t len); \ STC_API uint32_t c_default_hash32(const void* data, size_t len); \ \ - _c_implement_CHASH(X, ctype, Key, Mapped, mappedDel, keyEqualsRaw, keyHashRaw, keyDel, \ - keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ - typedef ctype##_##X ctype##_##X##_t + _implement_CHASH(X, C, Key, Mapped, mappedDel, keyEqualsRaw, keyHashRaw, keyDel, \ + keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ + typedef C##_##X C##_##X##_t /* -------------------------- IMPLEMENTATION ------------------------- */ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -#define _c_implement_CHASH(X, ctype, Key, Mapped, mappedDel, keyEqualsRaw, keyHashRaw, keyDel, \ - keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ - STC_DEF ctype##_##X \ - ctype##_##X##_with_capacity(size_t cap) { \ - ctype##_##X h = ctype##_inits; \ - ctype##_##X##_reserve(&h, cap); \ +#define _implement_CHASH(X, C, Key, Mapped, mappedDel, keyEqualsRaw, keyHashRaw, keyDel, \ + keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ + STC_DEF C##_##X \ + C##_##X##_with_capacity(size_t cap) { \ + C##_##X h = C##_inits; \ + C##_##X##_reserve(&h, cap); \ return h; \ } \ STC_DEF void \ - ctype##_##X##_push_n(ctype##_##X* self, const ctype##_##X##_rawvalue_t arr[], size_t n) { \ - for (size_t i=0; isize == 0) return; \ - ctype##_##X##_value_t* e = self->table, *end = e + self->bucket_count; \ + C##_##X##_value_t* e = self->table, *end = e + self->bucket_count; \ uint8_t *hx = self->_hashx; \ - for (; e != end; ++e) if (*hx++) ctype##_##X##_entry_del(e); \ + for (; e != end; ++e) if (*hx++) C##_##X##_entry_del(e); \ } \ \ - STC_DEF void ctype##_##X##_del(ctype##_##X* self) { \ - ctype##_##X##_wipe_(self); \ + STC_DEF void C##_##X##_del(C##_##X* self) { \ + C##_##X##_wipe_(self); \ c_free(self->_hashx); \ c_free(self->table); \ } \ \ - STC_DEF void ctype##_##X##_clear(ctype##_##X* self) { \ - ctype##_##X##_wipe_(self); \ + STC_DEF void C##_##X##_clear(C##_##X* self) { \ + C##_##X##_wipe_(self); \ self->size = 0; \ memset(self->_hashx, 0, self->bucket_count); \ } \ \ - STC_DEF ctype##_bucket_t \ - ctype##_##X##_bucket(const ctype##_##X* self, const ctype##_##X##_rawkey_t* rkeyptr) { \ - uint32_t sx, hash = keyHashRaw(rkeyptr, sizeof(ctype##_##X##_rawkey_t)); \ + STC_DEF C##_bucket_t \ + C##_##X##_bucket(const C##_##X* self, const C##_##X##_rawkey_t* rkeyptr) { \ + uint32_t sx, hash = keyHashRaw(rkeyptr, sizeof(C##_##X##_rawkey_t)); \ size_t cap = self->bucket_count; \ - ctype##_bucket_t b = {chash_reduce(hash, cap), (hash & chash_HASH) | chash_USED}; \ + C##_bucket_t b = {chash_reduce(hash, cap), (hash & chash_HASH) | chash_USED}; \ uint8_t* hashx = self->_hashx; \ while ((sx = hashx[b.idx])) { \ if (sx == b.hx) { \ - ctype##_##X##_rawkey_t r = keyToRaw(&KEY_REF_##ctype(self->table + b.idx)); \ + C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(self->table + b.idx)); \ if (keyEqualsRaw(&r, rkeyptr)) break; \ } \ if (++b.idx == cap) b.idx = 0; \ @@ -370,67 +366,67 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; return b; \ } \ \ - STC_DEF ctype##_##X##_value_t* \ - ctype##_##X##_find(const ctype##_##X* self, RawKey rkey) { \ + STC_DEF C##_##X##_value_t* \ + C##_##X##_find(const C##_##X* self, RawKey rkey) { \ if (self->size == 0) return NULL; \ - ctype##_bucket_t b = ctype##_##X##_bucket(self, &rkey); \ + C##_bucket_t b = C##_##X##_bucket(self, &rkey); \ return self->_hashx[b.idx] ? &self->table[b.idx] : NULL; \ } \ \ STC_DEF bool \ - ctype##_##X##_contains(const ctype##_##X* self, RawKey rkey) { \ - return self->size && self->_hashx[ctype##_##X##_bucket(self, &rkey).idx]; \ + C##_##X##_contains(const C##_##X* self, RawKey rkey) { \ + return self->size && self->_hashx[C##_##X##_bucket(self, &rkey).idx]; \ } \ \ - STC_INLINE void ctype##_##X##_reserve_expand_(ctype##_##X* self) { \ + STC_INLINE void C##_##X##_reserve_expand_(C##_##X* self) { \ if (self->size + 1 >= self->bucket_count * self->max_load_factor) \ - ctype##_##X##_reserve(self, 5 + self->size * 3 / 2); \ + C##_##X##_reserve(self, 5 + self->size * 3 / 2); \ } \ - STC_DEF ctype##_##X##_result_t \ - ctype##_##X##_insert_key_(ctype##_##X* self, RawKey rkey) { \ - ctype##_##X##_reserve_expand_(self); \ - ctype##_bucket_t b = ctype##_##X##_bucket(self, &rkey); \ - ctype##_##X##_result_t res = {&self->table[b.idx], !self->_hashx[b.idx]}; \ + STC_DEF C##_##X##_result_t \ + C##_##X##_insert_key_(C##_##X* self, RawKey rkey) { \ + C##_##X##_reserve_expand_(self); \ + C##_bucket_t b = C##_##X##_bucket(self, &rkey); \ + C##_##X##_result_t res = {&self->table[b.idx], !self->_hashx[b.idx]}; \ if (res.second) { \ - KEY_REF_##ctype(res.first) = keyFromRaw(rkey); \ + *KEY_REF_##C(res.first) = keyFromRaw(rkey); \ self->_hashx[b.idx] = (uint8_t) b.hx; \ ++self->size; \ } \ return res; \ } \ \ - STC_DEF ctype##_##X \ - ctype##_##X##_clone(ctype##_##X m) { \ - ctype##_##X clone = { \ - c_new_2(ctype##_##X##_value_t, m.bucket_count), \ + STC_DEF C##_##X \ + C##_##X##_clone(C##_##X m) { \ + C##_##X clone = { \ + c_new_2(C##_##X##_value_t, m.bucket_count), \ (uint8_t *) memcpy(c_malloc(m.bucket_count + 1), m._hashx, m.bucket_count + 1), \ m.size, m.bucket_count, m.min_load_factor, m.max_load_factor \ }; \ - ctype##_##X##_value_t *e = m.table, *end = e + m.bucket_count, *dst = clone.table; \ + C##_##X##_value_t *e = m.table, *end = e + m.bucket_count, *dst = clone.table; \ for (uint8_t *hx = m._hashx; e != end; ++hx, ++e, ++dst) \ - if (*hx) *dst = ctype##_##X##_value_clone(*e); \ + if (*hx) *dst = C##_##X##_value_clone(*e); \ return clone; \ } \ \ STC_DEF void \ - ctype##_##X##_reserve(ctype##_##X* self, size_t newcap) { \ + C##_##X##_reserve(C##_##X* self, size_t newcap) { \ if (newcap < self->size) return; \ size_t oldcap = self->bucket_count; \ newcap = (size_t) (newcap / self->max_load_factor) | 1; \ - ctype##_##X tmp = { \ - c_new_2 (ctype##_##X##_value_t, newcap), \ + C##_##X tmp = { \ + c_new_2 (C##_##X##_value_t, newcap), \ (uint8_t *) c_calloc(newcap + 1, sizeof(uint8_t)), \ self->size, (uint32_t) newcap, \ self->min_load_factor, self->max_load_factor \ }; \ /* Rehash: */ \ - tmp._hashx[newcap] = 0xff; c_swap(ctype##_##X, *self, tmp); \ - ctype##_##X##_value_t* e = tmp.table, *slot = self->table; \ + tmp._hashx[newcap] = 0xff; c_swap(C##_##X, *self, tmp); \ + C##_##X##_value_t* e = tmp.table, *slot = self->table; \ uint8_t* hashx = self->_hashx; \ for (size_t i = 0; i < oldcap; ++i, ++e) \ if (tmp._hashx[i]) { \ - RawKey r = keyToRaw(&KEY_REF_##ctype(e)); \ - ctype##_bucket_t b = ctype##_##X##_bucket(self, &r); \ + RawKey r = keyToRaw(KEY_REF_##C(e)); \ + C##_bucket_t b = C##_##X##_bucket(self, &r); \ slot[b.idx] = *e, \ hashx[b.idx] = (uint8_t) b.hx; \ } \ @@ -439,23 +435,23 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; } \ \ STC_DEF void \ - ctype##_##X##_erase_entry(ctype##_##X* self, ctype##_##X##_value_t* val) { \ + C##_##X##_erase_entry(C##_##X* self, C##_##X##_value_t* val) { \ size_t i = chash_entry_index(*self, val), j = i, k, cap = self->bucket_count; \ - ctype##_##X##_value_t* slot = self->table; \ + C##_##X##_value_t* slot = self->table; \ uint8_t* hashx = self->_hashx; \ - ctype##_##X##_entry_del(&slot[i]); \ + C##_##X##_entry_del(&slot[i]); \ do { /* deletion from hash table without tombstone */ \ if (++j == cap) j = 0; /* ++j; j %= cap; is slow */ \ if (! hashx[j]) \ break; \ - RawKey r = keyToRaw(&KEY_REF_##ctype(slot + j)); \ + RawKey r = keyToRaw(KEY_REF_##C(slot + j)); \ k = chash_reduce(keyHashRaw(&r, sizeof(RawKey)), 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, k = --self->size; \ if ((float) k / cap < self->min_load_factor && k > 512) \ - ctype##_##X##_reserve(self, k*1.2); \ + C##_##X##_reserve(self, k*1.2); \ } /* https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ */ @@ -474,8 +470,8 @@ STC_DEF uint32_t c_default_hash32(const void* data, size_t len) { } #else -#define _c_implement_CHASH(X, ctype, Key, Mapped, mappedDel, keyEqualsRaw, keyHashRaw, keyDel, \ - keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) +#define _implement_CHASH(X, C, Key, Mapped, mappedDel, keyEqualsRaw, keyHashRaw, keyDel, \ + keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) #endif #endif -- cgit v1.2.3