From df0f4db2bb6ea55c0d45918e799b06a9970cec2b Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Tue, 2 Feb 2021 18:18:12 +0100 Subject: Rewrote unordered map AA-tree csmap.h. Now uses array as memory pool instead of individual allocated nodes. 40% faster. V1 moved to examples. --- benchmarks/cmap_benchmark2.cpp | 39 +++- benchmarks/csmap_benchmark2.cpp | 105 ++++++--- examples/csmap_ex2.c | 21 ++ examples/csmap_v1.h | 507 ++++++++++++++++++++++++++++++++++++++++ stc/crandom.h | 21 +- stc/csmap.h | 332 +++++++++++++++----------- 6 files changed, 846 insertions(+), 179 deletions(-) create mode 100644 examples/csmap_ex2.c create mode 100644 examples/csmap_v1.h diff --git a/benchmarks/cmap_benchmark2.cpp b/benchmarks/cmap_benchmark2.cpp index 8624b741..65543712 100644 --- a/benchmarks/cmap_benchmark2.cpp +++ b/benchmarks/cmap_benchmark2.cpp @@ -16,10 +16,11 @@ enum {N1 = 4000000, S1 = 1, MaxLoadFactor100 = 80}; uint64_t seed = time(NULL); static inline uint32_t hash32(const void* data, size_t len) { - return (uint32_t) ((*(const uint32_t *) data) * 2654435769u); + return *(const uint32_t *)data * 2654435769u; } static inline uint32_t hash64(const void* data, size_t len) { - return (uint32_t) (((*(const uint64_t *) data) * 11400714819323198485ull) >> 24); + uint64_t x = *(const uint64_t *)data * 11400714819323198485ull; + return x ^ (x >> 24); } template using umap = std::unordered_map; template using bmap = ska::bytell_hash_map; @@ -127,14 +128,34 @@ static void ins_and_erase_cmap_i(picobench::state& s) cmap_i_del(&map); } +static void ins_and_erase_cmap_x(picobench::state& s) +{ + cmap_x map = cmap_x_init(); + cmap_x_set_load_factors(&map, 0.0, MaxLoadFactor100 / 100.0); + stc64_srandom(seed); + + picobench::scope scope(s); + c_forrange (s.iterations()) + cmap_x_emplace(&map, stc64_random(), 0); + cmap_x_clear(&map); + stc64_srandom(seed); + c_forrange (s.iterations()) + cmap_x_emplace(&map, stc64_random(), 0); + stc64_srandom(seed); + c_forrange (s.iterations()) + cmap_x_erase(&map, stc64_random()); + s.set_result(cmap_x_size(map)); + cmap_x_del(&map); +} + #define P samples(S1).iterations({N1/4}) -PICOBENCH(ins_and_erase_i).P; -PICOBENCH(ins_and_erase_i).P; -PICOBENCH(ins_and_erase_i).P; -PICOBENCH(ins_and_erase_i).P; -PICOBENCH(ins_and_erase_i).P; -PICOBENCH(ins_and_erase_i).P; -PICOBENCH(ins_and_erase_cmap_i).P; +PICOBENCH(ins_and_erase_i).P; +PICOBENCH(ins_and_erase_i).P; +PICOBENCH(ins_and_erase_i).P; +PICOBENCH(ins_and_erase_i).P; +PICOBENCH(ins_and_erase_i).P; +PICOBENCH(ins_and_erase_i).P; +PICOBENCH(ins_and_erase_cmap_x).P; #undef P PICOBENCH_SUITE("Map3"); diff --git a/benchmarks/csmap_benchmark2.cpp b/benchmarks/csmap_benchmark2.cpp index 8ef45d9a..770bdde5 100644 --- a/benchmarks/csmap_benchmark2.cpp +++ b/benchmarks/csmap_benchmark2.cpp @@ -1,3 +1,4 @@ +#include #include #include #include @@ -8,8 +9,8 @@ #define PICOBENCH_IMPLEMENT_WITH_MAIN #include "picobench.hpp" -enum {N1 = 2000000, S1 = 1}; -uint64_t seed = time(NULL); +enum {N1 = 3000000, S1 = 1}; +uint64_t seed = time(NULL); // 18237129837891; using omap_i = std::map; using omap_x = std::map; @@ -25,7 +26,6 @@ template static void ctor_and_ins_one_i(picobench::state& s) { size_t result = 0; - picobench::scope scope(s); c_forrange (n, s.iterations()) { MapInt map; @@ -38,7 +38,6 @@ static void ctor_and_ins_one_i(picobench::state& s) static void ctor_and_ins_one_csmap_i(picobench::state& s) { size_t result = 0; - picobench::scope scope(s); c_forrange (n, s.iterations()) { csmap_i map = csmap_i_init(); @@ -50,54 +49,96 @@ static void ctor_and_ins_one_csmap_i(picobench::state& s) } #define P samples(S1).iterations({N1}) -PICOBENCH(ctor_and_ins_one_i).P; -PICOBENCH(ctor_and_ins_one_csmap_i).P; +//PICOBENCH(ctor_and_ins_one_i).P; +//PICOBENCH(ctor_and_ins_one_csmap_i).P; +#undef P + + +PICOBENCH_SUITE("Map_insert_only"); + +template +static void insert_i(picobench::state& s) +{ + size_t result = 0; + MapInt map; + stc64_srandom(seed); + s.start_timer(); + c_forrange (n, s.iterations()) + map.emplace(stc64_random() & 0xfffffff, n); + s.set_result(map.size()); + s.stop_timer(); +} + +static void insert_csmap_i(picobench::state& s) +{ + size_t result = 0; + csmap_i map = csmap_i_init(); + stc64_srandom(seed); + s.start_timer(); + c_forrange (n, s.iterations()) + csmap_i_emplace(&map, stc64_random() & 0xfffffff, n); + s.set_result(csmap_i_size(map)); + s.stop_timer(); + csmap_i_del(&map); +} + +#define P samples(S1).iterations({N1}) +//PICOBENCH(insert_i).P; +//PICOBENCH(insert_csmap_i).P; #undef P + PICOBENCH_SUITE("Map2"); template static void ins_and_erase_i(picobench::state& s) { size_t result = 0; + uint64_t mask = (1ull << s.arg()) - 1; MapInt map; stc64_srandom(seed); picobench::scope scope(s); - c_forrange (s.iterations()) - map.emplace(stc64_random(), 0); + c_forrange (i, s.iterations()) + map.emplace(stc64_random() & mask, i); + result = map.size(); + map.clear(); stc64_srandom(seed); - c_forrange (s.iterations()) - map.emplace(stc64_random(), 0); + c_forrange (i, s.iterations()) + map[stc64_random() & mask] = i; + stc64_srandom(seed); c_forrange (s.iterations()) - map.erase(stc64_random()); - s.set_result(map.size()); + map.erase(stc64_random() & mask); + s.set_result(result); } static void ins_and_erase_csmap_i(picobench::state& s) { + size_t result = 0; + uint64_t mask = (1ull << s.arg()) - 1; csmap_i map = csmap_i_init(); stc64_srandom(seed); picobench::scope scope(s); - c_forrange (s.iterations()) - csmap_i_emplace(&map, stc64_random(), 0); + c_forrange (i, s.iterations()) + csmap_i_emplace(&map, stc64_random() & mask, i); + result = csmap_i_size(map); csmap_i_clear(&map); stc64_srandom(seed); - c_forrange (s.iterations()) - csmap_i_emplace(&map, stc64_random(), 0); + c_forrange (i, s.iterations()) + csmap_i_put(&map, stc64_random() & mask, i); stc64_srandom(seed); c_forrange (s.iterations()) - csmap_i_erase(&map, stc64_random()); - s.set_result(csmap_i_size(map)); + csmap_i_erase(&map, stc64_random() & mask); + s.set_result(result); csmap_i_del(&map); } -#define P samples(S1).iterations({N1/4}) +#define P samples(S1).iterations({N1/2, N1/2, N1/2, N1/2}).args({18, 23, 25, 31}) PICOBENCH(ins_and_erase_i).P; PICOBENCH(ins_and_erase_csmap_i).P; #undef P @@ -113,9 +154,12 @@ static void ins_and_access_i(picobench::state& s) stc64_srandom(seed); picobench::scope scope(s); - c_forrange (N1) + c_forrange (N1) { result += ++map[stc64_random() & mask]; - s.set_result(result); + auto it = map.find(stc64_random() & mask); + if (it != map.end()) map.erase(it->first); + } + s.set_result(result + map.size()); } static void ins_and_access_csmap_i(picobench::state& s) @@ -126,9 +170,12 @@ static void ins_and_access_csmap_i(picobench::state& s) stc64_srandom(seed); picobench::scope scope(s); - c_forrange (N1) + c_forrange (N1) { result += ++csmap_i_emplace(&map, stc64_random() & mask, 0).first->second; - s.set_result(result); + csmap_i_value_t* val = csmap_i_find(&map, stc64_random() & mask); + if (val) csmap_i_erase(&map, val->first); + } + s.set_result(result + csmap_i_size(map)); csmap_i_del(&map); } @@ -164,7 +211,7 @@ static void ins_and_access_s(picobench::state& s) map.erase(it); } } - s.set_result(result); + s.set_result(result + map.size()); } static void ins_and_access_csmap_s(picobench::state& s) @@ -185,14 +232,14 @@ static void ins_and_access_csmap_s(picobench::state& s) csmap_s_erase(&map, val->first.str); } } - s.set_result(result); + s.set_result(result + csmap_s_size(map)); cstr_del(&str); csmap_s_del(&map); } #define P samples(S1).iterations({N1/5, N1/5, N1/5, N1/10, N1/40}).args({13, 7, 8, 100, 1000}) -PICOBENCH(ins_and_access_s).P; -PICOBENCH(ins_and_access_csmap_s).P; +//PICOBENCH(ins_and_access_s).P; +//PICOBENCH(ins_and_access_csmap_s).P; #undef P PICOBENCH_SUITE("Map5"); @@ -257,6 +304,6 @@ static void iterate_csmap_x(picobench::state& s) #define P samples(S1).iterations({N1/20}).args({12}) -PICOBENCH(iterate_x).P; -PICOBENCH(iterate_csmap_x).P; +//PICOBENCH(iterate_x).P; +//PICOBENCH(iterate_csmap_x).P; #undef P diff --git a/examples/csmap_ex2.c b/examples/csmap_ex2.c new file mode 100644 index 00000000..3c2d6cc7 --- /dev/null +++ b/examples/csmap_ex2.c @@ -0,0 +1,21 @@ +#include +#include +#include + +using_csmap(i, int, int); + +int main() +{ + csmap_i map = csmap_i_init(); + stc64_srandom(1); + c_forrange (i, 1000000) csmap_i_emplace(&map, stc64_random() & 0xffffff, i); + + size_t n = 0, sum = 0; + c_foreach (i, csmap_i, map) { + sum += i.ref->first; + if (n++ < 20) printf("%d: %d\n", i.ref->first, i.ref->second); + } + printf("size %zu: %zu\n", csmap_i_size(map), sum); + csmap_i_del(&map); + puts("done"); +} \ No newline at end of file diff --git a/examples/csmap_v1.h b/examples/csmap_v1.h new file mode 100644 index 00000000..806d6247 --- /dev/null +++ b/examples/csmap_v1.h @@ -0,0 +1,507 @@ +/* MIT License + * + * Copyright (c) 2021 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_sx_init(); + 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 + +#define using_csmap(...) \ + c_MACRO_OVERLOAD(using_csmap, __VA_ARGS__) + +#define using_csmap_3(X, Key, Mapped) \ + using_csmap_4(X, Key, Mapped, c_default_compare) + +#define using_csmap_4(X, Key, Mapped, keyCompare) \ + using_csmap_6(X, Key, Mapped, keyCompare, c_default_del, c_default_clone) + +#define using_csmap_6(X, Key, Mapped, keyCompare, mappedDel, mappedClone) \ + using_csmap_8(X, Key, Mapped, keyCompare, mappedDel, mappedClone, c_default_del, c_default_clone) + +#define using_csmap_8(X, Key, Mapped, keyCompare, mappedDel, mappedClone, keyDel, keyClone) \ + using_csmap_10(X, Key, Mapped, keyCompare, mappedDel, mappedClone, \ + keyDel, keyClone, c_default_to_raw, Key) + +#define using_csmap_10(X, Key, Mapped, keyCompareRaw, mappedDel, mappedClone, \ + keyDel, keyFromRaw, keyToRaw, RawKey) \ + _using_CBST(X, csmap, Key, Mapped, keyCompareRaw, mappedDel, 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, keyCompareRaw, _UNUSED_, 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_compare_raw, cstr_del, 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, cstr_compare_raw, mappedDel, 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, keyCompare, cstr_del, 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]; \ + uint8_t level; \ + C##_##X##_value_t value; \ + } C##_##X##_node_t; \ +\ + typedef struct { \ + C##_##X##_value_t *ref; \ + int _top; \ + C##_##X##_node_t *_tn, *_st[50]; \ + } C##_##X##_iter_t + + +#define _using_CBST(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \ + keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ + _using_CBST_types(X, C, Key, Mapped); \ +\ + typedef struct { \ + C##_##X##_node_t* root; \ + size_t size; \ + } C##_##X; \ +\ + 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_API C##_##X \ + C##_##X##_init(void); \ + 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_r_(C##_##X##_node_t* tn); \ +\ + STC_INLINE void \ + C##_##X##_del(C##_##X* self) {C##_##X##_del_r_(self->root);} \ + STC_INLINE void \ + C##_##X##_clear(C##_##X* self) {C##_##X##_del(self); *self = C##_##X##_init();} \ + STC_INLINE void \ + C##_##X##_swap(C##_##X* a, C##_##X* b) {c_swap(C##_##X, *a, *b);} \ +\ + 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_API C##_##X##_node_t* C##_##X##_clone_r_(C##_##X##_node_t *tn); \ + STC_INLINE C##_##X \ + C##_##X##_clone(C##_##X bst) { \ + C##_##X clone = {C##_##X##_clone_r_(bst.root), bst.size}; \ + return clone; \ + } \ +\ + STC_API C##_##X##_value_t* \ + C##_##X##_find_it(const C##_##X* self, RawKey rkey, C##_##X##_iter_t* out); \ +\ + STC_INLINE C##_##X##_value_t* \ + C##_##X##_find(const C##_##X* self, RawKey rkey) { \ + C##_##X##_iter_t it; \ + return C##_##X##_find_it(self, rkey, &it); \ + } \ + STC_INLINE bool \ + C##_##X##_contains(const C##_##X* self, RawKey rkey) { \ + return C##_##X##_find(self, rkey) != 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) ); \ + } \ + STC_INLINE void \ + C##_##X##_push_n(C##_##X* self, const C##_##X##_rawvalue_t arr[], size_t n) { \ + for (size_t i=0; isecond); \ + 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) { \ + C##_##X##_iter_t it; \ + return &C##_##X##_find_it(self, rkey, &it)->second; \ + }) \ +\ + 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_API void \ + C##_##X##_next(C##_##X##_iter_t* it); \ +\ + STC_INLINE C##_##X##_iter_t \ + C##_##X##_begin(C##_##X* self) { \ + C##_##X##_iter_t it = {NULL, 0, self->root}; \ + C##_##X##_next(&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 SET_ONLY_##C( it.ref ) \ + MAP_ONLY_##C( &it.ref->second );} \ +\ + STC_API C##_##X##_node_t* \ + C##_##X##_erase_r_(C##_##X##_node_t *tn, const C##_##X##_rawkey_t* rkey, int *erased); \ +\ + STC_INLINE size_t \ + C##_##X##_erase(C##_##X* self, RawKey rkey) { \ + int erased = 0; \ + self->root = C##_##X##_erase_r_(self->root, &rkey, &erased); \ + self->size -= erased; return erased; \ + } \ + STC_INLINE size_t \ + C##_##X##_erase_at(C##_##X* self, C##_##X##_iter_t pos) { \ + return C##_##X##_erase(self, keyToRaw(KEY_REF_##C(pos.ref))); \ + } \ +\ + _implement_CBST(X, C, Key, Mapped, keyCompareRaw, mappedDel, 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, keyCompareRaw, mappedDel, keyDel, \ + keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ + STC_DEF C##_##X \ + C##_##X##_init(void) { \ + C##_##X m = {(C##_##X##_node_t *) &cbst_nil, 0}; \ + return m; \ + } \ +\ + STC_DEF C##_##X##_value_t* \ + C##_##X##_find_it(const C##_##X* self, C##_##X##_rawkey_t rkey, C##_##X##_iter_t* out) { \ + C##_##X##_node_t *tn = self->root; \ + out->_top = 0; \ + while (tn->level) { \ + C##_##X##_rawkey_t rx = keyToRaw(KEY_REF_##C(&tn->value)); \ + switch (keyCompareRaw(&rx, &rkey)) { \ + case -1: tn = tn->link[1]; break; \ + case 1: out->_st[out->_top++] = tn; tn = tn->link[0]; break; \ + case 0: out->_tn = tn->link[1]; return (out->ref = &tn->value); \ + } \ + } \ + return (out->ref = NULL); \ + } \ +\ + STC_DEF void \ + C##_##X##_next(C##_##X##_iter_t *it) { \ + C##_##X##_node_t *tn = it->_tn; \ + if (it->_top || tn->level) { \ + while (tn->level) { \ + it->_st[it->_top++] = tn; \ + tn = tn->link[0]; \ + } \ + tn = it->_st[--it->_top]; \ + it->_tn = tn->link[1]; \ + it->ref = &tn->value; \ + } else \ + it->ref = NULL; \ + } \ +\ + static C##_##X##_node_t * \ + C##_##X##_skew_(C##_##X##_node_t *tn) { \ + if (tn->link[0]->level == tn->level && tn->level) { \ + C##_##X##_node_t *tmp = tn->link[0]; \ + tn->link[0] = tmp->link[1]; \ + tmp->link[1] = tn; \ + tn = tmp; \ + } \ + return tn; \ + } \ +\ + static C##_##X##_node_t * \ + C##_##X##_split_(C##_##X##_node_t *tn) { \ + if (tn->link[1]->link[1]->level == tn->level && tn->level) { \ + C##_##X##_node_t *tmp = tn->link[1]; \ + tn->link[1] = tmp->link[0]; \ + tmp->link[0] = tn; \ + tn = tmp; \ + ++tn->level; \ + } \ + return tn; \ + } \ +\ +/*\ + static C##_##X##_node_t* ** recursive version ** \ + C##_##X##_insert_key_r_(C##_##X##_node_t* tn, const C##_##X##_rawkey_t* rkey, C##_##X##_result_t* res) { \ + if (tn->level == 0) { \ + tn = c_new_1(C##_##X##_node_t); \ + res->first = &tn->value, res->second = true; \ + tn->link[0] = tn->link[1] = (C##_##X##_node_t*) &cbst_nil, tn->level = 1; \ + *KEY_REF_##C(&tn->value) = keyFromRaw(*rkey); \ + return tn; \ + } \ + C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(&tn->value)); \ + int c = keyCompareRaw(&r, rkey); \ + if (c == 0) { res->first = &tn->value; return tn; } \ + tn->link[c == -1] = C##_##X##_insert_key_r_(tn->link[c == -1], rkey, res); \ + tn = C##_##X##_skew_(tn); \ + tn = C##_##X##_split_(tn); \ + return tn; \ + } \ +\ + static C##_##X##_size_t ** recursive version, array based ** \ + C##_##X##_insert_key_r_(C##_##X* self, C##_##X##_size_t tn, const C##_##X##_rawkey_t* rkey, C##_##X##_result_t* res) { \ + if (tn == 0) { \ + tn = C##_##X##_node_new_(self); \ + *KEY_REF_##C(&self->data[tn].value) = keyFromRaw(*rkey); \ + res->first = &self->data[tn].value, res->second = true; \ + return tn; \ + } \ + C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(&self->data[tn].value)); \ + int c = keyCompareRaw(&r, rkey), dir; \ + if (c == 0) { res->first = &self->data[tn].value; return tn; } \ + dir = (c == -1); \ + C##_##X##_size_t node = C##_##X##_insert_key_r_(self, self->data[tn].link[dir], rkey, res); \ + C##_##X##_node_t *d = self->data; \ + d[tn].link[dir] = node; \ + tn = C##_##X##_skew_(d, tn); \ + tn = C##_##X##_split_(d, tn); \ + return tn; \ + } \ +*/\ + static inline C##_##X##_node_t* \ + C##_##X##_insert_key_i_(C##_##X##_node_t* tn, const C##_##X##_rawkey_t* rkey, C##_##X##_result_t* res) { \ + C##_##X##_node_t *up[64], *it = tn; \ + int c, top = 0, dir = 0; \ + while (it->level) { \ + up[top++] = it; \ + C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(&it->value)); \ + if ((c = keyCompareRaw(&r, rkey)) == 0) {res->first = &it->value; return tn;} \ + it = it->link[(dir = (c == -1))]; \ + } \ + tn = c_new_1(C##_##X##_node_t); \ + *KEY_REF_##C(&tn->value) = keyFromRaw(*rkey); \ + res->first = &tn->value, res->second = true; \ + tn->link[0] = tn->link[1] = (C##_##X##_node_t*) &cbst_nil, tn->level = 1; \ + if (top == 0) return tn; \ + up[top - 1]->link[dir] = tn; \ + while (top--) { \ + if (top) dir = (up[top - 1]->link[1] == up[top]); \ + up[top] = C##_##X##_skew_(up[top]); \ + up[top] = C##_##X##_split_(up[top]); \ + if (top) up[top - 1]->link[dir] = up[top]; \ + } \ + return up[0]; \ + } \ +\ + STC_DEF C##_##X##_result_t \ + C##_##X##_insert_key(C##_##X* self, RawKey rkey) { \ + C##_##X##_result_t res = {NULL, false}; \ + self->root = C##_##X##_insert_key_i_(self->root, &rkey, &res); \ + self->size += res.second; \ + return res; \ + } \ +\ + STC_DEF C##_##X##_node_t* \ + C##_##X##_erase_r_(C##_##X##_node_t *tn, const C##_##X##_rawkey_t* rkey, int *erased) { \ + if (tn->level == 0) \ + return tn; \ + C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(&tn->value)); \ + int c = keyCompareRaw(&r, rkey); \ + if (c != 0) \ + tn->link[c == -1] = C##_##X##_erase_r_(tn->link[c == -1], rkey, erased); \ + else { \ + if (tn->link[0]->level && tn->link[1]->level) { \ + C##_##X##_node_t *h = tn->link[0]; \ + while (h->link[1]->level) \ + h = h->link[1]; \ + tn->value = h->value; \ + r = keyToRaw(KEY_REF_##C(&tn->value)); \ + tn->link[0] = C##_##X##_erase_r_(tn->link[0], &r, erased); \ + } else { \ + C##_##X##_node_t *tmp = tn; \ + tn = tn->link[tn->link[0]->level == 0]; \ + C##_##X##_value_del(&tmp->value); \ + free(tmp); \ + *erased = 1; \ + } \ + } \ + 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 = C##_##X##_skew_(tn); \ + tn = C##_##X##_split_(tn); \ + } \ + return tn; \ + } \ +\ + STC_DEF C##_##X##_node_t* \ + C##_##X##_clone_r_(C##_##X##_node_t *tn) { \ + if (! tn->level) return tn; \ + C##_##X##_node_t *cn = c_new_1(C##_##X##_node_t); \ + cn->link[0] = C##_##X##_clone_r_(tn->link[0]); \ + cn->link[1] = C##_##X##_clone_r_(tn->link[1]); \ + cn->level = tn->level; \ + cn->value = C##_##X##_value_clone(tn->value); \ + return cn; \ + } \ +\ + STC_DEF void \ + C##_##X##_del_r_(C##_##X##_node_t* tn) { \ + if (tn->level != 0) { \ + C##_##X##_del_r_(tn->link[0]); \ + C##_##X##_del_r_(tn->link[1]); \ + C##_##X##_value_del(&tn->value); \ + c_free(tn); \ + } \ + } + + +_using_CBST_types(_, csmap, int, int); +static csmap___node_t cbst_nil = {&cbst_nil, &cbst_nil, 0}; + +#else +#define _implement_CBST(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \ + keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) +#endif + +#endif diff --git a/stc/crandom.h b/stc/crandom.h index b43fdd46..689bf620 100644 --- a/stc/crandom.h +++ b/stc/crandom.h @@ -84,14 +84,14 @@ STC_INLINE double stc64_uniformf(stc64_t* rng, stc64_uniformf_t* dist) { } #if defined(__SIZEOF_INT128__) - #define cumul128(a, b, lo, hi) \ + #define cmul128(a, b, lo, hi) \ do { __uint128_t _z = (__uint128_t)(a) * (b); \ *(lo) = (uint64_t)_z, *(hi) = _z >> 64; } while(0) #elif defined(_MSC_VER) && defined(_WIN64) #include - #define cumul128(a, b, lo, hi) (*(lo) = _umul128(a, b, hi), (void)0) + #define cmul128(a, b, lo, hi) (*(lo) = _umul128(a, b, hi), (void)0) #elif defined(__x86_64__) - #define cumul128(a, b, lo, hi) \ + #define cmul128(a, b, lo, hi) \ asm("mulq %[rhs]" : "=a" (*(lo)), "=d" (*(hi)) \ : [lhs] "0" (a), [rhs] "rm" (b)) #endif @@ -99,8 +99,8 @@ STC_INLINE double stc64_uniformf(stc64_t* rng, stc64_uniformf_t* dist) { /* Unbiased bounded uniform distribution. */ STC_INLINE int64_t stc64_uniform(stc64_t* rng, stc64_uniform_t* d) { uint64_t lo, hi; -#ifdef cumul128 - do { cumul128(stc64_rand(rng), d->range, &lo, &hi); } while (lo < d->threshold); +#ifdef cmul128 + do { cmul128(stc64_rand(rng), d->range, &lo, &hi); } while (lo < d->threshold); #else hi = stc64_rand(rng) % d->range; #endif @@ -118,10 +118,11 @@ STC_API double stc64_normalf(stc64_t* rng, stc64_normalf_t* dist); /* PRNG crandom: by Tyge Løvset, NORCE Research, 2020. * Extremely fast PRNG suited for parallel usage with Weyl-sequence parameter. - * Faster than sfc64, wyhash64, and xoshiro256** on most platforms. - * 256bit state, updates only 192bit per rng. - * 2^63 unique threads with a minimum 2^64 period lengths each. - * 2^127 minimum period length for single thread (double loop). + * 256bit state, updates 192bit per rng. + * Faster than pcg, sfc64, xoshiro256** on most platforms. + * wyrand64 is slightly faster, but has only 64-bit state, + * unfit when longer periods or multiple threads are required. + * stc64 supports 2^63 unique threads with a minimum 2^64 period lengths each. * Passes PractRand tested up to 8TB output, Vigna's Hamming weight test, * and simple correlation tests, i.e. interleaved streams with one-bit diff state. */ @@ -131,7 +132,7 @@ STC_DEF stc64_t stc64_init(uint64_t seed) { } STC_DEF stc64_t stc64_with_seq(uint64_t seed, uint64_t seq) { stc64_t rng = {{seed, seed, seed, (seq << 1u) | 1u}}; - for (int i = 0; i < 8; ++i) stc64_rand(&rng); + for (int i = 0; i < 12; ++i) stc64_rand(&rng); return rng; } diff --git a/stc/csmap.h b/stc/csmap.h index 2e45f1a4..120b79f2 100644 --- a/stc/csmap.h +++ b/stc/csmap.h @@ -123,10 +123,14 @@ int main(void) { #define MAP_ONLY_csmap(...) __VA_ARGS__ #define KEY_REF_csset(vp) (vp) #define KEY_REF_csmap(vp) (&(vp)->first) +#ifndef CSMAP_SIZE_T +#define CSMAP_SIZE_T uint32_t +#endif #define _using_CBST_types(X, C, Key, Mapped) \ typedef Key C##_##X##_key_t; \ typedef Mapped C##_##X##_mapped_t; \ + typedef CSMAP_SIZE_T C##_##X##_size_t; \ \ typedef SET_ONLY_##C( C##_##X##_key_t ) \ MAP_ONLY_##C( struct {C##_##X##_key_t first; \ @@ -134,25 +138,24 @@ int main(void) { C##_##X##_value_t; \ \ typedef struct C##_##X##_node { \ - struct C##_##X##_node *link[2]; \ - uint8_t level; \ + C##_##X##_size_t link[2]; \ + int8_t level; \ C##_##X##_value_t value; \ } C##_##X##_node_t; \ \ typedef struct { \ C##_##X##_value_t *ref; \ + C##_##X##_node_t *_d; \ int _top; \ - C##_##X##_node_t *_tn, *_st[34]; \ + C##_##X##_size_t _tn, _st[64]; \ } C##_##X##_iter_t - #define _using_CBST(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \ - keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ + keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ _using_CBST_types(X, C, Key, Mapped); \ \ typedef struct { \ - C##_##X##_node_t* root; \ - size_t size; \ + C##_##X##_node_t* data; \ } C##_##X; \ \ typedef RawKey C##_##X##_rawkey_t; \ @@ -167,18 +170,23 @@ int main(void) { bool second; \ } C##_##X##_result_t; \ \ - STC_API C##_##X \ - C##_##X##_init(void); \ + STC_API C##_##X C##_##X##_init(void); \ + STC_API C##_##X C##_##X##_clone(C##_##X bst); \ +\ + STC_API void \ + C##_##X##_reserve(C##_##X* self, size_t cap); \ + STC_INLINE C##_##X \ + C##_##X##_with_capacity(size_t size) { \ + C##_##X x = C##_##X##_init(); \ + C##_##X##_reserve(&x, size); \ + return x; \ + } \ STC_INLINE bool \ - C##_##X##_empty(C##_##X m) {return m.size == 0;} \ + C##_##X##_empty(C##_##X m) {return _smap_size(&m) == 0;} \ STC_INLINE size_t \ - C##_##X##_size(C##_##X m) {return m.size;} \ -\ + C##_##X##_size(C##_##X m) {return _smap_size(&m);} \ STC_API void \ - C##_##X##_del_r_(C##_##X##_node_t* tn); \ -\ - STC_INLINE void \ - C##_##X##_del(C##_##X* self) {C##_##X##_del_r_(self->root);} \ + C##_##X##_del(C##_##X* self); \ STC_INLINE void \ C##_##X##_clear(C##_##X* self) {C##_##X##_del(self); *self = C##_##X##_init();} \ STC_INLINE void \ @@ -195,13 +203,6 @@ int main(void) { MAP_ONLY_##C( val.second = mappedFromRaw(mappedToRaw(&val.second)); ) \ return val; \ } \ -\ - STC_API C##_##X##_node_t* C##_##X##_clone_r_(C##_##X##_node_t *tn); \ - STC_INLINE C##_##X \ - C##_##X##_clone(C##_##X bst) { \ - C##_##X clone = {C##_##X##_clone_r_(bst.root), bst.size}; \ - return clone; \ - } \ \ STC_API C##_##X##_value_t* \ C##_##X##_find_it(const C##_##X* self, RawKey rkey, C##_##X##_iter_t* out); \ @@ -258,26 +259,15 @@ int main(void) { return &C##_##X##_find_it(self, rkey, &it)->second; \ }) \ \ - 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_API void \ - C##_##X##_next(C##_##X##_iter_t* it); \ + STC_API C##_##X##_value_t* C##_##X##_front(C##_##X* self); \ + STC_API C##_##X##_value_t* C##_##X##_back(C##_##X* self); \ + STC_API void C##_##X##_next(C##_##X##_iter_t* it); \ \ STC_INLINE C##_##X##_iter_t \ C##_##X##_begin(C##_##X* self) { \ - C##_##X##_iter_t it = {NULL, 0, self->root}; \ - C##_##X##_next(&it); return it; \ + C##_##X##_iter_t it = {NULL, self->data, 0, (C##_##X##_size_t) _smap_root(self)}; \ + if (it._tn) C##_##X##_next(&it); \ + return it; \ } \ STC_INLINE C##_##X##_iter_t \ C##_##X##_end(C##_##X* self) {\ @@ -286,17 +276,10 @@ int main(void) { STC_INLINE C##_##X##_mapped_t* \ C##_##X##_itval(C##_##X##_iter_t it) {return SET_ONLY_##C( it.ref ) \ MAP_ONLY_##C( &it.ref->second );} \ + STC_API int \ + C##_##X##_erase(C##_##X* self, RawKey rkey); \ \ - STC_API C##_##X##_node_t* \ - C##_##X##_erase_r_(C##_##X##_node_t *tn, const C##_##X##_rawkey_t* rkey, int *erased); \ -\ - STC_INLINE size_t \ - C##_##X##_erase(C##_##X* self, RawKey rkey) { \ - int erased = 0; \ - self->root = C##_##X##_erase_r_(self->root, &rkey, &erased); \ - self->size -= erased; return erased; \ - } \ - STC_INLINE size_t \ + STC_INLINE int \ C##_##X##_erase_at(C##_##X* self, C##_##X##_iter_t pos) { \ return C##_##X##_erase(self, keyToRaw(KEY_REF_##C(pos.ref))); \ } \ @@ -312,20 +295,70 @@ int main(void) { keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ STC_DEF C##_##X \ C##_##X##_init(void) { \ - C##_##X m = {(C##_##X##_node_t *) &cbst_nil, 0}; \ + C##_##X m = {(C##_##X##_node_t *) (_smap_inits + 4)}; \ return m; \ } \ +\ + STC_DEF C##_##X##_value_t* \ + C##_##X##_front(C##_##X* self) { \ + C##_##X##_node_t *d = self->data; \ + C##_##X##_size_t tn = (C##_##X##_size_t) _smap_root(self); \ + while (d[tn].link[0]) tn = d[tn].link[0]; \ + return &d[tn].value; \ + } \ + STC_DEF C##_##X##_value_t* \ + C##_##X##_back(C##_##X* self) { \ + C##_##X##_node_t *d = self->data; \ + C##_##X##_size_t tn = (C##_##X##_size_t) _smap_root(self); \ + while (d[tn].link[1]) tn = d[tn].link[1]; \ + return &d[tn].value; \ + } \ +\ + STC_DEF void \ + C##_##X##_reserve(C##_##X* self, size_t cap) { \ + C##_##X##_size_t oldcap = _smap_cap(self); \ + if (cap > oldcap) { \ + size_t* rep = (size_t *) c_realloc(oldcap ? _smap_rep(self) : NULL, \ + 4*sizeof(size_t) + (cap + 1)*sizeof(C##_##X##_node_t)); \ + if (oldcap == 0) \ + memset(rep, 0, sizeof(size_t)*4 + sizeof(C##_##X##_node_t)); \ + rep[_smap_CAP] = cap; \ + self->data = (C##_##X##_node_t *) (rep + 4); \ + } \ + } \ +\ + STC_DEF C##_##X##_size_t \ + C##_##X##_node_new_(C##_##X* self) { \ + size_t tn, *rep = _smap_rep(self); \ + if (rep[_smap_DISP]) { \ + tn = rep[_smap_DISP]; \ + rep[_smap_DISP] = self->data[tn].link[1]; \ + } else if ((tn = rep[_smap_SIZE] + 1) > rep[_smap_CAP]) \ + C##_##X##_reserve(self, 4 + tn*3/2); \ + C##_##X##_node_t* dn = &self->data[tn]; \ + dn->link[0] = dn->link[1] = 0; dn->level = 1; \ + return (C##_##X##_size_t) tn; \ + } \ +\ + STC_DEF void \ + C##_##X##_node_del_(C##_##X##_node_t *d, C##_##X##_size_t tn) { \ + size_t *rep = ((size_t *) d) - 4; \ + keyDel(KEY_REF_##C(&d[tn].value)); \ + d[tn].link[1] = (C##_##X##_size_t) rep[_smap_DISP]; d[tn].level = 0; \ + rep[_smap_DISP] = tn; \ + } \ \ STC_DEF C##_##X##_value_t* \ C##_##X##_find_it(const C##_##X* self, C##_##X##_rawkey_t rkey, C##_##X##_iter_t* out) { \ - C##_##X##_node_t *tn = self->root; \ + C##_##X##_size_t tn = _smap_root(self); \ + C##_##X##_node_t *d = out->_d = self->data; \ out->_top = 0; \ - while (tn->level) { \ - C##_##X##_rawkey_t rx = keyToRaw(KEY_REF_##C(&tn->value)); \ + if (tn) while (d[tn].level) { \ + C##_##X##_rawkey_t rx = keyToRaw(KEY_REF_##C(&d[tn].value)); \ switch (keyCompareRaw(&rx, &rkey)) { \ - case -1: tn = tn->link[1]; break; \ - case 1: out->_st[out->_top++] = tn; tn = tn->link[0]; break; \ - case 0: out->ref = &tn->value; out->_tn = tn->link[1]; return out->ref; \ + case -1: tn = d[tn].link[1]; break; \ + case 1: out->_st[out->_top++] = tn; tn = d[tn].link[0]; break; \ + case 0: out->_tn = d[tn].link[1]; return (out->ref = &d[tn].value); \ } \ } \ return (out->ref = NULL); \ @@ -333,129 +366,166 @@ int main(void) { \ STC_DEF void \ C##_##X##_next(C##_##X##_iter_t *it) { \ - C##_##X##_node_t *tn = it->_tn; \ - if (it->_top || tn->level) { \ - while (tn->level) { \ + C##_##X##_size_t tn = it->_tn; \ + if (it->_top || it->_d[tn].level) { \ + while (it->_d[tn].level) { \ it->_st[it->_top++] = tn; \ - tn = tn->link[0]; \ + tn = it->_d[tn].link[0]; \ } \ tn = it->_st[--it->_top]; \ - it->_tn = tn->link[1]; \ - it->ref = &tn->value; \ + it->_tn = it->_d[tn].link[1]; \ + it->ref = &it->_d[tn].value; \ } else \ it->ref = NULL; \ } \ \ - static C##_##X##_node_t * \ - C##_##X##_skew_(C##_##X##_node_t *tn) { \ - if (tn->link[0]->level == tn->level && tn->level) { \ - C##_##X##_node_t *tmp = tn->link[0]; \ - tn->link[0] = tmp->link[1]; \ - tmp->link[1] = tn; \ + static C##_##X##_size_t \ + C##_##X##_skew_(C##_##X##_node_t *d, C##_##X##_size_t tn) { \ + if (d[d[tn].link[0]].level == d[tn].level) { \ + C##_##X##_size_t tmp = d[tn].link[0]; \ + d[tn].link[0] = d[tmp].link[1]; \ + d[tmp].link[1] = tn; \ tn = tmp; \ } \ return tn; \ } \ \ - static C##_##X##_node_t * \ - C##_##X##_split_(C##_##X##_node_t *tn) { \ - if (tn->link[1]->link[1]->level == tn->level && tn->level) { \ - C##_##X##_node_t *tmp = tn->link[1]; \ - tn->link[1] = tmp->link[0]; \ - tmp->link[0] = tn; \ + static C##_##X##_size_t \ + C##_##X##_split_(C##_##X##_node_t *d, C##_##X##_size_t tn) { \ + if (d[d[d[tn].link[1]].link[1]].level == d[tn].level) { \ + C##_##X##_size_t tmp = d[tn].link[1]; \ + d[tn].link[1] = d[tmp].link[0]; \ + d[tmp].link[0] = tn; \ tn = tmp; \ - ++tn->level; \ + ++d[tn].level; \ } \ return tn; \ } \ \ - STC_DEF C##_##X##_node_t* \ - C##_##X##_insert_key_r_(C##_##X##_node_t* tn, const C##_##X##_rawkey_t* rkey, C##_##X##_result_t* res) { \ - if (tn->level == 0) { \ - tn = c_new_1(C##_##X##_node_t); \ - res->first = &tn->value, res->second = true; \ - tn->link[0] = tn->link[1] = (C##_##X##_node_t*) &cbst_nil, tn->level = 1; \ - *KEY_REF_##C(&tn->value) = keyFromRaw(*rkey); \ - return tn; \ + static inline C##_##X##_size_t \ + C##_##X##_insert_key_i_(C##_##X* self, C##_##X##_size_t tn, const C##_##X##_rawkey_t* rkey, C##_##X##_result_t* res) { \ + C##_##X##_size_t up[64], it = tn; \ + C##_##X##_node_t* d = self->data; \ + int c, top = 0, dir = 0; \ + while (it) { \ + up[top++] = it; \ + C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(&d[it].value)); \ + if ((c = keyCompareRaw(&r, rkey)) == 0) {res->first = &d[it].value; return tn;} \ + dir = (c == -1); \ + it = d[it].link[dir]; \ } \ - C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(&tn->value)); \ - int c = keyCompareRaw(&r, rkey); \ - if (c == 0) { res->first = &tn->value; return tn; } \ - tn->link[c == -1] = C##_##X##_insert_key_r_(tn->link[c == -1], rkey, res); \ - tn = C##_##X##_skew_(tn); \ - tn = C##_##X##_split_(tn); \ - return tn; \ + it = C##_##X##_node_new_(self); d = self->data; \ + *KEY_REF_##C(&d[it].value) = keyFromRaw(*rkey); \ + res->first = &d[it].value, res->second = true; \ + if (top == 0) return it; \ + d[up[top - 1]].link[dir] = it; \ + while (top--) { \ + if (top) dir = (d[up[top - 1]].link[1] == up[top]); \ + up[top] = C##_##X##_skew_(d, up[top]); \ + up[top] = C##_##X##_split_(d, up[top]); \ + if (top) d[up[top - 1]].link[dir] = up[top]; \ + } \ + return up[0]; \ } \ \ STC_DEF C##_##X##_result_t \ C##_##X##_insert_key(C##_##X* self, RawKey rkey) { \ C##_##X##_result_t res = {NULL, false}; \ - self->root = C##_##X##_insert_key_r_(self->root, &rkey, &res); \ - self->size += res.second; \ + C##_##X##_size_t tn = C##_##X##_insert_key_i_(self, (C##_##X##_size_t) _smap_root(self), &rkey, &res); \ + _smap_root(self) = tn; \ + _smap_size(self) += res.second; \ return res; \ } \ \ - STC_DEF C##_##X##_node_t* \ - C##_##X##_erase_r_(C##_##X##_node_t *tn, const C##_##X##_rawkey_t* rkey, int *erased) { \ - if (tn->level == 0) \ - return tn; \ - C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(&tn->value)); \ + static C##_##X##_size_t \ + C##_##X##_erase_r_(C##_##X##_node_t *d, C##_##X##_size_t tn, const C##_##X##_rawkey_t* rkey, int *erased) { \ + if (tn == 0) return 0; \ + C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(&d[tn].value)); \ int c = keyCompareRaw(&r, rkey); \ if (c != 0) \ - tn->link[c == -1] = C##_##X##_erase_r_(tn->link[c == -1], rkey, erased); \ + d[tn].link[c == -1] = C##_##X##_erase_r_(d, d[tn].link[c == -1], rkey, erased); \ else { \ - if (tn->link[0]->level && tn->link[1]->level) { \ - C##_##X##_node_t *h = tn->link[0]; \ - while (h->link[1]->level) \ - h = h->link[1]; \ - tn->value = h->value; \ - r = keyToRaw(KEY_REF_##C(&tn->value)); \ - tn->link[0] = C##_##X##_erase_r_(tn->link[0], &r, erased); \ + if (d[d[tn].link[0]].level && d[d[tn].link[1]].level) { \ + C##_##X##_size_t h = d[tn].link[0]; \ + while (d[d[h].link[1]].level) \ + h = d[h].link[1]; \ + d[tn].value = d[h].value; \ + r = keyToRaw(KEY_REF_##C(&d[tn].value)); \ + d[tn].link[0] = C##_##X##_erase_r_(d, d[tn].link[0], &r, erased); \ } else { \ - C##_##X##_node_t *tmp = tn; \ - tn = tn->link[tn->link[0]->level == 0]; \ - C##_##X##_value_del(&tmp->value); \ - free(tmp); \ + C##_##X##_size_t tmp = tn; \ + tn = d[tn].link[ d[d[tn].link[0]].level == 0 ]; \ + C##_##X##_value_del(&d[tmp].value); \ + C##_##X##_node_del_(d, tmp); \ *erased = 1; \ } \ } \ - 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 = C##_##X##_skew_(tn); \ - tn = C##_##X##_split_(tn); \ + C##_##X##_size_t t1 = d[tn].link[1]; \ + if (d[d[tn].link[0]].level < d[tn].level - 1 || d[t1].level < d[tn].level - 1) { \ + if (d[t1].level > --d[tn].level) \ + d[t1].level = d[tn].level; \ + tn = C##_##X##_skew_(d, tn); \ + tn = C##_##X##_split_(d, tn); \ } \ return tn; \ } \ \ - STC_DEF C##_##X##_node_t* \ - C##_##X##_clone_r_(C##_##X##_node_t *tn) { \ - if (! tn->level) return tn; \ - C##_##X##_node_t *cn = c_new_1(C##_##X##_node_t); \ - cn->link[0] = C##_##X##_clone_r_(tn->link[0]); \ - cn->link[1] = C##_##X##_clone_r_(tn->link[1]); \ - cn->level = tn->level; \ - cn->value = C##_##X##_value_clone(tn->value); \ + STC_DEF int \ + C##_##X##_erase(C##_##X* self, RawKey rkey) { \ + int erased = 0; \ + C##_##X##_size_t root = C##_##X##_erase_r_(self->data, (C##_##X##_size_t) _smap_root(self), &rkey, &erased); \ + if (erased) {_smap_root(self) = root; --_smap_size(self);} \ + return erased; \ + } \ +\ + static C##_##X##_size_t \ + C##_##X##_clone_r_(C##_##X* self, const C##_##X##_node_t* src, C##_##X##_size_t tn) { \ + if (tn == 0) return 0; \ + C##_##X##_size_t cn = C##_##X##_node_new_(self); \ + C##_##X##_node_t* d = self->data; \ + d[cn].link[0] = C##_##X##_clone_r_(self, src, src[tn].link[0]); \ + d[cn].link[1] = C##_##X##_clone_r_(self, src, src[tn].link[1]); \ + d[cn].level = src[tn].level; \ + d[cn].value = C##_##X##_value_clone(src[tn].value); \ return cn; \ } \ + STC_DEF C##_##X \ + C##_##X##_clone(C##_##X bst) { \ + C##_##X clone = C##_##X##_with_capacity(_smap_size(&bst)); \ + C##_##X##_size_t root = C##_##X##_clone_r_(&clone, bst.data, (C##_##X##_size_t) _smap_root(&bst)); \ + _smap_root(&clone) = root; \ + return clone; \ + } \ \ + static void \ + C##_##X##_del_r_(C##_##X##_node_t* d, C##_##X##_size_t tn) { \ + if (tn) { \ + C##_##X##_del_r_(d, d[tn].link[0]); \ + C##_##X##_del_r_(d, d[tn].link[1]); \ + C##_##X##_value_del(&d[tn].value); \ + } \ + } \ STC_DEF void \ - C##_##X##_del_r_(C##_##X##_node_t* tn) { \ - if (tn->level != 0) { \ - C##_##X##_del_r_(tn->link[0]); \ - C##_##X##_del_r_(tn->link[1]); \ - C##_##X##_value_del(&tn->value); \ - c_free(tn); \ + C##_##X##_del(C##_##X* self) { \ + if (_smap_root(self)) { \ + C##_##X##_del_r_(self->data, (C##_##X##_size_t) _smap_root(self)); \ + c_free(_smap_rep(self)); \ } \ } - _using_CBST_types(_, csmap, int, int); -static csmap___node_t cbst_nil = {&cbst_nil, &cbst_nil, 0}; +static size_t _smap_inits[4] = {0, 0, 0, 0}; #else #define _implement_CBST(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \ keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) #endif +enum {_smap_ROOT=0, _smap_DISP=1, _smap_SIZE=2, _smap_CAP=3}; +#define _smap_rep(self) (((size_t *)(self)->data) - 4) +#define _smap_root(self) _smap_rep(self)[_smap_ROOT] +#define _smap_disp(self) _smap_rep(self)[_smap_DISP] +#define _smap_size(self) _smap_rep(self)[_smap_SIZE] +#define _smap_cap(self) _smap_rep(self)[_smap_CAP] + #endif -- cgit v1.2.3