Added possibility to have per container-instance customizable compare/lookup functions (cmp, less, eq, hash) for priority queue and associative containers. Is achived by embedding the container in a struct along with function pointer(s) which can be accessed through the c_container_of() macro. See the updated cpque.c example in the examples folder.

4 files changed, 84 insertions, 43 deletions

diff --git a/examples/cpque.c b/examples/cpque.c
index 5866f17b..502a8c7b 100644
--- a/examples/cpque.c
+++ b/examples/cpque.c
@@ -1,24 +1,40 @@
 // Implements c++ example: https://en.cppreference.com/w/cpp/container/priority_queue
+// Example of dynamic compare function
+
 #include <stdio.h>
 #include <stdbool.h>
+#include <stc/forward.h>
+#include <stc/views.h>
 
-// Example of dynamic compare function
+// predeclare
+declare_cpque(ipque, int);
 
-static bool (*less_fn)(const int* x, const int* y);
+struct {
+    ipque Q;
+    bool (*less)(const int*, const int*);
+} typedef IPQueue;
 
-#define i_val int
-#define i_less less_fn
 #define i_type ipque
+#define i_val int
+#define i_opt c_declared // avoid redeclaring container type
+#define i_less_functor(self, x, y) c_container_of(self, IPQueue, Q)->less(x, y) // <== This.
 #include <stc/cpque.h>
 
-void print_queue(ipque q) {
-    ipque copy = ipque_clone(q);
-    while (!ipque_empty(&copy)) {
-        printf("%d ", *ipque_top(&copy));
-        ipque_pop(&copy);
-    }
+#define print(name, q, n) do { \
+    printf("%s: \t", name); \
+    c_forrange (i, n) printf("%d ", q[i]); \
+    puts(""); \
+} while(0)
+
+void print_queue(const char* name, IPQueue q) {
+    // NB: make a copy because there is no way to traverse
+    // priority_queue's content without erasing the queue.
+    IPQueue copy = {ipque_clone(q.Q), q.less};
+    
+    for (printf("%s: \t", name); !ipque_empty(&copy.Q); ipque_pop(&copy.Q))
+        printf("%d ", *ipque_top(&copy.Q));
     puts("");
-    ipque_drop(&copy);
+    ipque_drop(&copy.Q);
 }
 
 static bool int_less(const int* x, const int* y) { return *x < *y; }
