From c609469b3eac08cc369f30a54cc737a3d9cadc3b Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 21 Feb 2021 17:03:36 +0100 Subject: Internal restructure. Added bsearch() to cvec. --- docs/cdeq_api.md | 12 +++-- docs/cmap_api.md | 8 ++-- docs/csmap_api.md | 6 +-- docs/cvec_api.md | 10 ++--- examples/demos.c | 1 - examples/ex_gauss1.c | 8 ++-- stc/cdeq.h | 118 ++++++++++++++++++++++-------------------------- stc/csmap.h | 46 +++++++++---------- stc/cvec.h | 123 ++++++++++++++++++++++++++++----------------------- 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 #include #include -#include "stc/crandom.h" -#include "stc/cstr.h" -#include "stc/cmap.h" -#include "stc/cvec.h" +#include +#include +#include +#include // 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 \ @@ -163,32 +164,16 @@ struct cdeq_rep { size_t size, cap; void* base[]; }; 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); \ } \ -\ - 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) { \ @@ -196,7 +181,7 @@ struct cdeq_rep { size_t size, cap; void* base[]; }; } \ 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; idata + i); \ for (i=n; idata[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 \ @@ -146,32 +147,16 @@ struct cvec_rep { size_t size, cap; void* data[]; }; cvec_##X##_erase(cvec_##X* self, size_t idx, size_t n) { \ 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) { \ @@ -179,7 +164,7 @@ struct cvec_rep { size_t size, cap; void* data[]; }; } \ 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;} \ @@ -187,6 +172,30 @@ struct cvec_rep { size_t size, cap; void* data[]; }; cvec_##X##_itval(cvec_##X##_iter_t it) {return it.ref;} \ 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 -- cgit v1.2.3