Internal restructure. Added bsearch() to cvec.

9 files changed, 163 insertions, 169 deletions

diff --git a/docs/cdeq_api.md b/docs/cdeq_api.md
index 09fcb535..d84b9fdf 100644
--- a/docs/cdeq_api.md
+++ b/docs/cdeq_api.md
@@ -1,7 +1,7 @@
 # STC [cdeq](../stc/cdeq.h): Double Ended Queue
 ![Deque](pics/deque.jpg)
 
-A **cdeq** is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. Note that this container is implemented similar to a vector, but has the same performance profile for both *push_back()* and *push_front()* as *cvec_X_push_back()*. Iterators may be invalidated after push-operations.
+A **cdeq** is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. Note that this container is implemented similar to a vector, but has the same performance profile for both *push_back()* and *push_front()* as *cdeq_X_push_back()*. Iterators may be invalidated after push-operations.
 
 See the c++ class [std::deque](https://en.cppreference.com/w/cpp/container/deque) for a functional description.
 
@@ -56,10 +56,6 @@ cdeq_X_value_t*     cdeq_X_at(cdeq_X* self, size_t idx);
 cdeq_X_value_t*     cdeq_X_front(cdeq_X* self);
 cdeq_X_value_t*     cdeq_X_back(cdeq_X* self);
 
-cdeq_X_iter_t       cdeq_X_find(const cdeq_X* self, RawValue raw);
-cdeq_X_iter_t       cdeq_X_find_in_range(const cdeq_X* self,
-                                         cdeq_X_iter_t first, cdeq_X_iter_t finish, RawValue raw);
-
 void                cdeq_X_push_front(cdeq_X* self, Value value);
 void                cdeq_X_push_back(cdeq_X* self, Value value);
 void                cdeq_X_emplace_front(cdeq_X* self, RawValue raw);
@@ -83,9 +79,11 @@ cdeq_X_iter_t       cdeq_X_erase_at(cdeq_X* self, cdeq_X_iter_t pos);
 cdeq_X_iter_t       cdeq_X_erase_range(cdeq_X* self, cdeq_X_iter_t first, cdeq_X_iter_t finish);
 cdeq_X_iter_t       cdeq_X_erase_range_p(cdeq_X* self, cdeq_X_value_t* pfirst, cdeq_X_value_t* pfinish);
 
+cdeq_X_iter_t       cdeq_X_find(const cdeq_X* self, RawValue raw);
+cdeq_X_iter_t       cdeq_X_find_in_range(cdeq_X_iter_t i1, cdeq_X_iter_t i2, RawValue raw);
 void                cdeq_X_sort(cdeq_X* self);
-void                cdeq_X_sort_with(cdeq_X* self, size_t ifirst, size_t ifinish,
-                                     int(*cmp)(const cdeq_X_value_t*, const cdeq_X_value_t*));
+void                cdeq_X_sort_range(cdeq_X_iter_t i1, cdeq_X_iter_t i2,
+                                      int(*cmp)(const cdeq_X_value_t*, const cdeq_X_value_t*));
 
 cdeq_X_iter_t       cdeq_X_begin(const cdeq_X* self);
 cdeq_X_iter_t       cdeq_X_end(const cdeq_X* self);
diff --git a/docs/cmap_api.md b/docs/cmap_api.md
index 77e4d523..0114a365 100644
--- a/docs/cmap_api.md
+++ b/docs/cmap_api.md
@@ -18,16 +18,16 @@ using_cmap(X, Key, Mapped, keyEqualsRaw, keyHashRaw, mappedDestroy, mappedFromRa
 using_cmap_keyarg(X, Key, Mapped, keyEquals, keyHash, keyDestroy);
 using_cmap_keyarg(X, Key, Mapped, keyEqualsRaw, keyHashRaw, keyDestroy, keyFromRaw, keyToRaw, RawKey);
 
-using_cmap_strkey(X, Mapped);                    // cmap(str, cstr, Mapped, ...)
+using_cmap_strkey(X, Mapped);                    // using_cmap(str, cstr, Mapped, ...)
 using_cmap_strkey(X, Mapped, mappedDestroy);
 using_cmap_strkey(X, Mapped, mappedDestroy, mappedFromRaw, mappedToRaw, RawMapped);
 
-using_cmap_strval(X, Key);                       // cmap(str, Key, cstr, ...)
+using_cmap_strval(X, Key);                       // using_cmap(str, Key, cstr, ...)
 using_cmap_strval(X, Key, keyEquals, keyHash);
 using_cmap_strval(X, Key, keyEquals, keyHash, keyDestroy);
 using_cmap_strval(X, Key, keyEqualsRaw, keyHashRaw, keyDestroy, keyFromRaw, keyToRaw, RawKey);
 
-using_cmap_str()                                 // cmap(str, cstr, cstr, ...)
+using_cmap_str()                                 // using_cmap(str, cstr, cstr, ...)
 ```
 The `using_cmap()` macro family must be instantiated in the global scope.
 Default values are given above for args not specified. `X` is a type tag name and
@@ -289,13 +289,11 @@ static inline int vikingraw_equals(const VikingRaw* rx, const VikingRaw* ry) {
 static inline Viking viking_fromRaw(VikingRaw raw) { // note: parameter is by value
     Viking vk = {cstr_from(raw.name), cstr_from(raw.country)}; return vk;
 }
-
 static inline VikingRaw viking_toRaw(Viking* vk) {
     VikingRaw raw = {vk->name.str, vk->country.str}; return raw;
 }
 
 // With this in place, we use the using_cmap_keyarg() macro to define {Viking -> int} hash map type:
-
 using_cmap_keyarg(vk, Viking, int, vikingraw_equals, vikingraw_hash,
                       viking_del, viking_fromRaw, viking_toRaw, VikingRaw);
 
diff --git a/docs/csmap_api.md b/docs/csmap_api.md
index f7f650fa..402ac2bf 100644
--- a/docs/csmap_api.md
+++ b/docs/csmap_api.md
@@ -17,16 +17,16 @@ using_csmap(X, Key, Mapped, keyCompareRaw, mappedDestroy, mappedFromRaw, mappedT
 using_csmap_keyarg(X, Key, Mapped, keyCompare, keyDestroy);
 using_csmap_keyarg(X, Key, Mapped, keyCompareRaw, keyDestroy, keyFromRaw, keyToRaw, RawKey);
 
-using_csmap_strkey(X, Mapped);                     // csmap(str, cstr, Mapped, ...)
+using_csmap_strkey(X, Mapped);                    // using_csmap(str, cstr, Mapped, ...)
 using_csmap_strkey(X, Mapped, mappedDestroy);
 using_csmap_strkey(X, Mapped, mappedDestroy, mappedFromRaw, mappedToRaw, RawMapped);
 
-using_csmap_strval(X, Key);                        // csmap(str, Key, cstr, ...)
+using_csmap_strval(X, Key);                       // using_csmap(str, Key, cstr, ...)
 using_csmap_strval(X, Key, keyCompare);
 using_csmap_strval(X, Key, keyCompare, keyDestroy);
 using_csmap_strval(X, Key, keyCompareRaw, keyDestroy, keyFromRaw, keyToRaw, RawKey);
 
-using_csmap_str();                                 // csmap(str, cstr, cstr, ...)
+using_csmap_str();                                // using_csmap(str, cstr, cstr, ...)
 ```
 The `using_csmap()` macro family must be instantiated in the global scope.
 Default values are given above for args not specified. `X` is a type tag name and
diff --git a/docs/cvec_api.md b/docs/cvec_api.md
index 3032c8e0..8bc3e67e 100644
--- a/docs/cvec_api.md
+++ b/docs/cvec_api.md
@@ -81,12 +81,12 @@ cvec_X_iter_t       cvec_X_erase_range(cvec_X* self, cvec_X_iter_t first, cvec_X
 cvec_X_iter_t       cvec_X_erase_range_p(cvec_X* self, cvec_X_value_t* pfirst, cvec_X_value_t* pfinish);
 
 cvec_X_iter_t       cvec_X_find(const cvec_X* self, RawValue raw);
-cvec_X_iter_t       cvec_X_find_in_range(const cvec_X* self,
-                                         cvec_X_iter_t first, cvec_X_iter_t finish, RawValue raw);
-
+cvec_X_iter_t       cvec_X_find_in_range(cvec_X_iter_t i1, cvec_X_iter_t i2, RawValue raw);
+bool                cvec_X_bsearch(const cvec_X* self);
+bool                cvec_X_bsearch_in_range(cvec_X_iter_t i1, cvec_X_iter_t i2, RawValue raw);
 void                cvec_X_sort(cvec_X* self);
-void                cvec_X_sort_with(cvec_X* self, size_t ifirst, size_t ifinish,
-                                     int(*cmp)(const cvec_X_value_t*, const cvec_X_value_t*));
+void                cvec_X_sort_range(cvec_X_iter_t i1, cvec_X_iter_t i2,
+                                      int(*cmp)(const cvec_X_value_t*, const cvec_X_value_t*));
 
 cvec_X_iter_t       cvec_X_begin(const cvec_X* self);
 cvec_X_iter_t       cvec_X_end(const cvec_X* self);
diff --git a/examples/demos.c b/examples/demos.c
index e89c3170..828a2c26 100644
--- a/examples/demos.c
+++ b/examples/demos.c
@@ -57,7 +57,6 @@ void vectordemo1()
 }

 

 

-

 using_cvec_str();

 

 void vectordemo2()

diff --git a/examples/ex_gauss1.c b/examples/ex_gauss1.c
index 85d818d5..8ef08694 100644
--- a/examples/ex_gauss1.c
+++ b/examples/ex_gauss1.c
@@ -1,10 +1,10 @@
 #include <stdio.h>

 #include <time.h>

 #include <math.h>

-#include "stc/crandom.h"

-#include "stc/cstr.h"

-#include "stc/cmap.h"

-#include "stc/cvec.h"

+#include <stc/crandom.h>

+#include <stc/cstr.h>

+#include <stc/cmap.h>

+#include <stc/cvec.h>

 

 // Declare int -> int hashmap. Uses typetag 'i' for ints.

 using_cmap(i, int, size_t);

diff --git a/stc/cdeq.h b/stc/cdeq.h
index 11c391da..0b5ed8d3 100644
--- a/stc/cdeq.h
+++ b/stc/cdeq.h
@@ -46,7 +46,8 @@
     } cdeq_##X

 

 struct cdeq_rep { size_t size, cap; void* base[]; };

-#define _cdeq_rep(self) c_container_of((self)->base, struct cdeq_rep, base)

+#define cdeq_rep_(self) c_container_of((self)->base, struct cdeq_rep, base)

+typedef int (*c_cmp_fn)(const void*, const void*);

 

 #define using_cdeq_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue) \

     typedefs_cdeq(X, Value, RawValue); \

@@ -54,11 +55,11 @@ struct cdeq_rep { size_t size, cap; void* base[]; };
     STC_API cdeq_##X \

     cdeq_##X##_init(void); \

     STC_INLINE bool \

-    cdeq_##X##_empty(cdeq_##X deq) {return !_cdeq_rep(&deq)->size;} \

+    cdeq_##X##_empty(cdeq_##X deq) {return !cdeq_rep_(&deq)->size;} \

     STC_INLINE size_t \

-    cdeq_##X##_size(cdeq_##X deq) {return _cdeq_rep(&deq)->size;} \

+    cdeq_##X##_size(cdeq_##X deq) {return cdeq_rep_(&deq)->size;} \

     STC_INLINE size_t \

-    cdeq_##X##_capacity(cdeq_##X deq) {return _cdeq_rep(&deq)->cap;} \

+    cdeq_##X##_capacity(cdeq_##X deq) {return cdeq_rep_(&deq)->cap;} \

     STC_INLINE Value \

     cdeq_##X##_value_fromraw(RawValue raw) {return valueFromRaw(raw);} \

     STC_INLINE cdeq_##X##_value_t \

@@ -73,7 +74,7 @@ struct cdeq_rep { size_t size, cap; void* base[]; };
     cdeq_##X##_resize(cdeq_##X* self, size_t size, Value fill_val); \

     STC_INLINE void \

     cdeq_##X##_reserve(cdeq_##X* self, size_t n) { \

-        _cdeq_##X##_expand(self, (n - _cdeq_rep(self)->size)*2/3, false); \

+        _cdeq_##X##_expand(self, (n - cdeq_rep_(self)->size)*1.5, false); \

     } \

     STC_INLINE void \

     cdeq_##X##_swap(cdeq_##X* a, cdeq_##X* b) {c_swap(cdeq_##X, *a, *b);} \

