Renamed cvecpq.h to cvec_pq.h and changed API. Added pqueue initialization example in inits.c. Documented my 64bit PRNG engine.

6 files changed, 103 insertions, 73 deletions

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 <stdio.h>

 #include <stc/clist.h>

 #include <stc/cmap.h>

-#include <stc/cvecpq.h>

+#include <stc/cvec_pq.h>

 

 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 <stdio.h>

 #include <time.h>

-#include "stc/cvecpq.h"

-#include "stc/crand.h"

+#include <stc/crand.h>

+#include <stc/cvec_pq.h>

 

 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<N; ++i)

         cvec_f_push_back(&vec, crand_gen_i32(&pcg));

-    cvecpq_f_build(&vec);

+    cvec_f_pqueue_build(&vec);

     printf("Built priority queue: %f secs\n", (clock() - start) / (float) CLOCKS_PER_SEC);

 

     for (int i=0; i<M; ++i)

-        printf("%.0f ", cvecpq_f_top(&vec)), cvecpq_f_pop(&vec);

+        printf("%.0f ", cvec_f_pqueue_top(&vec)), cvec_f_pqueue_pop(&vec);

     start = clock();

     for (int i=M; i<N; ++i)

-        cvecpq_f_pop(&vec);

+        cvec_f_pqueue_pop(&vec);

     printf("\n\npopped PQ: %f secs\n", (clock() - start) / (float) CLOCKS_PER_SEC);

 

     pcg = crand_eng32_init(seed);

     start = clock();

     for (int i=0; i<N; ++i)

-        cvecpq_f_push(&vec, crand_gen_i32(&pcg));

+        cvec_f_pqueue_push(&vec, crand_gen_i32(&pcg));

     printf("pushed PQ: %f secs\n", (clock() - start) / (float) CLOCKS_PER_SEC);

     for (int i=0; i<M; ++i)

-        printf("%.0f ", cvecpq_f_top(&vec)), cvecpq_f_pop(&vec);

+        printf("%.0f ", cvec_f_pqueue_top(&vec)), cvec_f_pqueue_pop(&vec);

     puts("");

 }

diff --git a/examples/inits.c b/examples/inits.c
index 0769ce3c..16da0a4f 100644
--- a/examples/inits.c
+++ b/examples/inits.c
@@ -1,7 +1,7 @@
 #include <stdio.h>

 #include <stc/cstr.h>

 #include <stc/cmap.h>

-#include <stc/cvec.h>

+#include <stc/cvec_pq.h>

 #include <stc/clist.h>

 

 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 <stdio.h>

 #include <time.h>

-#include <stc/cvecpq.h>

+#include <stc/cvec_pq.h>

 #include <stc/cmap.h>

 #include <stc/crand.h>

 

 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/cvecpq.h b/stc/cvec_pq.h
index 2e6f2d09..c6a896d3 100644
--- a/stc/cvecpq.h
+++ b/stc/cvec_pq.h
@@ -21,57 +21,60 @@
  * SOFTWARE.

  */

 

-/*  Priority Queue using CVec as heap.

+/*  Priority Queue using cvec as heap.

 

-    #include <stc/cvecpq.h>

     #include <stc/crand.h>

-    declare_cvec(i, int);

-    declare_cvec_priority_queue(i, >); // min-heap (increasing values)

+    #include <stc/cvec_pq.h>

+    declare_cvec(f, float);

+    declare_cvec_pqueue(f, >); // 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));

+        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("%d ", cvecpq_i_top(&heap));

-            cvecpq_i_pop(&heap);

+            printf("%f ", cvec_f_pqueue_top(&queue));

+            cvec_f_pqueue_pop(&queue);

         }

-        cvec_i_destroy(&heap);

+        cvec_f_destroy(&queue);

     }

 */

 

-#ifndef CVECPQ__H__

-#define CVECPQ__H__

+#ifndef CVEC_PQ__H__

+#define CVEC_PQ__H__

 

 #include "cvec.h"

 

-#define declare_cvec_priority_queue(tag, cmpOpr) /* < or > */ \

+#define declare_cvec_pqueue(tag, cmpOpr) /* < or > */ \

  \

 STC_API void \

-cvecpq_##tag##_build(cvec_##tag* self); \

+cvec_##tag##_pqueue_build(cvec_##tag* self); \

 STC_API void \

-cvecpq_##tag##_erase(cvec_##tag* self, size_t i); \

+cvec_##tag##_pqueue_erase(cvec_##tag* self, size_t i); \

 STC_INLINE cvec_##tag##_value_t \

-cvecpq_##tag##_top(cvec_##tag* self) {return self->data[0];} \

+cvec_##tag##_pqueue_top(cvec_##tag* self) {return self->data[0];} \

 STC_INLINE void \

-cvecpq_##tag##_pop(cvec_##tag* self) {cvecpq_##tag##_erase(self, 0);} \

+cvec_##tag##_pqueue_pop(cvec_##tag* self) {cvec_##tag##_pqueue_erase(self, 0);} \

 STC_API void \

-cvecpq_##tag##_push(cvec_##tag* self, cvec_##tag##_value_t value); \

+cvec_##tag##_pqueue_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); \

+cvec_##tag##_pqueue_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

+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_priority_queue(tag, cmpOpr) \

+#define implement_cvec_pqueue(tag, cmpOpr) \

  \

 STC_INLINE void \

-_cvecpq_##tag##_siftDown(cvec_##tag##_value_t* arr, size_t i, size_t n) { \

+_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) \

@@ -85,15 +88,23 @@ _cvecpq_##tag##_siftDown(cvec_##tag##_value_t* arr, size_t i, size_t n) { \
 } \

  \

 STC_API void \

-cvecpq_##tag##_erase(cvec_##tag* self, size_t i) { \

+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); \

-    _cvecpq_##tag##_siftDown(self->data - 1, i + 1, n); \

+    _cvec_##tag##_pqueue_sift_down(self->data - 1, i + 1, n); \

 } \

  \

 STC_API void \

-cvecpq_##tag##_push(cvec_##tag* self, cvec_##tag##_value_t value) { \

+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; \

@@ -102,21 +113,13 @@ cvecpq_##tag##_push(cvec_##tag* self, cvec_##tag##_value_t value) { \
     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##_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<size; ++i) cvecpq_##tag##_push(self, in[i]); \

-} \

- \

-STC_API void \

-cvecpq_##tag##_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) \

-        _cvecpq_##tag##_siftDown(arr, k, n); \

+    for (size_t i=0; i<size; ++i) cvec_##tag##_pqueue_push(self, in[i]); \

 }

 

 #else

-#define implement_cvec_priority_queue(tag, cmpOpr)

+#define implement_cvec_pqueue(tag, cmpOpr)

 #endif

 

 #endif