From 3bf571bd7f0c8eface28bb5d2b7607d934865e00 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 30 Jul 2020 09:59:24 +0200 Subject: Renamed cvecpq.h to cvec_pq.h and changed API. Added pqueue initialization example in inits.c. Documented my 64bit PRNG engine. --- examples/geek7.c | 10 ++--- examples/heap.c | 16 +++---- examples/inits.c | 27 +++++++++++- examples/priority.c | 13 +++--- stc/crand.h | 29 ++++++------ stc/cvec_pq.h | 125 ++++++++++++++++++++++++++++++++++++++++++++++++++++ stc/cvecpq.h | 122 -------------------------------------------------- 7 files changed, 186 insertions(+), 156 deletions(-) create mode 100644 stc/cvec_pq.h delete mode 100644 stc/cvecpq.h diff --git a/examples/geek7.c b/examples/geek7.c index 36805dce..2524ea95 100644 --- a/examples/geek7.c +++ b/examples/geek7.c @@ -24,11 +24,11 @@ After inserting all the elements excluding the ones which are to be deleted, Pop #include #include #include -#include +#include declare_cmap(ii, int, int); declare_cvec(i, int); -declare_cvec_priority_queue(i, >); +declare_cvec_pqueue(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 - cvecpq_i_push(&heap, arr[i]); + cvec_i_pqueue_push(&heap, arr[i]); } // Print top k elements in the min heap for (int i = 0; i < k; ++i) { - printf("%d ", cvecpq_i_top(&heap)); + printf("%d ", cvec_i_pqueue_top(&heap)); // Pop the top element - cvecpq_i_pop(&heap); + cvec_i_pqueue_pop(&heap); } cvec_i_destroy(&heap); } diff --git a/examples/heap.c b/examples/heap.c index 0f4ab4c2..72232d58 100644 --- a/examples/heap.c +++ b/examples/heap.c @@ -1,10 +1,10 @@ #include #include -#include "stc/cvecpq.h" -#include "stc/crand.h" +#include +#include declare_cvec(f, float); -declare_cvec_priority_queue(f, >); +declare_cvec_pqueue(f, >); int main() { @@ -15,22 +15,22 @@ int main() clock_t start = clock(); for (int i=0; i #include #include -#include +#include #include declare_cmap(id, int, cstr_t, cstr_destroy); // Map of int -> cstr_t @@ -11,8 +11,31 @@ typedef struct {int x, y;} ipair_t; declare_cvec(ip, ipair_t, c_default_destroy, c_mem_compare); declare_clist(ip, ipair_t, c_default_destroy, c_mem_compare); +declare_cvec(f, float); +declare_cvec_pqueue(f, >); + int main(void) { + // regular vector: + 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); + c_push(&floats, cvec_f_pqueue, c_items(40.0f, 20.0f, 50.0f, 30.0f, 10.0f)); + // Output sorted: + while (cvec_size(floats) > 0) { + printf("%.1f ", cvec_f_pqueue_top(&floats)); + cvec_f_pqueue_pop(&floats); + } + puts("\n"); + cvec_f_destroy(&floats); + + // ------------------ + int year = 2020; cmap_id idnames = cmap_init; c_push(&idnames, cmap_id, c_items( @@ -23,6 +46,7 @@ int main(void) { c_foreach (i, cmap_id, idnames) printf("%d: %s\n", i.item->key, i.item->value.str); + puts(""); cmap_id_destroy(&idnames); // ------------------ @@ -42,6 +66,7 @@ int main(void) { c_foreach (i, cmap_cnt, countries) printf("%s: %d\n", i.item->key.str, i.item->value); + puts(""); cmap_cnt_destroy(&countries); // ------------------ diff --git a/examples/priority.c b/examples/priority.c index 64449304..015f24fb 100644 --- a/examples/priority.c +++ b/examples/priority.c @@ -1,25 +1,26 @@ #include #include -#include +#include #include #include declare_cvec(i, uint32_t); -declare_cvec_priority_queue(i, >); // min-heap (increasing values) +declare_cvec_pqueue(i, >); // min-heap (increasing values) int main() { crand_eng32_t pcg = crand_eng32_init(time(NULL)); + crand_uniform_i32_t dist = crand_uniform_i32_init(0, 100000000); cvec_i heap = cvec_init; - // Push ten million random numbers to queue + // Push ten million random numbers to priority queue for (int i=0; i<10000000; ++i) - cvecpq_i_push(&heap, crand_gen_i32(&pcg)); + cvec_i_pqueue_push(&heap, crand_uniform_i32(&pcg, dist)); // Extract the hundred smallest. for (int i=0; i<100; ++i) { - printf("%u ", cvecpq_i_top(&heap)); - cvecpq_i_pop(&heap); + printf("%u ", cvec_i_pqueue_top(&heap)); + cvec_i_pqueue_pop(&heap); } cvec_i_destroy(&heap); } diff --git a/stc/crand.h b/stc/crand.h index 841cb473..63a10156 100644 --- a/stc/crand.h +++ b/stc/crand.h @@ -115,34 +115,35 @@ STC_API uint32_t crand_gen_i32(crand_eng32_t* rng) { return (xors >> rot) | (xors << ((-rot) & 31)); } -/* SFC64 random number generator: http://pracrand.sourceforge.net */ - +/* New 64bit PRNG losely based on SFC64: Copyright 2020, Tyge Løvset */ +/* Faster: Updates only 192bit state. Parallel: Ensures unique sequence for each seq (2^63 seqs) */ +/* Minimal period is 2^64 per seq, average ~ 2^127 per seq */ STC_API crand_eng64_t crand_eng64_with_seq(uint64_t seed, uint64_t seq) { crand_eng64_t rng = {seed, seed, seed, (seq << 1u) | 1u}; /* increment must be odd */ for (int i = 0; i < 12; ++i) crand_gen_i64(&rng); return rng; } -#if USE_SFC64 -STC_API uint64_t crand_gen_i64(crand_eng64_t* rng) { /* original sfc64 */ +STC_API uint64_t crand_gen_i64(crand_eng64_t* rng) { enum {LROT = 24, RSHIFT = 11, LSHIFT = 3}; uint64_t *s = rng->state; - const uint64_t result = s[0] + s[1] + s[3]++; - s[0] = s[1] ^ (s[1] >> RSHIFT); - s[1] = s[2] + (s[2] << LSHIFT); - s[2] = ((s[2] << LROT) | (s[2] >> (64 - LROT))) + result; + const uint64_t b = s[1], result = s[0] ^ (s[2] += s[3]|1); + s[0] = (b + (b << LSHIFT)) ^ (b >> RSHIFT); + s[1] = ((b << LROT) | (b >> (64 - LROT))) + result; return result; } -#else -STC_API uint64_t crand_gen_i64(crand_eng64_t* rng) { /* copyright: Tyge Løvset */ + +/* // Original 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; - const uint64_t b = s[1], result = s[0] ^ (s[2] += s[3]|1); - s[0] = (b + (b << LSHIFT)) ^ (b >> RSHIFT); - s[1] = ((b << LROT) | (b >> (64 - LROT))) + result; + const uint64_t result = s[0] + s[1] + s[3]++; + s[0] = s[1] ^ (s[1] >> RSHIFT); + s[1] = s[2] + (s[2] << LSHIFT); + s[2] = ((s[2] << LROT) | (s[2] >> (64 - LROT))) + result; return result; } -#endif +*/ #endif #endif diff --git a/stc/cvec_pq.h b/stc/cvec_pq.h new file mode 100644 index 00000000..c6a896d3 --- /dev/null +++ b/stc/cvec_pq.h @@ -0,0 +1,125 @@ +/* MIT License + * + * Copyright (c) 2020 Tyge Løvset, NORCE, www.norceresearch.no + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +/* Priority Queue using cvec as heap. + + #include + #include + declare_cvec(f, float); + declare_cvec_pqueue(f, >); // min-heap (increasing values) + + int main() { + crand_eng32_t gen = crand_eng32_init(1234); + crand_uniform_f32_t dist = crand_uniform_f32_init(10.0f, 100.0f); + + cvec_f queue = cvec_init; + // Push ten million random numbers onto the queue. + for (int i=0; i<10000000; ++i) + cvec_f_pqueue_push(&queue, crand_uniform_f32(&gen, dist)); + // Extract the 100 smallest. + for (int i=0; i<100; ++i) { + printf("%f ", cvec_f_pqueue_top(&queue)); + cvec_f_pqueue_pop(&queue); + } + cvec_f_destroy(&queue); + } +*/ + +#ifndef CVEC_PQ__H__ +#define CVEC_PQ__H__ + +#include "cvec.h" + +#define declare_cvec_pqueue(tag, cmpOpr) /* < or > */ \ + \ +STC_API void \ +cvec_##tag##_pqueue_build(cvec_##tag* self); \ +STC_API void \ +cvec_##tag##_pqueue_erase(cvec_##tag* self, size_t i); \ +STC_INLINE cvec_##tag##_value_t \ +cvec_##tag##_pqueue_top(cvec_##tag* self) {return self->data[0];} \ +STC_INLINE void \ +cvec_##tag##_pqueue_pop(cvec_##tag* self) {cvec_##tag##_pqueue_erase(self, 0);} \ +STC_API void \ +cvec_##tag##_pqueue_push(cvec_##tag* self, cvec_##tag##_value_t value); \ +STC_API void \ +cvec_##tag##_pqueue_push_n(cvec_##tag *self, const cvec_##tag##_value_t in[], size_t size); \ + \ +implement_cvec_pqueue(tag, cmpOpr) \ +typedef cvec_##tag##_value_t cvec_##tag##_pqueue_input_t + +/* -------------------------- IMPLEMENTATION ------------------------- */ + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) +#define implement_cvec_pqueue(tag, cmpOpr) \ + \ +STC_INLINE void \ +_cvec_##tag##_pqueue_sift_down(cvec_##tag##_value_t* arr, size_t i, size_t n) { \ + size_t r = i, c = i << 1; \ + while (c <= n) { \ + if (c < n && cvec_##tag##_sort_compare(&arr[c], &arr[c + 1]) cmpOpr 0) \ + ++c; \ + if (cvec_##tag##_sort_compare(&arr[r], &arr[c]) cmpOpr 0) { \ + cvec_##tag##_value_t t = arr[r]; arr[r] = arr[c]; arr[r = c] = t; \ + } else \ + return; \ + c <<= 1; \ + } \ +} \ + \ +STC_API void \ +cvec_##tag##_pqueue_build(cvec_##tag* self) { \ + size_t n = cvec_size(*self); \ + cvec_##tag##_value_t *arr = self->data - 1; \ + for (size_t k = n >> 1; k != 0; --k) \ + _cvec_##tag##_pqueue_sift_down(arr, k, n); \ +} \ + \ +STC_API void \ +cvec_##tag##_pqueue_erase(cvec_##tag* self, size_t i) { \ + size_t n = cvec_size(*self) - 1; \ + self->data[i] = self->data[n]; \ + cvec_##tag##_pop_back(self); \ + _cvec_##tag##_pqueue_sift_down(self->data - 1, i + 1, n); \ +} \ + \ +STC_API void \ +cvec_##tag##_pqueue_push(cvec_##tag* self, cvec_##tag##_value_t value) { \ + cvec_##tag##_push_back(self, value); /* sift-up the value */ \ + size_t n = cvec_size(*self), c = n; \ + cvec_##tag##_value_t *arr = self->data - 1; \ + for (; c > 1 && cvec_##tag##_sort_compare(&arr[c >> 1], &value) cmpOpr 0; c >>= 1) \ + arr[c] = arr[c >> 1]; \ + if (c != n) arr[c] = value; \ +} \ +STC_API void \ +cvec_##tag##_pqueue_push_n(cvec_##tag *self, const cvec_##tag##_value_t in[], size_t size) { \ + cvec_##tag##_reserve(self, cvec_size(*self) + size); \ + for (size_t i=0; i - #include - declare_cvec(i, int); - declare_cvec_priority_queue(i, >); // min-heap (increasing values) - int main() { - crand_eng32_t pcg = crand_eng32_init(1234); - cvec_i heap = cvec_init; - // Push one million random numbers onto the queue. - for (int i=0; i<1000000; ++i) - cvecpq_i_push(&heap, crand_gen_i32(&pcg)); - // Extract the 100 smallest. - for (int i=0; i<100; ++i) { - printf("%d ", cvecpq_i_top(&heap)); - cvecpq_i_pop(&heap); - } - cvec_i_destroy(&heap); - } -*/ - -#ifndef CVECPQ__H__ -#define CVECPQ__H__ - -#include "cvec.h" - -#define declare_cvec_priority_queue(tag, cmpOpr) /* < or > */ \ - \ -STC_API void \ -cvecpq_##tag##_build(cvec_##tag* self); \ -STC_API void \ -cvecpq_##tag##_erase(cvec_##tag* self, size_t i); \ -STC_INLINE cvec_##tag##_value_t \ -cvecpq_##tag##_top(cvec_##tag* self) {return self->data[0];} \ -STC_INLINE void \ -cvecpq_##tag##_pop(cvec_##tag* self) {cvecpq_##tag##_erase(self, 0);} \ -STC_API void \ -cvecpq_##tag##_push(cvec_##tag* self, cvec_##tag##_value_t value); \ -STC_API void \ -cvecpq_##tag##_push_n(cvec_##tag *self, const cvec_##tag##_value_t in[], size_t size); \ - \ -implement_cvec_priority_queue(tag, cmpOpr) \ -typedef cvec_##tag##_value_t cvecpq_##tag##_input_t - -/* -------------------------- IMPLEMENTATION ------------------------- */ - -#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -#define implement_cvec_priority_queue(tag, cmpOpr) \ - \ -STC_INLINE void \ -_cvecpq_##tag##_siftDown(cvec_##tag##_value_t* arr, size_t i, size_t n) { \ - size_t r = i, c = i << 1; \ - while (c <= n) { \ - if (c < n && cvec_##tag##_sort_compare(&arr[c], &arr[c + 1]) cmpOpr 0) \ - ++c; \ - if (cvec_##tag##_sort_compare(&arr[r], &arr[c]) cmpOpr 0) { \ - cvec_##tag##_value_t t = arr[r]; arr[r] = arr[c]; arr[r = c] = t; \ - } else \ - return; \ - c <<= 1; \ - } \ -} \ - \ -STC_API void \ -cvecpq_##tag##_erase(cvec_##tag* self, size_t i) { \ - size_t n = cvec_size(*self) - 1; \ - self->data[i] = self->data[n]; \ - cvec_##tag##_pop_back(self); \ - _cvecpq_##tag##_siftDown(self->data - 1, i + 1, n); \ -} \ - \ -STC_API void \ -cvecpq_##tag##_push(cvec_##tag* self, cvec_##tag##_value_t value) { \ - cvec_##tag##_push_back(self, value); /* sift-up the value */ \ - size_t n = cvec_size(*self), c = n; \ - cvec_##tag##_value_t *arr = self->data - 1; \ - for (; c > 1 && cvec_##tag##_sort_compare(&arr[c >> 1], &value) cmpOpr 0; c >>= 1) \ - arr[c] = arr[c >> 1]; \ - if (c != n) arr[c] = value; \ -} \ -STC_API void \ -cvecpq_##tag##_push_n(cvec_##tag *self, const cvec_##tag##_value_t 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) \ - _cvecpq_##tag##_siftDown(arr, k, n); \ -} - -#else -#define implement_cvec_priority_queue(tag, cmpOpr) -#endif - -#endif -- cgit v1.2.3