diff options
| author | realtradam <[email protected]> | 2023-04-12 15:55:33 -0400 |
|---|---|---|
| committer | realtradam <[email protected]> | 2023-04-12 15:55:33 -0400 |
| commit | 0841165881871ee01b782129be681209aeed2423 (patch) | |
| tree | 8a76b61dcaab381b6b42305201ae8b6259f6b6c0 /include/stc | |
| parent | 554f3e8acf7855b5d6a90cc68cefb7445460b03c (diff) | |
| parent | 0516aa3ae823ed9a22b2c5f776948c8447c32c31 (diff) | |
| download | STC-modified-0841165881871ee01b782129be681209aeed2423.tar.gz STC-modified-0841165881871ee01b782129be681209aeed2423.zip | |
Merge branch 'master' into modified
Diffstat (limited to 'include/stc')
| -rw-r--r-- | include/stc/algo/coroutine.h | 25 | ||||
| -rw-r--r-- | include/stc/algo/crange.h | 6 | ||||
| -rw-r--r-- | include/stc/algo/csort.h | 6 | ||||
| -rw-r--r-- | include/stc/algo/filter.h | 95 | ||||
| -rw-r--r-- | include/stc/calgo.h | 8 | ||||
| -rw-r--r-- | include/stc/carc.h | 20 | ||||
| -rw-r--r-- | include/stc/cbits.h | 40 | ||||
| -rw-r--r-- | include/stc/cbox.h | 20 | ||||
| -rw-r--r-- | include/stc/ccommon.h | 102 | ||||
| -rw-r--r-- | include/stc/cdeq.h | 13 | ||||
| -rw-r--r-- | include/stc/clist.h | 112 | ||||
| -rw-r--r-- | include/stc/cmap.h | 98 | ||||
| -rw-r--r-- | include/stc/cpque.h | 14 | ||||
| -rw-r--r-- | include/stc/cqueue.h | 10 | ||||
| -rw-r--r-- | include/stc/crand.h | 174 | ||||
| -rw-r--r-- | include/stc/csmap.h | 112 | ||||
| -rw-r--r-- | include/stc/cspan.h | 23 | ||||
| -rw-r--r-- | include/stc/cstack.h | 4 | ||||
| -rw-r--r-- | include/stc/cvec.h | 15 | ||||
| -rw-r--r-- | include/stc/extend.h | 66 | ||||
| -rw-r--r-- | include/stc/forward.h | 2 | ||||
| -rw-r--r-- | include/stc/priv/altnames.h | 4 | ||||
| -rw-r--r-- | include/stc/priv/raii.h | 27 | ||||
| -rw-r--r-- | include/stc/priv/template.h | 76 | ||||
| -rw-r--r-- | include/stc/priv/template2.h | 78 |
25 files changed, 682 insertions, 468 deletions
diff --git a/include/stc/algo/coroutine.h b/include/stc/algo/coroutine.h index 59e4cfca..b0ecd6b7 100644 --- a/include/stc/algo/coroutine.h +++ b/include/stc/algo/coroutine.h @@ -59,20 +59,20 @@ int main(void) { enum { cco_state_final = -1, - cco_state_expired = -2, + cco_state_done = -2, }; -#define cco_alive(ctx) ((ctx)->cco_state > 0) +#define cco_suspended(ctx) ((ctx)->cco_state > 0) +#define cco_alive(ctx) ((ctx)->cco_state != cco_state_done) #define cco_begin(ctx) \ int *_state = &(ctx)->cco_state; \ switch (*_state) { \ - case cco_state_expired: \ case 0: #define cco_end(retval) \ - *_state = cco_state_expired; break; \ - default: goto _cco_final_; /* avoid unused-warning */ \ + *_state = cco_state_done; break; \ + case -99: goto _cco_final_; \ } \ return retval @@ -83,13 +83,16 @@ enum { case __LINE__:; \ } while (0) -#define cco_yield_3(corocall, ctx, retval) \ +#define cco_yield_2(corocall2, ctx2) \ + cco_yield_3(corocall2, ctx2, ) + +#define cco_yield_3(corocall2, ctx2, retval) \ do { \ *_state = __LINE__; \ do { \ - corocall; if (cco_alive(ctx)) return retval; \ + corocall2; if (cco_suspended(ctx2)) return retval; \ case __LINE__:; \ - } while ((ctx)->cco_state >= cco_state_final); \ + } while (cco_alive(ctx2)); \ } while (0) #define cco_final \ @@ -105,4 +108,10 @@ enum { if (*_state > 0) *_state = cco_state_final; \ } while (0) +#define cco_reset(ctx) \ + do { \ + int* _state = &(ctx)->cco_state; \ + if (*_state == cco_state_done) *_state = 0; \ + } while (0) + #endif diff --git a/include/stc/algo/crange.h b/include/stc/algo/crange.h index 4fc957b6..ca06c258 100644 --- a/include/stc/algo/crange.h +++ b/include/stc/algo/crange.h @@ -34,9 +34,9 @@ int main() // use a temporary crange object. int a = 100, b = INT32_MAX; - c_forfilter (i, crange, crange_obj(a, b, 8) - , i.index > 10 - && c_flt_take(i, 3)) + c_forfilter (i, crange, crange_obj(a, b, 8), + c_flt_skip(i, 10) && + c_flt_take(i, 3)) printf(" %lld", *i.ref); puts(""); } diff --git a/include/stc/algo/csort.h b/include/stc/algo/csort.h index c452064f..53fe9fcc 100644 --- a/include/stc/algo/csort.h +++ b/include/stc/algo/csort.h @@ -20,8 +20,8 @@ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ -#include <stc/ccommon.h> -#include <stc/priv/template.h> +#include "../ccommon.h" +#include "../priv/template.h" /* Generic Quicksort in C, performs as fast as c++ std::sort(). template params: @@ -86,4 +86,4 @@ static inline void c_PASTE(cqsort_, i_tag)(i_val arr[], intptr_t lo, intptr_t hi static inline void c_PASTE(csort_, i_tag)(i_val arr[], intptr_t n) { c_PASTE(cqsort_, i_tag)(arr, 0, n - 1); } -#include <stc/priv/template.h> +#include "../priv/template2.h" diff --git a/include/stc/algo/filter.h b/include/stc/algo/filter.h index 48a36d9b..e133577c 100644 --- a/include/stc/algo/filter.h +++ b/include/stc/algo/filter.h @@ -24,24 +24,24 @@ #include <stdio.h> #define i_val int #include <stc/cstack.h> -#include <stc/algo/filter.h> +#include <stc/calgo.h> int main() { - c_with (cstack_int stk = c_make(cstack_int, {1, 2, 3, 4, 5, 6, 7, 8, 9}), - cstack_int_drop(&stk)) - { - c_foreach (i, cstack_int, stk) - printf(" %d", *i.ref); - puts(""); - - c_forfilter (i, cstack_int, stk - , c_flt_skipwhile(i, *i.ref < 3) - && (*i.ref & 1) == 0 // even only - && c_flt_take(i, 2)) // break after 2 - printf(" %d", *i.ref); - puts(""); - } + cstack_int stk = c_make(cstack_int, {1, 2, 3, 4, 5, 6, 7, 8, 9}); + + c_foreach (i, cstack_int, stk) + printf(" %d", *i.ref); + puts(""); + + c_forfilter (i, cstack_int, stk, + c_flt_skipwhile(i, *i.ref < 3) && + (*i.ref & 1) == 0 && // even only + c_flt_take(i, 2)) // break after 2 + printf(" %d", *i.ref); + puts(""); + + cstack_int_drop(&stk); } */ #ifndef STC_FILTER_H_INCLUDED @@ -49,24 +49,71 @@ int main() #include <stc/ccommon.h> -#ifndef c_NFILTERS -#define c_NFILTERS 32 -#endif +// c_forfilter: -#define c_flt_take(i, n) _flt_take(&(i).b, n) -#define c_flt_skip(i, n) (c_flt_count(i) > (n)) +#define c_flt_skip(i, n) (c_flt_counter(i) > (n)) #define c_flt_skipwhile(i, pred) ((i).b.s2[(i).b.s2top++] |= !(pred)) +#define c_flt_take(i, n) _flt_take(&(i).b, n) #define c_flt_takewhile(i, pred) _flt_takewhile(&(i).b, pred) -#define c_flt_last(i) (i).b.s1[(i).b.s1top-1] -#define c_flt_count(i) ++(i).b.s1[(i).b.s1top++] +#define c_flt_counter(i) ++(i).b.s1[(i).b.s1top++] +#define c_flt_getcount(i) (i).b.s1[(i).b.s1top - 1] #define c_forfilter(i, C, cnt, filter) \ + c_forfilter_it(i, C, C##_begin(&cnt), filter) + +#define c_forfilter_it(i, C, start, filter) \ for (struct {struct _flt_base b; C##_iter it; C##_value *ref;} \ - i = {.it=C##_begin(&cnt), .ref=i.it.ref} ; !i.b.done & (i.ref != NULL) ; \ + i = {.it=start, .ref=i.it.ref} ; !i.b.done & (i.it.ref != NULL) ; \ C##_next(&i.it), i.ref = i.it.ref, i.b.s1top=0, i.b.s2top=0) \ if (!(filter)) ; else -// ----- + +// c_find_if, c_erase_if, c_eraseremove_if: + +#define c_find_if(...) c_MACRO_OVERLOAD(c_find_if, __VA_ARGS__) +#define c_find_if_4(it, C, cnt, pred) do { \ + intptr_t _index = 0; \ + for (it = C##_begin(&cnt); it.ref && !(pred); C##_next(&it)) \ + ++_index; \ +} while (0) + +#define c_find_if_5(it, C, start, end, pred) do { \ + intptr_t _index = 0; \ + const C##_value* _endref = (end).ref; \ + for (it = start; it.ref != _endref && !(pred); C##_next(&it)) \ + ++_index; \ + if (it.ref == _endref) it.ref = NULL; \ +} while (0) + + +// Use with: clist, cmap, cset, csmap, csset: +#define c_erase_if(it, C, cnt, pred) do { \ + C* _cnt = &cnt; \ + intptr_t _index = 0; \ + for (C##_iter it = C##_begin(_cnt); it.ref; ++_index) { \ + if (pred) it = C##_erase_at(_cnt, it); \ + else C##_next(&it); \ + } \ +} while (0) + + +// Use with: cstack, cvec, cdeq, cqueue: +#define c_eraseremove_if(it, C, cnt, pred) do { \ + C* _cnt = &cnt; \ + intptr_t _n = 0, _index = 0; \ + C##_iter it = C##_begin(_cnt), _i; \ + while (it.ref && !(pred)) \ + C##_next(&it), ++_index; \ + for (_i = it; it.ref; C##_next(&it), ++_index) \ + if (pred) C##_value_drop(it.ref), ++_n; \ + else *_i.ref = *it.ref, C##_next(&_i); \ + _cnt->_len -= _n; \ +} while (0) + +// ------------------------ private ------------------------- +#ifndef c_NFILTERS +#define c_NFILTERS 32 +#endif struct _flt_base { uint32_t s1[c_NFILTERS]; diff --git a/include/stc/calgo.h b/include/stc/calgo.h new file mode 100644 index 00000000..21e73faf --- /dev/null +++ b/include/stc/calgo.h @@ -0,0 +1,8 @@ +#ifndef STC_CALGO_INCLUDED +#define STC_CALGO_INCLUDED + +#include "algo/crange.h" +#include "algo/filter.h" +#include "algo/coroutine.h" + +#endif diff --git a/include/stc/carc.h b/include/stc/carc.h index 02bbaf52..8ef80b12 100644 --- a/include/stc/carc.h +++ b/include/stc/carc.h @@ -90,7 +90,7 @@ typedef i_keyraw _cx_raw; #define _i_atomic_inc(v) (void)(++*(v)) #define _i_atomic_dec_and_test(v) !(--*(v)) #endif -#if !c_option(c_is_forward) +#ifndef i_is_forward _cx_deftypes(_c_carc_types, _cx_self, i_key); #endif struct _cx_memb(_rep_) { catomic_long counter; i_key value; }; @@ -177,8 +177,8 @@ 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* x, const _cx_self* y) { - _cx_raw rx = i_keyto(x->get), ry = i_keyto(y->get); +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)); } #endif @@ -187,27 +187,27 @@ STC_INLINE int _cx_memb(_cmp)(const _cx_self* x, const _cx_self* y) { 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* x, const _cx_self* y) { - _cx_raw rx = i_keyto(x->get), ry = i_keyto(y->get); +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)); } #elif !defined i_no_cmp STC_INLINE bool _cx_memb(_raw_eq)(const _cx_raw* rx, const _cx_raw* ry) { return i_cmp(rx, ry) == 0; } -STC_INLINE bool _cx_memb(_eq)(const _cx_self* x, const _cx_self* y) - { return _cx_memb(_cmp)(x, y) == 0; } +STC_INLINE bool _cx_memb(_eq)(const _cx_self* self, const _cx_self* other) + { return _cx_memb(_cmp)(self, other) == 0; } #endif #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* x) - { _cx_raw rx = i_keyto(x->get); 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 #undef _i_eq #undef _i_atomic_inc #undef _i_atomic_dec_and_test -#include "priv/template.h" +#include "priv/template2.h" diff --git a/include/stc/cbits.h b/include/stc/cbits.h index fa0da665..826df847 100644 --- a/include/stc/cbits.h +++ b/include/stc/cbits.h @@ -27,26 +27,26 @@ Similar to boost::dynamic_bitset / std::bitset #include "cbits.h" int main() { - c_with (cbits bset = cbits_with_size(23, true), cbits_drop(&bset)) - { - cbits_reset(&bset, 9); - cbits_resize(&bset, 43, false); - - printf("%4zu: ", cbits_size(&bset)); - c_forrange (i, cbits_size(&bset)) - printf("%d", cbits_at(&bset, i)); - puts(""); - cbits_set(&bset, 28); - cbits_resize(&bset, 77, true); - cbits_resize(&bset, 93, false); - cbits_resize(&bset, 102, true); - cbits_set_value(&bset, 99, false); - - printf("%4zu: ", cbits_size(&bset)); - c_forrange (i, cbits_size(&bset)) - printf("%d", cbits_at(&bset, i)); - puts(""); - } + cbits bset = cbits_with_size(23, true); + cbits_reset(&bset, 9); + cbits_resize(&bset, 43, false); + + printf("%4zu: ", cbits_size(&bset)); + c_forrange (i, cbits_size(&bset)) + printf("%d", cbits_at(&bset, i)); + puts(""); + cbits_set(&bset, 28); + cbits_resize(&bset, 77, true); + cbits_resize(&bset, 93, false); + cbits_resize(&bset, 102, true); + cbits_set_value(&bset, 99, false); + + printf("%4zu: ", cbits_size(&bset)); + c_forrange (i, cbits_size(&bset)) + printf("%d", cbits_at(&bset, i)); + puts(""); + + cbits_drop(&bset); } */ #ifndef CBITS_H_INCLUDED diff --git a/include/stc/cbox.h b/include/stc/cbox.h index 641fcbfc..ca88fc66 100644 --- a/include/stc/cbox.h +++ b/include/stc/cbox.h @@ -76,7 +76,7 @@ int main() { #include "priv/template.h" typedef i_keyraw _cx_raw; -#if !c_option(c_is_forward) +#ifndef i_is_forward _cx_deftypes(_c_cbox_types, _cx_self, i_key); #endif @@ -163,8 +163,8 @@ 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* x, const _cx_self* y) { - _cx_raw rx = i_keyto(x->get), ry = i_keyto(y->get); +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)); } #endif @@ -173,25 +173,25 @@ STC_INLINE int _cx_memb(_cmp)(const _cx_self* x, const _cx_self* y) { 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* x, const _cx_self* y) { - _cx_raw rx = i_keyto(x->get), ry = i_keyto(y->get); +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)); } #elif !defined i_no_cmp STC_INLINE bool _cx_memb(_raw_eq)(const _cx_raw* rx, const _cx_raw* ry) { return i_cmp(rx, ry) == 0; } -STC_INLINE bool _cx_memb(_eq)(const _cx_self* x, const _cx_self* y) - { return _cx_memb(_cmp)(x, y) == 0; } +STC_INLINE bool _cx_memb(_eq)(const _cx_self* self, const _cx_self* other) + { return _cx_memb(_cmp)(self, other) == 0; } #endif #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* x) - { _cx_raw rx = i_keyto(x->get); 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 #undef _i_eq -#include "priv/template.h" +#include "priv/template2.h" diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index d163b4ab..d5508807 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -30,6 +30,7 @@ #include <string.h> #include <assert.h> #include "priv/altnames.h" +#include "priv/raii.h" #define c_NPOS INTPTR_MAX #define c_ZI PRIiPTR @@ -81,7 +82,8 @@ #define c_delete(T, ptr) do { T *_tp = ptr; T##_drop(_tp); free(_tp); } while (0) #define c_static_assert(b) ((int)(0*sizeof(int[(b) ? 1 : -1]))) -#define c_container_of(p, T, m) ((T*)((char*)(p) + 0*sizeof((p) == &((T*)0)->m) - offsetof(T, m))) +#define c_container_of(p, C, m) ((C*)((char*)(1 ? (p) : &((C*)0)->m) - offsetof(C, m))) +#define c_const_cast(T, p) ((T)(p) + 0*sizeof((T)0 == (p))) #define c_swap(T, xp, yp) do { T *_xp = xp, *_yp = yp, \ _tv = *_xp; *_xp = *_yp; *_yp = _tv; } while (0) #define c_sizeof (intptr_t)sizeof @@ -120,10 +122,13 @@ #define c_make(C, ...) \ C##_from_n((C##_raw[])__VA_ARGS__, c_sizeof((C##_raw[])__VA_ARGS__)/c_sizeof(C##_raw)) -#define c_arraylen(a) (intptr_t)(sizeof(a)/sizeof 0[a]) #define c_litstrlen(literal) (c_sizeof("" literal) - 1) +#define c_arraylen(a) (intptr_t)(sizeof(a)/sizeof 0[a]) +// Non-owning c-string typedef const char* crawstr; +#define crawstr_clone(s) (s) +#define crawstr_drop(p) ((void)p) #define crawstr_cmp(xp, yp) strcmp(*(xp), *(yp)) #define crawstr_hash(p) cstrhash(*(p)) @@ -132,24 +137,23 @@ typedef const char* crawstr; #define c_sv_2(str, n) (c_LITERAL(csview){str, n}) #define c_SV(sv) (int)(sv).size, (sv).str // print csview: use format "%.*s" -#define c_PAIR(ref) (ref)->first, (ref)->second #define c_ROTL(x, k) (x << (k) | x >> (8*sizeof(x) - (k))) STC_INLINE uint64_t cfasthash(const void* key, intptr_t len) { - const uint8_t *x = (const uint8_t*) key; - uint64_t u8, h = 1; intptr_t n = len >> 3; - uint32_t u4; + uint32_t u4; uint64_t u8; + switch (len) { + case 8: memcpy(&u8, key, 8); return u8*0xc6a4a7935bd1e99d; + case 4: memcpy(&u4, key, 4); return u4*0xc6a4a7935bd1e99d; + case 0: return 1; + } + const uint8_t *x = (const uint8_t*)key; + uint64_t h = *x, n = (uint64_t)len >> 3; + len &= 7; while (n--) { memcpy(&u8, x, 8), x += 8; - h += (c_ROTL(u8, 26) ^ u8)*0xc6a4a7935bd1e99d; + h += u8*0xc6a4a7935bd1e99d; } - switch (len &= 7) { - case 0: return h; - case 4: memcpy(&u4, x, 4); - return h + u4*0xc6a4a7935bd1e99d; - } - h += *x++; - while (--len) h = (h << 10) - h + *x++; + while (len--) h = (h << 10) - h - *x++; return c_ROTL(h, 26) ^ h; } @@ -178,10 +182,9 @@ STC_INLINE char* cstrnstrn(const char *str, const char *needle, for (C##_iter it = start, *_endref = (C##_iter*)(finish).ref \ ; it.ref != (C##_value*)_endref; C##_next(&it)) -#define c_forwhile(i, C, start, cond) \ - for (struct {C##_iter it; C##_value *ref; intptr_t index;} \ - i = {.it=start, .ref=i.it.ref}; i.it.ref && (cond) \ - ; C##_next(&i.it), i.ref = i.it.ref, ++i.index) +#define c_foreach_rv(it, C, cnt) \ + for (C##_iter it = {.ref=C##_end(&cnt).end - 1, .end=(cnt).data - 1} \ + ; it.ref != it.end; --it.ref) #define c_forpair(key, val, C, cnt) /* structured binding */ \ for (struct {C##_iter it; const C##_key* key; C##_mapped* val;} _ = {.it=C##_begin(&cnt)} \ @@ -196,10 +199,11 @@ STC_INLINE char* cstrnstrn(const char *str, const char *needle, #define c_forrange_4(i, start, stop, step) \ for (long long i=start, _inc=step, _end=(long long)(stop) - (_inc > 0) \ ; (_inc > 0) ^ (i > _end); i += _inc) + #ifndef __cplusplus #define c_forlist(it, T, ...) \ - for (struct {T* data; T* ref; int size, index;} \ - it = {.data=(T[])__VA_ARGS__, .ref=it.data, .size=(int)(sizeof((T[])__VA_ARGS__)/sizeof(T))} \ + for (struct {T* ref; int size, index;} \ + it = {.ref=(T[])__VA_ARGS__, .size=(int)(sizeof((T[])__VA_ARGS__)/sizeof(T))} \ ; it.index < it.size; ++it.ref, ++it.index) #else #include <initializer_list> @@ -208,63 +212,9 @@ STC_INLINE char* cstrnstrn(const char *str, const char *needle, it = {._il=__VA_ARGS__, .data=it._il.begin(), .ref=it.data, .size=it._il.size()} \ ; it.index < it.size; ++it.ref, ++it.index) #endif -#define c_with(...) c_MACRO_OVERLOAD(c_with, __VA_ARGS__) -#define c_with_2(declvar, drop) for (declvar, *_i, **_ip = &_i; _ip; _ip = 0, drop) -#define c_with_3(declvar, pred, drop) for (declvar, *_i, **_ip = &_i; _ip && (pred); _ip = 0, drop) -#define c_scope(...) c_MACRO_OVERLOAD(c_scope, __VA_ARGS__) -#define c_scope_2(init, drop) for (int _i = (init, 1); _i; _i = 0, drop) -#define c_scope_3(init, pred, drop) for (int _i = (init, 1); _i && (pred); _i = 0, drop) -#define c_defer(...) for (int _i = 1; _i; _i = 0, __VA_ARGS__) - -#define c_auto(...) c_MACRO_OVERLOAD(c_auto, __VA_ARGS__) -#define c_auto_2(C, a) \ - c_with_2(C a = C##_init(), C##_drop(&a)) -#define c_auto_3(C, a, b) \ - c_with_2(c_EXPAND(C a = C##_init(), b = C##_init()), \ - (C##_drop(&b), C##_drop(&a))) -#define c_auto_4(C, a, b, c) \ - c_with_2(c_EXPAND(C a = C##_init(), b = C##_init(), c = C##_init()), \ - (C##_drop(&c), C##_drop(&b), C##_drop(&a))) -#define c_auto_5(C, a, b, c, d) \ - 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))) - -/* Generic functions */ - -#define c_drop(C, ...) do { c_forlist (_i, C*, {__VA_ARGS__}) C##_drop(*_i.ref); } while(0) -#define c_find_if(...) c_MACRO_OVERLOAD(c_find_if, __VA_ARGS__) -#define c_find_if_4(it, C, cnt, pred) do { \ - intptr_t index = 0; \ - for (it = C##_begin(&cnt); it.ref && !(pred); C##_next(&it)) \ - ++index; \ -} while (0) -#define c_find_if_5(it, C, start, end, pred) do { \ - intptr_t index = 0; \ - const C##_value* _endref = (end).ref; \ - for (it = start; it.ref != _endref && !(pred); C##_next(&it)) \ - ++index; \ - if (it.ref == _endref) it.ref = NULL; \ -} while (0) - -// use with: clist, cmap, cset, csmap, csset, cstr: -#define c_erase_if(it, C, cnt, pred) do { \ - C* _cnt = &cnt; \ - for (C##_iter it = C##_begin(_cnt); it.ref;) { \ - if (pred) it = C##_erase_at(_cnt, it); \ - else C##_next(&it); \ - } \ -} while (0) -// use with: cstack, cvec, cdeq, cqueue: -#define c_eraseremove_if(it, C, cnt, pred) do { \ - C* _cnt = &cnt; \ - intptr_t _n = 0; \ - C##_iter _first = C##_begin(_cnt), it = _first; \ - for (; it.ref; C##_next(&it)) \ - if (pred) ++_n; \ - else C##_value_drop(_first.ref), *_first.ref = *it.ref, C##_next(&_first); \ - _cnt->_len -= _n; \ -} while (0) +#define c_drop(C, ...) \ + do { c_forlist (_i, C*, {__VA_ARGS__}) C##_drop(*_i.ref); } while(0) #endif // CCOMMON_H_INCLUDED diff --git a/include/stc/cdeq.h b/include/stc/cdeq.h index c4f84a1b..ff6e744f 100644 --- a/include/stc/cdeq.h +++ b/include/stc/cdeq.h @@ -36,7 +36,7 @@ #endif #include "priv/template.h" -#if !c_option(c_is_forward) +#ifndef i_is_forward _cx_deftypes(_c_cdeq_types, _cx_self, i_key); #endif typedef i_keyraw _cx_raw; @@ -196,11 +196,10 @@ _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* x, const _cx_self* y) { - if (x->_len != y->_len) return false; - _cx_iter i = _cx_memb(_begin)(x), j = _cx_memb(_begin)(y); - for (; i.ref; _cx_memb(_next)(&i), _cx_memb(_next)(&j)) { - const _cx_raw _rx = i_keyto(i.ref), _ry = i_keyto(j.ref); +_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; @@ -443,5 +442,5 @@ _cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y) { #endif // !c_no_cmp #endif // !_i_queue #endif // IMPLEMENTATION -#include "priv/template.h" #define CDEQ_H_INCLUDED +#include "priv/template2.h" diff --git a/include/stc/clist.h b/include/stc/clist.h index f8a21f40..f7fb4152 100644 --- a/include/stc/clist.h +++ b/include/stc/clist.h @@ -26,7 +26,7 @@ it also support both push_back() and push_front(), unlike std::forward_list: #include <stdio.h> - #include <stc/crandom.h> + #include <stc/crand.h> #define i_key int64_t #define i_tag ix @@ -38,12 +38,12 @@ { int n; for (int i = 0; i < 1000000; ++i) // one million - clist_ix_push_back(&list, crandom() >> 32); + clist_ix_push_back(&list, crand() >> 32); n = 0; c_foreach (i, clist_ix, list) if (++n % 10000 == 0) printf("%8d: %10zu\n", n, *i.ref); // Sort them... - clist_ix_sort(&list); // mergesort O(n*log n) + clist_ix_sort(&list); // qsort O(n*log n) n = 0; puts("sorted"); c_foreach (i, clist_ix, list) @@ -66,11 +66,6 @@ #define _clist_tonode(vp) c_container_of(vp, _cx_node, value) -_c_clist_types(clist_VOID, int); -_c_clist_complete_types(clist_VOID, dummy); -typedef int clist_VOID_comp(const clist_VOID_node*, const clist_VOID_node*); -extern clist_VOID_node* _clist_mergesort(clist_VOID_node*, clist_VOID_comp*); - #define _c_clist_insert_entry_after(ref, val) \ _cx_node *entry = (_cx_node *)i_malloc(c_sizeof *entry); entry->value = val; \ _c_clist_insert_after_node(ref, entry) @@ -87,7 +82,7 @@ extern clist_VOID_node* _clist_mergesort(clist_VOID_node*, clist_VOID_comp*); #endif #include "priv/template.h" -#if !c_option(c_is_forward) +#ifndef i_is_forward _cx_deftypes(_c_clist_types, _cx_self, i_key); #endif _cx_deftypes(_c_clist_complete_types, _cx_self, dummy); @@ -104,7 +99,10 @@ STC_API _cx_iter _cx_memb(_find_in)(_cx_iter it1, _cx_iter it2, _cx_raw v STC_API intptr_t _cx_memb(_remove)(_cx_self* self, _cx_raw val); #endif #ifndef i_no_cmp -STC_API int _cx_memb(_sort_cmp_)(const _cx_node* x, const _cx_node* y); +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) + { return _cx_memb(_sort_with)(self, _cx_memb(_sort_cmp_)); } #endif STC_API void _cx_memb(_reverse)(_cx_self* self); STC_API _cx_iter _cx_memb(_splice)(_cx_self* self, _cx_iter it, _cx_self* other); @@ -206,9 +204,8 @@ _cx_memb(_get_mut)(_cx_self* self, _cx_raw val) { return _cx_memb(_find_in)(_cx_memb(_begin)(self), _cx_memb(_end)(self), val).ref; } -STC_INLINE bool -_cx_memb(_eq)(const _cx_self* x, const _cx_self* y) { - _cx_iter i = _cx_memb(_begin)(x), j = _cx_memb(_begin)(y); +STC_INLINE bool _cx_memb(_eq)(const _cx_self* self, const _cx_self* other) { + _cx_iter i = _cx_memb(_begin)(self), j = _cx_memb(_begin)(other); for (; i.ref && j.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; @@ -216,68 +213,6 @@ _cx_memb(_eq)(const _cx_self* x, const _cx_self* y) { return !(i.ref || j.ref); } #endif -#ifndef i_no_cmp - -STC_INLINE void -_cx_memb(_sort)(_cx_self* self) { - if (self->last) - self->last = (_cx_node *)_clist_mergesort((clist_VOID_node *)self->last->next, - (clist_VOID_comp *)_cx_memb(_sort_cmp_)); -} -STC_INLINE void -_cx_memb(_sort_with)(_cx_self* self, int(*cmp)(const _cx_node*, const _cx_node*)) { - if (self->last) - self->last = (_cx_node *)_clist_mergesort((clist_VOID_node *)self->last->next, - (clist_VOID_comp *)cmp); -} -#endif - -#if defined(i_extern) -/* Implement non-templated extern functions */ -// Singly linked list Mergesort implementation by Simon Tatham. O(n*log n). -// https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html -clist_VOID_node * -_clist_mergesort(clist_VOID_node *list, clist_VOID_comp* cmp) { - clist_VOID_node *p, *q, *e, *tail, *oldhead; - int insize = 1, nmerges, psize, qsize, i; - - while (1) { - p = oldhead = list; - list = tail = NULL; - nmerges = 0; - - while (p) { - ++nmerges; - q = p, psize = 0; - for (i = 0; i < insize; ++i) { - ++psize; - q = (q->next == oldhead ? NULL : q->next); - if (!q) break; - } - qsize = insize; - - while (psize || (qsize && q)) { - if (psize && (!(qsize && q) || cmp(p, q) <= 0)) { - e = p, p = p->next, --psize; - if (p == oldhead) p = NULL; - } else { - e = q, q = q->next, --qsize; - if (q == oldhead) q = NULL; - } - if (tail) tail->next = e; else list = e; - tail = e; - } - p = q; - } - tail->next = list; - - if (nmerges <= 1) - return tail; - - insize *= 2; - } -} -#endif // i_extern // -------------------------- IMPLEMENTATION ------------------------- #if defined(i_implement) @@ -443,15 +378,30 @@ _cx_memb(_remove)(_cx_self* self, _cx_raw val) { return n; } #endif -#ifndef i_no_cmp -STC_DEF int -_cx_memb(_sort_cmp_)(const _cx_node* x, const _cx_node* y) { - const _cx_raw a = i_keyto((&x->value)); - const _cx_raw b = i_keyto((&y->value)); +#ifndef i_no_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)); } + +STC_DEF bool _cx_memb(_sort_with)(_cx_self* self, int(*cmp)(const _cx_value*, const _cx_value*)) { + size_t len = 0, cap = 0; + _cx_value *a = NULL, *p = NULL; + _cx_iter i; + for (i = _cx_memb(_begin)(self); i.ref; _cx_memb(_next)(&i)) { + if (len == cap) { + if ((p = (_cx_value *)i_realloc(a, (cap += cap/2 + 4)*sizeof *a))) a = p; + else { i_free(a); return false; } + } + a[len++] = *i.ref; + } + qsort(a, len, sizeof *a, (int(*)(const void*, const void*))cmp); + for (i = _cx_memb(_begin)(self); i.ref; _cx_memb(_next)(&i), ++p) + *i.ref = *p; + i_free(a); return true; +} #endif // !c_no_cmp #endif // i_implement #define CLIST_H_INCLUDED -#include "priv/template.h" +#include "priv/template2.h" diff --git a/include/stc/cmap.h b/include/stc/cmap.h index bc3b5546..14782b71 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -31,20 +31,20 @@ #include <stc/cmap.h> int main(void) { - c_with (cmap_ichar m = cmap_ichar_init(), cmap_ichar_drop(&m)) - { - cmap_ichar_emplace(&m, 5, 'a'); - cmap_ichar_emplace(&m, 8, 'b'); - cmap_ichar_emplace(&m, 12, 'c'); - - cmap_ichar_value* v = cmap_ichar_get(&m, 10); // NULL - char val = *cmap_ichar_at(&m, 5); // 'a' - cmap_ichar_emplace_or_assign(&m, 5, 'd'); // update - cmap_ichar_erase(&m, 8); - - c_foreach (i, cmap_ichar, m) - printf("map %d: %c\n", i.ref->first, i.ref->second); - } + cmap_ichar m = {0}; + cmap_ichar_emplace(&m, 5, 'a'); + cmap_ichar_emplace(&m, 8, 'b'); + cmap_ichar_emplace(&m, 12, 'c'); + + cmap_ichar_value* v = cmap_ichar_get(&m, 10); // NULL + char val = *cmap_ichar_at(&m, 5); // 'a' + cmap_ichar_emplace_or_assign(&m, 5, 'd'); // update + cmap_ichar_erase(&m, 8); + + c_foreach (i, cmap_ichar, m) + printf("map %d: %c\n", i.ref->first, i.ref->second); + + cmap_ichar_drop(&m); } */ #include "ccommon.h" @@ -82,13 +82,7 @@ typedef struct { int64_t idx; uint8_t hx; } chash_bucket_t; #define _i_size i_ssize #endif #include "priv/template.h" -#ifndef i_hash_functor - #define i_hash_functor(self, x) i_hash(x) -#endif -#ifndef i_eq_functor - #define i_eq_functor(self, x, y) i_eq(x, y) -#endif -#if !c_option(c_is_forward) +#ifndef i_is_forward _cx_deftypes(_c_chash_types, _cx_self, i_key, i_val, i_ssize, _i_MAP_ONLY, _i_SET_ONLY); #endif @@ -97,8 +91,8 @@ _i_MAP_ONLY( struct _cx_value { _cx_mapped second; }; ) -typedef i_keyraw _cx_rawkey; -typedef i_valraw _cx_memb(_rawmapped); +typedef i_keyraw _cx_keyraw; +typedef i_valraw _cx_memb(_rmapped); typedef _i_SET_ONLY( i_keyraw ) _i_MAP_ONLY( struct { i_keyraw first; i_valraw second; } ) @@ -111,8 +105,8 @@ STC_API _cx_self _cx_memb(_clone)(_cx_self map); STC_API void _cx_memb(_drop)(_cx_self* self); STC_API void _cx_memb(_clear)(_cx_self* self); STC_API bool _cx_memb(_reserve)(_cx_self* self, _i_size capacity); -STC_API chash_bucket_t _cx_memb(_bucket_)(const _cx_self* self, const _cx_rawkey* rkeyptr); -STC_API _cx_result _cx_memb(_insert_entry_)(_cx_self* self, _cx_rawkey rkey); +STC_API chash_bucket_t _cx_memb(_bucket_)(const _cx_self* self, const _cx_keyraw* rkeyptr); +STC_API _cx_result _cx_memb(_insert_entry_)(_cx_self* self, _cx_keyraw rkey); STC_API void _cx_memb(_erase_entry)(_cx_self* self, _cx_value* val); STC_INLINE _cx_self _cx_memb(_init)(void) { _cx_self map = {0}; return map; } @@ -123,23 +117,23 @@ STC_INLINE _i_size _cx_memb(_size)(const _cx_self* map) { return map->size; STC_INLINE _i_size _cx_memb(_bucket_count)(_cx_self* map) { return map->bucket_count; } STC_INLINE _i_size _cx_memb(_capacity)(const _cx_self* map) { return (_i_size)((float)map->bucket_count * (i_max_load_factor)); } -STC_INLINE bool _cx_memb(_contains)(const _cx_self* self, _cx_rawkey rkey) +STC_INLINE bool _cx_memb(_contains)(const _cx_self* self, _cx_keyraw rkey) { return self->size && self->_hashx[_cx_memb(_bucket_)(self, &rkey).idx]; } #ifndef _i_isset STC_API _cx_result _cx_memb(_insert_or_assign)(_cx_self* self, i_key key, i_val mapped); #if !defined i_no_emplace - STC_API _cx_result _cx_memb(_emplace_or_assign)(_cx_self* self, _cx_rawkey rkey, i_valraw rmapped); + STC_API _cx_result _cx_memb(_emplace_or_assign)(_cx_self* self, _cx_keyraw rkey, i_valraw rmapped); #endif STC_INLINE const _cx_mapped* - _cx_memb(_at)(const _cx_self* self, _cx_rawkey rkey) { + _cx_memb(_at)(const _cx_self* self, _cx_keyraw rkey) { chash_bucket_t b = _cx_memb(_bucket_)(self, &rkey); assert(self->_hashx[b.idx]); return &self->table[b.idx].second; } STC_INLINE _cx_mapped* - _cx_memb(_at_mut)(_cx_self* self, _cx_rawkey rkey) + _cx_memb(_at_mut)(_cx_self* self, _cx_keyraw rkey) { return (_cx_mapped*)_cx_memb(_at)(self, rkey); } #endif // !_i_isset @@ -161,7 +155,7 @@ _cx_memb(_value_clone)(_cx_value _val) { #if !defined i_no_emplace STC_INLINE _cx_result -_cx_memb(_emplace)(_cx_self* self, _cx_rawkey rkey _i_MAP_ONLY(, i_valraw rmapped)) { +_cx_memb(_emplace)(_cx_self* self, _cx_keyraw rkey _i_MAP_ONLY(, i_valraw rmapped)) { _cx_result _res = _cx_memb(_insert_entry_)(self, rkey); if (_res.inserted) { *_i_keyref(_res.ref) = i_keyfrom(rkey); @@ -224,7 +218,7 @@ STC_INLINE _cx_iter _cx_memb(_begin)(const _cx_self* self) { if (it._hx) while (*it._hx == 0) ++it.ref, ++it._hx; - if (it.ref == it.end) it.ref = NULL; + if (it.ref == it._end) it.ref = NULL; return it; } @@ -235,7 +229,7 @@ _cx_memb(_end)(const _cx_self* self) STC_INLINE void _cx_memb(_next)(_cx_iter* it) { while ((++it->ref, *++it->_hx == 0)) ; - if (it->ref == it->end) it->ref = NULL; + if (it->ref == it->_end) it->ref = NULL; } STC_INLINE _cx_iter @@ -245,7 +239,7 @@ _cx_memb(_advance)(_cx_iter it, size_t n) { } STC_INLINE _cx_iter -_cx_memb(_find)(const _cx_self* self, _cx_rawkey rkey) { +_cx_memb(_find)(const _cx_self* self, _cx_keyraw rkey) { int64_t idx; if (self->size && self->_hashx[idx = _cx_memb(_bucket_)(self, &rkey).idx]) return c_LITERAL(_cx_iter){self->table + idx, @@ -255,7 +249,7 @@ _cx_memb(_find)(const _cx_self* self, _cx_rawkey rkey) { } STC_INLINE const _cx_value* -_cx_memb(_get)(const _cx_self* self, _cx_rawkey rkey) { +_cx_memb(_get)(const _cx_self* self, _cx_keyraw rkey) { int64_t idx; if (self->size && self->_hashx[idx = _cx_memb(_bucket_)(self, &rkey).idx]) return self->table + idx; @@ -263,11 +257,11 @@ _cx_memb(_get)(const _cx_self* self, _cx_rawkey rkey) { } STC_INLINE _cx_value* -_cx_memb(_get_mut)(_cx_self* self, _cx_rawkey rkey) +_cx_memb(_get_mut)(_cx_self* self, _cx_keyraw rkey) { return (_cx_value*)_cx_memb(_get)(self, rkey); } STC_INLINE int -_cx_memb(_erase)(_cx_self* self, _cx_rawkey rkey) { +_cx_memb(_erase)(_cx_self* self, _cx_keyraw rkey) { if (self->size == 0) return 0; chash_bucket_t b = _cx_memb(_bucket_)(self, &rkey); @@ -283,11 +277,11 @@ _cx_memb(_erase_at)(_cx_self* self, _cx_iter it) { } STC_INLINE bool -_cx_memb(_eq)(const _cx_self* m1, const _cx_self* m2) { - if (_cx_memb(_size)(m1) != _cx_memb(_size)(m2)) return false; - for (_cx_iter i = _cx_memb(_begin)(m1); i.ref; _cx_memb(_next)(&i)) { - const _cx_rawkey _raw = i_keyto(_i_keyref(i.ref)); - if (!_cx_memb(_contains)(m2, _raw)) return false; +_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); i.ref; _cx_memb(_next)(&i)) { + const _cx_keyraw _raw = i_keyto(_i_keyref(i.ref)); + if (!_cx_memb(_contains)(other, _raw)) return false; } return true; } @@ -355,7 +349,7 @@ STC_DEF void _cx_memb(_clear)(_cx_self* self) { #if !defined i_no_emplace STC_DEF _cx_result - _cx_memb(_emplace_or_assign)(_cx_self* self, _cx_rawkey rkey, i_valraw rmapped) { + _cx_memb(_emplace_or_assign)(_cx_self* self, _cx_keyraw rkey, i_valraw rmapped) { _cx_result _res = _cx_memb(_insert_entry_)(self, rkey); if (_res.inserted) _res.ref->first = i_keyfrom(rkey); @@ -370,15 +364,15 @@ STC_DEF void _cx_memb(_clear)(_cx_self* self) { #endif // !_i_isset STC_DEF chash_bucket_t -_cx_memb(_bucket_)(const _cx_self* self, const _cx_rawkey* rkeyptr) { - const uint64_t _hash = i_hash_functor(self, rkeyptr); +_cx_memb(_bucket_)(const _cx_self* self, const _cx_keyraw* rkeyptr) { + const uint64_t _hash = i_hash(rkeyptr); int64_t _cap = self->bucket_count; chash_bucket_t b = {c_PASTE(fastrange_,_i_expandby)(_hash, (uint64_t)_cap), (uint8_t)(_hash | 0x80)}; const uint8_t* _hx = self->_hashx; while (_hx[b.idx]) { if (_hx[b.idx] == b.hx) { - const _cx_rawkey _raw = i_keyto(_i_keyref(self->table + b.idx)); - if (i_eq_functor(self, (&_raw), rkeyptr)) + const _cx_keyraw _raw = i_keyto(_i_keyref(self->table + b.idx)); + if (i_eq((&_raw), rkeyptr)) break; } if (++b.idx == _cap) @@ -388,7 +382,7 @@ _cx_memb(_bucket_)(const _cx_self* self, const _cx_rawkey* rkeyptr) { } STC_DEF _cx_result -_cx_memb(_insert_entry_)(_cx_self* self, _cx_rawkey rkey) { +_cx_memb(_insert_entry_)(_cx_self* self, _cx_keyraw rkey) { _cx_result res = {NULL}; if (self->size + 2 > (i_ssize)((float)self->bucket_count * (i_max_load_factor))) if (!_cx_memb(_reserve)(self, self->size*3/2)) @@ -444,7 +438,7 @@ _cx_memb(_reserve)(_cx_self* self, const _i_size newcap) { const _cx_value* e = self->table; const uint8_t* h = self->_hashx; for (i_ssize i = 0; i < _oldbuckets; ++i, ++e) if (*h++) { - _cx_rawkey r = i_keyto(_i_keyref(e)); + _cx_keyraw r = i_keyto(_i_keyref(e)); chash_bucket_t b = _cx_memb(_bucket_)(&m, &r); m.table[b.idx] = *e; m._hashx[b.idx] = b.hx; @@ -468,8 +462,8 @@ _cx_memb(_erase_entry)(_cx_self* self, _cx_value* _val) { j = 0; if (! _hashx[j]) break; - const _cx_rawkey _raw = i_keyto(_i_keyref(_slot + j)); - k = (i_ssize)c_PASTE(fastrange_,_i_expandby)(i_hash_functor(self, (&_raw)), (uint64_t)_cap); + const _cx_keyraw _raw = i_keyto(_i_keyref(_slot + j)); + k = (i_ssize)c_PASTE(fastrange_,_i_expandby)(i_hash((&_raw)), (uint64_t)_cap); if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ _slot[i] = _slot[j], _hashx[i] = _hashx[j], i = j; } @@ -479,8 +473,6 @@ _cx_memb(_erase_entry)(_cx_self* self, _cx_value* _val) { #endif // i_implement #undef i_max_load_factor -#undef i_hash_functor -#undef i_eq_functor #undef _i_size #undef _i_isset #undef _i_ismap @@ -489,4 +481,4 @@ _cx_memb(_erase_entry)(_cx_self* self, _cx_value* _val) { #undef _i_MAP_ONLY #undef _i_SET_ONLY #define CMAP_H_INCLUDED -#include "priv/template.h" +#include "priv/template2.h" diff --git a/include/stc/cpque.h b/include/stc/cpque.h index 4955f2e0..b95b5020 100644 --- a/include/stc/cpque.h +++ b/include/stc/cpque.h @@ -32,10 +32,7 @@ #endif #include "priv/template.h" -#ifndef i_less_functor - #define i_less_functor(self, x, y) i_less(x, y) -#endif -#if !c_option(c_is_forward) +#ifndef i_is_forward _cx_deftypes(_c_cpque_types, _cx_self, i_key); #endif typedef i_keyraw _cx_raw; @@ -120,8 +117,8 @@ STC_DEF void _cx_memb(_sift_down_)(_cx_self* self, const intptr_t idx, const intptr_t n) { _cx_value t, *arr = self->data - 1; for (intptr_t r = idx, c = idx*2; c <= n; c *= 2) { - c += i_less_functor(self, (&arr[c]), (&arr[c + (c < n)])); - if (!(i_less_functor(self, (&arr[r]), (&arr[c])))) return; + c += i_less((&arr[c]), (&arr[c + (c < n)])); + if (!(i_less((&arr[r]), (&arr[c])))) return; t = arr[r], arr[r] = arr[c], arr[r = c] = t; } } @@ -156,12 +153,11 @@ _cx_memb(_push)(_cx_self* self, _cx_value value) { _cx_memb(_reserve)(self, self->_len*3/2 + 4); _cx_value *arr = self->data - 1; /* base 1 */ intptr_t c = ++self->_len; - for (; c > 1 && (i_less_functor(self, (&arr[c/2]), (&value))); c /= 2) + for (; c > 1 && (i_less((&arr[c/2]), (&value))); c /= 2) arr[c] = arr[c/2]; arr[c] = value; } #endif #define CPQUE_H_INCLUDED -#undef i_less_functor -#include "priv/template.h" +#include "priv/template2.h" diff --git a/include/stc/cqueue.h b/include/stc/cqueue.h index 67909f8e..1934305a 100644 --- a/include/stc/cqueue.h +++ b/include/stc/cqueue.h @@ -22,7 +22,7 @@ */ // STC queue /* -#include <stc/crandom.h> +#include <stc/crand.h> #include <stdio.h> #define i_key int @@ -30,19 +30,19 @@ int main() { int n = 10000000; - stc64_t rng = stc64_new(1234); - stc64_uniform_t dist = stc64_uniform_new(0, n); + 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; i<n; ++i) - cqueue_int_push(&Q, stc64_uniform(&rng, &dist)); + cqueue_int_push(&Q, crand_unif(&rng, &dist)); // Push or pop on the queue ten million times printf("before: size, capacity: %d, %d\n", n, cqueue_int_size(&Q), cqueue_int_capacity(&Q)); for (int i=n; i>0; --i) { - int r = stc64_uniform(&rng, &dist); + int r = crand_unif(&rng, &dist); if (r & 1) ++n, cqueue_int_push(&Q, r); else diff --git a/include/stc/crand.h b/include/stc/crand.h new file mode 100644 index 00000000..a1b7250d --- /dev/null +++ b/include/stc/crand.h @@ -0,0 +1,174 @@ +/* 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. + */ +#include "ccommon.h" + +#ifndef CRAND_H_INCLUDED +#define CRAND_H_INCLUDED +/* +// crand: Pseudo-random number generator +#include "stc/crand.h" + +int main() { + uint64_t seed = 123456789; + crand_t rng = crand_init(seed); + crand_unif_t dist1 = crand_unif_init(1, 6); + crand_norm_t dist3 = crand_norm_init(1.0, 10.0); + + uint64_t i = crand_u64(&rng); + int64_t iu = crand_unif(&rng, &dist1); + double xn = crand_norm(&rng, &dist3); +} +*/ +#include <string.h> +#include <math.h> + +typedef struct crand { uint64_t state[5]; } crand_t; +typedef struct crand_unif { int64_t lower; uint64_t range, threshold; } crand_unif_t; +typedef struct crand_norm { double mean, stddev, next; int has_next; } crand_norm_t; + +/* PRNG crand_t. + * Very fast PRNG suited for parallel usage with Weyl-sequence parameter. + * 320-bit state, 256 bit is mutable. + * Noticable faster than xoshiro and pcg, slighly slower than wyrand64 and + * Romu, but these have restricted capacity for larger parallel jobs or unknown minimum periods. + * crand_t supports 2^63 unique threads with a minimum 2^64 period lengths each. + * Passes all statistical tests, e.g PractRand and correlation tests, i.e. interleaved + * streams with one-bit diff state. Even the 16-bit version (LR=6, RS=5, LS=3) passes + * PractRand to multiple TB input. + */ + +/* Global crand_t PRNGs */ +STC_API void csrand(uint64_t seed); +STC_API uint64_t crand(void); +STC_API double crandf(void); + +/* Init crand_t prng with a seed */ +STC_API crand_t crand_init(uint64_t seed); + +/* Unbiased bounded uniform distribution. range [low, high] */ +STC_API crand_unif_t crand_unif_init(int64_t low, int64_t high); +STC_API int64_t crand_unif(crand_t* rng, crand_unif_t* dist); + +/* Normal/gaussian distribution. */ +STC_INLINE crand_norm_t crand_norm_init(double mean, double stddev) + { crand_norm_t r = {mean, stddev, 0.0, 0}; return r; } + +STC_API double crand_norm(crand_t* rng, crand_norm_t* dist); + +/* Main crand_t prng */ +STC_INLINE uint64_t crand_u64(crand_t* rng) { + uint64_t *s = rng->state; + const uint64_t result = (s[0] ^ (s[3] += s[4])) + s[1]; + s[0] = s[1] ^ (s[1] >> 11); + s[1] = s[2] + (s[2] << 3); + s[2] = ((s[2] << 24) | (s[2] >> (64 - 24))) + result; + return result; +} + +/* Float64 random number in range [0.0, 1.0). */ +STC_INLINE double crand_f64(crand_t* rng) { + union {uint64_t i; double f;} u = {0x3FF0000000000000U | (crand_u64(rng) >> 12)}; + return u.f - 1.0; +} + +/* -------------------------- IMPLEMENTATION ------------------------- */ +#if defined(i_implement) + +/* Global random() */ +static crand_t crand_global = {{ + 0x26aa069ea2fb1a4d, 0x70c72c95cd592d04, + 0x504f333d3aa0b359, 0x9e3779b97f4a7c15, + 0x6a09e667a754166b +}}; + +STC_DEF void csrand(uint64_t seed) + { crand_global = crand_init(seed); } + +STC_DEF uint64_t crand(void) + { return crand_u64(&crand_global); } + +STC_DEF double crandf(void) + { return crand_f64(&crand_global); } + +STC_DEF crand_t crand_init(uint64_t seed) { + crand_t rng; uint64_t* s = rng.state; + s[0] = seed + 0x9e3779b97f4a7c15; + s[1] = (s[0] ^ (s[0] >> 30))*0xbf58476d1ce4e5b9; + s[2] = (s[1] ^ (s[1] >> 27))*0x94d049bb133111eb; + s[3] = (s[2] ^ (s[2] >> 31)); + s[4] = ((seed + 0x6aa069ea2fb1a4d) << 1) | 1; + return rng; +} + +/* Init unbiased uniform uint RNG with bounds [low, high] */ +STC_DEF crand_unif_t crand_unif_init(int64_t low, int64_t high) { + crand_unif_t dist = {low, (uint64_t) (high - low + 1)}; + dist.threshold = (uint64_t)(0 - dist.range) % dist.range; + return dist; +} + +#if defined(__SIZEOF_INT128__) + #define c_umul128(a, b, lo, hi) \ + do { __uint128_t _z = (__uint128_t)(a)*(b); \ + *(lo) = (uint64_t)_z, *(hi) = (uint64_t)(_z >> 64U); } while(0) +#elif defined(_MSC_VER) && defined(_WIN64) + #include <intrin.h> + #define c_umul128(a, b, lo, hi) ((void)(*(lo) = _umul128(a, b, hi))) +#elif defined(__x86_64__) + #define c_umul128(a, b, lo, hi) \ + asm("mulq %3" : "=a"(*(lo)), "=d"(*(hi)) : "a"(a), "rm"(b)) +#endif + +/* Int64 uniform distributed RNG, range [low, high]. */ +STC_DEF int64_t crand_unif(crand_t* rng, crand_unif_t* d) { + uint64_t lo, hi; +#ifdef c_umul128 + do { c_umul128(crand_u64(rng), d->range, &lo, &hi); } while (lo < d->threshold); +#else + do { lo = crand_u64(rng); hi = lo % d->range; } while (lo - hi > -d->range); +#endif + return d->lower + (int64_t)hi; +} + +/* Normal distribution PRNG. Marsaglia polar method */ +STC_DEF double crand_norm(crand_t* rng, crand_norm_t* dist) { + double u1, u2, s, m; + if (dist->has_next++ & 1) + return dist->next*dist->stddev + dist->mean; + do { + u1 = 2.0 * crand_f64(rng) - 1.0; + u2 = 2.0 * crand_f64(rng) - 1.0; + s = u1*u1 + u2*u2; + } while (s >= 1.0 || s == 0.0); + m = sqrt(-2.0 * log(s) / s); + dist->next = u2*m; + return (u1*m)*dist->stddev + dist->mean; +} + +#endif +#endif +#undef i_opt +#undef i_static +#undef i_header +#undef i_implement +#undef i_extern diff --git a/include/stc/csmap.h b/include/stc/csmap.h index 0f72ca2d..ebfe8d44 100644 --- a/include/stc/csmap.h +++ b/include/stc/csmap.h @@ -32,25 +32,22 @@ #include <stc/csmap.h> int main(void) { - c_with (csmap_sx m = csmap_sx_init(), csmap_sx_drop(&m)) - { - csmap_sx_emplace(&m, "Testing one", 1.234); - csmap_sx_emplace(&m, "Testing two", 12.34); - csmap_sx_emplace(&m, "Testing three", 123.4); - - csmap_sx_value *v = csmap_sx_get(&m, "Testing five"); // NULL - double num = *csmap_sx_at(&m, "Testing one"); - csmap_sx_emplace_or_assign(&m, "Testing three", 1000.0); // update - csmap_sx_erase(&m, "Testing two"); - - c_foreach (i, csmap_sx, m) - printf("map %s: %g\n", cstr_str(&i.ref->first), i.ref->second); - } + csmap_sx m = {0}; + csmap_sx_emplace(&m, "Testing one", 1.234); + csmap_sx_emplace(&m, "Testing two", 12.34); + csmap_sx_emplace(&m, "Testing three", 123.4); + + csmap_sx_value *v = csmap_sx_get(&m, "Testing five"); // NULL + double num = *csmap_sx_at(&m, "Testing one"); + csmap_sx_emplace_or_assign(&m, "Testing three", 1000.0); // update + csmap_sx_erase(&m, "Testing two"); + + c_foreach (i, csmap_sx, m) + printf("map %s: %g\n", cstr_str(&i.ref->first), i.ref->second); + + csmap_sx_drop(&m); } */ -#ifdef STC_CSMAP_V1 -#include "alt/csmap.h" -#else #include "ccommon.h" #ifndef CSMAP_H_INCLUDED @@ -80,10 +77,7 @@ int main(void) { #define _i_size i_ssize #endif #include "priv/template.h" -#ifndef i_cmp_functor - #define i_cmp_functor(self, x, y) i_cmp(x, y) -#endif -#if !c_option(c_is_forward) +#ifndef i_is_forward _cx_deftypes(_c_aatree_types, _cx_self, i_key, i_val, i_ssize, _i_MAP_ONLY, _i_SET_ONLY); #endif @@ -97,14 +91,14 @@ struct _cx_node { _cx_value value; }; -typedef i_keyraw _cx_rawkey; -typedef i_valraw _cx_memb(_rawmapped); +typedef i_keyraw _cx_keyraw; +typedef i_valraw _cx_memb(_rmapped); typedef _i_SET_ONLY( i_keyraw ) _i_MAP_ONLY( struct { i_keyraw first; i_valraw second; } ) _cx_raw; #if !defined i_no_emplace -STC_API _cx_result _cx_memb(_emplace)(_cx_self* self, _cx_rawkey rkey _i_MAP_ONLY(, i_valraw rmapped)); +STC_API _cx_result _cx_memb(_emplace)(_cx_self* self, _cx_keyraw rkey _i_MAP_ONLY(, i_valraw rmapped)); #endif // !i_no_emplace #if !defined i_no_clone STC_API _cx_self _cx_memb(_clone)(_cx_self tree); @@ -113,11 +107,11 @@ STC_API _cx_result _cx_memb(_insert)(_cx_self* self, i_key key _i_MAP_ONLY( STC_API _cx_result _cx_memb(_push)(_cx_self* self, _cx_value _val); STC_API void _cx_memb(_drop)(_cx_self* self); STC_API bool _cx_memb(_reserve)(_cx_self* self, _i_size cap); -STC_API _cx_value* _cx_memb(_find_it)(const _cx_self* self, _cx_rawkey rkey, _cx_iter* out); -STC_API _cx_iter _cx_memb(_lower_bound)(const _cx_self* self, _cx_rawkey rkey); +STC_API _cx_value* _cx_memb(_find_it)(const _cx_self* self, _cx_keyraw rkey, _cx_iter* out); +STC_API _cx_iter _cx_memb(_lower_bound)(const _cx_self* self, _cx_keyraw rkey); STC_API _cx_value* _cx_memb(_front)(const _cx_self* self); STC_API _cx_value* _cx_memb(_back)(const _cx_self* self); -STC_API int _cx_memb(_erase)(_cx_self* self, _cx_rawkey rkey); +STC_API int _cx_memb(_erase)(_cx_self* self, _cx_keyraw rkey); 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); STC_API void _cx_memb(_next)(_cx_iter* it); @@ -126,13 +120,13 @@ STC_INLINE _cx_self _cx_memb(_init)(void) { _cx_self tree = {0}; return tree STC_INLINE bool _cx_memb(_empty)(const _cx_self* cx) { return cx->size == 0; } STC_INLINE _i_size _cx_memb(_size)(const _cx_self* cx) { return cx->size; } STC_INLINE _i_size _cx_memb(_capacity)(const _cx_self* cx) { return cx->cap; } -STC_INLINE _cx_iter _cx_memb(_find)(const _cx_self* self, _cx_rawkey rkey) +STC_INLINE _cx_iter _cx_memb(_find)(const _cx_self* self, _cx_keyraw rkey) { _cx_iter it; _cx_memb(_find_it)(self, rkey, &it); return it; } -STC_INLINE bool _cx_memb(_contains)(const _cx_self* self, _cx_rawkey rkey) +STC_INLINE bool _cx_memb(_contains)(const _cx_self* self, _cx_keyraw rkey) { _cx_iter it; return _cx_memb(_find_it)(self, rkey, &it) != NULL; } -STC_INLINE const _cx_value* _cx_memb(_get)(const _cx_self* self, _cx_rawkey rkey) +STC_INLINE const _cx_value* _cx_memb(_get)(const _cx_self* self, _cx_keyraw rkey) { _cx_iter it; return _cx_memb(_find_it)(self, rkey, &it); } -STC_INLINE _cx_value* _cx_memb(_get_mut)(_cx_self* self, _cx_rawkey rkey) +STC_INLINE _cx_value* _cx_memb(_get_mut)(_cx_self* self, _cx_keyraw rkey) { _cx_iter it; return _cx_memb(_find_it)(self, rkey, &it); } STC_INLINE _cx_self @@ -185,14 +179,14 @@ _cx_memb(_shrink_to_fit)(_cx_self *self) { #ifndef _i_isset STC_API _cx_result _cx_memb(_insert_or_assign)(_cx_self* self, i_key key, i_val mapped); #if !defined i_no_emplace - STC_API _cx_result _cx_memb(_emplace_or_assign)(_cx_self* self, _cx_rawkey rkey, i_valraw rmapped); + STC_API _cx_result _cx_memb(_emplace_or_assign)(_cx_self* self, _cx_keyraw rkey, i_valraw rmapped); #endif STC_INLINE const _cx_mapped* - _cx_memb(_at)(const _cx_self* self, _cx_rawkey rkey) + _cx_memb(_at)(const _cx_self* self, _cx_keyraw rkey) { _cx_iter it; return &_cx_memb(_find_it)(self, rkey, &it)->second; } STC_INLINE _cx_mapped* - _cx_memb(_at_mut)(_cx_self* self, _cx_rawkey rkey) + _cx_memb(_at_mut)(_cx_self* self, _cx_keyraw rkey) { _cx_iter it; return &_cx_memb(_find_it)(self, rkey, &it)->second; } #endif // !_i_isset @@ -222,12 +216,12 @@ _cx_memb(_advance)(_cx_iter it, size_t n) { } STC_INLINE bool -_cx_memb(_eq)(const _cx_self* m1, const _cx_self* m2) { - if (_cx_memb(_size)(m1) != _cx_memb(_size)(m2)) return false; - _cx_iter i = _cx_memb(_begin)(m1), j = _cx_memb(_begin)(m2); +_cx_memb(_eq)(const _cx_self* self, const _cx_self* other) { + if (_cx_memb(_size)(self) != _cx_memb(_size)(other)) return false; + _cx_iter i = _cx_memb(_begin)(self), j = _cx_memb(_begin)(other); for (; i.ref; _cx_memb(_next)(&i), _cx_memb(_next)(&j)) { - const _cx_rawkey _rx = i_keyto(_i_keyref(i.ref)), _ry = i_keyto(_i_keyref(j.ref)); - if ((i_cmp_functor(m1, (&_rx), (&_ry))) != 0) return false; + const _cx_keyraw _rx = i_keyto(_i_keyref(i.ref)), _ry = i_keyto(_i_keyref(j.ref)); + if (!(i_eq((&_rx), (&_ry)))) return false; } return true; } @@ -299,7 +293,7 @@ _cx_memb(_new_node_)(_cx_self* self, int level) { return tn; } -static _cx_result _cx_memb(_insert_entry_)(_cx_self* self, _cx_rawkey rkey); +static _cx_result _cx_memb(_insert_entry_)(_cx_self* self, _cx_keyraw rkey); STC_DEF _cx_result _cx_memb(_insert)(_cx_self* self, i_key _key _i_MAP_ONLY(, i_val _mapped)) { @@ -336,7 +330,7 @@ _cx_memb(_push)(_cx_self* self, _cx_value _val) { #if !defined i_no_emplace STC_DEF _cx_result - _cx_memb(_emplace_or_assign)(_cx_self* self, _cx_rawkey rkey, i_valraw rmapped) { + _cx_memb(_emplace_or_assign)(_cx_self* self, _cx_keyraw rkey, i_valraw rmapped) { _cx_result _res = _cx_memb(_insert_entry_)(self, rkey); if (_res.inserted) _res.ref->first = i_keyfrom(rkey); @@ -351,13 +345,13 @@ _cx_memb(_push)(_cx_self* self, _cx_value _val) { #endif // !_i_isset STC_DEF _cx_value* -_cx_memb(_find_it)(const _cx_self* self, _cx_rawkey rkey, _cx_iter* out) { +_cx_memb(_find_it)(const _cx_self* self, _cx_keyraw rkey, _cx_iter* out) { i_ssize tn = self->root; _cx_node *d = out->_d = self->nodes; out->_top = 0; while (tn) { - int c; const _cx_rawkey _raw = i_keyto(_i_keyref(&d[tn].value)); - if ((c = i_cmp_functor(self, (&_raw), (&rkey))) < 0) + int c; const _cx_keyraw _raw = i_keyto(_i_keyref(&d[tn].value)); + if ((c = i_cmp((&_raw), (&rkey))) < 0) tn = d[tn].link[1]; else if (c > 0) { out->_st[out->_top++] = tn; tn = d[tn].link[0]; } @@ -368,7 +362,7 @@ _cx_memb(_find_it)(const _cx_self* self, _cx_rawkey rkey, _cx_iter* out) { } STC_DEF _cx_iter -_cx_memb(_lower_bound)(const _cx_self* self, _cx_rawkey rkey) { +_cx_memb(_lower_bound)(const _cx_self* self, _cx_keyraw rkey) { _cx_iter it; _cx_memb(_find_it)(self, rkey, &it); if (!it.ref && it._top) { @@ -418,14 +412,14 @@ _cx_memb(_split_)(_cx_node *d, i_ssize tn) { } static i_ssize -_cx_memb(_insert_entry_i_)(_cx_self* self, i_ssize tn, const _cx_rawkey* rkey, _cx_result* _res) { +_cx_memb(_insert_entry_i_)(_cx_self* self, i_ssize tn, const _cx_keyraw* rkey, _cx_result* _res) { i_ssize up[64], tx = tn; _cx_node* d = self->nodes; int c, top = 0, dir = 0; while (tx) { up[top++] = tx; - const _cx_rawkey _raw = i_keyto(_i_keyref(&d[tx].value)); - if (!(c = i_cmp_functor(self, (&_raw), rkey))) + const _cx_keyraw _raw = i_keyto(_i_keyref(&d[tx].value)); + if (!(c = i_cmp((&_raw), rkey))) { _res->ref = &d[tx].value; return tn; } dir = (c < 0); tx = d[tx].link[dir]; @@ -450,7 +444,7 @@ _cx_memb(_insert_entry_i_)(_cx_self* self, i_ssize tn, const _cx_rawkey* rkey, _ } static _cx_result -_cx_memb(_insert_entry_)(_cx_self* self, _cx_rawkey rkey) { +_cx_memb(_insert_entry_)(_cx_self* self, _cx_keyraw rkey) { _cx_result res = {NULL}; i_ssize tn = _cx_memb(_insert_entry_i_)(self, self->root, &rkey, &res); self->root = tn; @@ -459,12 +453,12 @@ _cx_memb(_insert_entry_)(_cx_self* self, _cx_rawkey rkey) { } static i_ssize -_cx_memb(_erase_r_)(_cx_self *self, i_ssize tn, const _cx_rawkey* rkey, int *erased) { +_cx_memb(_erase_r_)(_cx_self *self, i_ssize tn, const _cx_keyraw* rkey, int *erased) { _cx_node *d = self->nodes; if (tn == 0) return 0; - _cx_rawkey raw = i_keyto(_i_keyref(&d[tn].value)); - i_ssize tx; int c = i_cmp_functor(self, (&raw), rkey); + _cx_keyraw raw = i_keyto(_i_keyref(&d[tn].value)); + i_ssize tx; int c = i_cmp((&raw), rkey); if (c != 0) d[tn].link[c < 0] = _cx_memb(_erase_r_)(self, d[tn].link[c < 0], rkey, erased); else { @@ -499,7 +493,7 @@ _cx_memb(_erase_r_)(_cx_self *self, i_ssize tn, const _cx_rawkey* rkey, int *era } STC_DEF int -_cx_memb(_erase)(_cx_self* self, _cx_rawkey rkey) { +_cx_memb(_erase)(_cx_self* self, _cx_keyraw rkey) { int erased = 0; i_ssize root = _cx_memb(_erase_r_)(self, self->root, &rkey, &erased); if (!erased) @@ -511,10 +505,10 @@ _cx_memb(_erase)(_cx_self* self, _cx_rawkey rkey) { STC_DEF _cx_iter _cx_memb(_erase_at)(_cx_self* self, _cx_iter it) { - _cx_rawkey raw = i_keyto(_i_keyref(it.ref)); + _cx_keyraw raw = i_keyto(_i_keyref(it.ref)); _cx_memb(_next)(&it); if (it.ref) { - _cx_rawkey nxt = i_keyto(_i_keyref(it.ref)); + _cx_keyraw nxt = i_keyto(_i_keyref(it.ref)); _cx_memb(_erase)(self, raw); _cx_memb(_find_it)(self, nxt, &it); } else @@ -530,7 +524,7 @@ _cx_memb(_erase_range)(_cx_self* self, _cx_iter it1, _cx_iter it2) { return it1; } _cx_key k1 = *_i_keyref(it1.ref), k2 = *_i_keyref(it2.ref); - _cx_rawkey r1 = i_keyto((&k1)); + _cx_keyraw r1 = i_keyto((&k1)); for (;;) { if (memcmp(&k1, &k2, sizeof k1) == 0) return it1; @@ -566,7 +560,7 @@ _cx_memb(_clone)(_cx_self tree) { #if !defined i_no_emplace STC_DEF _cx_result -_cx_memb(_emplace)(_cx_self* self, _cx_rawkey rkey _i_MAP_ONLY(, i_valraw rmapped)) { +_cx_memb(_emplace)(_cx_self* self, _cx_keyraw rkey _i_MAP_ONLY(, i_valraw rmapped)) { _cx_result res = _cx_memb(_insert_entry_)(self, rkey); if (res.inserted) { *_i_keyref(res.ref) = i_keyfrom(rkey); @@ -594,7 +588,6 @@ _cx_memb(_drop)(_cx_self* self) { } #endif // i_implement -#undef i_cmp_functor #undef _i_size #undef _i_isset #undef _i_ismap @@ -602,5 +595,4 @@ _cx_memb(_drop)(_cx_self* self) { #undef _i_MAP_ONLY #undef _i_SET_ONLY #define CSMAP_H_INCLUDED -#include "priv/template.h" -#endif // !STC_CSMAP_V1 +#include "priv/template2.h" diff --git a/include/stc/cspan.h b/include/stc/cspan.h index 00313540..ac3e9206 100644 --- a/include/stc/cspan.h +++ b/include/stc/cspan.h @@ -48,10 +48,12 @@ int demo2() { puts(""); c_forfilter (i, Intspan, span, - , c_flt_skipwhile(i, *i.ref < 25) - && (*i.ref & 1) == 0 // even only - && c_flt_take(i, 2)) // break after 2 + c_flt_skipwhile(i, *i.ref < 25) && + (*i.ref & 1) == 0 && // even only + c_flt_take(i, 2) // break after 2 + ){ printf(" %d", *i.ref); + } puts(""); } */ @@ -65,9 +67,6 @@ int demo2() { using_cspan_3(Self, T, 1) #define using_cspan_3(Self, T, RANK) \ - using_cspan_4(Self, T, RANK, c_default_eq) - -#define using_cspan_4(Self, T, RANK, i_eq) \ typedef T Self##_value; typedef T Self##_raw; \ typedef struct { \ Self##_value *data; \ @@ -99,18 +98,6 @@ int demo2() { it->ref += _cspan_next##RANK(RANK, it->pos, it->_s->shape, it->_s->stride.d); \ if (it->pos[0] == it->_s->shape[0]) it->ref = NULL; \ } \ - STC_INLINE bool Self##_eq(const Self* x, const Self* y) { \ - if (memcmp(x->shape, y->shape, sizeof x->shape)) return false; \ - Self##_iter i = Self##_begin(x), j = Self##_begin(y); \ - for (; i.ref; Self##_next(&i), Self##_next(&j)) \ - if (!(i_eq(i.ref, j.ref))) return false; \ - return true; \ - } \ - STC_INLINE Self##_iter Self##_find(const Self* self, Self##_raw raw) { \ - Self##_iter i = Self##_begin(self); \ - for (; i.ref; Self##_next(&i)) if (i_eq(i.ref, &raw)) return i; \ - return i; \ - } \ struct stc_nostruct #define using_cspan2(Self, T) using_cspan_3(Self, T, 1); using_cspan_3(Self##2, T, 2) diff --git a/include/stc/cstack.h b/include/stc/cstack.h index f0c930e5..c2792358 100644 --- a/include/stc/cstack.h +++ b/include/stc/cstack.h @@ -33,7 +33,7 @@ #endif #include "priv/template.h" -#if !c_option(c_is_forward) +#ifndef i_is_forward #ifdef i_capacity #define i_no_clone _cx_deftypes(_c_cstack_fixed, _cx_self, i_key, i_capacity); @@ -189,4 +189,4 @@ STC_INLINE void _cx_memb(_next)(_cx_iter* it) STC_INLINE _cx_iter _cx_memb(_advance)(_cx_iter it, size_t n) { if ((it.ref += n) >= it.end) it.ref = NULL ; return it; } -#include "priv/template.h" +#include "priv/template2.h" diff --git a/include/stc/cvec.h b/include/stc/cvec.h index 91cdb25c..a1aa74b2 100644 --- a/include/stc/cvec.h +++ b/include/stc/cvec.h @@ -39,7 +39,7 @@ struct MyStruct { #include <stc/cvec.h> #define i_key int -#define i_opt c_is_forward // forward declared +#define i_is_forward // forward declared #define i_tag i32 #include <stc/cvec.h> @@ -73,7 +73,7 @@ int main() { #endif #include "priv/template.h" -#if !c_option(c_is_forward) +#ifndef i_is_forward _cx_deftypes(_c_cvec_types, _cx_self, i_key); #endif typedef i_keyraw _cx_raw; @@ -234,11 +234,10 @@ _cx_memb(_get_mut)(const _cx_self* self, _cx_raw raw) { return (_cx_value*) _cx_memb(_get)(self, raw); } STC_INLINE bool -_cx_memb(_eq)(const _cx_self* x, const _cx_self* y) { - if (x->_len != y->_len) return false; - _cx_iter i = _cx_memb(_begin)(x), j = _cx_memb(_begin)(y); - for (; i.ref; _cx_memb(_next)(&i), _cx_memb(_next)(&j)) { - const _cx_raw _rx = i_keyto(i.ref), _ry = i_keyto(j.ref); +_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; @@ -439,4 +438,4 @@ STC_DEF int _cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y) { #endif // !c_no_cmp #endif // i_implement #define CVEC_H_INCLUDED -#include "priv/template.h" +#include "priv/template2.h" diff --git a/include/stc/extend.h b/include/stc/extend.h new file mode 100644 index 00000000..66b3ebd1 --- /dev/null +++ b/include/stc/extend.h @@ -0,0 +1,66 @@ +/* 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. + */ +#include <stc/ccommon.h> +#include <stc/forward.h> + +#ifdef i_key_str + #define _i_key cstr +#elif defined i_keyclass + #define _i_key i_keyclass +#elif defined i_keyboxed + #define _i_key i_keyboxed +#elif defined i_key + #define _i_key i_key +#endif + +#ifdef i_val_str + #define _i_val cstr +#elif defined i_valclass + #define _i_val i_valclass +#elif defined i_valboxed + #define _i_val i_valboxed +#elif defined i_val + #define _i_val i_val +#endif + +#ifdef _i_key + c_PASTE(forward_, i_con)(i_type, _i_key, _i_val); +#else + c_PASTE(forward_, i_con)(i_type, _i_val); +#endif + +typedef struct { + i_extend + i_type get; +} c_PASTE(i_type, _ext); + +#define c_getcon(cptr) c_container_of(cptr, _cx_memb(_ext), get) + +#define i_is_forward +#define _i_inc <stc/i_con.h> +#include _i_inc +#undef _i_inc +#undef _i_key +#undef _i_val +#undef i_con +#undef i_extend diff --git a/include/stc/forward.h b/include/stc/forward.h index 00c531fe..31e67e7d 100644 --- a/include/stc/forward.h +++ b/include/stc/forward.h @@ -118,7 +118,7 @@ typedef union { } SELF##_result; \ \ typedef struct { \ - SELF##_value *ref, *end; \ + SELF##_value *ref, *_end; \ uint8_t* _hx; \ } SELF##_iter; \ \ diff --git a/include/stc/priv/altnames.h b/include/stc/priv/altnames.h index b10c7a11..723b6a66 100644 --- a/include/stc/priv/altnames.h +++ b/include/stc/priv/altnames.h @@ -23,7 +23,6 @@ #define c_FORLIST c_forlist #define c_FORRANGE c_forrange #define c_FOREACH c_foreach -#define c_FORWHILE c_forwhile #define c_FORPAIR c_forpair #define c_FORFILTER c_forfilter #define c_FORMATCH c_formatch @@ -33,6 +32,3 @@ #define c_WITH c_with #define c_SCOPE c_scope #define c_DEFER c_defer -#define c_NEW c_new -#define c_ARRAYLEN c_arraylen -#define c_ARGSV c_SV // [deprecated] diff --git a/include/stc/priv/raii.h b/include/stc/priv/raii.h new file mode 100644 index 00000000..bb41e0d1 --- /dev/null +++ b/include/stc/priv/raii.h @@ -0,0 +1,27 @@ +#define c_defer(...) \ + for (int _i = 1; _i; _i = 0, __VA_ARGS__) + +#define c_with(...) c_MACRO_OVERLOAD(c_with, __VA_ARGS__) +#define c_with_2(declvar, drop) \ + for (declvar, *_i, **_ip = &_i; _ip; _ip = 0, drop) +#define c_with_3(declvar, pred, drop) \ + for (declvar, *_i, **_ip = &_i; _ip && (pred); _ip = 0, drop) + +#define c_scope(...) c_MACRO_OVERLOAD(c_scope, __VA_ARGS__) +#define c_scope_2(init, drop) \ + for (int _i = (init, 1); _i; _i = 0, drop) +#define c_scope_3(init, pred, drop) \ + for (int _i = (init, 1); _i && (pred); _i = 0, drop) + +#define c_auto(...) c_MACRO_OVERLOAD(c_auto, __VA_ARGS__) +#define c_auto_2(C, a) \ + c_with_2(C a = C##_init(), C##_drop(&a)) +#define c_auto_3(C, a, b) \ + c_with_2(c_EXPAND(C a = C##_init(), b = C##_init()), \ + (C##_drop(&b), C##_drop(&a))) +#define c_auto_4(C, a, b, c) \ + c_with_2(c_EXPAND(C a = C##_init(), b = C##_init(), c = C##_init()), \ + (C##_drop(&c), C##_drop(&b), C##_drop(&a))) +#define c_auto_5(C, a, b, c, d) \ + 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))) diff --git a/include/stc/priv/template.h b/include/stc/priv/template.h index e352f488..16ef51af 100644 --- a/include/stc/priv/template.h +++ b/include/stc/priv/template.h @@ -20,28 +20,28 @@ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ -#ifndef _i_template +#ifdef _i_template + #error template.h already included +#endif #define _i_template #ifndef STC_TEMPLATE_H_INCLUDED #define STC_TEMPLATE_H_INCLUDED - #define _cx_self c_PASTE(_i_prefix, i_tag) + #define _cx_self i_type #define _cx_memb(name) c_PASTE(_cx_self, name) #define _cx_deftypes(macro, SELF, ...) c_EXPAND(macro(SELF, __VA_ARGS__)) #define _cx_value _cx_memb(_value) #define _cx_key _cx_memb(_key) #define _cx_mapped _cx_memb(_mapped) #define _cx_raw _cx_memb(_raw) - #define _cx_rawkey _cx_memb(_rawkey) + #define _cx_keyraw _cx_memb(_keyraw) #define _cx_iter _cx_memb(_iter) #define _cx_result _cx_memb(_result) #define _cx_node _cx_memb(_node) #endif -#ifdef i_type - #define i_tag i_type - #undef _i_prefix - #define _i_prefix +#ifndef i_type + #define i_type c_PASTE(_i_prefix, i_tag) #endif #ifndef i_ssize @@ -96,6 +96,9 @@ #endif #endif +#if c_option(c_is_forward) + #define i_is_forward +#endif #if c_option(c_no_cmp) #define i_no_cmp #endif @@ -289,62 +292,3 @@ #ifndef _i_has_from #define i_no_emplace #endif - -#else // ============================================================ - -#undef i_type -#undef i_tag -#undef i_imp -#undef i_opt -#undef i_less -#undef i_cmp -#undef i_eq -#undef i_hash -#undef i_rawclass -#undef i_capacity -#undef i_ssize - -#undef i_val -#undef i_val_str -#undef i_val_ssv -#undef i_valboxed -#undef i_valclass -#undef i_valraw -#undef i_valclone -#undef i_valfrom -#undef i_valto -#undef i_valdrop - -#undef i_key -#undef i_key_str -#undef i_key_ssv -#undef i_keyboxed -#undef i_keyclass -#undef i_keyraw -#undef i_keyclone -#undef i_keyfrom -#undef i_keyto -#undef i_keydrop - -#undef i_header -#undef i_implement -#undef i_static -#undef i_extern - -#undef i_allocator -#undef i_malloc -#undef i_calloc -#undef i_realloc -#undef i_free - -#undef i_no_cmp -#undef i_no_hash -#undef i_no_clone -#undef i_no_emplace - -#undef _i_prefix -#undef _i_expandby -#undef _i_has_from -#undef _i_has_eq -#undef _i_template -#endif diff --git a/include/stc/priv/template2.h b/include/stc/priv/template2.h new file mode 100644 index 00000000..27c6a890 --- /dev/null +++ b/include/stc/priv/template2.h @@ -0,0 +1,78 @@ +/* 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. + */ +#undef i_type +#undef i_tag +#undef i_imp +#undef i_opt +#undef i_less +#undef i_cmp +#undef i_eq +#undef i_hash +#undef i_rawclass +#undef i_capacity +#undef i_ssize + +#undef i_val +#undef i_val_str +#undef i_val_ssv +#undef i_valboxed +#undef i_valclass +#undef i_valraw +#undef i_valclone +#undef i_valfrom +#undef i_valto +#undef i_valdrop + +#undef i_key +#undef i_key_str +#undef i_key_ssv +#undef i_keyboxed +#undef i_keyclass +#undef i_keyraw +#undef i_keyclone +#undef i_keyfrom +#undef i_keyto +#undef i_keydrop + +#undef i_header +#undef i_implement +#undef i_static +#undef i_extern + +#undef i_allocator +#undef i_malloc +#undef i_calloc +#undef i_realloc +#undef i_free + +#undef i_no_cmp +#undef i_no_hash +#undef i_no_clone +#undef i_no_emplace +#undef i_is_forward + +#undef _i_prefix +#undef _i_expandby +#undef _i_has_from +#undef _i_has_eq +#undef _i_template |
