From 5b78847871217562dcddbb0bd34076a892eb49e1 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 6 Sep 2020 23:32:30 +0200 Subject: Renamed push_****(), _insert() to _emplace(). added insert_or_assign(), etc. --- README.md | 4 +- examples/advanced.c | 2 +- examples/benchmark.c | 19 +++---- examples/birthday.c | 4 +- examples/demos.c | 27 +++++----- examples/ex_gaussian.c | 2 +- examples/geek1.c | 4 +- examples/geek3.c | 8 +-- examples/geek4.c | 12 ++--- examples/geek7.c | 2 +- examples/inits.c | 8 +-- examples/mapmap.c | 14 +++--- examples/phonebook.c | 2 +- examples/stack.c | 3 +- examples/words.c | 4 +- stc/clist.h | 26 +++++----- stc/cmap.h | 131 +++++++++++++++++++++++++++---------------------- stc/cqueue.h | 9 ++-- stc/cstack.h | 9 ++-- stc/cvec.h | 16 +++--- 20 files changed, 156 insertions(+), 150 deletions(-) diff --git a/README.md b/README.md index b5f76405..93c320f6 100644 --- a/README.md +++ b/README.md @@ -224,8 +224,8 @@ declare_cmap(ii, int, int); int main() { cmap_ii nums = cmap_ini; - cmap_ii_put(&nums, 8, 64); // put() works as c++ std::unordered_map<>::insert_or_replace() - cmap_ii_insert(&nums, 11, 121); // only insert value if key does not exists - like std::unordered_map::insert(). + cmap_ii_put(&nums, 8, 64); // simular to insert_or_replace(), + cmap_ii_emplace(&nums, 11, 121); printf("%d\n", cmap_ii_find(nums, 8)->value); cmap_ii_destroy(&nums); diff --git a/examples/advanced.c b/examples/advanced.c index 90f800e0..29ba55aa 100644 --- a/examples/advanced.c +++ b/examples/advanced.c @@ -72,7 +72,7 @@ int main() VikingVw einar = {"Einar", "Norway"}; cmap_vk_entry_t *e = cmap_vk_find(&vikings, einar); e->value += 5; // update - cmap_vk_insert(&vikings, einar, 0)->value += 5; // again + cmap_vk_emplace(&vikings, einar, 0).item->value += 5; // again c_foreach (k, cmap_vk, vikings) { printf("%s of %s has %d hp\n", k.item->key.name.str, k.item->key.country.str, k.item->value); diff --git a/examples/benchmark.c b/examples/benchmark.c index 1c94397d..15d659ff 100644 --- a/examples/benchmark.c +++ b/examples/benchmark.c @@ -37,8 +37,7 @@ crand_rng64_t rng; #define CMAP_SETUP(tt, Key, Value) cmap_##tt map = cmap_ini \ ; cmap_##tt##_set_load_factors(&map, max_load_factor, 0.0) #define CMAP_PUT(tt, key, val) cmap_##tt##_put(&map, key, val)->value -#define CMAP_INSERT(tt, key, val) cmap_##tt##_insert(&map, key, val) -#define CMAP_EMPLACE(tt, key, val) cmap_try_emplace(tt, &map, key, val) +#define CMAP_EMPLACE(tt, key, val) cmap_##tt##_emplace(&map, key, val) #define CMAP_ERASE(tt, key) cmap_##tt##_erase(&map, key) #define CMAP_FIND(tt, key) (cmap_##tt##_find(map, key) != NULL) #define CMAP_FOR(tt, i) c_foreach (i, cmap_##tt, map) @@ -50,7 +49,7 @@ crand_rng64_t rng; #define KMAP_SETUP(tt, Key, Value) khash_t(ii)* map = kh_init(ii); khiter_t ki; int ret #define KMAP_PUT(tt, key, val) (*(ki = kh_put(ii, map, key, &ret), map->vals[ki] = val, &map->vals[ki])) -#define KMAP_INSERT(tt, key, val) (ki = kh_put(ii, map, key, &ret), ret ? (map->vals[ki] = val) : val) +#define KMAP_EMPLACE(tt, key, val) (ki = kh_put(ii, map, key, &ret), ret ? (map->vals[ki] = val) : val) #define KMAP_ERASE(tt, key) ((ki = kh_get(ii, map, key)) != kh_end(map) ? kh_del(ii, map, ki), 1 : 0) #define KMAP_FIND(tt, key) (kh_get(ii, map, key) != kh_end(map)) #define KMAP_SIZE(tt) kh_size(map) @@ -60,7 +59,6 @@ crand_rng64_t rng; #define UMAP_SETUP(tt, Key, Value) std::unordered_map map; map.max_load_factor(max_load_factor) #define UMAP_PUT(tt, key, val) (map[key] = val) -#define UMAP_INSERT(tt, key, val) map.insert(std::make_pair(key, val)) #define UMAP_EMPLACE(tt, key, val) map.emplace(key, val) #define UMAP_FIND(tt, key) (map.find(key) != map.end()) #define UMAP_ERASE(tt, key) map.erase(key) @@ -73,7 +71,6 @@ crand_rng64_t rng; #define BMAP_SETUP(tt, Key, Value) ska::bytell_hash_map map; map.max_load_factor(max_load_factor) #define BMAP_PUT(tt, key, val) UMAP_PUT(tt, key, val) -#define BMAP_INSERT(tt, key, val) UMAP_INSERT(tt, key, val) #define BMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val) #define BMAP_FIND(tt, key) UMAP_FIND(tt, key) #define BMAP_ERASE(tt, key) UMAP_ERASE(tt, key) @@ -86,7 +83,6 @@ crand_rng64_t rng; #define FMAP_SETUP(tt, Key, Value) ska::flat_hash_map map; map.max_load_factor(max_load_factor) #define FMAP_PUT(tt, key, val) UMAP_PUT(tt, key, val) -#define FMAP_INSERT(tt, key, val) UMAP_INSERT(tt, key, val) #define FMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val) #define FMAP_FIND(tt, key) UMAP_FIND(tt, key) #define FMAP_ERASE(tt, key) UMAP_ERASE(tt, key) @@ -99,7 +95,6 @@ crand_rng64_t rng; #define HMAP_SETUP(tt, Key, Value) tsl::hopscotch_map map; map.max_load_factor(max_load_factor) #define HMAP_PUT(tt, key, val) UMAP_PUT(tt, key, val) -#define HMAP_INSERT(tt, key, val) UMAP_INSERT(tt, key, val) #define HMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val) #define HMAP_FIND(tt, key) UMAP_FIND(tt, key) #define HMAP_ERASE(tt, key) UMAP_ERASE(tt, key) @@ -112,7 +107,6 @@ crand_rng64_t rng; #define RMAP_SETUP(tt, Key, Value) robin_hood::unordered_map map #define RMAP_PUT(tt, key, val) UMAP_PUT(tt, key, val) -#define RMAP_INSERT(tt, key, val) UMAP_INSERT(tt, key, val) #define RMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val) #define RMAP_FIND(tt, key) UMAP_FIND(tt, key) #define RMAP_ERASE(tt, key) UMAP_ERASE(tt, key) @@ -125,7 +119,6 @@ crand_rng64_t rng; #define SMAP_SETUP(tt, Key, Value) spp::sparse_hash_map map; map.max_load_factor(max_load_factor) #define SMAP_PUT(tt, key, val) UMAP_PUT(tt, key, val) -#define SMAP_INSERT(tt, key, val) UMAP_INSERT(tt, key, val) #define SMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val) #define SMAP_FIND(tt, key) UMAP_FIND(tt, key) #define SMAP_ERASE(tt, key) UMAP_ERASE(tt, key) @@ -225,14 +218,14 @@ int main(int argc, char* argv[]) seed = time(NULL); printf("\nRandom keys are in range [0, 2^%d), seed = %zu:\n", rr, seed); printf("\nUnordered maps: %d repeats of Insert random key + try to remove a random key:\n", N1); - RUN_TEST(1) + //RUN_TEST(1) printf("\nUnordered maps: Insert %d index keys, then remove them in same order:\n", N2); - RUN_TEST(2) + //RUN_TEST(2) printf("\nUnordered maps: Insert %d random keys, then remove them in same order:\n", N3); - RUN_TEST(3) + //RUN_TEST(3) - printf("\nUnordered maps: Iterate %d random keys, then remove them in same order:\n", N4); + printf("\nUnordered maps: Iterate %d random keys:\n", N4); RUN_TEST(4) } diff --git a/examples/birthday.c b/examples/birthday.c index be2114da..bf807e67 100644 --- a/examples/birthday.c +++ b/examples/birthday.c @@ -21,7 +21,7 @@ void repeats(void) clock_t now = clock(); for (size_t i = 0; i < N; ++i) { uint64_t k = crand_i64(&rng) & mask; - int v = ++cmap_ic_insert(&m, k, 0)->value; + int v = ++cmap_ic_emplace(&m, k, 0).item->value; if (v > 1) printf("%zu: %llx - %d\n", i, k, v); } float diff = (float) (clock() - now) / CLOCKS_PER_SEC; @@ -40,7 +40,7 @@ void distribution(void) clock_t now = clock(); crand_uniform_i32_t dist = crand_uniform_i32_init(rng, 0, M); for (size_t i = 0; i < N; ++i) { - ++cmap_x_insert(&map, crand_uniform_i32(&dist), 0)->value; + ++cmap_x_emplace(&map, crand_uniform_i32(&dist), 0).item->value; } float diff = (float) (clock() - now) / CLOCKS_PER_SEC; diff --git a/examples/demos.c b/examples/demos.c index 474e539e..c0c5de18 100644 --- a/examples/demos.c +++ b/examples/demos.c @@ -61,9 +61,9 @@ void vectordemo2() { printf("\nVECTORDEMO2\n"); cvec_str names = cvec_ini; - cvec_str_push_back(&names, "Mary"); - cvec_str_push_back(&names, "Joe"); - cvec_str_push_back(&names, "Chris"); + cvec_str_emplace_back(&names, "Mary"); + cvec_str_emplace_back(&names, "Joe"); + cvec_str_emplace_back(&names, "Chris"); cstr_assign(&names.data[1], "Jane"); // replace Joe printf("names[1]: %s\n", names.data[1].str); @@ -151,26 +151,25 @@ void mapdemo2() } -declare_cmap_strkey(ss, cstr_t, cstr_destroy); +declare_cmap_str(); void mapdemo3() { printf("\nMAPDEMO3\n"); - cmap_ss table = cmap_ini; - cmap_ss_put(&table, "Map", cstr_make("test")); - cmap_ss_put(&table, "Make", cstr_make("my")); - cmap_ss_put(&table, "Sunny", cstr_make("day")); - cmap_ss_entry_t *e = cmap_ss_find(&table, "Make"); - c_foreach (i, cmap_ss, table) + cmap_str table = cmap_ini; + cmap_str_put(&table, "Map", "test"); + cmap_str_put(&table, "Make", "my"); + cmap_str_put(&table, "Sunny", "day"); + cmap_str_entry_t *e = cmap_str_find(&table, "Make"); + c_foreach (i, cmap_str, table) printf("entry: %s: %s\n", i.item->key.str, i.item->value.str); printf("size %zu: remove: Make: %s\n", cmap_size(table), e->value.str); - cmap_ss_erase(&table, "Make"); - //cmap_ss_eraseEntry(&table, e); + cmap_str_erase(&table, "Make"); printf("size %zu\n", cmap_size(table)); - c_foreach (i, cmap_ss, table) + c_foreach (i, cmap_str, table) printf("entry: %s: %s\n", i.item->key.str, i.item->value.str); - cmap_ss_destroy(&table); // frees key and value CStrs, and hash table (CVec). + cmap_str_destroy(&table); // frees key and value CStrs, and hash table (CVec). } diff --git a/examples/ex_gaussian.c b/examples/ex_gaussian.c index a4682a2b..d2da77d9 100644 --- a/examples/ex_gaussian.c +++ b/examples/ex_gaussian.c @@ -32,7 +32,7 @@ int main() cmap_i mhist = cmap_ini; for (size_t i = 0; i < N; ++i) { int index = round( crand_normal_f64(&dist) ); - cmap_i_insert(&mhist, index, 0)->value += 1; + cmap_i_emplace(&mhist, index, 0).item->value += 1; } // Transfer map to vec and sort it by map keys. diff --git a/examples/geek1.c b/examples/geek1.c index 8759e143..194b92da 100644 --- a/examples/geek1.c +++ b/examples/geek1.c @@ -21,7 +21,7 @@ int findMaximumPairs(int a[], int n, int k) // Hash-table cmap_ii hash = cmap_ini; for (int i = 0; i < n; i++) { - cmap_ii_insert(&hash, a[i] % k, 0)->value++; + cmap_ii_emplace(&hash, a[i] % k, 0).item->value++; } int count = 0; @@ -39,7 +39,7 @@ int findMaximumPairs(int a[], int n, int k) int second = k - it.item->key; cmap_ii_entry_t *hf = cmap_ii_find(&hash, first), - *hs = cmap_ii_insert(&hash, second, 0); + *hs = cmap_ii_emplace(&hash, second, 0).item; // Check for minimal occurrence if (hf->value < hs->value) { // Take the minimal diff --git a/examples/geek3.c b/examples/geek3.c index 044d7b16..be3c8c10 100644 --- a/examples/geek3.c +++ b/examples/geek3.c @@ -15,10 +15,10 @@ int main () // ... cmap_si_put(&mymap, "Mars", 3396); - cmap_si_insert(&mymap, "Saturn", 0)->value += 272; - cmap_si_put(&mymap, "Jupiter", cmap_si_insert(&mymap, "Saturn", 0)->value + 9638); - cmap_si_insert(&mymap, "Sun", 0)->value += 1000; - cmap_si_insert(&mymap, "Sun", 0)->value += 1000; + cmap_si_emplace(&mymap, "Saturn", 0).item->value += 272; + cmap_si_put(&mymap, "Jupiter", cmap_si_emplace(&mymap, "Saturn", 0).item->value + 9638); + cmap_si_emplace(&mymap, "Sun", 0).item->value += 1000; + cmap_si_emplace(&mymap, "Sun", 0).item->value += 1000; c_foreach (x, cmap_si, mymap) { printf("%s: %d\n", x.item->key.str, x.item->value); diff --git a/examples/geek4.c b/examples/geek4.c index 06c93de4..9f4df539 100644 --- a/examples/geek4.c +++ b/examples/geek4.c @@ -106,13 +106,13 @@ int commonWords(cvec_str S) // make it false for (int k = 0; k < cvec_size(ans); k++) { if (ans.data[k].value != false - && cmap_sb_insert(&has, ans.data[k].key.str, false)->value == false) { + && cmap_sb_emplace(&has, ans.data[k].key.str, false).item->value == false) { ans.data[k].value = false; } // This line is used to consider only distinct words else if (ans.data[k].value != false - && cmap_sb_insert(&has, ans.data[k].key.str, false)->value == true) { + && cmap_sb_emplace(&has, ans.data[k].key.str, false).item->value == true) { cmap_sb_put(&has, ans.data[k].key.str, false); } } @@ -137,10 +137,10 @@ int commonWords(cvec_str S) int main() { cvec_str S = cvec_ini; - cvec_str_push_back(&S, "there is a cow"); - cvec_str_push_back(&S, "cow is our mother"); - cvec_str_push_back(&S, "cow gives us milk and milk is sweet"); - cvec_str_push_back(&S, "there is a boy who loves cow"); + cvec_str_emplace_back(&S, "there is a cow"); + cvec_str_emplace_back(&S, "cow is our mother"); + cvec_str_emplace_back(&S, "cow gives us milk and milk is sweet"); + cvec_str_emplace_back(&S, "there is a boy who loves cow"); printf("%d\n", commonWords(S)); cvec_str_destroy(&S); diff --git a/examples/geek7.c b/examples/geek7.c index 4be984ee..379dac9f 100644 --- a/examples/geek7.c +++ b/examples/geek7.c @@ -41,7 +41,7 @@ void findElementsAfterDel(int arr[], int m, int del[], for (int i = 0; i < n; ++i) { // Increment the count of del[i] - cmap_ii_insert(&mp, del[i], 0)->value++; + cmap_ii_emplace(&mp, del[i], 0).item->value++; } cpqueue_i heap = cpqueue_i_init(); diff --git a/examples/inits.c b/examples/inits.c index d7b7a37b..16882e7a 100644 --- a/examples/inits.c +++ b/examples/inits.c @@ -68,10 +68,10 @@ int main(void) { {"Spain", 10}, {"France", 10}, )); - cmap_cnt_insert(&countries, "Greenland", 0)->value += 20; - cmap_cnt_insert(&countries, "Sweden", 0)->value += 20; - cmap_cnt_insert(&countries, "Norway", 0)->value += 20; - cmap_cnt_insert(&countries, "Finland", 0)->value += 20; + cmap_cnt_emplace(&countries, "Greenland", 0).item->value += 20; + cmap_cnt_emplace(&countries, "Sweden", 0).item->value += 20; + cmap_cnt_emplace(&countries, "Norway", 0).item->value += 20; + cmap_cnt_emplace(&countries, "Finland", 0).item->value += 20; c_foreach (i, cmap_cnt, countries) printf("%s: %d\n", i.item->key.str, i.item->value); diff --git a/examples/mapmap.c b/examples/mapmap.c index a0c1b173..6929dc69 100644 --- a/examples/mapmap.c +++ b/examples/mapmap.c @@ -9,14 +9,14 @@ declare_cmap_strkey(cfg, cmap_str, cmap_str_destroy); int main(void) { cmap_cfg config = cmap_ini; cmap_str init = cmap_ini; - cmap_str_put(&cmap_cfg_insert(&config, "user", init)->value, "name", "Joe"); - cmap_str_put(&cmap_cfg_insert(&config, "user", init)->value, "groups", "proj1,proj3"); - cmap_str_put(&cmap_cfg_insert(&config, "group", init)->value, "proj1", "Energy"); - cmap_str_put(&cmap_cfg_insert(&config, "group", init)->value, "proj2", "Windy"); - cmap_str_put(&cmap_cfg_insert(&config, "group", init)->value, "proj3", "Oil"); - cmap_str_put(&cmap_cfg_insert(&config, "admin", init)->value, "employees", "2302"); + cmap_str_insert_or_assign(&cmap_cfg_emplace(&config, "user", init).item->value, "name", "Joe"); + cmap_str_insert_or_assign(&cmap_cfg_emplace(&config, "user", init).item->value, "groups", "proj1,proj3"); + cmap_str_insert_or_assign(&cmap_cfg_emplace(&config, "group", init).item->value, "proj1", "Energy"); + cmap_str_insert_or_assign(&cmap_cfg_emplace(&config, "group", init).item->value, "proj2", "Windy"); + cmap_str_insert_or_assign(&cmap_cfg_emplace(&config, "group", init).item->value, "proj3", "Oil"); + cmap_str_insert_or_assign(&cmap_cfg_emplace(&config, "admin", init).item->value, "employees", "2302"); - cmap_str_put(&cmap_cfg_insert(&config, "group", init)->value, "proj2", "Wind"); // Update + cmap_str_insert_or_assign(&cmap_cfg_emplace(&config, "group", init).item->value, "proj2", "Wind"); // Update c_foreach (i, cmap_cfg, config) c_foreach (j, cmap_str, i.item->value) diff --git a/examples/phonebook.c b/examples/phonebook.c index d2ed227f..50a16467 100644 --- a/examples/phonebook.c +++ b/examples/phonebook.c @@ -62,7 +62,7 @@ int main(int argc, char **argv) printf("\nPhone book after erasing Tariq and Elliott:\n"); print_phone_book(phone_book); - cmap_str_put(&phone_book, "Zak Byers", "(555) 396-188"); + cmap_str_insert_or_assign(&phone_book, "Zak Byers", "(555) 396-188"); printf("\nPhone book after update phone of Zak Byers:\n"); print_phone_book(phone_book); diff --git a/examples/stack.c b/examples/stack.c index de30c5b4..dedf1eb5 100644 --- a/examples/stack.c +++ b/examples/stack.c @@ -4,8 +4,9 @@ #include declare_cvec(i, int); +declare_cvec(c, char); declare_cstack(i, cvec_i); -declare_cstack(c, cstr); +declare_cstack(c, cvec_c); int main() { cstack_i stack = cstack_i_init(); diff --git a/examples/words.c b/examples/words.c index 275ffee7..92f98c85 100644 --- a/examples/words.c +++ b/examples/words.c @@ -16,7 +16,7 @@ int main1() "this", "sentence", "is", "not", "a", "sentence", "this", "sentence", "is", "a", "hoax" )); - clist_str_push_back_v(&lwords, cstr_from("%f", 123897.0 / 23.0)); + clist_str_push_back(&lwords, cstr_from("%f", 123897.0 / 23.0)); c_foreach (w, clist_str, lwords) printf("%s\n", w.item->value.str); puts(""); @@ -29,7 +29,7 @@ int main1() cmap_si word_map = cmap_ini; c_foreach (w, cvec_str, words) - ++cmap_si_insert(&word_map, w.item->str, 0)->value; + ++cmap_si_emplace(&word_map, w.item->str, 0).item->value; c_foreach (pair, cmap_si, word_map) { printf("%d occurrences of word '%s'\n", diff --git a/stc/clist.h b/stc/clist.h index 3e1a88b2..8a196b7b 100644 --- a/stc/clist.h +++ b/stc/clist.h @@ -113,16 +113,16 @@ STC_API size_t _clist_size(const clist_void* self); STC_API void \ clist_##X##_push_n(clist_##X *self, const clist_##X##_input_t in[], size_t size); \ STC_API void \ - clist_##X##_push_back_v(clist_##X* self, Value value); \ + clist_##X##_push_back(clist_##X* self, Value value); \ STC_INLINE void \ - clist_##X##_push_back(clist_##X* self, RawValue rawValue) { \ - clist_##X##_push_back_v(self, valueFromRaw(rawValue)); \ + clist_##X##_emplace_back(clist_##X* self, RawValue rawValue) { \ + clist_##X##_push_back(self, valueFromRaw(rawValue)); \ } \ STC_API void \ - clist_##X##_push_front_v(clist_##X* self, Value value); \ + clist_##X##_push_front(clist_##X* self, Value value); \ STC_INLINE void \ - clist_##X##_push_front(clist_##X* self, RawValue rawValue) { \ - clist_##X##_push_front_v(self, valueFromRaw(rawValue)); \ + clist_##X##_emplace_front(clist_##X* self, RawValue rawValue) { \ + clist_##X##_push_front(self, valueFromRaw(rawValue)); \ } \ STC_API void \ clist_##X##_pop_front(clist_##X* self); \ @@ -152,10 +152,10 @@ STC_API size_t _clist_size(const clist_void* self); clist_##X##_itval(clist_##X##_iter_t it) {return &it.item->value;} \ \ STC_API clist_##X##_iter_t \ - clist_##X##_insert_after_v(clist_##X* self, clist_##X##_iter_t pos, Value value); \ + clist_##X##_insert_after(clist_##X* self, clist_##X##_iter_t pos, Value value); \ STC_INLINE clist_##X##_iter_t \ - clist_##X##_insert_after(clist_##X* self, clist_##X##_iter_t pos, RawValue rawValue) { \ - return clist_##X##_insert_after_v(self, pos, valueFromRaw(rawValue)); \ + clist_##X##_emplace_after(clist_##X* self, clist_##X##_iter_t pos, RawValue rawValue) { \ + return clist_##X##_insert_after(self, pos, valueFromRaw(rawValue)); \ } \ STC_API clist_##X##_iter_t \ clist_##X##_erase_after(clist_##X* self, clist_##X##_iter_t pos); \ @@ -203,18 +203,18 @@ STC_API size_t _clist_size(const clist_void* self); } \ \ STC_API void \ - clist_##X##_push_back_v(clist_##X* self, Value value) { \ + clist_##X##_push_back(clist_##X* self, Value value) { \ _clist_insert_after(self, X, self->last, value); \ self->last = entry; \ } \ STC_API void \ - clist_##X##_push_front_v(clist_##X* self, Value value) { \ + clist_##X##_push_front(clist_##X* self, Value value) { \ _clist_insert_after(self, X, self->last, value); \ if (!self->last) self->last = entry; \ } \ STC_API void \ clist_##X##_push_n(clist_##X *self, const clist_##X##_input_t in[], size_t size) { \ - for (size_t i=0; ilast && pos.item == pos.end) self->last = entry; \ pos.item = entry; return pos; \ diff --git a/stc/cmap.h b/stc/cmap.h index 3378388a..8ee50ec3 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -61,8 +61,8 @@ int main(void) { #define cset_size(s) cmap_size(s) #define cset_bucket_count(s) cmap_bucket_count(s) #define cmap_try_emplace(X, self, k, v) do { \ - struct cmap_##X##_result __r = cmap_##X##_insert_key(self, k); \ - if (__r.inserted) __r.entry->value = v; \ + cmap_##X##_result_t __r = cmap_##X##_insert_key_(self, k); \ + if (__r.inserted) __r.item->value = v; \ } while (false) /* https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction */ @@ -70,6 +70,7 @@ int main(void) { #define chash_entry_index(h, entryPtr) ((entryPtr) - (h).table) enum {chash_HASH = 0x7f, chash_USED = 0x80}; +typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; #define declare_cmap(...) \ c_MACRO_OVERLOAD(declare_cmap, __VA_ARGS__) @@ -139,10 +140,12 @@ enum {chash_HASH = 0x7f, chash_USED = 0x80}; declare_CHASH(X, ctype, cstr_t, Value, valueDestroy, cstr_equals_raw, cstr_hash_raw, \ cstr_destroy, const char*, cstr_to_raw, cstr_make, Value, c_default_from_raw) +#define CSET_ONLY_cset(x) x +#define CSET_ONLY_cmap(x) #define CMAP_ONLY_cset(x) #define CMAP_ONLY_cmap(x) x -#define CMAP_BOTH_cset(x, y) x -#define CMAP_BOTH_cmap(x, y) x, y +#define CMAP_ARGS_cset(x, y) x +#define CMAP_ARGS_cmap(x, y) x, y /* CHASH full: use 'void' for Value if ctype is cset */ #define declare_CHASH(X, ctype, Key, Value, valueDestroy, keyEqualsRaw, keyHashRaw, \ @@ -162,6 +165,11 @@ typedef struct { \ CMAP_ONLY_##ctype(RawValue value;) \ } ctype##_##X##_input_t; \ \ +typedef struct { \ + ctype##_##X##_entry_t *item; \ + bool inserted; \ +} ctype##_##X##_result_t; \ + \ typedef Key ctype##_##X##_key_t; \ typedef Value ctype##_##X##_value_t; \ typedef RawKey ctype##_##X##_rawkey_t; \ @@ -204,38 +212,47 @@ STC_API void \ ctype##_##X##_clear(ctype##_##X* self); \ STC_API ctype##_##X##_entry_t* \ ctype##_##X##_find(const ctype##_##X* self, ctype##_##X##_rawkey_t rawKey); \ +STC_API bool \ +ctype##_##X##_contains(const ctype##_##X* self, ctype##_##X##_rawkey_t rawKey); \ \ -struct ctype##_##X##_result {ctype##_##X##_entry_t *entry; bool inserted;}; \ -STC_API struct ctype##_##X##_result \ -ctype##_##X##_insert_key(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey); \ +STC_API ctype##_##X##_result_t \ +ctype##_##X##_insert_key_(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey); \ \ -STC_INLINE ctype##_##X##_entry_t* /* like c++ std::map.insert(): */ \ -ctype##_##X##_insert(ctype##_##X* self, CMAP_BOTH_##ctype(ctype##_##X##_rawkey_t rawKey, RawValue rawValue)) { \ - struct ctype##_##X##_result res = ctype##_##X##_insert_key(self, rawKey); \ - CMAP_ONLY_##ctype( if (res.inserted) res.entry->value = valueFromRaw(rawValue); ) \ - return res.entry; \ +CSET_ONLY_##ctype( STC_INLINE ctype##_##X##_result_t \ +ctype##_##X##_insert(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey) { \ + return ctype##_##X##_insert_key_(self, rawKey); \ +}) \ +STC_INLINE ctype##_##X##_result_t \ +ctype##_##X##_emplace(ctype##_##X* self, CMAP_ARGS_##ctype(ctype##_##X##_rawkey_t rawKey, RawValue rawValue)) { \ + ctype##_##X##_result_t res = ctype##_##X##_insert_key_(self, rawKey); \ + CMAP_ONLY_##ctype( if (res.inserted) res.item->value = valueFromRaw(rawValue); ) \ + return res; \ } \ \ -STC_INLINE ctype##_##X##_entry_t* /* like c++ std::map.insert_or_assign(): */ \ -ctype##_##X##_put(ctype##_##X* self, CMAP_BOTH_##ctype(ctype##_##X##_rawkey_t rawKey, RawValue rawValue)) { \ - struct ctype##_##X##_result res = ctype##_##X##_insert_key(self, rawKey); \ - CMAP_ONLY_##ctype( if (!res.inserted) valueDestroy(&res.entry->value); \ - res.entry->value = valueFromRaw(rawValue); ) \ - return res.entry; \ -} \ CMAP_ONLY_##ctype( \ -STC_INLINE ctype##_##X##_entry_t* /* cmap_put_v(key, move(value)) */ \ -ctype##_##X##_put_v(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey, Value value) { \ - struct ctype##_##X##_result res = ctype##_##X##_insert_key(self, rawKey); \ - if (!res.inserted) valueDestroy(&res.entry->value); \ - res.entry->value = value; \ - return res.entry; \ +STC_INLINE ctype##_##X##_result_t \ +ctype##_##X##_insert_or_assign(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey, RawValue rawValue) { \ + ctype##_##X##_result_t res = ctype##_##X##_insert_key_(self, rawKey); \ + if (!res.inserted) valueDestroy(&res.item->value); \ + res.item->value = valueFromRaw(rawValue); return res; \ } \ -) /* end CMAP_ONLY */ \ +STC_INLINE ctype##_##X##_entry_t* \ +ctype##_##X##_putv(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey, Value value) { \ + ctype##_##X##_result_t res = ctype##_##X##_insert_key_(self, rawKey); \ + if (!res.inserted) valueDestroy(&res.item->value); \ + res.item->value = value; return res.item; \ +}) \ + \ +STC_INLINE ctype##_##X##_entry_t* \ +ctype##_##X##_put(ctype##_##X* self, CMAP_ARGS_##ctype(ctype##_##X##_rawkey_t rawKey, RawValue rawValue)) { \ + CMAP_ONLY_##ctype( return ctype##_##X##_insert_or_assign(self, rawKey, rawValue).item; ) \ + CSET_ONLY_##ctype( return ctype##_##X##_insert_key_(self, rawKey).item; ) \ +} \ + \ STC_API size_t \ ctype##_##X##_reserve(ctype##_##X* self, size_t size); \ STC_API bool \ -ctype##_##X##_erase_entry(ctype##_##X* self, ctype##_##X##_entry_t* entry); \ +ctype##_##X##_erase_entry(ctype##_##X* self, ctype##_##X##_entry_t* item); \ STC_API bool \ ctype##_##X##_erase(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey); \ \ @@ -279,7 +296,7 @@ ctype##_##X##_with_capacity(size_t cap) { \ } \ STC_API void \ ctype##_##X##_push_n(ctype##_##X* self, const ctype##_##X##_input_t in[], size_t size) { \ - for (size_t i=0; i_hashx, 0, self->bucket_count); \ } \ \ -STC_API size_t \ -ctype##_##X##_bucket(const ctype##_##X* self, const ctype##_##X##_rawkey_t* rawKeyPtr, uint32_t* hxPtr) { \ - uint32_t hash = keyHashRaw(rawKeyPtr, sizeof(ctype##_##X##_rawkey_t)); \ - uint32_t sx, hx = (hash & chash_HASH) | chash_USED; \ +STC_API ctype##_bucket_t \ +ctype##_##X##_bucket(const ctype##_##X* self, const ctype##_##X##_rawkey_t* rawKeyPtr) { \ + uint32_t sx, hash = keyHashRaw(rawKeyPtr, sizeof(ctype##_##X##_rawkey_t)); \ size_t cap = self->bucket_count; \ - size_t idx = chash_reduce(hash, cap); \ + ctype##_bucket_t b = {chash_reduce(hash, cap), (hash & chash_HASH) | chash_USED}; \ uint8_t* hashx = self->_hashx; \ - while ((sx = hashx[idx])) { \ - if (sx == hx) { \ - ctype##_##X##_rawkey_t r = keyToRaw(&self->table[idx].key); \ + while ((sx = hashx[b.idx])) { \ + if (sx == b.hx) { \ + ctype##_##X##_rawkey_t r = keyToRaw(&self->table[b.idx].key); \ if (keyEqualsRaw(&r, rawKeyPtr)) break; \ } \ - if (++idx == cap) idx = 0; \ + if (++b.idx == cap) b.idx = 0; \ } \ - *hxPtr = hx; \ - return idx; \ + return b; \ } \ \ STC_API ctype##_##X##_entry_t* \ ctype##_##X##_find(const ctype##_##X* self, ctype##_##X##_rawkey_t rawKey) { \ if (self->size == 0) return NULL; \ - uint32_t hx; \ - size_t idx = ctype##_##X##_bucket(self, &rawKey, &hx); \ - return self->_hashx[idx] ? &self->table[idx] : NULL; \ + ctype##_bucket_t b = ctype##_##X##_bucket(self, &rawKey); \ + return self->_hashx[b.idx] ? &self->table[b.idx] : NULL; \ } \ \ STC_INLINE void ctype##_##X##_reserve_expand(ctype##_##X* self) { \ if (self->size + 1 >= self->bucket_count * self->max_load_factor) \ ctype##_##X##_reserve(self, 5 + self->size * 3 / 2); \ +} \ +STC_API bool \ +ctype##_##X##_contains(const ctype##_##X* self, ctype##_##X##_rawkey_t rawKey) { \ + return self->size && self->_hashx[ctype##_##X##_bucket(self, &rawKey).idx]; \ } \ \ -STC_API struct ctype##_##X##_result \ -ctype##_##X##_insert_key(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey) { \ +STC_API ctype##_##X##_result_t \ +ctype##_##X##_insert_key_(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey) { \ ctype##_##X##_reserve_expand(self); \ - uint32_t hx; \ - size_t idx = ctype##_##X##_bucket(self, &rawKey, &hx); \ - struct ctype##_##X##_result res = {&self->table[idx], !self->_hashx[idx]}; \ + ctype##_bucket_t b = ctype##_##X##_bucket(self, &rawKey); \ + ctype##_##X##_result_t res = {&self->table[b.idx], !self->_hashx[b.idx]}; \ if (res.inserted) { \ - res.entry->key = keyFromRaw(rawKey); \ - self->_hashx[idx] = (uint8_t) hx; \ + res.item->key = keyFromRaw(rawKey); \ + self->_hashx[b.idx] = (uint8_t) b.hx; \ ++self->size; \ } \ return res; \ @@ -361,13 +378,12 @@ ctype##_##X##_reserve(ctype##_##X* self, size_t newcap) { \ tmp._hashx[newcap] = 0xff; c_swap(ctype##_##X, *self, tmp); \ ctype##_##X##_entry_t* 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##_##X##_rawkey_t r = keyToRaw(&e->key); \ - size_t idx = ctype##_##X##_bucket(self, &r, &hx); \ - slot[idx] = *e, \ - hashx[idx] = (uint8_t) hx; \ + ctype##_bucket_t b = ctype##_##X##_bucket(self, &r); \ + slot[b.idx] = *e, \ + hashx[b.idx] = (uint8_t) b.hx; \ } \ free(tmp._hashx); \ free(tmp.table); \ @@ -375,8 +391,8 @@ ctype##_##X##_reserve(ctype##_##X* self, size_t newcap) { \ } \ \ STC_API bool \ -ctype##_##X##_erase_entry(ctype##_##X* self, ctype##_##X##_entry_t* entry) { \ - size_t i = chash_entry_index(*self, entry), j = i, k, cap = self->bucket_count; \ +ctype##_##X##_erase_entry(ctype##_##X* self, ctype##_##X##_entry_t* item) { \ + size_t i = chash_entry_index(*self, item), j = i, k, cap = self->bucket_count; \ ctype##_##X##_entry_t* slot = self->table; \ uint8_t* hashx = self->_hashx; \ ctype##_##X##_rawkey_t r; \ @@ -403,9 +419,8 @@ ctype##_##X##_erase(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey) { \ return false; \ if (self->size < self->bucket_count * self->shrink_limit_factor && self->bucket_count * sizeof(ctype##_##X##_entry_t) > 1024) \ ctype##_##X##_reserve(self, self->size * 6 / 5); \ - uint32_t hx; \ - size_t i = ctype##_##X##_bucket(self, &rawKey, &hx); \ - return ctype##_##X##_erase_entry(self, self->table + i); \ + ctype##_bucket_t b = ctype##_##X##_bucket(self, &rawKey); \ + return ctype##_##X##_erase_entry(self, self->table + b.idx); \ } \ typedef int ctype##_##X##_dud diff --git a/stc/cqueue.h b/stc/cqueue.h index b8378e49..a9efa1b6 100644 --- a/stc/cqueue.h +++ b/stc/cqueue.h @@ -79,14 +79,13 @@ cqueue_##X##_back(cqueue_##X* self) {return ctype##_back(self);} \ STC_INLINE void \ cqueue_##X##_pop(cqueue_##X* self) {ctype##_pop_front(self);} \ STC_API void \ -cqueue_##X##_push_v(cqueue_##X* self, ctype##_value_t value) { \ - ctype##_push_back_v(self, value); \ +cqueue_##X##_push(cqueue_##X* self, ctype##_value_t value) { \ + ctype##_push_back(self, value); \ } \ STC_INLINE void \ -cqueue_##X##_push(cqueue_##X* self, cqueue_##X##_rawvalue_t rawValue) { \ - ctype##_push_back(self, rawValue); \ +cqueue_##X##_emplace(cqueue_##X* self, cqueue_##X##_rawvalue_t rawValue) { \ + ctype##_emplace_back(self, rawValue); \ } \ - \ STC_API void \ cqueue_##X##_push_n(cqueue_##X *self, const cqueue_##X##_input_t in[], size_t size) { \ ctype##_push_n(self, in, size); \ diff --git a/stc/cstack.h b/stc/cstack.h index 10e91865..a56d99af 100644 --- a/stc/cstack.h +++ b/stc/cstack.h @@ -66,14 +66,13 @@ cstack_##X##_top(cstack_##X* self) {return ctype##_back(self);} \ STC_INLINE void \ cstack_##X##_pop(cstack_##X* self) {ctype##_pop_back(self);} \ STC_API void \ -cstack_##X##_push_v(cstack_##X* self, ctype##_value_t value) { \ - ctype##_push_back_v(self, value); \ +cstack_##X##_push(cstack_##X* self, ctype##_value_t value) { \ + ctype##_push_back(self, value); \ } \ STC_INLINE void \ -cstack_##X##_push(cstack_##X* self, cstack_##X##_rawvalue_t rawValue) { \ - ctype##_push_back(self, rawValue); \ +cstack_##X##_emplace(cstack_##X* self, cstack_##X##_rawvalue_t rawValue) { \ + ctype##_emplace_back(self, rawValue); \ } \ - \ STC_API void \ cstack_##X##_push_n(cstack_##X *self, const cstack_##X##_input_t in[], size_t size) { \ ctype##_push_n(self, in, size); \ diff --git a/stc/cvec.h b/stc/cvec.h index e5724301..0edd41ff 100644 --- a/stc/cvec.h +++ b/stc/cvec.h @@ -73,16 +73,16 @@ cvec_##X##_resize(cvec_##X* self, size_t size, Value fill_val); \ STC_API void \ cvec_##X##_push_n(cvec_##X *self, const cvec_##X##_input_t in[], size_t size); \ STC_API void \ -cvec_##X##_push_back_v(cvec_##X* self, Value value); \ +cvec_##X##_push_back(cvec_##X* self, Value value); \ STC_INLINE void \ -cvec_##X##_push_back(cvec_##X* self, RawValue rawValue) { \ - cvec_##X##_push_back_v(self, valueFromRaw(rawValue)); \ +cvec_##X##_emplace_back(cvec_##X* self, RawValue rawValue) { \ + cvec_##X##_push_back(self, valueFromRaw(rawValue)); \ } \ STC_API void \ -cvec_##X##_insert_v(cvec_##X* self, size_t pos, Value value); \ +cvec_##X##_insert(cvec_##X* self, size_t pos, Value value); \ STC_INLINE void \ -cvec_##X##_insert(cvec_##X* self, size_t pos, RawValue rawValue) { \ - cvec_##X##_insert_v(self, pos, valueFromRaw(rawValue)); \ +cvec_##X##_emplace(cvec_##X* self, size_t pos, RawValue rawValue) { \ + cvec_##X##_insert(self, pos, valueFromRaw(rawValue)); \ } \ STC_API void \ cvec_##X##_erase(cvec_##X* self, size_t pos, size_t size); \ @@ -196,7 +196,7 @@ cvec_##X##_resize(cvec_##X* self, size_t size, Value null_val) { \ } \ \ STC_API void \ -cvec_##X##_push_back_v(cvec_##X* self, Value value) { \ +cvec_##X##_push_back(cvec_##X* self, Value value) { \ size_t len = cvec_size(*self); \ if (len == cvec_capacity(*self)) \ cvec_##X##_reserve(self, 4 + len * 3 / 2); \ @@ -205,7 +205,7 @@ cvec_##X##_push_back_v(cvec_##X* self, Value value) { \ } \ \ STC_API void \ -cvec_##X##_insert_v(cvec_##X* self, size_t pos, Value value) { \ +cvec_##X##_insert(cvec_##X* self, size_t pos, Value value) { \ size_t len = cvec_size(*self); \ if (len == cvec_capacity(*self)) \ cvec_##X##_reserve(self, 4 + len * 3 / 2); \ -- cgit v1.2.3