@@ -91,7 +92,7 @@ struct cdeq_rep { size_t size, cap; void* base[]; };
         return x; \

     } \

     STC_API cdeq_##X \

-    cdeq_##X##_clone(cdeq_##X vec); \

+    cdeq_##X##_clone(cdeq_##X deq); \

 \

     STC_INLINE void \

     cdeq_##X##_shrink_to_fit(cdeq_##X *self) { \

@@ -109,7 +110,7 @@ struct cdeq_rep { size_t size, cap; void* base[]; };
     } \

     STC_INLINE void \

     cdeq_##X##_pop_back(cdeq_##X* self) { \

-        valueDestroy(&self->data[--_cdeq_rep(self)->size]); \

+        valueDestroy(&self->data[--cdeq_rep_(self)->size]); \

     } \

 \

     STC_API void \

@@ -121,7 +122,7 @@ struct cdeq_rep { size_t size, cap; void* base[]; };
     STC_INLINE void \

     cdeq_##X##_pop_front(cdeq_##X* self) { \

         valueDestroy(self->data++); \

-        --_cdeq_rep(self)->size; \

+        --cdeq_rep_(self)->size; \

     } \

 \

     STC_API cdeq_##X##_iter_t \

@@ -164,39 +165,23 @@ struct cdeq_rep { size_t size, cap; void* base[]; };
         return cdeq_##X##_erase_range_p(self, self->data + idx, self->data + idx + n); \

     } \

 \

