From 1c686f72bf9857c904b1320df7248ee5144d484e Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 23 Jul 2020 20:35:07 +0200 Subject: Changed cvecpq.h priority queue API and crandom.h API --- examples/advanced.c | 11 +++------- examples/benchmark.c | 6 +++--- examples/geek7.c | 8 ++++---- examples/heap.c | 18 ++++++++--------- examples/list.c | 4 ++-- examples/priority.c | 10 +++++----- examples/rngbirthday.c | 8 ++++---- examples/rngtest.c | 12 +++++------ stc/crandom.h | 54 +++++++++++++++++++++++++++----------------------- stc/cvecpq.h | 49 +++++++++++++++++++++++++-------------------- 10 files changed, 93 insertions(+), 87 deletions(-) diff --git a/examples/advanced.c b/examples/advanced.c index b27f214d..68ddc9ef 100644 --- a/examples/advanced.c +++ b/examples/advanced.c @@ -63,17 +63,12 @@ declare_CMap(vk, Viking, int, c_defaultDestroy, vikingvw_equals, vikingvw_hash, int main() { -/* CMap_vk vikings = cmap_init; - cmap_vk_put(&vikings, (VikingVw) {"Einar", "Norway"}, 20); - cmap_vk_put(&vikings, (VikingVw) {"Olaf", "Denmark"}, 24); - cmap_vk_put(&vikings, (VikingVw) {"Harald", "Iceland"}, 12); -*/ - CMap_vk vikings = cmap_vk_from( (CMapInput_vk[]) { + c_push(&vikings, cmap_vk, c_items( {{"Einar", "Norway"}, 20}, {{"Olaf", "Denmark"}, 24}, - {{"Harald", "Iceland"}, 12} - }, 3); + {{"Harald", "Iceland"}, 12}, + )); CMapEntry_vk* e = cmap_vk_find(&vikings, (VikingVw) {"Einar", "Norway"}); e->value += 5; // update diff --git a/examples/benchmark.c b/examples/benchmark.c index 3bcd3d5c..3c1b49bb 100644 --- a/examples/benchmark.c +++ b/examples/benchmark.c @@ -26,9 +26,9 @@ KHASH_MAP_INIT_INT64(ii, uint64_t) size_t seed = 1234; static const float maxLoadFactor = 0.77f; -sfc64_random_t rng; -#define SEED(s) rng = sfc64_seed(seed) -#define RAND(N) (sfc64_random(&rng) & ((1 << N) - 1)) +crandom64_t rng; +#define SEED(s) rng = crandom64_init(seed) +#define RAND(N) (crandom64(&rng) & ((1 << N) - 1)) #define CMAP_SETUP(tag, Key, Value) CMap_##tag map = cmap_init \ diff --git a/examples/geek7.c b/examples/geek7.c index bac3f21b..c5da63ec 100644 --- a/examples/geek7.c +++ b/examples/geek7.c @@ -28,7 +28,7 @@ After inserting all the elements excluding the ones which are to be deleted, Pop declare_CMap(ii, int, int); declare_CVec(i, int); -declare_CVec_priorityQ(i, >); +declare_CVec_priority_queue(i, >); // Find k minimum element from arr[0..m-1] after deleting // elements from del[0..n-1] @@ -62,15 +62,15 @@ void findElementsAfterDel(int arr[], int m, int del[], // Else push it in the min heap else - cvec_i_pushPriorityQ(&heap, arr[i]); + cvecpq_i_push(&heap, arr[i]); } // Print top k elements in the min heap for (int i = 0; i < k; ++i) { - printf("%d ", cvec_i_topPriorityQ(&heap)); + printf("%d ", cvecpq_i_top(&heap)); // Pop the top element - cvec_i_popPriorityQ(&heap); + cvecpq_i_pop(&heap); } cvec_i_destroy(&heap); } diff --git a/examples/heap.c b/examples/heap.c index 6fbb346f..e4e91544 100644 --- a/examples/heap.c +++ b/examples/heap.c @@ -4,33 +4,33 @@ #include "stc/crandom.h" declare_CVec(f, float); -declare_CVec_priorityQ(f, >); +declare_CVec_priority_queue(f, >); int main() { uint32_t seed = time(NULL); - pcg32_random_t pcg = pcg32_seed(seed, 0); + crandom32_t pcg = crandom32_init(seed); int N = 30000000, M = 100; CVec_f vec = cvec_init; clock_t start = clock(); for (int i=0; ivalue); puts(""); - pcg32_random_t pcg = pcg32_seed(time(NULL), 0); + crandom32_t pcg = crandom32_init(time(NULL)); int n; for (int i=0; i<10000000; ++i) // ten million - clist_ix_pushBack(&list, pcg32_random(&pcg)); + clist_ix_pushBack(&list, crandom32(&pcg)); n = 100; c_foreach (i, clist_ix, list) if (n--) printf("%8d: %10zu\n", 100 - n, i.item->value); else break; diff --git a/examples/priority.c b/examples/priority.c index d6168a6b..4032b19c 100644 --- a/examples/priority.c +++ b/examples/priority.c @@ -6,21 +6,21 @@ #include declare_CVec(i, uint32_t); -declare_CVec_priorityQ(i, >); // min-heap (increasing values) +declare_CVec_priority_queue(i, >); // min-heap (increasing values) declare_CMap(ii, int, int); int main() { - pcg32_random_t pcg = pcg32_seed(time(NULL), 0); + crandom32_t pcg = crandom32_init(time(NULL)); CVec_i heap = cvec_init; // Push ten million random numbers to queue for (int i=0; i<10000000; ++i) - cvec_i_pushPriorityQ(&heap, pcg32_random(&pcg)); + cvecpq_i_push(&heap, crandom32(&pcg)); // Extract the hundred smallest. for (int i=0; i<100; ++i) { - printf("%u ", cvec_i_topPriorityQ(&heap)); - cvec_i_popPriorityQ(&heap); + printf("%u ", cvecpq_i_top(&heap)); + 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 1be96449..560b275a 100644 --- a/examples/rngbirthday.c +++ b/examples/rngbirthday.c @@ -15,12 +15,12 @@ const static uint64_t mask = (1ull << 52) - 1; void repeats(void) { - sfc64_random_t rng = sfc64_seed(seed); + crandom64_t rng = crandom64_init(seed); CMap_ic m = cmap_init; cmap_ic_reserve(&m, N); clock_t now = clock(); for (size_t i = 0; i < N; ++i) { - uint64_t k = sfc64_random(&rng) & mask; + uint64_t k = crandom64(&rng) & mask; int v = ++cmap_ic_at(&m, k, 0)->value; if (v > 1) printf("%zu: %x - %d\n", i, k, v); } @@ -34,12 +34,12 @@ declare_CVec(x, uint64_t); void distribution(void) { - pcg32_random_t rng = pcg32_seed(seed, seed); // time(NULL), time(NULL)); + crandom32_t rng = crandom32_init(seed); // time(NULL), time(NULL)); const size_t N = 1ull << 28, M = 1ull << 9; // 1ull << 10; CMap_x map = cmap_x_make(M); clock_t now = clock(); for (size_t i = 0; i < N; ++i) { - ++cmap_x_at(&map, pcg32_randomBounded(&rng, M), 0)->value; + ++cmap_x_at(&map, crandom32b(&rng, M), 0)->value; } float diff = (float) (clock() - now) / CLOCKS_PER_SEC; diff --git a/examples/rngtest.c b/examples/rngtest.c index c465b5c3..af7c7dca 100644 --- a/examples/rngtest.c +++ b/examples/rngtest.c @@ -14,26 +14,26 @@ int main(void) uint64_t v; printf("start\n"); - pcg32_random_t pcg = pcg32_seed(time(NULL), 1); + crandom32_t pcg = crandom32_init(time(NULL)); before = clock(); \ v = 0; for (size_t i=0; i -typedef struct {uint64_t state; uint64_t inc;} pcg32_random_t; +/* + * PCG32 random number generator: https://www.pcg-random.org/index.html + */ +typedef struct {uint64_t state; uint64_t inc;} crandom32_t; -/* 32 bit random number generator */ -STC_INLINE uint32_t pcg32_random(pcg32_random_t* rng) +STC_INLINE uint32_t crandom32(crandom32_t* rng) { uint64_t old = rng->state; rng->state = old * 6364136223846793005ull + rng->inc; @@ -39,39 +41,41 @@ STC_INLINE uint32_t pcg32_random(pcg32_random_t* rng) return (xos >> rot) | (xos << ((-rot) & 31)); } -/* float random int number in range [0, 1). NB: 23 bit resolution. */ -STC_INLINE float pcg32_randomFloat(pcg32_random_t* rng) { - union {uint32_t i; float f;} u = {0x3F800000u | (pcg32_random(rng) >> 9)}; +/* float random int number in range [0, 1). Note: 23 bit resolution. */ +STC_INLINE float crandom32f(crandom32_t* rng) { + union {uint32_t i; float f;} u = {0x3F800000u | (crandom32(rng) >> 9)}; return u.f - 1.0f; } /* Uniform random number in range [0, bound) */ -STC_INLINE uint32_t pcg32_randomBounded(pcg32_random_t* rng, uint32_t bound) { - return (uint32_t) (((uint64_t) pcg32_random(rng) * bound) >> 32); +STC_INLINE uint32_t crandom32b(crandom32_t* rng, uint32_t bound) { + return (uint32_t) (((uint64_t) crandom32(rng) * bound) >> 32); } -STC_INLINE pcg32_random_t pcg32_seed(uint64_t seed, uint64_t seq) { - pcg32_random_t rng = {0u, (seq << 1u) | 1u}; /* inc must be odd */ - pcg32_random(&rng); +STC_INLINE crandom32_t crandom32_init2(uint64_t seed, uint64_t seq) { + crandom32_t rng = {0u, (seq << 1u) | 1u}; /* inc must be odd */ + crandom32(&rng); rng.state += seed; - pcg32_random(&rng); + crandom32(&rng); return rng; } -/* - * Rotate bits left - */ +STC_INLINE crandom32_t crandom32_init(uint64_t seed) { + return crandom32_init2(seed, seed); +} + + +/* Rotate bits left */ STC_INLINE uint64_t c_rotateLeft64(uint64_t x, int bits) { return (x << bits) | (x >> (64 - bits)); } /* - * sfc64: http://pracrand.sourceforge.net + * SFC64 random number generator: http://pracrand.sourceforge.net */ -typedef struct {uint64_t state[4];} sfc64_random_t; +typedef struct {uint64_t state[4];} crandom64_t; -/* 64 bit random number generator */ -STC_API uint64_t sfc64_random(sfc64_random_t* rng) { +STC_API uint64_t crandom64(crandom64_t* rng) { enum {LR=24, RS=11, LS=3}; uint64_t *s = rng->state; const uint64_t result = s[0] + s[1] + s[3]++; @@ -81,15 +85,15 @@ STC_API uint64_t sfc64_random(sfc64_random_t* rng) { return result; } -/* double random int number in range [0, 1). */ -STC_INLINE double sfc64_randomFloat(sfc64_random_t* rng) { - union {uint64_t i; double f;} u = {0x3FF0000000000000ull | (sfc64_random(rng) >> 12)}; +/* float64 random int number in range [0, 1), 52 bit resolution */ +STC_INLINE double crandom64f(crandom64_t* rng) { + union {uint64_t i; double f;} u = {0x3FF0000000000000ull | (crandom64(rng) >> 12)}; return u.f - 1.0; } -STC_API sfc64_random_t sfc64_seed(const uint64_t seed) { - sfc64_random_t state = {{seed, seed, seed, 1}}; - for (int i = 0; i < 12; ++i) sfc64_random(&state); +STC_API crandom64_t crandom64_init(const uint64_t seed) { + crandom64_t state = {{seed, seed, seed, 1}}; + for (int i = 0; i < 12; ++i) crandom64(&state); return state; } diff --git a/stc/cvecpq.h b/stc/cvecpq.h index 993ca841..1d0f390b 100644 --- a/stc/cvecpq.h +++ b/stc/cvecpq.h @@ -26,17 +26,17 @@ #include #include declare_CVec(i, int); - declare_CVec_priorityQ(i, >); // min-heap (increasing values) + declare_CVec_priority_queue(i, >); // min-heap (increasing values) int main() { pcg32_random_t pcg = pcg32_seed(1234, 0); CVec_i heap = cvec_init; - // Push on one million random numbers + // Push one million random numbers onto the queue. for (int i=0; i<1000000; ++i) - cvec_i_pushPriorityQ(&heap, pcg32_random(&pcg)); + cvecpq_i_push(&heap, pcg32_random(&pcg)); // Extract the 100 smallest. for (int i=0; i<100; ++i) { - printf("%d ", cvec_i_topPriorityQ(&heap)); - cvec_i_popPriorityQ(&heap); + printf("%d ", cvecpq_i_top(&heap)); + cvecpq_i_pop(&heap); } cvec_i_destroy(&heap); } @@ -47,29 +47,31 @@ #include "cvec.h" -#define declare_CVec_priorityQ(tag, cmpOpr) /* < or > */ \ +#define declare_CVec_priority_queue(tag, cmpOpr) /* < or > */ \ \ STC_API void \ -cvec_##tag##_buildPriorityQ(CVec_##tag* self); \ +cvecpq_##tag##_build(CVec_##tag* self); \ STC_API void \ -cvec_##tag##_eraseFromPriorityQ(CVec_##tag* self, size_t i); \ +cvecpq_##tag##_erase(CVec_##tag* self, size_t i); \ STC_INLINE CVecValue_##tag \ -cvec_##tag##_topPriorityQ(CVec_##tag* self) {return self->data[0];} \ +cvecpq_##tag##_top(CVec_##tag* self) {return self->data[0];} \ STC_INLINE void \ -cvec_##tag##_popPriorityQ(CVec_##tag* self) {cvec_##tag##_eraseFromPriorityQ(self, 0);} \ +cvecpq_##tag##_pop(CVec_##tag* self) {cvecpq_##tag##_erase(self, 0);} \ STC_API void \ -cvec_##tag##_pushPriorityQ(CVec_##tag* self, CVecValue_##tag value); \ +cvecpq_##tag##_push(CVec_##tag* self, CVecValue_##tag value); \ +STC_API void \ +cvecpq_##tag##_pushN(CVec_##tag *self, const CVecValue_##tag in[], size_t size); \ \ -implement_CVec_priorityQ(tag, cmpOpr) \ -typedef CVec_##tag CVec_priorityQ_##tag +implement_CVec_priority_queue(tag, cmpOpr) \ +typedef CVecValue_##tag cvecpq_##tag##_input_t /* -------------------------- IMPLEMENTATION ------------------------- */ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -#define implement_CVec_priorityQ(tag, cmpOpr) \ +#define implement_CVec_priority_queue(tag, cmpOpr) \ \ STC_INLINE void \ -_cvec_##tag##_siftDown(CVecValue_##tag* arr, size_t i, size_t n) { \ +_cvecpq_##tag##_siftDown(CVecValue_##tag* arr, size_t i, size_t n) { \ size_t r = i, c = i << 1; \ while (c <= n) { \ if (c < n && cvec_##tag##_sortCompare(&arr[c], &arr[c + 1]) cmpOpr 0) \ @@ -83,33 +85,38 @@ _cvec_##tag##_siftDown(CVecValue_##tag* arr, size_t i, size_t n) { \ } \ \ STC_API void \ -cvec_##tag##_eraseFromPriorityQ(CVec_##tag* self, size_t i) { \ +cvecpq_##tag##_erase(CVec_##tag* self, size_t i) { \ size_t n = cvec_size(*self) - 1; \ self->data[i] = self->data[n]; \ cvec_##tag##_popBack(self); \ - _cvec_##tag##_siftDown(self->data - 1, i + 1, n); \ + _cvecpq_##tag##_siftDown(self->data - 1, i + 1, n); \ } \ \ STC_API void \ -cvec_##tag##_pushPriorityQ(CVec_##tag* self, CVecValue_##tag value) { \ +cvecpq_##tag##_push(CVec_##tag* self, CVecValue_##tag value) { \ cvec_##tag##_pushBack(self, value); /* sift-up the value */ \ size_t n = cvec_size(*self), c = n; \ CVecValue_##tag *arr = self->data - 1; \ for (; c > 1 && cvec_##tag##_sortCompare(&arr[c >> 1], &value) cmpOpr 0; c >>= 1) \ arr[c] = arr[c >> 1]; \ if (c != n) arr[c] = value; \ +} \ +STC_API void \ +cvecpq_##tag##_pushN(CVec_##tag *self, const CVecValue_##tag in[], size_t size) { \ + cvec_##tag##_reserve(self, cvec_size(*self) + size); \ + for (size_t i=0; idata - 1; \ for (size_t k = n >> 1; k != 0; --k) \ - _cvec_##tag##_siftDown(arr, k, n); \ + _cvecpq_##tag##_siftDown(arr, k, n); \ } #else -#define implement_CVec_priorityQ(tag, cmpOpr) +#define implement_CVec_priority_queue(tag, cmpOpr) #endif #endif -- cgit v1.2.3