From 8532f8e1db438d791a2d7b49d29f73a253dfb492 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Mon, 27 Jul 2020 11:59:48 +0200 Subject: Renamed cmap_xx_at() to cmap_xx_insert(). Does insert like c++ std::map::insert(), rust HashMap::insert() Updated cstr_hashRaw() to djb2() algorithm. --- examples/benchmark.c | 4 ++-- examples/geek1.c | 4 ++-- examples/geek3.c | 8 ++++---- examples/geek4.c | 4 ++-- examples/geek7.c | 2 +- examples/inits.c | 15 ++++++++------- examples/mapmap.c | 10 +++++----- examples/prime.c | 6 +++--- examples/priority.c | 3 +-- examples/rngbirthday.c | 4 ++-- stc/cmap.h | 4 ++-- stc/cstr.h | 5 ++++- 12 files changed, 36 insertions(+), 33 deletions(-) diff --git a/examples/benchmark.c b/examples/benchmark.c index 65eef03f..c9a82d6d 100644 --- a/examples/benchmark.c +++ b/examples/benchmark.c @@ -33,7 +33,7 @@ crandom64_t rng; #define CMAP_FIND(tag, key) (cmap_##tag##_find(map, key) != NULL) #define CMAP_SIZE(tag) cmap_size(map) #define CMAP_BUCKETS(tag) cmap_bucketCount(map) -#define CMAP_CLEAR(tag) cmap_##tag##_clear(&map) +#define CMAP_CLEAR(tag) cmap_##tag##_destroy(&map) #define KMAP_SETUP(tag, Key, Value) khash_t(ii)* map = kh_init(ii); khiter_t ki; int ret #define KMAP_PUT(tag, key, val) (*(ki = kh_put(ii, map, key, &ret), map->vals[ki] = val, &map->vals[ki])) @@ -41,7 +41,7 @@ crandom64_t rng; #define KMAP_FIND(tag, key) (kh_get(ii, map, key) != kh_end(map)) #define KMAP_SIZE(tag) ((size_t) kh_size(map)) #define KMAP_BUCKETS(tag) ((size_t) kh_n_buckets(map)) -#define KMAP_CLEAR(tag) kh_destroy(ii, map) +#define KMAP_CLEAR(tag) kh_destroy(ii, map) #define UMAP_SETUP(tag, Key, Value) std::unordered_map map; map.max_load_factor(maxLoadFactor) #define UMAP_PUT(tag, key, val) (map[key] = val) diff --git a/examples/geek1.c b/examples/geek1.c index bb4678df..f8471122 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_init; for (int i = 0; i < n; i++) { - cmap_ii_at(&hash, a[i] % k, 0)->value++; + cmap_ii_insert(&hash, a[i] % k, 0)->value++; } int count = 0; @@ -39,7 +39,7 @@ int findMaximumPairs(int a[], int n, int k) int second = k - it.item->key; CMapEntry_ii *hf = cmap_ii_find(&hash, first), - *hs = cmap_ii_at(&hash, second, 0); + *hs = cmap_ii_insert(&hash, second, 0); // Check for minimal occurrence if (hf->value < hs->value) { // Take the minimal diff --git a/examples/geek3.c b/examples/geek3.c index 42e50a7c..f6f8942a 100644 --- a/examples/geek3.c +++ b/examples/geek3.c @@ -15,10 +15,10 @@ int main () // ... cmap_si_put(&mymap, "Mars", 3396); - cmap_si_at(&mymap, "Saturn", 0)->value += 272; - cmap_si_put(&mymap, "Jupiter", cmap_si_at(&mymap, "Saturn", 0)->value + 9638); - cmap_si_at(&mymap, "Sun", 0)->value += 1000; - cmap_si_at(&mymap, "Sun", 0)->value += 1000; + 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; 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 81740367..e7522bb3 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_at(&has, ans.data[k].key.str, false)->value == false) { + && cmap_sb_insert(&has, ans.data[k].key.str, false)->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_at(&has, ans.data[k].key.str, false)->value == true) { + && cmap_sb_insert(&has, ans.data[k].key.str, false)->value == true) { cmap_sb_put(&has, ans.data[k].key.str, false); } } diff --git a/examples/geek7.c b/examples/geek7.c index c5da63ec..e304718d 100644 --- a/examples/geek7.c +++ b/examples/geek7.c @@ -40,7 +40,7 @@ void findElementsAfterDel(int arr[], int m, int del[], for (int i = 0; i < n; ++i) { // Increment the count of del[i] - cmap_ii_at(&mp, del[i], 0)->value++; + cmap_ii_insert(&mp, del[i], 0)->value++; } CVec_i heap = cvec_init; diff --git a/examples/inits.c b/examples/inits.c index 64e85a48..240ce5c9 100644 --- a/examples/inits.c +++ b/examples/inits.c @@ -24,25 +24,26 @@ int main(void) { c_foreach (i, cmap_id, idnames) printf("%d: %s\n", i.item->key, i.item->value.str); cmap_id_destroy(&idnames); - + // ------------------ + CMap_cnt countries = cmap_init; - cmap_cnt_at(&countries, "Greenland", 0)->value += 20; + cmap_cnt_insert(&countries, "Greenland", 0)->value += 20; c_push(&countries, cmap_cnt, c_items( {"Norway", 100}, {"Denmark", 50}, {"Iceland", 10}, )); - cmap_cnt_at(&countries, "Sweden", 0)->value += 20; - cmap_cnt_at(&countries, "Norway", 0)->value += 20; - cmap_cnt_at(&countries, "Finland", 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; c_foreach (i, cmap_cnt, countries) printf("%s: %d\n", i.item->key.str, i.item->value); cmap_cnt_destroy(&countries); - + // ------------------ CVec_ip pairs1 = cvec_init; @@ -57,7 +58,7 @@ int main(void) { printf("(%d %d) ", i.item->x, i.item->y); puts(""); cvec_ip_destroy(&pairs1); - + // ------------------ CList_ip pairs2 = clist_init; diff --git a/examples/mapmap.c b/examples/mapmap.c index 30d7f0fb..67672dee 100644 --- a/examples/mapmap.c +++ b/examples/mapmap.c @@ -12,11 +12,11 @@ declare_CMap(im, int, CMap_ii, cmap_ii_destroy); int main(void) { CMap_im m = cmap_init; CMap_ii ini = cmap_init; - cmap_ii_put(&cmap_im_at(&m, 100, ini)->value, 2000, 200); - cmap_ii_put(&cmap_im_at(&m, 100, ini)->value, 2001, 201); - cmap_ii_put(&cmap_im_at(&m, 100, ini)->value, 2000, 400); // update - cmap_ii_put(&cmap_im_at(&m, 110, ini)->value, 2000, 500); - cmap_ii_put(&cmap_im_at(&m, 120, ini)->value, 3000, 600); + cmap_ii_put(&cmap_im_insert(&m, 100, ini)->value, 2000, 200); + cmap_ii_put(&cmap_im_insert(&m, 100, ini)->value, 2001, 201); + cmap_ii_put(&cmap_im_insert(&m, 100, ini)->value, 2000, 400); // update + cmap_ii_put(&cmap_im_insert(&m, 110, ini)->value, 2000, 500); + cmap_ii_put(&cmap_im_insert(&m, 120, ini)->value, 3000, 600); c_foreach (i, cmap_im, m) c_foreach (j, cmap_ii, i.item->value) diff --git a/examples/prime.c b/examples/prime.c index 74aa108e..05ef4d57 100644 --- a/examples/prime.c +++ b/examples/prime.c @@ -28,9 +28,9 @@ static inline void sieveOfEratosthenes(size_t n) puts("done"); // Count the primes size_t count = 0; - for (size_t i = 1; i <= n; ++i) - if (cbitset_test(prime, i)) ++count; - printf("number of primes: %zu\n", count); + //for (size_t i = 1; i <= n; ++i) + // if (cbitset_test(prime, i)) ++count; + printf("number of primes: %zu\n", cbitset_count(prime)); // print primes < 1000 for (size_t i = 1; i <= 1000; ++i) if (cbitset_test(prime, i)) printf("%zu ", i); diff --git a/examples/priority.c b/examples/priority.c index 4032b19c..c1890f8c 100644 --- a/examples/priority.c +++ b/examples/priority.c @@ -7,7 +7,6 @@ declare_CVec(i, uint32_t); declare_CVec_priority_queue(i, >); // min-heap (increasing values) -declare_CMap(ii, int, int); int main() { crandom32_t pcg = crandom32_init(time(NULL)); @@ -23,4 +22,4 @@ int main() { cvecpq_i_pop(&heap); } cvec_i_destroy(&heap); -} \ No newline at end of file +} diff --git a/examples/rngbirthday.c b/examples/rngbirthday.c index 560b275a..1e6178aa 100644 --- a/examples/rngbirthday.c +++ b/examples/rngbirthday.c @@ -21,7 +21,7 @@ void repeats(void) clock_t now = clock(); for (size_t i = 0; i < N; ++i) { uint64_t k = crandom64(&rng) & mask; - int v = ++cmap_ic_at(&m, k, 0)->value; + int v = ++cmap_ic_insert(&m, k, 0)->value; if (v > 1) printf("%zu: %x - %d\n", i, k, v); } float diff = (float) (clock() - now) / CLOCKS_PER_SEC; @@ -39,7 +39,7 @@ void distribution(void) CMap_x map = cmap_x_make(M); clock_t now = clock(); for (size_t i = 0; i < N; ++i) { - ++cmap_x_at(&map, crandom32b(&rng, M), 0)->value; + ++cmap_x_insert(&map, crandom32b(&rng, M), 0)->value; } float diff = (float) (clock() - now) / CLOCKS_PER_SEC; diff --git a/stc/cmap.h b/stc/cmap.h index 21f24862..7bf94ab3 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -180,7 +180,7 @@ ctype##_##tag##_get(const CType##_##tag* self, CType##RawKey_##tag rawKey) \ STC_API CType##Entry_##tag* /* similar to c++ std::map.insert_or_assign(): */ \ ctype##_##tag##_put(CType##_##tag* self, OPT_2_##ctype(CType##RawKey_##tag rawKey, Value value)); \ OPT_1_##ctype(STC_API CType##Entry_##tag* /* similar to c++ std::map.operator[](): */ \ -ctype##_##tag##_at(CType##_##tag* self, CType##RawKey_##tag rawKey, Value initValue);) \ +ctype##_##tag##_insert(CType##_##tag* self, CType##RawKey_##tag rawKey, Value initValue);) \ STC_INLINE void \ ctype##_##tag##_swap(CType##_##tag* a, CType##_##tag* b) { c_swap(CType##_##tag, *a, *b); } \ STC_API size_t \ @@ -284,7 +284,7 @@ ctype##_##tag##_put(CType##_##tag* self, OPT_2_##ctype(CType##RawKey_##tag rawKe \ OPT_1_##ctype( \ STC_API CType##Entry_##tag* \ -ctype##_##tag##_at(CType##_##tag* self, CType##RawKey_##tag rawKey, Value initValue) { \ +ctype##_##tag##_insert(CType##_##tag* self, CType##RawKey_##tag rawKey, Value initValue) { \ ctype##_##tag##_reserveExpand_(self); \ uint32_t hx; \ size_t idx = ctype##_##tag##_bucket(self, &rawKey, &hx); \ diff --git a/stc/cstr.h b/stc/cstr.h index 972e29b6..e1eebb7d 100644 --- a/stc/cstr.h +++ b/stc/cstr.h @@ -189,7 +189,10 @@ cstr_find(CStr s, size_t pos, const char* needle) { #define cstr_compareRaw(x, y) strcmp(*(x), *(y)) #define cstr_equalsRaw(x, y) (strcmp(*(x), *(y)) == 0) STC_INLINE uint32_t cstr_hashRaw(const char* const* sPtr, size_t ignored) { - return c_defaultHash(*sPtr, strlen(*sPtr)); + uint32_t hash = 5381, c; /* djb2 */ + const char* tmp = *sPtr; + while (c = *tmp++) hash = ((hash << 5) + hash) ^ c; + return hash; } /* -------------------------- IMPLEMENTATION ------------------------- */ -- cgit v1.2.3