-    STC_API cdeq_##X##_iter_t \

-    cdeq_##X##_find(const cdeq_##X* self, RawValue raw); \

-    STC_API cdeq_##X##_iter_t \

-    cdeq_##X##_find_in_range(const cdeq_##X* self, cdeq_##X##_iter_t first, cdeq_##X##_iter_t finish, RawValue raw); \

-\

     STC_INLINE cdeq_##X##_value_t* \

     cdeq_##X##_front(cdeq_##X* self) {return self->data;} \

     STC_INLINE cdeq_##X##_value_t* \

-    cdeq_##X##_back(cdeq_##X* self) {return self->data + _cdeq_rep(self)->size - 1;} \

+    cdeq_##X##_back(cdeq_##X* self) {return self->data + cdeq_rep_(self)->size - 1;} \

     STC_INLINE cdeq_##X##_value_t* \

     cdeq_##X##_at(cdeq_##X* self, size_t i) { \

-        assert(i < _cdeq_rep(self)->size); \

+        assert(i < cdeq_rep_(self)->size); \

         return self->data + i; \

     } \

 \

-    STC_API int \

-    cdeq_##X##_value_compare(const cdeq_##X##_value_t* x, const cdeq_##X##_value_t* y); \

-    STC_INLINE void \

-    cdeq_##X##_sort_with(cdeq_##X* self, size_t ifirst, size_t ifinish, int(*cmp)(const cdeq_##X##_value_t*, const cdeq_##X##_value_t*)) { \

-        qsort(self->data + ifirst, ifinish - ifirst, sizeof(Value), (_cdeq_cmp) cmp); \

-    } \

-    STC_INLINE void \

-    cdeq_##X##_sort(cdeq_##X* self) { \

-        cdeq_##X##_sort_with(self, 0, _cdeq_rep(self)->size, cdeq_##X##_value_compare); \

-    } \

-\

     STC_INLINE cdeq_##X##_iter_t \

     cdeq_##X##_begin(const cdeq_##X* self) { \

         cdeq_##X##_iter_t it = {self->data}; return it; \

     } \

     STC_INLINE cdeq_##X##_iter_t \

     cdeq_##X##_end(const cdeq_##X* self) { \

-        cdeq_##X##_iter_t it = {self->data + _cdeq_rep(self)->size}; return it; \

+        cdeq_##X##_iter_t it = {self->data + cdeq_rep_(self)->size}; return it; \

     } \

     STC_INLINE void \

     cdeq_##X##_next(cdeq_##X##_iter_t* it) {++it->ref;} \

@@ -205,6 +190,23 @@ struct cdeq_rep { size_t size, cap; void* base[]; };
     STC_INLINE size_t \

     cdeq_##X##_index(cdeq_##X deq, cdeq_##X##_iter_t it) {return it.ref - deq.data;} \

 \

+    STC_API cdeq_##X##_iter_t \

+    cdeq_##X##_find_in_range(cdeq_##X##_iter_t first, cdeq_##X##_iter_t finish, RawValue raw); \

+    STC_INLINE cdeq_##X##_iter_t \

+    cdeq_##X##_find(const cdeq_##X* self, RawValue raw) { \

+        return cdeq_##X##_find_in_range(cdeq_##X##_begin(self), cdeq_##X##_end(self), raw); \

+    } \

+    STC_API int \

+    cdeq_##X##_value_compare(const cdeq_##X##_value_t* x, const cdeq_##X##_value_t* y); \

+    STC_INLINE void \

+    cdeq_##X##_sort_range(cdeq_##X##_iter_t i1, cdeq_##X##_iter_t i2, \

+                          int(*cmp)(const cdeq_##X##_value_t*, const cdeq_##X##_value_t*)) { \

+        qsort(i1.ref, i2.ref - i1.ref, sizeof(cdeq_##X##_value_t), (c_cmp_fn) cmp); \

+    } \

+    STC_INLINE void \

+    cdeq_##X##_sort(cdeq_##X* self) { \

+        cdeq_##X##_sort_range(cdeq_##X##_begin(self), cdeq_##X##_end(self), cdeq_##X##_value_compare); \

+    } \

     _c_implement_cdeq_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue) \

     typedef cdeq_##X cdeq_##X##_t

 

