Changed cvecpq.h priority queue API and crandom.h API

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

-        cvec_f_pushBack(&vec, pcg32_random(&pcg));

-    cvec_f_buildPriorityQ(&vec);

+        cvec_f_pushBack(&vec, crandom32(&pcg));

+    cvecpq_f_build(&vec);

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

 

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

-        printf("%.0f ", cvec_f_topPriorityQ(&vec)), cvec_f_popPriorityQ(&vec);

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

     start = clock();

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

-        cvec_f_popPriorityQ(&vec);

+        cvecpq_f_pop(&vec);

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

 

-    pcg = pcg32_seed(seed, 0);

+    pcg = crandom32_init(seed);

     start = clock();

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

-        cvec_f_pushPriorityQ(&vec, pcg32_random(&pcg));

+        cvecpq_f_push(&vec, crandom32(&pcg));

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

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

-        printf("%.0f ", cvec_f_topPriorityQ(&vec)), cvec_f_popPriorityQ(&vec);

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

     puts("");

 }

diff --git a/examples/list.c b/examples/list.c
index 694ec60b..81569260 100644
--- a/examples/list.c
+++ b/examples/list.c
@@ -9,10 +9,10 @@ int main() {
     c_foreach (i, clist_ix, list) printf("%zu ", i.item->value);

     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 <stc/crandom.h>

 

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

-        v += pcg32_random(&pcg) & 0xffffffff;

+        v += crandom32(&pcg);

     }

     difference = clock() - before;

     printf("pcg32: %.02f, %zu\n", (float) difference / CLOCKS_PER_SEC, v);

 

-    sfc64_random_t sfc = sfc64_seed(time(NULL));

+    crandom64_t sfc = crandom64_init(time(NULL));

     before = clock(); \

     v = 0;

     for (size_t i=0; i<NN; i++) {

-        v += sfc64_random(&sfc) & 0xffffffff;

+        v += crandom64(&sfc) & 0xffffffff;

     }

     difference = clock() - before;

     printf("sfc64: %.02f, %zu\n", (float) difference / CLOCKS_PER_SEC, v);

 

-    for (int i=0; i<8; ++i) printf("%f ", sfc64_randomFloat(&sfc));

+    for (int i=0; i<8; ++i) printf("%f ", crandom64f(&sfc));

     puts("");

-    for (int i=0; i<8; ++i) printf("%f ", pcg32_randomFloat(&pcg));

+    for (int i=0; i<8; ++i) printf("%f ", crandom32f(&pcg));

     puts("");

 }
\ No newline at end of file
diff --git a/stc/crandom.h b/stc/crandom.h
index 1cf3fb2d..af7070bc 100644
--- a/stc/crandom.h
+++ b/stc/crandom.h
@@ -27,10 +27,12 @@
 #include "cdefs.h"

 #include <string.h>

 

-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 <stc/cvecpq.h>

     #include <stc/crandom.h>

     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,15 +85,15 @@ _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; \

@@ -99,17 +101,22 @@ cvec_##tag##_pushPriorityQ(CVec_##tag* self, CVecValue_##tag value) { \
         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; i<size; ++i) cvecpq_##tag##_push(self, in[i]); \

+} \

  \

 STC_API void \

-cvec_##tag##_buildPriorityQ(CVec_##tag* self) { \

+cvecpq_##tag##_build(CVec_##tag* self) { \

     size_t n = cvec_size(*self);  \

     CVecValue_##tag *arr = self->data - 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