Fixed a minor API mixup, Docs: open addressing/closed hashing..

7 files changed, 80 insertions, 55 deletions

diff --git a/README.md b/README.md
index 9e19fca4..30eb2096 100644
--- a/README.md
+++ b/README.md
@@ -62,9 +62,14 @@ And with multiple containers...
 

 struct Point { float x, y; };

 

-// declare your container types

+int Point_compare(const struct Point* a, const struct Point* b) {

+    if (a->x != b->x) return 1 - 2*(a->x < b->x);

+    return (a->y > b->y) - (a->y < b->y);

+}

+

+// declare container types

 using_cset(i, int);                         // unordered set

-using_cvec(p, struct Point, c_no_compare);  // vector, struct as elements

+using_cvec(p, struct Point, Point_compare); // vector, struct as elements

 using_cdeq(i, int);                         // deque

 using_clist(i, int);                        // singly linked list

 using_cqueue(i, cdeq_i);                    // queue, using deque as adapter

@@ -79,7 +84,7 @@ int main(void) {
     c_init (cqueue_i, que, {10, 20, 30});

     c_init (csmap_i, map, { {20, 2}, {10, 1}, {30, 3} });

 

-    // add one more element

+    // add one more element to each container

     cset_i_insert(&set, 40);

     cvec_p_push_back(&vec, (struct Point) {40, 4});

     cdeq_i_push_front(&deq, 5);

@@ -87,13 +92,28 @@ int main(void) {
     cqueue_i_push(&que, 40);

     csmap_i_emplace(&map, 40, 4);

 

-    // print them

-    c_foreach (i, cset_i, set) printf(" %d", *i.ref); puts("");

-    c_foreach (i, cvec_p, vec) printf(" (%g, %g)", i.ref->x, i.ref->y); puts("");

-    c_foreach (i, cdeq_i, deq) printf(" %d", *i.ref); puts("");

-    c_foreach (i, clist_i, lst) printf(" %d", *i.ref); puts("");

-    c_foreach (i, cqueue_i, que) printf(" %d", *i.ref); puts("");

-    c_foreach (i, csmap_i, map) printf(" [%d: %d]", i.ref->first, i.ref->second);

+    // find an element in each container

+    cset_i_iter_t i1 = cset_i_find(&set, 20);

+    cvec_p_iter_t i2 = cvec_p_find(&vec, (struct Point) {20, 2});

+    cdeq_i_iter_t i3 = cdeq_i_find(&deq, 20);

+    clist_i_iter_t i4 = clist_i_find_before(&lst, 20);

+    csmap_i_iter_t i5 = csmap_i_find(&map, 20);

+    printf("\nFound: %d, (%g, %g), %d, %d, [%d: %d]\n", *i1.ref, i2.ref->x, i2.ref->y, *i3.ref,

+                                                        *clist_i_fwd(i4, 1).ref, i5.ref->first, i5.ref->second);

+    // erase the elements found

+    cset_i_erase_at(&set, i1);

+    cvec_p_erase_at(&vec, i2);

+    cdeq_i_erase_at(&deq, i3);

+    clist_i_erase_after(&lst, i4);

+    csmap_i_erase_at(&map, i5);

+

+    printf("After erasing elements found:");

+    printf("\n set:"); c_foreach (i, cset_i, set) printf(" %d", *i.ref);

+    printf("\n vec:"); c_foreach (i, cvec_p, vec) printf(" (%g, %g)", i.ref->x, i.ref->y);

+    printf("\n deq:"); c_foreach (i, cdeq_i, deq) printf(" %d", *i.ref);

+    printf("\n lst:"); c_foreach (i, clist_i, lst) printf(" %d", *i.ref);

+    printf("\n que:"); c_foreach (i, cqueue_i, que) printf(" %d", *i.ref);

+    printf("\n map:"); c_foreach (i, csmap_i, map) printf(" [%d: %d]", i.ref->first, i.ref->second);

 

     // cleanup

     cset_i_del(&set);

@@ -104,24 +124,26 @@ int main(void) {
     csmap_i_del(&map);

 }

 ```

-Outputs

+Output

 ```

- 10 20 30 40

- (10, 1) (20, 2) (30, 3) (40, 4)

- 5 10 20 30

- 5 10 20 30

- 10 20 30 40

- [10: 1] [20: 2] [30: 3] [40: 4]

+Found: 20, (20, 2), 20, 20, [20: 2]

+After erasing elements found:

+ set: 10 30 40

+ vec: (10, 1) (30, 3) (40, 4)

+ deq: 5 10 30

+ lst: 5 10 30

+ que: 10 20 30 40

+ map: [10: 1] [30: 3] [40: 4]

 ```

 

 Highlights

 ----------

-- **Friendly** - Incredible easy to use and deploy. The ***using_***-declaration instantiates the container type to use. You may pass *optional* arguments for customization of value- *comparison*, *destruction*, *cloning*, *convertion types*, and more. Most methods have similar named corresponding methods in STL.

-- **Extreme Performance** - The associative containers **cmap** and **cset** are roughly ***5 times faster than the STL equivalents***, *std::unordered_map* and *std::unordered_set*! **csmap** and **csset** are more than 20% faster in general  than *std::unordered_map/set* See *Performance*. Also **cdeq** are in some cases significantly faster than *std::deque*, however implementations vary between different c++ compilers.

-- **Type Safety** - No error prone casting of container types and elements back and forth from your containers. Less obscure bugs in your code. The compiler will let you know when retrieving or passing wrong container or element types to the methods.

+- **User friendly** - Incredible easy to use and deploy. The ***using_***-declaration instantiates the container type to use. You may pass *optional* arguments for customization of value- *comparison*, *destruction*, *cloning*, *convertion types*, and more. Most methods have similar named corresponding methods in STL.

+- **Extreme performance** - The associative containers **cmap** and **cset** are more than ***4 times faster than c++ STL equivalents***, *std::unordered_map* and *std::unordered_set*! **csmap** and **csset** are more than 20% faster than *std::unordered_map/set* Also **cdeq** is significantly faster than *std::deque* in most cases, however implementations vary between different c++ compilers. See *Performance*.

+- **Full type safety** - No error prone casting of container types and elements back and forth from your containers. Less obscure bugs in your code. The compiler will let you know when retrieving or passing wrong container or element types to the methods.

 - **Uniform API** - Methods to ***construct***, ***initialize***, ***iterate*** and ***destruct*** are intuitive and uniform across the various containers, as can be seen from the example above.

-- **Small Footprint** - Both source code and generated executables are small. The executable from the above example with six different containers is *18 kb in size*, when compiled with TinyC.

-- **Dual Mode Compilation** - Can be used a simple header-only library with static methods (default), or as a traditional library by defining symbol STC_HEADER in your project. See below for instructions.

+- **Small footprint** - Both source code and generated executables are small. The executable from the above example with six different containers is *18 kb in size*, when compiled with TinyC.

+- **Dual mode compilation** - Can be used a simple header-only library with static methods (default), or as a traditional library by defining symbol STC_HEADER in your project. See below for instructions.

 

 Installation

 ------------

@@ -208,14 +230,14 @@ The containers are memory efficent, i.e. they occupy as little memory as practic
 - **cstr**, **cvec**: Type size: one pointer. The size and capacity is stored as part of the heap allocation that also holds the vector elements.

 - **clist**: Type size: one pointer. Each node allocates block storing value and next pointer.

 - **cdeq**:  Type size: two pointers. Otherwise equal to cvec.

-- **cmap**: Type size: 4 pointers. cmap uses one table of keys+value, and one table of precomputed hash-value/used bucket, which occupies only one byte per bucket. The open hashing has a default max load factor of 85%, and hash table scales by 1.5x when reaching that.

+- **cmap**: Type size: 4 pointers. cmap uses one table of keys+value, and one table of precomputed hash-value/used bucket, which occupies only one byte per bucket. The closed hashing has a default max load factor of 85%, and hash table scales by 1.5x when reaching that.

 - **cset**: Same as cmap, but this uses a table of keys only, not (key, value) pairs.

 - **carray**: carray1, carray2 and carray3. Type size: One pointer plus one, two, or three size_t variables to store dimensions. Arrays are allocated as one contiguous block of heap memory.

 

 More on **cmap**

 ----------------

 

-**cmap** uses open hashing, and default max load-factor is 0.85.

+**cmap** uses closed hashing, and default max load-factor is 0.85.

 

 You can customize the destroy-, hash-, equals- functions, but also define a convertion from a raw/literal type to the key-type specified. This is very useful when e.g. having cstr as key, and therefore a few using-macros are pre-defined

 for **cmap** with **cstr** keys and/or values:

diff --git a/benchmarks/cdeq_benchmark.cpp b/benchmarks/cdeq_benchmark.cpp
index b56c5c38..6211afa5 100644
--- a/benchmarks/cdeq_benchmark.cpp
+++ b/benchmarks/cdeq_benchmark.cpp
@@ -5,6 +5,9 @@
 #include <stc/cdeq.h>

 #include <stc/crandom.h>

 

+static float secs(time_t t1, time_t t2) { return (float)(t2 - t1) / CLOCKS_PER_SEC; }

+

+

 enum {N = 1000000000, M = 12345, P = 5000, R = 2000};

 using_cdeq(i, int);

 

diff --git a/docs/cmap_api.md b/docs/cmap_api.md
index 61441fb7..c57dc38f 100644
--- a/docs/cmap_api.md
+++ b/docs/cmap_api.md
@@ -2,7 +2,7 @@
 ![Map](pics/map.jpg)
 
 A **cmap** is an associative container that contains key-value pairs with unique keys. Search, insertion,
-and removal of elements have average constant-time complexity. Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. This allows fast access to individual elements, since once the hash is computed, it refers to the exact bucket the element is placed into. It is implemented as open hashing with linear probing, and without leaving tombstones on erase.
+and removal of elements have average constant-time complexity. Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. This allows fast access to individual elements, since once the hash is computed, it refers to the exact bucket the element is placed into. It is implemented as closed hashing (aka open addressing) with linear probing, and without leaving tombstones on erase.
 
 See the c++ class [std::unordered_map](https://en.cppreference.com/w/cpp/container/unordered_map) for a functional description.
 
diff --git a/stc/cdeq.h b/stc/cdeq.h
index 29bb72fa..2ce7d398 100644
--- a/stc/cdeq.h
+++ b/stc/cdeq.h
@@ -149,11 +149,11 @@
         return cdeq_##X##_erase_range_p(self, first.ref, finish.ref); \

     } \

     STC_INLINE cdeq_##X##_iter_t \

-    cdeq_##X##_erase(cdeq_##X* self, cdeq_##X##_iter_t pos) { \

+    cdeq_##X##_erase_at(cdeq_##X* self, cdeq_##X##_iter_t pos) { \

         return cdeq_##X##_erase_range_p(self, pos.ref, pos.ref + 1); \

     } \

     STC_INLINE cdeq_##X##_iter_t \

-    cdeq_##X##_erase_at(cdeq_##X* self, size_t idx, size_t n) { \

+    cdeq_##X##_erase(cdeq_##X* self, size_t idx, size_t n) { \

         return cdeq_##X##_erase_range_p(self, self->data + idx, self->data + idx + n); \

     } \

 \

diff --git a/stc/cmap.h b/stc/cmap.h
index f1d7f291..888718d4 100644
--- a/stc/cmap.h
+++ b/stc/cmap.h
@@ -23,7 +23,7 @@
 #ifndef CMAP__H__

 #define CMAP__H__

 

-// Unordered set/map - implemented as open hashing with linear probing and no tombstones.

+// Unordered set/map - implemented as closed hashing with linear probing and no tombstones.

 /*

 #include <stdio.h>

 #include <stc/cmap.h>

@@ -433,8 +433,8 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t;
         C##_##X##_value_t* slot = self->table; \

         uint8_t* hashx = self->_hashx; \

         C##_##X##_entry_del(&slot[i]); \

-        do { /* deletion from hash table without tombstone */ \

-            if (++j == cap) j = 0; /* ++j; j %= cap; is slow */ \

+        do { /* delete without leaving tombstone */ \

+            if (++j == cap) j = 0; \

             if (! hashx[j]) \

                 break; \

             RawKey r = keyToRaw(KEY_REF_##C(slot + j)); \

diff --git a/stc/cset.h b/stc/cset.h
index 2b85edfc..e025bb45 100644
--- a/stc/cset.h
+++ b/stc/cset.h
@@ -23,7 +23,7 @@
 #ifndef CSET__H__

 #define CSET__H__

 

-// Unordered set - implemented as open hashing with linear probing and no tombstones.

+// Unordered set - implemented as closed hashing with linear probing and no tombstones.

 

 #include "cmap.h"

 

diff --git a/stc/csmap.h b/stc/csmap.h
index 978578de..3755e2ca 100644
--- a/stc/csmap.h
+++ b/stc/csmap.h
@@ -61,8 +61,8 @@ int main(void) {
 

 #define using_csmap_10(X, Key, Mapped, keyCompareRaw, mappedDel, mappedClone, \

                           keyDel, keyFromRaw, keyToRaw, RawKey) \

-    _using_CBST(X, csmap, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \

-                   keyFromRaw, keyToRaw, RawKey, mappedClone, c_default_to_raw, Mapped)

+    _using_AATREE(X, csmap, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \

+                     keyFromRaw, keyToRaw, RawKey, mappedClone, c_default_to_raw, Mapped)

 

 /* csset: */

 #define using_csset(...) \

@@ -78,28 +78,28 @@ int main(void) {
     using_csset_7(X, Key, keyCompare, keyDel, keyClone, c_default_to_raw, Key)

 

 #define using_csset_7(X, Key, keyCompareRaw, keyDel, keyFromRaw, keyToRaw, RawKey) \

-    _using_CBST(X, csset, Key, Key, keyCompareRaw, _UNUSED_, keyDel, \

-                   keyFromRaw, keyToRaw, RawKey, _UNUSED_, _UNUSED_, void)

+    _using_AATREE(X, csset, Key, Key, keyCompareRaw, _UNUSED_, keyDel, \

+                     keyFromRaw, keyToRaw, RawKey, _UNUSED_, _UNUSED_, void)

 

 /* csset_str, csmap_str, csmap_strkey, csmap_strval: */

 #define using_csset_str() \

-    _using_CBST_strkey(str, csset, cstr_t, _UNUSED_, _UNUSED_)

+    _using_AATREE_strkey(str, csset, cstr_t, _UNUSED_, _UNUSED_)

 #define using_csmap_str() \

-    _using_CBST(str, csmap, cstr_t, cstr_t, cstr_compare_raw, cstr_del, cstr_del, \

+    _using_AATREE(str, csmap, cstr_t, cstr_t, cstr_compare_raw, cstr_del, cstr_del, \

                      cstr_from, cstr_to_raw, const char*, cstr_from, cstr_to_raw, const char*)

 

 #define using_csmap_strkey(...) \

     c_MACRO_OVERLOAD(using_csmap_strkey, __VA_ARGS__)

 

 #define using_csmap_strkey_2(X, Mapped) \

-    _using_CBST_strkey(X, csmap, Mapped, c_default_del, c_default_clone)

+    _using_AATREE_strkey(X, csmap, Mapped, c_default_del, c_default_clone)

 

 #define using_csmap_strkey_4(X, Mapped, mappedDel, mappedClone) \

-    _using_CBST_strkey(X, csmap, Mapped, mappedDel, mappedClone)

+    _using_AATREE_strkey(X, csmap, Mapped, mappedDel, mappedClone)

 

-#define _using_CBST_strkey(X, C, Mapped, mappedDel, mappedClone) \

-    _using_CBST(X, C, cstr_t, Mapped, cstr_compare_raw, mappedDel, cstr_del, \

-                   cstr_from, cstr_to_raw, const char*, mappedClone, c_default_to_raw, Mapped)

+#define _using_AATREE_strkey(X, C, Mapped, mappedDel, mappedClone) \

+    _using_AATREE(X, C, cstr_t, Mapped, cstr_compare_raw, mappedDel, cstr_del, \

+                     cstr_from, cstr_to_raw, const char*, mappedClone, c_default_to_raw, Mapped)

 

 #define using_csmap_strval(...) \

     c_MACRO_OVERLOAD(using_csmap_strval, __VA_ARGS__)

@@ -114,8 +114,8 @@ int main(void) {
     using_csmap_strval_7(X, Key, keyCompare, keyDel, keyClone, c_default_to_raw, Key)

 

 #define using_csmap_strval_7(X, Key, keyCompare, keyDel, keyFromRaw, keyToRaw, RawKey) \

-    _using_CBST(X, csmap, Key, cstr_t, keyCompare, cstr_del, keyDel, \

-                   keyFromRaw, keyToRaw, RawKey, cstr_from, cstr_to_raw, const char*)

+    _using_AATREE(X, csmap, Key, cstr_t, keyCompare, cstr_del, keyDel, \

+                     keyFromRaw, keyToRaw, RawKey, cstr_from, cstr_to_raw, const char*)

 

 #define SET_ONLY_csset(...) __VA_ARGS__

 #define SET_ONLY_csmap(...)

@@ -127,7 +127,7 @@ int main(void) {
 #define CSMAP_SIZE_T uint32_t

 #endif

 

-#define _using_CBST_types(X, C, Key, Mapped) \

+#define _using_AATREE_types(X, C, Key, Mapped) \

     typedef Key C##_##X##_key_t; \

     typedef Mapped C##_##X##_mapped_t; \

     typedef CSMAP_SIZE_T C##_##X##_size_t; \

@@ -150,9 +150,9 @@ int main(void) {
         C##_##X##_size_t _tn, _st[48]; \

     } C##_##X##_iter_t

 

-#define _using_CBST(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \

-                       keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \

-    _using_CBST_types(X, C, Key, Mapped); \

+#define _using_AATREE(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \

+                         keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \

+    _using_AATREE_types(X, C, Key, Mapped); \

 \

     typedef struct { \

         C##_##X##_node_t* data; \

@@ -286,15 +286,15 @@ int main(void) {
         return C##_##X##_erase(self, keyToRaw(KEY_REF_##C(pos.ref))); \

     } \

 \

-    _implement_CBST(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \

-                       keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \

+    _implement_AATREE(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \

+                         keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \

     typedef C##_##X C##_##X##_t

 

 /* -------------------------- IMPLEMENTATION ------------------------- */

 

 #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION)

-#define _implement_CBST(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \

-                           keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \

+#define _implement_AATREE(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \

+                             keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \

     STC_DEF C##_##X \

     C##_##X##_init(void) { \

         C##_##X m = {(C##_##X##_node_t *) (_smap_inits + 4)}; \

@@ -516,12 +516,12 @@ int main(void) {
         } \

     }

 

-_using_CBST_types(_, csmap, int, int);

+_using_AATREE_types(_, csmap, int, int);

 static size_t _smap_inits[4] = {0, 0, 0, 0};

 

 #else

-#define _implement_CBST(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \

-                           keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped)

+#define _implement_AATREE(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \

+                             keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped)

 #endif

 

 enum {_smap_ROOT=0, _smap_DISP=1, _smap_SIZE=2, _smap_CAP=3};