@@ -229,14 +231,14 @@ static inline double _maxf(double x, double y) {return x > y ? x : y;}
     cdeq_##X##_emplace_n(cdeq_##X *self, const cdeq_##X##_rawvalue_t arr[], size_t n) { \

         if (!n) return; \

         _cdeq_##X##_expand(self, n, false); \

-        cdeq_##X##_value_t* p = self->data + _cdeq_rep(self)->size; \

+        cdeq_##X##_value_t* p = self->data + cdeq_rep_(self)->size; \

         for (size_t i=0; i < n; ++i) *p++ = valueFromRaw(arr[i]); \

-        _cdeq_rep(self)->size += n; \

+        cdeq_rep_(self)->size += n; \

     } \

 \

     STC_DEF void \

     cdeq_##X##_clear(cdeq_##X* self) { \

-        struct cdeq_rep* rep = _cdeq_rep(self); if (rep->cap) { \

+        struct cdeq_rep* rep = cdeq_rep_(self); if (rep->cap) { \

             for (cdeq_##X##_value_t *p = self->data, *q = p + rep->size; p != q; ++p) \

                 valueDestroy(p); \

             rep->size = 0; \

@@ -245,13 +247,13 @@ static inline double _maxf(double x, double y) {return x > y ? x : y;}
     STC_DEF void \

     cdeq_##X##_del(cdeq_##X* self) { \

         cdeq_##X##_clear(self); \

-        if (_cdeq_rep(self)->cap) \

-            c_free(_cdeq_rep(self)); \

+        if (cdeq_rep_(self)->cap) \

+            c_free(cdeq_rep_(self)); \

     } \

 \

     STC_DEF void \

     _cdeq_##X##_expand(cdeq_##X* self, size_t n, bool at_front) { \

-        struct cdeq_rep* rep = _cdeq_rep(self); \

+        struct cdeq_rep* rep = cdeq_rep_(self); \

         size_t len = rep->size, cap = rep->cap; \

         size_t nfront = self->data - self->base, nback = cap - (nfront + len); \

         if (at_front && nfront >= n || !at_front && nback >= n) \

@@ -275,10 +277,10 @@ static inline double _maxf(double x, double y) {return x > y ? x : y;}
     STC_DEF void \

     cdeq_##X##_resize(cdeq_##X* self, size_t size, Value null_val) { \

         _cdeq_##X##_expand(self, size, false); \

-        size_t i, n = _cdeq_rep(self)->size; \

+        size_t i, n = cdeq_rep_(self)->size; \

         for (i=size; i<n; ++i) valueDestroy(self->data + i); \

         for (i=n; i<size; ++i) self->data[i] = null_val; \

-        if (self->data) _cdeq_rep(self)->size = size; \

+        if (self->data) cdeq_rep_(self)->size = size; \

     } \

 \

     STC_DEF void \

@@ -286,28 +288,28 @@ static inline double _maxf(double x, double y) {return x > y ? x : y;}
         if (self->data == self->base) \

             _cdeq_##X##_expand(self, 1, true); \

         *--self->data = value; \

-        ++_cdeq_rep(self)->size; \

+        ++cdeq_rep_(self)->size; \

     } \

     STC_DEF void \

     cdeq_##X##_push_back(cdeq_##X* self, Value value) { \

-        if (_cdeq_nfront(self) + _cdeq_rep(self)->size == _cdeq_rep(self)->cap) \

+        if (_cdeq_nfront(self) + cdeq_rep_(self)->size == cdeq_rep_(self)->cap) \

             _cdeq_##X##_expand(self, 1, false); \

-        self->data[_cdeq_rep(self)->size++] = value; \

+        self->data[cdeq_rep_(self)->size++] = value; \

     } \

 \

     STC_DEF cdeq_##X \

-    cdeq_##X##_clone(cdeq_##X vec) { \

-        size_t len = _cdeq_rep(&vec)->size; \

+    cdeq_##X##_clone(cdeq_##X deq) { \

+        size_t len = cdeq_rep_(&deq)->size; \

         cdeq_##X out = cdeq_##X##_with_capacity(len); \

-        cdeq_##X##_insert_range_p(&out, out.data, vec.data, vec.data + len); \

+        cdeq_##X##_insert_range_p(&out, out.data, deq.data, deq.data + len); \

         return out; \

     } \

 \

     STC_DEF cdeq_##X##_iter_t \

     cdeq_##X##_insert_range_p(cdeq_##X* self, cdeq_##X##_value_t* pos, \

                               const cdeq_##X##_value_t* first, const cdeq_##X##_value_t* finish) { \

-        size_t n = finish - first, idx = pos - self->data, size = _cdeq_rep(self)->size; \

-        bool at_front = (idx < size/2); \

+        size_t n = finish - first, idx = pos - self->data, size = cdeq_rep_(self)->size; \

+        bool at_front = (idx*2 < size); \

         _cdeq_##X##_expand(self, n, at_front); \

         if (at_front) { \

             memmove(self->data - n, self->data, idx*sizeof(Value)); \

@@ -317,7 +319,7 @@ static inline double _maxf(double x, double y) {return x > y ? x : y;}
             memmove(pos + n, pos, (size - idx)*sizeof(Value)); \

         } \

         cdeq_##X##_iter_t it = {pos}; \

-        if (n) _cdeq_rep(self)->size += n; \

+        if (n) cdeq_rep_(self)->size += n; \

         while (first != finish) \

             *pos++ = valueFromRaw(valueToRaw(first++)); \

         return it; \

@@ -327,28 +329,23 @@ static inline double _maxf(double x, double y) {return x > y ? x : y;}
     cdeq_##X##_erase_range_p(cdeq_##X* self, cdeq_##X##_value_t* first, cdeq_##X##_value_t* finish) { \

         intptr_t len = finish - first; \

         if (len > 0) { \

-            cdeq_##X##_value_t* p = first, *end = self->data + _cdeq_rep(self)->size; \

+            cdeq_##X##_value_t* p = first, *end = self->data + cdeq_rep_(self)->size; \

             while (p != finish) valueDestroy(p++); \

             if (first == self->data) self->data += len; \

             else memmove(first, finish, (end - finish) * sizeof(Value)); \

-            _cdeq_rep(self)->size -= len; \

+            cdeq_rep_(self)->size -= len; \

         } \

         cdeq_##X##_iter_t it = {first}; return it; \

     } \

 \

     STC_DEF cdeq_##X##_iter_t \

