diff options
Diffstat (limited to 'include/stc/algo')
| -rw-r--r-- | include/stc/algo/coroutine.h | 117 | ||||
| -rw-r--r-- | include/stc/algo/crange.h | 25 | ||||
| -rw-r--r-- | include/stc/algo/csort.h | 89 | ||||
| -rw-r--r-- | include/stc/algo/filter.h | 35 | ||||
| -rw-r--r-- | include/stc/algo/raii.h | 51 | ||||
| -rw-r--r-- | include/stc/algo/sort.h | 123 |
6 files changed, 210 insertions, 230 deletions
diff --git a/include/stc/algo/coroutine.h b/include/stc/algo/coroutine.h deleted file mode 100644 index b0ecd6b7..00000000 --- a/include/stc/algo/coroutine.h +++ /dev/null @@ -1,117 +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. - */ -#ifndef STC_COROUTINE_INCLUDED -#define STC_COROUTINE_INCLUDED -/* -#include <stdio.h> -#include <stc/algo/coroutine.h> - -struct iterate { - int max_x, max_y; - int x, y; - int cco_state; // required member -}; - -bool iterate(struct iterate* I) { - cco_begin(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(true); - - cco_final: - puts("final"); - cco_end(false); -} - -int main(void) { - struct iterate it = {.max_x=3, .max_y=3}; - int n = 0; - while (iterate(&it)) - { - printf("%d %d\n", it.x, it.y); - // example of early stop: - if (++n == 20) cco_stop(&it); // signal to stop at next - } - return 0; -} -*/ -#include <stc/ccommon.h> - -enum { - cco_state_final = -1, - cco_state_done = -2, -}; - -#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 0: - -#define cco_end(retval) \ - *_state = cco_state_done; break; \ - case -99: goto _cco_final_; \ - } \ - return retval - -#define cco_yield(...) c_MACRO_OVERLOAD(cco_yield, __VA_ARGS__) -#define cco_yield_1(retval) \ - do { \ - *_state = __LINE__; return retval; \ - case __LINE__:; \ - } while (0) - -#define cco_yield_2(corocall2, ctx2) \ - cco_yield_3(corocall2, ctx2, ) - -#define cco_yield_3(corocall2, ctx2, retval) \ - do { \ - *_state = __LINE__; \ - do { \ - corocall2; if (cco_suspended(ctx2)) return retval; \ - case __LINE__:; \ - } while (cco_alive(ctx2)); \ - } while (0) - -#define cco_final \ - case cco_state_final: \ - _cco_final_ - -#define cco_return \ - goto _cco_final_ - -#define cco_stop(ctx) \ - do { \ - int* _state = &(ctx)->cco_state; \ - 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 ca06c258..faeda162 100644 --- a/include/stc/algo/crange.h +++ b/include/stc/algo/crange.h @@ -25,16 +25,17 @@ #include <stc/algo/filter.h> #include <stc/algo/crange.h> -int main() +int main(void) { - crange r1 = crange_make(80, 90); + crange r1 = crange_init(80, 90); c_foreach (i, crange, r1) printf(" %lld", *i.ref); puts(""); // use a temporary crange object. int a = 100, b = INT32_MAX; - c_forfilter (i, crange, crange_obj(a, b, 8), + crange r2 = crange_init(a, b, 8); + c_forfilter (i, crange, r2, c_flt_skip(i, 10) && c_flt_take(i, 3)) printf(" %lld", *i.ref); @@ -44,29 +45,27 @@ int main() #ifndef STC_CRANGE_H_INCLUDED #define STC_CRANGE_H_INCLUDED -#include <stc/ccommon.h> - -#define crange_obj(...) \ - (*(crange[]){crange_make(__VA_ARGS__)}) +#include "../ccommon.h" typedef long long crange_value; typedef struct { crange_value start, end, step, value; } crange; typedef struct { crange_value *ref, end, step; } crange_iter; -#define crange_make(...) c_MACRO_OVERLOAD(crange_make, __VA_ARGS__) -#define crange_make_1(stop) crange_make_3(0, stop, 1) -#define crange_make_2(start, stop) crange_make_3(start, stop, 1) +#define crange_make crange_init // [deprecated] +#define crange_init(...) c_MACRO_OVERLOAD(crange_init, __VA_ARGS__) +#define crange_init_1(stop) crange_init_3(0, stop, 1) +#define crange_init_2(start, stop) crange_init_3(start, stop, 1) -STC_INLINE crange crange_make_3(crange_value start, crange_value stop, crange_value step) +STC_INLINE crange crange_init_3(crange_value start, crange_value stop, crange_value step) { crange r = {start, stop - (step > 0), step}; return r; } STC_INLINE crange_iter crange_begin(crange* self) { self->value = self->start; crange_iter it = {&self->value, self->end, self->step}; return it; } -STC_INLINE crange_iter crange_end(crange* self) +STC_INLINE crange_iter crange_end(crange* self) { crange_iter it = {NULL}; return it; } -STC_INLINE void crange_next(crange_iter* it) +STC_INLINE void crange_next(crange_iter* it) { *it->ref += it->step; if ((it->step > 0) == (*it->ref > it->end)) it->ref = NULL; } #endif diff --git a/include/stc/algo/csort.h b/include/stc/algo/csort.h deleted file mode 100644 index 53fe9fcc..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. - */ -#include "../ccommon.h" -#include "../priv/template.h" - -/* 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 <stdio.h> -#define i_val int -#include <stc/algo/csort.h> - -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(""); -} -*/ - -typedef i_val c_PASTE(c_CONCAT(csort_, i_tag), _value); - -static inline void c_PASTE(cisort_, i_tag)(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 c_PASTE(cqsort_, i_tag)(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) c_PASTE(cqsort_, i_tag)(arr, lo, j); - else if (j > lo) c_PASTE(cisort_, i_tag)(arr, lo, j); - lo = i; - } -} - -static inline void c_PASTE(csort_, i_tag)(i_val arr[], intptr_t n) - { c_PASTE(cqsort_, i_tag)(arr, 0, n - 1); } - -#include "../priv/template2.h" diff --git a/include/stc/algo/filter.h b/include/stc/algo/filter.h index e133577c..320cd50d 100644 --- a/include/stc/algo/filter.h +++ b/include/stc/algo/filter.h @@ -24,11 +24,11 @@ #include <stdio.h> #define i_val int #include <stc/cstack.h> -#include <stc/calgo.h> +#include <stc/algorithm.h> -int main() +int main(void) { - cstack_int stk = c_make(cstack_int, {1, 2, 3, 4, 5, 6, 7, 8, 9}); + cstack_int stk = c_init(cstack_int, {1, 2, 3, 4, 5, 6, 7, 8, 9}); c_foreach (i, cstack_int, stk) printf(" %d", *i.ref); @@ -47,7 +47,7 @@ int main() #ifndef STC_FILTER_H_INCLUDED #define STC_FILTER_H_INCLUDED -#include <stc/ccommon.h> +#include "../ccommon.h" // c_forfilter: @@ -85,29 +85,42 @@ int main() 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 { \ C* _cnt = &cnt; \ - intptr_t _index = 0; \ - for (C##_iter it = C##_begin(_cnt); it.ref; ++_index) { \ + 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, _index = 0; \ + intptr_t _n = 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) \ + C##_next(&it); \ + for (_i = it; it.ref; C##_next(&it)) \ if (pred) C##_value_drop(it.ref), ++_n; \ else *_i.ref = *it.ref, C##_next(&_i); \ - _cnt->_len -= _n; \ + C##_adjust_end_(_cnt, -_n); \ } while (0) // ------------------------ private ------------------------- diff --git a/include/stc/algo/raii.h b/include/stc/algo/raii.h new file mode 100644 index 00000000..584f5c59 --- /dev/null +++ b/include/stc/algo/raii.h @@ -0,0 +1,51 @@ +/* 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. +*/ +#ifndef STC_RAII_INCLUDED +#define STC_RAII_INCLUDED + +#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))) + +#endif diff --git a/include/stc/algo/sort.h b/include/stc/algo/sort.h new file mode 100644 index 00000000..86c9b9f1 --- /dev/null +++ b/include/stc/algo/sort.h @@ -0,0 +1,123 @@ +/* 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_key - value type [required] +#define i_less - less function. default: *x < *y +#define i_type name - define {{name}}_sort_n(), else {{i_key}}array_sort_n(). + +// ex1: +#include <stdio.h> +#define i_key int +#include <stc/algo/sort.h> + +int main(void) { + int nums[] = {23, 321, 5434, 25, 245, 1, 654, 33, 543, 21}; + + intarray_sort_n(nums, c_arraylen(nums)); + + for (int i = 0; i < c_arraylen(nums); i++) + printf(" %d", nums[i]); + puts(""); +} + +// ex2: +#define i_key int +#define i_type IDeq +#define i_more // retain input template params to be reused by sort.h +#include <stc/cdeq.h> +#include <stc/algo/sort.h> + +int main(void) { + 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" + +#if !defined i_key && defined i_val + #define i_key i_val +#endif +#ifndef i_type + #define i_at(arr, idx) (&arr[idx]) + #ifndef i_tag + #define i_tag i_key + #endif + #define i_type c_PASTE(i_tag, s) + typedef i_key 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_key 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_key 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_key, 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 |