@@ -28,18 +44,29 @@ static bool int_lambda(const int* x, const int* y) { return (*x ^ 1) < (*y ^ 1);
 int main()
 {
     const int data[] = {1,8,5,6,3,4,0,9,7,2}, n = c_arraylen(data);
-    c_auto (ipque, q, q2, q3)  // init() and defered drop()
-    {
-        less_fn = int_less;
-        c_forrange (i, n) ipque_push(&q, data[i]);
-        print_queue(q);
-
-        less_fn = int_greater;
-        c_forrange (i, n) ipque_push(&q2, data[i]);
-        print_queue(q2);
-
-        less_fn = int_lambda;
-        c_forrange (i, n) ipque_push(&q3, data[i]);
-        print_queue(q3);
-    }
+    print("data", data, n);
+
+    IPQueue q1 = {ipque_init(), int_less};  // Max priority queue
+
+    c_forrange (i, n)
+        ipque_push(&q1.Q, data[i]);
+
+    print_queue("q1", q1);
+
+    // Min priority queue
+    // std::greater<int> makes the max priority queue act as a min priority queue
+    IPQueue minq1 = {ipque_init(), int_greater};
+    c_forrange (i, n) ipque_push(&minq1.Q, data[i]);
+
+    print_queue("minq1", minq1);
+
+    // Using lambda to compare elements.
+    IPQueue q5 = {ipque_init(), int_lambda};
+
+    c_forrange (i, n)
+        ipque_push(&q5.Q, data[i]);
+    
+    print_queue("q5", q5);
+
+    c_drop(ipque, &q1.Q, &minq1.Q, &q5.Q);
 }
diff --git a/include/stc/cmap.h b/include/stc/cmap.h
index 95dfadae..3683b357 100644
--- a/include/stc/cmap.h
+++ b/include/stc/cmap.h
@@ -74,6 +74,12 @@ typedef struct      { size_t idx; uint8_t hx; } chash_bucket_t;
   #define i_max_load_factor 0.85f
 #endif
 #include "template.h"
+#ifndef i_hash_functor
+  #define i_hash_functor(self, x) i_hash(x)
+#endif
+#ifndef i_eq_functor
+  #define i_eq_functor(self, x, y) i_eq(x, y)
+#endif
 #if !c_option(c_declared)
   _cx_deftypes(_c_chash_types, _cx_self, i_key, i_val, i_size, _i_MAP_ONLY, _i_SET_ONLY);
 #endif
@@ -330,14 +336,14 @@ STC_DEF void _cx_memb(_clear)(_cx_self* self) {
 
 STC_DEF chash_bucket_t
 _cx_memb(_bucket_)(const _cx_self* self, const _cx_rawkey* rkeyptr) {
-    const uint64_t _hash = i_hash(rkeyptr);
+    const uint64_t _hash = i_hash_functor(self, rkeyptr);
     i_size _cap = self->bucket_count;
     chash_bucket_t b = {c_paste(fastrange_,_i_expandby)(_hash, _cap), (uint8_t)(_hash | 0x80)};
     const uint8_t* _hx = self->_hashx;
     while (_hx[b.idx]) {
         if (_hx[b.idx] == b.hx) {
             const _cx_rawkey _raw = i_keyto(_i_keyref(self->table + b.idx));
-            if (i_eq((&_raw), rkeyptr))
+            if (i_eq_functor(self, (&_raw), rkeyptr))
                 break;
         }
         if (++b.idx == _cap)
@@ -425,7 +431,7 @@ _cx_memb(_erase_entry)(_cx_self* self, _cx_value* _val) {
         if (! _hashx[j])
             break;
         const _cx_rawkey _raw = i_keyto(_i_keyref(_slot + j));
-        k = c_paste(fastrange_,_i_expandby)(i_hash((&_raw)), _cap);
+        k = c_paste(fastrange_,_i_expandby)(i_hash_functor(self, (&_raw)), _cap);
         if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */
             _slot[i] = _slot[j], _hashx[i] = _hashx[j], i = j;
     }
@@ -435,6 +441,8 @@ _cx_memb(_erase_entry)(_cx_self* self, _cx_value* _val) {
 
 #endif // i_implement
 #undef i_max_load_factor
+#undef i_hash_functor
+#undef i_eq_functor
 #undef _i_isset
 #undef _i_ismap
 #undef _i_ishash
diff --git a/include/stc/cpque.h b/include/stc/cpque.h
index af64d553..fbeafcc3 100644
--- a/include/stc/cpque.h
+++ b/include/stc/cpque.h
@@ -32,9 +32,11 @@
 #endif
 
 #include "template.h"
-
+#ifndef i_less_functor
+  #define i_less_functor(self, x, y) i_less(x, y)
+#endif
 #if !c_option(c_declared)
-   _cx_deftypes(_c_cpque_types, _cx_self, i_key);
+  _cx_deftypes(_c_cpque_types, _cx_self, i_key);
 #endif
 typedef i_keyraw _cx_raw;
 
@@ -109,10 +111,11 @@ STC_INLINE void _cx_memb(_emplace)(_cx_self* self, _cx_raw raw)
 #if defined(i_implement)
 
 STC_DEF void
-_cx_memb(_sift_down_)(_cx_value* arr, const size_t idx, const size_t n) {
+_cx_memb(_sift_down_)(_cx_self* self, const size_t idx, const size_t n) {
+    _cx_value* arr = self->data - 1; 
     for (size_t r = idx, c = idx*2; c <= n; c *= 2) {
-        c += (c < n && (i_less((&arr[c]), (&arr[c + 1]))));
-        if (!(i_less((&arr[r]), (&arr[c])))) return;
+        c += (c < n && (i_less_functor(self, (&arr[c]), (&arr[c + 1]))));
+        if (!(i_less_functor(self, (&arr[r]), (&arr[c])))) return;
         _cx_value t = arr[r]; arr[r] = arr[c]; arr[r = c] = t;
     }
 }
@@ -120,9 +123,8 @@ _cx_memb(_sift_down_)(_cx_value* arr, const size_t idx, const size_t n) {
 STC_DEF void
 _cx_memb(_make_heap)(_cx_self* self) {
     size_t n = self->_len;
-    _cx_value *arr = self->data - 1;
     for (size_t k = n/2; k != 0; --k)
-        _cx_memb(_sift_down_)(arr, k, n);
+        _cx_memb(_sift_down_)(self, k, n);
 }
 
 #if !defined _i_no_clone
@@ -139,7 +141,7 @@ _cx_memb(_erase_at)(_cx_self* self, const size_t idx) {
     i_keydrop((self->data + idx));
     const size_t n = --self->_len;
     self->data[idx] = self->data[n];
-    _cx_memb(_sift_down_)(self->data - 1, idx + 1, n);
+    _cx_memb(_sift_down_)(self, idx + 1, n);
 }
 
 STC_DEF void
@@ -148,11 +150,12 @@ _cx_memb(_push)(_cx_self* self, _cx_value value) {
         _cx_memb(_reserve)(self, self->_len*3/2 + 4);
     _cx_value *arr = self->data - 1; /* base 1 */
     size_t c = ++self->_len;
-    for (; c > 1 && (i_less((&arr[c/2]), (&value))); c /= 2)
+    for (; c > 1 && (i_less_functor(self, (&arr[c/2]), (&value))); c /= 2)
         arr[c] = arr[c/2];
     arr[c] = value;
 }
 
 #endif
 #define CPQUE_H_INCLUDED
+#undef i_less_functor
 #include "template.h"
diff --git a/include/stc/csmap.h b/include/stc/csmap.h
index cea60851..aced3f2a 100644
--- a/include/stc/csmap.h
+++ b/include/stc/csmap.h
@@ -74,9 +74,11 @@ int main(void) {
   #define _i_keyref(vp) (&(vp)->first)
 #endif
 #include "template.h"
-
+#ifndef i_cmp_functor
+  #define i_cmp_functor(self, x, y) i_cmp(x, y)
+#endif
 #if !c_option(c_declared)
-_cx_deftypes(_c_aatree_types, _cx_self, i_key, i_val, i_size, _i_MAP_ONLY, _i_SET_ONLY);
+  _cx_deftypes(_c_aatree_types, _cx_self, i_key, i_val, i_size, _i_MAP_ONLY, _i_SET_ONLY);
 #endif
 
 _i_MAP_ONLY( struct _cx_value {
@@ -150,7 +152,7 @@ STC_INLINE int
 _cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y) {
     const _cx_rawkey rx = i_keyto(_i_keyref(x));
     const _cx_rawkey ry = i_keyto(_i_keyref(y));
-    return i_cmp((&rx), (&ry));
+    return i_cmp_functor(self, (&rx), (&ry));
 }
 
 STC_INLINE void
@@ -337,7 +339,7 @@ _cx_memb(_find_it)(const _cx_self* self, _cx_rawkey rkey, _cx_iter* out) {
     out->_top = 0;
     while (tn) {
         int c; const _cx_rawkey raw = i_keyto(_i_keyref(&d[tn].value));
-        if ((c = i_cmp((&raw), (&rkey))) < 0)
+        if ((c = i_cmp_functor(self, (&raw), (&rkey))) < 0)
             tn = d[tn].link[1];
         else if (c > 0)
             { out->_st[out->_top++] = tn; tn = d[tn].link[0]; }
@@ -405,7 +407,7 @@ _cx_memb(_insert_entry_i_)(_cx_self* self, i_size tn, const _cx_rawkey* rkey, _c
     while (tx) {
         up[top++] = tx;
         const _cx_rawkey raw = i_keyto(_i_keyref(&d[tx].value));
-        if (!(c = i_cmp((&raw), rkey)))
+        if (!(c = i_cmp_functor(self, (&raw), rkey)))
             { res->ref = &d[tx].value; return tn; }
         dir = (c < 0);
         tx = d[tx].link[dir];
@@ -443,7 +445,7 @@ _cx_memb(_erase_r_)(_cx_self *self, i_size tn, const _cx_rawkey* rkey, int *eras
     if (tn == 0)
         return 0;
     _cx_rawkey raw = i_keyto(_i_keyref(&d[tn].value));
-    i_size tx; int c = i_cmp((&raw), rkey);
+    i_size tx; int c = i_cmp_functor(self, (&raw), rkey);
     if (c != 0)
         d[tn].link[c < 0] = _cx_memb(_erase_r_)(self, d[tn].link[c < 0], rkey, erased);
     else {
@@ -573,6 +575,7 @@ _cx_memb(_drop)(_cx_self* self) {
 }
 
 #endif // i_implement
+#undef i_cmp_functor
 #undef _i_isset
 #undef _i_ismap
 #undef _i_keyref