-    cdeq_##X##_find_in_range(const cdeq_##X* self, cdeq_##X##_iter_t first, cdeq_##X##_iter_t finish, RawValue raw) { \

-        for (; first.ref != finish.ref; cdeq_##X##_next(&first)) { \

-            RawValue r = valueToRaw(first.ref); \

-            if (valueCompareRaw(&r, &raw) == 0) return first; \

+    cdeq_##X##_find_in_range(cdeq_##X##_iter_t i1, cdeq_##X##_iter_t i2, RawValue raw) { \

+        for (; i1.ref != i2.ref; ++i1.ref) { \

+            RawValue r = valueToRaw(i1.ref); \

+            if (valueCompareRaw(&raw, &r) == 0) return i1; \

         } \

-        return cdeq_##X##_end(self); \

+        return i2; \

     } \

-    STC_DEF cdeq_##X##_iter_t \

-    cdeq_##X##_find(const cdeq_##X* self, RawValue raw) { \

-        return cdeq_##X##_find_in_range(self, cdeq_##X##_begin(self), cdeq_##X##_end(self), raw); \

-    } \

-\

     STC_DEF int \

     cdeq_##X##_value_compare(const cdeq_##X##_value_t* x, const cdeq_##X##_value_t* y) { \

         RawValue rx = valueToRaw(x); \

@@ -360,13 +357,4 @@ static inline double _maxf(double x, double y) {return x > y ? x : y;}
 #define _c_implement_cdeq_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue)

 #endif

 

-#if defined(_WIN32) && defined(_DLL)

-#define STC_EXTERN_IMPORT extern __declspec(dllimport)

-#else

-#define STC_EXTERN_IMPORT extern

-#endif

-

-typedef int(*_cdeq_cmp)(const void*, const void*);

-STC_EXTERN_IMPORT void qsort(void *start, size_t nitems, size_t size, _cdeq_cmp cmp);

-

 #endif

diff --git a/stc/csmap.h b/stc/csmap.h
index a7f49a08..e56f4fb2 100644
--- a/stc/csmap.h
+++ b/stc/csmap.h
@@ -147,7 +147,7 @@ int main(void) {
 #endif

 

 struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; };

-#define _csmap_rep(self) c_container_of((self)->nodes, struct csmap_rep, nodes)

+#define csmap_rep_(self) c_container_of((self)->nodes, struct csmap_rep, nodes)

 

 #define _using_AATREE(X, C, Key, Mapped, keyCompareRaw, \

                          mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \

@@ -202,11 +202,11 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; };
         return x; \

     } \

     STC_INLINE bool \

-    C##_##X##_empty(C##_##X tree) {return _csmap_rep(&tree)->size == 0;} \

+    C##_##X##_empty(C##_##X tree) {return csmap_rep_(&tree)->size == 0;} \

     STC_INLINE size_t \

-    C##_##X##_size(C##_##X tree) {return _csmap_rep(&tree)->size;} \

+    C##_##X##_size(C##_##X tree) {return csmap_rep_(&tree)->size;} \

     STC_INLINE size_t \

-    C##_##X##_capacity(C##_##X tree) {return _csmap_rep(&tree)->cap;} \

+    C##_##X##_capacity(C##_##X tree) {return csmap_rep_(&tree)->cap;} \

     STC_API void \

     C##_##X##_del(C##_##X* self); \

     STC_INLINE void \

@@ -294,7 +294,7 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; };
 \

     STC_INLINE C##_##X##_iter_t \

     C##_##X##_begin(C##_##X* self) { \

-        C##_##X##_iter_t it = {NULL, self->nodes, 0, (C##_##X##_size_t) _csmap_rep(self)->root}; \

+        C##_##X##_iter_t it = {NULL, self->nodes, 0, (C##_##X##_size_t) csmap_rep_(self)->root}; \

         if (it._tn) C##_##X##_next(&it); \

         return it; \

     } \

@@ -335,21 +335,21 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0};
     STC_DEF C##_##X##_value_t* \

     C##_##X##_front(C##_##X* self) { \

         C##_##X##_node_t *d = self->nodes; \

-        C##_##X##_size_t tn = (C##_##X##_size_t) _csmap_rep(self)->root; \

+        C##_##X##_size_t tn = (C##_##X##_size_t) csmap_rep_(self)->root; \

         while (d[tn].link[0]) tn = d[tn].link[0]; \

         return &d[tn].value; \

     } \

     STC_DEF C##_##X##_value_t* \

     C##_##X##_back(C##_##X* self) { \

         C##_##X##_node_t *d = self->nodes; \

-        C##_##X##_size_t tn = (C##_##X##_size_t) _csmap_rep(self)->root; \

+        C##_##X##_size_t tn = (C##_##X##_size_t) csmap_rep_(self)->root; \

         while (d[tn].link[1]) tn = d[tn].link[1]; \

         return &d[tn].value; \

     } \

 \

     STC_DEF void \

     C##_##X##_reserve(C##_##X* self, size_t cap) { \

-        struct csmap_rep* rep = _csmap_rep(self); \

+        struct csmap_rep* rep = csmap_rep_(self); \

         C##_##X##_size_t oldcap = rep->cap; \

         if (cap > oldcap) { \

             rep = (struct csmap_rep*) c_realloc(oldcap ? rep : NULL, \

@@ -363,13 +363,13 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0};
 \

     STC_DEF C##_##X##_size_t \

     C##_##X##_node_new_(C##_##X* self, int level) { \

-        size_t tn; struct csmap_rep *rep = _csmap_rep(self); \

+        size_t tn; struct csmap_rep *rep = csmap_rep_(self); \

         if (rep->disp) { \

             tn = rep->disp; \

             rep->disp = self->nodes[tn].link[1]; \

         } else { \

             if ((tn = rep->head + 1) > rep->cap) C##_##X##_reserve(self, 4 + tn*3/2); \

-            ++_csmap_rep(self)->head; /* do after reserve */ \

+            ++csmap_rep_(self)->head; /* do after reserve */ \

         } \

         C##_##X##_node_t* dn = &self->nodes[tn]; \

         dn->link[0] = dn->link[1] = 0; dn->level = level; \

@@ -378,7 +378,7 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0};
 \

     STC_DEF C##_##X##_value_t* \

     C##_##X##_find_it(const C##_##X* self, C##_##X##_rawkey_t rkey, C##_##X##_iter_t* out) { \

