From a913490c248f6cfdca3481d81d6d344f4d066cb9 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Tue, 18 Apr 2023 17:48:47 +0200 Subject: Removed unneeded custom size type in maps and bits.h. Prepared for possible robin-hood impl. Improved sso_bench.c testing string hash - twice as fast as m.ankeln robin impl !?. --- include/stc/priv/template2.h | 1 - 1 file changed, 1 deletion(-) (limited to 'include/stc/priv/template2.h') diff --git a/include/stc/priv/template2.h b/include/stc/priv/template2.h index 27c6a890..2e8a6c8d 100644 --- a/include/stc/priv/template2.h +++ b/include/stc/priv/template2.h @@ -30,7 +30,6 @@ #undef i_hash #undef i_rawclass #undef i_capacity -#undef i_ssize #undef i_val #undef i_val_str -- cgit v1.2.3 From 50a16934dde8e65bbcf628d6342c1649f7e09365 Mon Sep 17 00:00:00 2001 From: Tyge Lovset Date: Thu, 18 May 2023 11:49:31 +0200 Subject: Huge update: cqueue and cdeq completely rewritten. cvec and cdeq API harmonized. Docs update/improved. --- README.md | 2 +- docs/ccommon_api.md | 2 +- docs/cdeq_api.md | 45 ++-- docs/clist_api.md | 10 +- docs/cqueue_api.md | 9 +- docs/csmap_api.md | 3 +- docs/cstack_api.md | 3 +- docs/cvec_api.md | 20 +- include/stc/algo/csort.h | 89 ------- include/stc/algo/sort.h | 100 ++++++++ include/stc/ccommon.h | 10 + include/stc/cdeq.h | 453 ++++++++-------------------------- include/stc/clist.h | 9 +- include/stc/cmap.h | 9 +- include/stc/cqueue.h | 226 ++++++++++++++--- include/stc/cvec.h | 121 ++++----- include/stc/forward.h | 13 +- include/stc/priv/template.h | 8 +- include/stc/priv/template2.h | 5 + misc/benchmarks/various/csort_bench.c | 44 ++-- misc/benchmarks/various/cspan_bench.c | 2 +- misc/examples/printspan.c | 6 - src/cregex.c | 2 +- 23 files changed, 550 insertions(+), 641 deletions(-) delete mode 100644 include/stc/algo/csort.h create mode 100644 include/stc/algo/sort.h (limited to 'include/stc/priv/template2.h') diff --git a/README.md b/README.md index 74c2238f..3b9cf90f 100644 --- a/README.md +++ b/README.md @@ -642,7 +642,7 @@ Major changes: - Algorithms: - [crange](docs/ccommon_api.md#crange) - similar to [boost::irange](https://www.boost.org/doc/libs/release/libs/range/doc/html/range/reference/ranges/irange.html) integer range generator. - [c_forfilter](docs/ccommon_api.md#c_forfilter) - ranges-like view filtering. - - [csort](include/stc/algo/csort.h) - [fast quicksort](misc/benchmarks/various/csort_bench.c) with custom inline comparison. + - [csort](include/stc/algo/sort.h) - [fast quicksort](misc/benchmarks/various/csort_bench.c) with custom inline comparison. - Renamed `c_ARGSV()` => `c_SV()`: **csview** print arg. Note `c_sv()` is shorthand for *csview_from()*. - Support for [uppercase flow-control](include/stc/priv/altnames.h) macro names in ccommon.h. - Some API changes in **cregex** and **cstr**. diff --git a/docs/ccommon_api.md b/docs/ccommon_api.md index e4c881dd..e37a1463 100644 --- a/docs/ccommon_api.md +++ b/docs/ccommon_api.md @@ -212,7 +212,7 @@ You may customize `i_tag` and the comparison function `i_cmp` or `i_less`. There is a [benchmark/test file here](../misc/benchmarks/various/csort_bench.c). ```c #define i_val int -#include +#include int main() { int array[] = {5, 3, 5, 9, 7, 4, 7, 2, 4, 9, 3, 1, 2, 6, 4}; diff --git a/docs/cdeq_api.md b/docs/cdeq_api.md index fc11fe66..91022a5c 100644 --- a/docs/cdeq_api.md +++ b/docs/cdeq_api.md @@ -1,7 +1,9 @@ # STC [cdeq](../include/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 *cdeq_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, but has also fast random access to elements. The container is +implemented as a circular dynamic buffer. 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. @@ -32,20 +34,20 @@ cdeq_X cdeq_X_clone(cdeq_X deq); void cdeq_X_clear(cdeq_X* self); void cdeq_X_copy(cdeq_X* self, const cdeq_X* other); -cdeq_X_iter cdeq_X_copy_range(cdeq_X* self, i_val* pos, const i_val* p1, const i_val* p2); bool cdeq_X_reserve(cdeq_X* self, intptr_t cap); void cdeq_X_shrink_to_fit(cdeq_X* self); -void cdeq_X_drop(cdeq_X* self); // destructor +void cdeq_X_drop(cdeq_X* self); // destructor bool cdeq_X_empty(const cdeq_X* self); intptr_t cdeq_X_size(const cdeq_X* self); intptr_t cdeq_X_capacity(const cdeq_X* self); const cdeq_X_value* cdeq_X_at(const cdeq_X* self, intptr_t idx); -const cdeq_X_value* cdeq_X_get(const cdeq_X* self, i_valraw raw); // return NULL if not found -cdeq_X_value* cdeq_X_get_mut(cdeq_X* self, i_valraw raw); // mutable get +cdeq_X_value* cdeq_X_at_mut(cdeq_X* self, intptr_t idx); +const cdeq_X_value* cdeq_X_get(const cdeq_X* self, i_valraw raw); // return NULL if not found +cdeq_X_value* cdeq_X_get_mut(cdeq_X* self, i_valraw raw); // mutable get cdeq_X_iter cdeq_X_find(const cdeq_X* self, i_valraw raw); -cdeq_X_iter cdeq_X_find_in(cdeq_X_iter i1, cdeq_X_iter i2, i_valraw raw); // return cvec_X_end() if not found +cdeq_X_iter cdeq_X_find_in(cdeq_X_iter i1, cdeq_X_iter i2, i_valraw raw); // return cvec_X_end() if not found cdeq_X_value* cdeq_X_front(const cdeq_X* self); cdeq_X_value* cdeq_X_back(const cdeq_X* self); @@ -55,38 +57,31 @@ cdeq_X_value* cdeq_X_emplace_front(cdeq_X* self, i_valraw raw); void cdeq_X_pop_front(cdeq_X* self); cdeq_X_value* cdeq_X_push_back(cdeq_X* self, i_val value); -cdeq_X_value* cdeq_X_push(cdeq_X* self, i_val value); // alias for push_back() +cdeq_X_value* cdeq_X_push(cdeq_X* self, i_val value); // alias for push_back() cdeq_X_value* cdeq_X_emplace_back(cdeq_X* self, i_valraw raw); -cdeq_X_value* cdeq_X_emplace(cdeq_X* self, i_valraw raw); // alias for emplace_back() +cdeq_X_value* cdeq_X_emplace(cdeq_X* self, i_valraw raw); // alias for emplace_back() void cdeq_X_pop_back(cdeq_X* self); -cdeq_X_iter cdeq_X_insert(cdeq_X* self, intptr_t idx, i_val value); // move value -cdeq_X_iter cdeq_X_insert_n(cdeq_X* self, intptr_t idx, const i_val[] arr, intptr_t n); // move arr values -cdeq_X_iter cdeq_X_insert_at(cdeq_X* self, cdeq_X_iter it, i_val value); // move value -cdeq_X_iter cdeq_X_insert_range(cdeq_X* self, i_val* pos, - const i_val* p1, const i_val* p2); - -cdeq_X_iter cdeq_X_emplace_n(cdeq_X* self, intptr_t idx, const i_valraw[] arr, intptr_t n); // clone values +cdeq_X_iter cdeq_X_insert_n(cdeq_X* self, intptr_t idx, const i_val[] arr, intptr_t n); // move values +cdeq_X_iter cdeq_X_insert(cdeq_X* self, intptr_t idx, i_val value); // move value +cdeq_X_iter cdeq_X_insert_at(cdeq_X* self, cdeq_X_iter it, i_val value); // move value +cdeq_X_iter cdeq_X_insert_uninit(cdeq_X* self, intptr_t idx, intptr_t n); // uninitialized data + // copy values: +cdeq_X_iter cdeq_X_emplace_n(cdeq_X* self, intptr_t idx, const i_valraw[] arr, intptr_t n); cdeq_X_iter cdeq_X_emplace_at(cdeq_X* self, cdeq_X_iter it, i_valraw raw); -cdeq_X_iter cdeq_X_emplace_range(cdeq_X* self, i_val* pos, - const i_valraw* p1, const i_valraw* p2); -cdeq_X_iter cdeq_X_erase_n(cdeq_X* self, intptr_t idx, intptr_t n); +void cdeq_X_erase_n(cdeq_X* self, intptr_t idx, intptr_t n); cdeq_X_iter cdeq_X_erase_at(cdeq_X* self, cdeq_X_iter it); cdeq_X_iter cdeq_X_erase_range(cdeq_X* self, cdeq_X_iter it1, cdeq_X_iter it2); -cdeq_X_iter cdeq_X_erase_range_p(cdeq_X* self, i_val* p1, i_val* p2); - -void cdeq_X_sort(cdeq_X* self); -void cdeq_X_sort_range(cdeq_X_iter i1, cdeq_X_iter i2, - int(*cmp)(const i_val*, const i_val*)); cdeq_X_iter cdeq_X_begin(const cdeq_X* self); cdeq_X_iter cdeq_X_end(const cdeq_X* self); void cdeq_X_next(cdeq_X_iter* it); -cdeq_X_iter cdeq_X_advance(cdeq_X_iter it, size_t n); +cdeq_X_iter cdeq_X_advance(cdeq_X_iter it, intptr_t n); -cdeq_X_raw cdeq_X_value_toraw(cdeq_X_value* pval); cdeq_X_value cdeq_X_value_clone(cdeq_X_value val); +cdeq_X_raw cdeq_X_value_toraw(const cdeq_X_value* pval); +void cdeq_X_value_drop(cdeq_X_value* pval); ``` ## Types diff --git a/docs/clist_api.md b/docs/clist_api.md index a1dbe105..44c3bb7c 100644 --- a/docs/clist_api.md +++ b/docs/clist_api.md @@ -84,19 +84,21 @@ void clist_X_sort(clist_X* self); void clist_X_sort_with(clist_X* self, int(*cmp)(const clist_X_value*, const clist_X_value*)); // Node API -clist_X_node* clist_X_get_node(clist_X_value* val); // get the enclosing node +clist_X_node* clist_X_get_node(clist_X_value* val); // get enclosing node clist_X_value* clist_X_push_back_node(clist_X* self, clist_X_node* node); clist_X_value* clist_X_insert_after_node(clist_X* self, clist_X_node* ref, clist_X_node* node); -clist_X_node* clist_X_unlink_after_node(clist_X* self, clist_X_node* ref); // return the unlinked node +clist_X_node* clist_X_unlink_after_node(clist_X* self, clist_X_node* ref); // return unlinked node +clist_X_node* clist_X_unlink_front_node(clist_X* self); // return unlinked node void clist_X_erase_after_node(clist_X* self, clist_X_node* node); clist_X_iter clist_X_begin(const clist_X* self); clist_X_iter clist_X_end(const clist_X* self); void clist_X_next(clist_X_iter* it); -clist_X_iter clist_X_advance(clist_X_iter it, size_t n); // return n elements ahead. +clist_X_iter clist_X_advance(clist_X_iter it, size_t n); // return n elements ahead. -clist_X_raw clist_X_value_toraw(clist_X_value* pval); clist_X_value clist_X_value_clone(clist_X_value val); +clist_X_raw clist_X_value_toraw(const clist_X_value* pval); +void clist_X_value_drop(clist_X_value* pval); ``` ## Types diff --git a/docs/cqueue_api.md b/docs/cqueue_api.md index 9ea4b148..7d8d4e5c 100644 --- a/docs/cqueue_api.md +++ b/docs/cqueue_api.md @@ -26,27 +26,34 @@ See the c++ class [std::queue](https://en.cppreference.com/w/cpp/container/queue ```c cqueue_X cqueue_X_init(void); +cqueue_X cqueue_X_with_capacity(intptr_t size); cqueue_X cqueue_X_clone(cqueue_X q); void cqueue_X_clear(cqueue_X* self); void cqueue_X_copy(cqueue_X* self, const cqueue_X* other); +bool cqueue_X_reserve(cqueue_X* self, intptr_t cap); +void cqueue_X_shrink_to_fit(cqueue_X* self); void cqueue_X_drop(cqueue_X* self); // destructor intptr_t cqueue_X_size(const cqueue_X* self); +intptr_t cqueue_X_capacity(const cqueue_X* self); bool cqueue_X_empty(const cqueue_X* self); + cqueue_X_value* cqueue_X_front(const cqueue_X* self); cqueue_X_value* cqueue_X_back(const cqueue_X* self); cqueue_X_value* cqueue_X_push(cqueue_X* self, i_val value); cqueue_X_value* cqueue_X_emplace(cqueue_X* self, i_valraw raw); - void cqueue_X_pop(cqueue_X* self); cqueue_X_iter cqueue_X_begin(const cqueue_X* self); cqueue_X_iter cqueue_X_end(const cqueue_X* self); void cqueue_X_next(cqueue_X_iter* it); +cqueue_X_iter cqueue_X_advance(cqueue_X_iter it, intptr_t n); i_val cqueue_X_value_clone(i_val value); +cqueue_X_raw cqueue_X_value_toraw(const cqueue_X_value* pval); +void cqueue_X_value_drop(cqueue_X_value* pval); ``` ## Types diff --git a/docs/csmap_api.md b/docs/csmap_api.md index 3e643cee..8c2048c0 100644 --- a/docs/csmap_api.md +++ b/docs/csmap_api.md @@ -83,7 +83,8 @@ void csmap_X_next(csmap_X_iter* iter); csmap_X_iter csmap_X_advance(csmap_X_iter it, intptr_t n); csmap_X_value csmap_X_value_clone(csmap_X_value val); -csmap_X_raw csmap_X_value_toraw(csmap_X_value* pval); +csmap_X_raw csmap_X_value_toraw(const csmap_X_value* pval); +void csmap_X_value_drop(csmap_X_value* pval); ``` ## Types diff --git a/docs/cstack_api.md b/docs/cstack_api.md index b1371f4e..c20de7d1 100644 --- a/docs/cstack_api.md +++ b/docs/cstack_api.md @@ -54,8 +54,9 @@ cstack_X_iter cstack_X_begin(const cstack_X* self); cstack_X_iter cstack_X_end(const cstack_X* self); void cstack_X_next(cstack_X_iter* it); -i_valraw cstack_X_value_toraw(cvec_X_value* pval); i_val cstack_X_value_clone(i_val value); +i_valraw cstack_X_value_toraw(const cvec_X_value* pval); +void cstack_X_value_drop(cvec_X_value* pval); ``` ## Types diff --git a/docs/cvec_api.md b/docs/cvec_api.md index 5879bc1f..194d48e1 100644 --- a/docs/cvec_api.md +++ b/docs/cvec_api.md @@ -37,10 +37,9 @@ cvec_X cvec_X_clone(cvec_X vec); void cvec_X_clear(cvec_X* self); void cvec_X_copy(cvec_X* self, const cvec_X* other); -cvec_X_iter cvec_X_copy_range(cvec_X* self, i_val* pos, const i_val* p1, const i_val* p2); +cvec_X_iter cvec_X_copy_n(cvec_X* self, intptr_t idx, const i_val* arr, intptr_t n); bool cvec_X_reserve(cvec_X* self, intptr_t cap); bool cvec_X_resize(cvec_X* self, intptr_t size, i_val null); -cvec_X_iter cvec_X_insert_uninit(cvec_X* self, i_val* pos, intptr_t n); // return pos iter void cvec_X_shrink_to_fit(cvec_X* self); void cvec_X_drop(cvec_X* self); // destructor @@ -50,8 +49,8 @@ intptr_t cvec_X_capacity(const cvec_X* self); const cvec_X_value* cvec_X_at(const cvec_X* self, intptr_t idx); const cvec_X_value* cvec_X_get(const cvec_X* self, i_valraw raw); // return NULL if not found -cvec_X_value* cvec_X_at_mut(cvec_X* self, intptr_t idx); -cvec_X_value* cvec_X_get_mut(cvec_X* self, i_valraw raw); // find mutable value, return value ptr +cvec_X_value* cvec_X_at_mut(cvec_X* self, intptr_t idx); // return mutable at idx +cvec_X_value* cvec_X_get_mut(cvec_X* self, i_valraw raw); // find mutable value cvec_X_iter cvec_X_find(const cvec_X* self, i_valraw raw); cvec_X_iter cvec_X_find_in(cvec_X_iter i1, cvec_X_iter i2, i_valraw raw); // return cvec_X_end() if not found // On sorted vectors: @@ -72,20 +71,16 @@ void cvec_X_pop(cvec_X* self); void cvec_X_pop_back(cvec_X* self); // alias for pop cvec_X_iter cvec_X_insert(cvec_X* self, intptr_t idx, i_val value); // move value -cvec_X_iter cvec_X_insert_n(cvec_X* self, intptr_t idx, const i_val[] arr, intptr_t n); // move n values +cvec_X_iter cvec_X_insert_n(cvec_X* self, intptr_t idx, const i_val arr[], intptr_t n); // move values cvec_X_iter cvec_X_insert_at(cvec_X* self, cvec_X_iter it, i_val value); // move value -cvec_X_iter cvec_X_insert_range(cvec_X* self, i_val* pos, - const i_val* p1, const i_val* p2); +cvec_X_iter cvec_X_insert_uninit(cvec_X* self, intptr_t idx, intptr_t n); // return iter at idx -cvec_X_iter cvec_X_emplace_n(cvec_X* self, intptr_t idx, const i_valraw[] arr, intptr_t n); // clone values +cvec_X_iter cvec_X_emplace_n(cvec_X* self, intptr_t idx, const i_valraw raw[], intptr_t n); cvec_X_iter cvec_X_emplace_at(cvec_X* self, cvec_X_iter it, i_valraw raw); -cvec_X_iter cvec_X_emplace_range(cvec_X* self, i_val* pos, - const i_valraw* p1, const i_valraw* p2); cvec_X_iter cvec_X_erase_n(cvec_X* self, intptr_t idx, intptr_t n); cvec_X_iter cvec_X_erase_at(cvec_X* self, cvec_X_iter it); cvec_X_iter cvec_X_erase_range(cvec_X* self, cvec_X_iter it1, cvec_X_iter it2); -cvec_X_iter cvec_X_erase_range_p(cvec_X* self, i_val* p1, i_val* p2); void cvec_X_sort(cvec_X* self); void cvec_X_sort_range(cvec_X_iter i1, cvec_X_iter i2, @@ -96,8 +91,9 @@ cvec_X_iter cvec_X_end(const cvec_X* self); void cvec_X_next(cvec_X_iter* iter); cvec_X_iter cvec_X_advance(cvec_X_iter it, size_t n); -cvec_X_raw cvec_X_value_toraw(cvec_X_value* pval); cvec_X_value cvec_X_value_clone(cvec_X_value val); +cvec_X_raw cvec_X_value_toraw(const cvec_X_value* pval); +cvec_X_raw cvec_X_value_drop(cvec_X_value* pval); ``` ## Types diff --git a/include/stc/algo/csort.h b/include/stc/algo/csort.h deleted file mode 100644 index e01a2893..00000000 --- a/include/stc/algo/csort.h +++ /dev/null @@ -1,89 +0,0 @@ -/* MIT License - * - * Copyright (c) 2023 Tyge Løvset - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in all - * copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ -/* Generic Quicksort in C, performs as fast as c++ std::sort(). -template params: -#define i_val - value type [required] -#define i_less - less function. default: *x < *y -#define i_tag NAME - define csort_NAME(). default {i_val} - -// test: -#include -#define i_val int -#include - -int main() { - int arr[] = {23, 321, 5434, 25, 245, 1, 654, 33, 543, 21}; - - csort_int(arr, c_arraylen(arr)); - - for (int i = 0; i < c_arraylen(arr); i++) - printf(" %d", arr[i]); - puts(""); -} -*/ -#include "../ccommon.h" -#define _i_prefix csort_ -#include "../priv/template.h" - -typedef i_val _cx_value; - -static inline void _cx_memb(_insertion)(i_val arr[], intptr_t lo, intptr_t hi) { - for (intptr_t j = lo, i = lo + 1; i <= hi; j = i, ++i) { - i_val key = arr[i]; - while (j >= 0 && (i_less((&key), (&arr[j])))) { - arr[j + 1] = arr[j]; - --j; - } - arr[j + 1] = key; - } -} - -static inline void _cx_memb(_quicksort)(i_val arr[], intptr_t lo, intptr_t hi) { - intptr_t i = lo, j; - while (lo < hi) { - i_val pivot = arr[lo + (hi - lo)*7/16]; - j = hi; - - while (i <= j) { - while (i_less((&arr[i]), (&pivot))) ++i; - while (i_less((&pivot), (&arr[j]))) --j; - if (i <= j) { - c_swap(i_val, arr+i, arr+j); - ++i; --j; - } - } - if (j - lo > hi - i) { - c_swap(intptr_t, &lo, &i); - c_swap(intptr_t, &hi, &j); - } - - if (j - lo > 64) _cx_memb(_quicksort)(arr, lo, j); - else if (j > lo) _cx_memb(_insertion)(arr, lo, j); - lo = i; - } -} - -static inline void _cx_self(i_val arr[], intptr_t n) - { _cx_memb(_quicksort)(arr, 0, n - 1); } - -#include "../priv/template2.h" diff --git a/include/stc/algo/sort.h b/include/stc/algo/sort.h new file mode 100644 index 00000000..20b7e1b3 --- /dev/null +++ b/include/stc/algo/sort.h @@ -0,0 +1,100 @@ +/* MIT License + * + * Copyright (c) 2023 Tyge Løvset + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ +/* Generic Quicksort in C, performs as fast as c++ std::sort(). +template params: +#define i_val - value type [required] +#define i_less - less function. default: *x < *y +#define i_tag name - define namearray_qsort(). i_tag defaults {i_val} + +// test: +#include +#define i_val int +#include + +int main() { + int arr[] = {23, 321, 5434, 25, 245, 1, 654, 33, 543, 21}; + + intarray_qsort(arr, c_arraylen(arr)); + + for (int i = 0; i < c_arraylen(arr); i++) + printf(" %d", arr[i]); + puts(""); +} +*/ +#include "../ccommon.h" +#ifndef i_type + #define i_at(arr, idx) (&arr[idx]) + #ifndef i_tag + #define i_tag i_val + #endif + #define i_type c_PASTE(i_tag, array) + typedef i_val i_type; +#endif +#ifndef i_at + #define i_at(arr, idx) _cx_memb(_at_mut)(arr, idx) +#endif +#include "../priv/template.h" + + +static inline void _cx_memb(_insertsort_ij)(_cx_self* arr, intptr_t lo, intptr_t hi) { + for (intptr_t j = lo, i = lo + 1; i <= hi; j = i, ++i) { + i_val key = *i_at(arr, i); + while (j >= 0 && (i_less((&key), i_at(arr, j)))) { + *i_at(arr, j + 1) = *i_at(arr, j); + --j; + } + *i_at(arr, j + 1) = key; + } +} + +static inline void _cx_memb(_sort_ij)(_cx_self* arr, intptr_t lo, intptr_t hi) { + intptr_t i = lo, j; + while (lo < hi) { + i_val pivot = *i_at(arr, lo + (hi - lo)*7/16); + j = hi; + + while (i <= j) { + while (i_less(i_at(arr, i), (&pivot))) ++i; + while (i_less((&pivot), i_at(arr, j))) --j; + if (i <= j) { + c_swap(i_val, i_at(arr, i), i_at(arr, j)); + ++i; --j; + } + } + if (j - lo > hi - i) { + c_swap(intptr_t, &lo, &i); + c_swap(intptr_t, &hi, &j); + } + + if (j - lo > 64) _cx_memb(_sort_ij)(arr, lo, j); + else if (j > lo) _cx_memb(_insertsort_ij)(arr, lo, j); + lo = i; + } +} + +static inline void _cx_memb(_sort_n)(_cx_self* arr, intptr_t len) { + _cx_memb(_sort_ij)(arr, 0, len - 1); +} + +#include "../priv/template2.h" +#undef i_at diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index fd673696..07c72e2f 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -171,6 +171,16 @@ STC_INLINE char* cstrnstrn(const char *str, const char *needle, return NULL; } +STC_INLINE intptr_t cnextpow2(intptr_t n) { + n--; + n |= n >> 1, n |= n >> 2; + n |= n >> 4, n |= n >> 8; + n |= n >> 16; + #if INTPTR_SIZE == INT64_SIZE + n |= n >> 32; + #endif + return n + 1; +} /* Control block macros */ #define c_foreach(...) c_MACRO_OVERLOAD(c_foreach, __VA_ARGS__) diff --git a/include/stc/cdeq.h b/include/stc/cdeq.h index ff6e744f..80dd1dbe 100644 --- a/include/stc/cdeq.h +++ b/include/stc/cdeq.h @@ -20,166 +20,82 @@ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ -#include "ccommon.h" - -#ifndef CDEQ_H_INCLUDED -#include "forward.h" -#include -#include - -#define _it2_ptr(it1, it2) (it1.ref && !it2.ref ? it2.end : it2.ref) -#define _it_ptr(it) (it.ref ? it.ref : it.end) -#endif // CDEQ_H_INCLUDED - -#ifndef _i_prefix #define _i_prefix cdeq_ +#define _pop _pop_front +#ifdef i_more + #include "cqueue.h" + #define i_more +#else + #define i_more + #include "cqueue.h" #endif -#include "priv/template.h" - -#ifndef i_is_forward -_cx_deftypes(_c_cdeq_types, _cx_self, i_key); -#endif -typedef i_keyraw _cx_raw; - -STC_API _cx_self _cx_memb(_init)(void); -STC_API _cx_self _cx_memb(_with_capacity)(const intptr_t n); -STC_API bool _cx_memb(_reserve)(_cx_self* self, const intptr_t n); -STC_API void _cx_memb(_clear)(_cx_self* self); -STC_API void _cx_memb(_drop)(_cx_self* self); -STC_API _cx_value* _cx_memb(_push)(_cx_self* self, i_key value); -STC_API void _cx_memb(_shrink_to_fit)(_cx_self *self); -STC_INLINE void _cx_memb(_put_n)(_cx_self* self, const _cx_raw* raw, intptr_t n) - { while (n--) _cx_memb(_push)(self, i_keyfrom(*raw++)); } -STC_INLINE _cx_self _cx_memb(_from_n)(const _cx_raw* raw, intptr_t n) - { _cx_self cx = {0}; _cx_memb(_put_n)(&cx, raw, n); return cx; } -STC_INLINE void _cx_memb(_value_drop)(_cx_value* val) { i_keydrop(val); } -#if !defined _i_queue -#if !defined i_no_emplace -STC_API _cx_iter _cx_memb(_emplace_range)(_cx_self* self, _cx_value* pos, - const _cx_raw* p1, const _cx_raw* p2); -#endif // i_no_emplace - -#if !defined i_no_cmp || defined _i_has_eq -STC_API _cx_iter _cx_memb(_find_in)(_cx_iter p1, _cx_iter p2, _cx_raw raw); -#endif -#ifndef i_no_cmp -STC_API int _cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y); -#endif -STC_API _cx_value* _cx_memb(_push_front)(_cx_self* self, i_key value); -STC_API _cx_iter _cx_memb(_erase_range_p)(_cx_self* self, _cx_value* p1, _cx_value* p2); -STC_API _cx_iter _cx_memb(_insert_range)(_cx_self* self, _cx_value* pos, - const _cx_value* p1, const _cx_value* p2); -#endif // !_i_queue +#undef _pop -#if !defined i_no_emplace -STC_INLINE _cx_value* _cx_memb(_emplace)(_cx_self* self, _cx_raw raw) - { return _cx_memb(_push)(self, i_keyfrom(raw)); } -#endif +STC_API _cx_value* _cx_memb(_push_front)(_cx_self* self, i_key value); +STC_API _cx_iter _cx_memb(_insert_n)(_cx_self* self, intptr_t idx, const _cx_value* arr, intptr_t n); +STC_API _cx_iter _cx_memb(_emplace_n)(_cx_self* self, intptr_t idx, const _cx_raw* raw, intptr_t n); +STC_API _cx_iter _cx_memb(_insert_uninit)(_cx_self* self, intptr_t idx, intptr_t n); +STC_API void _cx_memb(_erase_n)(_cx_self* self, intptr_t idx, intptr_t n); -#if !defined i_no_clone -#if !defined _i_queue -STC_API _cx_iter _cx_memb(_copy_range)(_cx_self* self, _cx_value* pos, - const _cx_value* p1, const _cx_value* p2); +STC_INLINE const _cx_value* +_cx_memb(_at)(const _cx_self* self, intptr_t idx) + { return self->data + _cdeq_topos(self, idx); } -STC_INLINE void _cx_memb(_copy)(_cx_self *self, const _cx_self* other) { - if (self->data == other->data) return; - _cx_memb(_clear)(self); - _cx_memb(_copy_range)(self, self->data, - other->data, other->data + other->_len); - } -#endif // !_i_queue -STC_API _cx_self _cx_memb(_clone)(_cx_self cx); -STC_INLINE i_key _cx_memb(_value_clone)(i_key val) - { return i_keyclone(val); } -#endif // !i_no_clone -STC_INLINE intptr_t _cx_memb(_size)(const _cx_self* self) { return self->_len; } -STC_INLINE intptr_t _cx_memb(_capacity)(const _cx_self* self) { return self->_cap; } -STC_INLINE bool _cx_memb(_empty)(const _cx_self* self) { return !self->_len; } -STC_INLINE _cx_raw _cx_memb(_value_toraw)(const _cx_value* pval) { return i_keyto(pval); } -STC_INLINE _cx_value* _cx_memb(_front)(const _cx_self* self) { return self->data; } -STC_INLINE _cx_value* _cx_memb(_back)(const _cx_self* self) - { return self->data + self->_len - 1; } -STC_INLINE void _cx_memb(_pop_front)(_cx_self* self) // == _pop() when _i_queue - { i_keydrop(self->data); ++self->data; --self->_len; } +STC_INLINE _cx_value* +_cx_memb(_at_mut)(_cx_self* self, intptr_t idx) + { return self->data + _cdeq_topos(self, idx); } -STC_INLINE _cx_iter _cx_memb(_begin)(const _cx_self* self) { - intptr_t n = self->_len; - return c_LITERAL(_cx_iter){n ? self->data : NULL, self->data + n}; +STC_INLINE _cx_value* +_cx_memb(_push_back)(_cx_self* self, _cx_value val) { + return _cx_memb(_push)(self, val); } -STC_INLINE _cx_iter _cx_memb(_end)(const _cx_self* self) - { return c_LITERAL(_cx_iter){NULL, self->data + self->_len}; } - -STC_INLINE void _cx_memb(_next)(_cx_iter* it) - { if (++it->ref == it->end) it->ref = NULL; } - -STC_INLINE _cx_iter _cx_memb(_advance)(_cx_iter it, size_t n) - { if ((it.ref += n) >= it.end) it.ref = NULL; return it; } - -#if !defined _i_queue - -STC_INLINE intptr_t _cx_memb(_index)(const _cx_self* self, _cx_iter it) - { return (it.ref - self->data); } -STC_INLINE void _cx_memb(_pop_back)(_cx_self* self) - { _cx_value* p = &self->data[--self->_len]; i_keydrop(p); } - -STC_INLINE const _cx_value* _cx_memb(_at)(const _cx_self* self, const intptr_t idx) { - assert(idx < self->_len); return self->data + idx; -} -STC_INLINE _cx_value* _cx_memb(_at_mut)(_cx_self* self, const intptr_t idx) { - assert(idx < self->_len); return self->data + idx; +STC_INLINE void +_cx_memb(_pop_back)(_cx_self* self) { + assert(!_cx_memb(_empty)(self)); + self->end = (self->end - 1) & self->capmask; + i_keydrop((self->data + self->end)); } -STC_INLINE _cx_value* _cx_memb(_push_back)(_cx_self* self, i_key value) { - return _cx_memb(_push)(self, value); -} -STC_INLINE _cx_iter -_cx_memb(_insert)(_cx_self* self, const intptr_t idx, i_key value) { - return _cx_memb(_insert_range)(self, self->data + idx, &value, &value + 1); -} -STC_INLINE _cx_iter -_cx_memb(_insert_n)(_cx_self* self, const intptr_t idx, const _cx_value arr[], const intptr_t n) { - return _cx_memb(_insert_range)(self, self->data + idx, arr, arr + n); -} STC_INLINE _cx_iter -_cx_memb(_insert_at)(_cx_self* self, _cx_iter it, i_key value) { - return _cx_memb(_insert_range)(self, _it_ptr(it), &value, &value + 1); +_cx_memb(_insert_at)(_cx_self* self, _cx_iter it, const _cx_value val) { + intptr_t idx = _cdeq_toidx(self, it.pos); + return _cx_memb(_insert_n)(self, idx, &val, 1); } -STC_INLINE _cx_iter -_cx_memb(_erase_n)(_cx_self* self, const intptr_t idx, const intptr_t n) { - return _cx_memb(_erase_range_p)(self, self->data + idx, self->data + idx + n); -} STC_INLINE _cx_iter _cx_memb(_erase_at)(_cx_self* self, _cx_iter it) { - return _cx_memb(_erase_range_p)(self, it.ref, it.ref + 1); + _cx_memb(_erase_n)(self, _cdeq_toidx(self, it.pos), 1); + if (it.pos == self->end) it.ref = NULL; + return it; } + STC_INLINE _cx_iter -_cx_memb(_erase_range)(_cx_self* self, _cx_iter i1, _cx_iter i2) { - return _cx_memb(_erase_range_p)(self, i1.ref, _it2_ptr(i1, i2)); +_cx_memb(_erase_range)(_cx_self* self, _cx_iter it1, _cx_iter it2) { + intptr_t idx1 = _cdeq_toidx(self, it1.pos); + intptr_t idx2 = _cdeq_toidx(self, it2.pos); + _cx_memb(_erase_n)(self, idx1, idx2 - idx1); + if (it1.pos == self->end) it1.ref = NULL; + return it1; } #if !defined i_no_emplace STC_INLINE _cx_value* -_cx_memb(_emplace_front)(_cx_self* self, _cx_raw raw) { - return _cx_memb(_push_front)(self, i_keyfrom(raw)); -} +_cx_memb(_emplace_front)(_cx_self* self, const _cx_raw raw) + { return _cx_memb(_push_front)(self, i_keyfrom(raw)); } -STC_INLINE _cx_value* _cx_memb(_emplace_back)(_cx_self* self, _cx_raw raw) { - return _cx_memb(_push)(self, i_keyfrom(raw)); -} +STC_INLINE _cx_value* +_cx_memb(_emplace_back)(_cx_self* self, const _cx_raw raw) + { return _cx_memb(_push)(self, i_keyfrom(raw)); } STC_INLINE _cx_iter -_cx_memb(_emplace_n)(_cx_self* self, const intptr_t idx, const _cx_raw arr[], const intptr_t n) { - return _cx_memb(_emplace_range)(self, self->data + idx, arr, arr + n); -} -STC_INLINE _cx_iter -_cx_memb(_emplace_at)(_cx_self* self, _cx_iter it, _cx_raw raw) { - return _cx_memb(_emplace_range)(self, _it_ptr(it), &raw, &raw + 1); -} -#endif // !i_no_emplace +_cx_memb(_emplace_at)(_cx_self* self, _cx_iter it, const _cx_raw raw) + { return _cx_memb(_insert_at)(self, it, i_keyfrom(raw)); } +#endif -#if !defined i_no_cmp || defined _i_has_eq +#if defined _i_has_eq || defined _i_has_cmp +STC_API _cx_iter _cx_memb(_find_in)(_cx_iter p1, _cx_iter p2, _cx_raw raw); +STC_API bool _cx_memb(_eq)(const _cx_self* self, const _cx_self* other); STC_INLINE _cx_iter _cx_memb(_find)(const _cx_self* self, _cx_raw raw) { @@ -194,253 +110,88 @@ _cx_memb(_get)(const _cx_self* self, _cx_raw raw) { STC_INLINE _cx_value* _cx_memb(_get_mut)(_cx_self* self, _cx_raw raw) { return (_cx_value *) _cx_memb(_get)(self, raw); } - -STC_INLINE bool -_cx_memb(_eq)(const _cx_self* self, const _cx_self* other) { - if (self->_len != other->_len) return false; - for (intptr_t i = 0; i < self->_len; ++i) { - const _cx_raw _rx = i_keyto(self->data+i), _ry = i_keyto(other->data+i); - if (!(i_eq((&_rx), (&_ry)))) return false; - } - return true; -} #endif -#ifndef i_no_cmp - -STC_INLINE void -_cx_memb(_sort_range)(_cx_iter i1, _cx_iter i2, int(*cmp)(const _cx_value*, const _cx_value*)) { - qsort(i1.ref, (size_t)(_it2_ptr(i1, i2) - i1.ref), sizeof *i1.ref, - (int(*)(const void*, const void*)) cmp); -} - -STC_INLINE void -_cx_memb(_sort)(_cx_self* self) { - _cx_memb(_sort_range)(_cx_memb(_begin)(self), _cx_memb(_end)(self), _cx_memb(_value_cmp)); -} -#endif // !c_no_cmp -#endif // _i_queue /* -------------------------- IMPLEMENTATION ------------------------- */ #if defined(i_implement) -#define _cdeq_nfront(self) ((self)->data - (self)->_base) - -STC_DEF _cx_self -_cx_memb(_init)(void) { - _cx_self cx = {NULL}; - return cx; -} - -STC_DEF void -_cx_memb(_clear)(_cx_self* self) { - if (self->_cap) { - for (_cx_value *p = self->data, *q = p + self->_len; p != q; ) - { --q; i_keydrop(q); } - self->_len = 0; - self->data = self->_base; - } -} - -STC_DEF void -_cx_memb(_shrink_to_fit)(_cx_self *self) { - if (self->_len != self->_cap) { - c_memmove(self->_base, self->data, self->_len*c_sizeof(i_key)); - _cx_value* d = (_cx_value*)i_realloc(self->_base, self->_len*c_sizeof(i_key)); - if (d) { - self->_base = d; - self->_cap = self->_len; - } - self->data = self->_base; - } -} - -STC_DEF void -_cx_memb(_drop)(_cx_self* self) { - if (self->_base) { - _cx_memb(_clear)(self); - i_free(self->_base); - } -} - -static intptr_t -_cx_memb(_realloc_)(_cx_self* self, const intptr_t n) { - const intptr_t cap = (intptr_t)((float)self->_len*1.7f) + n + 7; - const intptr_t nfront = _cdeq_nfront(self); - _cx_value* d = (_cx_value*)i_realloc(self->_base, cap*c_sizeof(i_key)); - if (!d) - return 0; - self->_cap = cap; - self->_base = d; - self->data = d + nfront; - return cap; -} - -static bool -_cx_memb(_expand_right_half_)(_cx_self* self, const intptr_t idx, const intptr_t n) { - const intptr_t sz = self->_len, cap = self->_cap; - const intptr_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront; - if (nback >= n || (intptr_t)((float)sz*1.3f) + n > cap) { - if (!_cx_memb(_realloc_)(self, n)) - return false; - c_memmove(self->data + idx + n, self->data + idx, (sz - idx)*c_sizeof(i_key)); - } else { -#if !defined _i_queue - const intptr_t unused = cap - (sz + n); - const intptr_t pos = (nfront*2 < unused) ? nfront : unused/2; -#else - const intptr_t pos = 0; -#endif - c_memmove(self->_base + pos, self->data, idx*c_sizeof(i_key)); - c_memmove(self->data + pos + idx + n, self->data + idx, (sz - idx)*c_sizeof(i_key)); - self->data = self->_base + pos; - } - return true; -} - -STC_DEF _cx_self -_cx_memb(_with_capacity)(const intptr_t n) { - _cx_self cx = _cx_memb(_init)(); - _cx_memb(_expand_right_half_)(&cx, 0, n); - return cx; -} - -STC_DEF bool -_cx_memb(_reserve)(_cx_self* self, const intptr_t n) { - const intptr_t sz = self->_len; - return n <= sz || _cx_memb(_expand_right_half_)(self, sz, n - sz); -} STC_DEF _cx_value* -_cx_memb(_push)(_cx_self* self, i_key value) { - if (_cdeq_nfront(self) + self->_len == self->_cap) - _cx_memb(_expand_right_half_)(self, self->_len, 1); - _cx_value *v = self->data + self->_len++; +_cx_memb(_push_front)(_cx_self* self, i_key value) { + intptr_t start = (self->start - 1) & self->capmask; + if (start == self->end) { // full + _cx_memb(_reserve)(self, self->capmask + 3); // => 2x expand + start = (self->start - 1) & self->capmask; + } + _cx_value *v = self->data + start; + self->start = start; *v = value; return v; } -#if !defined i_no_clone -STC_DEF _cx_self -_cx_memb(_clone)(_cx_self cx) { - _cx_self out = _cx_memb(_with_capacity)(cx._len); - if (out._base) - for (intptr_t i = 0; i < cx._len; ++i) - out.data[i] = i_keyclone(cx.data[i]); - return out; -} -#endif - -#if !defined _i_queue - -static void -_cx_memb(_expand_left_half_)(_cx_self* self, const intptr_t idx, const intptr_t n) { - intptr_t cap = self->_cap; - const intptr_t sz = self->_len; - const intptr_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront; - if (nfront >= n) { - self->data = (_cx_value *)c_memmove(self->data - n, self->data, idx*c_sizeof(i_key)); - } else { - if ((intptr_t)((float)sz*1.3f) + n > cap) - cap = _cx_memb(_realloc_)(self, n); - const intptr_t unused = cap - (sz + n); - const intptr_t pos = (nback*2 < unused) ? unused - nback : unused/2; - c_memmove(self->_base + pos + idx + n, self->data + idx, (sz - idx)*c_sizeof(i_key)); - self->data = (_cx_value *)c_memmove(self->_base + pos, self->data, idx*c_sizeof(i_key)); - } -} - -static _cx_iter -_cx_memb(_insert_uninit)(_cx_self* self, _cx_value* pos, const intptr_t n) { - if (n) { - if (!pos) pos = self->data + self->_len; - const intptr_t idx = (pos - self->data); - if (idx*2 < self->_len) - _cx_memb(_expand_left_half_)(self, idx, n); - else - _cx_memb(_expand_right_half_)(self, idx, n); - self->_len += n; - pos = self->data + idx; - } - return c_LITERAL(_cx_iter){pos, self->data + self->_len}; -} - -STC_DEF _cx_value* -_cx_memb(_push_front)(_cx_self* self, i_key value) { - if (self->data == self->_base) - _cx_memb(_expand_left_half_)(self, 0, 1); - else - --self->data; - ++self->_len; - *self->data = value; - return self->data; +STC_DEF void +_cx_memb(_erase_n)(_cx_self* self, const intptr_t idx, const intptr_t n) { + const intptr_t len = _cx_memb(_size)(self); + for (intptr_t i = idx + n - 1; i >= idx; --i) + i_keydrop(_cx_memb(_at_mut)(self, i)); + for (intptr_t i = idx, j = i + n; j < len; ++i, ++j) + *_cx_memb(_at_mut)(self, i) = *_cx_memb(_at)(self, j); + self->end = (self->end - n) & self->capmask; } STC_DEF _cx_iter -_cx_memb(_insert_range)(_cx_self* self, _cx_value* pos, - const _cx_value* p1, const _cx_value* p2) { - _cx_iter it = _cx_memb(_insert_uninit)(self, pos, (p2 - p1)); - if (it.ref) - c_memcpy(it.ref, p1, (p2 - p1)*c_sizeof *p1); +_cx_memb(_insert_uninit)(_cx_self* self, const intptr_t idx, const intptr_t n) { + const intptr_t len = _cx_memb(_size)(self); + _cx_iter it = {._s=self}; + if (len + n > self->capmask) + if (!_cx_memb(_reserve)(self, len + n)) + return it; + for (intptr_t j = len - 1, i = j + n; j >= idx; --j, --i) + *_cx_memb(_at_mut)(self, i) = *_cx_memb(_at)(self, j); + self->end = (self->end + n) & self->capmask; + it.pos = _cdeq_topos(self, idx); + it.ref = self->data + it.pos; return it; } STC_DEF _cx_iter -_cx_memb(_erase_range_p)(_cx_self* self, _cx_value* p1, _cx_value* p2) { - assert(p1 && p2); - intptr_t len = p2 - p1; - _cx_value* p = p1, *end = self->data + self->_len; - for (; p != p2; ++p) - { i_keydrop(p); } - c_memmove(p1, p2, (end - p2)*c_sizeof *p1); - self->_len -= len; - return c_LITERAL(_cx_iter){p2 == end ? NULL : p1, end - len}; -} - -#if !defined i_no_clone -STC_DEF _cx_iter -_cx_memb(_copy_range)(_cx_self* self, _cx_value* pos, - const _cx_value* p1, const _cx_value* p2) { - _cx_iter it = _cx_memb(_insert_uninit)(self, pos, (p2 - p1)); - if (it.ref) - for (_cx_value* p = it.ref; p1 != p2; ++p1) - *p++ = i_keyclone((*p1)); +_cx_memb(_insert_n)(_cx_self* self, const intptr_t idx, const _cx_value* arr, const intptr_t n) { + _cx_iter it = _cx_memb(_insert_uninit)(self, idx, n); + for (intptr_t i = idx, j = 0; j < n; ++i, ++j) + *_cx_memb(_at_mut)(self, i) = arr[j]; return it; } -#endif // !i_no_clone -#if !defined i_no_emplace STC_DEF _cx_iter -_cx_memb(_emplace_range)(_cx_self* self, _cx_value* pos, - const _cx_raw* p1, const _cx_raw* p2) { - _cx_iter it = _cx_memb(_insert_uninit)(self, pos, (p2 - p1)); - if (it.ref) - for (_cx_value* p = it.ref; p1 != p2; ++p1) - *p++ = i_keyfrom((*p1)); +_cx_memb(_emplace_n)(_cx_self* self, const intptr_t idx, const _cx_raw* raw, const intptr_t n) { + _cx_iter it = _cx_memb(_insert_uninit)(self, idx, n); + for (intptr_t i = idx, j = 0; j < n; ++i, ++j) + *_cx_memb(_at_mut)(self, i) = i_keyfrom(raw[j]); return it; } -#endif // !i_no_emplace -#if !defined i_no_cmp || defined _i_has_eq +#if defined _i_has_eq || defined _i_has_cmp STC_DEF _cx_iter _cx_memb(_find_in)(_cx_iter i1, _cx_iter i2, _cx_raw raw) { - const _cx_value* p2 = _it2_ptr(i1, i2); - for (; i1.ref != p2; ++i1.ref) { + for (; i1.ref; _cx_memb(_next)(&i1)) { const _cx_raw r = i_keyto(i1.ref); if (i_eq((&raw), (&r))) - return i1; + break; } - i2.ref = NULL; - return i2; + return i1; } -#endif -#ifndef i_no_cmp -STC_DEF int -_cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y) { - const _cx_raw rx = i_keyto(x); - const _cx_raw ry = i_keyto(y); - return i_cmp((&rx), (&ry)); + +STC_DEF bool +_cx_memb(_eq)(const _cx_self* self, const _cx_self* other) { + if (_cx_memb(_size)(self) != _cx_memb(_size)(other)) return false; + for (_cx_iter i = _cx_memb(_begin)(self), j = _cx_memb(_begin)(other); + i.ref; _cx_memb(_next)(&i), _cx_memb(_next)(&j)) + { + const _cx_raw _rx = i_keyto(i.ref), _ry = i_keyto(j.ref); + if (!(i_eq((&_rx), (&_ry)))) return false; + } + return true; } -#endif // !c_no_cmp -#endif // !_i_queue +#endif #endif // IMPLEMENTATION #define CDEQ_H_INCLUDED #include "priv/template2.h" diff --git a/include/stc/clist.h b/include/stc/clist.h index 65a1ac87..128e848d 100644 --- a/include/stc/clist.h +++ b/include/stc/clist.h @@ -109,8 +109,9 @@ STC_API _cx_value* _cx_memb(_push_back_node)(_cx_self* self, _cx_node* node STC_API _cx_value* _cx_memb(_insert_after_node)(_cx_self* self, _cx_node* ref, _cx_node* node); STC_API _cx_node* _cx_memb(_unlink_after_node)(_cx_self* self, _cx_node* ref); STC_API void _cx_memb(_erase_after_node)(_cx_self* self, _cx_node* ref); -STC_INLINE _cx_node* _cx_memb(_get_node)(_cx_value* vp) { return _clist_tonode(vp); } - +STC_INLINE _cx_node* _cx_memb(_get_node)(_cx_value* pval) { return _clist_tonode(pval); } +STC_INLINE _cx_node* _cx_memb(_unlink_front_node)(_cx_self* self) + { return _cx_memb(_unlink_after_node)(self, self->last); } #if !defined i_no_clone STC_API _cx_self _cx_memb(_clone)(_cx_self cx); STC_INLINE i_key _cx_memb(_value_clone)(i_key val) { return i_keyclone(val); } @@ -144,10 +145,10 @@ STC_INLINE _cx_value* _cx_memb(_push)(_cx_self* self, i_key value) { return _cx_memb(_push_back)(self, value); } STC_INLINE void _cx_memb(_pop_front)(_cx_self* self) { assert(!_cx_memb(_empty)(self)); _cx_memb(_erase_after_node)(self, self->last); } -STC_INLINE _cx_node* _cx_memb(_unlink_node_front)(_cx_self* self) - { return _cx_memb(_unlink_after_node)(self, self->last); } STC_INLINE _cx_value* _cx_memb(_front)(const _cx_self* self) { return &self->last->next->value; } STC_INLINE _cx_value* _cx_memb(_back)(const _cx_self* self) { return &self->last->value; } +STC_INLINE _cx_raw _cx_memb(_value_toraw)(const _cx_value* pval) { return i_keyto(pval); } +STC_INLINE void _cx_memb(_value_drop)(_cx_value* pval) { i_keydrop(pval); } STC_INLINE intptr_t _cx_memb(_count)(const _cx_self* self) { diff --git a/include/stc/cmap.h b/include/stc/cmap.h index ec3238f6..4ba6156b 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -276,13 +276,6 @@ STC_INLINE intptr_t fastrange_1(uint64_t x, uint64_t n) STC_INLINE intptr_t fastrange_2(uint64_t x, uint64_t n) { return (intptr_t)(x & (n - 1)); } // n power of 2. -STC_INLINE uint64_t next_power_of_2(uint64_t n) { - n--; - n |= n >> 1, n |= n >> 2; - n |= n >> 4, n |= n >> 8; - n |= n >> 16, n |= n >> 32; - return n + 1; -} #endif // CMAP_H_INCLUDED STC_DEF _cx_iter _cx_memb(_begin)(const _cx_self* self) { @@ -422,7 +415,7 @@ _cx_memb(_reserve)(_cx_self* self, const intptr_t _newcap) { return true; intptr_t _newbucks = (intptr_t)((float)_newcap / (i_max_load_factor)) | 1; #if i_expandby == 2 - _newbucks = (intptr_t)next_power_of_2((uint64_t)_newbucks); + _newbucks = cnextpow2(_newbucks); #endif _cx_self m = { (_cx_value *)i_malloc(_newbucks*c_sizeof(_cx_value)), diff --git a/include/stc/cqueue.h b/include/stc/cqueue.h index 254bc834..09a747e5 100644 --- a/include/stc/cqueue.h +++ b/include/stc/cqueue.h @@ -20,44 +20,198 @@ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ -// STC queue -/* -#include -#include - -#define i_key int -#include - -int main() { - int n = 10000000; - crand_t rng = crand_init(1234); - crand_unif_t dist = crand_unif_init(0, n); - - c_auto (cqueue_int, Q) - { - // Push ten million random numbers onto the queue. - for (int i=0; i0; --i) { - int r = crand_unif(&rng, &dist); - if (r & 1) - ++n, cqueue_int_push(&Q, r); - else - --n, cqueue_int_pop(&Q); - } - printf("after: size, capacity: %d, %d\n", n, cqueue_int_size(&Q), cqueue_int_capacity(&Q)); +#include "ccommon.h" + +#ifndef CQUEUE_H_INCLUDED +#include "forward.h" +#include +#include +#endif // CQUEUE_H_INCLUDED + +#ifndef _i_prefix +#define _i_prefix cqueue_ +#endif +#include "priv/template.h" + +#ifndef i_is_forward +_cx_deftypes(_c_cdeq_types, _cx_self, i_key); +#endif +typedef i_keyraw _cx_raw; + +STC_API _cx_self _cx_memb(_with_capacity)(const intptr_t n); +STC_API bool _cx_memb(_reserve)(_cx_self* self, const intptr_t n); +STC_API void _cx_memb(_clear)(_cx_self* self); +STC_API void _cx_memb(_drop)(_cx_self* self); +STC_API _cx_value* _cx_memb(_push)(_cx_self* self, i_key value); // push_back +STC_API void _cx_memb(_shrink_to_fit)(_cx_self *self); +STC_API _cx_iter _cx_memb(_advance)(_cx_iter it, intptr_t n); + +#define _cdeq_toidx(self, pos) (((pos) - (self)->start) & (self)->capmask) +#define _cdeq_topos(self, idx) (((self)->start + (idx)) & (self)->capmask) + +STC_INLINE _cx_self _cx_memb(_init)(void) + { _cx_self cx = {0}; return cx; } +STC_INLINE void _cx_memb(_put_n)(_cx_self* self, const _cx_raw* raw, intptr_t n) + { while (n--) _cx_memb(_push)(self, i_keyfrom(*raw++)); } +STC_INLINE _cx_self _cx_memb(_from_n)(const _cx_raw* raw, intptr_t n) + { _cx_self cx = {0}; _cx_memb(_put_n)(&cx, raw, n); return cx; } +STC_INLINE void _cx_memb(_value_drop)(_cx_value* val) { i_keydrop(val); } + +#if !defined i_no_emplace +STC_INLINE _cx_value* _cx_memb(_emplace)(_cx_self* self, _cx_raw raw) + { return _cx_memb(_push)(self, i_keyfrom(raw)); } +#endif + +#if !defined i_no_clone +STC_API _cx_self _cx_memb(_clone)(_cx_self cx); +STC_INLINE i_key _cx_memb(_value_clone)(i_key val) + { return i_keyclone(val); } +#endif // !i_no_clone +STC_INLINE intptr_t _cx_memb(_size)(const _cx_self* self) + { return _cdeq_toidx(self, self->end); } +STC_INLINE intptr_t _cx_memb(_capacity)(const _cx_self* self) + { return self->capmask; } +STC_INLINE bool _cx_memb(_empty)(const _cx_self* self) + { return self->start == self->end; } +STC_INLINE _cx_raw _cx_memb(_value_toraw)(const _cx_value* pval) + { return i_keyto(pval); } + +STC_INLINE _cx_value* +_cx_memb(_front)(const _cx_self* self) + { return self->data + self->start; } + +STC_INLINE _cx_value* +_cx_memb(_back)(const _cx_self* self) + { return self->data + ((self->end - 1) & self->capmask); } + +STC_INLINE void +_cx_memb(_pop)(_cx_self* self) { // pop_front + c_ASSERT(!_cx_memb(_empty)(self)); + i_keydrop((self->data + self->start)); + self->start = (self->start + 1) & self->capmask; +} + +STC_INLINE void _cx_memb(_copy)(_cx_self* self, const _cx_self* other) { + if (self->data == other->data) return; + _cx_memb(_drop)(self); + *self = _cx_memb(_clone)(*other); +} + +STC_INLINE _cx_iter +_cx_memb(_begin)(const _cx_self* self) { + return c_LITERAL(_cx_iter){ + _cx_memb(_empty)(self) ? NULL : self->data + self->start, + self->start, self + }; +} + +STC_INLINE _cx_iter +_cx_memb(_end)(const _cx_self* self) + { return c_LITERAL(_cx_iter){NULL, self->end, self}; } + +STC_INLINE void +_cx_memb(_next)(_cx_iter* it) { + if (it->pos != it->_s->capmask) { ++it->ref; ++it->pos; } + else { it->ref -= it->pos; it->pos = 0; } + if (it->pos == it->_s->end) it->ref = NULL; +} + +/* -------------------------- IMPLEMENTATION ------------------------- */ +#if defined(i_implement) + +STC_DEF _cx_iter _cx_memb(_advance)(_cx_iter it, intptr_t n) { + intptr_t len = _cx_memb(_size)(it._s); + intptr_t pos = it.pos, idx = _cdeq_toidx(it._s, pos); + it.pos = (pos + n) & it._s->capmask; + it.ref += it.pos - pos; + if (!c_LTu(idx + n, len)) it.ref = NULL; + return it; +} + +STC_DEF void +_cx_memb(_clear)(_cx_self* self) { + c_foreach (i, _cx_self, *self) + { i_keydrop(i.ref); } + self->start = 0, self->end = 0; +} + +STC_DEF void +_cx_memb(_drop)(_cx_self* self) { + _cx_memb(_clear)(self); + i_free(self->data); +} + +STC_DEF _cx_self +_cx_memb(_with_capacity)(const intptr_t n) { + _cx_self cx = {0}; + _cx_memb(_reserve)(&cx, n); + return cx; +} + +STC_DEF bool +_cx_memb(_reserve)(_cx_self* self, const intptr_t n) { + if (n <= self->capmask) + return true; + intptr_t oldcap = self->capmask + 1, newcap = cnextpow2(n + 1); + _cx_value* data = (_cx_value *)i_realloc(self->data, newcap*c_sizeof *self->data); + if (!data) + return false; + intptr_t head = oldcap - self->start; + if (self->start < self->end || self->start == 0) + ; + else if (head < self->end) { + self->start = newcap - head; + c_memmove(data + self->start, data + oldcap - head, head*c_sizeof *data); + } else { + c_memmove(data + oldcap, data, self->end*c_sizeof *data); + self->end += oldcap; } + self->capmask = newcap - 1; + self->data = data; + return true; } -*/ -#define _i_prefix cqueue_ -#define _i_queue -#define _pop_front _pop +STC_DEF _cx_value* +_cx_memb(_push)(_cx_self* self, i_key value) { // push_back + intptr_t end = (self->end + 1) & self->capmask; + if (end == self->start) { // full + _cx_memb(_reserve)(self, self->capmask + 3); // => 2x expand + end = (self->end + 1) & self->capmask; + } + _cx_value *v = self->data + self->end; + self->end = end; + *v = value; + return v; +} + +STC_DEF void +_cx_memb(_shrink_to_fit)(_cx_self *self) { + intptr_t sz = _cx_memb(_size)(self), j = 0; + if (sz > self->capmask/2) + return; + _cx_self out = _cx_memb(_with_capacity)(sz); + if (!out.data) + return; + c_foreach (i, _cx_self, *self) + out.data[j++] = *i.ref; + out.end = sz; + i_free(self->data); + *self = out; +} -#include "cdeq.h" +#if !defined i_no_clone +STC_DEF _cx_self +_cx_memb(_clone)(_cx_self cx) { + intptr_t sz = _cx_memb(_size)(&cx), j = 0; + _cx_self out = _cx_memb(_with_capacity)(sz); + if (out.data) + c_foreach (i, _cx_self, cx) + out.data[j++] = i_keyclone((*i.ref)); + out.end = sz; + return out; +} -#undef _pop_front -#undef _i_queue +#endif // i_no_clone +#endif // IMPLEMENTATION +#include "priv/template2.h" +#define CQUEUE_H_INCLUDED diff --git a/include/stc/cvec.h b/include/stc/cvec.h index 3cbd90b7..a7eb1a05 100644 --- a/include/stc/cvec.h +++ b/include/stc/cvec.h @@ -81,10 +81,8 @@ STC_API void _cx_memb(_clear)(_cx_self* self); STC_API bool _cx_memb(_reserve)(_cx_self* self, intptr_t cap); STC_API bool _cx_memb(_resize)(_cx_self* self, intptr_t size, i_key null); STC_API _cx_value* _cx_memb(_push)(_cx_self* self, i_key value); -STC_API _cx_iter _cx_memb(_erase_range_p)(_cx_self* self, _cx_value* p1, _cx_value* p2); -STC_API _cx_iter _cx_memb(_insert_range)(_cx_self* self, _cx_value* pos, - const _cx_value* p1, const _cx_value* p2); -STC_API _cx_iter _cx_memb(_insert_uninit)(_cx_self* self, _cx_value* pos, const intptr_t n); +STC_API _cx_iter _cx_memb(_erase_n)(_cx_self* self, intptr_t idx, intptr_t n); +STC_API _cx_iter _cx_memb(_insert_uninit)(_cx_self* self, intptr_t idx, intptr_t n); #if !defined i_no_cmp || defined _i_has_eq STC_API _cx_iter _cx_memb(_find_in)(_cx_iter it1, _cx_iter it2, _cx_raw raw); #endif @@ -95,26 +93,23 @@ STC_API _cx_iter _cx_memb(_binary_search_in)(_cx_iter it1, _cx_iter it2, STC_INLINE void _cx_memb(_value_drop)(_cx_value* val) { i_keydrop(val); } #if !defined i_no_emplace -STC_API _cx_iter _cx_memb(_emplace_range)(_cx_self* self, _cx_value* pos, - const _cx_raw* p1, const _cx_raw* p2); -STC_INLINE _cx_value* _cx_memb(_emplace)(_cx_self* self, _cx_raw raw) - { return _cx_memb(_push)(self, i_keyfrom(raw)); } -STC_INLINE _cx_value* _cx_memb(_emplace_back)(_cx_self* self, _cx_raw raw) - { return _cx_memb(_push)(self, i_keyfrom(raw)); } -STC_INLINE _cx_iter -_cx_memb(_emplace_n)(_cx_self* self, const intptr_t idx, const _cx_raw arr[], const intptr_t n) { - return _cx_memb(_emplace_range)(self, self->data + idx, arr, arr + n); +STC_API _cx_iter +_cx_memb(_emplace_n)(_cx_self* self, intptr_t idx, const _cx_raw raw[], intptr_t n); + +STC_INLINE _cx_value* _cx_memb(_emplace)(_cx_self* self, _cx_raw raw) { + return _cx_memb(_push)(self, i_keyfrom(raw)); } -STC_INLINE _cx_iter -_cx_memb(_emplace_at)(_cx_self* self, _cx_iter it, _cx_raw raw) { - return _cx_memb(_emplace_range)(self, _it_ptr(it), &raw, &raw + 1); +STC_INLINE _cx_value* _cx_memb(_emplace_back)(_cx_self* self, _cx_raw raw) { + return _cx_memb(_push)(self, i_keyfrom(raw)); +} +STC_INLINE _cx_iter _cx_memb(_emplace_at)(_cx_self* self, _cx_iter it, _cx_raw raw) { + return _cx_memb(_emplace_n)(self, _it_ptr(it) - self->data, &raw, 1); } #endif // !i_no_emplace #if !defined i_no_clone STC_API _cx_self _cx_memb(_clone)(_cx_self cx); -STC_API _cx_iter _cx_memb(_copy_range)(_cx_self* self, _cx_value* pos, - const _cx_value* p1, const _cx_value* p2); +STC_API _cx_iter _cx_memb(_copy_n)(_cx_self* self, intptr_t idx, const _cx_value arr[], intptr_t n); STC_INLINE void _cx_memb(_put_n)(_cx_self* self, const _cx_raw* raw, intptr_t n) { while (n--) _cx_memb(_push)(self, i_keyfrom(*raw++)); } STC_INLINE _cx_self _cx_memb(_from_n)(const _cx_raw* raw, intptr_t n) @@ -124,8 +119,7 @@ STC_INLINE i_key _cx_memb(_value_clone)(_cx_value val) STC_INLINE void _cx_memb(_copy)(_cx_self* self, const _cx_self* other) { if (self->data == other->data) return; _cx_memb(_clear)(self); - _cx_memb(_copy_range)(self, self->data, other->data, - other->data + other->_len); + _cx_memb(_copy_n)(self, 0, other->data, other->_len); } #endif // !i_no_clone @@ -161,31 +155,29 @@ _cx_memb(_shrink_to_fit)(_cx_self* self) { _cx_memb(_reserve)(self, _cx_memb(_size)(self)); } - -STC_INLINE _cx_iter -_cx_memb(_insert)(_cx_self* self, const intptr_t idx, i_key value) { - return _cx_memb(_insert_range)(self, self->data + idx, &value, &value + 1); -} STC_INLINE _cx_iter _cx_memb(_insert_n)(_cx_self* self, const intptr_t idx, const _cx_value arr[], const intptr_t n) { - return _cx_memb(_insert_range)(self, self->data + idx, arr, arr + n); + _cx_iter it = _cx_memb(_insert_uninit)(self, idx, n); + if (it.ref) + c_memcpy(it.ref, arr, n*c_sizeof *arr); + return it; } STC_INLINE _cx_iter -_cx_memb(_insert_at)(_cx_self* self, _cx_iter it, i_key value) { - return _cx_memb(_insert_range)(self, _it_ptr(it), &value, &value + 1); +_cx_memb(_insert)(_cx_self* self, const intptr_t idx, const i_key value) { + return _cx_memb(_insert_n)(self, idx, &value, 1); } - STC_INLINE _cx_iter -_cx_memb(_erase_n)(_cx_self* self, const intptr_t idx, const intptr_t n) { - return _cx_memb(_erase_range_p)(self, self->data + idx, self->data + idx + n); +_cx_memb(_insert_at)(_cx_self* self, _cx_iter it, const i_key value) { + return _cx_memb(_insert_n)(self, _it_ptr(it) - self->data, &value, 1); } + STC_INLINE _cx_iter _cx_memb(_erase_at)(_cx_self* self, _cx_iter it) { - return _cx_memb(_erase_range_p)(self, it.ref, it.ref + 1); + return _cx_memb(_erase_n)(self, it.ref - self->data, 1); } STC_INLINE _cx_iter _cx_memb(_erase_range)(_cx_self* self, _cx_iter i1, _cx_iter i2) { - return _cx_memb(_erase_range_p)(self, i1.ref, _it2_ptr(i1, i2)); + return _cx_memb(_erase_n)(self, i1.ref - self->data, _it2_ptr(i1, i2) - i1.ref); } STC_INLINE const _cx_value* @@ -329,73 +321,58 @@ _cx_memb(_push)(_cx_self* self, i_key value) { } STC_DEF _cx_iter -_cx_memb(_insert_uninit)(_cx_self* self, _cx_value* pos, const intptr_t n) { - if (n) { - if (!pos) pos = self->data + self->_len; - const intptr_t idx = (pos - self->data); - if (self->_len + n > self->_cap) { - if (!_cx_memb(_reserve)(self, self->_len*3/2 + n)) - return _cx_memb(_end)(self); - pos = self->data + idx; - } - c_memmove(pos + n, pos, (self->_len - idx)*c_sizeof *pos); - self->_len += n; - } +_cx_memb(_insert_uninit)(_cx_self* self, const intptr_t idx, const intptr_t n) { + if (self->_len + n > self->_cap) + if (!_cx_memb(_reserve)(self, self->_len*3/2 + n)) + return _cx_memb(_end)(self); + + _cx_value* pos = self->data + idx; + c_memmove(pos + n, pos, (self->_len - idx)*c_sizeof *pos); + self->_len += n; return c_LITERAL(_cx_iter){pos, self->data + self->_len}; } STC_DEF _cx_iter -_cx_memb(_insert_range)(_cx_self* self, _cx_value* pos, - const _cx_value* p1, const _cx_value* p2) { - _cx_iter it = _cx_memb(_insert_uninit)(self, pos, (p2 - p1)); - if (it.ref) - c_memcpy(it.ref, p1, (p2 - p1)*c_sizeof *p1); - return it; -} - -STC_DEF _cx_iter -_cx_memb(_erase_range_p)(_cx_self* self, _cx_value* p1, _cx_value* p2) { - intptr_t len = (p2 - p1); - _cx_value* p = p1, *end = self->data + self->_len; - for (; p != p2; ++p) +_cx_memb(_erase_n)(_cx_self* self, const intptr_t idx, const intptr_t len) { + _cx_value* d = self->data + idx, *p = d, *end = self->data + self->_len; + for (intptr_t i = 0; i < len; ++i, ++p) { i_keydrop(p); } - c_memmove(p1, p2, (end - p2)*c_sizeof *p1); + c_memmove(d, p, (end - p)*c_sizeof *d); self->_len -= len; - return c_LITERAL(_cx_iter){p2 == end ? NULL : p1, end - len}; + return c_LITERAL(_cx_iter){p == end ? NULL : d, end - len}; } #if !defined i_no_clone STC_DEF _cx_self _cx_memb(_clone)(_cx_self cx) { _cx_self out = _cx_memb(_init)(); - _cx_memb(_copy_range)(&out, out.data, cx.data, cx.data + cx._len); + _cx_memb(_copy_n)(&out, 0, cx.data, cx._len); return out; } STC_DEF _cx_iter -_cx_memb(_copy_range)(_cx_self* self, _cx_value* pos, - const _cx_value* p1, const _cx_value* p2) { - _cx_iter it = _cx_memb(_insert_uninit)(self, pos, (p2 - p1)); +_cx_memb(_copy_n)(_cx_self* self, const intptr_t idx, + const _cx_value arr[], const intptr_t n) { + _cx_iter it = _cx_memb(_insert_uninit)(self, idx, n); if (it.ref) - for (_cx_value* p = it.ref; p1 != p2; ++p1) - *p++ = i_keyclone((*p1)); + for (_cx_value* p = it.ref, *q = p + n; p != q; ++arr) + *p++ = i_keyclone((*arr)); return it; } #endif // !i_no_clone #if !defined i_no_emplace STC_DEF _cx_iter -_cx_memb(_emplace_range)(_cx_self* self, _cx_value* pos, - const _cx_raw* p1, const _cx_raw* p2) { - _cx_iter it = _cx_memb(_insert_uninit)(self, pos, (p2 - p1)); +_cx_memb(_emplace_n)(_cx_self* self, const intptr_t idx, const _cx_raw raw[], intptr_t n) { + _cx_iter it = _cx_memb(_insert_uninit)(self, idx, n); if (it.ref) - for (_cx_value* p = it.ref; p1 != p2; ++p1) - *p++ = i_keyfrom((*p1)); + for (_cx_value* p = it.ref; n--; ++raw, ++p) + *p = i_keyfrom((*raw)); return it; } #endif // !i_no_emplace - #if !defined i_no_cmp || defined _i_has_eq + STC_DEF _cx_iter _cx_memb(_find_in)(_cx_iter i1, _cx_iter i2, _cx_raw raw) { const _cx_value* p2 = _it2_ptr(i1, i2); diff --git a/include/stc/forward.h b/include/stc/forward.h index b534e48b..9eafb857 100644 --- a/include/stc/forward.h +++ b/include/stc/forward.h @@ -81,12 +81,17 @@ typedef union { #define _c_cdeq_types(SELF, VAL) \ typedef VAL SELF##_value; \ - typedef struct { SELF##_value *ref, *end; } SELF##_iter; \ \ typedef struct SELF { \ - SELF##_value *_base, *data; \ - intptr_t _len, _cap; \ - } SELF + SELF##_value *data; \ + intptr_t start, end, capmask; \ + } SELF; \ +\ + typedef struct { \ + SELF##_value *ref; \ + intptr_t pos; \ + const SELF* _s; \ + } SELF##_iter #define _c_clist_types(SELF, VAL) \ typedef VAL SELF##_value; \ diff --git a/include/stc/priv/template.h b/include/stc/priv/template.h index 2605a434..f70281c7 100644 --- a/include/stc/priv/template.h +++ b/include/stc/priv/template.h @@ -20,9 +20,7 @@ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ -#ifdef _i_template - #error template.h already included -#endif +#ifndef _i_template #define _i_template #ifndef STC_TEMPLATE_H_INCLUDED @@ -107,6 +105,9 @@ #ifdef i_eq #define _i_has_eq #endif +#if defined i_cmp || defined i_less + #define _i_has_cmp +#endif #if defined i_key_str #define i_keyclass cstr @@ -288,3 +289,4 @@ #ifndef _i_has_from #define i_no_emplace #endif +#endif diff --git a/include/stc/priv/template2.h b/include/stc/priv/template2.h index 2e8a6c8d..66ed7739 100644 --- a/include/stc/priv/template2.h +++ b/include/stc/priv/template2.h @@ -20,6 +20,9 @@ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ +#ifdef i_more +#undef i_more +#else #undef i_type #undef i_tag #undef i_imp @@ -74,4 +77,6 @@ #undef _i_expandby #undef _i_has_from #undef _i_has_eq +#undef _i_has_cmp #undef _i_template +#endif \ No newline at end of file diff --git a/misc/benchmarks/various/csort_bench.c b/misc/benchmarks/various/csort_bench.c index d5d7fa7c..4d1149fc 100644 --- a/misc/benchmarks/various/csort_bench.c +++ b/misc/benchmarks/various/csort_bench.c @@ -5,8 +5,12 @@ #ifdef __cplusplus #include #endif +#define NDEBUG +#define i_type Ints #define i_val int -#include +#define i_more +#include +#include #define ROTL(d,bits) ((d<<(bits)) | (d>>(8*sizeof(d)-(bits)))) uint64_t romutrio(uint64_t s[3]) { @@ -21,14 +25,14 @@ static int cmp_int(const void* a, const void* b) { return c_default_cmp((const int*)a, (const int*)b); } -void testsort(int *a, int size, const char *desc) { +void testsort(Ints *a, int size, const char *desc) { clock_t t = clock(); #ifdef __cplusplus - printf("std::sort: "); std::sort(a, a + size); + printf("std::sort: "); std::sort(a->data, a->data + size); #elif defined QSORT - printf("qsort: "); qsort(a, size, sizeof *a, cmp_int); + printf("qsort: "); qsort(a->data, size, sizeof *a->data, cmp_int); #else - printf("stc_sort: "); csort_int(a, size); + printf("stc_qsort: "); Ints_sort_n(a, size); #endif t = clock() - t; @@ -41,27 +45,27 @@ int main(int argc, char *argv[]) { size_t i, size = argc > 1 ? strtoull(argv[1], NULL, 0) : 10000000; uint64_t s[3] = {123456789, 3456789123, 789123456}; - int32_t *a = (int32_t*)malloc(sizeof(*a) * size); - if (!a) return -1; + Ints a = Ints_with_capacity(size); for (i = 0; i < size; i++) - a[i] = romutrio(s) & (1U << 30) - 1; - testsort(a, size, "random"); + *Ints_push(&a, romutrio(s) & (1U << 30) - 1); + testsort(&a, size, "random"); for (i = 0; i < 20; i++) - printf(" %d", (int)a[i]); + printf(" %d", (int)*Ints_at(&a, i)); puts(""); for (i = 0; i < size; i++) - a[i] = i; - testsort(a, size, "sorted"); + *Ints_at_mut(&a, i) = i; + testsort(&a, size, "sorted"); for (i = 0; i < size; i++) - a[i] = size - i; - testsort(a, size, "reverse sorted"); + *Ints_at_mut(&a, i) = size - i; + testsort(&a, size, "reverse sorted"); for (i = 0; i < size; i++) - a[i] = 126735; - testsort(a, size, "constant"); + *Ints_at_mut(&a, i) = 126735; + testsort(&a, size, "constant"); for (i = 0; i < size; i++) - a[i] = i + 1; - a[size - 1] = 0; - testsort(a, size, "rotated"); - free(a); + *Ints_at_mut(&a, i) = i + 1; + *Ints_at_mut(&a, size - 1) = 0; + testsort(&a, size, "rotated"); + + Ints_drop(&a); } diff --git a/misc/benchmarks/various/cspan_bench.c b/misc/benchmarks/various/cspan_bench.c index 589df13a..02ae3237 100644 --- a/misc/benchmarks/various/cspan_bench.c +++ b/misc/benchmarks/various/cspan_bench.c @@ -1,4 +1,4 @@ -#define STC_NDEBUG +#define NDEBUG #include #include #include diff --git a/misc/examples/printspan.c b/misc/examples/printspan.c index 7459ac77..60a2d934 100644 --- a/misc/examples/printspan.c +++ b/misc/examples/printspan.c @@ -6,8 +6,6 @@ #include #define i_val int #include -#define i_val int -#include #define i_val_str #include #include @@ -40,9 +38,6 @@ int main() cstack_int stk = c_make(cstack_int, {1, 2, 3, 4, 5, 6, 7}); printMe( (intspan)cspan_from(&stk) ); - cdeq_int deq = c_make(cdeq_int, {1, 2, 3, 4, 5, 6, 7, 8}); - printMe( (intspan)cspan_from(&deq) ); - csset_str set = c_make(csset_str, {"5", "7", "4", "3", "8", "2", "1", "9", "6"}); printf("%d:", (int)csset_str_size(&set)); c_foreach (e, csset_str, set) @@ -52,6 +47,5 @@ int main() // cleanup cvec_int_drop(&vec); cstack_int_drop(&stk); - cdeq_int_drop(&deq); csset_str_drop(&set); } diff --git a/src/cregex.c b/src/cregex.c index a1d43944..981a256a 100644 --- a/src/cregex.c +++ b/src/cregex.c @@ -1220,7 +1220,7 @@ _build_subst(const char* replace, int nmatch, const csview match[], if (g < (int)nmatch) { csview m = mfun && mfun(g, match[g], &mstr) ? cstr_sv(&mstr) : match[g]; if (len + m.size > cap) - dst = cstr_reserve(subst, cap = cap*3/2 + m.size); + dst = cstr_reserve(subst, cap += cap*3/2 + m.size); for (int i = 0; i < (int)m.size; ++i) dst[len++] = m.str[i]; } -- cgit v1.2.3 From 00150a367c1e50c6b68ab878043beb6c1c8baa02 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Wed, 24 May 2023 13:18:27 +0200 Subject: Fixes for clang compiler. --- include/stc/algo/raii.h | 2 +- include/stc/priv/template2.h | 2 +- misc/examples/csset_erase.c | 2 +- misc/examples/make.sh | 16 ++++++++-------- 4 files changed, 11 insertions(+), 11 deletions(-) (limited to 'include/stc/priv/template2.h') diff --git a/include/stc/algo/raii.h b/include/stc/algo/raii.h index 7b1b445b..b0008a96 100644 --- a/include/stc/algo/raii.h +++ b/include/stc/algo/raii.h @@ -51,4 +51,4 @@ c_with_2(c_EXPAND(C a = C##_init(), b = C##_init(), c = C##_init(), d = C##_init()), \ (C##_drop(&d), C##_drop(&c), C##_drop(&b), C##_drop(&a))) -#endif \ No newline at end of file +#endif diff --git a/include/stc/priv/template2.h b/include/stc/priv/template2.h index 66ed7739..d7588ca0 100644 --- a/include/stc/priv/template2.h +++ b/include/stc/priv/template2.h @@ -79,4 +79,4 @@ #undef _i_has_eq #undef _i_has_cmp #undef _i_template -#endif \ No newline at end of file +#endif diff --git a/misc/examples/csset_erase.c b/misc/examples/csset_erase.c index 5fe3fcba..649bb1e3 100644 --- a/misc/examples/csset_erase.c +++ b/misc/examples/csset_erase.c @@ -38,4 +38,4 @@ int main() puts(""); csset_int_drop(&set); -} \ No newline at end of file +} diff --git a/misc/examples/make.sh b/misc/examples/make.sh index 25b720b8..5c81c4d3 100755 --- a/misc/examples/make.sh +++ b/misc/examples/make.sh @@ -7,14 +7,14 @@ if [ "$(uname)" = 'Linux' ]; then fi cc=gcc; cflags="-DSTC_STATIC -s -O3 -std=c99 -Wall -Wextra -Wpedantic -Wconversion -Wwrite-strings -Wdouble-promotion -Wno-unused-parameter -Wno-implicit-fallthrough -Wno-maybe-uninitialized -Wno-missing-field-initializers" -#cc=gcc; cflags="-g -std=c99 -Werror -Wfatal-errors -Wpedantic -Wall $sanitize" -#cc=tcc; cflags="-Wall -std=c99" -#cc=clang; cflags="-s -O2 -std=c99 -Werror -Wfatal-errors -Wpedantic -Wall -Wno-unused-function -Wsign-compare -Wwrite-strings" -#cc=gcc; cflags="-x c++ -s -O2 -Wall -std=c++20" -#cc=g++; cflags="-x c++ -s -O2 -Wall" -#cc=cl; cflags="-O2 -nologo -W3 -MD" -#cc=cl; cflags="-nologo -TP" -#cc=cl; cflags="-nologo -std:c11" +#cc=gcc; cflags="-DSTC_STATIC -g -std=c99 -Werror -Wfatal-errors -Wpedantic -Wall $sanitize" +#cc=tcc; cflags="-DSTC_STATIC -Wall -std=c99" +#cc=clang; cflags="-DSTC_STATIC -s -O3 -std=c99 -Wall -Wextra -Wpedantic -Wconversion -Wwrite-strings -Wdouble-promotion -Wno-unused-parameter -Wno-unused-function -Wno-implicit-fallthrough -Wno-missing-field-initializers" +#cc=gcc; cflags="-DSTC_STATIC -x c++ -s -O2 -Wall -std=c++20" +#cc=g++; cflags="-DSTC_STATIC -x c++ -s -O2 -Wall" +#cc=cl; cflags="-DSTC_STATIC -O2 -nologo -W3 -MD" +#cc=cl; cflags="-DSTC_STATIC -nologo -TP" +#cc=cl; cflags="-DSTC_STATIC -nologo -std:c11" if [ "$cc" = "cl" ]; then oflag='/Fe:' -- cgit v1.2.3 From 5f935739d2ce280beda36c7a7ddb0e0ee34c8fb3 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 9 Jun 2023 22:37:15 +0200 Subject: Rename i_extern template flag to i_import. i_extern still available, but deprecated. --- README.md | 6 +++--- docs/clist_api.md | 1 - docs/cregex_api.md | 4 ++-- docs/csview_api.md | 4 ++-- include/stc/ccommon.h | 8 ++++---- include/stc/crand.h | 2 +- include/stc/cregex.h | 4 ++-- include/stc/cspan.h | 2 +- include/stc/cstr.h | 10 +++++----- include/stc/csview.h | 5 ++--- include/stc/priv/template2.h | 2 +- include/stc/utf8.h | 4 ++-- misc/examples/forfilter.c | 2 +- misc/examples/regex1.c | 2 +- misc/examples/regex2.c | 2 +- misc/examples/regex_match.c | 2 +- misc/examples/regex_replace.c | 2 +- misc/examples/splitstr.c | 2 +- misc/tests/cregex_test.c | 2 +- src/cregex.c | 2 +- src/libstc.c | 4 ++-- 21 files changed, 35 insertions(+), 37 deletions(-) (limited to 'include/stc/priv/template2.h') diff --git a/README.md b/README.md index e63a56e4..f14858e7 100644 --- a/README.md +++ b/README.md @@ -333,6 +333,7 @@ After erasing the elements found: --- ## Installation +*NEEDS REWRITE!* Because it is headers-only, headers can simply be included in your program. By default, functions are static (some inlined). You may add the *include* folder to the **CPATH** environment variable to let GCC, Clang, and TinyC locate the headers. @@ -345,8 +346,7 @@ You may also cherry-pick shared linking mode on individual containers by `#defin `#define i_implement`, or force static symbols by `#define i_static` before container includes. As a special case, there may be non-templated functions in templated containers that should be implemented only -once and if needed. Currently, define `i_extern` before including **clist** for its sorting function, and before -**cregex** or **utf8** to implement them (global `STC_EXTERN` can alternatively be defined). +once and if needed. Currently, define `i_import` before including **cregex** or **utf8** to implement them. It is possible to generate single headers by executing the python script `src/singleheader.py header-file > single`. @@ -356,7 +356,7 @@ or define your own, e.g.: ```c // stc_libs.c #define STC_IMPLEMENT // implement all the following as shared objects - +#define i_implement #include #include "Point.h" diff --git a/docs/clist_api.md b/docs/clist_api.md index 36935c88..51b7af6a 100644 --- a/docs/clist_api.md +++ b/docs/clist_api.md @@ -118,7 +118,6 @@ Interleave *push_front()* / *push_back()* then *sort()*: ```c #define i_type DList #define i_val double -#define i_extern // link with sort() fn. #include #include diff --git a/docs/cregex_api.md b/docs/cregex_api.md index fc86cc63..ff69c549 100644 --- a/docs/cregex_api.md +++ b/docs/cregex_api.md @@ -99,7 +99,7 @@ If an error occurs ```cregex_compile``` returns a negative error code stored in [ [Run this code](https://godbolt.org/z/z434TMKfo) ] ```c -#define i_extern // include external cstr, utf8, cregex functions implementation. +#define i_import // include dependent cstr, utf8 and cregex function definitions. #include int main() { @@ -151,7 +151,7 @@ c_formatch (it, &re, input) ## Using cregex in a project -The easiest is to `#define i_extern` before `#include `. Make sure to do that in one translation unit only. +The easiest is to `#define i_import` before `#include `. Make sure to do that in one translation unit only. For reference, **cregex** uses the following files: - `stc/cregex.h`, `stc/utf8.h`, `stc/csview.h`, `stc/cstr.h`, `stc/ccommon.h`, `stc/forward.h` diff --git a/docs/csview_api.md b/docs/csview_api.md index b697b7d6..879822d3 100644 --- a/docs/csview_api.md +++ b/docs/csview_api.md @@ -148,8 +148,8 @@ red Apples ### Example 2: UTF8 handling ```c -#define i_extern -#include // i_extern: implement cstr + dependencies (utf8) +#define i_import // include dependent cstr, utf8 and cregex function definitions. +#include int main() { diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index 87522a6e..e491a567 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -241,6 +241,9 @@ STC_INLINE intptr_t cnextpow2(intptr_t n) { #undef STC_API #undef STC_DEF +#ifdef i_extern +# define i_import +#endif #if !defined(i_static) && !defined(STC_STATIC) && (defined(i_header) || defined(STC_HEADER) || \ defined(i_implement) || defined(STC_IMPLEMENT)) #define STC_API extern @@ -250,9 +253,6 @@ STC_INLINE intptr_t cnextpow2(intptr_t n) { #define STC_API static inline #define STC_DEF static inline #endif -#if defined(STC_EXTERN) - #define i_extern -#endif -#if defined(STC_IMPLEMENT) || defined(i_extern) +#if defined(STC_IMPLEMENT) || defined(i_import) #define i_implement #endif diff --git a/include/stc/crand.h b/include/stc/crand.h index b9687c01..95a65fb0 100644 --- a/include/stc/crand.h +++ b/include/stc/crand.h @@ -158,4 +158,4 @@ STC_DEF double crand_norm(crand_t* rng, crand_norm_t* dist) { #undef i_static #undef i_header #undef i_implement -#undef i_extern +#undef i_import diff --git a/include/stc/cregex.h b/include/stc/cregex.h index e6180a31..43a7fcbf 100644 --- a/include/stc/cregex.h +++ b/include/stc/cregex.h @@ -161,12 +161,12 @@ void cregex_drop(cregex* re); #if defined i_implement # include "../../src/cregex.c" #endif -#if defined i_extern +#if defined i_import # include "../../src/utf8code.c" #endif #endif // CREGEX_H_INCLUDED #undef i_opt #undef i_header #undef i_static -#undef i_extern +#undef i_import #undef i_implement diff --git a/include/stc/cspan.h b/include/stc/cspan.h index 5b592098..dd6cb1c0 100644 --- a/include/stc/cspan.h +++ b/include/stc/cspan.h @@ -265,4 +265,4 @@ STC_DEF intptr_t _cspan_slice(int32_t odim[], int32_t ostri[], int* orank, #undef i_header #undef i_implement #undef i_static -#undef i_extern +#undef i_import diff --git a/include/stc/cstr.h b/include/stc/cstr.h index ae80dab4..f47889b4 100644 --- a/include/stc/cstr.h +++ b/include/stc/cstr.h @@ -405,8 +405,8 @@ STC_INLINE bool cstr_getline(cstr *self, FILE *fp) #endif // CSTR_H_INCLUDED -/* -------------------------- EXTERN ------------------------- */ -#if defined(i_extern) && !defined(CSTR_X_INCLUDED) +/* -------------------------- UTF8 CASE CONVERSION ------------------------- */ +#if defined(i_import) && !defined(CSTR_X_INCLUDED) #define CSTR_X_INCLUDED static struct { @@ -437,11 +437,11 @@ cstr cstr_tocase(csview sv, int k) { cstr_shrink_to_fit(&out); return out; } -#endif // i_extern +#endif // i_import /* -------------------------- IMPLEMENTATION ------------------------- */ #ifndef CSTR_C_INCLUDED -#if defined i_extern || (defined i_implement && !defined _i_no_undef) +#if defined i_import || (defined i_implement && !defined _i_no_undef) #define CSTR_C_INCLUDED uint64_t cstr_hash(const cstr *self) { @@ -659,4 +659,4 @@ intptr_t cstr_printf(cstr* self, const char* fmt, ...) { #undef i_header #undef i_static #undef i_implement -#undef i_extern +#undef i_import diff --git a/include/stc/csview.h b/include/stc/csview.h index d38d5f59..ee217e98 100644 --- a/include/stc/csview.h +++ b/include/stc/csview.h @@ -151,7 +151,7 @@ STC_INLINE bool csview_eq(const csview* x, const csview* y) /* -------------------------- IMPLEMENTATION ------------------------- */ #ifndef CSVIEW_C_INCLUDED -#if defined i_extern || (defined i_implement && !defined _i_no_undef) +#if defined i_import || (defined i_implement && !defined _i_no_undef) #define CSVIEW_C_INCLUDED csview_iter csview_advance(csview_iter it, intptr_t pos) { @@ -201,11 +201,10 @@ csview csview_token(csview sv, const char* sep, intptr_t* start) { *start += tok.size + sep_size; return tok; } - #endif #endif #undef i_opt #undef i_header #undef i_implement #undef i_static -#undef i_extern +#undef i_import diff --git a/include/stc/priv/template2.h b/include/stc/priv/template2.h index d7588ca0..75402150 100644 --- a/include/stc/priv/template2.h +++ b/include/stc/priv/template2.h @@ -59,7 +59,7 @@ #undef i_header #undef i_implement #undef i_static -#undef i_extern +#undef i_import #undef i_allocator #undef i_malloc diff --git a/include/stc/utf8.h b/include/stc/utf8.h index 338f0db9..e853263b 100644 --- a/include/stc/utf8.h +++ b/include/stc/utf8.h @@ -115,14 +115,14 @@ STC_INLINE intptr_t utf8_pos(const char* s, intptr_t index) { return (intptr_t)(utf8_at(s, index) - s); } #endif // UTF8_H_INCLUDED -#if defined i_extern || (defined i_implement && !defined _i_no_undef) +#if defined i_import || (defined i_implement && !defined _i_no_undef) # include "../../src/utf8code.c" #endif #ifndef _i_no_undef #undef i_static #undef i_header #undef i_implement -#undef i_extern +#undef i_import #undef i_opt #endif #undef _i_no_undef diff --git a/misc/examples/forfilter.c b/misc/examples/forfilter.c index f9505aa9..94a84065 100644 --- a/misc/examples/forfilter.c +++ b/misc/examples/forfilter.c @@ -1,5 +1,5 @@ #include -#define i_extern +#define i_import #include #define i_implement #include diff --git a/misc/examples/regex1.c b/misc/examples/regex1.c index 4a56b8ac..d8032358 100644 --- a/misc/examples/regex1.c +++ b/misc/examples/regex1.c @@ -1,4 +1,4 @@ -#define i_extern +#define i_import #include int main(int argc, char* argv[]) diff --git a/misc/examples/regex2.c b/misc/examples/regex2.c index 3133f7c2..5718a1d8 100644 --- a/misc/examples/regex2.c +++ b/misc/examples/regex2.c @@ -1,4 +1,4 @@ -#define i_extern +#define i_import #include int main() diff --git a/misc/examples/regex_match.c b/misc/examples/regex_match.c index b4932015..ebda366f 100644 --- a/misc/examples/regex_match.c +++ b/misc/examples/regex_match.c @@ -1,4 +1,4 @@ -#define i_extern +#define i_import #include #define i_implement #include diff --git a/misc/examples/regex_replace.c b/misc/examples/regex_replace.c index cad195d5..2c7794af 100644 --- a/misc/examples/regex_replace.c +++ b/misc/examples/regex_replace.c @@ -1,4 +1,4 @@ -#define i_extern +#define i_import #include #include #include diff --git a/misc/examples/splitstr.c b/misc/examples/splitstr.c index 658c46a1..32b5f17f 100644 --- a/misc/examples/splitstr.c +++ b/misc/examples/splitstr.c @@ -1,5 +1,5 @@ #include -#define i_extern // cstr + utf8 functions +#define i_import // cstr + utf8 functions #include #define i_implement #include diff --git a/misc/tests/cregex_test.c b/misc/tests/cregex_test.c index 301ecf4f..3ddcc608 100644 --- a/misc/tests/cregex_test.c +++ b/misc/tests/cregex_test.c @@ -1,4 +1,4 @@ -#define i_extern +#define i_import #include #include #include diff --git a/src/cregex.c b/src/cregex.c index 62a64b11..1af719b4 100644 --- a/src/cregex.c +++ b/src/cregex.c @@ -27,7 +27,7 @@ THE SOFTWARE. #define CREGEX_C_INCLUDED #include -#ifdef i_extern +#ifdef i_import # define _i_extern #endif #ifndef CREGEX_H_INCLUDED diff --git a/src/libstc.c b/src/libstc.c index 99611e05..afc19a08 100644 --- a/src/libstc.c +++ b/src/libstc.c @@ -1,6 +1,6 @@ #include #if 1 -#define i_extern +#define i_import #include "../include/stc/utf8.h" #define i_implement #include "../include/stc/cstr.h" @@ -9,7 +9,7 @@ #define i_implement #include "../include/stc/csview.h" #else -#define i_extern +#define i_import #include "../include/stc/cregex.h" #define i_implement #include "../include/stc/csview.h" -- cgit v1.2.3 From b617eded8cee98dd3ff9ac896328b172d37fcf91 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Tue, 20 Jun 2023 15:17:07 +0200 Subject: Minor internals. --- include/stc/cqueue.h | 10 +++++----- include/stc/priv/template.h | 10 ++++------ include/stc/priv/template2.h | 2 +- 3 files changed, 10 insertions(+), 12 deletions(-) (limited to 'include/stc/priv/template2.h') diff --git a/include/stc/cqueue.h b/include/stc/cqueue.h index aa3d7384..2f709172 100644 --- a/include/stc/cqueue.h +++ b/include/stc/cqueue.h @@ -165,21 +165,21 @@ _cx_memb(_reserve)(_cx_self* self, const intptr_t n) { if (n <= self->capmask) return true; intptr_t oldcap = self->capmask + 1, newcap = cnextpow2(n + 1); - _cx_value* data = (_cx_value *)i_realloc(self->data, newcap*c_sizeof *self->data); - if (!data) + _cx_value* d = (_cx_value *)i_realloc(self->data, newcap*c_sizeof *self->data); + if (!d) return false; intptr_t head = oldcap - self->start; if (self->start <= self->end) ; else if (head < self->end) { self->start = newcap - head; - c_memmove(data + self->start, data + oldcap - head, head*c_sizeof *data); + c_memmove(d + self->start, d + oldcap - head, head*c_sizeof *d); } else { - c_memmove(data + oldcap, data, self->end*c_sizeof *data); + c_memmove(d + oldcap, d, self->end*c_sizeof *d); self->end += oldcap; } self->capmask = newcap - 1; - self->data = data; + self->data = d; return true; } diff --git a/include/stc/priv/template.h b/include/stc/priv/template.h index f70281c7..b3f3eabe 100644 --- a/include/stc/priv/template.h +++ b/include/stc/priv/template.h @@ -112,7 +112,6 @@ #if defined i_key_str #define i_keyclass cstr #define i_rawclass crawstr - #define i_keyfrom cstr_from #ifndef i_tag #define i_tag str #endif @@ -188,7 +187,7 @@ #ifndef i_keyfrom #define i_keyfrom c_default_clone #else - #define _i_has_from + #define i_has_emplace #endif #ifndef i_keyto #define i_keyto c_default_toraw @@ -225,8 +224,7 @@ #ifdef i_val_str #define i_valclass cstr - #define i_valraw crawstr - #define i_valfrom cstr_from + #define i_valraw const char* #elif defined i_val_ssv #define i_valclass cstr #define i_valraw csview @@ -266,7 +264,7 @@ #ifndef i_valfrom #define i_valfrom c_default_clone #else - #define _i_has_from + #define i_has_emplace #endif #ifndef i_valto #define i_valto c_default_toraw @@ -286,7 +284,7 @@ #ifndef i_valraw #define i_valraw i_keyraw #endif -#ifndef _i_has_from +#ifndef i_has_emplace #define i_no_emplace #endif #endif diff --git a/include/stc/priv/template2.h b/include/stc/priv/template2.h index 75402150..4604e610 100644 --- a/include/stc/priv/template2.h +++ b/include/stc/priv/template2.h @@ -72,10 +72,10 @@ #undef i_no_clone #undef i_no_emplace #undef i_is_forward +#undef i_has_emplace #undef _i_prefix #undef _i_expandby -#undef _i_has_from #undef _i_has_eq #undef _i_has_cmp #undef _i_template -- cgit v1.2.3 From 3fed66750bed9c82a8bb12fd86b963d2f5ec0eb5 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Tue, 20 Jun 2023 16:32:32 +0200 Subject: Renamed `i_more` => `i_retain` (avoids undef of template parameters on next STC container inclusion). --- docs/ccommon_api.md | 4 ++-- include/stc/algo/sort.h | 23 +++++++++++++++++++++-- include/stc/cdeq.h | 6 +++--- include/stc/priv/template2.h | 4 ++-- misc/benchmarks/various/csort_bench.c | 2 +- 5 files changed, 29 insertions(+), 10 deletions(-) (limited to 'include/stc/priv/template2.h') diff --git a/docs/ccommon_api.md b/docs/ccommon_api.md index 89a98cbb..c9c65156 100644 --- a/docs/ccommon_api.md +++ b/docs/ccommon_api.md @@ -222,11 +222,11 @@ int main() { } ``` Containers with random access may also be sorted. Even sorting cdeq/cqueue (with ring buffer) is -possible and very fast. Note that `i_more` must be defined to pick up template parameters from the container: +possible and very fast. Note that `i_retain` must be defined to retain specified template parameters for use by sort: ```c #define i_type MyDeq #define i_val int -#define i_more +#define i_retain #include // deque #include #include diff --git a/include/stc/algo/sort.h b/include/stc/algo/sort.h index 291d90a6..002e6499 100644 --- a/include/stc/algo/sort.h +++ b/include/stc/algo/sort.h @@ -26,7 +26,7 @@ template params: #define i_less - less function. default: *x < *y #define i_type name - define {{name}}_sort_n(), else {{i_val}}array_sort_n(). -// test: +// ex1: #include #define i_val int #include @@ -34,12 +34,31 @@ template params: int main() { int nums[] = {23, 321, 5434, 25, 245, 1, 654, 33, 543, 21}; - intarray_sort_n(nums, c_arraylen(arr)); + intarray_sort_n(nums, c_arraylen(nums)); for (int i = 0; i < c_arraylen(nums); i++) printf(" %d", nums[i]); puts(""); } + +// ex2: +#define i_val int +#define i_type IDeq +#define i_retain // retain input template params to be reused by sort.h +#include +#include + +int main() { + IDeq nums = c_init(IDeq, {5434, 25, 245, 1, 654, 33, 543, 21}); + IDeq_push_front(&nums, 23); + IDeq_push_front(&nums, 321); + + IDeq_sort_n(&nums, IDeq_size(&nums)); + + c_foreach (i, IDeq, nums) + printf(" %d", *i.ref); + IDeq_drop(&nums); +} */ #include "../ccommon.h" diff --git a/include/stc/cdeq.h b/include/stc/cdeq.h index 0eac5a1d..06dfdb82 100644 --- a/include/stc/cdeq.h +++ b/include/stc/cdeq.h @@ -23,11 +23,11 @@ #define _i_prefix cdeq_ #define _pop _pop_front #define _pull _pull_front -#ifdef i_more +#ifdef i_retain #include "cqueue.h" - #define i_more + #define i_retain #else - #define i_more + #define i_retain #include "cqueue.h" #endif #undef _pop diff --git a/include/stc/priv/template2.h b/include/stc/priv/template2.h index 4604e610..47b82937 100644 --- a/include/stc/priv/template2.h +++ b/include/stc/priv/template2.h @@ -20,8 +20,8 @@ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ -#ifdef i_more -#undef i_more +#ifdef i_retain +#undef i_retain #else #undef i_type #undef i_tag diff --git a/misc/benchmarks/various/csort_bench.c b/misc/benchmarks/various/csort_bench.c index d434693f..93034dde 100644 --- a/misc/benchmarks/various/csort_bench.c +++ b/misc/benchmarks/various/csort_bench.c @@ -8,7 +8,7 @@ #define NDEBUG #define i_type Ints #define i_val int -#define i_more +#define i_retain #include #include -- cgit v1.2.3 From 764d6b5a831c4ff58fb717a1360fe80f691a424d Mon Sep 17 00:00:00 2001 From: Tyge Lovset Date: Thu, 29 Jun 2023 09:32:39 +0200 Subject: Usage change: comparison is no longer enabled when specifying i_val for cvec, cdeq and clist (like cstack and cqueue). Comparison functions are still required when specifying i_valclass. For fundamental/native types like integers, floats etc., define i_native_cmp along with i_val instead of i_less/i_cmp/i_eq. --- include/stc/carc.h | 75 ++++++++++++++++++++++++++---------------- include/stc/cbox.h | 71 +++++++++++++++++++++++---------------- include/stc/ccommon.h | 4 +-- include/stc/cdeq.h | 4 +-- include/stc/clist.h | 13 ++++---- include/stc/cqueue.h | 6 ++-- include/stc/cstr.h | 2 +- include/stc/csview.h | 2 +- include/stc/cvec.h | 18 +++++----- include/stc/priv/template.h | 53 +++++++++++++++-------------- include/stc/priv/template2.h | 5 +-- misc/examples/arc_containers.c | 4 +-- misc/examples/arc_demo.c | 14 +++++--- misc/examples/arcvec_erase.c | 2 +- misc/examples/box2.c | 4 +-- misc/examples/complex.c | 4 +-- misc/examples/csmap_find.c | 1 - misc/examples/demos.c | 1 + misc/examples/intrusive.c | 5 +-- misc/examples/list.c | 1 + misc/examples/lower_bound.c | 1 + misc/examples/music_arc.c | 6 ++-- misc/examples/new_list.c | 5 +-- misc/examples/new_sptr.c | 6 ++-- misc/examples/new_vec.c | 5 +-- misc/examples/scheduler.c | 1 - 26 files changed, 176 insertions(+), 137 deletions(-) (limited to 'include/stc/priv/template2.h') diff --git a/include/stc/carc.h b/include/stc/carc.h index 2096b968..db0cdcec 100644 --- a/include/stc/carc.h +++ b/include/stc/carc.h @@ -30,6 +30,11 @@ typedef struct { cstr name, last; } Person; Person Person_make(const char* name, const char* last) { return (Person){.name = cstr_from(name), .last = cstr_from(last)}; } +Person Person_clone(Person p) { + p.name = cstr_clone(p.name); + p.last = cstr_clone(p.last); + return p; +} void Person_drop(Person* p) { printf("drop: %s %s\n", cstr_str(&p->name), cstr_str(&p->last)); cstr_drop(&p->name); @@ -37,8 +42,8 @@ void Person_drop(Person* p) { } #define i_type ArcPers -#define i_key Person -#define i_keydrop Person_drop +#define i_valclass Person // clone, drop, cmp, hash +#define i_opt c_no_cmp|c_no_hash // exclude cmp, hash #include int main() { @@ -77,14 +82,7 @@ int main() { #endif // CARC_H_INCLUDED #define _i_prefix carc_ -#if !defined i_cmp && !defined i_less && \ - !defined i_valclass && !defined i_valboxed && \ - !defined i_val_str && !defined i_val_ssv - #if !defined i_eq - #define i_eq(x, y) x == y - #endif - #define i_less(x, y) x < y -#endif +#define _i_carc #include "priv/template.h" typedef i_keyraw _cx_raw; @@ -178,32 +176,53 @@ STC_INLINE void _cx_MEMB(_assign)(_cx_Self* self, _cx_Self ptr) { *self = ptr; } -#ifndef i_no_cmp -STC_INLINE int _cx_MEMB(_raw_cmp)(const _cx_raw* rx, const _cx_raw* ry) - { return i_cmp(rx, ry); } +#if defined _i_has_cmp + STC_INLINE int _cx_MEMB(_raw_cmp)(const _cx_raw* rx, const _cx_raw* ry) + { return i_cmp(rx, ry); } -STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { - _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); - return i_cmp((&rx), (&ry)); -} + STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { + _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); + return i_cmp((&rx), (&ry)); + } +#else + STC_INLINE int _cx_MEMB(_raw_cmp)(const _cx_raw* rx, const _cx_raw* ry) + { return c_default_cmp(&rx, &ry); } -STC_INLINE bool _cx_MEMB(_raw_eq)(const _cx_raw* rx, const _cx_raw* ry) - { return i_eq(rx, ry); } + STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { + return c_default_cmp(&self->get, &other->get); + } +#endif +#if defined _i_has_eq || defined _i_has_cmp + STC_INLINE bool _cx_MEMB(_raw_eq)(const _cx_raw* rx, const _cx_raw* ry) + { return i_eq(rx, ry); } -STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { - _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); - return i_eq((&rx), (&ry)); -} + STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { + _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); + return i_eq((&rx), (&ry)); + } +#else + STC_INLINE bool _cx_MEMB(_raw_eq)(const _cx_raw* rx, const _cx_raw* ry) + { return rx == ry; } + + STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { + return self->get == other->get; + } #endif +#if defined i_hash + STC_INLINE uint64_t _cx_MEMB(_raw_hash)(const _cx_raw* rx) + { return i_hash(rx); } -#ifndef i_no_hash -STC_INLINE uint64_t _cx_MEMB(_raw_hash)(const _cx_raw* rx) - { return i_hash(rx); } + STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) + { return i_hash(self->get); } +#else + STC_INLINE uint64_t _cx_MEMB(_raw_hash)(const _cx_raw* rx) + { return c_default_hash(&rx); } -STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) - { _cx_raw rx = i_keyto(self->get); return i_hash((&rx)); } + STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) + { return c_default_hash(&self->get); } #endif #undef _i_atomic_inc #undef _i_atomic_dec_and_test #include "priv/template2.h" +#undef _i_carc \ No newline at end of file diff --git a/include/stc/cbox.h b/include/stc/cbox.h index 24de71d4..c8d919b2 100644 --- a/include/stc/cbox.h +++ b/include/stc/cbox.h @@ -25,6 +25,7 @@ /* cbox: heap allocated boxed type #define i_implement #include +#include // c_auto typedef struct { cstr name, email; } Person; @@ -41,8 +42,9 @@ void Person_drop(Person* p) { c_drop(cstr, &p->name, &p->email); } -#define i_keyclass Person // bind Person clone+drop fn's #define i_type PBox +#define i_valclass Person // bind Person clone+drop fn's +#define i_no_cmp // no cmp/hash is defined #include int main() { @@ -70,14 +72,7 @@ int main() { #endif // CBOX_H_INCLUDED #define _i_prefix cbox_ -#if !defined i_cmp && !defined i_less && \ - !defined i_valclass && !defined i_valboxed && \ - !defined i_val_str && !defined i_val_ssv - #if !defined i_eq - #define i_eq(x, y) x == y - #endif - #define i_less(x, y) x < y -#endif +#define _i_cbox #include "priv/template.h" typedef i_keyraw _cx_raw; @@ -164,30 +159,50 @@ STC_INLINE void _cx_MEMB(_assign)(_cx_Self* self, _cx_Self* moved) { moved->get = NULL; } -#ifndef i_no_cmp -STC_INLINE int _cx_MEMB(_raw_cmp)(const _cx_raw* rx, const _cx_raw* ry) - { return i_cmp(rx, ry); } - -STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { - _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); - return i_cmp((&rx), (&ry)); -} +#if defined _i_has_cmp + STC_INLINE int _cx_MEMB(_raw_cmp)(const _cx_raw* rx, const _cx_raw* ry) + { return i_cmp(rx, ry); } -STC_INLINE bool _cx_MEMB(_raw_eq)(const _cx_raw* rx, const _cx_raw* ry) - { return i_eq(rx, ry); } + STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { + _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); + return i_cmp((&rx), (&ry)); + } +#else + STC_INLINE int _cx_MEMB(_raw_cmp)(const _cx_raw* rx, const _cx_raw* ry) + { return c_default_cmp(&rx, &ry); } -STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { - _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); - return i_eq((&rx), (&ry)); -} + STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { + return c_default_cmp(&self->get, &other->get); + } #endif +#if defined _i_has_eq || defined _i_has_cmp + STC_INLINE bool _cx_MEMB(_raw_eq)(const _cx_raw* rx, const _cx_raw* ry) + { return i_eq(rx, ry); } -#ifndef i_no_hash -STC_INLINE uint64_t _cx_MEMB(_raw_hash)(const _cx_raw* rx) - { return i_hash(rx); } + STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { + _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); + return i_eq((&rx), (&ry)); + } +#else + STC_INLINE bool _cx_MEMB(_raw_eq)(const _cx_raw* rx, const _cx_raw* ry) + { return rx == ry; } -STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) - { _cx_raw rx = i_keyto(self->get); return i_hash((&rx)); } + STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { + return self->get == other->get; + } #endif +#if defined i_hash + STC_INLINE uint64_t _cx_MEMB(_raw_hash)(const _cx_raw* rx) + { return i_hash(rx); } + STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) + { return i_hash(self->get); } +#else + STC_INLINE uint64_t _cx_MEMB(_raw_hash)(const _cx_raw* rx) + { return c_default_hash(&rx); } + + STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) + { return c_default_hash(&self->get); } +#endif #include "priv/template2.h" +#undef _i_cbox \ No newline at end of file diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index 5f280218..bbf1579b 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -113,8 +113,8 @@ #define c_no_clone (1<<2) #define c_no_emplace (1<<3) #define c_no_cmp (1<<4) -#define c_no_hash (1<<5) - +#define c_native_cmp (1<<5) +#define c_no_hash (1<<6) /* Function macros and others */ #define c_litstrlen(literal) (c_sizeof("" literal) - 1) diff --git a/include/stc/cdeq.h b/include/stc/cdeq.h index 06dfdb82..2db040f1 100644 --- a/include/stc/cdeq.h +++ b/include/stc/cdeq.h @@ -101,7 +101,7 @@ _cx_MEMB(_emplace_at)(_cx_Self* self, _cx_iter it, const _cx_raw raw) { return _cx_MEMB(_insert_at)(self, it, i_keyfrom(raw)); } #endif -#if defined _i_has_cmp || defined _i_has_eq +#if defined _i_has_eq || defined _i_has_cmp STC_API _cx_iter _cx_MEMB(_find_in)(_cx_iter p1, _cx_iter p2, _cx_raw raw); STC_INLINE _cx_iter @@ -179,7 +179,7 @@ _cx_MEMB(_emplace_n)(_cx_Self* self, const intptr_t idx, const _cx_raw* raw, con } #endif -#if defined _i_has_cmp || defined _i_has_eq +#if defined _i_has_eq || defined _i_has_cmp STC_DEF _cx_iter _cx_MEMB(_find_in)(_cx_iter i1, _cx_iter i2, _cx_raw raw) { for (; i1.pos != i2.pos; _cx_MEMB(_next)(&i1)) { diff --git a/include/stc/clist.h b/include/stc/clist.h index 0785a6af..38358d73 100644 --- a/include/stc/clist.h +++ b/include/stc/clist.h @@ -93,11 +93,11 @@ STC_API _cx_value* _cx_MEMB(_push_front)(_cx_Self* self, i_key value); STC_API _cx_iter _cx_MEMB(_insert_at)(_cx_Self* self, _cx_iter it, i_key value); STC_API _cx_iter _cx_MEMB(_erase_at)(_cx_Self* self, _cx_iter it); STC_API _cx_iter _cx_MEMB(_erase_range)(_cx_Self* self, _cx_iter it1, _cx_iter it2); -#if !defined i_no_cmp || defined _i_has_eq +#if defined _i_has_eq || defined _i_has_cmp STC_API _cx_iter _cx_MEMB(_find_in)(_cx_iter it1, _cx_iter it2, _cx_raw val); STC_API intptr_t _cx_MEMB(_remove)(_cx_Self* self, _cx_raw val); #endif -#ifndef i_no_cmp +#if defined _i_has_cmp STC_API bool _cx_MEMB(_sort_with)(_cx_Self* self, int(*cmp)(const _cx_value*, const _cx_value*)); STC_API int _cx_MEMB(_sort_cmp_)(const _cx_value*, const _cx_value*); STC_INLINE bool _cx_MEMB(_sort)(_cx_Self* self) @@ -188,7 +188,7 @@ _cx_MEMB(_splice_range)(_cx_Self* self, _cx_iter it, return _cx_MEMB(_splice)(self, it, &tmp); } -#if !defined i_no_cmp || defined _i_has_eq +#if defined _i_has_eq || defined _i_has_cmp STC_INLINE _cx_iter _cx_MEMB(_find)(const _cx_Self* self, _cx_raw val) { return _cx_MEMB(_find_in)(_cx_MEMB(_begin)(self), _cx_MEMB(_end)(self), val); @@ -350,8 +350,7 @@ _cx_MEMB(_split_off)(_cx_Self* self, _cx_iter it1, _cx_iter it2) { return lst; } -#if !defined i_no_cmp || defined _i_has_eq - +#if defined _i_has_eq || defined _i_has_cmp STC_DEF _cx_iter _cx_MEMB(_find_in)(_cx_iter it1, _cx_iter it2, _cx_raw val) { c_foreach (it, _cx_Self, it1, it2) { @@ -379,7 +378,7 @@ _cx_MEMB(_remove)(_cx_Self* self, _cx_raw val) { } #endif -#ifndef i_no_cmp +#if defined _i_has_cmp STC_DEF int _cx_MEMB(_sort_cmp_)(const _cx_value* x, const _cx_value* y) { const _cx_raw a = i_keyto(x), b = i_keyto(y); return i_cmp((&a), (&b)); @@ -401,7 +400,7 @@ STC_DEF bool _cx_MEMB(_sort_with)(_cx_Self* self, int(*cmp)(const _cx_value*, co *i.ref = *p; i_free(a); return true; } -#endif // !c_no_cmp +#endif // _i_has_cmp #endif // i_implement #define CLIST_H_INCLUDED #include "priv/template2.h" diff --git a/include/stc/cqueue.h b/include/stc/cqueue.h index 6eee712b..e9f1b877 100644 --- a/include/stc/cqueue.h +++ b/include/stc/cqueue.h @@ -63,8 +63,8 @@ STC_INLINE _cx_value* _cx_MEMB(_emplace)(_cx_Self* self, _cx_raw raw) { return _cx_MEMB(_push)(self, i_keyfrom(raw)); } #endif -#if defined _i_has_cmp || defined _i_has_eq -STC_API bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other); +#if defined _i_has_eq || defined _i_has_cmp +STC_API bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other); #endif #if !defined i_no_clone @@ -224,7 +224,7 @@ _cx_MEMB(_clone)(_cx_Self cx) { } #endif // i_no_clone -#if defined _i_has_cmp || defined _i_has_eq +#if defined _i_has_eq || defined _i_has_cmp STC_DEF bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { if (_cx_MEMB(_size)(self) != _cx_MEMB(_size)(other)) return false; diff --git a/include/stc/cstr.h b/include/stc/cstr.h index ce42cf8d..0f217f53 100644 --- a/include/stc/cstr.h +++ b/include/stc/cstr.h @@ -433,7 +433,7 @@ cstr cstr_tocase(csview sv, int k) { #endif // i_import /* -------------------------- IMPLEMENTATION ------------------------- */ -#if defined i_import || defined i_implement +#if defined i_implement #ifndef CSTR_C_INCLUDED #define CSTR_C_INCLUDED diff --git a/include/stc/csview.h b/include/stc/csview.h index 07ab4059..f960968c 100644 --- a/include/stc/csview.h +++ b/include/stc/csview.h @@ -150,7 +150,7 @@ STC_INLINE csview cstr_u8_substr(const cstr* self , intptr_t bytepos, intptr_t u #endif /* -------------------------- IMPLEMENTATION ------------------------- */ -#if defined i_import || defined i_implement +#if defined i_implement #ifndef CSVIEW_C_INCLUDED #define CSVIEW_C_INCLUDED diff --git a/include/stc/cvec.h b/include/stc/cvec.h index 3213dd1c..6806e2bc 100644 --- a/include/stc/cvec.h +++ b/include/stc/cvec.h @@ -40,7 +40,7 @@ struct MyStruct { #include #define i_key int -#define i_is_forward // forward declared +#define i_is_forward #define i_tag i32 #include @@ -85,10 +85,10 @@ STC_API bool _cx_MEMB(_resize)(_cx_Self* self, intptr_t size, i_key n STC_API _cx_value* _cx_MEMB(_push)(_cx_Self* self, i_key value); STC_API _cx_iter _cx_MEMB(_erase_n)(_cx_Self* self, intptr_t idx, intptr_t n); STC_API _cx_iter _cx_MEMB(_insert_uninit)(_cx_Self* self, intptr_t idx, intptr_t n); -#if !defined i_no_cmp || defined _i_has_eq +#if defined _i_has_eq || defined _i_has_cmp STC_API _cx_iter _cx_MEMB(_find_in)(_cx_iter it1, _cx_iter it2, _cx_raw raw); #endif -#ifndef i_no_cmp +#if defined _i_has_cmp STC_API int _cx_MEMB(_value_cmp)(const _cx_value* x, const _cx_value* y); STC_API _cx_iter _cx_MEMB(_binary_search_in)(_cx_iter it1, _cx_iter it2, _cx_raw raw, _cx_iter* lower_bound); #endif @@ -214,7 +214,7 @@ STC_INLINE intptr_t _cx_MEMB(_index)(const _cx_Self* self, _cx_iter it) STC_INLINE void _cx_MEMB(_adjust_end_)(_cx_Self* self, intptr_t n) { self->_len += n; } -#if !defined i_no_cmp || defined _i_has_eq +#if defined _i_has_eq || defined _i_has_cmp STC_INLINE _cx_iter _cx_MEMB(_find)(const _cx_Self* self, _cx_raw raw) { @@ -240,7 +240,7 @@ _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { return true; } #endif -#ifndef i_no_cmp +#if defined _i_has_cmp STC_INLINE _cx_iter _cx_MEMB(_binary_search)(const _cx_Self* self, _cx_raw raw) { @@ -265,7 +265,7 @@ STC_INLINE void _cx_MEMB(_sort)(_cx_Self* self) { _cx_MEMB(_sort_range)(_cx_MEMB(_begin)(self), _cx_MEMB(_end)(self), _cx_MEMB(_value_cmp)); } -#endif // !c_no_cmp +#endif // _i_has_cmp /* -------------------------- IMPLEMENTATION ------------------------- */ #if defined(i_implement) || defined(i_static) @@ -378,7 +378,7 @@ _cx_MEMB(_emplace_n)(_cx_Self* self, const intptr_t idx, const _cx_raw raw[], in return it; } #endif // !i_no_emplace -#if !defined i_no_cmp || defined _i_has_eq +#if defined _i_has_eq || defined _i_has_cmp STC_DEF _cx_iter _cx_MEMB(_find_in)(_cx_iter i1, _cx_iter i2, _cx_raw raw) { @@ -392,7 +392,7 @@ _cx_MEMB(_find_in)(_cx_iter i1, _cx_iter i2, _cx_raw raw) { return i2; } #endif -#ifndef i_no_cmp +#if defined _i_has_cmp STC_DEF _cx_iter _cx_MEMB(_binary_search_in)(_cx_iter i1, _cx_iter i2, const _cx_raw raw, @@ -417,7 +417,7 @@ STC_DEF int _cx_MEMB(_value_cmp)(const _cx_value* x, const _cx_value* y) { const _cx_raw ry = i_keyto(y); return i_cmp((&rx), (&ry)); } -#endif // !c_no_cmp +#endif // _i_has_cmp #endif // i_implement #define CVEC_H_INCLUDED #include "priv/template2.h" diff --git a/include/stc/priv/template.h b/include/stc/priv/template.h index c1b7c1e7..03c27bdb 100644 --- a/include/stc/priv/template.h +++ b/include/stc/priv/template.h @@ -102,12 +102,6 @@ #if c_option(c_no_emplace) #define i_no_emplace #endif -#ifdef i_eq - #define _i_has_eq -#endif -#if defined i_cmp || defined i_less - #define _i_has_cmp -#endif #if defined i_key_str #define i_keyclass cstr @@ -155,10 +149,10 @@ #endif #ifdef i_rawclass - #if !defined i_cmp && !defined i_no_cmp + #if !(defined i_cmp || defined i_no_cmp) #define i_cmp c_PASTE(i_keyraw, _cmp) #endif - #if !defined i_hash && !defined i_no_hash + #if !(defined i_hash || defined i_no_hash || defined i_no_cmp) #define i_hash c_PASTE(i_keyraw, _hash) #endif #endif @@ -176,7 +170,7 @@ #ifndef i_tag #define i_tag i_key #endif -#if c_option(c_no_clone) +#if c_option(c_no_clone) || defined _i_carc #define i_no_clone #elif !(defined i_keyclone || defined i_no_clone) && (defined i_keydrop || defined i_keyraw) #error i_keyclone/valclone should be defined when i_keydrop/valdrop or i_keyraw/valraw is defined @@ -199,24 +193,33 @@ #define i_keydrop c_default_drop #endif -// i_eq, i_less, i_cmp -#if !defined i_eq && (defined i_cmp || defined i_less) - #define i_eq(x, y) !(i_cmp(x, y)) -#elif !defined i_eq - #define i_eq c_default_eq -#endif -#if defined i_less && defined i_cmp - #error "Only one of i_less and i_cmp may be defined" -#elif !defined i_less && !defined i_cmp - #define i_less c_default_less -#elif !defined i_less - #define i_less(x, y) (i_cmp(x, y)) < 0 -#endif -#ifndef i_cmp - #define i_cmp(x, y) (i_less(y, x)) - (i_less(x, y)) +#ifndef i_no_cmp + #if c_option(c_native_cmp) || defined i_native_cmp || defined i_cmp || defined i_less + #define _i_has_cmp + #endif + #if defined i_eq + #define _i_has_eq + #endif + + // i_eq, i_less, i_cmp + #if !defined i_eq && (defined i_cmp || defined i_less) + #define i_eq(x, y) !(i_cmp(x, y)) + #elif !defined i_eq + #define i_eq(x, y) *x == *y + #endif + #if defined i_cmp && defined i_less + #error "Only one of i_cmp and i_less may be defined" + #elif defined i_cmp + #define i_less(x, y) (i_cmp(x, y)) < 0 + #elif !defined i_less + #define i_less(x, y) *x < *y + #endif + #ifndef i_cmp + #define i_cmp(x, y) (i_less(y, x)) - (i_less(x, y)) + #endif #endif -#ifndef i_hash +#if !(defined i_hash || defined _i_cbox || defined _i_carc) #define i_hash c_default_hash #endif diff --git a/include/stc/priv/template2.h b/include/stc/priv/template2.h index 47b82937..bd8bc5fc 100644 --- a/include/stc/priv/template2.h +++ b/include/stc/priv/template2.h @@ -67,6 +67,7 @@ #undef i_realloc #undef i_free +#undef i_native_cmp #undef i_no_cmp #undef i_no_hash #undef i_no_clone @@ -74,9 +75,9 @@ #undef i_is_forward #undef i_has_emplace +#undef _i_has_cmp +#undef _i_has_eq #undef _i_prefix #undef _i_expandby -#undef _i_has_eq -#undef _i_has_cmp #undef _i_template #endif diff --git a/misc/examples/arc_containers.c b/misc/examples/arc_containers.c index 7038734e..b05bbea6 100644 --- a/misc/examples/arc_containers.c +++ b/misc/examples/arc_containers.c @@ -13,17 +13,15 @@ #define i_val Map #define i_valdrop(p) (printf("drop Arc:\n"), Map_drop(p)) // no need for atomic ref. count in single thread: -#define i_opt c_no_atomic|c_no_cmp|c_no_clone +#define i_opt c_no_atomic #include #define i_type Stack #define i_valboxed Arc // define i_valboxed for carc/cbox value (not i_val) -#define i_opt c_no_cmp #include #define i_type List #define i_valboxed Arc // as above -#define i_opt c_no_cmp #include int main() diff --git a/misc/examples/arc_demo.c b/misc/examples/arc_demo.c index 2339adbb..4cda1c8b 100644 --- a/misc/examples/arc_demo.c +++ b/misc/examples/arc_demo.c @@ -11,13 +11,13 @@ void int_drop(int* x) { #define i_type Arc // set type name to be defined (instead of 'carc_int') #define i_val int #define i_valdrop int_drop // optional, just to display the elements destroyed -#define i_no_clone // required because of valdrop +#define i_native_cmp // use int comparison (x < y, x == y). #include // Arc -#define i_keyboxed Arc // note: use i_keyboxed instead of i_key for carc/cbox elements +#define i_keyboxed Arc // note: use i_keyboxed instead of i_key for carc/cbox elements #include // csset_Arc (like: std::set>) -#define i_valboxed Arc // note: as above. +#define i_valboxed Arc // note: as above. #include // cvec_Arc (like: std::vector>) int main() @@ -25,8 +25,12 @@ int main() const int years[] = {2021, 2012, 2022, 2015}; cvec_Arc vec = {0}; - c_forrange (i, c_arraylen(years)) - cvec_Arc_push(&vec, Arc_from(years[i])); + c_forrange (i, c_arraylen(years)) { + cvec_Arc_emplace(&vec, years[i]); + // cvec_Arc_push(&vec, Arc_from(years[i])); // alt. + } + + cvec_Arc_sort(&vec); printf("vec:"); c_foreach (i, cvec_Arc, vec) diff --git a/misc/examples/arcvec_erase.c b/misc/examples/arcvec_erase.c index 28160c1c..0b9252d9 100644 --- a/misc/examples/arcvec_erase.c +++ b/misc/examples/arcvec_erase.c @@ -5,7 +5,7 @@ void show_drop(int* x) { printf("drop: %d\n", *x); } #define i_type Arc #define i_val int #define i_valdrop show_drop -#define i_no_clone // required because of valdrop +#define i_native_cmp // enable sort/search for int type #include // Shared pointer to int #define i_type Vec diff --git a/misc/examples/box2.c b/misc/examples/box2.c index 963a3815..d3762462 100644 --- a/misc/examples/box2.c +++ b/misc/examples/box2.c @@ -15,16 +15,14 @@ typedef struct { } Rectangle; #define i_val Point -#define i_no_cmp #include // cbox_Point #define i_val Rectangle -#define i_no_cmp #include // cbox_Rectangle // Box in box: -#define i_valboxed cbox_Point // NB: use i_valboxed when value is a cbox or carc! #define i_type BoxBoxPoint +#define i_valboxed cbox_Point // NB: use i_valboxed when value is a cbox or carc! #define i_no_cmp #include // BoxBoxPoint diff --git a/misc/examples/complex.c b/misc/examples/complex.c index 2d8dbf62..b5ea847a 100644 --- a/misc/examples/complex.c +++ b/misc/examples/complex.c @@ -13,8 +13,8 @@ #include #define i_type StackList -#define i_valclass FloatStack // "class" picks up _clone, _drop -#define i_opt c_no_cmp // no FloatStack_cmp() +#define i_valclass FloatStack // "class" picks up _clone, _drop, _cmp +#define i_opt c_no_cmp // exclude FloatStack_cmp(): not defined #include #define i_type ListMap diff --git a/misc/examples/csmap_find.c b/misc/examples/csmap_find.c index c123e398..645828a3 100644 --- a/misc/examples/csmap_find.c +++ b/misc/examples/csmap_find.c @@ -9,7 +9,6 @@ #include #define i_val csmap_istr_raw -#define i_opt c_no_cmp #define i_tag istr #include diff --git a/misc/examples/demos.c b/misc/examples/demos.c index 8488dfb9..b2f50ebf 100644 --- a/misc/examples/demos.c +++ b/misc/examples/demos.c @@ -74,6 +74,7 @@ void vectordemo2() #define i_val int #define i_tag ix +#define i_native_cmp #include void listdemo1() diff --git a/misc/examples/intrusive.c b/misc/examples/intrusive.c index 0d503575..0d59c5ab 100644 --- a/misc/examples/intrusive.c +++ b/misc/examples/intrusive.c @@ -4,7 +4,8 @@ #define i_type List #define i_val int -#include +#define i_native_cmp +#include void printList(List list) { printf("list:"); @@ -16,7 +17,7 @@ void printList(List list) { int main() { List list = {0}; c_forlist (i, int, {6, 9, 3, 1, 7, 4, 5, 2, 8}) - List_push_back_node(&list, c_new(List_node, {0, *i.ref})); + List_push_back_node(&list, c_new(List_node, {.value=*i.ref})); printList(list); diff --git a/misc/examples/list.c b/misc/examples/list.c index ed27aa50..08fe837f 100644 --- a/misc/examples/list.c +++ b/misc/examples/list.c @@ -5,6 +5,7 @@ #define i_type DList #define i_val double +#define i_native_cmp #include int main() { diff --git a/misc/examples/lower_bound.c b/misc/examples/lower_bound.c index d146c4d9..5b395e45 100644 --- a/misc/examples/lower_bound.c +++ b/misc/examples/lower_bound.c @@ -1,6 +1,7 @@ #include #define i_val int +#define i_native_cmp #include #define i_val int diff --git a/misc/examples/music_arc.c b/misc/examples/music_arc.c index 18ea30c0..4efc35c8 100644 --- a/misc/examples/music_arc.c +++ b/misc/examples/music_arc.c @@ -23,13 +23,13 @@ void Song_drop(Song* s) { // Define the shared pointer: #define i_type SongArc #define i_valclass Song -#define i_opt c_no_hash // arc require hash fn, disable as we don't need it. +#define i_no_hash // no hash fn for Song, fallback hash pointer to Song. #include // ... and a vector of them #define i_type SongVec -#define i_valboxed SongArc // use i_valboxed on carc / cbox instead of i_val -#include +#define i_valboxed SongArc // use i_valboxed on carc / cbox (instead of i_val) +#include void example3() { diff --git a/misc/examples/new_list.c b/misc/examples/new_list.c index 382943bb..b5ff847e 100644 --- a/misc/examples/new_list.c +++ b/misc/examples/new_list.c @@ -27,12 +27,13 @@ int point_cmp(const Point* a, const Point* b) { #include #define i_val float +#define i_native_cmp // use < and == operators for comparison #include void MyStruct_drop(MyStruct* s); #define i_type MyList -#define i_valclass MyStruct // i_valclass uses MyStruct_drop -#define i_opt c_no_clone|c_no_cmp +#define i_valclass MyStruct // MyStruct contains "class"-types, so define as "class" +#define i_opt c_no_clone|c_no_cmp // exclude cloning and comparison support #include void MyStruct_drop(MyStruct* s) { diff --git a/misc/examples/new_sptr.c b/misc/examples/new_sptr.c index 36a61f9c..2eff41a5 100644 --- a/misc/examples/new_sptr.c +++ b/misc/examples/new_sptr.c @@ -9,15 +9,13 @@ int Person_cmp(const Person* a, const Person* b); uint64_t Person_hash(const Person* p); #define i_type PersonArc -#define i_valclass Person // "class" ensure Person_drop will be called -#define i_cmp Person_cmp // enable carc object comparisons (not ptr to obj) -#define i_hash Person_hash // enable carc object hash (not ptr to obj) +#define i_valclass Person // "class" assume _clone, _drop, _cmp, _hash is defined. #include #define i_type IPtr #define i_val int #define i_valdrop(x) printf("drop: %d\n", *x) -#define i_no_clone +#define i_native_cmp #include #define i_type IPStack diff --git a/misc/examples/new_vec.c b/misc/examples/new_vec.c index e10910d9..6329b185 100644 --- a/misc/examples/new_vec.c +++ b/misc/examples/new_vec.c @@ -10,16 +10,17 @@ typedef struct MyStruct { } MyStruct; #define i_val int -#define i_is_forward #define i_tag i32 +#define i_is_forward #include typedef struct Point { int x, y; } Point; #define i_val Point +#define i_tag pnt #define i_less(a, b) a->x < b->x || (a->x == b->x && a->y < b->y) +#define i_eq(a, b) a->x == b->x && a->y == b->y #define i_is_forward -#define i_tag pnt #include int main() diff --git a/misc/examples/scheduler.c b/misc/examples/scheduler.c index 59101b4e..04f7ba4a 100644 --- a/misc/examples/scheduler.c +++ b/misc/examples/scheduler.c @@ -8,7 +8,6 @@ cco_closure(bool, Task, #define i_type Scheduler #define i_val struct Task -#define i_no_cmp #include static bool schedule(Scheduler* sched) -- cgit v1.2.3 From e25dec033773ab713a7593a923e2c83745be0b9a Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 2 Jul 2023 22:01:46 +0200 Subject: Update in coroutine API. cco_yield, cco_await, cco_await_on, cco_block_on has changed. cco_final: renamed => cco_cleanup: Reverted i_retain template param back to => i_more. --- docs/ccommon_api.md | 62 +++++++++++------- include/stc/algo/coroutine.h | 120 ++++++++++++++++++++-------------- include/stc/algo/sort.h | 2 +- include/stc/cdeq.h | 6 +- include/stc/priv/template2.h | 4 +- misc/benchmarks/various/csort_bench.c | 2 +- misc/examples/cointerleave.c | 11 ++-- misc/examples/coread.c | 7 +- misc/examples/coroutines.c | 54 +++++++-------- misc/examples/dining_philosophers.c | 16 +++-- misc/examples/generator.c | 5 +- misc/examples/scheduler.c | 34 +++++----- misc/examples/triples.c | 10 +-- 13 files changed, 189 insertions(+), 144 deletions(-) (limited to 'include/stc/priv/template2.h') diff --git a/docs/ccommon_api.md b/docs/ccommon_api.md index c9c65156..b30bdda6 100644 --- a/docs/ccommon_api.md +++ b/docs/ccommon_api.md @@ -222,11 +222,11 @@ int main() { } ``` Containers with random access may also be sorted. Even sorting cdeq/cqueue (with ring buffer) is -possible and very fast. Note that `i_retain` must be defined to retain specified template parameters for use by sort: +possible and very fast. Note that `i_more` must be defined to retain specified template parameters for use by sort: ```c #define i_type MyDeq #define i_val int -#define i_retain +#define i_more #include // deque #include #include @@ -313,6 +313,7 @@ the gcd() function. It also ensures that it stops when the diagonal size >= 100: [ [Run this code](https://godbolt.org/z/coqqrfbd5) ] ```c #include +#include struct triples { int n; // input: max number of triples to be generated. @@ -320,22 +321,23 @@ struct triples { int cco_state; // required member }; -bool triples(struct triples* i) { // coroutine +int triples(struct triples* i) { // coroutine cco_routine(i) { for (i->c = 5; i->n; ++i->c) { for (i->a = 1; i->a < i->c; ++i->a) { for (i->b = i->a + 1; i->b < i->c; ++i->b) { if ((int64_t)i->a*i->a + (int64_t)i->b*i->b == (int64_t)i->c*i->c) { - cco_yield(false); - if (--i->n == 0) cco_return; + cco_yield(); + if (--i->n == 0) + cco_return; } } } } - cco_final: + cco_cleanup: puts("done"); } - return true; + return 0; } int gcd(int a, int b) { // greatest common denominator @@ -352,7 +354,7 @@ int main() struct triples t = {.n=INT32_MAX}; int n = 0; - while (!triples(&t)) { + while (triples(&t)) { // Skip triples with GCD(a,b) > 1 if (gcd(t.a, t.b) > 1) continue; @@ -366,28 +368,36 @@ int main() } ``` ### Coroutine API -**Note**: *cco_yield()* may not be called inside a `switch` statement. Use `if-else-if` constructs instead. -To resume the coroutine from where it was suspended with *cco_yield()*, simply call the coroutine again. +To resume the coroutine from where it was suspended with *cco_yield()*: call the coroutine again. + +**Note**: *cco_yield()* / *cco_await()* may not be called inside a `switch` statement; either use +`if-else-if` constructs, or `cco_switch / cco_case / cco_default` for switch-emulation instead. | | Function / operator | Description | |:----------|:-------------------------------------|:----------------------------------------| -| | `cco_final:` | Label for cleanup in coroutine | +| | Function / 'keywords': | | +|`cco_result` | Enum `CCO_DONE=0`, `CCO_YIELD`, `CCO_AWAIT` | Recommended return values in coroutines | +| | Function / 'keywords': | | +| | `cco_cleanup:` | Label for cleanup position in coroutine | | `bool` | `cco_done(co)` | Is coroutine done? | -| | `cco_routine(co) { ... }` | The coroutine closure | -| | `cco_yield()` | Yield/suspend execution | -| | `cco_yield(ret)` | Yield/suspend execution and return ret | -| | `cco_await(promise)` | Await/suspend until promise is true | -| | `cco_await(promise, ret)` | Await/suspend with ret value | -| | `cco_return` | Replaces return. Jump to cco_final: if exist| -| | `cco_return_v(val)` | Yield final value, enter final-state | -| | `cco_closure(Ret, Closure, ...)` | Define coroutine closure struct. | -| `void` | `cco_await_on(closure) { }` | Await on closure to finish | -| `void` | `cco_await_on(co, func) { }` | Await on func(co) to finish | +| | `cco_routine(co) { }` | The coroutine scope | +| | `cco_yield();` | Yield/suspend execution (return CCO_YIELD)| +| | `cco_yield_v();` | Yield/suspend execution (return void) | +| | `cco_yield_v(ret);` | Yield/suspend execution (return ret) | +| | `cco_yield_final();` | Yield final time, enables cleanup-state | +| | `cco_yield_final(val);` | Yield a final value (e.g. CCO_ERROR) | +| | `cco_await(condition);` | Suspend until condition is true (return CCO_AWAIT)| +| | `cco_await_v(condition);` | Suspend until condition is true (return void) | +| | `cco_await_v(condition, ret);` | Suspend until condition is true (return ret)| +| | `cco_await_on(cocall);` | Await on sub-coroutine to finish | +| | `cco_return;` | Return from coroutine (inside cco_routine) | +| | `cco_closure(Closure, ...);` | Define a coroutine closure struct (optional) | | | Semaphores: | | | | `cco_sem` | Semaphore type | +| `cco_sem` | `cco_sem_from(long value)` | Create semaphore | +| | `cco_sem_set(sem, long value)` | Set semaphore value | | | `cco_sem_await(sem)` | Await for the semaphore count > 0 | | | `cco_sem_await(sem, ret)` | Await with ret on the semaphore | -| `cco_sem` | `cco_sem_init(long value)` | Set semaphore value | | | `cco_sem_release(sem)` | Signal the semaphore (count += 1) | | | Timers: | | | | `cco_timer` | Timer type | @@ -401,11 +411,15 @@ To resume the coroutine from where it was suspended with *cco_yield()*, simply c | | From caller side: | | | `void` | `cco_stop(co)` | Next call of coroutine finalizes | | `void` | `cco_reset(co)` | Reset state to initial (for reuse) | -| `void` | `cco_block_on(closure) { }` | Run blocking until closure is finished | -| `void` | `cco_block_on(co, func) { }` | Run blocking until func is finished | +| `void` | `cco_block_on(cocall) { }` | Run blocking until cocall is finished | +| `void` | `cco_block_on(cocall, int *result) { }`| Run blocking until cocall is finished | | | Time functions: | | | `double` | `cco_time(void)` | Return secs with usec prec. since Epoch | | | `cco_sleep(double sec)` | Sleep for seconds (msec or usec prec.) | +| | Emulate switch: | | +| | `cco_switch(x) { }` | Like switch syntax | +| | `cco_case(val) { }` | Braces are required. Fall-through if no break; | +| | `cco_default { }` | Default action | --- ## RAII scope macros diff --git a/include/stc/algo/coroutine.h b/include/stc/algo/coroutine.h index e20fd8ad..198b0439 100644 --- a/include/stc/algo/coroutine.h +++ b/include/stc/algo/coroutine.h @@ -32,22 +32,22 @@ struct iterpair { int cco_state; // required member }; -bool iterpair(struct iterpair* I) { +int iterpair(struct iterpair* I) { cco_routine(I) { for (I->x = 0; I->x < I->max_x; I->x++) for (I->y = 0; I->y < I->max_y; I->y++) - cco_yield(false); + cco_yield(); - cco_final: // required if there is cleanup code + cco_cleanup: // required if there is cleanup code puts("final"); } - return true; // finished + return 0; // CCO_DONE } int main(void) { struct iterpair it = {.max_x=3, .max_y=3}; int n = 0; - while (!iterpair(&it)) + while (iterpair(&it)) { printf("%d %d\n", it.x, it.y); // example of early stop: @@ -59,12 +59,19 @@ int main(void) { #include "../ccommon.h" enum { - cco_state_final = -1, - cco_state_done = -2, + CCO_STATE_CLEANUP = -1, + CCO_STATE_DONE = -2, }; +typedef enum { + CCO_DONE = 0, + CCO_YIELD = 1, + CCO_AWAIT = 2, + CCO_ERROR = -1, +} cco_result; #define cco_initial(co) ((co)->cco_state == 0) -#define cco_done(co) ((co)->cco_state == cco_state_done) +#define cco_suspended(co) ((co)->cco_state > 0) +#define cco_done(co) ((co)->cco_state == CCO_STATE_DONE) /* Emulate switch in coro: always use { } after cco_case(val) and cco_default. */ #define cco_switch(x) for (long long _sw = (long long)(x), _b=0; !_b; _b=1) @@ -72,83 +79,97 @@ enum { #define cco_default #define cco_routine(co) \ - for (int *_state = &(co)->cco_state; *_state != cco_state_done; *_state = cco_state_done) \ + for (int *_state = &(co)->cco_state; *_state != CCO_STATE_DONE; *_state = CCO_STATE_DONE) \ _resume: switch (*_state) case 0: // thanks, @liigo! -#define cco_yield(ret) \ +#define cco_yield() cco_yield_v(CCO_YIELD) +#define cco_yield_v(ret) \ do { \ *_state = __LINE__; return ret; goto _resume; \ case __LINE__:; \ } while (0) -#define cco_await(...) c_MACRO_OVERLOAD(cco_await, __VA_ARGS__) -#define cco_await_1(promise) cco_await_2(promise, ) -#define cco_await_2(promise, ret) \ +#define cco_await(promise) cco_await_v_2(promise, CCO_AWAIT) +#define cco_await_v(...) c_MACRO_OVERLOAD(cco_await_v, __VA_ARGS__) +#define cco_await_v_1(promise) cco_await_v_2(promise, ) +#define cco_await_v_2(promise, ret) \ do { \ *_state = __LINE__; \ case __LINE__: if (!(promise)) {return ret; goto _resume;} \ } while (0) -#define cco_closure(Ret, Closure, ...) \ - struct Closure { \ - Ret (*cco_fn)(struct Closure*); \ - int cco_state; \ - __VA_ARGS__ \ - } - -typedef struct cco_base { - void (*cco_fn)(struct cco_base*); - int cco_state; -} cco_base; - -#define cco_base_cast(closure) \ - ((cco_base *)(closure) + 0*sizeof((cco_resume(closure), (int*)0 == &(closure)->cco_state))) - -#define cco_resume(closure) (closure)->cco_fn(closure) -#define cco_await_on(...) c_MACRO_OVERLOAD(cco_await_on, __VA_ARGS__) -#define cco_await_on_1(closure) cco_await_2((cco_resume(closure), cco_done(closure)), ) -#define cco_await_on_2(co, func) cco_await_2((func(co), cco_done(co)), ) +/* cco_await_on(): assumes coroutine returns a cco_result value (int) */ +#define cco_await_on(corocall) \ + do { \ + *_state = __LINE__; \ + case __LINE__: { int _r = corocall; if (_r != CCO_DONE) {return _r; goto _resume;} } \ + } while (0) +/* cco_block_on(): assumes coroutine returns a cco_result value (int) */ #define cco_block_on(...) c_MACRO_OVERLOAD(cco_block_on, __VA_ARGS__) -#define cco_block_on_1(closure) while (cco_resume(closure), !cco_done(closure)) -#define cco_block_on_2(co, func) while (func(co), !cco_done(co)) +#define cco_block_on_1(corocall) while (corocall != CCO_DONE) +#define cco_block_on_2(corocall, res) while ((*(res) = (corocall)) != CCO_DONE) -#define cco_final \ - *_state = cco_state_final; case cco_state_final +#define cco_cleanup \ + *_state = CCO_STATE_CLEANUP; case CCO_STATE_CLEANUP #define cco_return \ do { \ - *_state = *_state >= 0 ? cco_state_final : cco_state_done; \ + *_state = *_state >= 0 ? CCO_STATE_CLEANUP : CCO_STATE_DONE; \ goto _resume; \ } while (0) -#define cco_return_v(value) \ +#define cco_yield_final() cco_yield_final_v(CCO_YIELD) +#define cco_yield_final_v(value) \ do { \ - *_state = *_state >= 0 ? cco_state_final : cco_state_done; \ + *_state = *_state >= 0 ? CCO_STATE_CLEANUP : CCO_STATE_DONE; \ return value; \ } while (0) #define cco_stop(co) \ do { \ int* _s = &(co)->cco_state; \ - if (*_s > 0) *_s = cco_state_final; \ - else if (*_s == 0) *_s = cco_state_done; \ + if (*_s > 0) *_s = CCO_STATE_CLEANUP; \ + else if (*_s == 0) *_s = CCO_STATE_DONE; \ } while (0) #define cco_reset(co) \ (void)((co)->cco_state = 0) +/* + * Closure (optional) + */ + +#define cco_closure(Name, ...) \ + struct Name { \ + int (*cco_fn)(struct Name*); \ + int cco_state; \ + __VA_ARGS__ \ + } + +typedef struct cco_base { + int (*cco_fn)(struct cco_base*); + int cco_state; +} cco_base; + +#define cco_resume(closure) \ + (closure)->cco_fn(closure) + +#define cco_cast(closure) \ + ((cco_base *)(closure) + 0*sizeof((cco_resume(closure), (int*)0 == &(closure)->cco_state))) + /* * Semaphore */ typedef struct { intptr_t count; } cco_sem; -#define cco_sem_await(...) c_MACRO_OVERLOAD(cco_sem_await, __VA_ARGS__) -#define cco_sem_await_1(sem) cco_sem_await_2(sem, ) -#define cco_sem_await_2(sem, ret) \ +#define cco_sem_await(sem) cco_sem_await_v_2(sem, CCO_AWAIT) +#define cco_sem_await_v(...) c_MACRO_OVERLOAD(cco_sem_await_v, __VA_ARGS__) +#define cco_sem_await_v_1(sem) cco_sem_await_v_2(sem, ) +#define cco_sem_await_v_2(sem, ret) \ do { \ - cco_await_2((sem)->count > 0, ret); \ + cco_await_v_2((sem)->count > 0, ret); \ --(sem)->count; \ } while (0) @@ -197,12 +218,13 @@ typedef struct { intptr_t count; } cco_sem; typedef struct { double interval, start; } cco_timer; -#define cco_timer_await(...) c_MACRO_OVERLOAD(cco_timer_await, __VA_ARGS__) -#define cco_timer_await_2(tm, sec) cco_timer_await_3(tm, sec, ) -#define cco_timer_await_3(tm, sec, ret) \ +#define cco_timer_await(tm, sec) cco_timer_await_v_3(tm, sec, CCO_AWAIT) +#define cco_timer_await_v(...) c_MACRO_OVERLOAD(cco_timer_await_v, __VA_ARGS__) +#define cco_timer_await_v_2(tm, sec) cco_timer_await_v_3(tm, sec, ) +#define cco_timer_await_v_3(tm, sec, ret) \ do { \ cco_timer_start(tm, sec); \ - cco_await_2(cco_timer_expired(tm), ret); \ + cco_await_v_2(cco_timer_expired(tm), ret); \ } while (0) static inline void cco_timer_start(cco_timer* tm, double sec) { diff --git a/include/stc/algo/sort.h b/include/stc/algo/sort.h index 002e6499..8365ccc5 100644 --- a/include/stc/algo/sort.h +++ b/include/stc/algo/sort.h @@ -44,7 +44,7 @@ int main() { // ex2: #define i_val int #define i_type IDeq -#define i_retain // retain input template params to be reused by sort.h +#define i_more // retain input template params to be reused by sort.h #include #include diff --git a/include/stc/cdeq.h b/include/stc/cdeq.h index 2db040f1..bac40f90 100644 --- a/include/stc/cdeq.h +++ b/include/stc/cdeq.h @@ -23,11 +23,11 @@ #define _i_prefix cdeq_ #define _pop _pop_front #define _pull _pull_front -#ifdef i_retain +#ifdef i_more #include "cqueue.h" - #define i_retain + #define i_more #else - #define i_retain + #define i_more #include "cqueue.h" #endif #undef _pop diff --git a/include/stc/priv/template2.h b/include/stc/priv/template2.h index bd8bc5fc..def5d01e 100644 --- a/include/stc/priv/template2.h +++ b/include/stc/priv/template2.h @@ -20,8 +20,8 @@ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ -#ifdef i_retain -#undef i_retain +#ifdef i_more +#undef i_more #else #undef i_type #undef i_tag diff --git a/misc/benchmarks/various/csort_bench.c b/misc/benchmarks/various/csort_bench.c index 93034dde..d434693f 100644 --- a/misc/benchmarks/various/csort_bench.c +++ b/misc/benchmarks/various/csort_bench.c @@ -8,7 +8,7 @@ #define NDEBUG #define i_type Ints #define i_val int -#define i_retain +#define i_more #include #include diff --git a/misc/examples/cointerleave.c b/misc/examples/cointerleave.c index 1ba7b861..61562a5f 100644 --- a/misc/examples/cointerleave.c +++ b/misc/examples/cointerleave.c @@ -15,7 +15,7 @@ static int get_value(struct GenValue* g) { cco_routine(g) { for (g->it = IVec_begin(g->v); g->it.ref; IVec_next(&g->it)) - cco_yield(*g->it.ref); + cco_yield_v(*g->it.ref); } return -1; } @@ -26,10 +26,10 @@ struct Generator { int value; }; -void interleaved(struct Generator* g) +cco_result interleaved(struct Generator* g) { cco_routine(g) { - do { + while (!(cco_done(&g->x) & cco_done(&g->y))) { g->value = get_value(&g->x); if (!cco_done(&g->x)) cco_yield(); @@ -37,8 +37,9 @@ void interleaved(struct Generator* g) g->value = get_value(&g->y); if (!cco_done(&g->y)) cco_yield(); - } while (!(cco_done(&g->x) & cco_done(&g->y))); + } } + return CCO_DONE; } void Use(void) @@ -48,7 +49,7 @@ void Use(void) struct Generator g = {{&a}, {&b}}; - cco_block_on(&g, interleaved) { + cco_block_on(interleaved(&g)) { printf("%d ", g.value); } puts(""); diff --git a/misc/examples/coread.c b/misc/examples/coread.c index 622228c0..a13f6be5 100644 --- a/misc/examples/coread.c +++ b/misc/examples/coread.c @@ -12,7 +12,7 @@ struct file_read { cstr line; }; -void file_read(struct file_read* g) +int file_read(struct file_read* g) { cco_routine(g) { g->fp = fopen(g->filename, "r"); @@ -21,18 +21,19 @@ void file_read(struct file_read* g) cco_await(!cstr_getline(&g->line, g->fp)); - cco_final: + cco_cleanup: printf("finish\n"); cstr_drop(&g->line); if (g->fp) fclose(g->fp); } + return 0; } int main(void) { struct file_read g = {__FILE__}; int n = 0; - cco_block_on(&g, file_read) + cco_block_on(file_read(&g)) { printf("%3d %s\n", ++n, cstr_str(&g.line)); //if (n == 10) cco_stop(&g); diff --git a/misc/examples/coroutines.c b/misc/examples/coroutines.c index 1e900fa1..b8dfaa13 100644 --- a/misc/examples/coroutines.c +++ b/misc/examples/coroutines.c @@ -4,27 +4,26 @@ // Demonstrate to call another coroutine from a coroutine: // First create prime generator, then call fibonacci sequence: -typedef long long llong; -bool is_prime(int64_t i) { - for (llong j=2; j*j <= i; ++j) +bool is_prime(long long i) { + for (long long j=2; j*j <= i; ++j) if (i % j == 0) return false; return true; } struct prime { int count, idx; - llong result, pos; + long long result, pos; int cco_state; }; -bool prime(struct prime* g) { +int prime(struct prime* g) { cco_routine(g) { if (g->result < 2) g->result = 2; if (g->result == 2) { if (g->count-- == 0) cco_return; ++g->idx; - cco_yield(false); + cco_yield(); } g->result += !(g->result & 1); for (g->pos = g->result; g->count > 0; g->pos += 2) { @@ -32,13 +31,13 @@ bool prime(struct prime* g) { --g->count; ++g->idx; g->result = g->pos; - cco_yield(false); + cco_yield(); } } - cco_final: + cco_cleanup: printf("final prm\n"); } - return true; + return 0; } @@ -46,13 +45,14 @@ bool prime(struct prime* g) { struct fibonacci { int count, idx; - llong result, b; + long long result, b; int cco_state; }; -bool fibonacci(struct fibonacci* g) { +int fibonacci(struct fibonacci* g) { assert(g->count < 94); + long long sum; cco_routine(g) { g->idx = 0; g->result = 0; @@ -61,17 +61,17 @@ bool fibonacci(struct fibonacci* g) { if (g->count-- == 0) cco_return; if (++g->idx > 1) { - // NB! locals lasts only until next cco_yield/cco_await! - llong sum = g->result + g->b; + // NB! locals lasts only until next yield/await! + sum = g->result + g->b; g->result = g->b; g->b = sum; } - cco_yield(false); + cco_yield(); } - cco_final: + cco_cleanup: printf("final fib\n"); } - return true; + return 0; } // Combine @@ -82,29 +82,31 @@ struct combined { int cco_state; }; - -void combined(struct combined* g) { +int combined(struct combined* g) { cco_routine(g) { - cco_await(prime(&g->prm)); - cco_await(fibonacci(&g->fib)); + cco_await_on(prime(&g->prm)); + cco_await_on(fibonacci(&g->fib)); // Reuse the g->prm context and extend the count: g->prm.count = 8, g->prm.result += 2; cco_reset(&g->prm); - cco_await(prime(&g->prm)); + cco_await_on(prime(&g->prm)); - cco_final: + cco_cleanup: puts("final combined"); } + return 0; } int main(void) { struct combined c = {.prm={.count=8}, .fib={14}}; + int res; - cco_block_on(&c, combined) { - printf("Prime(%d)=%lld, Fib(%d)=%lld\n", - c.prm.idx, c.prm.result, - c.fib.idx, c.fib.result); + cco_block_on(combined(&c), &res) { + if (res == CCO_YIELD) + printf("Prime(%d)=%lld, Fib(%d)=%lld\n", + c.prm.idx, c.prm.result, + c.fib.idx, c.fib.result); } } diff --git a/misc/examples/dining_philosophers.c b/misc/examples/dining_philosophers.c index e13eb055..61fe67fb 100644 --- a/misc/examples/dining_philosophers.c +++ b/misc/examples/dining_philosophers.c @@ -27,7 +27,7 @@ struct Dining { // Philosopher coroutine -void philosopher(struct Philosopher* p) +int philosopher(struct Philosopher* p) { double duration; cco_routine(p) { @@ -48,14 +48,15 @@ void philosopher(struct Philosopher* p) cco_sem_release(p->right_fork); } - cco_final: + cco_cleanup: printf("Philosopher %d finished\n", p->id); } + return 0; } // Dining coroutine -void dining(struct Dining* d) +int dining(struct Dining* d) { cco_routine(d) { for (int i = 0; i < num_forks; ++i) @@ -68,20 +69,21 @@ void dining(struct Dining* d) } while (1) { - // per-"frame" logic update of all philosophers states + // per-"frame" logic resume each philosopher for (int i = 0; i < num_philosophers; ++i) { philosopher(&d->ph[i]); } cco_yield(); // suspend, return control back to main } - cco_final: + cco_cleanup: for (int i = 0; i < num_philosophers; ++i) { cco_stop(&d->ph[i]); philosopher(&d->ph[i]); } puts("Dining finished"); } + return 0; } int main() @@ -89,13 +91,13 @@ int main() struct Dining dine; cco_reset(&dine); int n=0; - cco_timer tm = cco_timer_from(10.0); // seconds + cco_timer tm = cco_timer_from(15.0); // seconds csrand((uint64_t)time(NULL)); while (!cco_done(&dine)) { if (cco_timer_expired(&tm)) cco_stop(&dine); - dining(&dine); + dining(&dine); // resume cco_sleep(0.001); ++n; } diff --git a/misc/examples/generator.c b/misc/examples/generator.c index 6b4b8407..3ff7a645 100644 --- a/misc/examples/generator.c +++ b/misc/examples/generator.c @@ -14,7 +14,7 @@ typedef struct { int cco_state; } Triple_iter; -void Triple_next(Triple_iter* it) { +int Triple_next(Triple_iter* it) { Triple_value* g = it->ref; cco_routine(it) { @@ -29,9 +29,10 @@ void Triple_next(Triple_iter* it) { } } } - cco_final: + cco_cleanup: it->ref = NULL; } + return 0; } Triple_iter Triple_begin(Triple* g) { diff --git a/misc/examples/scheduler.c b/misc/examples/scheduler.c index 04f7ba4a..c1168850 100644 --- a/misc/examples/scheduler.c +++ b/misc/examples/scheduler.c @@ -2,9 +2,11 @@ #include #include -cco_closure(bool, Task, +struct Task { + int (*fn)(struct Task*); + int cco_state; struct Scheduler* sched; -); +}; #define i_type Scheduler #define i_val struct Task @@ -16,49 +18,49 @@ static bool schedule(Scheduler* sched) Scheduler_pop(sched); if (!cco_done(&task)) - cco_resume(&task); + task.fn(&task); return !Scheduler_empty(sched); } -static bool push_task(const struct Task* task) +static int push_task(const struct Task* task) { Scheduler_push(task->sched, *task); - return false; + return CCO_YIELD; } -static bool taskA(struct Task* task) +static int taskA(struct Task* task) { cco_routine(task) { puts("Hello, from task A"); - cco_yield(push_task(task)); + cco_yield_v(push_task(task)); puts("A is back doing work"); - cco_yield(push_task(task)); + cco_yield_v(push_task(task)); puts("A is back doing more work"); - cco_yield(push_task(task)); + cco_yield_v(push_task(task)); puts("A is back doing even more work"); } - return true; + return 0; } -static bool taskB(struct Task* task) +static int taskB(struct Task* task) { cco_routine(task) { puts("Hello, from task B"); - cco_yield(push_task(task)); + cco_yield_v(push_task(task)); puts("B is back doing work"); - cco_yield(push_task(task)); + cco_yield_v(push_task(task)); puts("B is back doing more work"); } - return true; + return 0; } void Use(void) { Scheduler scheduler = c_init(Scheduler, { - {.cco_fn=taskA, .sched=&scheduler}, - {.cco_fn=taskB, .sched=&scheduler}, + {.fn=taskA, .sched=&scheduler}, + {.fn=taskB, .sched=&scheduler}, }); while (schedule(&scheduler)) {} diff --git a/misc/examples/triples.c b/misc/examples/triples.c index 17e3d40b..a8ca6b47 100644 --- a/misc/examples/triples.c +++ b/misc/examples/triples.c @@ -32,7 +32,7 @@ struct triples { int cco_state; }; -void triples_coro(struct triples* t) { +int triples_coro(struct triples* t) { cco_routine(t) { t->count = 0; for (t->c = 5; t->size; ++t->c) { @@ -46,9 +46,10 @@ void triples_coro(struct triples* t) { } } } - cco_final: + cco_cleanup: puts("done"); } + return 0; } int main() @@ -57,11 +58,10 @@ int main() triples_vanilla(5); puts("\nCoroutine triples:"); - struct triples t = {INT32_MAX}; + struct triples t = {.size=INT32_MAX}; int n = 0; - while (!cco_done(&t)) { - triples_coro(&t); + while (triples_coro(&t)) { if (gcd(t.a, t.b) > 1) continue; if (t.c < 100) -- cgit v1.2.3 From 313c1d7bb9b92e75801429c1f7f132589860292e Mon Sep 17 00:00:00 2001 From: tylov Date: Tue, 18 Jul 2023 01:36:51 +0200 Subject: Renamed i_native_cmp => i_cmp_native Added c_all_of(), c_any_of(), c_none_of() to algo/filter.h --- README.md | 4 ++-- docs/carc_api.md | 24 +++++++++++++-------- docs/cbox_api.md | 29 +++++++++++++++----------- docs/cdeq_api.md | 23 +++++++++++---------- docs/clist_api.md | 21 ++++++++++--------- docs/cmap_api.md | 39 +++++++++++++++++------------------ docs/cpque_api.md | 18 ++++++++-------- docs/cqueue_api.md | 16 +++++++------- docs/cset_api.md | 26 +++++++++++------------ docs/csmap_api.md | 36 ++++++++++++++++---------------- docs/csset_api.md | 18 ++++++++-------- docs/cstack_api.md | 16 +++++++------- docs/cvec_api.md | 23 +++++++++++---------- include/stc/algo/coroutine.h | 13 ++++++++---- include/stc/algo/filter.h | 16 +++++++++++++- include/stc/priv/template.h | 8 +++---- include/stc/priv/template2.h | 2 +- misc/benchmarks/various/csort_bench.c | 2 +- misc/examples/arc_demo.c | 2 +- misc/examples/arcvec_erase.c | 2 +- misc/examples/demos.c | 2 +- misc/examples/intrusive.c | 2 +- misc/examples/list.c | 2 +- misc/examples/lower_bound.c | 2 +- misc/examples/new_list.c | 2 +- misc/examples/new_sptr.c | 2 +- 26 files changed, 191 insertions(+), 159 deletions(-) (limited to 'include/stc/priv/template2.h') diff --git a/README.md b/README.md index b7e06790..6bbe50ee 100644 --- a/README.md +++ b/README.md @@ -252,7 +252,7 @@ struct Point { float x, y; }; #include // cvec_pnt: vector of struct Point #define i_key int -#define i_native_cmp // enable sort/search. Use native `<` and `==` operators +#define i_cmp_native // enable sort/search. Use native `<` and `==` operators #include // clist_int: singly linked list #define i_key int @@ -619,7 +619,7 @@ STC is generally very memory efficient. Memory usage for the different container - cspan: Support for column-major (fortran order) multidim spans and transposed views. - Removed default comparison for clist, cvec and cdeq (as with cstack and cqueue). - Using i_key_str, i_keyclass, i_keyboxed still expects comparisons defined. - - Define i_native_cmp to enable built-in i_key types comparisons (<, ==). + - Define i_cmp_native to enable built-in i_key types comparisons (<, ==). - cstr and csview are now shared linked by default. Static linking by defining i_static. - New cdeq and cqueue implementation(s), using circular buffer. - Renamed i_extern => i_import. diff --git a/docs/carc_api.md b/docs/carc_api.md index 8b7b67a1..fb79019a 100644 --- a/docs/carc_api.md +++ b/docs/carc_api.md @@ -20,15 +20,21 @@ See similar c++ class [std::shared_ptr](https://en.cppreference.com/w/cpp/memory ## Header file and declaration ```c -#define i_type // full typename of the carc -#define i_key // element type: REQUIRED - -#define i_keyraw // convertion "raw" type - defaults to i_key -#define i_keyto // convertion func i_key* => i_keyraw: REQUIRED IF i_keyraw defined. -#define i_keyfrom // convertion func i_keyraw => i_key - -#define i_opt c_no_atomic // Non-atomic reference counting, like Rust Rc. -#define i_tag // alternative typename: carc_{i_tag}. i_tag defaults to i_key +#define i_key // element type: REQUIRED. Note: i_val* may be specified instead of i_key*. +#define i_type // carc container type name +#define i_cmp // three-way compareison. REQUIRED IF i_key is a non-integral type + // Note that containers of carcs will "inherit" i_cmp + // when using carc in containers with i_valboxed MyArc - ie. the i_type. +#define i_cmp_native // define instead of i_cmp only when i_key is an integral/native-type. +#define i_keydrop // destroy element func - defaults to empty destruct +#define i_keyclone // REQUIRED if i_keydrop is defined, unless 'i_opt c_no_clone' is defined. + +#define i_keyraw // convertion type (lookup): default to {i_key} +#define i_keyto // convertion func i_key* => i_keyraw: REQUIRED IF i_keyraw defined. +#define i_keyfrom // from-raw func. + +#define i_opt c_no_atomic // Non-atomic reference counting, like Rust Rc. +#define i_tag // alternative typename: carc_{i_tag}. i_tag defaults to i_key #include ``` `X` should be replaced by the value of `i_tag` in all of the following documentation. diff --git a/docs/cbox_api.md b/docs/cbox_api.md index b6c76d2f..0e6fca64 100644 --- a/docs/cbox_api.md +++ b/docs/cbox_api.md @@ -14,18 +14,23 @@ See similar c++ class [std::unique_ptr](https://en.cppreference.com/w/cpp/memory ## Header file and declaration ```c -#define i_type // full typename of the cbox -#define i_key // element type: REQUIRED -#define i_cmp // three-way compare two i_key* : REQUIRED IF i_key is a non-integral type -#define i_keydrop // destroy element func - defaults to empty destruct -#define i_keyclone // REQUIRED if i_keydrop is defined, unless 'i_opt c_no_clone' is defined. - -#define i_keyraw // convertion type (lookup): default to {i_key} -#define i_keyto // convertion func i_key* => i_keyraw: REQUIRED IF i_keyraw defined. -#define i_keyfrom // from-raw func. - -#define i_keyclass // alt. to i_key: REQUIRES that {i_key}_clone, {i_key}_drop, {i_keyraw}_cmp exist. -#define i_tag // alternative typename: cbox_{i_tag}. i_tag defaults to i_key +#define i_key // element type: REQUIRED. Note: i_val* may be specified instead of i_key*. +#define i_type // cbox container type name +#define i_cmp // three-way compareison. REQUIRED IF i_key is a non-integral type + // Note that containers of carcs will "inherit" i_cmp + // when using carc in containers with i_valboxed MyArc - ie. the i_type. +#define i_cmp_native // define instead of i_cmp only when i_key is an integral/native-type. +#define i_keydrop // destroy element func - defaults to empty destruct +#define i_keyclone // REQUIRED if i_keydrop is defined, unless 'i_opt c_no_clone' is defined. + +#define i_keyraw // convertion type (lookup): default to {i_key} +#define i_keyto // convertion func i_key* => i_keyraw: REQUIRED IF i_keyraw defined. +#define i_keyfrom // from-raw func. + +#define i_tag // alternative typename: cbox_{i_tag}. i_tag defaults to i_key +#define i_keyclass // Use instead of i_key when functions {i_key}_clone, + // {i_key}_drop and {i_keyraw}_cmp exist. +#define i_keyboxed // Use instead of i_key when key is a carc- or a cbox-type. #include ``` `X` should be replaced by the value of `i_tag` in all of the following documentation. diff --git a/docs/cdeq_api.md b/docs/cdeq_api.md index c6de6cd6..38de7f66 100644 --- a/docs/cdeq_api.md +++ b/docs/cdeq_api.md @@ -10,17 +10,18 @@ See the c++ class [std::deque](https://en.cppreference.com/w/cpp/container/deque ## Header file and declaration ```c -#define i_type // full typename of the container -#define i_key // value: REQUIRED -#define i_cmp // three-way compare two i_keyraw* : REQUIRED IF i_keyraw is a non-integral type -#define i_keydrop // destroy value func - defaults to empty destruct -#define i_keyclone // REQUIRED IF i_keydrop defined - -#define i_keyraw // convertion "raw" type - defaults to i_key -#define i_keyfrom // convertion func i_keyraw => i_key -#define i_keyto // convertion func i_key* => i_keyraw - -#define i_tag // alternative typename: cdeq_{i_tag}. i_tag defaults to i_key +#define i_key // element type: REQUIRED. Note: i_val* may be specified instead of i_key*. +#define i_type // cdeq container type name +#define i_cmp // three-way compare of two i_keyraw*. +#define i_cmp_native // define instead of i_cmp only when i_key is an integral/native-type. +#define i_keydrop // destroy value func - defaults to empty destruct +#define i_keyclone // REQUIRED IF i_keydrop is defined + +#define i_keyraw // convertion "raw" type - defaults to i_key +#define i_keyfrom // convertion func i_keyraw => i_key +#define i_keyto // convertion func i_key* => i_keyraw + +#define i_tag // alternative typename: cdeq_{i_tag}. i_tag defaults to i_key #include ``` `X` should be replaced by the value of `i_tag` in all of the following documentation. diff --git a/docs/clist_api.md b/docs/clist_api.md index 3d785789..d8d614c2 100644 --- a/docs/clist_api.md +++ b/docs/clist_api.md @@ -22,16 +22,17 @@ See the c++ class [std::list](https://en.cppreference.com/w/cpp/container/list) ## Header file and declaration ```c -#define i_type // container type name (default: clist_{i_key}) -#define i_key // value: REQUIRED -#define i_cmp // three-way compare two i_keyraw* : REQUIRED IF i_keyraw is a non-integral type -#define i_keydrop // destroy value func - defaults to empty destruct -#define i_keyclone // REQUIRED IF i_keydrop defined - -#define i_keyraw // convertion "raw" type (default: {i_key}) -#define i_keyto // convertion func i_key* => i_keyraw -#define i_keyfrom // convertion func i_keyraw => i_key -#define i_tag // alternative typename: cpque_{i_tag}. i_tag defaults to i_key +#define i_key // element type: REQUIRED. Note: i_val* may be specified instead of i_key*. +#define i_type // clist container type name +#define i_cmp // three-way compare two i_keyraw* +#define i_cmp_native // define instead of i_cmp only when i_key is an integral/native-type. +#define i_keydrop // destroy value func - defaults to empty destruct +#define i_keyclone // REQUIRED IF i_keydrop defined + +#define i_keyraw // convertion "raw" type (default: {i_key}) +#define i_keyto // convertion func i_key* => i_keyraw +#define i_keyfrom // convertion func i_keyraw => i_key +#define i_tag // alternative typename: cpque_{i_tag}. i_tag defaults to i_key #include ``` diff --git a/docs/cmap_api.md b/docs/cmap_api.md index eca350b4..17f27662 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -17,26 +17,25 @@ See the c++ class [std::unordered_map](https://en.cppreference.com/w/cpp/contain ## Header file and declaration ```c -#define i_type // container type name (default: cmap_{i_key}) -#define i_key // hash key: REQUIRED -#define i_val // map value: REQUIRED -#define i_hash // hash func i_keyraw*: REQUIRED IF i_keyraw is non-pod type -#define i_eq // equality comparison two i_keyraw*: REQUIRED IF i_keyraw is a - // non-integral type. Three-way i_cmp may alternatively be specified. -#define i_keydrop // destroy key func - defaults to empty destruct -#define i_keyclone // REQUIRED IF i_keydrop defined -#define i_keyraw // convertion "raw" type - defaults to i_key -#define i_keyfrom // convertion func i_keyraw => i_key -#define i_keyto // convertion func i_key* => i_keyraw - -#define i_valdrop // destroy value func - defaults to empty destruct -#define i_valclone // REQUIRED IF i_valdrop defined -#define i_valraw // convertion "raw" type - defaults to i_val -#define i_valfrom // convertion func i_valraw => i_val -#define i_valto // convertion func i_val* => i_valraw - -#define i_tag // alternative typename: cmap_{i_tag}. i_tag defaults to i_val -#define i_expandby // default 1. If 2, table expand 2x (else 1.5x) +#define i_key // key type: REQUIRED. +#define i_val // mapped value type: REQUIRED. +#define i_type // container type name (default: cmap_{i_key}) +#define i_hash // hash func i_keyraw*: REQUIRED IF i_keyraw is non-pod type +#define i_eq // equality comparison two i_keyraw*: REQUIRED IF i_keyraw is a + // non-integral type. Three-way i_cmp may alternatively be specified. +#define i_keydrop // destroy key func - defaults to empty destruct +#define i_keyclone // REQUIRED IF i_keydrop defined +#define i_keyraw // convertion "raw" type - defaults to i_key +#define i_keyfrom // convertion func i_keyraw => i_key +#define i_keyto // convertion func i_key* => i_keyraw + +#define i_valdrop // destroy value func - defaults to empty destruct +#define i_valclone // REQUIRED IF i_valdrop defined +#define i_valraw // convertion "raw" type - defaults to i_val +#define i_valfrom // convertion func i_valraw => i_val +#define i_valto // convertion func i_val* => i_valraw + +#define i_tag // alternative typename: cmap_{i_tag}. i_tag defaults to i_val #include ``` `X` should be replaced by the value of `i_tag` in all of the following documentation. diff --git a/docs/cpque_api.md b/docs/cpque_api.md index 5b63dfd1..4cde927b 100644 --- a/docs/cpque_api.md +++ b/docs/cpque_api.md @@ -8,17 +8,17 @@ See the c++ class [std::priority_queue](https://en.cppreference.com/w/cpp/contai ## Header file and declaration ```c -#define i_type // define type name of the container (default cpque_{i_key}) -#define i_key // value: REQUIRED -#define i_less // compare two i_key* : REQUIRED IF i_key/i_keyraw is a non-integral type -#define i_keydrop // destroy value func - defaults to empty destruct -#define i_keyclone // REQUIRED IF i_keydrop defined +#define i_key // element type: REQUIRED. Note: i_val* may be specified instead of i_key*. +#define i_type // cpque container type name +#define i_less // compare two i_key* : REQUIRED IF i_key/i_keyraw is a non-integral type +#define i_keydrop // destroy value func - defaults to empty destruct +#define i_keyclone // REQUIRED IF i_keydrop defined -#define i_keyraw // convertion type -#define i_keyfrom // convertion func i_keyraw => i_key -#define i_keyto // convertion func i_key* => i_keyraw. +#define i_keyraw // convertion type +#define i_keyfrom // convertion func i_keyraw => i_key +#define i_keyto // convertion func i_key* => i_keyraw. -#define i_tag // alternative typename: cpque_{i_tag}. i_tag defaults to i_key +#define i_tag // alternative typename: cpque_{i_tag}. i_tag defaults to i_key #include ``` `X` should be replaced by the value of `i_tag` in all of the following documentation. diff --git a/docs/cqueue_api.md b/docs/cqueue_api.md index b324e5fc..1834baf9 100644 --- a/docs/cqueue_api.md +++ b/docs/cqueue_api.md @@ -7,16 +7,16 @@ See the c++ class [std::queue](https://en.cppreference.com/w/cpp/container/queue ## Header file and declaration ```c -#define i_type // container type name (default: cqueue_{i_key}) -#define i_key // value: REQUIRED -#define i_keydrop // destroy value func - defaults to empty destruct -#define i_keyclone // REQUIRED IF i_keydrop defined +#define i_key // element type: REQUIRED. Note: i_val* may be specified instead of i_key*. +#define i_type // cqueue container type name +#define i_keydrop // destroy value func - defaults to empty destruct +#define i_keyclone // REQUIRED IF i_keydrop defined -#define i_keyraw // convertion "raw" type - defaults to i_key -#define i_keyfrom // convertion func i_keyraw => i_key -#define i_keyto // convertion func i_key* => i_keyraw +#define i_keyraw // convertion "raw" type - defaults to i_key +#define i_keyfrom // convertion func i_keyraw => i_key +#define i_keyto // convertion func i_key* => i_keyraw -#define i_tag // alternative typename: cqueue_{i_tag}. i_tag defaults to i_key +#define i_tag // alternative typename: cqueue_{i_tag}. i_tag defaults to i_key #include ``` `X` should be replaced by the value of `i_tag` in all of the following documentation. diff --git a/docs/cset_api.md b/docs/cset_api.md index e894ad4f..928d63a8 100644 --- a/docs/cset_api.md +++ b/docs/cset_api.md @@ -7,19 +7,19 @@ A **cset** is an associative container that contains a set of unique objects of ## Header file and declaration ```c -#define i_type // container type name (default: cset_{i_key}) -#define i_key // hash key: REQUIRED. -#define i_hash // hash func: REQUIRED IF i_keyraw is a non-pod type. -#define i_eq // equality comparison two i_keyraw*: !i_cmp is used if not defined. -#define i_keydrop // destroy key func - defaults to empty destruct -#define i_keyclone // REQUIRED IF i_keydrop defined - -#define i_keyraw // convertion "raw" type - defaults to i_key -#define i_keyfrom // convertion func i_keyraw => i_key - defaults to plain copy -#define i_keyto // convertion func i_key* => i_keyraw - defaults to plain copy - -#define i_tag // alternative typename: cmap_{i_tag}. i_tag defaults to i_key -#define i_expandby // default 1. If 2, table expand 2x (else 1.5x) +#define i_key // element type: REQUIRED. Note: i_val* may be specified instead of i_key*. +#define i_type // container type name +#define i_hash // hash func i_keyraw*: REQUIRED IF i_keyraw is non-pod type +#define i_eq // equality comparison two i_keyraw*: REQUIRED IF i_keyraw is a + // non-integral type. Three-way i_cmp may alternatively be specified. +#define i_keydrop // destroy key func: defaults to empty destruct +#define i_keyclone // clone func: REQUIRED IF i_keydrop defined + +#define i_keyraw // convertion "raw" type - defaults to i_key +#define i_keyfrom // convertion func i_keyraw => i_key - defaults to plain copy +#define i_keyto // convertion func i_key* => i_keyraw - defaults to plain copy + +#define i_tag // alternative typename: cmap_{i_tag}. i_tag defaults to i_key #include ``` `X` should be replaced by the value of `i_tag` in all of the following documentation. diff --git a/docs/csmap_api.md b/docs/csmap_api.md index 099d7dfc..afaf49f3 100644 --- a/docs/csmap_api.md +++ b/docs/csmap_api.md @@ -15,24 +15,24 @@ See the c++ class [std::map](https://en.cppreference.com/w/cpp/container/map) fo ## Header file and declaration ```c -#define i_type // container type name (default: cmap_{i_key}) -#define i_key // key: REQUIRED -#define i_val // value: REQUIRED -#define i_cmp // three-way compare two i_keyraw* : REQUIRED IF i_keyraw is a non-integral type - -#define i_keydrop // destroy key func - defaults to empty destruct -#define i_keyclone // REQUIRED IF i_valdrop defined -#define i_keyraw // convertion "raw" type - defaults to i_key -#define i_keyfrom // convertion func i_keyraw => i_key -#define i_keyto // convertion func i_key* => i_keyraw - -#define i_valdrop // destroy value func - defaults to empty destruct -#define i_valclone // REQUIRED IF i_valdrop defined -#define i_valraw // convertion "raw" type - defaults to i_val -#define i_valfrom // convertion func i_valraw => i_val -#define i_valto // convertion func i_val* => i_valraw - -#define i_tag // alternative typename: csmap_{i_tag}. i_tag defaults to i_val +#define i_key // key type: REQUIRED. +#define i_val // mapped value type: REQUIRED. +#define i_type // container type name (default: cmap_{i_key}) +#define i_cmp // three-way compare two i_keyraw* : REQUIRED IF i_keyraw is a non-integral type + +#define i_keydrop // destroy key func - defaults to empty destruct +#define i_keyclone // REQUIRED IF i_valdrop defined +#define i_keyraw // convertion "raw" type - defaults to i_key +#define i_keyfrom // convertion func i_keyraw => i_key +#define i_keyto // convertion func i_key* => i_keyraw + +#define i_valdrop // destroy value func - defaults to empty destruct +#define i_valclone // REQUIRED IF i_valdrop defined +#define i_valraw // convertion "raw" type - defaults to i_val +#define i_valfrom // convertion func i_valraw => i_val +#define i_valto // convertion func i_val* => i_valraw + +#define i_tag // alternative typename: csmap_{i_tag}. i_tag defaults to i_val #include ``` `X` should be replaced by the value of `i_tag` in all of the following documentation. diff --git a/docs/csset_api.md b/docs/csset_api.md index aef3af3c..21e38f61 100644 --- a/docs/csset_api.md +++ b/docs/csset_api.md @@ -8,17 +8,17 @@ See the c++ class [std::set](https://en.cppreference.com/w/cpp/container/set) fo ## Header file and declaration ```c -#define i_type // full typename of the container -#define i_key // key: REQUIRED -#define i_cmp // three-way compare two i_keyraw* : REQUIRED IF i_keyraw is a non-integral type -#define i_keydrop // destroy key func - defaults to empty destruct -#define i_keyclone // REQUIRED IF i_keydrop defined +#define i_key // element type: REQUIRED. Note: i_val* may be specified instead of i_key*. +#define i_type // container type name +#define i_cmp // three-way compare two i_keyraw* : REQUIRED IF i_keyraw is a non-integral type +#define i_keydrop // destroy key func - defaults to empty destruct +#define i_keyclone // REQUIRED IF i_keydrop defined -#define i_keyraw // convertion "raw" type - defaults to i_key -#define i_keyfrom // convertion func i_keyraw => i_key - defaults to plain copy -#define i_keyto // convertion func i_key* => i_keyraw - defaults to plain copy +#define i_keyraw // convertion "raw" type - defaults to i_key +#define i_keyfrom // convertion func i_keyraw => i_key - defaults to plain copy +#define i_keyto // convertion func i_key* => i_keyraw - defaults to plain copy -#define i_tag // alternative typename: csset_{i_tag}. i_tag defaults to i_key +#define i_tag // alternative typename: csset_{i_tag}. i_tag defaults to i_key #include ``` `X` should be replaced by the value of `i_tag` in all of the following documentation. diff --git a/docs/cstack_api.md b/docs/cstack_api.md index e799b152..fb629392 100644 --- a/docs/cstack_api.md +++ b/docs/cstack_api.md @@ -8,16 +8,16 @@ See the c++ class [std::stack](https://en.cppreference.com/w/cpp/container/stack ## Header file and declaration ```c -#define i_type // full typename of the container -#define i_key // value: REQUIRED -#define i_keydrop // destroy value func - defaults to empty destruct -#define i_keyclone // REQUIRED IF i_keydrop defined +#define i_key // element type: REQUIRED. Note: i_val* may be specified instead of i_key*. +#define i_type // container type name +#define i_keydrop // destroy value func - defaults to empty destruct +#define i_keyclone // REQUIRED IF i_keydrop defined -#define i_keyraw // convertion "raw" type - defaults to i_key -#define i_keyfrom // convertion func i_keyraw => i_key -#define i_keyto // convertion func i_key* => i_keyraw +#define i_keyraw // convertion "raw" type - defaults to i_key +#define i_keyfrom // convertion func i_keyraw => i_key +#define i_keyto // convertion func i_key* => i_keyraw -#define i_tag // alternative typename: cstack_{i_tag}. i_tag defaults to i_key +#define i_tag // alternative typename: cstack_{i_tag}. i_tag defaults to i_key #include ``` `X` should be replaced by the value of `i_tag` in all of the following documentation. diff --git a/docs/cvec_api.md b/docs/cvec_api.md index d38ef23f..9cba74b5 100644 --- a/docs/cvec_api.md +++ b/docs/cvec_api.md @@ -12,17 +12,18 @@ See the c++ class [std::vector](https://en.cppreference.com/w/cpp/container/vect ## Header file and declaration ```c -#define i_type // full typename of the container -#define i_key // value: REQUIRED -#define i_cmp // three-way compare two i_keyraw* : REQUIRED IF i_keyraw is a non-integral type -#define i_keydrop // destroy value func - defaults to empty destruct -#define i_keyclone // REQUIRED IF i_keydrop defined - -#define i_keyraw // convertion "raw" type - defaults to i_key -#define i_keyfrom // convertion func i_keyraw => i_key -#define i_keyto // convertion func i_key* => i_keyraw - -#define i_tag // alternative typename: cvec_{i_tag}. i_tag defaults to i_key +#define i_type // container type name +#define i_key // element type: REQUIRED. Note: i_val* may be specified instead of i_key*. +#define i_cmp // three-way compare two i_keyraw* +#define i_cmp_native // define instead of i_cmp only when i_key is an integral/native-type. +#define i_keydrop // destroy value func - defaults to empty destruct +#define i_keyclone // REQUIRED IF i_keydrop defined + +#define i_keyraw // convertion "raw" type - defaults to i_key +#define i_keyfrom // convertion func i_keyraw => i_key +#define i_keyto // convertion func i_key* => i_keyraw + +#define i_tag // alternative typename: cvec_{i_tag}. i_tag defaults to i_key #include ``` `X` should be replaced by the value of `i_tag` in all of the following documentation. diff --git a/include/stc/algo/coroutine.h b/include/stc/algo/coroutine.h index 3a5382f3..e4c0915c 100644 --- a/include/stc/algo/coroutine.h +++ b/include/stc/algo/coroutine.h @@ -178,17 +178,22 @@ typedef struct { intptr_t count; } cco_sem; #ifdef _WIN32 #ifdef __cplusplus - #define _c_LINKC extern "C" __declspec(dllimport) + #define _c_LINKC extern "C" __declspec(dllimport) #else - #define _c_LINKC __declspec(dllimport) + #define _c_LINKC __declspec(dllimport) + #endif + #if _WIN32_WINNT < _WIN32_WINNT_WIN8 || defined __TINYC__ + #define _c_getsystime GetSystemTimeAsFileTime + #else + #define _c_getsystime GetSystemTimePreciseAsFileTime #endif struct _FILETIME; - _c_LINKC void GetSystemTimePreciseAsFileTime(struct _FILETIME*); + _c_LINKC void _c_getsystime(struct _FILETIME*); _c_LINKC void Sleep(unsigned long); static inline double cco_time(void) { /* seconds since epoch */ unsigned long long quad; /* 64-bit value representing 1/10th usecs since Jan 1 1601, 00:00 UTC */ - GetSystemTimePreciseAsFileTime((struct _FILETIME*)&quad); + _c_getsystime((struct _FILETIME*)&quad); return (double)(quad - 116444736000000000ULL)*1e-7; /* time diff Jan 1 1601-Jan 1 1970 in 1/10th usecs */ } diff --git a/include/stc/algo/filter.h b/include/stc/algo/filter.h index 4a227927..1a62c3e1 100644 --- a/include/stc/algo/filter.h +++ b/include/stc/algo/filter.h @@ -85,6 +85,21 @@ int main(void) if (it.ref == _endref) it.ref = NULL; \ } while (0) +#define c_all_of(boolptr, it, C, cnt, pred) do { \ + C##_iter it; \ + c_find_if_4(it, C, cnt, !(pred)); \ + *(boolptr) = it.ref == NULL; \ +} while (0) +#define c_any_of(boolptr, it, C, cnt, pred) do { \ + C##_iter it; \ + c_find_if_4(it, C, cnt, pred); \ + *(boolptr) = it.ref != NULL; \ +} while (0) +#define c_none_of(boolptr, it, C, cnt, pred) do { \ + C##_iter it; \ + c_find_if_4(it, C, cnt, pred); \ + *(boolptr) = it.ref == NULL; \ +} while (0) // Use with: clist, cmap, cset, csmap, csset: #define c_erase_if(it, C, cnt, pred) do { \ @@ -95,7 +110,6 @@ int main(void) } \ } while (0) - // Use with: cstack, cvec, cdeq, cqueue: #define c_eraseremove_if(it, C, cnt, pred) do { \ C* _cnt = &cnt; \ diff --git a/include/stc/priv/template.h b/include/stc/priv/template.h index 30ed5732..ccdce718 100644 --- a/include/stc/priv/template.h +++ b/include/stc/priv/template.h @@ -103,7 +103,7 @@ #define i_no_emplace #endif #if c_option(c_native_cmp) - #define i_native_cmp + #define i_cmp_native #endif #if c_option(c_no_clone) || defined _i_carc #define i_no_clone @@ -203,10 +203,10 @@ #endif #ifndef i_no_cmp - #if defined i_cmp || defined i_less || defined i_native_cmp + #if defined i_cmp || defined i_less || defined i_cmp_native #define _i_has_cmp #endif - #if defined i_eq || defined i_native_cmp + #if defined i_eq || defined i_cmp_native #define _i_has_eq #endif @@ -228,7 +228,7 @@ #endif #endif -#if !defined i_hash && (!(defined _i_cbox || defined _i_carc) || defined i_native_cmp) +#if !defined i_hash && (!(defined _i_cbox || defined _i_carc) || defined i_cmp_native) #define i_hash c_default_hash #endif diff --git a/include/stc/priv/template2.h b/include/stc/priv/template2.h index def5d01e..351defde 100644 --- a/include/stc/priv/template2.h +++ b/include/stc/priv/template2.h @@ -67,7 +67,7 @@ #undef i_realloc #undef i_free -#undef i_native_cmp +#undef i_cmp_native #undef i_no_cmp #undef i_no_hash #undef i_no_clone diff --git a/misc/benchmarks/various/csort_bench.c b/misc/benchmarks/various/csort_bench.c index f6b7f1db..793a0503 100644 --- a/misc/benchmarks/various/csort_bench.c +++ b/misc/benchmarks/various/csort_bench.c @@ -48,7 +48,7 @@ int main(int argc, char *argv[]) { Ints a = Ints_with_capacity(size); for (i = 0; i < size; i++) - *Ints_push(&a, romutrio(s) & (1U << 30) - 1); + Ints_push(&a, romutrio(s) & (1U << 30) - 1); testsort(&a, size, "random"); for (i = 0; i < 20; i++) printf(" %d", (int)*Ints_at(&a, i)); diff --git a/misc/examples/arc_demo.c b/misc/examples/arc_demo.c index 87d64e67..929a48a1 100644 --- a/misc/examples/arc_demo.c +++ b/misc/examples/arc_demo.c @@ -11,7 +11,7 @@ void int_drop(int* x) { #define i_type Arc // set type name to be defined (instead of 'carc_int') #define i_key int #define i_keydrop int_drop // optional, just to display the elements destroyed -#define i_native_cmp // use int comparison (x < y, x == y). +#define i_cmp_native // use int comparison (x < y, x == y). #include // Arc #define i_keyboxed Arc // note: use i_keyboxed instead of i_key for carc/cbox elements diff --git a/misc/examples/arcvec_erase.c b/misc/examples/arcvec_erase.c index addef8b7..ba54c1c7 100644 --- a/misc/examples/arcvec_erase.c +++ b/misc/examples/arcvec_erase.c @@ -5,7 +5,7 @@ void show_drop(int* x) { printf("drop: %d\n", *x); } #define i_type Arc #define i_key int #define i_keydrop show_drop -#define i_native_cmp // enable sort/search for int type +#define i_cmp_native // enable sort/search for int type #include // Shared pointer to int #define i_type Vec diff --git a/misc/examples/demos.c b/misc/examples/demos.c index ecc89f2e..1a604d9f 100644 --- a/misc/examples/demos.c +++ b/misc/examples/demos.c @@ -74,7 +74,7 @@ void vectordemo2(void) #define i_key int #define i_tag ix -#define i_native_cmp +#define i_cmp_native #include void listdemo1(void) diff --git a/misc/examples/intrusive.c b/misc/examples/intrusive.c index 4fca654b..c22ed260 100644 --- a/misc/examples/intrusive.c +++ b/misc/examples/intrusive.c @@ -4,7 +4,7 @@ #define i_type List #define i_key int -#define i_native_cmp +#define i_cmp_native #include void printList(List list) { diff --git a/misc/examples/list.c b/misc/examples/list.c index fa33305a..ad8bebb8 100644 --- a/misc/examples/list.c +++ b/misc/examples/list.c @@ -5,7 +5,7 @@ #define i_type DList #define i_key double -#define i_native_cmp +#define i_cmp_native #include int main(void) { diff --git a/misc/examples/lower_bound.c b/misc/examples/lower_bound.c index e5d816e9..bea828f2 100644 --- a/misc/examples/lower_bound.c +++ b/misc/examples/lower_bound.c @@ -1,7 +1,7 @@ #include #define i_key int -#define i_native_cmp +#define i_cmp_native #include #define i_key int diff --git a/misc/examples/new_list.c b/misc/examples/new_list.c index 9676e7b4..2112bf1f 100644 --- a/misc/examples/new_list.c +++ b/misc/examples/new_list.c @@ -27,7 +27,7 @@ int point_cmp(const Point* a, const Point* b) { #include #define i_key float -#define i_native_cmp // use < and == operators for comparison +#define i_cmp_native // use < and == operators for comparison #include void MyStruct_drop(MyStruct* s); diff --git a/misc/examples/new_sptr.c b/misc/examples/new_sptr.c index 7fef5d1f..3c6fa16c 100644 --- a/misc/examples/new_sptr.c +++ b/misc/examples/new_sptr.c @@ -15,7 +15,7 @@ uint64_t Person_hash(const Person* p); #define i_type IPtr #define i_key int #define i_keydrop(x) printf("drop: %d\n", *x) -#define i_native_cmp +#define i_cmp_native #include #define i_type IPStack -- cgit v1.2.3 From be5651c9fc3d3ecd2d9d24e6e4763260ef86de41 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 10 Aug 2023 21:17:48 +0200 Subject: Update template.h - also renamed i_cmp_native => i_use_cmp --- README.md | 4 +- docs/carc_api.md | 2 +- docs/cbox_api.md | 2 +- docs/cdeq_api.md | 2 +- docs/clist_api.md | 2 +- docs/cvec_api.md | 4 +- include/stc/carc.h | 64 ++++++++++++--------------- include/stc/cbox.h | 65 ++++++++++++---------------- include/stc/ccommon.h | 2 +- include/stc/priv/template.h | 29 ++++++------- include/stc/priv/template2.h | 2 +- misc/examples/linkedlists/intrusive.c | 2 +- misc/examples/linkedlists/list.c | 2 +- misc/examples/linkedlists/new_list.c | 2 +- misc/examples/mixed/astar.c | 1 - misc/examples/mixed/complex.c | 1 - misc/examples/mixed/demos.c | 3 +- misc/examples/smartpointers/arc_containers.c | 4 +- misc/examples/smartpointers/arc_demo.c | 3 +- misc/examples/smartpointers/arcvec_erase.c | 3 +- misc/examples/smartpointers/box.c | 1 + misc/examples/smartpointers/box2.c | 1 - misc/examples/smartpointers/music_arc.c | 4 +- misc/examples/smartpointers/new_sptr.c | 3 +- misc/examples/smartpointers/person_arc.c | 3 +- misc/examples/sortedmaps/csmap_insert.c | 1 - misc/examples/sortedmaps/multimap.c | 1 + misc/examples/vectors/lower_bound.c | 2 +- 28 files changed, 99 insertions(+), 116 deletions(-) (limited to 'include/stc/priv/template2.h') diff --git a/README.md b/README.md index 69c51417..48ccdd6f 100644 --- a/README.md +++ b/README.md @@ -251,7 +251,7 @@ struct Point { float x, y; }; #include // cvec_pnt: vector of struct Point #define i_key int -#define i_cmp_native // enable sort/search. Use native `<` and `==` operators +#define i_use_cmp // enable sort/search. Use native `<` and `==` operators #include // clist_int: singly linked list #define i_key int @@ -658,7 +658,7 @@ STC is generally very memory efficient. Memory usage for the different container - Removed deprecated . Use `` with the new API. - Reverted names _unif and _norm back to `_uniform` and `_normal`. - Removed default comparison for **clist**, **cvec** and **cdeq**: - - Define `i_cmp_native` to enable comparison for built-in i_key types (<, ==). + - Define `i_use_cmp` to enable comparison for built-in i_key types (<, ==). - Use of `i_keyclass` still expects comparison functions to be defined. - Use of `i_keyboxed` compares stored pointers instead of pointed to values if comparison not defined. - Renamed input enum flags for ***cregex***-functions. diff --git a/docs/carc_api.md b/docs/carc_api.md index fb79019a..3e394378 100644 --- a/docs/carc_api.md +++ b/docs/carc_api.md @@ -25,7 +25,7 @@ See similar c++ class [std::shared_ptr](https://en.cppreference.com/w/cpp/memory #define i_cmp // three-way compareison. REQUIRED IF i_key is a non-integral type // Note that containers of carcs will "inherit" i_cmp // when using carc in containers with i_valboxed MyArc - ie. the i_type. -#define i_cmp_native // define instead of i_cmp only when i_key is an integral/native-type. +#define i_use_cmp // define instead of i_cmp only when i_key is an integral/native-type. #define i_keydrop // destroy element func - defaults to empty destruct #define i_keyclone // REQUIRED if i_keydrop is defined, unless 'i_opt c_no_clone' is defined. diff --git a/docs/cbox_api.md b/docs/cbox_api.md index 0e6fca64..c683d9ef 100644 --- a/docs/cbox_api.md +++ b/docs/cbox_api.md @@ -19,7 +19,7 @@ See similar c++ class [std::unique_ptr](https://en.cppreference.com/w/cpp/memory #define i_cmp // three-way compareison. REQUIRED IF i_key is a non-integral type // Note that containers of carcs will "inherit" i_cmp // when using carc in containers with i_valboxed MyArc - ie. the i_type. -#define i_cmp_native // define instead of i_cmp only when i_key is an integral/native-type. +#define i_use_cmp // define instead of i_cmp only when i_key is an integral/native-type. #define i_keydrop // destroy element func - defaults to empty destruct #define i_keyclone // REQUIRED if i_keydrop is defined, unless 'i_opt c_no_clone' is defined. diff --git a/docs/cdeq_api.md b/docs/cdeq_api.md index c544f213..3ce58e78 100644 --- a/docs/cdeq_api.md +++ b/docs/cdeq_api.md @@ -13,7 +13,7 @@ See the c++ class [std::deque](https://en.cppreference.com/w/cpp/container/deque #define i_key // element type: REQUIRED. Note: i_val* may be specified instead of i_key*. #define i_type // cdeq container type name #define i_cmp // three-way compare of two i_keyraw*. -#define i_cmp_native // define instead of i_cmp only when i_key is an integral/native-type. +#define i_use_cmp // define instead of i_cmp only when i_key is an integral/native-type. #define i_keydrop // destroy value func - defaults to empty destruct #define i_keyclone // REQUIRED IF i_keydrop is defined diff --git a/docs/clist_api.md b/docs/clist_api.md index d8d614c2..a24d813b 100644 --- a/docs/clist_api.md +++ b/docs/clist_api.md @@ -25,7 +25,7 @@ See the c++ class [std::list](https://en.cppreference.com/w/cpp/container/list) #define i_key // element type: REQUIRED. Note: i_val* may be specified instead of i_key*. #define i_type // clist container type name #define i_cmp // three-way compare two i_keyraw* -#define i_cmp_native // define instead of i_cmp only when i_key is an integral/native-type. +#define i_use_cmp // define instead of i_cmp only when i_key is an integral/native-type. #define i_keydrop // destroy value func - defaults to empty destruct #define i_keyclone // REQUIRED IF i_keydrop defined diff --git a/docs/cvec_api.md b/docs/cvec_api.md index 3f827df6..8997ed51 100644 --- a/docs/cvec_api.md +++ b/docs/cvec_api.md @@ -15,7 +15,7 @@ See the c++ class [std::vector](https://en.cppreference.com/w/cpp/container/vect #define i_type // container type name #define i_key // element type: REQUIRED. Note: i_val* may be specified instead of i_key*. #define i_cmp // three-way compare two i_keyraw* -#define i_cmp_native // define instead of i_cmp only when i_key is an integral/native-type. +#define i_use_cmp // define instead of i_cmp only when i_key is an integral/native-type. #define i_keydrop // destroy value func - defaults to empty destruct #define i_keyclone // REQUIRED IF i_keydrop defined @@ -224,4 +224,4 @@ int main(void) { c_drop(UVec, &vec, &vec2); // cleanup } -``` \ No newline at end of file +``` diff --git a/include/stc/carc.h b/include/stc/carc.h index 9ba2ddd1..e1dfe14e 100644 --- a/include/stc/carc.h +++ b/include/stc/carc.h @@ -176,50 +176,40 @@ STC_INLINE void _cx_MEMB(_assign)(_cx_Self* self, _cx_Self ptr) { *self = ptr; } -#if defined _i_has_cmp +#if defined i_use_cmp STC_INLINE int _cx_MEMB(_raw_cmp)(const _cx_raw* rx, const _cx_raw* ry) { return i_cmp(rx, ry); } - STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { - _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); - return i_cmp((&rx), (&ry)); - } -#else - STC_INLINE int _cx_MEMB(_raw_cmp)(const _cx_raw* rx, const _cx_raw* ry) - { return c_default_cmp(&rx, &ry); } - - STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { - return c_default_cmp(&self->get, &other->get); - } -#endif -#if defined _i_has_eq || defined _i_has_cmp STC_INLINE bool _cx_MEMB(_raw_eq)(const _cx_raw* rx, const _cx_raw* ry) { return i_eq(rx, ry); } - - STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { - _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); - return i_eq((&rx), (&ry)); - } -#else - STC_INLINE bool _cx_MEMB(_raw_eq)(const _cx_raw* rx, const _cx_raw* ry) - { return rx == ry; } - - STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { - return self->get == other->get; - } -#endif -#if defined i_hash + #ifndef i_no_hash STC_INLINE uint64_t _cx_MEMB(_raw_hash)(const _cx_raw* rx) { return i_hash(rx); } - - STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) - { _cx_raw rx = i_keyto(self->get); return i_hash(&rx); } -#else - STC_INLINE uint64_t _cx_MEMB(_raw_hash)(const _cx_raw* rx) - { return c_default_hash(&rx); } - - STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) - { return c_default_hash(&self->get); } + #endif // i_no_hash + + #if defined i_ptr_cmp + STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { + return c_default_cmp(&self->get, &other->get); + } + STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { + return self->get == other->get; + } + STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) + { return c_default_hash(&self->get); } + #else + STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { + _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); + return i_cmp((&rx), (&ry)); + } + STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { + _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); + return i_eq((&rx), (&ry)); + } + #ifndef i_no_hash + STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) + { _cx_raw rx = i_keyto(self->get); return i_hash(&rx); } + #endif // i_no_hash + #endif // i_ptr_cmp #endif #undef _i_atomic_inc diff --git a/include/stc/cbox.h b/include/stc/cbox.h index 25d41b92..b799c24c 100644 --- a/include/stc/cbox.h +++ b/include/stc/cbox.h @@ -159,50 +159,41 @@ STC_INLINE void _cx_MEMB(_assign)(_cx_Self* self, _cx_Self* moved) { moved->get = NULL; } -#if defined _i_has_cmp +#if defined i_use_cmp STC_INLINE int _cx_MEMB(_raw_cmp)(const _cx_raw* rx, const _cx_raw* ry) { return i_cmp(rx, ry); } - STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { - _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); - return i_cmp((&rx), (&ry)); - } -#else - STC_INLINE int _cx_MEMB(_raw_cmp)(const _cx_raw* rx, const _cx_raw* ry) - { return c_default_cmp(&rx, &ry); } - - STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { - return c_default_cmp(&self->get, &other->get); - } -#endif -#if defined _i_has_eq || defined _i_has_cmp STC_INLINE bool _cx_MEMB(_raw_eq)(const _cx_raw* rx, const _cx_raw* ry) { return i_eq(rx, ry); } - - STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { - _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); - return i_eq((&rx), (&ry)); - } -#else - STC_INLINE bool _cx_MEMB(_raw_eq)(const _cx_raw* rx, const _cx_raw* ry) - { return rx == ry; } - - STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { - return self->get == other->get; - } -#endif -#if defined i_hash + #ifndef i_no_hash STC_INLINE uint64_t _cx_MEMB(_raw_hash)(const _cx_raw* rx) { return i_hash(rx); } - - STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) - { _cx_raw rx = i_keyto(self->get); return i_hash(&rx); } -#else - STC_INLINE uint64_t _cx_MEMB(_raw_hash)(const _cx_raw* rx) - { return c_default_hash(&rx); } - - STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) - { return c_default_hash(&self->get); } + #endif // i_no_hash + + #if defined i_ptr_cmp + STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { + return c_default_cmp(&self->get, &other->get); + } + STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { + return self->get == other->get; + } + STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) + { return c_default_hash(&self->get); } + #else + STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { + _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); + return i_cmp((&rx), (&ry)); + } + STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { + _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); + return i_eq((&rx), (&ry)); + } + #ifndef i_no_hash + STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) + { _cx_raw rx = i_keyto(self->get); return i_hash(&rx); } + #endif // i_no_hash + #endif // i_ptr_cmp #endif + #include "priv/template2.h" #undef _i_cbox diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index 2528b94f..b37ad1da 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -117,7 +117,7 @@ typedef long long _llong; #define c_no_clone (1<<2) #define c_no_emplace (1<<3) #define c_no_cmp (1<<4) -#define c_native_cmp (1<<5) +#define c_use_cmp (1<<5) #define c_no_hash (1<<6) /* Function macros and others */ diff --git a/include/stc/priv/template.h b/include/stc/priv/template.h index 49b4d8da..fae9093e 100644 --- a/include/stc/priv/template.h +++ b/include/stc/priv/template.h @@ -102,8 +102,8 @@ #if c_option(c_no_emplace) #define i_no_emplace #endif -#if c_option(c_native_cmp) - #define i_cmp_native +#if c_option(c_use_cmp) || defined _i_ismap || defined _i_isset || defined _i_ispque + #define i_use_cmp #endif #if c_option(c_no_clone) || defined _i_carc #define i_no_clone @@ -127,7 +127,7 @@ #elif defined i_keyboxed #define i_keyclass i_keyboxed #define i_rawclass c_PASTE(i_keyboxed, _raw) - #ifndef i_no_cmp + #if !defined i_no_cmp && defined i_use_cmp #define i_eq c_PASTE(i_keyboxed, _raw_eq) #endif #endif @@ -138,7 +138,7 @@ #define i_rawclass i_key #endif -#ifdef i_keyclass +#if defined i_keyclass #define i_key i_keyclass #ifndef i_keyclone #define i_keyclone c_PASTE(i_key, _clone) @@ -154,8 +154,8 @@ #endif #endif -#ifdef i_rawclass - #if !(defined i_cmp || defined i_no_cmp) +#if defined i_rawclass && defined i_use_cmp + #if !(defined i_cmp || defined i_less || defined i_no_cmp) #define i_cmp c_PASTE(i_keyraw, _cmp) #endif #if !(defined i_hash || defined i_no_hash || defined i_no_cmp) @@ -171,26 +171,29 @@ #endif #endif -#ifndef i_no_cmp - #if defined i_cmp || defined i_less || defined i_cmp_native +#if !defined i_no_cmp + #if defined i_cmp || defined i_less || defined i_use_cmp #define _i_has_cmp #endif - #if defined i_eq || defined i_cmp_native + #if defined i_eq || defined i_use_cmp #define _i_has_eq #endif #endif +#if !(defined i_hash || defined i_no_hash || defined i_no_cmp) + #define i_hash c_default_hash +#endif #if !defined i_key #error "No i_key or i_val defined" #elif defined i_keyraw ^ defined i_keyto #error "Both i_keyraw/i_valraw and i_keyto/i_valto must be defined, if any" #elif !defined i_no_clone && (defined i_keyclone ^ defined i_keydrop) - #error "Both i_keyclone/i_valclone and i_keydrop/i_valdrop must be defined, if any" + #error "Both i_keyclone/i_valclone and i_keydrop/i_valdrop must be defined, if any (unless i_no_clone defined)." #elif defined i_from || defined i_drop #error "i_from / i_drop not supported. Define i_keyfrom/i_valfrom and/or i_keydrop/i_valdrop instead" #elif defined i_keyraw && defined _i_ishash && !(defined i_hash && (defined _i_has_cmp || defined i_eq)) #error "For cmap/cset, both i_hash and i_eq (or i_less or i_cmp) must be defined when i_keyraw is defined." -#elif defined i_keyraw && (defined _i_ismap || defined _i_isset || defined _i_ispque) && !defined _i_has_cmp +#elif defined i_keyraw && defined i_use_cmp && !defined _i_has_cmp #error "For csmap/csset/cpque, i_cmp or i_less must be defined when i_keyraw is defined." #endif @@ -234,10 +237,6 @@ #endif #endif -#if !defined i_hash && (!(defined _i_cbox || defined _i_carc) || defined i_cmp_native) - #define i_hash c_default_hash -#endif - #if defined _i_ismap // ---- process cmap/csmap value i_val, ... ---- #ifdef i_val_str diff --git a/include/stc/priv/template2.h b/include/stc/priv/template2.h index 351defde..1e0d4a2e 100644 --- a/include/stc/priv/template2.h +++ b/include/stc/priv/template2.h @@ -67,7 +67,7 @@ #undef i_realloc #undef i_free -#undef i_cmp_native +#undef i_use_cmp #undef i_no_cmp #undef i_no_hash #undef i_no_clone diff --git a/misc/examples/linkedlists/intrusive.c b/misc/examples/linkedlists/intrusive.c index c7402d09..edb072c7 100644 --- a/misc/examples/linkedlists/intrusive.c +++ b/misc/examples/linkedlists/intrusive.c @@ -4,7 +4,7 @@ #define i_type List #define i_key int -#define i_cmp_native +#define i_use_cmp #include void printList(List list) { diff --git a/misc/examples/linkedlists/list.c b/misc/examples/linkedlists/list.c index 518cc09b..e83dc6b2 100644 --- a/misc/examples/linkedlists/list.c +++ b/misc/examples/linkedlists/list.c @@ -5,7 +5,7 @@ #define i_type DList #define i_key double -#define i_cmp_native +#define i_use_cmp #include int main(void) { diff --git a/misc/examples/linkedlists/new_list.c b/misc/examples/linkedlists/new_list.c index 2112bf1f..7518929a 100644 --- a/misc/examples/linkedlists/new_list.c +++ b/misc/examples/linkedlists/new_list.c @@ -27,7 +27,7 @@ int point_cmp(const Point* a, const Point* b) { #include #define i_key float -#define i_cmp_native // use < and == operators for comparison +#define i_use_cmp // use < and == operators for comparison #include void MyStruct_drop(MyStruct* s); diff --git a/misc/examples/mixed/astar.c b/misc/examples/mixed/astar.c index 590b7952..d15a9ed7 100644 --- a/misc/examples/mixed/astar.c +++ b/misc/examples/mixed/astar.c @@ -61,7 +61,6 @@ point_key_cmp(const point* a, const point* b) #include #define i_key point -#define i_opt c_no_cmp #include #define i_key point diff --git a/misc/examples/mixed/complex.c b/misc/examples/mixed/complex.c index 4eb1574b..9fcbc417 100644 --- a/misc/examples/mixed/complex.c +++ b/misc/examples/mixed/complex.c @@ -14,7 +14,6 @@ #define i_type StackList #define i_keyclass FloatStack // "class" picks up _clone, _drop, _cmp -#define i_opt c_no_cmp // exclude FloatStack_cmp(): not defined #include #define i_type ListMap diff --git a/misc/examples/mixed/demos.c b/misc/examples/mixed/demos.c index 7f5091fd..43c9a7ae 100644 --- a/misc/examples/mixed/demos.c +++ b/misc/examples/mixed/demos.c @@ -53,6 +53,7 @@ void vectordemo1(void) } #define i_key_str +#define i_use_cmp #include void vectordemo2(void) @@ -74,7 +75,7 @@ void vectordemo2(void) #define i_key int #define i_tag ix -#define i_cmp_native +#define i_use_cmp #include void listdemo1(void) diff --git a/misc/examples/smartpointers/arc_containers.c b/misc/examples/smartpointers/arc_containers.c index 6209005d..c2bff56f 100644 --- a/misc/examples/smartpointers/arc_containers.c +++ b/misc/examples/smartpointers/arc_containers.c @@ -12,11 +12,11 @@ #define i_key Map #define i_keydrop(p) (printf("drop Arc:\n"), Map_drop(p)) // no need for atomic ref. count in single thread: -#define i_opt c_no_atomic +#define i_opt c_no_atomic|c_no_cmp #include #define i_type Stack -#define i_keyboxed Arc // define i_keyboxed for carc/cbox value (not i_key) +#define i_keyboxed Arc // use i_keyboxed for carc/cbox key #include #define i_type List diff --git a/misc/examples/smartpointers/arc_demo.c b/misc/examples/smartpointers/arc_demo.c index 929a48a1..a66d84b0 100644 --- a/misc/examples/smartpointers/arc_demo.c +++ b/misc/examples/smartpointers/arc_demo.c @@ -11,13 +11,14 @@ void int_drop(int* x) { #define i_type Arc // set type name to be defined (instead of 'carc_int') #define i_key int #define i_keydrop int_drop // optional, just to display the elements destroyed -#define i_cmp_native // use int comparison (x < y, x == y). +#define i_use_cmp // use int comparison (x < y, x == y). #include // Arc #define i_keyboxed Arc // note: use i_keyboxed instead of i_key for carc/cbox elements #include // csset_Arc (like: std::set>) #define i_keyboxed Arc // note: as above. +#define i_use_cmp #include // cvec_Arc (like: std::vector>) int main(void) diff --git a/misc/examples/smartpointers/arcvec_erase.c b/misc/examples/smartpointers/arcvec_erase.c index 9d757533..0526b6a0 100644 --- a/misc/examples/smartpointers/arcvec_erase.c +++ b/misc/examples/smartpointers/arcvec_erase.c @@ -5,11 +5,12 @@ void show_drop(int* x) { printf("drop: %d\n", *x); } #define i_type Arc #define i_key int #define i_keydrop show_drop -#define i_cmp_native // enable sort/search for int type +#define i_use_cmp // enable sort/search for int type #include // Shared pointer to int #define i_type Vec #define i_keyboxed Arc +#define i_use_cmp #include // Vec: cvec diff --git a/misc/examples/smartpointers/box.c b/misc/examples/smartpointers/box.c index 94d126c0..5c8018d4 100644 --- a/misc/examples/smartpointers/box.c +++ b/misc/examples/smartpointers/box.c @@ -30,6 +30,7 @@ void Person_drop(Person* p) { #define i_type PBox #define i_keyclass Person // "class" binds _cmp, _clone, _drop functions. +#define i_use_cmp #include #define i_type Persons diff --git a/misc/examples/smartpointers/box2.c b/misc/examples/smartpointers/box2.c index eaab1c47..9b782c74 100644 --- a/misc/examples/smartpointers/box2.c +++ b/misc/examples/smartpointers/box2.c @@ -22,7 +22,6 @@ typedef struct { // Box in box: #define i_type BoxBoxPoint #define i_keyboxed cbox_Point // NB: use i_keyboxed when value is a cbox or carc! -#define i_no_cmp #include // BoxBoxPoint Point origin(void) { diff --git a/misc/examples/smartpointers/music_arc.c b/misc/examples/smartpointers/music_arc.c index 13d368c3..e9ebbbfe 100644 --- a/misc/examples/smartpointers/music_arc.c +++ b/misc/examples/smartpointers/music_arc.c @@ -23,7 +23,7 @@ void Song_drop(Song* s) { // Define the shared pointer: #define i_type SongArc #define i_keyclass Song -#define i_no_hash // no hash fn for Song, fallback hash pointer to Song. +#define i_opt c_use_cmp|c_no_hash #include // ... and a vector of them @@ -64,4 +64,4 @@ void example3(void) int main(void) { example3(); -} +} \ No newline at end of file diff --git a/misc/examples/smartpointers/new_sptr.c b/misc/examples/smartpointers/new_sptr.c index 3c6fa16c..50e28ae2 100644 --- a/misc/examples/smartpointers/new_sptr.c +++ b/misc/examples/smartpointers/new_sptr.c @@ -10,12 +10,13 @@ uint64_t Person_hash(const Person* p); #define i_type PersonArc #define i_keyclass Person // "class" assume _clone, _drop, _cmp, _hash is defined. +#define i_use_cmp #include #define i_type IPtr #define i_key int #define i_keydrop(x) printf("drop: %d\n", *x) -#define i_cmp_native +#define i_use_cmp #include #define i_type IPStack diff --git a/misc/examples/smartpointers/person_arc.c b/misc/examples/smartpointers/person_arc.c index 38c883a7..11040cd2 100644 --- a/misc/examples/smartpointers/person_arc.c +++ b/misc/examples/smartpointers/person_arc.c @@ -31,11 +31,12 @@ void Person_drop(Person* p) { #define i_type PSPtr #define i_keyclass Person // ensure Person_drop -#define i_cmp Person_cmp // specify object cmp, instead of ptr cmp for arc. +#define i_use_cmp #include #define i_type Persons #define i_keyboxed PSPtr // binds PSPtr_cmp, PSPtr_drop... +#define i_use_cmp #include diff --git a/misc/examples/sortedmaps/csmap_insert.c b/misc/examples/sortedmaps/csmap_insert.c index c9f02891..04b8ddc6 100644 --- a/misc/examples/sortedmaps/csmap_insert.c +++ b/misc/examples/sortedmaps/csmap_insert.c @@ -13,7 +13,6 @@ #include #define i_key csmap_ii_raw -#define i_opt c_no_cmp #define i_tag ii #include diff --git a/misc/examples/sortedmaps/multimap.c b/misc/examples/sortedmaps/multimap.c index 1068a5dc..a4490f91 100644 --- a/misc/examples/sortedmaps/multimap.c +++ b/misc/examples/sortedmaps/multimap.c @@ -41,6 +41,7 @@ void OlympicLoc_drop(OlympicLoc* self); // Create a clist, can be sorted by year. #define i_keyclass OlympicLoc // binds _cmp, _clone and _drop. +#define i_use_cmp #define i_tag OL #include diff --git a/misc/examples/vectors/lower_bound.c b/misc/examples/vectors/lower_bound.c index bea828f2..09cf2008 100644 --- a/misc/examples/vectors/lower_bound.c +++ b/misc/examples/vectors/lower_bound.c @@ -1,7 +1,7 @@ #include #define i_key int -#define i_cmp_native +#define i_use_cmp #include #define i_key int -- cgit v1.2.3 From 4ba846d378481cb74f68456a3ad4d7cd77d92522 Mon Sep 17 00:00:00 2001 From: tylov Date: Fri, 11 Aug 2023 08:52:50 +0200 Subject: Updated carc, cbox and template.h - simplifications: removed i_no_cmp/c_no_cmp, --- README.md | 9 +++++-- include/stc/carc.h | 49 ++++++++++++++++----------------- include/stc/cbox.h | 50 +++++++++++++++++----------------- include/stc/priv/template.h | 64 ++++++++++++++++++-------------------------- include/stc/priv/template2.h | 1 - 5 files changed, 83 insertions(+), 90 deletions(-) (limited to 'include/stc/priv/template2.h') diff --git a/README.md b/README.md index 48ccdd6f..fbdbd9fc 100644 --- a/README.md +++ b/README.md @@ -194,8 +194,13 @@ int main(void) Floats_drop(&nums); } ``` -For user-defined struct elements, `i_cmp` compare function should be defined because the default `<` and `==` -only works for integral types. *Alternatively, `#define i_opt c_no_cmp` to disable sorting and searching*. Similarily, if an element destructor `i_keydrop` is defined, `i_keyclone` function is required. +Comparison/lookup functions are enabled by default for associative containers and priority queue (cmap, cset, csmap, csset, cpque). To enable it for the remaining containers, define `i_cmp` or `i_less` (and optionally `i_eq`) on the element type. If the element is an integral type, simply define `i_use_cmp` to use `<` and `==` operators for comparisons. + +Note that for `#define i_keyclass Type`, defining `i_use_cmp` means that *Type_cmp()* function is expected to exist (along with *Type_clone()* and *Type_drop()*). + +To summarize, `i_use_cmp` is only needed to enable comparison (sort/search) functions when defining cstack, cvec, cqueue, cdeq, carc, cbox. With built-in types, it enables the comparison operators, whereas for keyclass types, it binds comparison to its Type_cmp() function. + +If an element destructor `i_keydrop` is defined, `i_keyclone` function is required. *Alternatively `#define i_opt c_no_clone` to disable container cloning.* Let's make a vector of vectors, which can be cloned. All of its element vectors will be destroyed when destroying the Vec2D. diff --git a/include/stc/carc.h b/include/stc/carc.h index e1dfe14e..e987f453 100644 --- a/include/stc/carc.h +++ b/include/stc/carc.h @@ -180,37 +180,38 @@ STC_INLINE void _cx_MEMB(_assign)(_cx_Self* self, _cx_Self ptr) { STC_INLINE int _cx_MEMB(_raw_cmp)(const _cx_raw* rx, const _cx_raw* ry) { return i_cmp(rx, ry); } + STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { + _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); + return i_cmp((&rx), (&ry)); + } + STC_INLINE bool _cx_MEMB(_raw_eq)(const _cx_raw* rx, const _cx_raw* ry) { return i_eq(rx, ry); } + + STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { + _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); + return i_eq((&rx), (&ry)); + } + #ifndef i_no_hash STC_INLINE uint64_t _cx_MEMB(_raw_hash)(const _cx_raw* rx) { return i_hash(rx); } + + STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) + { _cx_raw rx = i_keyto(self->get); return i_hash(&rx); } #endif // i_no_hash - #if defined i_ptr_cmp - STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { - return c_default_cmp(&self->get, &other->get); - } - STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { - return self->get == other->get; - } - STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) - { return c_default_hash(&self->get); } - #else - STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { - _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); - return i_cmp((&rx), (&ry)); - } - STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { - _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); - return i_eq((&rx), (&ry)); - } - #ifndef i_no_hash - STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) - { _cx_raw rx = i_keyto(self->get); return i_hash(&rx); } - #endif // i_no_hash - #endif // i_ptr_cmp -#endif +#else + + STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { + return c_default_cmp(&self->get, &other->get); + } + STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { + return self->get == other->get; + } + STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) + { return c_default_hash(&self->get); } +#endif // i_use_cmp #undef _i_atomic_inc #undef _i_atomic_dec_and_test diff --git a/include/stc/cbox.h b/include/stc/cbox.h index b799c24c..37daa69e 100644 --- a/include/stc/cbox.h +++ b/include/stc/cbox.h @@ -44,7 +44,6 @@ void Person_drop(Person* p) { #define i_type PBox #define i_valclass Person // bind Person clone+drop fn's -#define i_no_cmp // no cmp/hash is defined #include int main(void) { @@ -163,37 +162,38 @@ STC_INLINE void _cx_MEMB(_assign)(_cx_Self* self, _cx_Self* moved) { STC_INLINE int _cx_MEMB(_raw_cmp)(const _cx_raw* rx, const _cx_raw* ry) { return i_cmp(rx, ry); } + STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { + _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); + return i_cmp((&rx), (&ry)); + } + STC_INLINE bool _cx_MEMB(_raw_eq)(const _cx_raw* rx, const _cx_raw* ry) { return i_eq(rx, ry); } + + STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { + _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); + return i_eq((&rx), (&ry)); + } + #ifndef i_no_hash STC_INLINE uint64_t _cx_MEMB(_raw_hash)(const _cx_raw* rx) { return i_hash(rx); } + + STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) + { _cx_raw rx = i_keyto(self->get); return i_hash(&rx); } #endif // i_no_hash - #if defined i_ptr_cmp - STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { - return c_default_cmp(&self->get, &other->get); - } - STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { - return self->get == other->get; - } - STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) - { return c_default_hash(&self->get); } - #else - STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { - _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); - return i_cmp((&rx), (&ry)); - } - STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { - _cx_raw rx = i_keyto(self->get), ry = i_keyto(other->get); - return i_eq((&rx), (&ry)); - } - #ifndef i_no_hash - STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) - { _cx_raw rx = i_keyto(self->get); return i_hash(&rx); } - #endif // i_no_hash - #endif // i_ptr_cmp -#endif +#else + + STC_INLINE int _cx_MEMB(_cmp)(const _cx_Self* self, const _cx_Self* other) { + return c_default_cmp(&self->get, &other->get); + } + STC_INLINE bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { + return self->get == other->get; + } + STC_INLINE uint64_t _cx_MEMB(_hash)(const _cx_Self* self) + { return c_default_hash(&self->get); } +#endif // i_use_cmp #include "priv/template2.h" #undef _i_cbox diff --git a/include/stc/priv/template.h b/include/stc/priv/template.h index fae9093e..3b8a5b39 100644 --- a/include/stc/priv/template.h +++ b/include/stc/priv/template.h @@ -93,9 +93,6 @@ #if c_option(c_is_forward) #define i_is_forward #endif -#if c_option(c_no_cmp) - #define i_no_cmp -#endif #if c_option(c_no_hash) #define i_no_hash #endif @@ -127,7 +124,7 @@ #elif defined i_keyboxed #define i_keyclass i_keyboxed #define i_rawclass c_PASTE(i_keyboxed, _raw) - #if !defined i_no_cmp && defined i_use_cmp + #if defined i_use_cmp #define i_eq c_PASTE(i_keyboxed, _raw_eq) #endif #endif @@ -152,34 +149,27 @@ #ifndef i_keydrop #define i_keydrop c_PASTE(i_key, _drop) #endif + #if !defined i_keyraw && (defined i_cmp || defined i_less || defined i_eq || defined i_hash) + #define i_use_cmp + #endif #endif #if defined i_rawclass && defined i_use_cmp - #if !(defined i_cmp || defined i_less || defined i_no_cmp) + #if !(defined i_cmp || defined i_less) #define i_cmp c_PASTE(i_keyraw, _cmp) #endif - #if !(defined i_hash || defined i_no_hash || defined i_no_cmp) + #if !(defined i_hash || defined i_no_hash) #define i_hash c_PASTE(i_keyraw, _hash) #endif #endif -#if !defined i_keyraw && !defined i_no_clone - #if !defined i_keyfrom && defined i_keyclone - #define i_keyfrom i_keyclone - #elif !defined i_keyclone && defined i_keyfrom - #define i_keyclone i_keyfrom - #endif +#if defined i_cmp || defined i_less || defined i_use_cmp + #define _i_has_cmp #endif - -#if !defined i_no_cmp - #if defined i_cmp || defined i_less || defined i_use_cmp - #define _i_has_cmp - #endif - #if defined i_eq || defined i_use_cmp - #define _i_has_eq - #endif +#if defined i_eq || defined i_use_cmp + #define _i_has_eq #endif -#if !(defined i_hash || defined i_no_hash || defined i_no_cmp) +#if !(defined i_hash || defined i_no_hash) #define i_hash c_default_hash #endif @@ -218,23 +208,21 @@ #define i_keydrop c_default_drop #endif -#ifndef i_no_cmp - // i_eq, i_less, i_cmp - #if !defined i_eq && (defined i_cmp || defined i_less) - #define i_eq(x, y) !(i_cmp(x, y)) - #elif !defined i_eq - #define i_eq(x, y) *x == *y - #endif - #if defined i_cmp && defined i_less - #error "Only one of i_cmp and i_less may be defined" - #elif defined i_cmp - #define i_less(x, y) (i_cmp(x, y)) < 0 - #elif !defined i_less - #define i_less(x, y) *x < *y - #endif - #ifndef i_cmp - #define i_cmp(x, y) (i_less(y, x)) - (i_less(x, y)) - #endif +// i_eq, i_less, i_cmp +#if !defined i_eq && (defined i_cmp || defined i_less) + #define i_eq(x, y) !(i_cmp(x, y)) +#elif !defined i_eq + #define i_eq(x, y) *x == *y +#endif +#if defined i_cmp && defined i_less + #error "Only one of i_cmp and i_less may be defined" +#elif defined i_cmp + #define i_less(x, y) (i_cmp(x, y)) < 0 +#elif !defined i_less + #define i_less(x, y) *x < *y +#endif +#ifndef i_cmp + #define i_cmp(x, y) (i_less(y, x)) - (i_less(x, y)) #endif #if defined _i_ismap // ---- process cmap/csmap value i_val, ... ---- diff --git a/include/stc/priv/template2.h b/include/stc/priv/template2.h index 1e0d4a2e..44254601 100644 --- a/include/stc/priv/template2.h +++ b/include/stc/priv/template2.h @@ -68,7 +68,6 @@ #undef i_free #undef i_use_cmp -#undef i_no_cmp #undef i_no_hash #undef i_no_clone #undef i_no_emplace -- cgit v1.2.3