More refactoring of cbits.h + minor changes in examples/benchmark.

3 files changed, 68 insertions, 49 deletions

diff --git a/benchmarks/misc/sso_bench2.cpp b/benchmarks/misc/sso_bench2.cpp
index 91ffe6ca..7d3bf5ca 100644
--- a/benchmarks/misc/sso_bench2.cpp
+++ b/benchmarks/misc/sso_bench2.cpp
@@ -2,7 +2,7 @@
 #include <iostream>
 #include <vector>
 #include <chrono>
-#include <stc/alt/cstr.h>
+//#define STC_USE_SSO 1
 #define i_val_str
 #include <stc/cstack.h>
 
@@ -29,8 +29,7 @@ static void sromutrio(uint64_t seed) {
 }
 
 
-static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz=+";
-static const int ARRAY_SIZE = sizeof(CHARS) - 1;
+static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz=+-";
 
 static const int BENCHMARK_SIZE = 10000000;
 static const int MAX_STRING_LENGTH = 20;
@@ -39,7 +38,7 @@ using time_point = std::chrono::high_resolution_clock::time_point;
 
 void addRandomString_STD(std::vector<std::string>& vec, const int length) {
     std::string s(length, 0);
-    char* p = s.data();
+    char* p = &s[0];
     for (int i = 0; i < length; ++i) {
         p[i] = CHARS[romutrio() & 63];
     }
@@ -60,10 +59,13 @@ void addRandomString_STC(cstack_str& vec, const int length) {
 template <class L, typename R>
 void benchmark(L& vec, const int length, R addRandomString) {
     time_point t1 = std::chrono::high_resolution_clock::now();
-    
-    for (int i = 0; i < BENCHMARK_SIZE; i++) {
-        addRandomString(vec, length);
-    }
+
+    if (length == 0)
+        for (int i = 0; i < BENCHMARK_SIZE; i++)
+            addRandomString(vec, (i*13 & 31) + 1);
+    else 
+        for (int i = 0; i < BENCHMARK_SIZE; i++)
+            addRandomString(vec, length);
 
     time_point t2 = std::chrono::high_resolution_clock::now();
     const auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
@@ -74,6 +76,23 @@ void benchmark(L& vec, const int length, R addRandomString) {
 int main() {
     sromutrio(1234);
     std::cerr << "length\ttime\tstd::string\n";
+    for (int k = 0; k < 4; k++) {
+        std::vector<std::string> vec; vec.reserve(BENCHMARK_SIZE);
+        benchmark(vec, 0, addRandomString_STD);
+        std::cout << '\t' << vec[0] << '\n';
+    }
+
+    sromutrio(1234);
+    std::cerr << "\nlength\ttime\tSTC string\n";
+    for (int k = 0; k < 4; k++) {
+        cstack_str vec = cstack_str_with_capacity(BENCHMARK_SIZE);
+        benchmark(vec, 0, addRandomString_STC);
+        std::cout << '\t' << cstr_str(&vec.data[0]) << '\n';
+        cstack_str_drop(&vec);
+    }
+
+    sromutrio(1234);
+    std::cerr << "length\ttime\tstd::string\n";
     for (int length = 1; length <= MAX_STRING_LENGTH; length++) {
         std::vector<std::string> vec; vec.reserve(BENCHMARK_SIZE);
         benchmark(vec, length, addRandomString_STD);
diff --git a/examples/mapmap.c b/examples/mapmap.c
index b3360d1e..2d681d23 100644
--- a/examples/mapmap.c
+++ b/examples/mapmap.c
@@ -24,15 +24,13 @@ void add(Departments* deps, const char* name, const char* email, const char* dep
     People_emplace_or_assign(people, name, email);

 }

 

-Stack contains(Departments* map, const char* name)

+int contains(Departments* map, const char* name)

 {

-    Stack stk = Stack_init();

-    const People_value* v;

+    int count = 0;

     c_foreach (i, Departments, *map)

-        if ((v = People_get(&i.ref->second, name))) {

-            Stack_push(&stk, People_value_clone(*v));

-        }

-    return stk;

+        if (People_contains(&i.ref->second, name))

+            ++count;

+    return count;

 }

 

 int main(void)

@@ -58,10 +56,10 @@ int main(void)
                 printf("%s: %s - %s\n", i.ref->first.str, _.name.str, _.email.str);

         puts("");

 

-        c_auto (Stack, s) printf("found: %" PRIuMAX "\n", Stack_size(s = contains(&map, "Nick Denton")));

-        c_auto (Stack, s) printf("found: %" PRIuMAX "\n", Stack_size(s = contains(&map, "Patrick Dust")));

-        c_auto (Stack, s) printf("found: %" PRIuMAX "\n", Stack_size(s = contains(&map, "Dennis Kay")));

-        c_auto (Stack, s) printf("found: %" PRIuMAX "\n", Stack_size(s = contains(&map, "Serena Bath")));

+        printf("found: %d\n", contains(&map, "Nick Denton"));

+        printf("found: %d\n", contains(&map, "Patrick Dust"));

+        printf("found: %d\n", contains(&map, "Dennis Kay"));

+        printf("found: %d\n", contains(&map, "Serena Bath"));

         puts("Done");

     }

 }

diff --git a/include/stc/cbits.h b/include/stc/cbits.h
index 347261d8..8d030e25 100644
--- a/include/stc/cbits.h
+++ b/include/stc/cbits.h
@@ -78,6 +78,8 @@ STC_INLINE void     cbits_drop(cbits* self) { c_free(self->data64); }
 STC_INLINE size_t   cbits_size(cbits set) { return set.size; }

 

 #define _cbits_bit(i) ((uint64_t)1 << ((i) & 63))

+#define _cbits_words(n) (((n) + 63) >> 6)

+#define _cbits_bytes(n) (_cbits_words(n) * sizeof(uint64_t))

 

 #define cbits_new(literal) \

     cbits_from_n(literal, c_strlen_lit(literal))

@@ -92,60 +94,60 @@ STC_INLINE cbits cbits_move(cbits* self) {
     return tmp;

 }

 

-STC_INLINE bool cbits_test(cbits set, size_t i) {

+STC_INLINE bool cbits_test(cbits set, const size_t i) {

     return (set.data64[i >> 6] & _cbits_bit(i)) != 0;

 }

 

-STC_INLINE bool cbits_at(cbits set, size_t i) {

+STC_INLINE bool cbits_at(cbits set, const size_t i) {

     return (set.data64[i >> 6] & _cbits_bit(i)) != 0;

 }

 

-STC_INLINE void cbits_set(cbits *self, size_t i) {

+STC_INLINE void cbits_set(cbits *self, const size_t i) {

     self->data64[i >> 6] |= _cbits_bit(i);

 }

 

-STC_INLINE void cbits_reset(cbits *self, size_t i) {

+STC_INLINE void cbits_reset(cbits *self, const size_t i) {

     self->data64[i >> 6] &= ~_cbits_bit(i);

 }

 

-STC_INLINE void cbits_set_value(cbits *self, size_t i, bool value) {

+STC_INLINE void cbits_set_value(cbits *self, const size_t i, const bool value) {

     self->data64[i >> 6] ^= ((uint64_t)-(int)value ^ self->data64[i >> 6]) & _cbits_bit(i);

 }

 

-STC_INLINE void cbits_flip(cbits *self, size_t i) {

+STC_INLINE void cbits_flip(cbits *self, const size_t i) {

     self->data64[i >> 6] ^= _cbits_bit(i);

 }

 

-STC_INLINE void cbits_set_all(cbits *self, bool value) {

-    memset(self->data64, -(int)value, ((self->size + 63) >> 6) * 8);

+STC_INLINE void cbits_set_all(cbits *self, const bool value) {

+    memset(self->data64, -(int)value, _cbits_bytes(self->size));

 }

 

-STC_INLINE void cbits_set_values(cbits *self, uint64_t pattern) {

-    size_t n = (self->size + 63) >> 6;

+STC_INLINE void cbits_set_values(cbits *self, const uint64_t pattern) {

+    size_t n = _cbits_words(self->size);

     for (size_t i=0; i<n; ++i) self->data64[i] = pattern;

 }

 

 STC_INLINE void cbits_flip_all(cbits *self) {

-    size_t n = (self->size + 63) >> 6;

+    size_t n = _cbits_words(self->size);

     for (size_t i=0; i<n; ++i) self->data64[i] ^= ~(uint64_t)0;

 }

 

 /* Intersection */

 STC_INLINE void cbits_intersect(cbits *self, cbits other) {

     assert(self->size == other.size);

-    size_t n = (self->size + 63) >> 6;

+    size_t n = _cbits_words(self->size);

     for (size_t i=0; i<n; ++i) self->data64[i] &= other.data64[i];

 }

 /* Union */

 STC_INLINE void cbits_union(cbits *self, cbits other) {

     assert(self->size == other.size);

-    size_t n = (self->size + 63) >> 6;

+    size_t n = _cbits_words(self->size);

     for (size_t i=0; i<n; ++i) self->data64[i] |= other.data64[i];

 }

 /* Exclusive disjunction */

 STC_INLINE void cbits_xor(cbits *self, cbits other) {

     assert(self->size == other.size);

-    size_t n = (self->size + 63) >> 6;

+    size_t n = _cbits_words(self->size);

     for (size_t i=0; i<n; ++i) self->data64[i] ^= other.data64[i];

 }

 

@@ -168,12 +170,12 @@ STC_INLINE void cbits_xor(cbits *self, cbits other) {
 STC_DEF cbits* cbits_copy(cbits* self, cbits other) {

     if (self->data64 == other.data64) return self;

     if (self->size != other.size) return cbits_take(self, cbits_clone(other));

-    memcpy(self->data64, other.data64, ((other.size + 63) >> 6) * 8);

+    memcpy(self->data64, other.data64, _cbits_bytes(other.size));

     return self;

 }

 

-STC_DEF void cbits_resize(cbits* self, size_t size, bool value) {

-    size_t new_n = (size + 63) >> 6, osize = self->size, old_n = (osize + 63) >> 6;

+STC_DEF void cbits_resize(cbits* self, const size_t size, const bool value) {

+    const size_t new_n = _cbits_words(size), osize = self->size, old_n = _cbits_words(osize);

     self->data64 = (uint64_t *) c_realloc(self->data64, new_n * 8);

     self->size = size;

     if (new_n >= old_n) {

@@ -185,17 +187,17 @@ STC_DEF void cbits_resize(cbits* self, size_t size, bool value) {
     }

 }

 

-STC_DEF cbits cbits_with_size(size_t size, bool value) {

-    cbits set = {(uint64_t *) c_malloc(((size + 63) >> 6) * 8), size};

+STC_DEF cbits cbits_with_size(const size_t size, const bool value) {

+    cbits set = {(uint64_t *) c_malloc(_cbits_bytes(size)), size};

     cbits_set_all(&set, value);

     return set;

 }

-STC_DEF cbits cbits_with_values(size_t size, uint64_t pattern) {

-    cbits set = {(uint64_t *) c_malloc(((size + 63) >> 6) * 8), size};

+STC_DEF cbits cbits_with_values(const size_t size, const uint64_t pattern) {

+    cbits set = {(uint64_t *) c_malloc(_cbits_bytes(size)), size};

     cbits_set_values(&set, pattern);

     return set;

 }

-STC_DEF cbits cbits_from_n(const char* str, size_t n) {

+STC_DEF cbits cbits_from_n(const char* str, const size_t n) {

     cbits set = cbits_with_size(n, false);

     for (size_t i=0; i<set.size; ++i)

         if (str[i] == '1') cbits_set(&set, i);

@@ -210,7 +212,7 @@ STC_DEF char* cbits_to_str(cbits set, char* out, size_t start, intptr_t stop) {
     return out;

 }

 STC_DEF cbits cbits_clone(cbits other) {

-    size_t bytes = ((other.size + 63) >> 6) * 8;

+    const size_t bytes = _cbits_bytes(other.size);

     cbits set = {(uint64_t *) memcpy(c_malloc(bytes), other.data64, bytes), other.size};

     return set;

 }

@@ -221,18 +223,18 @@ STC_DEF size_t cbits_count(cbits s) {
     return count;

 }

 

-#define _cbits_SETOP(OPR, x) \

+#define _cbits_OPR(OPR, VAL) \

     assert(s.size == other.size); \

-    size_t n = s.size >> 6; \

+    const size_t n = s.size >> 6; \

     for (size_t i = 0; i < n; ++i) \

-        if ((s.data64[i] OPR other.data64[i]) != x) \

+        if ((s.data64[i] OPR other.data64[i]) != VAL) \

             return false; \

     if (!(s.size & 63)) return true; \

-    uint64_t i = n, m = _cbits_bit(s.size) - 1; \

-    return ((s.data64[i] OPR other.data64[i]) & m) == (x & m)

+    const uint64_t i = n, m = _cbits_bit(s.size) - 1; \

+    return ((s.data64[i] OPR other.data64[i]) & m) == (VAL & m)

 

-STC_DEF bool cbits_subset_of(cbits s, cbits other) { _cbits_SETOP(|, s.data64[i]); }

-STC_DEF bool cbits_disjoint(cbits s, cbits other) { _cbits_SETOP(&, 0); }

+STC_DEF bool cbits_subset_of(cbits s, cbits other) { _cbits_OPR(|, s.data64[i]); }

+STC_DEF bool cbits_disjoint(cbits s, cbits other) { _cbits_OPR(&, 0); }

 

 #endif

 #endif