-        C##_##X##_size_t tn = _csmap_rep(self)->root; \

+        C##_##X##_size_t tn = csmap_rep_(self)->root; \

         C##_##X##_node_t *d = out->_d = self->nodes; \

         out->_top = 0; \

         while (tn) { \

@@ -457,9 +457,9 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0};
     STC_DEF C##_##X##_result_t \

     C##_##X##_insert_entry_(C##_##X* self, RawKey rkey) { \

         C##_##X##_result_t res = {NULL, false}; \

-        C##_##X##_size_t tn = C##_##X##insert_entry_i_(self, (C##_##X##_size_t) _csmap_rep(self)->root, &rkey, &res); \

-        _csmap_rep(self)->root = tn; \

-        _csmap_rep(self)->size += res.second; \

+        C##_##X##_size_t tn = C##_##X##insert_entry_i_(self, (C##_##X##_size_t) csmap_rep_(self)->root, &rkey, &res); \

+        csmap_rep_(self)->root = tn; \

+        csmap_rep_(self)->size += res.second; \

         return res; \

     } \

 \

@@ -504,8 +504,8 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0};
     STC_DEF int \

     C##_##X##_erase(C##_##X* self, RawKey rkey) { \

         int erased = 0; \

-        C##_##X##_size_t root = C##_##X##_erase_r_(self->nodes, (C##_##X##_size_t) _csmap_rep(self)->root, &rkey, &erased); \

-        if (erased) {_csmap_rep(self)->root = root; --_csmap_rep(self)->size;} \

+        C##_##X##_size_t root = C##_##X##_erase_r_(self->nodes, (C##_##X##_size_t) csmap_rep_(self)->root, &rkey, &erased); \

+        if (erased) {csmap_rep_(self)->root = root; --csmap_rep_(self)->size;} \

         return erased; \

     } \

 \

@@ -520,10 +520,10 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0};
     } \

     STC_DEF C##_##X \

     C##_##X##_clone(C##_##X tree) { \

-        C##_##X clone = C##_##X##_with_capacity(_csmap_rep(&tree)->size); \

-        C##_##X##_size_t root = C##_##X##_clone_r_(&clone, tree.nodes, (C##_##X##_size_t) _csmap_rep(&tree)->root); \

-        _csmap_rep(&clone)->root = root; \

-        _csmap_rep(&clone)->size = _csmap_rep(&tree)->size; \

+        C##_##X clone = C##_##X##_with_capacity(csmap_rep_(&tree)->size); \

+        C##_##X##_size_t root = C##_##X##_clone_r_(&clone, tree.nodes, (C##_##X##_size_t) csmap_rep_(&tree)->root); \

+        csmap_rep_(&clone)->root = root; \

+        csmap_rep_(&clone)->size = csmap_rep_(&tree)->size; \

         return clone; \

     } \

 \

@@ -537,9 +537,9 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0};
     } \

     STC_DEF void \

     C##_##X##_del(C##_##X* self) { \

-        if (_csmap_rep(self)->root) { \

-            C##_##X##_del_r_(self->nodes, (C##_##X##_size_t) _csmap_rep(self)->root); \

-            c_free(_csmap_rep(self)); \

+        if (csmap_rep_(self)->root) { \

+            C##_##X##_del_r_(self->nodes, (C##_##X##_size_t) csmap_rep_(self)->root); \

+            c_free(csmap_rep_(self)); \

         } \

     }

 

diff --git a/stc/cvec.h b/stc/cvec.h
index 7ba00076..5899132e 100644
--- a/stc/cvec.h
+++ b/stc/cvec.h
@@ -46,7 +46,8 @@
     } cvec_##X

     

 struct cvec_rep { size_t size, cap; void* data[]; };

-#define _cvec_rep(self) c_container_of((self)->data, struct cvec_rep, data)

+#define cvec_rep_(self) c_container_of((self)->data, struct cvec_rep, data)

+typedef int (*c_cmp_fn)(const void*, const void*);

 

 #define using_cvec_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue) \

     typedefs_cvec(X, Value, RawValue); \

@@ -54,11 +55,11 @@ struct cvec_rep { size_t size, cap; void* data[]; };
     STC_API cvec_##X \

     cvec_##X##_init(void); \

     STC_INLINE size_t \

-    cvec_##X##_size(cvec_##X vec) { return _cvec_rep(&vec)->size; } \

+    cvec_##X##_size(cvec_##X vec) { return cvec_rep_(&vec)->size; } \

     STC_INLINE size_t \

-    cvec_##X##_capacity(cvec_##X vec) { return _cvec_rep(&vec)->cap; } \

+    cvec_##X##_capacity(cvec_##X vec) { return cvec_rep_(&vec)->cap; } \

     STC_INLINE bool \

-    cvec_##X##_empty(cvec_##X vec) {return !_cvec_rep(&vec)->size;} \

+    cvec_##X##_empty(cvec_##X vec) {return !cvec_rep_(&vec)->size;} \

     STC_INLINE Value \

     cvec_##X##_value_fromraw(RawValue raw) {return valueFromRaw(raw);} \

     STC_INLINE cvec_##X##_value_t \

@@ -104,7 +105,7 @@ struct cvec_rep { size_t size, cap; void* data[]; };
     } \

     STC_INLINE void \

     cvec_##X##_pop_back(cvec_##X* self) { \

-        valueDestroy(&self->data[--_cvec_rep(self)->size]); \

+        valueDestroy(&self->data[--cvec_rep_(self)->size]); \

     } \

 \

     STC_API cvec_##X##_iter_t \

@@ -147,39 +148,23 @@ struct cvec_rep { size_t size, cap; void* data[]; };
         return cvec_##X##_erase_range_p(self, self->data + idx, self->data + idx + n); \

     } \

 \

-    STC_API cvec_##X##_iter_t \

-    cvec_##X##_find(const cvec_##X* self, RawValue raw); \

