Internal restructure. Added bsearch() to cvec.

1 files changed, 67 insertions, 56 deletions

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