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. --- README.md | 115 ++++++++++++++++++++++++++----------------------- 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 +- stc/cbitset.h | 30 +++++++++---- stc/cdefs.h | 2 +- stc/crand.h | 7 +-- 17 files changed, 171 insertions(+), 132 deletions(-) diff --git a/README.md b/README.md index 03ef8bf3..0369755c 100644 --- a/README.md +++ b/README.md @@ -11,10 +11,10 @@ An elegant, typesafe, generic, customizable, user-friendly, consistent, and very - **stc/cset.h** - A generic **unordered set** implemented in tandem with *unordered map* - **stc/cstr.h** - Compact and powerful **string** class. - **stc/cvec.h** - Dynamic generic **vector** class, works well as a **stack**. -- **stc/cvecpq.h** - Priority queue adapter for **cvec.h**, implemented as a **heap**. +- **stc/cvec_pq.h** - Priority queue adapter for **cvec.h**, implemented as a **heap**. in *O*(1). Also contains various *splice* functions and (merge) *sort*. - **stc/coption.h** - Implementation of *getopt_long*-"like" function, *coption_get*, to parse command line arguments. -- **stc/crandom.h** - A few very efficent modern random number generators *pcg32* and *sfc64*. It also implements the crypto-strong *siphash* algorithm. +- **stc/crand.h** - A few very efficent modern random number generators *pcg32* and *sfc64-variant*. - **stc/cdefs.h** - A common include file with some general definitions. The usage of the containers is similar to the C++ standard containers, so it should be easier for those who are familiar with them. @@ -64,30 +64,31 @@ This library is very efficent. Containers have templated intrusive elements. One **CMAP**=*cmap*, KMAP=*khash*, UMAP=*std::unordered_map*, BMAP=*ska::bytell_hash_map*, FMAP=*ska::flat_hash_map*, RMAP=*robin_hood::unordered_map* ``` -Random keys are in range [0, 2^20): -map: 7000000 repeats of Insert random key + (try to) remove a different random key: -CMAP(ii): sz: 523938, bucks: 1013337, time: 0.39, sum: 24500003500000, erase: 3237392 --> fastest -KMAP(ii): sz: 523938, bucks: 2097152, time: 0.46, sum: 24500003500000, erase: 3237392 -UMAP(ii): sz: 523938, bucks: 1056323, time: 2.21, sum: 24500003500000, erase: 3237392 -BMAP(ii): sz: 523938, bucks: 1048576, time: 0.46, sum: 24500003500000, erase: 3237392 -FMAP(ii): sz: 523938, bucks: 1048576, time: 0.43, sum: 24500003500000, erase: 3237392 -RMAP(ii): sz: 523938, bucks: 838860, time: 0.82, sum: 24500003500000, erase: 3237392 - -map: Insert 10000000 sequensial keys, then remove them in same order: -CMAP(ii): sz: 0, bucks: 17001171, time: 0.75, erase 10000000 --> second fastest -KMAP(ii): sz: 0, bucks: 16777216, time: 0.48, erase 10000000 -UMAP(ii): sz: 0, bucks: 17961079, time: 1.04, erase 10000000 -BMAP(ii): sz: 0, bucks: 16777216, time: 1.04, erase 10000000 -FMAP(ii): sz: 0, bucks: 16777216, time: 0.94, erase 10000000 -RMAP(ii): sz: 0, bucks: 13421772, time: 0.84, erase 10000000 - -map: Insert 10000000 random keys, then remove them in same order: -CMAP(ii): sz: 0, bucks: 1621347, time: 0.41, erase 1048490 --> fastest -KMAP(ii): sz: 0, bucks: 2097152, time: 0.77, erase 1048490 -UMAP(ii): sz: 0, bucks: 2144977, time: 1.67, erase 1048490 -BMAP(ii): sz: 0, bucks: 2097152, time: 0.52, erase 1048490 -FMAP(ii): sz: 0, bucks: 2097152, time: 0.44, erase 1048490 -RMAP(ii): sz: 0, bucks: 1677721, time: 0.65, erase 1048490 +Random keys are in range [0, 2^20), seed = 1596103163: + +Unordered maps: 50000000 repeats of Insert random key + try to remove a random key: +CMAP: time: 2.49 sec +KMAP: time: 11.80 sec +UMAP: time: 16.07 sec +BMAP: time: 3.54 sec +FMAP: time: 2.79 sec +RMAP: time: 5.96 sec + +Unordered maps: Insert 50000000 index keys, then remove them in same order: +CMAP: time: 5.16 sec +KMAP: time: 3.34 sec +UMAP: time: 4.91 sec +BMAP: time: 5.37 sec +FMAP: time: 4.51 sec +RMAP: time: 5.14 sec + +Unordered maps: Insert 100000000 random keys, then remove them in same order: +CMAP: time: 2.62 sec +KMAP: time: 6.27 sec +UMAP: time: 15.30 sec +BMAP: time: 5.17 sec +FMAP: time: 3.37 sec +RMAP: time: 4.99 sec ``` Memory efficiency ----------------- @@ -113,7 +114,7 @@ cmap_si_put(&map, cstr_make("mykey"), 12); but the main incovenience is with lookup: ``` cstr lookup = cstr_make("mykey"); -int x = cmap_si_get(&map, lookup)->value; +int x = cmap_si_find(&map, lookup)->value; cstr_destroy(&lookup); ``` To avoid this, use *declare_cmap_str()*: @@ -121,8 +122,8 @@ To avoid this, use *declare_cmap_str()*: declare_cmap_str(si, int); ... cmap_si map = cmap_init; -cmap_si_put(&map, "mykey", 12); // constructs a cstr key from the const char* internally. -int x = cmap_si_get(&map, "mykey")->value; // no allocation of string key happens here. +cmap_si_put(&map, "mykey", 12); // constructs a cstr key from the const char* internally. +int x = cmap_si_find(&map, "mykey")->value; // no allocation of string key happens here. cmap_si_destroy(&map); ``` An alternative would be to use *char* * as key type, but you would have to manage the memory of the hash char* keys yourself. @@ -145,7 +146,7 @@ Note: The *cmap_sm_destroy(&theMap)* call below, will destroy all the nested con void verify_destroy(float* v) {printf("destroy %g\n", *v);} declare_carray(f, float, verify_destroy); // you should omit the last argument - float type need no destroy. -declare_clist(t2, carray2_f, carray2_f_destroy, c_no_compare); +declare_clist(t2, carray2f, carray2f_destroy, c_no_compare); declare_cmap(il, int, clist_t2, clist_t2_destroy); declare_cmap_str(sm, cmap_il, cmap_il_destroy); @@ -155,20 +156,20 @@ int main() { cmap_sm theMap = cmap_init; { // Construct. - carray2_f table = carray2_f_make(xdim, ydim, 0.f); + carray2f table = carray2f_make(xdim, ydim, 0.f); clist_t2 tableList = clist_init; cmap_il listMap = cmap_init; // Put in some data. - carray2_f_data(table, x)[y] = 3.1415927; // table[x][y] + carray2f_data(table, x)[y] = 3.1415927; // table[x][y] clist_t2_push_back(&tableList, table); cmap_il_put(&listMap, entry, tableList); cmap_sm_put(&theMap, "First", listMap); } // Access the data entry - carray2_f table = clist_back(cmap_il_get(&cmap_sm_get(&theMap, "First")->value, entry)->value); - printf("value is: %f\n", carray2_f_value(table, x, y)); + carray2f table = clist_back(cmap_il_get(&cmap_sm_get(&theMap, "First")->value, entry)->value); + printf("value is: %f\n", carray2f_value(table, x, y)); cmap_sm_destroy(&theMap); // free up the whole shebang! } @@ -178,7 +179,7 @@ int main() { #include int main() { - cstr s1 = cstr_make("one-nine-three-seven-five"); + cstr_t s1 = cstr_make("one-nine-three-seven-five"); printf("%s.\n", s1.str); cstr_insert(&s1, 3, "-two"); @@ -290,26 +291,32 @@ int main() { #include #include #include -#include -declare_clist(i, uint64_t); - +#include +declare_clist(fx, double); + int main() { - clist_i list = clist_init; - int N = 2000000, n; - crandom64_t rng = crandom64_uniform_engine(time(NULL)); - for (int i=0; ivalue); - puts("sorting:"); - // Sort them... - clist_i_sort(&list); // mergesort O(n*log n) - n = 0; - puts("done:"); - c_foreach (i, clist_i, list) - if (++n % (N/50) == 0) printf("%10d: %zu\n", n, i.item->value); - clist_i_destroy(&list); + clist_fx list = clist_init; + crand_eng64_t eng = crand_eng64_init(time(NULL)); + crand_uniform_f64_t dist = crand_uniform_f64_init(100.0, 1000.0); + int k; + + for (int i = 0; i < 10000000; ++i) + clist_fx_push_back(&list, crand_uniform_f64(&eng, dist)); + k = 0; c_foreach (i, clist_fx, list) + if (++k <= 100) printf("%8d: %10f\n", k, i.item->value); else break; + + clist_fx_sort(&list); // mergesort O(n*log n) + puts("sorted"); + + k = 0; c_foreach (i, clist_fx, list) + if (++k <= 100) 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); + puts(""); + + clist_fx_destroy(&list); } ``` **carray**. 1d, 2d and 3d arrays, allocated from heap in one memory block. *carray3* may have sub-array "views" of *carray2* and *carray1* etc., as shown in the following example: 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); } diff --git a/stc/cbitset.h b/stc/cbitset.h index aed8b6a7..cb8040ce 100644 --- a/stc/cbitset.h +++ b/stc/cbitset.h @@ -48,13 +48,6 @@ int main() { #include #include "cdefs.h" -#if defined(__GNUC__) -#define cbitset_popcnt64(i) __builtin_popcountll(i) -#else -#include -#define cbitset_popcnt64(i) _mm_popcnt_u64(i) -#endif - typedef struct { uint64_t* _arr; size_t size; } cbitset_t; #define cbitset_init {NULL, 0} @@ -158,11 +151,30 @@ STC_API void cbitset_resize(cbitset_t* self, size_t size, bool value) { } } +#if defined(__GNUC__) + #define c_popcount64(x) __builtin_popcountll(x) +#elif defined(_MSC_VER) + #include + #define c_popcount64(x) _mm_popcnt_u64(x) +#else +/* http://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation */ +static inline uint64_t c_popcount64(uint64_t x) { + uint64_t m1 = 0x5555555555555555ll; + uint64_t m2 = 0x3333333333333333ll; + uint64_t m4 = 0x0F0F0F0F0F0F0F0Fll; + uint64_t h01 = 0x0101010101010101ll; + x -= (x >> 1) & m1; + x = (x & m2) + ((x >> 2) & m2); + x = (x + (x >> 4)) & m4; + return (x * h01) >> 56; +} +#endif + STC_API size_t cbitset_count(cbitset_t set) { size_t count = 0, n = (set.size + 63) >> 6; if (set.size > 0) { - --n; for (size_t i=0; i> 13); + return (uint32_t) x; // (x >> 13); } #endif diff --git a/stc/crand.h b/stc/crand.h index 63a10156..b6595bcd 100644 --- a/stc/crand.h +++ b/stc/crand.h @@ -43,7 +43,7 @@ typedef struct {float min, range;} crand_uniform_f32_t; /* 32 bit random number generator engine */ STC_API crand_eng32_t crand_eng32_with_seq(uint64_t seed, uint64_t seq); STC_INLINE crand_eng32_t crand_eng32_init(uint64_t seed) { - return crand_eng32_with_seq(seed, 1); + return crand_eng32_with_seq(seed, seed); } /* int random number generator, range [0, 2^32) */ @@ -98,7 +98,7 @@ STC_INLINE double crand_uniform_f64(crand_eng64_t* rng, crand_uniform_f64_t dist #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -/* PCG32 random number generator: https://www.pcg-random.org/index.html */ +/* PCG32 random number generator: https://www.pcg-random.org/download.html */ STC_API crand_eng32_t crand_eng32_with_seq(uint64_t seed, uint64_t seq) { crand_eng32_t rng = {0u, (seq << 1u) | 1u}; /* inc must be odd */ @@ -107,6 +107,7 @@ STC_API crand_eng32_t crand_eng32_with_seq(uint64_t seed, uint64_t seq) { crand_gen_i32(&rng); return rng; } + STC_API uint32_t crand_gen_i32(crand_eng32_t* rng) { uint64_t old = rng->state[0]; rng->state[0] = old * 6364136223846793005ull + rng->state[1]; @@ -133,7 +134,7 @@ STC_API uint64_t crand_gen_i64(crand_eng64_t* rng) { return result; } -/* // Original SFC64 random number generator: http://pracrand.sourceforge.net +/* // SFC64 random number generator: http://pracrand.sourceforge.net STC_API uint64_t crand_gen_i64(crand_eng64_t* rng) { enum {LROT = 24, RSHIFT = 11, LSHIFT = 3}; uint64_t *s = rng->state; -- cgit v1.2.3