-    STC_API cvec_##X##_iter_t \

-    cvec_##X##_find_in_range(const cvec_##X* self, cvec_##X##_iter_t first, cvec_##X##_iter_t finish, RawValue raw); \

-\

     STC_INLINE cvec_##X##_value_t* \

     cvec_##X##_front(cvec_##X* self) {return self->data;} \

     STC_INLINE cvec_##X##_value_t* \

-    cvec_##X##_back(cvec_##X* self) {return self->data + _cvec_rep(self)->size - 1;} \

+    cvec_##X##_back(cvec_##X* self) {return self->data + cvec_rep_(self)->size - 1;} \

     STC_INLINE cvec_##X##_value_t* \

      cvec_##X##_at(cvec_##X* self, size_t i) { \

-        assert(i < _cvec_rep(self)->size); \

+        assert(i < cvec_rep_(self)->size); \

         return self->data + i; \

     } \

 \

-    STC_API int \

-    cvec_##X##_value_compare(const cvec_##X##_value_t* x, const cvec_##X##_value_t* y); \

-    STC_INLINE void \

-    cvec_##X##_sort_with(cvec_##X* self, size_t ifirst, size_t ifinish, int(*cmp)(const cvec_##X##_value_t*, const cvec_##X##_value_t*)) { \

-        qsort(self->data + ifirst, ifinish - ifirst, sizeof(Value), (_cvec_cmp) cmp); \

-    } \

-    STC_INLINE void \

-    cvec_##X##_sort(cvec_##X* self) { \

-        cvec_##X##_sort_with(self, 0, _cvec_rep(self)->size, cvec_##X##_value_compare); \

-    } \

-\

     STC_INLINE cvec_##X##_iter_t \

     cvec_##X##_begin(const cvec_##X* self) { \

         cvec_##X##_iter_t it = {self->data}; return it; \

     } \

     STC_INLINE cvec_##X##_iter_t \

     cvec_##X##_end(const cvec_##X* self) { \

-        cvec_##X##_iter_t it = {self->data + _cvec_rep(self)->size}; return it; \

+        cvec_##X##_iter_t it = {self->data + cvec_rep_(self)->size}; return it; \

     } \

     STC_INLINE void \

     cvec_##X##_next(cvec_##X##_iter_t* it) {++it->ref;} \

@@ -188,6 +173,30 @@ struct cvec_rep { size_t size, cap; void* data[]; };
     STC_INLINE size_t \

     cvec_##X##_index(cvec_##X vec, cvec_##X##_iter_t it) {return it.ref - vec.data;} \

 \

+    STC_API cvec_##X##_iter_t \

+    cvec_##X##_find_in_range(cvec_##X##_iter_t first, cvec_##X##_iter_t finish, RawValue raw); \

+    STC_INLINE cvec_##X##_iter_t \

+    cvec_##X##_find(const cvec_##X* self, RawValue raw) { \

+        return cvec_##X##_find_in_range(cvec_##X##_begin(self), cvec_##X##_end(self), raw); \

+    } \

+    STC_API int \

+    cvec_##X##_value_compare(const cvec_##X##_value_t* x, const cvec_##X##_value_t* y); \

+    STC_API cvec_##X##_iter_t \

+    cvec_##X##_bsearch_in_range(cvec_##X##_iter_t i1, cvec_##X##_iter_t i2, RawValue raw); \

+    STC_INLINE cvec_##X##_iter_t \

+    cvec_##X##_bsearch(cvec_##X* self, RawValue raw) { \

+        return cvec_##X##_bsearch_in_range(cvec_##X##_begin(self), cvec_##X##_end(self), raw); \

+    } \

+    STC_INLINE void \

+    cvec_##X##_sort_range(cvec_##X##_iter_t i1, cvec_##X##_iter_t i2, \

+                          int(*cmp)(const cvec_##X##_value_t*, const cvec_##X##_value_t*)) { \

+        qsort(i1.ref, i2.ref - i1.ref, sizeof(cvec_##X##_value_t), (c_cmp_fn) cmp); \

+    } \

+    STC_INLINE void \

+    cvec_##X##_sort(cvec_##X* self) { \

+        cvec_##X##_sort_range(cvec_##X##_begin(self), cvec_##X##_end(self), cvec_##X##_value_compare); \

+    } \

+\

     _c_implement_cvec_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue) \

     typedef cvec_##X cvec_##X##_t

 

@@ -206,15 +215,15 @@ static struct cvec_rep _cvec_inits = {0, 0};
     STC_DEF void \

     cvec_##X##_emplace_n(cvec_##X *self, const cvec_##X##_rawvalue_t arr[], size_t n) { \

         if (!n) return; \

-        cvec_##X##_reserve(self, _cvec_rep(self)->size + n); \

-        cvec_##X##_value_t* p = self->data + _cvec_rep(self)->size; \

+        cvec_##X##_reserve(self, cvec_rep_(self)->size + n); \

+        cvec_##X##_value_t* p = self->data + cvec_rep_(self)->size; \

         for (size_t i=0; i < n; ++i) *p++ = valueFromRaw(arr[i]); \

-        _cvec_rep(self)->size += n; \

+        cvec_rep_(self)->size += n; \

     } \

 \

     STC_DEF void \

     cvec_##X##_clear(cvec_##X* self) { \

