From 39d6f5ccd16360cd38d5d43752b4325aa6575bac Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 30 Jul 2020 12:50:56 +0200 Subject: Various cleanup of examples and READM.md. Added support for popcount on compilers without intrinsics. --- examples/advanced.c | 5 +++-- examples/benchmark.c | 23 ++++++++++++++--------- examples/geek1.c | 2 +- examples/geek2.c | 4 ++-- examples/geek4.c | 2 +- examples/geek5.c | 2 +- examples/geek6.c | 2 +- examples/geek7.c | 2 +- examples/inits.c | 22 +++++++++++++--------- examples/list.c | 22 +++++++++++----------- examples/mapmap.c | 12 ++++++------ examples/prime.c | 47 ++++++++++++++++++++++++++++------------------- examples/rngbirthday.c | 4 ++-- 13 files changed, 84 insertions(+), 65 deletions(-) (limited to 'examples') diff --git a/examples/advanced.c b/examples/advanced.c index 68732544..e57738cc 100644 --- a/examples/advanced.c +++ b/examples/advanced.c @@ -69,9 +69,10 @@ int main() {{"Olaf", "Denmark"}, 24}, {{"Harald", "Iceland"}, 12}, )); - - cmapentry_vk* e = cmap_vk_find(&vikings, (VikingVw) {"Einar", "Norway"}); + VikingVw look = {"Einar", "Norway"}; + cmapentry_vk* e = cmap_vk_find(&vikings, look); e->value += 5; // update + cmap_vk_insert(&vikings, look, 0)->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 f8536a16..07219ec2 100644 --- a/examples/benchmark.c +++ b/examples/benchmark.c @@ -14,7 +14,12 @@ // Visual Studio: compile with -TP to force C++: cl -TP -EHsc -O2 benchmark.c -declare_cmap(ii, int64_t, int64_t, c_default_destroy, c_default_equals, c_fibonacci_hash64); +static inline uint32_t fibfast_hash(const void* data, size_t len) { + const uint64_t key = *(const uint64_t *) data; + return (uint32_t) (key * 11400714819323198485llu); +} + +declare_cmap(ii, int64_t, int64_t, c_default_destroy, c_default_equals, fibfast_hash); // c_fibonacci_hash64); KHASH_MAP_INIT_INT64(ii, uint64_t) @@ -39,8 +44,8 @@ crand_eng64_t rng; #define KMAP_PUT(tag, key, val) (*(ki = kh_put(ii, map, key, &ret), map->vals[ki] = val, &map->vals[ki])) #define KMAP_ERASE(tag, key) ((ki = kh_get(ii, map, key)) != kh_end(map) ? kh_del(ii, map, ki), 1 : 0) #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_SIZE(tag) kh_size(map) +#define KMAP_BUCKETS(tag) kh_n_buckets(map) #define KMAP_CLEAR(tag) kh_destroy(ii, map) #define UMAP_SETUP(tag, Key, Value) std::unordered_map map; map.max_load_factor(max_load_factor) @@ -93,8 +98,8 @@ int rr = RR; erased += M##_ERASE(tag, RAND(rr)); \ } \ difference = clock() - before; \ - printf(#M ": size: %zu, buckets: %8zu, time: %.02f, sum: %zu, erased %zu\n", \ - M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, checksum, erased); \ + printf(#M ": size: %zu, buckets: %8zu, time: %5.02f, sum: %zu, erased %zu\n", \ + (size_t) M##_SIZE(tag), (size_t) M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, checksum, erased); \ M##_CLEAR(tag); \ } @@ -108,8 +113,8 @@ int rr = RR; for (size_t i = 0; i < N2; ++i) \ erased += M##_ERASE(tag, i); \ difference = clock() - before; \ - printf(#M ": size: %zu, buckets: %8zu, time: %.02f, erased %zu\n", \ - M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, erased); \ + printf(#M ": size: %zu, buckets: %8zu, time: %5.02f, erased %zu\n", \ + (size_t) M##_SIZE(tag), (size_t) M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, erased); \ M##_CLEAR(tag); \ } @@ -125,8 +130,8 @@ int rr = RR; for (size_t i = 0; i < N3; ++i) \ erased += M##_ERASE(tag, RAND(rr)); \ difference = clock() - before; \ - printf(#M ": size: %zu, buckets: %8zu, time: %.02f, erased %zu\n", \ - M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, erased); \ + printf(#M ": size: %zu, buckets: %8zu, time: %5.02f, erased %zu\n", \ + (size_t) M##_SIZE(tag), (size_t) M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, erased); \ M##_CLEAR(tag); \ } diff --git a/examples/geek1.c b/examples/geek1.c index 1df74024..c780a9ea 100644 --- a/examples/geek1.c +++ b/examples/geek1.c @@ -7,7 +7,7 @@ int a[] = { 1, 2, 2, 3, 2, 4, 10 }; //int a[] = { 1, 2, 2, 3, 2, 4, 10, 8, 9, 3, 2, 4 }; -#ifndef __cplusplus +#ifndef CXX // C program to implement the above approach #include #include diff --git a/examples/geek2.c b/examples/geek2.c index 988f1f98..cb4b45ee 100644 --- a/examples/geek2.c +++ b/examples/geek2.c @@ -1,4 +1,4 @@ -#ifndef __cplusplus +#ifndef CXX #include #include @@ -41,7 +41,7 @@ int main() // queried using references (&str). if (! cmap_ss_find(&book_reviews, "Les Misérables")) { printf("We've got %zu reviews, but Les Misérables ain't one.\n", - book_reviews.size); + cmap_size(book_reviews)); } // oops, this review has a lot of spelling mistakes, let's delete it. diff --git a/examples/geek4.c b/examples/geek4.c index c541e805..cef28ee7 100644 --- a/examples/geek4.c +++ b/examples/geek4.c @@ -30,7 +30,7 @@ Efficient Approach: For all the words of the first sentence, we can check if it of the first sentence in a map and check how many of these stored words are present in all of the other sentences. */ -#ifndef __cplusplus +#ifndef CXX // C implementation of the approach #include diff --git a/examples/geek5.c b/examples/geek5.c index d9885293..eef27c19 100644 --- a/examples/geek5.c +++ b/examples/geek5.c @@ -15,7 +15,7 @@ Input: arr[] = {"abc", "def", "abc"}, L = 1, R = 3, str = "ghf" Output: 0 */ -#ifndef __cplusplus +#ifndef CXX #include #include diff --git a/examples/geek6.c b/examples/geek6.c index 4689d934..db0b3bcf 100644 --- a/examples/geek6.c +++ b/examples/geek6.c @@ -23,7 +23,7 @@ We can use the unordered_map in C++ to implement the hash which allow to perform operation in almost O(1) time complexity. */ -#ifndef __cplusplus +#ifndef CXX // C program to find the smallest // positive missing number diff --git a/examples/geek7.c b/examples/geek7.c index 2524ea95..16e70e98 100644 --- a/examples/geek7.c +++ b/examples/geek7.c @@ -17,7 +17,7 @@ If present, erase it from the hash map. Else, insert it into a Min heap. After inserting all the elements excluding the ones which are to be deleted, Pop out k elements from the Min heap. */ -#ifndef __cplusplus +#ifndef CXX // C implementation of the approach diff --git a/examples/inits.c b/examples/inits.c index 16da0a4f..0d3f8bd8 100644 --- a/examples/inits.c +++ b/examples/inits.c @@ -16,17 +16,21 @@ declare_cvec_pqueue(f, >); int main(void) { - // regular vector: + + // CVEC FLOAT / PRIORITY QUEUE + cvec_f floats = cvec_init; c_push(&floats, cvec_f, c_items(4.0f, 2.0f, 5.0f, 3.0f, 1.0f)); - // Output: + c_foreach (i, cvec_f, floats) printf("%.1f ", *i.item); puts(""); - // reorganise as a priority queue, and add more numbers: - cvec_f_pqueue_build(&floats); + // CVEC PRIORITY QUEUE + + cvec_f_pqueue_build(&floats); // reorganise vec c_push(&floats, cvec_f_pqueue, c_items(40.0f, 20.0f, 50.0f, 30.0f, 10.0f)); - // Output sorted: + + // sorted: while (cvec_size(floats) > 0) { printf("%.1f ", cvec_f_pqueue_top(&floats)); cvec_f_pqueue_pop(&floats); @@ -34,7 +38,7 @@ int main(void) { puts("\n"); cvec_f_destroy(&floats); - // ------------------ + // CMAP ID int year = 2020; cmap_id idnames = cmap_init; @@ -49,7 +53,7 @@ int main(void) { puts(""); cmap_id_destroy(&idnames); - // ------------------ + // CMAP CNT cmap_cnt countries = cmap_init; @@ -69,7 +73,7 @@ int main(void) { puts(""); cmap_cnt_destroy(&countries); - // ------------------ + // CVEC PAIR cvec_ip pairs1 = cvec_init; c_push(&pairs1, cvec_ip, c_items( @@ -84,7 +88,7 @@ int main(void) { puts(""); cvec_ip_destroy(&pairs1); - // ------------------ + // CLIST PAIR clist_ip pairs2 = clist_init; c_push(&pairs2, clist_ip, c_items( diff --git a/examples/list.c b/examples/list.c index a65a8454..bf777611 100644 --- a/examples/list.c +++ b/examples/list.c @@ -5,25 +5,25 @@ declare_clist(fx, double); int main() { + int k, n = 100000; clist_fx list = clist_init; crand_eng64_t eng = crand_eng64_init(time(NULL)); - crand_uniform_f64_t dist = crand_uniform_f64_init(1.0, 100.0); - int n; - for (int i = 0; i < 10000000; ++i) // ten million + crand_uniform_f64_t dist = crand_uniform_f64_init(0.0f, n); + + for (int i = 0; i < 100000; ++i) clist_fx_push_back(&list, crand_uniform_f64(&eng, dist)); - n = 100; - c_foreach (i, clist_fx, list) - if (n--) printf("%8d: %10f\n", 100 - n, i.item->value); else break; - // Sort them... + k = 0; c_foreach (i, clist_fx, list) + if (++k <= 10) printf("%8d: %10f\n", k, i.item->value); else break; + clist_fx_sort(&list); // mergesort O(n*log n) - n = 100; puts("sorted"); - c_foreach (i, clist_fx, list) - if (n--) printf("%8d: %10f\n", 100 - n, i.item->value); else break; + + k = 0; c_foreach (i, clist_fx, list) + if (++k <= 10) printf("%8d: %10f\n", k, i.item->value); else break; clist_fx_clear(&list); c_push(&list, clist_fx, c_items(10, 20, 30, 40, 50)); - c_foreach (i, clist_fx, list) printf("%f ", i.item->value); + c_foreach (i, clist_fx, list) printf("%.1f ", i.item->value); puts(""); clist_fx_destroy(&list); diff --git a/examples/mapmap.c b/examples/mapmap.c index b349e8d3..82f35cd3 100644 --- a/examples/mapmap.c +++ b/examples/mapmap.c @@ -11,12 +11,12 @@ 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_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); + cmap_ii init = cmap_init; + cmap_ii_put(&cmap_im_insert(&m, 100, init)->value, 2000, 200); + cmap_ii_put(&cmap_im_insert(&m, 100, init)->value, 2001, 201); + cmap_ii_put(&cmap_im_insert(&m, 100, init)->value, 2000, 400); // update + cmap_ii_put(&cmap_im_insert(&m, 110, init)->value, 2000, 500); + cmap_ii_put(&cmap_im_insert(&m, 120, init)->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 2e6c99ee..974a7d90 100644 --- a/examples/prime.c +++ b/examples/prime.c @@ -1,35 +1,44 @@ #include #include +#include -static inline void sieveOfEratosthenes(size_t n) +declare_cvec(ux, uint64_t); + +static inline cvec_ux sieveOfEratosthenes(size_t n) { - cbitset_t prime = cbitset_make(n + 1, true); - printf("computing prime numbers up to %zu\n", n); - cbitset_reset(&prime, 0); - cbitset_reset(&prime, 1); + cbitset_t pbits = cbitset_make(n + 1, true); + cbitset_reset(&pbits, 0); + cbitset_reset(&pbits, 1); for (size_t i = 2; i <= n; ++i) { - // If prime[i] is not changed, then it is a prime - if (cbitset_test(prime, i) && i*i <= n) { + // If pbits[i] is not changed, then it is a prime + if (cbitset_test(pbits, i) && i*i <= n) { for (size_t j = i*i; j <= n; j += i) { - cbitset_reset(&prime, j); + cbitset_reset(&pbits, j); } } } + puts("count:"); + size_t np = cbitset_count(pbits); 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", cbitset_count(prime)); - // print primes < 1000 - for (size_t i = 1; i <= 1000; ++i) - if (cbitset_test(prime, i)) printf("%zu ", i); - puts(""); - cbitset_destroy(&prime); + cvec_ux primes = cvec_init; + cvec_ux_reserve(&primes, np); + for (uint32_t i = 2; i <= n; ++i) + if (cbitset_test(pbits, i)) cvec_ux_push_back(&primes, i); + + cbitset_destroy(&pbits); + return primes; } int main(void) { - sieveOfEratosthenes(1000000000); + int n = 1000000000; + printf("computing prime numbers up to %u\n", n); + + cvec_ux primes = sieveOfEratosthenes(n); + printf("number of primes: %zu\n", cvec_size(primes)); + for (size_t i = 0; i < 100; ++i) + printf("%zu ", primes.data[i]); + + cvec_ux_destroy(&primes); } \ No newline at end of file diff --git a/examples/rngbirthday.c b/examples/rngbirthday.c index c20bac26..03c5b783 100644 --- a/examples/rngbirthday.c +++ b/examples/rngbirthday.c @@ -22,7 +22,7 @@ void repeats(void) for (size_t i = 0; i < N; ++i) { uint64_t k = crand_gen_i64(&rng) & mask; int v = ++cmap_ic_insert(&m, k, 0)->value; - if (v > 1) printf("%zu: %x - %d\n", i, k, v); + if (v > 1) printf("%zu: %llx - %d\n", i, k, v); } float diff = (float) (clock() - now) / CLOCKS_PER_SEC; printf("%.02f", diff); @@ -49,7 +49,7 @@ void distribution(void) sum /= map.size; c_foreach (i, cmap_x, map) - printf("%zu: %zu - %zu\n", i.item->key, i.item->value, sum); + printf("%u: %zu - %zu\n", i.item->key, i.item->value, sum); printf("%.02f\n", diff); } -- cgit v1.2.3