-        struct cvec_rep* rep = _cvec_rep(self); if (rep->cap) { \

+        struct cvec_rep* rep = cvec_rep_(self); if (rep->cap) { \

             for (cvec_##X##_value_t *p = self->data, *q = p + rep->size; p != q; ++p) \

                 valueDestroy(p); \

             rep->size = 0; \

@@ -223,13 +232,13 @@ static struct cvec_rep _cvec_inits = {0, 0};
     STC_DEF void \

     cvec_##X##_del(cvec_##X* self) { \

         cvec_##X##_clear(self); \

-        if (_cvec_rep(self)->cap) \

-            c_free(_cvec_rep(self)); \

+        if (cvec_rep_(self)->cap) \

+            c_free(cvec_rep_(self)); \

     } \

 \

     STC_DEF void \

     cvec_##X##_reserve(cvec_##X* self, size_t cap) { \

-        struct cvec_rep* rep = _cvec_rep(self); \

+        struct cvec_rep* rep = cvec_rep_(self); \

         size_t len = rep->size, oldcap = rep->cap; \

         if (cap > oldcap) { \

             rep = (struct cvec_rep*) c_realloc(oldcap ? rep : NULL, \

@@ -242,7 +251,7 @@ static struct cvec_rep _cvec_inits = {0, 0};
     STC_DEF void \

     cvec_##X##_resize(cvec_##X* self, size_t len, Value null_val) { \

         cvec_##X##_reserve(self, len); \

-        struct cvec_rep* rep = _cvec_rep(self); \

+        struct cvec_rep* rep = cvec_rep_(self); \

         size_t i, n = rep->size; \

         for (i = len; i < n; ++i) valueDestroy(self->data + i); \

         for (i = n; i < len; ++i) self->data[i] = null_val; \

@@ -251,15 +260,15 @@ static struct cvec_rep _cvec_inits = {0, 0};
 \

     STC_DEF void \

     cvec_##X##_push_back(cvec_##X* self, Value value) { \

-        size_t len = _cvec_rep(self)->size; \

+        size_t len = cvec_rep_(self)->size; \

         if (len == cvec_##X##_capacity(*self)) \

-            cvec_##X##_reserve(self, 4 + len*3/2); \

-        self->data[_cvec_rep(self)->size++] = value; \

+            cvec_##X##_reserve(self, 4 + len*1.5); \

+        self->data[cvec_rep_(self)->size++] = value; \

     } \

 \

     STC_DEF cvec_##X \

     cvec_##X##_clone(cvec_##X vec) { \

-        size_t len = _cvec_rep(&vec)->size; \

+        size_t len = cvec_rep_(&vec)->size; \

         cvec_##X out = cvec_##X##_with_capacity(len); \

         cvec_##X##_insert_range_p(&out, out.data, vec.data, vec.data + len); \

         return out; \

@@ -267,13 +276,13 @@ static struct cvec_rep _cvec_inits = {0, 0};
 \

     STC_DEF cvec_##X##_iter_t \

     cvec_##X##_insert_range_p(cvec_##X* self, cvec_##X##_value_t* pos, const cvec_##X##_value_t* first, const cvec_##X##_value_t* finish) { \

-        size_t len = finish - first, idx = pos - self->data, size = _cvec_rep(self)->size; \

+        size_t len = finish - first, idx = pos - self->data, size = cvec_rep_(self)->size; \

         cvec_##X##_iter_t it = {pos}; \

         if (len == 0) return it; \

         if (size + len > cvec_##X##_capacity(*self)) \

-            cvec_##X##_reserve(self, 4 + (size + len)*3/2), \

+            cvec_##X##_reserve(self, 4 + (size + len)*1.5), \

             it.ref = pos = self->data + idx; \

-        _cvec_rep(self)->size += len; \

+        cvec_rep_(self)->size += len; \

         memmove(pos + len, pos, (size - idx) * sizeof(Value)); \

         while (first != finish) \

             *pos++ = valueFromRaw(valueToRaw(first++)); \

@@ -284,25 +293,35 @@ static struct cvec_rep _cvec_inits = {0, 0};
     cvec_##X##_erase_range_p(cvec_##X* self, cvec_##X##_value_t* first, cvec_##X##_value_t* finish) { \

         intptr_t len = finish - first; \

         if (len > 0) { \

-            cvec_##X##_value_t* p = first, *end = self->data + _cvec_rep(self)->size; \

+            cvec_##X##_value_t* p = first, *end = self->data + cvec_rep_(self)->size; \

             while (p != finish) valueDestroy(p++); \

             memmove(first, finish, (end - finish) * sizeof(Value)); \

-            _cvec_rep(self)->size -= len; \

+            cvec_rep_(self)->size -= len; \

         } \

         cvec_##X##_iter_t it = {first}; return it; \

     } \

 \

     STC_DEF cvec_##X##_iter_t \

-    cvec_##X##_find_in_range(const cvec_##X* self, cvec_##X##_iter_t first, cvec_##X##_iter_t finish, RawValue raw) { \

-        for (; first.ref != finish.ref; cvec_##X##_next(&first)) { \

-            RawValue r = valueToRaw(first.ref); \

-            if (valueCompareRaw(&r, &raw) == 0) return first; \

+    cvec_##X##_find_in_range(cvec_##X##_iter_t i1, cvec_##X##_iter_t i2, RawValue raw) { \

+        for (; i1.ref != i2.ref; ++i1.ref) { \

+            RawValue r = valueToRaw(i1.ref); \

+            if (valueCompareRaw(&raw, &r) == 0) return i1; \

         } \

-        return cvec_##X##_end(self); \

+        return i2; \

     } \

     STC_DEF cvec_##X##_iter_t \

-    cvec_##X##_find(const cvec_##X* self, RawValue raw) { \

-        return cvec_##X##_find_in_range(self, cvec_##X##_begin(self), cvec_##X##_end(self), raw); \

+    cvec_##X##_bsearch_in_range(cvec_##X##_iter_t i1, cvec_##X##_iter_t i2, RawValue raw) { \

+        cvec_##X##_iter_t mid, last = i2; \

+        while (i1.ref != i2.ref) { \

+            mid.ref = i1.ref + ((i2.ref - i1.ref)>>1); \

+            RawValue m = valueToRaw(mid.ref); \

+            switch (valueCompareRaw(&raw, &m)) { \

+                case 0: return mid; \

+                case -1: i2.ref = mid.ref; break; \

+                case 1: i1.ref = mid.ref + 1; \

+            } \

+        } \

+        return last; \

     } \

 \

     STC_DEF int \

@@ -316,12 +335,4 @@ static struct cvec_rep _cvec_inits = {0, 0};
 #define _c_implement_cvec_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue)

 #endif

 

-#if defined(_WIN32) && defined(_DLL)

-#define STC_EXTERN_IMPORT extern __declspec(dllimport)

-#else

-#define STC_EXTERN_IMPORT extern

-#endif

-typedef int(*_cvec_cmp)(const void*, const void*);

-STC_EXTERN_IMPORT void qsort(void *base, size_t nitems, size_t size, _cvec_cmp cmp);

-

 #endif