From 0c64fe64f7fb3df211e87094962e1c2a9e08a6c8 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 20 May 2021 17:46:35 +0200 Subject: Moved stc folder into include folder. --- include/stc/carray.h | 218 +++++++++++++++++++ include/stc/cbits.h | 230 ++++++++++++++++++++ include/stc/ccommon.h | 163 ++++++++++++++ include/stc/cdeq.h | 359 +++++++++++++++++++++++++++++++ include/stc/clist.h | 395 ++++++++++++++++++++++++++++++++++ include/stc/cmap.h | 470 +++++++++++++++++++++++++++++++++++++++++ include/stc/cpque.h | 146 +++++++++++++ include/stc/cqueue.h | 93 ++++++++ include/stc/crandom.h | 149 +++++++++++++ include/stc/cset.h | 71 +++++++ include/stc/csmap.h | 571 ++++++++++++++++++++++++++++++++++++++++++++++++++ include/stc/csptr.h | 164 +++++++++++++++ include/stc/csset.h | 71 +++++++ include/stc/cstack.h | 82 ++++++++ include/stc/cstr.h | 412 ++++++++++++++++++++++++++++++++++++ include/stc/csview.h | 161 ++++++++++++++ include/stc/cvec.h | 345 ++++++++++++++++++++++++++++++ 17 files changed, 4100 insertions(+) create mode 100644 include/stc/carray.h create mode 100644 include/stc/cbits.h create mode 100644 include/stc/ccommon.h create mode 100644 include/stc/cdeq.h create mode 100644 include/stc/clist.h create mode 100644 include/stc/cmap.h create mode 100644 include/stc/cpque.h create mode 100644 include/stc/cqueue.h create mode 100644 include/stc/crandom.h create mode 100644 include/stc/cset.h create mode 100644 include/stc/csmap.h create mode 100644 include/stc/csptr.h create mode 100644 include/stc/csset.h create mode 100644 include/stc/cstack.h create mode 100644 include/stc/cstr.h create mode 100644 include/stc/csview.h create mode 100644 include/stc/cvec.h (limited to 'include') diff --git a/include/stc/carray.h b/include/stc/carray.h new file mode 100644 index 00000000..e3859b8a --- /dev/null +++ b/include/stc/carray.h @@ -0,0 +1,218 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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 CARRAY_H_INCLUDED +#define CARRAY_H_INCLUDED + +#include "ccommon.h" +#include +/* +// carray2 and carray3 - 2D and 3D dynamic arrays in one memory block with easy indexing. +#include +#include +using_carray2(i, int); + +int main() { + int w = 7, h = 5; + c_with (carray2i image = carray2i_init(w, h), carray2i_del(&image)) + { + int *dat = carray2i_data(&image); + for (int i = 0; i < carray2i_size(image); ++i) + dat[i] = i; + + for (int x = 0; x < image.xdim; ++x) + for (int y = 0; y < image.ydim; ++y) + printf(" %d", image.data[x][y]); + puts("\n"); + + c_foreach (i, carray2i, image) + printf(" %d", *i.ref); + puts(""); + } +} +*/ + +#define using_carray2(...) c_MACRO_OVERLOAD(using_carray2, __VA_ARGS__) + +#define using_carray2_2(X, Value) \ + _c_using_carray2(carray2##X, Value, c_default_del, c_default_fromraw) +#define using_carray2_3(X, Value, valueDel) \ + _c_using_carray2(carray2##X, Value, valueDel, c_no_clone) +#define using_carray2_4(X, Value, valueDel, valueClone) \ + _c_using_carray2(carray2##X, Value, valueDel, valueClone) + +#define _c_using_carray2(CX, Value, valueDel, valueClone) \ +\ + typedef Value CX##_value_t; \ + typedef struct { CX##_value_t **data; size_t xdim, ydim; } CX; \ + typedef struct { CX##_value_t *ref; } CX##_iter_t; \ +\ + STC_API CX CX##_with_values(size_t xdim, size_t ydim, Value value); \ + STC_API CX CX##_with_storage(size_t xdim, size_t ydim, CX##_value_t* storage); \ + STC_API CX CX##_clone(CX src); \ +\ + STC_INLINE CX CX##_init(size_t xdim, size_t ydim) { \ + return CX##_with_storage(xdim, ydim, c_new_n(CX##_value_t, xdim*ydim)); \ + } \ + STC_INLINE size_t CX##_size(CX arr) { return arr.xdim*arr.ydim; } \ + STC_INLINE CX##_value_t *CX##_data(CX* self) { return *self->data; } \ + STC_INLINE CX##_value_t *CX##_at(CX* self, size_t x, size_t y) { \ + return *self->data + self->ydim*x + y; \ + } \ + STC_INLINE CX##_value_t *CX##_release(CX* self) { \ + CX##_value_t *t = *self->data; c_free(self->data); self->data = NULL; return t; \ + } \ +\ + STC_INLINE CX##_iter_t CX##_begin(const CX* self) { \ + return c_make(CX##_iter_t){*self->data}; \ + } \ + STC_INLINE CX##_iter_t CX##_end(const CX* self) { \ + return c_make(CX##_iter_t){*self->data + self->xdim*self->ydim}; \ + } \ + STC_INLINE void CX##_next(CX##_iter_t* it) { ++it->ref; } \ +\ + _c_implement_carray2(CX, Value, valueDel, valueClone) \ + STC_API void CX##_del(CX* self) + +// carray3: + +#define using_carray3(...) c_MACRO_OVERLOAD(using_carray3, __VA_ARGS__) + +#define using_carray3_2(X, Value) \ + _c_using_carray3(carray3##X, Value, c_default_del, c_default_fromraw) +#define using_carray3_3(X, Value, valueDel) \ + _c_using_carray3(carray3##X, Value, valueDel, c_no_clone) +#define using_carray3_4(X, Value, valueDel, valueClone) \ + _c_using_carray3(carray3##X, Value, valueDel, valueClone) + +#define _c_using_carray3(CX, Value, valueDel, valueClone) \ +\ + typedef Value CX##_value_t; \ + typedef struct { CX##_value_t ***data; size_t xdim, ydim, zdim; } CX; \ + typedef struct { CX##_value_t *ref; } CX##_iter_t; \ +\ + STC_API CX CX##_with_values(size_t xdim, size_t ydim, size_t zdim, Value value); \ + STC_API CX CX##_with_storage(size_t xdim, size_t ydim, size_t zdim, CX##_value_t* storage); \ + STC_API CX CX##_clone(CX src); \ +\ + STC_INLINE CX CX##_init(size_t xdim, size_t ydim, size_t zdim) { \ + return CX##_with_storage(xdim, ydim, zdim, c_new_n(CX##_value_t, xdim*ydim*zdim)); \ + } \ + STC_INLINE size_t CX##_size(CX arr) { return arr.xdim*arr.ydim*arr.zdim; } \ + STC_INLINE CX##_value_t* CX##_data(CX* self) { return **self->data; } \ + STC_INLINE CX##_value_t* CX##_at(CX* self, size_t x, size_t y, size_t z) { \ + return **self->data + self->zdim*(self->ydim*x + y) + z; \ + } \ +\ + STC_INLINE CX##_value_t* CX##_release(CX* self) { \ + CX##_value_t *values = **self->data; \ + c_free(self->data); self->data = NULL; \ + return values; \ + } \ +\ + STC_INLINE CX##_iter_t CX##_begin(const CX* self) { \ + return c_make(CX##_iter_t){**self->data}; \ + } \ + STC_INLINE CX##_iter_t CX##_end(const CX* self) { \ + return c_make(CX##_iter_t){**self->data + CX##_size(*self)}; \ + } \ + STC_INLINE void CX##_next(CX##_iter_t* it) { ++it->ref; } \ +\ + _c_implement_carray3(CX, Value, valueDel, valueClone) \ + STC_API void CX##_del(CX* self) + +/* -------------------------- IMPLEMENTATION ------------------------- */ + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) + +#define _c_implement_carray2(CX, Value, valueDel, valueClone) \ +\ + STC_DEF CX CX##_with_storage(size_t xdim, size_t ydim, CX##_value_t* block) { \ + CX _arr = {c_new_n(CX##_value_t*, xdim), xdim, ydim}; \ + for (size_t x = 0; x < xdim; ++x, block += ydim) \ + _arr.data[x] = block; \ + return _arr; \ + } \ +\ + STC_DEF CX CX##_with_values(size_t xdim, size_t ydim, Value value) { \ + CX _arr = CX##_init(xdim, ydim); \ + for (CX##_value_t* p = _arr.data[0], *e = p + xdim*ydim; p != e; ++p) \ + *p = value; \ + return _arr; \ + } \ +\ + STC_DEF CX CX##_clone(CX src) { \ + CX _arr = CX##_init(src.xdim, src.ydim); \ + for (CX##_value_t* p = _arr.data[0], *q = src.data[0], *e = p + CX##_size(src); p != e; ++p, ++q) \ + *p = valueClone(*q); \ + return _arr; \ + } \ +\ + STC_DEF void CX##_del(CX* self) { \ + if (!self->data) return; \ + for (CX##_value_t* p = self->data[0], *e = p + CX##_size(*self); p != e; ++p) \ + valueDel(p); \ + c_free(self->data[0]); /* data */ \ + c_free(self->data); /* pointers */ \ + } + +// carray3 impl. + +#define _c_implement_carray3(CX, Value, valueDel, valueClone) \ +\ + STC_DEF CX CX##_with_storage(size_t xdim, size_t ydim, size_t zdim, CX##_value_t* block) { \ + CX _arr = {c_new_n(CX##_value_t**, xdim*(ydim + 1)), xdim, ydim, zdim}; \ + CX##_value_t** p = (CX##_value_t**) &_arr.data[xdim]; \ + for (size_t x = 0, y; x < xdim; ++x, p += ydim) \ + for (_arr.data[x] = p, y = 0; y < ydim; ++y, block += zdim) \ + _arr.data[x][y] = block; \ + return _arr; \ + } \ +\ + STC_DEF CX CX##_with_values(size_t xdim, size_t ydim, size_t zdim, Value value) { \ + CX _arr = CX##_init(xdim, ydim, zdim); \ + for (CX##_value_t* p = **_arr.data, *e = p + xdim*ydim*zdim; p != e; ++p) \ + *p = value; \ + return _arr; \ + } \ +\ + STC_DEF CX CX##_clone(CX src) { \ + CX _arr = CX##_init(src.xdim, src.ydim, src.zdim); \ + for (CX##_value_t* p = **_arr.data, *q = **src.data, *e = p + CX##_size(src); p != e; ++p, ++q) \ + *p = valueClone(*q); \ + return _arr; \ + } \ +\ + STC_DEF void CX##_del(CX* self) { \ + if (!self->data) return; \ + for (CX##_value_t* p = **self->data, *e = p + CX##_size(*self); p != e; ++p) \ + valueDel(p); \ + c_free(self->data[0][0]); /* data */ \ + c_free(self->data); /* pointers */ \ + } + +#else +#define _c_implement_carray2(CX, Value, valueDel, valueClone) +#define _c_implement_carray3(CX, Value, valueDel, valueClone) +#endif + +#endif diff --git a/include/stc/cbits.h b/include/stc/cbits.h new file mode 100644 index 00000000..fc2d525b --- /dev/null +++ b/include/stc/cbits.h @@ -0,0 +1,230 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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 CBITS_H_INCLUDED +#define CBITS_H_INCLUDED + +/* +Similar to boost::dynamic_bitset / std::bitset + +#include +#include "cbits.h" + +int main() { + c_with (cbits bset = cbits_with_size(23, true), cbits_del(&bset)) + { + cbits_reset(&bset, 9); + cbits_resize(&bset, 43, false); + + printf("%4zu: ", bset.size); + c_forrange (i, bset.size) + 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: ", bset.size); + c_forrange (i, bset.size) + printf("%d", cbits_at(&bset, i)); + puts(""); + } +} +*/ +#include +#include +#include "ccommon.h" + +typedef struct { + uint64_t *data64; + size_t size; +} cbits; + +STC_API cbits cbits_with_size(size_t size, bool value); +STC_API cbits cbits_with_values(size_t size, uint64_t pattern); +STC_API cbits cbits_from_str(const char* str); +STC_API char* cbits_to_str(cbits set, char* str, size_t start, intptr_t stop); +STC_API cbits cbits_clone(cbits other); +STC_API void cbits_resize(cbits* self, size_t size, bool value); +STC_API cbits* cbits_assign(cbits* self, cbits other); +STC_API size_t cbits_count(cbits set); +STC_API bool cbits_subset_of(cbits set, cbits other); +STC_API bool cbits_disjoint(cbits set, cbits other); + +STC_INLINE cbits cbits_init() { return c_make(cbits){NULL, 0}; } +STC_INLINE void cbits_clear(cbits* self) { self->size = 0; } +STC_INLINE void cbits_del(cbits* self) { c_free(self->data64); } +STC_INLINE size_t cbits_size(cbits set) { return set.size; } + +STC_INLINE cbits* cbits_take(cbits* self, cbits other) { + if (self->data64 != other.data64) {cbits_del(self); *self = other;} + return self; +} + +STC_INLINE cbits cbits_move(cbits* self) { + cbits tmp = *self; self->data64 = NULL, self->size = 0; + return tmp; +} + +STC_INLINE bool cbits_test(cbits set, size_t i) { + return (set.data64[i >> 6] & (1ull << (i & 63))) != 0; +} + +STC_INLINE bool cbits_at(cbits set, size_t i) { + return (set.data64[i >> 6] & (1ull << (i & 63))) != 0; +} + +STC_INLINE void cbits_set(cbits *self, size_t i) { + self->data64[i >> 6] |= 1ull << (i & 63); +} + +STC_INLINE void cbits_reset(cbits *self, size_t i) { + self->data64[i >> 6] &= ~(1ull << (i & 63)); +} + +STC_INLINE void cbits_set_value(cbits *self, size_t i, bool value) { + self->data64[i >> 6] ^= (-(uint64_t)value ^ self->data64[i >> 6]) & 1ull << (i & 63); +} + +STC_INLINE void cbits_flip(cbits *self, size_t i) { + self->data64[i >> 6] ^= 1ull << (i & 63); +} + +STC_INLINE void cbits_set_all(cbits *self, bool value) { + memset(self->data64, -(int)value, ((self->size + 63) >> 6) * 8); +} + +STC_INLINE void cbits_set_values(cbits *self, uint64_t pattern) { + size_t n = (self->size + 63) >> 6; + for (size_t i=0; idata64[i] = pattern; +} + +STC_INLINE void cbits_flip_all(cbits *self) { + size_t n = (self->size + 63) >> 6; + for (size_t i=0; idata64[i] ^= ~0ull; +} + +/* Intersection */ +STC_INLINE void cbits_intersect(cbits *self, cbits other) { + assert(self->size == other.size); + size_t n = (self->size + 63) >> 6; + for (size_t i=0; idata64[i] &= other.data64[i]; +} +/* Union */ +STC_INLINE void cbits_union(cbits *self, cbits other) { + assert(self->size == other.size); + size_t n = (self->size + 63) >> 6; + for (size_t i=0; idata64[i] |= other.data64[i]; +} +/* Exclusive disjunction */ +STC_INLINE void cbits_xor(cbits *self, cbits other) { + assert(self->size == other.size); + size_t n = (self->size + 63) >> 6; + for (size_t i=0; idata64[i] ^= other.data64[i]; +} + +#if defined(__GNUC__) || defined(__clang__) + STC_INLINE uint64_t cpopcount64(uint64_t x) {return __builtin_popcountll(x);} +#elif defined(_MSC_VER) && defined(_WIN64) + #include + STC_INLINE uint64_t cpopcount64(uint64_t x) {return __popcnt64(x);} +#else + STC_INLINE uint64_t cpopcount64(uint64_t x) { /* http://en.wikipedia.org/wiki/Hamming_weight */ + x -= (x >> 1) & 0x5555555555555555; + x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); + x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f; + return (x * 0x0101010101010101) >> 56; + } +#endif + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) + +STC_DEF cbits* cbits_assign(cbits* self, cbits other) { + if (self->data64 == other.data64) return self; + if (self->size != other.size) return cbits_take(self, cbits_clone(other)); + memcpy(self->data64, other.data64, ((other.size + 63) >> 6)*8); + return self; +} + +STC_DEF void cbits_resize(cbits* self, size_t size, bool value) { + size_t new_n = (size + 63) >> 6, osize = self->size, old_n = (osize + 63) >> 6; + self->data64 = (uint64_t *) c_realloc(self->data64, new_n * 8); + self->size = size; + if (new_n >= old_n) { + memset(self->data64 + old_n, -(int)value, (new_n - old_n) * 8); + if (old_n > 0) { + uint64_t m = (1ull << (osize & 63)) - 1; /* mask */ + value ? (self->data64[old_n - 1] |= ~m) : (self->data64[old_n - 1] &= m); + } + } +} + +STC_DEF cbits cbits_with_size(size_t size, bool value) { + cbits set = {(uint64_t *) c_malloc(((size + 63) >> 6) * 8), size}; + cbits_set_all(&set, value); + return set; +} +STC_DEF cbits cbits_with_values(size_t size, uint64_t pattern) { + cbits set = {(uint64_t *) c_malloc(((size + 63) >> 6) * 8), size}; + cbits_set_values(&set, pattern); + return set; +} +STC_DEF cbits cbits_from_str(const char* str) { + const char* p = str; while (*p) ++p; + cbits set = cbits_with_size(p - str, false); + for (size_t i=0; i> 6) * 8; + cbits set = {(uint64_t *) memcpy(c_malloc(bytes), other.data64, bytes), other.size}; + return set; +} +STC_DEF size_t cbits_count(cbits s) { + size_t count = 0, n = s.size >> 6; + for (size_t i = 0; i < n; ++i) count += cpopcount64(s.data64[i]); + if (s.size & 63) count += cpopcount64(s.data64[n] & ((1ull << (s.size & 63)) - 1)); + return count; +} + +#define _cbits_SETOP(OPR, x) \ + assert(s.size == other.size); \ + size_t n = s.size >> 6; \ + for (size_t i = 0; i < n; ++i) \ + if ((s.data64[i] OPR other.data64[i]) != x) \ + return false; \ + if (!(s.size & 63)) return true; \ + uint64_t i = n, m = (1ull << (s.size & 63)) - 1; \ + return ((s.data64[i] OPR other.data64[i]) & m) == (x & m) + +STC_DEF bool cbits_subset_of(cbits s, cbits other) { _cbits_SETOP(|, s.data64[i]); } +STC_DEF bool cbits_disjoint(cbits s, cbits other) { _cbits_SETOP(&, 0); } + +#endif +#endif diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h new file mode 100644 index 00000000..d29ce699 --- /dev/null +++ b/include/stc/ccommon.h @@ -0,0 +1,163 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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 CCOMMON_H_INCLUDED +#define CCOMMON_H_INCLUDED + +#define __USE_MINGW_ANSI_STDIO 1 + +#include +#include +#include +#include + +#if defined(_MSC_VER) +# define STC_FORCE_INLINE static __forceinline +#elif defined(__GNUC__) || defined(__clang__) +# define STC_FORCE_INLINE static inline __attribute((always_inline)) +#else +# define STC_FORCE_INLINE static inline +#endif +#define STC_INLINE static inline + +#if defined(STC_HEADER) || defined(STC_IMPLEMENTATION) +# define STC_API extern +# define STC_DEF +# define STC_LIBRARY_ONLY(...) __VA_ARGS__ +# define STC_STATIC_ONLY(...) +#else +# define STC_API static inline +# define STC_DEF static inline +# define STC_LIBRARY_ONLY(...) +# define STC_STATIC_ONLY(...) __VA_ARGS__ +#endif + +/* Macro overloading feature support: https://rextester.com/ONP80107 */ +#define _c_CAT( A, B ) A ## B +#define _c_EXPAND(...) __VA_ARGS__ +#define _c_ARG_N(_0, _1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, _14, _15, _16, _17, N,...) N +#define _c_RSEQ_N 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 +#define _c_APPLY_ARG_N(ARGS) _c_EXPAND(_c_ARG_N ARGS) +#define _c_ARG_COUNT(...) _c_EXPAND(_c_APPLY_ARG_N((__VA_ARGS__, _c_RSEQ_N))) +#define _c_SELECT(NAME, NUM) _c_CAT( NAME ## _, NUM) + +#define c_MACRO_OVERLOAD(NAME, ...) _c_SELECT(NAME, _c_ARG_COUNT(__VA_ARGS__))(__VA_ARGS__) +#define c_static_assert(cond, ...) typedef char _static_assert_[(cond) ? 1 : -1] +#define c_container_of(ptr, type, member) \ + ((type *)((char *)(ptr) - offsetof(type, member))) + +#define c_struct(S) typedef struct S S; struct S +#if __cplusplus +#define c_new(T) static_cast(c_malloc(sizeof(T))) +#define c_new_n(T, n) static_cast(c_malloc(sizeof(T)*(n))) +#define c_make(T) T +#else +#define c_new(T) c_malloc(sizeof(T)) +#define c_new_n(T, n) c_malloc(sizeof(T)*(n)) +#define c_make(T) (T) +#endif +#ifndef c_malloc +#define c_malloc(sz) malloc(sz) +#define c_calloc(n, sz) calloc(n, sz) +#define c_realloc(p, sz) realloc(p, sz) +#define c_free(p) free(p) +#endif + +#define c_swap(T, x, y) do { T _c_t = x; x = y; y = _c_t; } while (0) +#define c_arraylen(a) (sizeof (a)/sizeof (a)[0]) + +#define c_default_compare(x, y) c_less_compare(c_default_less, x, y) +#define c_default_less(x, y) (*(x) < *(y)) +#define c_no_compare(x, y) (assert(!"c_no_compare() called"), 0) +#define c_less_compare(less, x, y) (less(y, x) - less(x, y)) + +#define c_default_equals(x, y) (*(x) == *(y)) +#define c_memcmp_equals(x, y) (memcmp(x, y, sizeof *(x)) == 0) + +#define c_rawstr_compare(x, y) strcmp(*(x), *(y)) +#define c_rawstr_equals(x, y) (strcmp(*(x), *(y)) == 0) +#define c_rawstr_hash(p, none) c_default_hash(*(p), strlen(*(p))) + +#define c_no_clone(x) (assert(!"c_no_clone() called"), x) +#define c_default_fromraw(x) (x) +#define c_default_toraw(ptr) (*(ptr)) + +#define c_default_del(ptr) ((void) (ptr)) + +/* Generic algorithms */ + +#define c_foreach(...) c_MACRO_OVERLOAD(c_foreach, __VA_ARGS__) +#define c_foreach_3(it, CX, cnt) \ + for (CX##_iter_t it = CX##_begin(&cnt), it##_end_ = CX##_end(&cnt) \ + ; it.ref != it##_end_.ref; CX##_next(&it)) +#define c_foreach_4(it, CX, start, finish) \ + for (CX##_iter_t it = start, it##_end_ = finish \ + ; it.ref != it##_end_.ref; CX##_next(&it)) + +#define c_forrange(...) c_MACRO_OVERLOAD(c_forrange, __VA_ARGS__) +#define c_forrange_1(stop) for (size_t _c_ii=0, _c_end=stop; _c_ii < _c_end; ++_c_ii) +#define c_forrange_2(i, stop) for (size_t i=0, _c_end=stop; i < _c_end; ++i) +#define c_forrange_3(i, type, stop) for (type i=0, _c_end=stop; i < _c_end; ++i) +#define c_forrange_4(i, type, start, stop) for (type i=start, _c_end=stop; i < _c_end; ++i) +#define c_forrange_5(i, type, start, stop, step) \ + for (type i=start, _c_inc=step, _c_end=(stop) - (0 < _c_inc) \ + ; (i <= _c_end) == (0 < _c_inc); i += _c_inc) + +#define c_defer(...) for (int _c_ii = 0; !_c_ii; ++_c_ii, __VA_ARGS__) +#define c_with(start, end) for (start, *_c_ii = NULL; !_c_ii; ++_c_ii, end) +#define c_withvar(ctype, var) c_with (ctype var = ctype##_init(), ctype##_del(&var)) + +#define c_withbuf(b, type, n) c_withbuf_N(b, type, n, 256) +#define c_withbuf_N(b, type, n, BYTES) \ + for (type _c_b[((BYTES) - 1) / sizeof(type) + 1], \ + *b = (n)*sizeof *b > (BYTES) ? c_new_n(type, n) : _c_b \ + ; b; b != _c_b ? c_free(b) : (void)0, b = NULL) +#define c_breakwith continue +#define c_breakdefer continue + +#define c_var(CX, c, ...) \ + CX c = CX##_init(); c_emplace(CX, c, __VA_ARGS__) + +#define c_emplace(CX, c, ...) do { \ + const CX##_rawvalue_t _c_arr[] = __VA_ARGS__; \ + CX##_emplace_items(&(c), _c_arr, c_arraylen(_c_arr)); \ +} while (0) + +#define c_del(CX, ...) do { \ + CX* _c_arr[] = {__VA_ARGS__}; \ + for (size_t _c_i = 0; _c_i < c_arraylen(_c_arr); ++_c_i) \ + CX##_del(_c_arr[_c_i]); \ +} while (0) + +#if defined(__SIZEOF_INT128__) + #define c_umul128(a, b, lo, hi) \ + do { __uint128_t _z = (__uint128_t)(a)*(b); \ + *(lo) = (uint64_t)_z, *(hi) = _z >> 64; } while(0) +#elif defined(_MSC_VER) && defined(_WIN64) + #include + #define c_umul128(a, b, lo, hi) (*(lo) = _umul128(a, b, hi), (void)0) +#elif defined(__x86_64__) + #define c_umul128(a, b, lo, hi) \ + asm("mulq %[rhs]" : "=a" (*(lo)), "=d" (*(hi)) \ + : [lhs] "0" (a), [rhs] "rm" (b)) +#endif +#endif diff --git a/include/stc/cdeq.h b/include/stc/cdeq.h new file mode 100644 index 00000000..990c556a --- /dev/null +++ b/include/stc/cdeq.h @@ -0,0 +1,359 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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 CDEQ_H_INCLUDED +#define CDEQ_H_INCLUDED + +#include "ccommon.h" +#include +#include + +#define using_cdeq(...) c_MACRO_OVERLOAD(using_cdeq, __VA_ARGS__) + +#define using_cdeq_2(X, Value) \ + using_cdeq_3(X, Value, c_default_compare) +#define using_cdeq_3(X, Value, valueCompare) \ + using_cdeq_5(X, Value, valueCompare, c_default_del, c_default_fromraw) +#define using_cdeq_4(X, Value, valueCompare, valueDel) \ + using_cdeq_5(X, Value, valueCompare, valueDel, c_no_clone) +#define using_cdeq_5(X, Value, valueCompare, valueDel, valueClone) \ + using_cdeq_7(X, Value, valueCompare, valueDel, valueClone, c_default_toraw, Value) +#define using_cdeq_7(X, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) \ + _c_using_cdeq(cdeq_##X, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) + +#define using_cdeq_str() \ + _c_using_cdeq(cdeq_str, cstr, c_rawstr_compare, cstr_del, cstr_from, cstr_toraw, const char*) + + +struct cdeq_rep { size_t size, cap; void* base[]; }; +#define _cdeq_rep(self) c_container_of((self)->_base, struct cdeq_rep, base) + + +#define _c_using_cdeq(CX, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) \ +\ + typedef Value CX##_value_t; \ + typedef RawValue CX##_rawvalue_t; \ + typedef struct {CX##_value_t *ref; } CX##_iter_t; \ + typedef struct {CX##_value_t *_base, *data;} CX; \ +\ + STC_API CX CX##_init(void); \ + STC_API CX CX##_clone(CX cx); \ + STC_API void CX##_clear(CX* self); \ + STC_API void CX##_del(CX* self); \ + STC_API CX##_iter_t CX##_find_in(CX##_iter_t p1, CX##_iter_t p2, RawValue raw); \ + STC_API int CX##_value_compare(const CX##_value_t* x, const CX##_value_t* y); \ + STC_API void CX##_push_back(CX* self, Value value); \ + STC_API void CX##_push_front(CX* self, Value value); \ + STC_API CX##_iter_t CX##_erase_range_p(CX* self, CX##_value_t* p1, CX##_value_t* p2); \ + STC_API CX##_iter_t CX##_insert_range_p(CX* self, CX##_value_t* pos, \ + const CX##_value_t* p1, const CX##_value_t* p2, bool clone); \ + STC_API CX##_iter_t CX##_emplace_range_p(CX* self, CX##_value_t* pos, \ + const CX##_rawvalue_t* p1, const CX##_rawvalue_t* p2); \ + STC_API void CX##_expand_right_(CX* self, size_t idx, size_t n); \ +\ + STC_INLINE bool CX##_empty(CX cx) {return !_cdeq_rep(&cx)->size;} \ + STC_INLINE size_t CX##_size(CX cx) {return _cdeq_rep(&cx)->size;} \ + STC_INLINE size_t CX##_capacity(CX cx) {return _cdeq_rep(&cx)->cap;} \ + STC_INLINE void CX##_swap(CX* a, CX* b) {c_swap(CX, *a, *b);} \ + STC_INLINE Value CX##_value_fromraw(RawValue raw) {return valueFromRaw(raw);} \ + STC_INLINE Value CX##_value_clone(Value val) \ + {return valueFromRaw(valueToRaw(&val));} \ + STC_INLINE void CX##_emplace_back(CX* self, RawValue raw) \ + {CX##_push_back(self, valueFromRaw(raw));} \ + STC_INLINE void CX##_emplace_front(CX* self, RawValue raw) \ + {CX##_push_front(self, valueFromRaw(raw));} \ + STC_INLINE void CX##_pop_back(CX* self) \ + {valueDel(&self->data[--_cdeq_rep(self)->size]);} \ + STC_INLINE void CX##_pop_front(CX* self) \ + {valueDel(self->data++); --_cdeq_rep(self)->size;} \ + STC_INLINE CX##_value_t* CX##_front(const CX* self) {return self->data;} \ + STC_INLINE CX##_value_t* CX##_back(const CX* self) \ + {return self->data + _cdeq_rep(self)->size - 1;} \ + STC_INLINE CX##_value_t* CX##_at(const CX* self, size_t idx) \ + {assert(idx < _cdeq_rep(self)->size); return self->data + idx;} \ + STC_INLINE CX##_iter_t CX##_begin(const CX* self) \ + {return c_make(CX##_iter_t){self->data};} \ + STC_INLINE CX##_iter_t CX##_end(const CX* self) \ + {return c_make(CX##_iter_t){self->data + _cdeq_rep(self)->size};} \ + STC_INLINE void CX##_next(CX##_iter_t* it) {++it->ref;} \ + STC_INLINE CX##_iter_t CX##_adv(CX##_iter_t it, intptr_t offs) {it.ref += offs; return it;} \ + STC_INLINE size_t CX##_idx(CX cx, CX##_iter_t it) {return it.ref - cx.data;} \ +\ + STC_INLINE CX \ + CX##_with_capacity(size_t n) { \ + CX cx = CX##_init(); \ + CX##_expand_right_(&cx, 0, n); \ + return cx; \ + } \ +\ + STC_INLINE void \ + CX##_reserve(CX* self, size_t n) { \ + size_t sz = _cdeq_rep(self)->size; \ + if (n > sz) CX##_expand_right_(self, sz, n - sz); \ + } \ +\ + STC_INLINE void \ + CX##_shrink_to_fit(CX *self) { \ + CX cx = CX##_clone(*self); \ + CX##_del(self); *self = cx; \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_insert(CX* self, size_t idx, Value value) { \ + return CX##_insert_range_p(self, self->data + idx, &value, &value + 1, false); \ + } \ + STC_INLINE CX##_iter_t \ + CX##_insert_n(CX* self, size_t idx, const CX##_value_t arr[], size_t n) { \ + return CX##_insert_range_p(self, self->data + idx, arr, arr + n, false); \ + } \ + STC_INLINE CX##_iter_t \ + CX##_insert_at(CX* self, CX##_iter_t it, Value value) { \ + return CX##_insert_range_p(self, it.ref, &value, &value + 1, false); \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_emplace(CX* self, size_t idx, RawValue raw) { \ + return CX##_emplace_range_p(self, self->data + idx, &raw, &raw + 1); \ + } \ + STC_INLINE CX##_iter_t \ + CX##_emplace_n(CX* self, size_t idx, const CX##_rawvalue_t arr[], size_t n) { \ + return CX##_emplace_range_p(self, self->data + idx, arr, arr + n); \ + } \ + STC_INLINE CX##_iter_t \ + CX##_emplace_at(CX* self, CX##_iter_t it, RawValue raw) { \ + return CX##_emplace_range_p(self, it.ref, &raw, &raw + 1); \ + } \ + STC_INLINE CX##_iter_t \ + CX##_emplace_range(CX* self, CX##_iter_t it, CX##_iter_t it1, CX##_iter_t it2) { \ + return CX##_insert_range_p(self, it.ref, it1.ref, it2.ref, true); \ + } \ + STC_INLINE void \ + CX##_emplace_items(CX *self, const CX##_rawvalue_t arr[], size_t n) { \ + CX##_emplace_range_p(self, self->data + _cdeq_rep(self)->size, arr, arr + n); \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_erase(CX* self, size_t idx) { \ + return CX##_erase_range_p(self, self->data + idx, self->data + idx + 1); \ + } \ + STC_INLINE CX##_iter_t \ + CX##_erase_n(CX* self, size_t idx, size_t n) { \ + return CX##_erase_range_p(self, self->data + idx, self->data + idx + n); \ + } \ + STC_INLINE CX##_iter_t \ + CX##_erase_at(CX* self, CX##_iter_t it) { \ + return CX##_erase_range_p(self, it.ref, it.ref + 1); \ + } \ + STC_INLINE CX##_iter_t \ + CX##_erase_range(CX* self, CX##_iter_t it1, CX##_iter_t it2) { \ + return CX##_erase_range_p(self, it1.ref, it2.ref); \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_find(const CX* self, RawValue raw) { \ + return CX##_find_in(CX##_begin(self), CX##_end(self), raw); \ + } \ +\ + STC_INLINE CX##_value_t* \ + CX##_get(const CX* self, RawValue raw) { \ + CX##_iter_t end = CX##_end(self); \ + CX##_value_t* val = CX##_find_in(CX##_begin(self), end, raw).ref; \ + return val == end.ref ? NULL : val; \ + } \ +\ + STC_INLINE void \ + CX##_sort_range(CX##_iter_t i1, CX##_iter_t i2, \ + int(*_cmp_)(const CX##_value_t*, const CX##_value_t*)) { \ + qsort(i1.ref, i2.ref - i1.ref, sizeof *i1.ref, (int(*)(const void*, const void*)) _cmp_); \ + } \ +\ + STC_INLINE void \ + CX##_sort(CX* self) { \ + CX##_sort_range(CX##_begin(self), CX##_end(self), CX##_value_compare); \ + } \ +\ + _c_implement_cdeq(CX, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) \ + struct stc_trailing_semicolon + +/* -------------------------- IMPLEMENTATION ------------------------- */ + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) + +static struct cdeq_rep _cdeq_inits = {0, 0}; +#define _cdeq_nfront(self) ((self)->data - (self)->_base) + +#define _c_implement_cdeq(CX, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) \ +\ + STC_DEF CX \ + CX##_init(void) { \ + CX##_value_t *b = (CX##_value_t *) _cdeq_inits.base; \ + return c_make(CX){b, b}; \ + } \ +\ + STC_DEF void \ + CX##_clear(CX* self) { \ + struct cdeq_rep* rep = _cdeq_rep(self); if (rep->cap) { \ + for (CX##_value_t *p = self->data, *q = p + rep->size; p != q; ++p) \ + valueDel(p); \ + rep->size = 0; \ + } \ + } \ +\ + STC_DEF void \ + CX##_del(CX* self) { \ + CX##_clear(self); \ + if (_cdeq_rep(self)->cap) \ + c_free(_cdeq_rep(self)); \ + } \ +\ + STC_DEF size_t \ + CX##_realloc_(CX* self, size_t n) { \ + struct cdeq_rep* rep = _cdeq_rep(self); \ + size_t sz = rep->size, cap = (size_t) (sz*1.7) + n + 7; \ + size_t nfront = _cdeq_nfront(self); \ + rep = (struct cdeq_rep*) c_realloc(rep->cap ? rep : NULL, \ + offsetof(struct cdeq_rep, base) + cap*sizeof(Value)); \ + rep->size = sz, rep->cap = cap; \ + self->_base = (CX##_value_t *) rep->base; \ + self->data = self->_base + nfront; \ + return cap; \ + } \ +\ + STC_DEF void \ + CX##_expand_left_(CX* self, size_t idx, size_t n) { \ + struct cdeq_rep* rep = _cdeq_rep(self); \ + size_t sz = rep->size, cap = rep->cap; \ + size_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront; \ + if (nfront >= n) { \ + self->data = (CX##_value_t *) memmove(self->data - n, self->data, idx*sizeof(Value)); \ + } else { \ + if (sz*1.3 + n > cap) cap = CX##_realloc_(self, n); \ + size_t unused = cap - (sz + n); \ + size_t pos = (nback*2 < unused) ? unused - nback : unused/2; \ + memmove(self->_base + pos + idx + n, self->data + idx, (sz - idx)*sizeof(Value)); \ + self->data = (CX##_value_t *) memmove(self->_base + pos, self->data, idx*sizeof(Value)); \ + } \ + } \ +\ + STC_DEF void \ + CX##_expand_right_(CX* self, size_t idx, size_t n) { \ + struct cdeq_rep* rep = _cdeq_rep(self); \ + size_t sz = rep->size, cap = rep->cap; \ + size_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront; \ + if (nback >= n || sz*1.3 + n > cap && CX##_realloc_(self, n)) { \ + memmove(self->data + idx + n, self->data + idx, (sz - idx)*sizeof(Value)); \ + } else { \ + size_t unused = cap - (sz + n); \ + size_t pos = (nfront*2 < unused) ? nfront : unused/2; \ + memmove(self->_base + pos, self->data, idx*sizeof(Value)); \ + memmove(self->data + pos + idx + n, self->data + idx, (sz - idx)*sizeof(Value)); \ + self->data = ((CX##_value_t *) self->_base) + pos; \ + } \ + } \ +\ + STC_DEF CX##_value_t* \ + CX##_insert_space_(CX* self, CX##_value_t* pos, size_t n) { \ + size_t idx = pos - self->data; \ + if (idx*2 < _cdeq_rep(self)->size) CX##_expand_left_(self, idx, n); \ + else CX##_expand_right_(self, idx, n); \ + if (n) _cdeq_rep(self)->size += n; /* do only if size > 0 */ \ + return self->data + idx; \ + } \ +\ + STC_DEF void \ + CX##_push_front(CX* self, Value value) { \ + if (self->data == self->_base) \ + CX##_expand_left_(self, 0, 1); \ + else \ + --self->data; \ + *self->data = value; \ + ++_cdeq_rep(self)->size; \ + } \ +\ + STC_DEF void \ + CX##_push_back(CX* self, Value value) { \ + struct cdeq_rep* rep = _cdeq_rep(self); \ + if (_cdeq_nfront(self) + rep->size == rep->cap) \ + CX##_expand_right_(self, rep->size, 1); \ + self->data[_cdeq_rep(self)->size++] = value; \ + } \ +\ + STC_DEF CX \ + CX##_clone(CX cx) { \ + size_t sz = _cdeq_rep(&cx)->size; \ + CX out = CX##_with_capacity(sz); \ + CX##_insert_range_p(&out, out.data, cx.data, cx.data + sz, true); \ + return out; \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_insert_range_p(CX* self, CX##_value_t* pos, const CX##_value_t* p1, \ + const CX##_value_t* p2, bool clone) { \ + pos = CX##_insert_space_(self, pos, p2 - p1); \ + CX##_iter_t it = {pos}; \ + if (clone) while (p1 != p2) *pos++ = valueFromRaw(valueToRaw(p1++)); \ + else memcpy(pos, p1, (p2 - p1)*sizeof *p1); \ + return it; \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_emplace_range_p(CX* self, CX##_value_t* pos, const CX##_rawvalue_t* p1, const CX##_rawvalue_t* p2) { \ + pos = CX##_insert_space_(self, pos, p2 - p1); \ + CX##_iter_t it = {pos}; \ + while (p1 != p2) *pos++ = valueFromRaw(*p1++); \ + return it; \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_erase_range_p(CX* self, CX##_value_t* p1, CX##_value_t* p2) { \ + size_t n = p2 - p1; \ + if (n > 0) { \ + CX##_value_t* p = p1, *end = self->data + _cdeq_rep(self)->size; \ + while (p != p2) valueDel(p++); \ + if (p1 == self->data) self->data += n; \ + else memmove(p1, p2, (end - p2) * sizeof(Value)); \ + _cdeq_rep(self)->size -= n; \ + } \ + return c_make(CX##_iter_t){p1}; \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_find_in(CX##_iter_t i1, CX##_iter_t i2, RawValue raw) { \ + for (; i1.ref != i2.ref; ++i1.ref) { \ + RawValue r = valueToRaw(i1.ref); \ + if (valueCompareRaw(&raw, &r) == 0) return i1; \ + } \ + return i2; \ + } \ +\ + STC_DEF int \ + CX##_value_compare(const CX##_value_t* x, const CX##_value_t* y) { \ + RawValue rx = valueToRaw(x); \ + RawValue ry = valueToRaw(y); \ + return valueCompareRaw(&rx, &ry); \ + } + +#else +#define _c_implement_cdeq(CX, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) +#endif + +#endif diff --git a/include/stc/clist.h b/include/stc/clist.h new file mode 100644 index 00000000..8e23a43e --- /dev/null +++ b/include/stc/clist.h @@ -0,0 +1,395 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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 CLIST_H_INCLUDED +#define CLIST_H_INCLUDED + +/* Circular Singly-linked Lists. + + This implements a std::forward_list-like class in C, but because it is circular, + it also support push* and splice* at both ends of the list. This makes it ideal + for being used as a queue, unlike std::forward_list. Basic usage is similar to cvec: + + #include + #include + #include + using_clist(ix, int64_t); + + int main() { + c_with (clist_ix list = clist_ix_init(), clist_ix_del(&list)) + { + stc64_t rng = stc64_init(12345); + int n; + for (int i=0; i<1000000; ++i) // one million + clist_ix_push_back(&list, stc64_rand(&rng) >> 32); + n = 0; + c_foreach (i, clist_ix, list) + if (++n % 10000 == 0) printf("%8d: %10zd\n", n, i.ref->value); + // Sort them... + clist_ix_sort(&list); // mergesort O(n*log n) + n = 0; + puts("sorted"); + c_foreach (i, clist_ix, list) + if (++n % 10000 == 0) printf("%8d: %10zd\n", n, i.ref->value); + } + } +*/ +#include "ccommon.h" +#include + +#define using_clist(...) c_MACRO_OVERLOAD(using_clist, __VA_ARGS__) + +#define using_clist_2(X, Value) \ + using_clist_3(X, Value, c_default_compare) +#define using_clist_3(X, Value, valueCompare) \ + using_clist_5(X, Value, valueCompare, c_default_del, c_default_fromraw) +#define using_clist_4(X, Value, valueCompare, valueDel) \ + using_clist_5(X, Value, valueCompare, valueDel, c_no_clone) +#define using_clist_5(X, Value, valueCompare, valueDel, valueClone) \ + _c_using_clist(clist_##X, Value, valueCompare, valueDel, valueClone, c_default_toraw, Value) +#define using_clist_7(X, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) \ + _c_using_clist(clist_##X, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) + +#define using_clist_str() \ + _c_using_clist(clist_str, cstr, c_rawstr_compare, cstr_del, cstr_from, cstr_toraw, const char*) + + +#define _c_using_clist_types(CX, Value) \ + typedef Value CX##_value_t; \ +\ + typedef struct CX##_node { \ + struct CX##_node *next; \ + CX##_value_t value; \ + } CX##_node_t; \ +\ + typedef struct { \ + CX##_node_t *last; \ + } CX; \ +\ + typedef struct { \ + CX##_node_t *const*_last, *prev; \ + CX##_value_t *ref; \ + } CX##_iter_t + +_c_using_clist_types(clist_VOID, int); +STC_API size_t _clist_count(const clist_VOID* self); +#define _clist_node(CX, vp) c_container_of(vp, CX##_node_t, value) + + +#define _c_using_clist(CX, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) \ +\ + _c_using_clist_types(CX, Value); \ + typedef RawValue CX##_rawvalue_t; \ +\ + STC_API CX CX##_clone(CX cx); \ + STC_API void CX##_del(CX* self); \ + STC_API void CX##_push_back(CX* self, Value value); \ + STC_API void CX##_push_front(CX* self, Value value); \ + STC_API CX##_iter_t CX##_insert(CX* self, CX##_iter_t it, Value value); \ + STC_API void CX##_emplace_items(CX *self, const CX##_rawvalue_t arr[], size_t n); \ + STC_API CX##_iter_t CX##_erase_at(CX* self, CX##_iter_t it); \ + STC_API CX##_iter_t CX##_erase_range(CX* self, CX##_iter_t it1, CX##_iter_t it2); \ + STC_API size_t CX##_remove(CX* self, RawValue val); \ + STC_API CX##_iter_t CX##_splice(CX* self, CX##_iter_t it, CX* other); \ + STC_API CX CX##_split(CX* self, CX##_iter_t it1, CX##_iter_t it2); \ + STC_API void CX##_sort(CX* self); \ + STC_API CX##_iter_t CX##_find_in(CX##_iter_t it1, CX##_iter_t it2, RawValue val); \ + STC_API CX##_node_t* CX##_erase_after_(CX* self, CX##_node_t* node); \ +\ + STC_INLINE CX CX##_init(void) {return c_make(CX){NULL};} \ + STC_INLINE bool CX##_empty(CX cx) {return cx.last == NULL;} \ + STC_INLINE size_t CX##_count(CX cx) \ + {return _clist_count((const clist_VOID*) &cx);} \ + STC_INLINE void CX##_clear(CX* self) {CX##_del(self);} \ + STC_INLINE Value CX##_value_clone(Value val) \ + {return valueFromRaw(valueToRaw(&val));} \ + STC_INLINE Value CX##_value_fromraw(RawValue raw) \ + {return valueFromRaw(raw);} \ + STC_INLINE void CX##_pop_front(CX* self) \ + {CX##_erase_after_(self, self->last);} \ + STC_INLINE CX##_iter_t CX##_erase(CX* self, CX##_iter_t it) \ + {return CX##_erase_at(self, it);} \ + STC_INLINE void CX##_emplace_back(CX* self, RawValue raw) \ + {CX##_push_back(self, valueFromRaw(raw));} \ + STC_INLINE void CX##_emplace_front(CX* self, RawValue raw) \ + {CX##_push_front(self, valueFromRaw(raw));} \ + STC_INLINE CX##_iter_t CX##_emplace(CX* self, CX##_iter_t it, RawValue raw) \ + {return CX##_insert(self, it, valueFromRaw(raw));} \ + STC_INLINE CX##_value_t* CX##_front(const CX* self) {return &self->last->next->value;} \ + STC_INLINE CX##_value_t* CX##_back(const CX* self) {return &self->last->value;} \ +\ + STC_INLINE CX##_iter_t \ + CX##_iter(const CX* self, CX##_node_t* prev) { \ + return c_make(CX##_iter_t){&self->last, prev, &prev->next->value}; \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_begin(const CX* self) { \ + CX##_value_t* head = self->last ? &self->last->next->value : NULL; \ + return c_make(CX##_iter_t){&self->last, self->last, head}; \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_end(const CX* self) { \ + return c_make(CX##_iter_t){NULL}; \ + } \ +\ + STC_INLINE void \ + CX##_next(CX##_iter_t* it) { \ + CX##_node_t* node = it->prev = _clist_node(CX, it->ref); \ + it->ref = (node == *it->_last ? NULL : &node->next->value); \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_fwd(CX##_iter_t it, size_t n) { \ + while (n-- && it.ref) CX##_next(&it); \ + return it; \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_splice_range(CX* self, CX##_iter_t it, \ + CX* other, CX##_iter_t it1, CX##_iter_t it2) { \ + CX tmp = CX##_split(other, it1, it2); \ + return CX##_splice(self, it, &tmp); \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_find(const CX* self, RawValue val) { \ + return CX##_find_in(CX##_begin(self), CX##_end(self), val); \ + } \ +\ + STC_INLINE CX##_value_t* \ + CX##_get(const CX* self, RawValue val) { \ + return CX##_find_in(CX##_begin(self), CX##_end(self), val).ref; \ + } \ +\ + _c_implement_clist(CX, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) \ + struct stc_trailing_semicolon + +/* -------------------------- IMPLEMENTATION ------------------------- */ + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) +#define _c_implement_clist(CX, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) \ +\ + STC_DEF CX \ + CX##_clone(CX cx) { \ + CX out = CX##_init(); \ + c_foreach_3 (it, CX, cx) CX##_emplace_back(&out, valueToRaw(it.ref)); \ + return out; \ + } \ +\ + STC_DEF void \ + CX##_del(CX* self) { \ + while (self->last) CX##_erase_after_(self, self->last); \ + } \ +\ + STC_DEF void \ + CX##_push_back(CX* self, Value value) { \ + _c_clist_insert_after(self, CX, self->last, value); \ + self->last = entry; \ + } \ +\ + STC_DEF void \ + CX##_push_front(CX* self, Value value) { \ + _c_clist_insert_after(self, CX, self->last, value); \ + if (!self->last) self->last = entry; \ + } \ +\ + STC_DEF void \ + CX##_emplace_items(CX *self, const CX##_rawvalue_t arr[], size_t n) { \ + for (size_t i=0; ilast; \ + _c_clist_insert_after(self, CX, node, value); \ + if (!self->last || !it.ref) { \ + it.prev = self->last ? self->last : entry; \ + self->last = entry; \ + } \ + it.ref = &entry->value; \ + return it; \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_erase_at(CX* self, CX##_iter_t it) { \ + CX##_node_t *node = _clist_node(CX, it.ref); \ + it.ref = (node == self->last) ? NULL : &node->next->value; \ + CX##_erase_after_(self, it.prev); \ + return it; \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_erase_range(CX* self, CX##_iter_t it1, CX##_iter_t it2) { \ + CX##_node_t *node = it1.ref ? it1.prev : NULL, \ + *done = it2.ref ? _clist_node(CX, it2.ref) : NULL; \ + while (node && node->next != done) \ + node = CX##_erase_after_(self, node); \ + return it2; \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_find_in(CX##_iter_t it1, CX##_iter_t it2, RawValue val) { \ + c_foreach_4 (it, CX, it1, it2) { \ + RawValue r = valueToRaw(it.ref); \ + if (valueCompareRaw(&r, &val) == 0) return it; \ + } \ + it2.ref = NULL; return it2; \ + } \ +\ + STC_DEF CX##_node_t* \ + CX##_erase_after_(CX* self, CX##_node_t* node) { \ + CX##_node_t* del = node->next, *next = del->next; \ + node->next = next; \ + if (del == next) self->last = node = NULL; \ + else if (self->last == del) self->last = node, node = NULL; \ + valueDel(&del->value); c_free(del); \ + return node; \ + } \ +\ + STC_DEF size_t \ + CX##_remove(CX* self, RawValue val) { \ + size_t n = 0; \ + CX##_node_t* prev = self->last, *node; \ + while (prev) { \ + node = prev->next; \ + RawValue r = valueToRaw(&node->value); \ + if (valueCompareRaw(&r, &val) == 0) \ + prev = CX##_erase_after_(self, prev), ++n; \ + else \ + prev = (node == self->last ? NULL : node); \ + } \ + return n; \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_splice(CX* self, CX##_iter_t it, CX* other) { \ + if (!self->last) \ + self->last = other->last; \ + else if (other->last) { \ + CX##_node_t *p = it.ref ? it.prev : self->last, *next = p->next; \ + it.prev = other->last; \ + p->next = it.prev->next; \ + it.prev->next = next; \ + if (!it.ref) self->last = it.prev; \ + } \ + other->last = NULL; return it; \ + } \ +\ + STC_DEF CX \ + CX##_split(CX* self, CX##_iter_t it1, CX##_iter_t it2) { \ + CX cx = {NULL}; \ + if (it1.ref == it2.ref) return cx; \ + CX##_node_t *p1 = it1.prev, \ + *p2 = it2.ref ? it2.prev : self->last; \ + p1->next = p2->next, p2->next = _clist_node(CX, it1.ref); \ + if (self->last == p2) self->last = (p1 == p2) ? NULL : p1; \ + cx.last = p2; \ + return cx; \ + } \ +\ + STC_DEF int \ + CX##_sort_cmp_(const clist_VOID_node_t* x, const clist_VOID_node_t* y) { \ + RawValue a = valueToRaw(&((const CX##_node_t *) x)->value); \ + RawValue b = valueToRaw(&((const CX##_node_t *) y)->value); \ + return valueCompareRaw(&a, &b); \ + } \ + STC_DEF void \ + CX##_sort(CX* self) { \ + if (self->last) \ + self->last = (CX##_node_t *) _clist_mergesort((clist_VOID_node_t *) self->last->next, CX##_sort_cmp_); \ + } + + +#define _c_clist_insert_after(self, CX, node, val) \ + CX##_node_t *entry = c_new (CX##_node_t); \ + if (node) entry->next = node->next, node->next = entry; \ + else entry->next = entry; \ + entry->value = val + /* +: set self->last based on node */ + +STC_DEF size_t +_clist_count(const clist_VOID* self) { + const clist_VOID_node_t *node = self->last; + if (!node) return 0; + size_t n = 1; + while ((node = node->next) != self->last) ++n; + return n; +} + +/* Singly linked list Mergesort implementation by Simon Tatham. O(n*log n). + * https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html + */ +STC_DEF clist_VOID_node_t * +_clist_mergesort(clist_VOID_node_t *list, int (*cmp)(const clist_VOID_node_t*, const clist_VOID_node_t*)) { + clist_VOID_node_t *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 > 0 || (qsize > 0 && q)) { + if (psize == 0) { + e = q, q = q->next, --qsize; + if (q == oldhead) q = NULL; + } else if (qsize == 0 || !q) { + e = p, p = p->next, --psize; + if (p == oldhead) p = NULL; + } else if (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; + } +} + +#else +#define _c_implement_clist(CX, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) +#endif + +#endif diff --git a/include/stc/cmap.h b/include/stc/cmap.h new file mode 100644 index 00000000..937da0af --- /dev/null +++ b/include/stc/cmap.h @@ -0,0 +1,470 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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 CMAP_H_INCLUDED +#define CMAP_H_INCLUDED + +// Unordered set/map - implemented as closed hashing with linear probing and no tombstones. +/* +#include +#include + +using_cmap(mx, int, char); // Map of int -> char + +int main(void) { + c_with (cmap_mx m = cmap_mx_init(), cmap_mx_del(&m)) + { + cmap_mx_emplace(&m, 5, 'a'); + cmap_mx_emplace(&m, 8, 'b'); + cmap_mx_emplace(&m, 12, 'c'); + + cmap_mx_iter_t it = cmap_mx_find(&m, 10); // none + char val = cmap_mx_find(&m, 5).ref->second; + cmap_mx_emplace_or_assign(&m, 5, 'd'); // update + cmap_mx_erase(&m, 8); + + c_foreach (i, cmap_mx, m) + printf("map %d: %c\n", i.ref->first, i.ref->second); + } +} +*/ +#include "ccommon.h" +#include +#include + +#define using_cmap(...) c_MACRO_OVERLOAD(using_cmap, __VA_ARGS__) + +#define using_cmap_3(X, Key, Mapped) \ + using_cmap_5(X, Key, Mapped, c_default_equals, c_default_hash) +#define using_cmap_5(X, Key, Mapped, keyEquals, keyHash) \ + using_cmap_7(X, Key, Mapped, keyEquals, keyHash, \ + c_default_del, c_default_fromraw) +#define using_cmap_6(X, Key, Mapped, keyEquals, keyHash, mappedDel) \ + using_cmap_7(X, Key, Mapped, keyEquals, keyHash, \ + mappedDel, c_no_clone) +#define using_cmap_7(X, Key, Mapped, keyEquals, keyHash, mappedDel, mappedClone) \ + using_cmap_9(X, Key, Mapped, keyEquals, keyHash, \ + mappedDel, mappedClone, c_default_toraw, Mapped) +#define using_cmap_9(X, Key, Mapped, keyEquals, keyHash, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped) \ + using_cmap_13(X, Key, Mapped, keyEquals, keyHash, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + c_default_del, c_default_fromraw, c_default_toraw, Key) + +#define using_cmap_13(X, Key, Mapped, keyEqualsRaw, keyHashRaw, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + keyDel, keyFromRaw, keyToRaw, RawKey) \ + _c_using_chash(cmap_##X, cmap_, Key, Mapped, keyEqualsRaw, keyHashRaw, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + keyDel, keyFromRaw, keyToRaw, RawKey) + + +#define using_cmap_keydef(...) c_MACRO_OVERLOAD(using_cmap_keydef, __VA_ARGS__) + +#define using_cmap_keydef_7(X, Key, Mapped, keyEquals, keyHash, keyDel, keyClone) \ + using_cmap_keydef_9(X, Key, Mapped, keyEquals, keyHash, \ + keyDel, keyClone, c_default_toraw, Key) + +#define using_cmap_keydef_9(X, Key, Mapped, keyEqualsRaw, keyHashRaw, \ + keyDel, keyFromRaw, keyToRaw, RawKey) \ + _c_using_chash(cmap_##X, cmap_, Key, Mapped, keyEqualsRaw, keyHashRaw, \ + c_default_del, c_default_fromraw, c_default_toraw, Mapped, \ + keyDel, keyFromRaw, keyToRaw, RawKey) + +#define using_cmap_str() \ + _c_using_chash(cmap_str, cmap_, cstr, cstr, c_rawstr_equals, c_rawstr_hash, \ + cstr_del, cstr_from, cstr_toraw, const char*, \ + cstr_del, cstr_from, cstr_toraw, const char*) + + +#define using_cmap_strkey(...) c_MACRO_OVERLOAD(using_cmap_strkey, __VA_ARGS__) + +#define using_cmap_strkey_2(X, Mapped) \ + using_cmap_strkey_4(X, Mapped, c_default_del, c_default_fromraw) +#define using_cmap_strkey_3(X, Mapped, mappedDel) \ + using_cmap_strkey_4(X, Mapped, mappedDel, c_no_clone) +#define using_cmap_strkey_4(X, Mapped, mappedDel, mappedClone) \ + _c_using_chash_strkey(X, cmap_, Mapped, mappedDel, mappedClone, c_default_toraw, Mapped) +#define using_cmap_strkey_6(X, Mapped, mappedDel, mappedFromRaw, mappedToRaw, RawMapped) \ + _c_using_chash_strkey(X, cmap_, Mapped, mappedDel, mappedFromRaw, mappedToRaw, RawMapped) + +#define _c_using_chash_strkey(X, C, Mapped, mappedDel, mappedFromRaw, mappedToRaw, RawMapped) \ + _c_using_chash(C##X, C, cstr, Mapped, c_rawstr_equals, c_rawstr_hash, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + cstr_del, cstr_from, cstr_toraw, const char*) + + +#define using_cmap_strval(...) c_MACRO_OVERLOAD(using_cmap_strval, __VA_ARGS__) + +#define using_cmap_strval_2(X, Key) \ + using_cmap_strval_4(X, Key, c_default_equals, c_default_hash) +#define using_cmap_strval_4(X, Key, keyEquals, keyHash) \ + using_cmap_strval_6(X, Key, keyEquals, keyHash, c_default_del, c_default_fromraw) +#define using_cmap_strval_5(X, Key, keyEquals, keyHash, keyDel) \ + using_cmap_strval_6(X, Key, keyEquals, keyHash, keyDel, c_no_clone) +#define using_cmap_strval_6(X, Key, keyEquals, keyHash, keyDel, keyClone) \ + using_cmap_strval_8(X, Key, keyEquals, keyHash, keyDel, keyClone, c_default_toraw, Key) + +#define using_cmap_strval_8(X, Key, keyEqualsRaw, keyHashRaw, keyDel, keyFromRaw, keyToRaw, RawKey) \ + _c_using_chash(cmap_##X, cmap_, Key, cstr, keyEqualsRaw, keyHashRaw, \ + cstr_del, cstr_from, cstr_toraw, const char*, \ + keyDel, keyFromRaw, keyToRaw, RawKey) + +#define SET_ONLY_cmap_(...) +#define MAP_ONLY_cmap_(...) __VA_ARGS__ +#define KEY_REF_cmap_(vp) (&(vp)->first) +#ifndef CMAP_SIZE_T +#define CMAP_SIZE_T uint32_t +#endif +#define _cmap_inits {NULL, NULL, 0, 0, 0.85f} +typedef struct {size_t idx; uint_fast8_t hx;} chash_bucket_t; \ + +STC_API uint64_t c_default_hash(const void *data, size_t len); +STC_INLINE uint64_t c_string_hash(const char *s) + {return c_default_hash(s, strlen(s));} +STC_INLINE uint64_t c_default_hash32(const void* data, size_t ignored) + {return *(const uint32_t *)data * 0xc6a4a7935bd1e99d;} +STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored) + {return *(const uint64_t *)data * 0xc6a4a7935bd1e99d;} + +#define _c_using_chash(CX, C, Key, Mapped, keyEqualsRaw, keyHashRaw, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + keyDel, keyFromRaw, keyToRaw, RawKey) \ + typedef Key CX##_key_t; \ + typedef Mapped CX##_mapped_t; \ + typedef RawKey CX##_rawkey_t; \ + typedef RawMapped CX##_rawmapped_t; \ + typedef CMAP_SIZE_T CX##_size_t; \ +\ + typedef SET_ONLY_##C( const CX##_key_t ) \ + MAP_ONLY_##C( struct {const CX##_key_t first; \ + Mapped second;} ) \ + CX##_value_t; \ +\ + typedef SET_ONLY_##C( RawKey ) \ + MAP_ONLY_##C( struct {RawKey first; \ + RawMapped second;} ) \ + CX##_rawvalue_t; \ +\ + typedef struct { \ + CX##_value_t *ref; \ + bool inserted; \ + } CX##_result_t; \ +\ + typedef struct { \ + CX##_value_t* table; \ + uint8_t* _hashx; \ + CX##_size_t size, bucket_count; \ + float max_load_factor; \ + } CX; \ +\ + typedef struct { \ + CX##_value_t *ref; \ + uint8_t* _hx; \ + } CX##_iter_t; \ +\ + STC_API CX CX##_with_capacity(size_t cap); \ + STC_API CX CX##_clone(CX map); \ + STC_API void CX##_del(CX* self); \ + STC_API void CX##_clear(CX* self); \ + STC_API void CX##_reserve(CX* self, size_t capacity); \ + STC_API chash_bucket_t CX##_bucket_(const CX* self, const CX##_rawkey_t* rkeyptr); \ + STC_API CX##_result_t CX##_insert_entry_(CX* self, RawKey rkey); \ + STC_API void CX##_erase_entry(CX* self, CX##_value_t* val); \ +\ + STC_INLINE CX CX##_init(void) {return c_make(CX)_cmap_inits;} \ + STC_INLINE void CX##_shrink_to_fit(CX* self) {CX##_reserve(self, self->size);} \ + STC_INLINE void CX##_max_load_factor(CX* self, float ml) {self->max_load_factor = ml;} \ + STC_INLINE bool CX##_empty(CX m) {return m.size == 0;} \ + STC_INLINE size_t CX##_size(CX m) {return m.size;} \ + STC_INLINE size_t CX##_bucket_count(CX map) {return map.bucket_count;} \ + STC_INLINE size_t CX##_capacity(CX map) \ + {return (size_t) (map.bucket_count * map.max_load_factor);} \ + STC_INLINE void CX##_swap(CX *map1, CX *map2) {c_swap(CX, *map1, *map2);} \ + STC_INLINE bool CX##_contains(const CX* self, RawKey rkey) \ + {return self->size && self->_hashx[CX##_bucket_(self, &rkey).idx];} \ +\ + STC_INLINE void \ + CX##_value_clone(CX##_value_t* _dst, CX##_value_t* _val) { \ + *(CX##_key_t*) KEY_REF_##C(_dst) = keyFromRaw(keyToRaw(KEY_REF_##C(_val))); \ + MAP_ONLY_##C( _dst->second = mappedFromRaw(mappedToRaw(&_val->second)); ) \ + } \ +\ + STC_INLINE void \ + CX##_value_del(CX##_value_t* _val) { \ + keyDel((CX##_key_t*) KEY_REF_##C(_val)); \ + MAP_ONLY_##C( mappedDel(&_val->second); ) \ + } \ +\ + STC_INLINE CX##_result_t \ + CX##_emplace(CX* self, RawKey rkey MAP_ONLY_##C(, RawMapped rmapped)) { \ + CX##_result_t _res = CX##_insert_entry_(self, rkey); \ + if (_res.inserted) { \ + *(CX##_key_t*) KEY_REF_##C(_res.ref) = keyFromRaw(rkey); \ + MAP_ONLY_##C(_res.ref->second = mappedFromRaw(rmapped);) \ + } \ + return _res; \ + } \ +\ + STC_INLINE void \ + CX##_emplace_items(CX* self, const CX##_rawvalue_t arr[], size_t n) { \ + for (size_t i=0; isecond = _mapped; )} \ + else {keyDel(&_key); MAP_ONLY_##C( mappedDel(&_mapped); )} \ + return _res; \ + } \ +\ + MAP_ONLY_##C( \ + STC_INLINE CX##_result_t \ + CX##_insert_or_assign(CX* self, Key _key, Mapped _mapped) { \ + CX##_result_t _res = CX##_insert_entry_(self, keyToRaw(&_key)); \ + if (_res.inserted) *(CX##_key_t*) &_res.ref->first = _key; \ + else {keyDel(&_key); mappedDel(&_res.ref->second);} \ + _res.ref->second = _mapped; return _res; \ + } \ + \ + STC_INLINE CX##_result_t \ + CX##_put(CX* self, Key k, Mapped m) { /* shorter, like operator[] */ \ + return CX##_insert_or_assign(self, k, m); \ + } \ + \ + STC_INLINE CX##_result_t \ + CX##_emplace_or_assign(CX* self, RawKey rkey, RawMapped rmapped) { \ + CX##_result_t _res = CX##_insert_entry_(self, rkey); \ + if (_res.inserted) *(CX##_key_t*) &_res.ref->first = keyFromRaw(rkey); \ + else mappedDel(&_res.ref->second); \ + _res.ref->second = mappedFromRaw(rmapped); return _res; \ + } \ + \ + STC_INLINE CX##_mapped_t* \ + CX##_at(const CX* self, RawKey rkey) { \ + chash_bucket_t b = CX##_bucket_(self, &rkey); \ + return &self->table[b.idx].second; \ + }) \ +\ + STC_INLINE CX##_iter_t \ + CX##_find(const CX* self, RawKey rkey) { \ + CX##_iter_t it = {NULL}; \ + if (self->size == 0) return it; \ + chash_bucket_t b = CX##_bucket_(self, &rkey); \ + if (*(it._hx = self->_hashx+b.idx)) it.ref = self->table+b.idx; \ + return it; \ + } \ +\ + STC_INLINE CX##_value_t* \ + CX##_get(const CX* self, RawKey rkey) \ + {return CX##_find(self, rkey).ref;} \ +\ + STC_INLINE CX##_iter_t \ + CX##_begin(const CX* self) { \ + CX##_iter_t it = {self->table, self->_hashx}; \ + if (it._hx) while (*it._hx == 0) ++it.ref, ++it._hx; \ + return it; \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_end(const CX* self) \ + {return c_make(CX##_iter_t){self->table + self->bucket_count};} \ +\ + STC_INLINE void \ + CX##_next(CX##_iter_t* it) \ + {while ((++it->ref, *++it->_hx == 0)) ;} \ +\ + STC_INLINE size_t \ + CX##_erase(CX* self, RawKey rkey) { \ + if (self->size == 0) return 0; \ + chash_bucket_t b = CX##_bucket_(self, &rkey); \ + return self->_hashx[b.idx] ? CX##_erase_entry(self, self->table + b.idx), 1 : 0; \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_erase_at(CX* self, CX##_iter_t it) { \ + CX##_erase_entry(self, it.ref); \ + if (*it._hx == 0) CX##_next(&it); \ + return it; \ + } \ +\ + _c_implement_chash(CX, C, Key, Mapped, keyEqualsRaw, keyHashRaw, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + keyDel, keyFromRaw, keyToRaw, RawKey) \ + struct stc_trailing_semicolon + +/* -------------------------- IMPLEMENTATION ------------------------- */ + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) + +#ifdef c_umul128 +STC_INLINE size_t fastrange_uint64_t(uint64_t x, uint64_t n) \ + {uint64_t l, h; c_umul128(x, n, &l, &h); return h;} +#endif +#define fastrange_uint32_t(x, n) ((size_t) (((uint32_t)(x)*(uint64_t)(n)) >> 32)) +#define chash_index_(h, entryPtr) ((entryPtr) - (h).table) + + +#define _c_implement_chash(CX, C, Key, Mapped, keyEqualsRaw, keyHashRaw, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + keyDel, keyFromRaw, keyToRaw, RawKey) \ + STC_DEF CX \ + CX##_with_capacity(size_t cap) { \ + CX h = _cmap_inits; \ + CX##_reserve(&h, cap); \ + return h; \ + } \ +\ + STC_INLINE void CX##_wipe_(CX* self) { \ + if (self->size == 0) return; \ + CX##_value_t* e = self->table, *end = e + self->bucket_count; \ + uint8_t *hx = self->_hashx; \ + for (; e != end; ++e) if (*hx++) CX##_value_del(e); \ + } \ +\ + STC_DEF void CX##_del(CX* self) { \ + CX##_wipe_(self); \ + c_free(self->_hashx); \ + c_free((void *) self->table); \ + } \ +\ + STC_DEF void CX##_clear(CX* self) { \ + CX##_wipe_(self); \ + self->size = 0; \ + memset(self->_hashx, 0, self->bucket_count); \ + } \ +\ + STC_DEF chash_bucket_t \ + CX##_bucket_(const CX* self, const CX##_rawkey_t* rkeyptr) { \ + const uint64_t _hash = keyHashRaw(rkeyptr, sizeof *rkeyptr); \ + uint_fast8_t _hx; size_t _cap = self->bucket_count; \ + chash_bucket_t b = {_c_SELECT(fastrange,CMAP_SIZE_T)(_hash, _cap), (uint_fast8_t)(_hash | 0x80)}; \ + const uint8_t* _hashx = self->_hashx; \ + while ((_hx = _hashx[b.idx])) { \ + if (_hx == b.hx) { \ + CX##_rawkey_t _raw = keyToRaw(KEY_REF_##C(self->table + b.idx)); \ + if (keyEqualsRaw(&_raw, rkeyptr)) break; \ + } \ + if (++b.idx == _cap) b.idx = 0; \ + } \ + return b; \ + } \ +\ + STC_DEF CX##_result_t \ + CX##_insert_entry_(CX* self, RawKey rkey) { \ + if (self->size + 1 >= (CX##_size_t) (self->bucket_count * self->max_load_factor)) \ + CX##_reserve(self, 8 + self->size * 3 / 2); \ + chash_bucket_t b = CX##_bucket_(self, &rkey); \ + CX##_result_t res = {&self->table[b.idx], !self->_hashx[b.idx]}; \ + if (res.inserted) { \ + self->_hashx[b.idx] = b.hx; \ + ++self->size; \ + } \ + return res; \ + } \ +\ + STC_DEF CX \ + CX##_clone(CX m) { \ + CX clone = { \ + c_new_n(CX##_value_t, m.bucket_count), \ + (uint8_t *) memcpy(c_malloc(m.bucket_count + 1), m._hashx, m.bucket_count + 1), \ + m.size, m.bucket_count, \ + m.max_load_factor \ + }; \ + CX##_value_t *e = m.table, *end = e + m.bucket_count, *dst = clone.table; \ + for (uint8_t *hx = m._hashx; e != end; ++hx, ++e, ++dst) \ + if (*hx) CX##_value_clone(dst, e); \ + return clone; \ + } \ +\ + STC_DEF void \ + CX##_reserve(CX* self, size_t _newcap) { \ + if (_newcap < self->size) return; \ + size_t _oldcap = self->bucket_count; \ + _newcap = (size_t) (2 + _newcap / self->max_load_factor) | 1; \ + CX _tmp = { \ + c_new_n(CX##_value_t, _newcap), \ + (uint8_t *) c_calloc(_newcap + 1, sizeof(uint8_t)), \ + self->size, (CX##_size_t) _newcap, \ + self->max_load_factor \ + }; \ + /* Rehash: */ \ + _tmp._hashx[_newcap] = 0xff; c_swap(CX, *self, _tmp); \ + CX##_value_t* e = _tmp.table, *_slot = self->table; \ + uint8_t* _hashx = self->_hashx; \ + for (size_t i = 0; i < _oldcap; ++i, ++e) \ + if (_tmp._hashx[i]) { \ + CX##_rawkey_t _raw = keyToRaw(KEY_REF_##C(e)); \ + chash_bucket_t b = CX##_bucket_(self, &_raw); \ + memcpy((void *) &_slot[b.idx], e, sizeof *e); \ + _hashx[b.idx] = (uint8_t) b.hx; \ + } \ + c_free(_tmp._hashx); \ + c_free((void *) _tmp.table); \ + } \ +\ + STC_DEF void \ + CX##_erase_entry(CX* self, CX##_value_t* _val) { \ + size_t i = chash_index_(*self, _val), j = i, k, _cap = self->bucket_count; \ + CX##_value_t* _slot = self->table; \ + uint8_t* _hashx = self->_hashx; \ + CX##_value_del(&_slot[i]); \ + for (;;) { /* delete without leaving tombstone */ \ + if (++j == _cap) j = 0; \ + if (! _hashx[j]) \ + break; \ + CX##_rawkey_t _raw = keyToRaw(KEY_REF_##C(_slot+j)); \ + k = _c_SELECT(fastrange,CMAP_SIZE_T)(keyHashRaw(&_raw, sizeof _raw), _cap); \ + if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ \ + memcpy((void *) &_slot[i], &_slot[j], sizeof *_slot), _hashx[i] = _hashx[j], i = j; \ + } \ + _hashx[i] = 0; \ + --self->size; \ + } + + +STC_DEF uint64_t c_default_hash(const void *key, size_t len) { + const uint64_t m = 0xb5ad4eceda1ce2a9; + uint64_t k, h = m + len; + const uint8_t *p = (const uint8_t *)key, *end = p + (len & ~7ull); + for (; p != end; p += 8) {memcpy(&k, p, 8); h ^= m*k;} + switch (len & 7) { + case 7: h ^= (uint64_t) p[6] << 48; + case 6: h ^= (uint64_t) p[5] << 40; + case 5: h ^= (uint64_t) p[4] << 32; + case 4: h ^= (uint64_t) p[3] << 24; + case 3: h ^= (uint64_t) p[2] << 16; + case 2: h ^= (uint64_t) p[1] << 8; + case 1: h ^= (uint64_t) p[0]; h *= m; + } + return h ^ (h >> 15); +} + +#else +#define _c_implement_chash(CX, C, Key, Mapped, keyEqualsRaw, keyHashRaw, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + keyDel, keyFromRaw, keyToRaw, RawKey) +#endif + +#endif diff --git a/include/stc/cpque.h b/include/stc/cpque.h new file mode 100644 index 00000000..20acf6f6 --- /dev/null +++ b/include/stc/cpque.h @@ -0,0 +1,146 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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. + */ + +/* Priority-Queue adapter (implemented as heap), default uses cvec. + + #include + #include + using_cvec(f, float); + using_cpque(f, cvec_f, -c_default_compare); // min-heap (increasing values) + + int main() { + stc64_t rng = stc64_init(1234); + stc64_uniformf_t dist = stc64_uniformf_init(10.0f, 100.0f); + + c_with (cpque_f queue = cpque_f_init(), cpque_f_del(&queue)) + { + // Push ten million random numbers onto the queue. + for (int i=0; i<10000000; ++i) + cpque_f_push(&queue, stc64_uniformf(&rng, dist)); + + // Extract the 100 smallest. + for (int i=0; i<100; ++i) { + printf("%f ", *cpque_f_top(queue)); + cpque_f_pop(&queue); + } + } + } +*/ +#ifndef CPQUEUE_H_INCLUDED +#define CPQUEUE_H_INCLUDED + +#include "cvec.h" + +#define using_cpque(...) c_MACRO_OVERLOAD(using_cpque, __VA_ARGS__) + +#define using_cpque_2(X, ctype) \ + _c_using_cpque(cpque_##X, ctype, ctype##_value_compare) +#define using_cpque_3(X, ctype, valueCompare) \ + _c_using_cpque(cpque_##X, ctype, valueCompare) + +#define _c_using_cpque(CX, ctype, valueCompare) \ + typedef ctype CX; \ + typedef ctype##_value_t CX##_value_t; \ + typedef ctype##_rawvalue_t CX##_rawvalue_t; \ +\ + STC_INLINE CX CX##_init(void) {return ctype##_init();} \ + STC_INLINE CX CX##_clone(CX pq) {return ctype##_clone(pq);} \ + STC_INLINE CX##_value_t CX##_value_clone(CX##_value_t val) \ + {return ctype##_value_clone(val);} \ + STC_INLINE void CX##_clear(CX* self) {ctype##_clear(self);} \ + STC_INLINE void CX##_del(CX* self) {ctype##_del(self);} \ +\ + STC_INLINE size_t CX##_size(CX pq) {return ctype##_size(pq);} \ + STC_INLINE bool CX##_empty(CX pq) {return ctype##_empty(pq);} \ + \ + STC_API void CX##_make_heap(CX* self); \ + STC_API void CX##_erase_at(CX* self, size_t idx); \ + STC_INLINE \ + const CX##_value_t* CX##_top(const CX* self) {return &self->data[0];} \ + STC_INLINE void CX##_pop(CX* self) {CX##_erase_at(self, 0);} \ + \ + STC_API void CX##_push(CX* self, CX##_value_t value); \ + STC_INLINE void CX##_emplace(CX* self, CX##_rawvalue_t raw) \ + {CX##_push(self, ctype##_value_fromraw(raw));} \ + STC_API void CX##_emplace_items(CX *self, const CX##_rawvalue_t arr[], size_t n); \ +\ + _c_implement_cpque(CX, ctype, valueCompare) \ + struct stc_trailing_semicolon + + +/* -------------------------- IMPLEMENTATION ------------------------- */ + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) + +#define _c_implement_cpque(CX, ctype, valueCompare) \ +\ + STC_INLINE void \ + CX##_sift_down_(CX##_value_t* arr, size_t i, size_t n) { \ + size_t r = i, c = i << 1; \ + while (c <= n) { \ + c += (c < n && valueCompare(&arr[c], &arr[c + 1]) < 0); \ + if (valueCompare(&arr[r], &arr[c]) < 0) { \ + CX##_value_t tmp = arr[r]; arr[r] = arr[c]; arr[r = c] = tmp; \ + } else \ + return; \ + c <<= 1; \ + } \ + } \ +\ + STC_API void \ + CX##_make_heap(CX* self) { \ + size_t n = CX##_size(*self); \ + CX##_value_t *arr = self->data - 1; \ + for (size_t k = n >> 1; k != 0; --k) \ + CX##_sift_down_(arr, k, n); \ + } \ +\ + STC_API void \ + CX##_erase_at(CX* self, size_t idx) { \ + size_t n = CX##_size(*self) - 1; \ + self->data[idx] = self->data[n]; \ + ctype##_pop_back(self); \ + CX##_sift_down_(self->data - 1, idx + 1, n); \ + } \ +\ + STC_API void \ + CX##_push(CX* self, CX##_value_t value) { \ + ctype##_push_back(self, value); /* sift-up the value */ \ + size_t n = CX##_size(*self), c = n; \ + CX##_value_t *arr = self->data - 1; \ + for (; c > 1 && valueCompare(&arr[c >> 1], &value) < 0; c >>= 1) \ + arr[c] = arr[c >> 1]; \ + if (c != n) arr[c] = value; \ + } \ +\ + STC_API void \ + CX##_emplace_items(CX *self, const CX##_rawvalue_t arr[], size_t n) { \ + for (size_t i = 0; i < n; ++i) \ + CX##_push(self, ctype##_value_fromraw(arr[i])); \ + } \ + +#else +#define _c_implement_cpque(CX, ctype, valueCompare) +#endif + +#endif diff --git a/include/stc/cqueue.h b/include/stc/cqueue.h new file mode 100644 index 00000000..37d18fba --- /dev/null +++ b/include/stc/cqueue.h @@ -0,0 +1,93 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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 CQUEUE_H_INCLUDED +#define CQUEUE_H_INCLUDED + +/* Queue adapter, default uses clist. + + #include + #include + using_cdeq(i, int); + using_cqueue(i, cdeq_i); + + int main() { + int n = 10000000; + stc64_t rng = stc64_init(1234); + stc64_uniform_t dist = stc64_uniform_init(rng, 0, n); + + c_with (cqueue_i queue = cqueue_i_init(), cqueue_i_del(&queue)) + { + // Push ten million random numbers onto the queue. + for (int i=0; i0; --i) { + int r = stc64_uniform(&dist); + if (r & 1) + ++n, cqueue_i_push(&queue, r); + else + --n, cqueue_i_pop(&queue); + } + } + printf("%d\n", n); + } +*/ +#include "cdeq.h" + +#define using_cqueue(X, ctype) \ + _c_using_cqueue(cqueue_##X, ctype) + +#define _c_using_cqueue(CX, ctype) \ + typedef ctype CX; \ + typedef ctype##_value_t CX##_value_t; \ + typedef ctype##_rawvalue_t CX##_rawvalue_t; \ + typedef ctype##_iter_t CX##_iter_t; \ +\ + STC_INLINE CX CX##_init(void) {return ctype##_init();} \ + STC_INLINE CX CX##_clone(CX q) {return ctype##_clone(q);} \ + STC_INLINE CX##_value_t CX##_value_clone(CX##_value_t val) \ + {return ctype##_value_clone(val);} \ + STC_INLINE void CX##_clear(CX* self) {ctype##_clear(self);} \ + STC_INLINE void CX##_del(CX* self) {ctype##_del(self);} \ +\ + STC_INLINE size_t CX##_size(CX q) {return ctype##_size(q);} \ + STC_INLINE bool CX##_empty(CX q) {return ctype##_empty(q);} \ + STC_INLINE CX##_value_t* CX##_front(const CX* self) {return ctype##_front(self);} \ + STC_INLINE CX##_value_t* CX##_back(const CX* self) {return ctype##_back(self);} \ +\ + STC_INLINE void CX##_pop(CX* self) {ctype##_pop_front(self);} \ + STC_INLINE void CX##_push(CX* self, ctype##_value_t value) \ + {ctype##_push_back(self, value);} \ + STC_INLINE void CX##_emplace(CX* self, CX##_rawvalue_t raw) \ + {ctype##_emplace_back(self, raw);} \ + STC_INLINE void CX##_emplace_items(CX *self, const CX##_rawvalue_t arr[], size_t n) \ + {ctype##_emplace_items(self, arr, n);} \ +\ + STC_INLINE CX##_iter_t CX##_begin(const CX* self) {return ctype##_begin(self);} \ + STC_INLINE CX##_iter_t CX##_end(const CX* self) {return ctype##_end(self);} \ + STC_INLINE void CX##_next(CX##_iter_t* it) {ctype##_next(it);} \ + struct stc_trailing_semicolon + +#endif diff --git a/include/stc/crandom.h b/include/stc/crandom.h new file mode 100644 index 00000000..073048ee --- /dev/null +++ b/include/stc/crandom.h @@ -0,0 +1,149 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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 CRANDOM_H_INCLUDED +#define CRANDOM_H_INCLUDED + +/* +// crandom: Pseudo-random number generator +#include "stc/crandom.h" +int main() { + uint64_t seed = 123456789; + stc64_t rng = stc64_init(seed); + stc64_uniform_t dist1 = stc64_uniform_init(1, 6); + stc64_uniformf_t dist2 = stc64_uniformf_init(1.0, 10.0); + stc64_normalf_t dist3 = stc64_normalf_init(1.0, 10.0); + + uint64_t i = stc64_rand(&rng); + int64_t iu = stc64_uniform(&rng, &dist1); + double xu = stc64_uniformf(&rng, &dist2); + double xn = stc64_normalf(&rng, &dist3); +} +*/ +#include "ccommon.h" +#include +#include + +typedef struct {uint64_t state[4];} stc64_t; +typedef struct {int64_t lower; uint64_t range, threshold;} stc64_uniform_t; +typedef struct {double lower, range;} stc64_uniformf_t; +typedef struct {double mean, stddev, next; unsigned has_next;} stc64_normalf_t; + + +/* Stc64: random number generator, range [0, 2^64). PRNG copyright Tyge Løvset, NORCE Research, 2020 */ +STC_API stc64_t stc64_init(uint64_t seed); +STC_API stc64_t stc64_with_seq(uint64_t seed, uint64_t seq); + +STC_INLINE uint64_t stc64_rand(stc64_t* rng) { + uint64_t *s = rng->state; + const uint64_t b = s[1], result = s[0] ^ (s[2] += s[3]|1); + s[0] = (b + (b << 3)) ^ (b >> 11); + s[1] = ((b << 24) | (b >> (64 - 24))) + result; + return result; +} + +/* Global random() */ +static stc64_t stc64_global = {{0x26aa069ea2fb1a4d, 0x70c72c95cd592d04, 0x504f333d3aa0b359, 0x6a09e667a754166b}}; +STC_INLINE void stc64_srandom(uint64_t seed) { stc64_global = stc64_init(seed); } +STC_INLINE uint64_t stc64_random(void) { return stc64_rand(&stc64_global); } + +/* Float64 random number in range [0.0, 1.0). */ +STC_INLINE double stc64_randf(stc64_t* rng) { + union {uint64_t i; double f;} u = {0x3FF0000000000000ull | (stc64_rand(rng) >> 12)}; + return u.f - 1.0; +} + +/* Int64 uniform distributed RNG, range [low, high]. */ +STC_API stc64_uniform_t stc64_uniform_init(int64_t low, int64_t high); + +/* Float64 uniform distributed RNG, range [low, high). */ +STC_INLINE stc64_uniformf_t stc64_uniformf_init(double low, double high) { + return c_make(stc64_uniformf_t){low, high - low}; +} +STC_INLINE double stc64_uniformf(stc64_t* rng, stc64_uniformf_t* dist) { + return stc64_randf(rng)*dist->range + dist->lower; +} + +/* Unbiased bounded uniform distribution. */ +STC_INLINE int64_t stc64_uniform(stc64_t* rng, stc64_uniform_t* d) { + uint64_t lo, hi; +#ifdef c_umul128 + do { c_umul128(stc64_rand(rng), d->range, &lo, &hi); } while (lo < d->threshold); +#else + hi = stc64_rand(rng) % d->range; +#endif + return d->lower + hi; +} + +/* Normal distributed RNG, Float64. */ +STC_INLINE stc64_normalf_t stc64_normalf_init(double mean, double stddev) { + return c_make(stc64_normalf_t){mean, stddev, 0.0, 0}; +} +STC_API double stc64_normalf(stc64_t* rng, stc64_normalf_t* dist); + + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) + +/* PRNG crandom: by Tyge Løvset, NORCE Research, 2020. + * Extremely fast PRNG suited for parallel usage with Weyl-sequence parameter. + * 256bit state, updates 192bit per rng. + * Faster than pcg, sfc64, xoshiro256** on most platforms. + * wyrand64 is slightly faster, but has only 64-bit state, + * unfit when longer periods or multiple threads are required. + * stc64 supports 2^63 unique threads with a minimum 2^64 period lengths each. + * Passes PractRand tested up to 8TB output, Vigna's Hamming weight test, + * and simple correlation tests, i.e. interleaved streams with one-bit diff state. + */ + +STC_DEF stc64_t stc64_init(uint64_t seed) { + return stc64_with_seq(seed, seed + 0x3504f333d3aa0b34); +} +STC_DEF stc64_t stc64_with_seq(uint64_t seed, uint64_t seq) { + stc64_t rng = {{seed, seed, seed, (seq << 1u) | 1u}}; + for (int i = 0; i < 12; ++i) stc64_rand(&rng); + return rng; +} + +/* Very fast unbiased uniform int RNG with bounds [low, high] */ +STC_DEF stc64_uniform_t stc64_uniform_init(int64_t low, int64_t high) { + stc64_uniform_t dist = {low, (uint64_t) (high - low + 1)}; + dist.threshold = (uint64_t)(-dist.range) % dist.range; + return dist; +} + +/* Marsaglia polar method for gaussian/normal distribution. */ +STC_DEF double stc64_normalf(stc64_t* rng, stc64_normalf_t* dist) { + double u1, u2, s, m; + if (dist->has_next++ & 1) + return dist->next * dist->stddev + dist->mean; + do { + u1 = 2.0 * stc64_randf(rng) - 1.0; + u2 = 2.0 * stc64_randf(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 diff --git a/include/stc/cset.h b/include/stc/cset.h new file mode 100644 index 00000000..81ccf6c7 --- /dev/null +++ b/include/stc/cset.h @@ -0,0 +1,71 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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 CSET_H_INCLUDED +#define CSET_H_INCLUDED + +// Unordered set - implemented as closed hashing with linear probing and no tombstones. +/* +#include +#include + +using_cset(sx, int); // Set of int + +int main(void) { + cset_sx s = cset_sx_init(); + cset_sx_insert(&s, 5); + cset_sx_insert(&s, 8); + + c_foreach (i, cset_sx, s) + printf("set %d\n", *i.ref); + cset_sx_del(&s); +} +*/ + +#include "cmap.h" + +/* cset: */ +#define using_cset(...) \ + c_MACRO_OVERLOAD(using_cset, __VA_ARGS__) + +#define using_cset_2(X, Key) \ + using_cset_4(X, Key, c_default_equals, c_default_hash) +#define using_cset_4(X, Key, keyEquals, keyHash) \ + using_cset_6(X, Key, keyEquals, keyHash, c_default_del, c_default_fromraw) +#define using_cset_5(X, Key, keyEquals, keyHash, keyDel) \ + using_cset_6(X, Key, keyEquals, keyHash, keyDel, c_no_clone) +#define using_cset_6(X, Key, keyEquals, keyHash, keyDel, keyClone) \ + using_cset_8(X, Key, keyEquals, keyHash, keyDel, keyClone, c_default_toraw, Key) + +#define using_cset_8(X, Key, keyEqualsRaw, keyHashRaw, keyDel, keyFromRaw, keyToRaw, RawKey) \ + _c_using_chash(cset_##X, cset_, Key, Key, keyEqualsRaw, keyHashRaw, \ + @@, @@, @@, void, keyDel, keyFromRaw, keyToRaw, RawKey) + +/* cset_str: */ +#define using_cset_str() \ + _c_using_chash_strkey(str, cset_, cstr, @@, @@, @@, void) + +#define SET_ONLY_cset_(...) __VA_ARGS__ +#define MAP_ONLY_cset_(...) +#define KEY_REF_cset_(vp) (vp) + +#endif diff --git a/include/stc/csmap.h b/include/stc/csmap.h new file mode 100644 index 00000000..4a57ee33 --- /dev/null +++ b/include/stc/csmap.h @@ -0,0 +1,571 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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 CSMAP_H_INCLUDED +#define CSMAP_H_INCLUDED + +// Sorted/Ordered set and map - implemented as an AA-tree. +/* +#include +#include +using_csmap(mx, int, char); // Sorted map + +int main(void) { + c_with (csmap_mx m = csmap_mx_init(), csmap_mx_del(&m)) + { + csmap_mx_insert(&m, 5, 'a'); + csmap_mx_insert(&m, 8, 'b'); + csmap_mx_insert(&m, 12, 'c'); + + csmap_mx_iter_t it = csmap_mx_find(&m, 10); // none + char val = csmap_mx_find(&m, 5).ref->second; + csmap_mx_put(&m, 5, 'd'); // update + csmap_mx_erase(&m, 8); + + c_foreach (i, csmap_mx, m) + printf("map %d: %c\n", i.ref->first, i.ref->second); + } +} +*/ +#include "ccommon.h" +#include +#include + +#define using_csmap(...) c_MACRO_OVERLOAD(using_csmap, __VA_ARGS__) + +#define using_csmap_3(X, Key, Mapped) \ + using_csmap_4(X, Key, Mapped, c_default_compare) +#define using_csmap_4(X, Key, Mapped, keyCompare) \ + using_csmap_6(X, Key, Mapped, keyCompare, c_default_del, c_default_fromraw) +#define using_csmap_5(X, Key, Mapped, keyCompare, mappedDel) \ + using_csmap_6(X, Key, Mapped, keyCompare, mappedDel, c_no_clone) +#define using_csmap_6(X, Key, Mapped, keyCompare, mappedDel, mappedClone) \ + using_csmap_8(X, Key, Mapped, keyCompare, mappedDel, mappedClone, c_default_toraw, Mapped) +#define using_csmap_8(X, Key, Mapped, keyCompare, mappedDel, mappedFromRaw, mappedToRaw, RawMapped) \ + using_csmap_12(X, Key, Mapped, keyCompare, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + c_default_del, c_default_fromraw, c_default_toraw, Key) + +#define using_csmap_12(X, Key, Mapped, keyCompareRaw, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + keyDel, keyFromRaw, keyToRaw, RawKey) \ + _c_using_aatree(csmap_##X, csmap_, Key, Mapped, keyCompareRaw, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + keyDel, keyFromRaw, keyToRaw, RawKey) + + +#define using_csmap_keydef(...) c_MACRO_OVERLOAD(using_csmap_keydef, __VA_ARGS__) + +#define using_csmap_keydef_6(X, Key, Mapped, keyCompare, keyDel, keyClone) \ + using_csmap_keydef_8(X, Key, Mapped, keyCompare, \ + keyDel, keyClone, c_default_toraw, Key) + +#define using_csmap_keydef_8(X, Key, Mapped, keyCompareRaw, \ + keyDel, keyFromRaw, keyToRaw, RawKey) \ + _c_using_aatree(csmap_##X, csmap_, Key, Mapped, keyCompareRaw, \ + c_default_del, c_default_fromraw, c_default_toraw, Mapped, \ + keyDel, keyFromRaw, keyToRaw, RawKey) + +#define using_csmap_str() \ + _c_using_aatree(csmap_str, csmap_, cstr, cstr, c_rawstr_compare, \ + cstr_del, cstr_from, cstr_toraw, const char*, \ + cstr_del, cstr_from, cstr_toraw, const char*) + + +#define using_csmap_strkey(...) c_MACRO_OVERLOAD(using_csmap_strkey, __VA_ARGS__) + +#define using_csmap_strkey_2(X, Mapped) \ + using_csmap_strkey_4(X, Mapped, c_default_del, c_default_fromraw) +#define using_csmap_strkey_3(X, Mapped, mappedDel) \ + using_csmap_strkey_4(X, Mapped, mappedDel, c_no_clone) +#define using_csmap_strkey_4(X, Mapped, mappedDel, mappedClone) \ + _c_using_aatree_strkey(X, csmap_, Mapped, mappedDel, mappedClone, c_default_toraw, Mapped) +#define using_csmap_strkey_6(X, Mapped, mappedDel, mappedFromRaw, mappedToRaw, RawMapped) \ + _c_using_aatree_strkey(X, csmap_, Mapped, mappedDel, mappedFromRaw, mappedToRaw, RawMapped) + +#define _c_using_aatree_strkey(X, C, Mapped, mappedDel, mappedFromRaw, mappedToRaw, RawMapped) \ + _c_using_aatree(C##X, C, cstr, Mapped, c_rawstr_compare, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + cstr_del, cstr_from, cstr_toraw, const char*) + + +#define using_csmap_strval(...) c_MACRO_OVERLOAD(using_csmap_strval, __VA_ARGS__) + +#define using_csmap_strval_2(X, Key) \ + using_csmap_strval_3(X, Key, c_default_compare) +#define using_csmap_strval_3(X, Key, keyCompare) \ + using_csmap_strval_5(X, Key, keyCompare, c_default_del, c_default_fromraw) +#define using_csmap_strval_4(X, Key, keyCompare, keyDel) \ + using_csmap_strval_5(X, Key, keyCompare, keyDel, c_no_clone) +#define using_csmap_strval_5(X, Key, keyCompare, keyDel, keyClone) \ + using_csmap_strval_7(X, Key, keyCompare, keyDel, keyClone, c_default_toraw, Key) + +#define using_csmap_strval_7(X, Key, keyCompareRaw, keyDel, keyFromRaw, keyToRaw, RawKey) \ + _c_using_aatree(csmap_##X, csmap_, Key, cstr, keyCompareRaw, \ + cstr_del, cstr_from, cstr_toraw, const char*, \ + keyDel, keyFromRaw, keyToRaw, RawKey) + +#define SET_ONLY_csmap_(...) +#define MAP_ONLY_csmap_(...) __VA_ARGS__ +#define KEY_REF_csmap_(vp) (&(vp)->first) +#ifndef CSMAP_SIZE_T +#define CSMAP_SIZE_T uint32_t +#endif +struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; +#define _csmap_rep(self) c_container_of((self)->nodes, struct csmap_rep, nodes) + + +#define _c_using_aatree(CX, C, Key, Mapped, keyCompareRaw, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + keyDel, keyFromRaw, keyToRaw, RawKey) \ + typedef Key CX##_key_t; \ + typedef Mapped CX##_mapped_t; \ + typedef RawKey CX##_rawkey_t; \ + typedef RawMapped CX##_rawmapped_t; \ + typedef CSMAP_SIZE_T CX##_size_t; \ +\ + typedef SET_ONLY_##C( const CX##_key_t ) \ + MAP_ONLY_##C( struct {const CX##_key_t first; \ + CX##_mapped_t second;} ) \ + CX##_value_t; \ +\ + typedef SET_ONLY_##C( RawKey ) \ + MAP_ONLY_##C( struct {RawKey first; \ + RawMapped second;} ) \ + CX##_rawvalue_t; \ +\ + typedef struct { \ + CX##_value_t *ref; \ + bool inserted; \ + } CX##_result_t; \ +\ + typedef struct CX##_node { \ + CX##_size_t link[2]; \ + int8_t level; \ + CX##_value_t value; \ + } CX##_node_t; \ +\ + typedef struct { \ + CX##_node_t *nodes; \ + } CX; \ +\ + typedef struct { \ + CX##_value_t *ref; \ + CX##_node_t *_d; \ + int _top; \ + CX##_size_t _tn, _st[36]; \ + } CX##_iter_t; \ +\ + STC_API CX CX##_init(void); \ + STC_API CX CX##_clone(CX tree); \ + STC_API void CX##_del(CX* self); \ + STC_API void CX##_reserve(CX* self, size_t cap); \ + STC_API CX##_value_t* CX##_find_it(const CX* self, RawKey rkey, CX##_iter_t* out); \ + STC_API CX##_iter_t CX##_lower_bound(const CX* self, RawKey rkey); \ + STC_API CX##_value_t* CX##_front(const CX* self); \ + STC_API CX##_value_t* CX##_back(const CX* self); \ + STC_API int CX##_erase(CX* self, RawKey rkey); \ + STC_API CX##_iter_t CX##_erase_at(CX* self, CX##_iter_t it); \ + STC_API CX##_iter_t CX##_erase_range(CX* self, CX##_iter_t it1, CX##_iter_t it2); \ + STC_API CX##_result_t CX##_insert_entry_(CX* self, RawKey rkey); \ + STC_API void CX##_next(CX##_iter_t* it); \ +\ + STC_INLINE bool CX##_empty(CX tree) {return _csmap_rep(&tree)->size == 0;} \ + STC_INLINE size_t CX##_size(CX tree) {return _csmap_rep(&tree)->size;} \ + STC_INLINE size_t CX##_capacity(CX tree) {return _csmap_rep(&tree)->cap;} \ + STC_INLINE void CX##_clear(CX* self) {CX##_del(self); *self = CX##_init();} \ + STC_INLINE void CX##_swap(CX* a, CX* b) {c_swap(CX, *a, *b);} \ + STC_INLINE bool CX##_contains(const CX* self, RawKey rkey) \ + {CX##_iter_t it; return CX##_find_it(self, rkey, &it) != NULL;} \ + STC_INLINE CX##_value_t* CX##_get(const CX* self, RawKey rkey) \ + {CX##_iter_t it; return CX##_find_it(self, rkey, &it);} \ +\ + STC_INLINE CX \ + CX##_with_capacity(size_t size) { \ + CX tree = CX##_init(); \ + CX##_reserve(&tree, size); \ + return tree; \ + } \ +\ + STC_INLINE void \ + CX##_value_del(CX##_value_t* val) { \ + keyDel((CX##_key_t*) KEY_REF_##C(val)); \ + MAP_ONLY_##C( mappedDel(&val->second); ) \ + } \ + STC_INLINE void \ + CX##_value_clone(CX##_value_t* dst, CX##_value_t* val) { \ + *(CX##_key_t*) KEY_REF_##C(dst) = keyFromRaw(keyToRaw(KEY_REF_##C(val))); \ + MAP_ONLY_##C( dst->second = mappedFromRaw(mappedToRaw(&val->second)); ) \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_find(const CX* self, RawKey rkey) { \ + CX##_iter_t it; \ + CX##_find_it(self, rkey, &it); \ + return it; \ + } \ +\ + STC_INLINE CX##_result_t \ + CX##_emplace(CX* self, RawKey rkey MAP_ONLY_##C(, RawMapped rmapped)) { \ + CX##_result_t res = CX##_insert_entry_(self, rkey); \ + if (res.inserted) { \ + *(CX##_key_t*) KEY_REF_##C(res.ref) = keyFromRaw(rkey); \ + MAP_ONLY_##C(res.ref->second = mappedFromRaw(rmapped);) \ + } \ + return res; \ + } \ +\ + STC_INLINE void \ + CX##_emplace_items(CX* self, const CX##_rawvalue_t arr[], size_t n) { \ + for (size_t i=0; isecond = mapped; )} \ + else {keyDel(&key); MAP_ONLY_##C( mappedDel(&mapped); )} \ + return res; \ + } \ +\ + MAP_ONLY_##C( \ + STC_INLINE CX##_result_t \ + CX##_insert_or_assign(CX* self, Key key, Mapped mapped) { \ + CX##_result_t res = CX##_insert_entry_(self, keyToRaw(&key)); \ + if (res.inserted) *(CX##_key_t*) &res.ref->first = key; \ + else {keyDel(&key); mappedDel(&res.ref->second);} \ + res.ref->second = mapped; return res; \ + } \ + \ + STC_INLINE CX##_result_t \ + CX##_put(CX* self, Key key, Mapped mapped) { \ + return CX##_insert_or_assign(self, key, mapped); \ + } \ + \ + STC_INLINE CX##_result_t \ + CX##_emplace_or_assign(CX* self, RawKey rkey, RawMapped rmapped) { \ + CX##_result_t res = CX##_insert_entry_(self, rkey); \ + if (res.inserted) *(CX##_key_t*) &res.ref->first = keyFromRaw(rkey); \ + else mappedDel(&res.ref->second); \ + res.ref->second = mappedFromRaw(rmapped); return res; \ + } \ + \ + STC_INLINE CX##_mapped_t* \ + CX##_at(const CX* self, RawKey rkey) { \ + CX##_iter_t it; \ + return &CX##_find_it(self, rkey, &it)->second; \ + }) \ +\ + STC_INLINE CX##_iter_t \ + CX##_begin(const CX* self) { \ + CX##_iter_t it; it._d = self->nodes, it._top = 0; \ + it._tn = (CX##_size_t) _csmap_rep(self)->root; \ + if (it._tn) CX##_next(&it); \ + return it; \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_end(const CX* self) {\ + return c_make(CX##_iter_t){.ref = NULL}; \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_fwd(CX##_iter_t it, size_t n) { \ + while (n-- && it.ref) CX##_next(&it); \ + return it; \ + } \ +\ + _c_implement_aatree(CX, C, Key, Mapped, keyCompareRaw, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + keyDel, keyFromRaw, keyToRaw, RawKey) \ + struct stc_trailing_semicolon + +/* -------------------------- IMPLEMENTATION ------------------------- */ + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) +static struct csmap_rep _csmap_inits = {0, 0, 0, 0}; + +#define _c_implement_aatree(CX, C, Key, Mapped, keyCompareRaw, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + keyDel, keyFromRaw, keyToRaw, RawKey) \ + STC_DEF CX \ + CX##_init(void) { \ + CX tree = {(CX##_node_t *) _csmap_inits.nodes}; \ + return tree; \ + } \ +\ + STC_DEF CX##_value_t* \ + CX##_front(const CX* self) { \ + CX##_node_t *d = self->nodes; \ + CX##_size_t tn = (CX##_size_t) _csmap_rep(self)->root; \ + while (d[tn].link[0]) tn = d[tn].link[0]; \ + return &d[tn].value; \ + } \ +\ + STC_DEF CX##_value_t* \ + CX##_back(const CX* self) { \ + CX##_node_t *d = self->nodes; \ + CX##_size_t tn = (CX##_size_t) _csmap_rep(self)->root; \ + while (d[tn].link[1]) tn = d[tn].link[1]; \ + return &d[tn].value; \ + } \ +\ + STC_DEF void \ + CX##_reserve(CX* self, size_t cap) { \ + struct csmap_rep* rep = _csmap_rep(self); \ + CX##_size_t oldcap = rep->cap; \ + if (cap > oldcap) { \ + rep = (struct csmap_rep*) c_realloc(oldcap ? rep : NULL, \ + sizeof(struct csmap_rep) + (cap + 1)*sizeof(CX##_node_t)); \ + if (oldcap == 0) \ + memset(rep, 0, sizeof(struct csmap_rep) + sizeof(CX##_node_t)); \ + rep->cap = cap; \ + self->nodes = (CX##_node_t *) rep->nodes; \ + } \ + } \ +\ + STC_DEF CX##_size_t \ + CX##_node_new_(CX* self, int level) { \ + size_t tn; struct csmap_rep *rep = _csmap_rep(self); \ + if (rep->disp) { \ + tn = rep->disp; \ + rep->disp = self->nodes[tn].link[1]; \ + } else { \ + if ((tn = rep->head + 1) > rep->cap) CX##_reserve(self, 4 + tn*3/2); \ + ++_csmap_rep(self)->head; /* do after reserve */ \ + } \ + CX##_node_t* dn = &self->nodes[tn]; \ + dn->link[0] = dn->link[1] = 0; dn->level = level; \ + return (CX##_size_t) tn; \ + } \ +\ + STC_DEF CX##_value_t* \ + CX##_find_it(const CX* self, RawKey rkey, CX##_iter_t* out) { \ + CX##_size_t tn = _csmap_rep(self)->root; \ + CX##_node_t *d = out->_d = self->nodes; \ + out->_top = 0; \ + while (tn) { \ + int c; CX##_rawkey_t raw = keyToRaw(KEY_REF_##C(&d[tn].value)); \ + if ((c = keyCompareRaw(&raw, &rkey)) < 0) \ + tn = d[tn].link[1]; \ + else if (c > 0) \ + { out->_st[out->_top++] = tn; tn = d[tn].link[0]; } \ + else \ + { out->_tn = d[tn].link[1]; return (out->ref = &d[tn].value); } \ + } \ + return (out->ref = NULL); \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_lower_bound(const CX* self, RawKey rkey) { \ + CX##_iter_t it; \ + CX##_find_it(self, rkey, &it); \ + if (!it.ref && it._top) { \ + CX##_size_t tn = it._st[--it._top]; \ + it._tn = it._d[tn].link[1]; \ + it.ref = &it._d[tn].value; \ + } \ + return it; \ + } \ +\ + STC_DEF void \ + CX##_next(CX##_iter_t *it) { \ + CX##_size_t tn = it->_tn; \ + if (it->_top || tn) { \ + while (tn) { \ + it->_st[it->_top++] = tn; \ + tn = it->_d[tn].link[0]; \ + } \ + tn = it->_st[--it->_top]; \ + it->_tn = it->_d[tn].link[1]; \ + it->ref = &it->_d[tn].value; \ + } else \ + it->ref = NULL; \ + } \ +\ + static CX##_size_t \ + CX##_skew_(CX##_node_t *d, CX##_size_t tn) { \ + if (tn && d[d[tn].link[0]].level == d[tn].level) { \ + CX##_size_t tmp = d[tn].link[0]; \ + d[tn].link[0] = d[tmp].link[1]; \ + d[tmp].link[1] = tn; \ + tn = tmp; \ + } \ + return tn; \ + } \ + static CX##_size_t \ + CX##_split_(CX##_node_t *d, CX##_size_t tn) { \ + if (d[d[d[tn].link[1]].link[1]].level == d[tn].level) { \ + CX##_size_t tmp = d[tn].link[1]; \ + d[tn].link[1] = d[tmp].link[0]; \ + d[tmp].link[0] = tn; \ + tn = tmp; \ + ++d[tn].level; \ + } \ + return tn; \ + } \ +\ + STC_DEF CX##_size_t \ + CX##_insert_entry_i_(CX* self, CX##_size_t tn, const CX##_rawkey_t* rkey, CX##_result_t* res) { \ + CX##_size_t up[64], tx = tn; \ + CX##_node_t* d = self->nodes; \ + int c, top = 0, dir = 0; \ + while (tx) { \ + up[top++] = tx; \ + RawKey raw = keyToRaw(KEY_REF_##C(&d[tx].value)); \ + if ((c = keyCompareRaw(&raw, rkey)) == 0) {res->ref = &d[tx].value; return tn;} \ + dir = (c < 0); \ + tx = d[tx].link[dir]; \ + } \ + tx = CX##_node_new_(self, 1); d = self->nodes; \ + res->ref = &d[tx].value, res->inserted = true; \ + if (top == 0) return tx; \ + d[up[top - 1]].link[dir] = tx; \ + while (top--) { \ + if (top) dir = (d[up[top - 1]].link[1] == up[top]); \ + up[top] = CX##_skew_(d, up[top]); \ + up[top] = CX##_split_(d, up[top]); \ + if (top) d[up[top - 1]].link[dir] = up[top]; \ + } \ + return up[0]; \ + } \ +\ + STC_DEF CX##_result_t \ + CX##_insert_entry_(CX* self, RawKey rkey) { \ + CX##_result_t res = {NULL, false}; \ + CX##_size_t tn = CX##_insert_entry_i_(self, (CX##_size_t) _csmap_rep(self)->root, &rkey, &res); \ + _csmap_rep(self)->root = tn; \ + _csmap_rep(self)->size += res.inserted; \ + return res; \ + } \ +\ + STC_DEF CX##_size_t \ + CX##_erase_r_(CX##_node_t *d, CX##_size_t tn, const CX##_rawkey_t* rkey, int *erased) { \ + if (tn == 0) return 0; \ + RawKey raw = keyToRaw(KEY_REF_##C(&d[tn].value)); \ + CX##_size_t tx; int c = keyCompareRaw(&raw, rkey); \ + if (c != 0) \ + d[tn].link[c < 0] = CX##_erase_r_(d, d[tn].link[c < 0], rkey, erased); \ + else { \ + if (!(*erased)++) CX##_value_del(&d[tn].value); \ + if (d[tn].link[0] && d[tn].link[1]) { \ + tx = d[tn].link[0]; \ + while (d[tx].link[1]) \ + tx = d[tx].link[1]; \ + memcpy((void *) &d[tn].value, &d[tx].value, sizeof d[0].value); /* move */ \ + raw = keyToRaw(KEY_REF_##C(&d[tn].value)); \ + d[tn].link[0] = CX##_erase_r_(d, d[tn].link[0], &raw, erased); \ + } else { /* unlink node */ \ + tx = tn; \ + tn = d[tn].link[ d[tn].link[0] == 0 ]; \ + /* move it to disposed nodes list */ \ + struct csmap_rep *rep = c_container_of(d, struct csmap_rep, nodes); \ + d[tx].link[1] = (CX##_size_t) rep->disp; \ + rep->disp = tx; \ + } \ + } \ + tx = d[tn].link[1]; \ + if (d[d[tn].link[0]].level < d[tn].level - 1 || d[tx].level < d[tn].level - 1) { \ + if (d[tx].level > --d[tn].level) \ + d[tx].level = d[tn].level; \ + tn = CX##_skew_(d, tn); \ + tx = d[tn].link[1] = CX##_skew_(d, d[tn].link[1]); \ + d[tx].link[1] = CX##_skew_(d, d[tx].link[1]); \ + tn = CX##_split_(d, tn); \ + d[tn].link[1] = CX##_split_(d, d[tn].link[1]); \ + } \ + return tn; \ + } \ +\ + STC_DEF int \ + CX##_erase(CX* self, RawKey rkey) { \ + int erased = 0; \ + CX##_size_t root = CX##_erase_r_(self->nodes, (CX##_size_t) _csmap_rep(self)->root, &rkey, &erased); \ + return erased ? (_csmap_rep(self)->root = root, --_csmap_rep(self)->size, 1) : 0; \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_erase_at(CX* self, CX##_iter_t it) { \ + CX##_rawkey_t raw = keyToRaw(KEY_REF_##C(it.ref)), nxt; \ + CX##_next(&it); \ + if (it.ref) nxt = keyToRaw(KEY_REF_##C(it.ref)); \ + CX##_erase(self, raw); \ + if (it.ref) CX##_find_it(self, nxt, &it); \ + return it; \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_erase_range(CX* self, CX##_iter_t it1, CX##_iter_t it2) { \ + if (!it2.ref) { while (it1.ref) it1 = CX##_erase_at(self, it1); \ + return it1; } \ + CX##_key_t k1 = *KEY_REF_##C(it1.ref), k2 = *KEY_REF_##C(it2.ref); \ + CX##_rawkey_t r1 = keyToRaw(&k1); \ + for (;;) { \ + if (memcmp(&k1, &k2, sizeof k1) == 0) return it1; \ + CX##_next(&it1); k1 = *KEY_REF_##C(it1.ref); \ + CX##_erase(self, r1); \ + CX##_find_it(self, (r1 = keyToRaw(&k1)), &it1); \ + } \ + } \ +\ + static CX##_size_t \ + CX##_clone_r_(CX* self, CX##_node_t* src, CX##_size_t sn) { \ + if (sn == 0) return 0; \ + CX##_size_t tx, tn = CX##_node_new_(self, src[sn].level); \ + CX##_value_clone(&self->nodes[tn].value, &src[sn].value); \ + tx = CX##_clone_r_(self, src, src[sn].link[0]); self->nodes[tn].link[0] = tx; \ + tx = CX##_clone_r_(self, src, src[sn].link[1]); self->nodes[tn].link[1] = tx; \ + return tn; \ + } \ + STC_DEF CX \ + CX##_clone(CX tree) { \ + CX clone = CX##_with_capacity(_csmap_rep(&tree)->size); \ + CX##_size_t root = CX##_clone_r_(&clone, tree.nodes, (CX##_size_t) _csmap_rep(&tree)->root); \ + _csmap_rep(&clone)->root = root; \ + _csmap_rep(&clone)->size = _csmap_rep(&tree)->size; \ + return clone; \ + } \ +\ + STC_DEF void \ + CX##_del_r_(CX##_node_t* d, CX##_size_t tn) { \ + if (tn) { \ + CX##_del_r_(d, d[tn].link[0]); \ + CX##_del_r_(d, d[tn].link[1]); \ + CX##_value_del(&d[tn].value); \ + } \ + } \ + STC_DEF void \ + CX##_del(CX* self) { \ + if (_csmap_rep(self)->root) { \ + CX##_del_r_(self->nodes, (CX##_size_t) _csmap_rep(self)->root); \ + c_free(_csmap_rep(self)); \ + } \ + } + +#else +#define _c_implement_aatree(CX, C, Key, Mapped, keyCompareRaw, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + keyDel, keyFromRaw, keyToRaw, RawKey) +#endif + +#endif diff --git a/include/stc/csptr.h b/include/stc/csptr.h new file mode 100644 index 00000000..66ae5240 --- /dev/null +++ b/include/stc/csptr.h @@ -0,0 +1,164 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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 CSPTR_H_INCLUDED +#define CSPTR_H_INCLUDED + +#include "ccommon.h" + +/* csptr: std::shared_ptr -like type: + +#include +#include + +typedef struct { cstr name, last; } Person; + +Person* Person_make(Person* p, const char* name, const char* last) { + p->name = cstr_from(name), p->last = cstr_from(last); + return p; +} +void Person_del(Person* p) { + printf("del: %s\n", p->name.str); + c_del(cstr, &p->name, &p->last); +} + +using_csptr(pe, Person, c_no_compare, Person_del); + +int main() { + csptr_pe p = csptr_pe_from(Person_make(c_new(Person), "John", "Smiths")); + csptr_pe q = csptr_pe_clone(p); // share the pointer + + printf("%s %s. uses: %zu\n", q.get->name.str, q.get->last.str, *q.use_count); + c_del(csptr_pe, &p, &q); +} +*/ +typedef long atomic_count_t; +#if defined(__GNUC__) || defined(__clang__) + STC_INLINE void atomic_increment(atomic_count_t* pw) {__atomic_add_fetch(pw, 1, __ATOMIC_SEQ_CST);} + STC_INLINE atomic_count_t atomic_decrement(atomic_count_t* pw) {return __atomic_sub_fetch(pw, 1, __ATOMIC_SEQ_CST);} +#elif defined(_MSC_VER) + #include + STC_INLINE void atomic_increment(atomic_count_t* pw) {_InterlockedIncrement(pw);} + STC_INLINE atomic_count_t atomic_decrement(atomic_count_t* pw) {return _InterlockedDecrement(pw);} +#elif defined(__i386__) || defined(__x86_64__) + STC_INLINE void atomic_increment(atomic_count_t* pw) { + __asm__ ( + "lock\n\t" + "incl %0": + "=m"( *pw ): // ++*pw // output (%0) + "m"( *pw ): // input (%1) + "cc" // clobbers + ); + } + STC_INLINE atomic_count_t atomic_decrement(atomic_count_t* pw) { + int r; + __asm__ __volatile__ ( + "lock\n\t" + "xadd %1, %0": + "=m"( *pw ), "=r"( r ): // int r = *pw; // outputs (%0, %1) + "m"( *pw ), "1"( -1 ): // *pw += -1; // inputs (%2, %3 == %1) + "memory", "cc" // clobbers + ); + return r - 1; + } +#endif + +#define csptr_null {NULL, NULL} + +#define using_csptr(...) c_MACRO_OVERLOAD(using_csptr, __VA_ARGS__) + +#define using_csptr_2(X, Value) \ + using_csptr_3(X, Value, c_default_compare) +#define using_csptr_3(X, Value, valueCompare) \ + using_csptr_4(X, Value, valueCompare, c_default_del) +#define using_csptr_4(X, Value, valueCompare, valueDel) \ + _c_using_csptr(csptr_##X, Value, valueCompare, valueDel) + + +#define _c_using_csptr(CX, Value, valueCompare, valueDel) \ + typedef Value CX##_value_t; \ +\ + typedef struct { \ + CX##_value_t* get; \ + atomic_count_t* use_count; \ + } CX; \ +\ + STC_INLINE CX \ + CX##_from(CX##_value_t* p) { \ + CX ptr = {p}; \ + if (p) *(ptr.use_count = c_new(atomic_count_t)) = 1; \ + return ptr; \ + } \ +\ + STC_INLINE CX \ + CX##_make(CX##_value_t val) { \ + CX ptr = {c_new(CX##_value_t), c_new(atomic_count_t)}; \ + *ptr.get = val, *ptr.use_count = 1; return ptr; \ + } \ +\ + STC_INLINE CX \ + CX##_clone(CX ptr) { \ + if (ptr.use_count) atomic_increment(ptr.use_count); \ + return ptr; \ + } \ +\ + STC_INLINE CX \ + CX##_move(CX* self) { \ + CX ptr = *self; \ + self->get = NULL, self->use_count = NULL; \ + return ptr; \ + } \ +\ + STC_INLINE void \ + CX##_del(CX* self) { \ + if (self->use_count && atomic_decrement(self->use_count) == 0) { \ + valueDel(self->get); \ + c_free(self->use_count); \ + c_free(self->get); \ + } \ + } \ +\ + STC_INLINE void \ + CX##_reset(CX* self) { \ + CX##_del(self); \ + self->use_count = NULL, self->get = NULL; \ + } \ +\ + STC_INLINE CX##_value_t* \ + CX##_reset_with(CX* self, CX##_value_t* p) { \ + CX##_del(self); \ + *self = CX##_from(p); \ + return self->get; \ + } \ +\ + STC_INLINE int \ + CX##_compare(CX* x, CX* y) { \ + return valueCompare(x->get, y->get); \ + } \ +\ + STC_INLINE bool \ + CX##_equals(CX* x, CX* y) { \ + return valueCompare(x->get, y->get) == 0; \ + } \ + struct stc_trailing_semicolon + +#endif diff --git a/include/stc/csset.h b/include/stc/csset.h new file mode 100644 index 00000000..1218fb42 --- /dev/null +++ b/include/stc/csset.h @@ -0,0 +1,71 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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 CSSET_H_INCLUDED +#define CSSET_H_INCLUDED + +// Sorted set - implemented as an AA-tree (balanced binary tree). +/* +#include +#include + +using_csset(i, int); // sorted set of int + +int main(void) { + csset_i s = csset_i_init(); + csset_i_insert(&s, 5); + csset_i_insert(&s, 8); + csset_i_insert(&s, 3); + csset_i_insert(&s, 5); + + c_foreach (k, csset_i, s) + printf("set %d\n", *k.ref); + csset_i_del(&s); +} +*/ + +#include "csmap.h" + +#define using_csset(...) \ + c_MACRO_OVERLOAD(using_csset, __VA_ARGS__) + +#define using_csset_2(X, Key) \ + using_csset_3(X, Key, c_default_compare) +#define using_csset_3(X, Key, keyCompare) \ + using_csset_5(X, Key, keyCompare, c_default_del, c_default_fromraw) +#define using_csset_4(X, Key, keyCompare, keyDel) \ + using_csset_5(X, Key, keyCompare, keyDel, c_no_clone) +#define using_csset_5(X, Key, keyCompare, keyDel, keyClone) \ + using_csset_7(X, Key, keyCompare, keyDel, keyClone, c_default_toraw, Key) + +#define using_csset_7(X, Key, keyCompareRaw, keyDel, keyFromRaw, keyToRaw, RawKey) \ + _c_using_aatree(csset_##X, csset_, Key, Key, keyCompareRaw, \ + @@, @@, @@, void, keyDel, keyFromRaw, keyToRaw, RawKey) + +#define using_csset_str() \ + _c_using_aatree_strkey(str, csset_, cstr, @@, @@, @@, void) + +#define SET_ONLY_csset_(...) __VA_ARGS__ +#define MAP_ONLY_csset_(...) +#define KEY_REF_csset_(vp) (vp) + +#endif diff --git a/include/stc/cstack.h b/include/stc/cstack.h new file mode 100644 index 00000000..2184c89e --- /dev/null +++ b/include/stc/cstack.h @@ -0,0 +1,82 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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 CSTACK_H_INCLUDED +#define CSTACK_H_INCLUDED + +/* Stack adapter, default uses cvec. + + #include + #include + + using_cvec(i, int); + using_cstack(i, cvec_i); + + int main() { + c_with (cstack_i stack = cstack_i_init(), cstack_i_del(&stack)) + { + for (int i=0; i<100; ++i) + cstack_i_push(&stack, i*i); + + for (int i=0; i<90; ++i) + cstack_i_pop(&stack); + + printf("top: %d\n", *cstack_i_top(&stack)); + } + } +*/ +#include "cvec.h" + +#define using_cstack(X, ctype) \ + _c_using_cstack(cstack_##X, ctype) + +#define _c_using_cstack(CX, ctype) \ + typedef ctype CX; \ + typedef ctype##_value_t CX##_value_t; \ + typedef ctype##_rawvalue_t CX##_rawvalue_t; \ + typedef ctype##_iter_t CX##_iter_t; \ +\ + STC_INLINE CX CX##_init(void) {return ctype##_init();} \ + STC_INLINE CX CX##_clone(CX st) {return ctype##_clone(st);} \ + STC_INLINE CX##_value_t CX##_value_clone(CX##_value_t val) \ + {return ctype##_value_clone(val);} \ + STC_INLINE void CX##_clear(CX* self) {ctype##_clear(self);} \ + STC_INLINE void CX##_del(CX* self) {ctype##_del(self);} \ +\ + STC_INLINE size_t CX##_size(CX st) {return ctype##_size(st);} \ + STC_INLINE bool CX##_empty(CX st) {return ctype##_empty(st);} \ + STC_INLINE CX##_value_t* CX##_top(const CX* self) {return ctype##_back(self);} \ +\ + STC_INLINE void CX##_pop(CX* self) {ctype##_pop_back(self);} \ + STC_INLINE void CX##_push(CX* self, ctype##_value_t value) \ + {ctype##_push_back(self, value);} \ + STC_INLINE void CX##_emplace(CX* self, CX##_rawvalue_t raw) \ + {ctype##_emplace_back(self, raw);} \ + STC_INLINE void CX##_emplace_items(CX *self, const CX##_rawvalue_t arr[], size_t n) \ + {ctype##_emplace_items(self, arr, n);} \ +\ + STC_INLINE CX##_iter_t CX##_begin(const CX* self) {return ctype##_begin(self);} \ + STC_INLINE CX##_iter_t CX##_end(const CX* self) {return ctype##_end(self);} \ + STC_INLINE void CX##_next(CX##_iter_t* it) {ctype##_next(it);} \ + struct stc_trailing_semicolon + +#endif diff --git a/include/stc/cstr.h b/include/stc/cstr.h new file mode 100644 index 00000000..131a3d78 --- /dev/null +++ b/include/stc/cstr.h @@ -0,0 +1,412 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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 CSTR_H_INCLUDED +#define CSTR_H_INCLUDED + +#include "ccommon.h" +#include /* malloc */ +#include +#include +#include /* vsnprintf */ +#include + +typedef struct { char* str; } cstr; +typedef struct { char *ref; } cstr_iter_t; +typedef char cstr_value_t; + +#define cstr_npos ((size_t) (-1)) +STC_LIBRARY_ONLY( extern const cstr cstr_null; ) + +struct cstr_rep { size_t size, cap; char str[sizeof(size_t)]; }; +#define _cstr_rep(self) c_container_of((self)->str, struct cstr_rep, str) +STC_STATIC_ONLY( static struct cstr_rep _cstr_nullrep = {0, 0, {0}}; + static const cstr cstr_null = {_cstr_nullrep.str}; ) +typedef const char strlit_t[]; +/* optimal memory: based on malloc_usable_size() sequence: 24, 40, 56, ... */ +#define _cstr_opt_mem(cap) ((((offsetof(struct cstr_rep, str) + (cap) + 8)>>4)<<4) + 8) +/* optimal string capacity: 7, 23, 39, ... */ +#define _cstr_opt_cap(cap) (_cstr_opt_mem(cap) - offsetof(struct cstr_rep, str) - 1) + +STC_API cstr cstr_from_n(const char* str, size_t n); +STC_API cstr cstr_from_fmt(const char* fmt, ...); +STC_API size_t cstr_reserve(cstr* self, size_t cap); +STC_API void cstr_resize(cstr* self, size_t len, char fill); +STC_API cstr* cstr_assign_n(cstr* self, const char* str, size_t n); +STC_API cstr* cstr_assign_fmt(cstr* self, const char* fmt, ...); +STC_API cstr* cstr_append_n(cstr* self, const char* str, size_t n); +STC_API void cstr_replace_n(cstr* self, size_t pos, size_t len, const char* str, size_t n); +STC_API size_t cstr_replace_all(cstr* self, const char* find, const char* replace); +STC_API void cstr_erase_n(cstr* self, size_t pos, size_t n); +STC_API size_t cstr_find(cstr s, const char* needle); +STC_API size_t cstr_find_n(cstr s, const char* needle, size_t pos, size_t nmax); +STC_API size_t cstr_ifind_n(cstr s, const char* needle, size_t pos, size_t nmax); +STC_API bool cstr_getdelim(cstr *self, int delim, FILE *stream); +STC_API int c_strncasecmp(const char* s1, const char* s2, size_t nmax); +STC_API char* c_strnstrn(const char* s, const char* needle, size_t slen, size_t nmax); +STC_API char* c_strncasestrn(const char* s, const char* needle, size_t slen, size_t nmax); + +STC_INLINE cstr cstr_init() { return cstr_null; } +#define cstr_lit(literal) \ + cstr_from_n(literal, sizeof c_make(strlit_t){literal} - 1) +STC_INLINE cstr cstr_from(const char* str) + { return cstr_from_n(str, strlen(str)); } +STC_INLINE size_t cstr_size(cstr s) { return _cstr_rep(&s)->size; } +STC_INLINE size_t cstr_length(cstr s) { return _cstr_rep(&s)->size; } +STC_INLINE size_t cstr_capacity(cstr s) { return _cstr_rep(&s)->cap; } +STC_INLINE bool cstr_empty(cstr s) { return _cstr_rep(&s)->size == 0; } +STC_INLINE void cstr_del(cstr* self) + { if (_cstr_rep(self)->cap) c_free(_cstr_rep(self)); } +STC_INLINE cstr cstr_clone(cstr s) + { return cstr_from_n(s.str, _cstr_rep(&s)->size); } +STC_INLINE void cstr_clear(cstr* self) + { self->str[_cstr_rep(self)->size = 0] = '\0'; } +STC_INLINE cstr* cstr_assign(cstr* self, const char* str) + { return cstr_assign_n(self, str, strlen(str)); } +STC_INLINE cstr* cstr_copy(cstr* self, cstr s) + { return cstr_assign_n(self, s.str, _cstr_rep(&s)->size); } +STC_INLINE cstr* cstr_append(cstr* self, const char* str) + { return cstr_append_n(self, str, strlen(str)); } +STC_INLINE cstr* cstr_append_s(cstr* self, cstr s) + { return cstr_append_n(self, s.str, _cstr_rep(&s)->size); } +STC_INLINE void cstr_push_back(cstr* self, char value) + { cstr_append_n(self, &value, 1); } +STC_INLINE void cstr_pop_back(cstr* self) + { self->str[ --_cstr_rep(self)->size ] = '\0'; } +STC_INLINE void cstr_insert_n(cstr* self, size_t pos, const char* str, size_t n) + { cstr_replace_n(self, pos, 0, str, n); } +STC_INLINE void cstr_insert(cstr* self, size_t pos, const char* str) + { cstr_replace_n(self, pos, 0, str, strlen(str)); } +STC_INLINE void cstr_insert_s(cstr* self, size_t pos, cstr s) + { cstr_replace_n(self, pos, 0, s.str, _cstr_rep(&s)->size); } +STC_INLINE void cstr_replace(cstr* self, size_t pos, size_t len, const char* str) + { cstr_replace_n(self, pos, len, str, strlen(str)); } +STC_INLINE void cstr_replace_s(cstr* self, size_t pos, size_t len, cstr s) + { cstr_replace_n(self, pos, len, s.str, _cstr_rep(&s)->size); } +STC_INLINE void cstr_erase(cstr* self, size_t pos) + { cstr_erase_n(self, pos, 1); } +STC_INLINE char* cstr_front(cstr* self) { return self->str; } +STC_INLINE char* cstr_back(cstr* self) + { return self->str + _cstr_rep(self)->size - 1; } +STC_INLINE cstr_iter_t cstr_begin(cstr* self) + { return c_make(cstr_iter_t){self->str}; } +STC_INLINE cstr_iter_t cstr_end(cstr* self) + { return c_make(cstr_iter_t){self->str + _cstr_rep(self)->size}; } +STC_INLINE void cstr_next(cstr_iter_t* it) {++it->ref; } +STC_INLINE bool cstr_equals(cstr s, const char* str) + { return strcmp(s.str, str) == 0; } +STC_INLINE bool cstr_equals_s(cstr s1, cstr s2) + { return strcmp(s1.str, s2.str) == 0; } +STC_INLINE bool cstr_iequals(cstr s, const char* str) + { return c_strncasecmp(s.str, str, cstr_npos) == 0; } +STC_INLINE bool cstr_contains(cstr s, const char* needle) + { return strstr(s.str, needle) != NULL; } +STC_INLINE bool cstr_icontains(cstr s, const char* needle) + { return c_strncasestrn(s.str, needle, cstr_size(s), cstr_npos) != NULL; } +STC_INLINE bool cstr_getline(cstr *self, FILE *stream) + { return cstr_getdelim(self, '\n', stream); } + +STC_INLINE cstr +cstr_with_capacity(size_t cap) { + cstr s = cstr_null; + cstr_reserve(&s, cap); + return s; +} + +STC_INLINE cstr +cstr_with_size(size_t len, char fill) { + cstr s = cstr_null; + cstr_resize(&s, len, fill); + return s; +} + +STC_INLINE cstr* +cstr_take(cstr* self, cstr s) { + if (self->str != s.str && _cstr_rep(self)->cap) + c_free(_cstr_rep(self)); + self->str = s.str; + return self; +} + +STC_INLINE cstr +cstr_move(cstr* self) { + cstr tmp = *self; + *self = cstr_null; + return tmp; +} + +STC_INLINE bool +cstr_begins_with(cstr s, const char* sub) { + while (*sub && *s.str == *sub) ++s.str, ++sub; + return *sub == 0; +} + +STC_INLINE bool +cstr_ends_with(cstr s, const char* sub) { + size_t n = strlen(sub), sz = _cstr_rep(&s)->size; + return n <= sz ? memcmp(s.str + sz - n, sub, n) == 0 : false; +} + +STC_INLINE bool +cstr_ibegins_with(cstr s, const char* sub) { + while (*sub && tolower(*s.str) == tolower(*sub)) ++s.str, ++sub; + return *sub == 0; +} + +STC_INLINE bool +cstr_iends_with(cstr s, const char* sub) { + size_t n = strlen(sub), sz = _cstr_rep(&s)->size; + return n <= sz ? c_strncasecmp(s.str + sz - n, sub, n) == 0 : false; +} + +/* cvec/cmap adaption functions: */ +#define cstr_toraw(xp) ((xp)->str) +#define cstr_compare_ref(xp, yp) strcmp((xp)->str, (yp)->str) +#define cstr_equals_ref(xp, yp) (strcmp((xp)->str, (yp)->str) == 0) +#define cstr_hash_ref(xp, none) c_default_hash((xp)->str, cstr_size(*(xp))) +#define cstr_hash(x) c_default_hash((x).str, cstr_size(x)) + +/* -------------------------- IMPLEMENTATION ------------------------- */ + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) + +STC_LIBRARY_ONLY( static struct cstr_rep _cstr_nullrep = {0, 0, {0}}; + const cstr cstr_null = {_cstr_nullrep.str}; ) + +STC_DEF size_t +cstr_reserve(cstr* self, size_t cap) { + struct cstr_rep* rep = _cstr_rep(self); + size_t oldcap = rep->cap; + if (cap > oldcap) { + rep = (struct cstr_rep*) c_realloc(oldcap ? rep : NULL, _cstr_opt_mem(cap)); + self->str = rep->str; + if (oldcap == 0) self->str[rep->size = 0] = '\0'; + return (rep->cap = _cstr_opt_cap(cap)); + } + return oldcap; +} + +STC_DEF void +cstr_resize(cstr* self, size_t len, char fill) { + size_t n = _cstr_rep(self)->size; + cstr_reserve(self, len); + if (len > n) memset(self->str + n, fill, len - n); + if (len | n) self->str[_cstr_rep(self)->size = len] = '\0'; +} + +STC_DEF cstr +cstr_from_n(const char* str, size_t n) { + if (n == 0) return cstr_null; + struct cstr_rep* rep = (struct cstr_rep*) c_malloc(_cstr_opt_mem(n)); + cstr s = {(char *) memcpy(rep->str, str, n)}; + s.str[rep->size = n] = '\0'; + rep->cap = _cstr_opt_cap(n); + return s; +} + +#if defined(__clang__) +# pragma clang diagnostic push +# pragma clang diagnostic ignored "-Wdeprecated-declarations" +#elif defined(_MSC_VER) +# pragma warning(push) +# pragma warning(disable: 4996) +#endif + +STC_DEF void +cstr_vfmt(cstr* self, const char* fmt, va_list args) { + va_list args2; + va_copy(args2, args); + int len = vsnprintf(NULL, (size_t)0, fmt, args); + cstr_reserve(self, len); + vsprintf(self->str, fmt, args2); + va_end(args2); + _cstr_rep(self)->size = len; +} + +#if defined(__clang__) +# pragma clang diagnostic pop +#elif defined(_MSC_VER) +# pragma warning(pop) +#endif + +STC_DEF cstr +cstr_from_fmt(const char* fmt, ...) { + cstr ret = cstr_null; + va_list args; va_start(args, fmt); + cstr_vfmt(&ret, fmt, args); + va_end(args); + return ret; +} + +STC_DEF cstr* +cstr_assign_fmt(cstr* self, const char* fmt, ...) { + cstr ret = cstr_null; + va_list args; va_start(args, fmt); + cstr_vfmt(&ret, fmt, args); + va_end(args); + cstr_del(self); *self = ret; + return self; +} + +STC_DEF cstr* +cstr_assign_n(cstr* self, const char* str, size_t n) { + if (n || _cstr_rep(self)->cap) { + cstr_reserve(self, n); + memmove(self->str, str, n); + self->str[_cstr_rep(self)->size = n] = '\0'; + } + return self; +} + +STC_DEF cstr* +cstr_append_n(cstr* self, const char* str, size_t n) { + if (n == 0) return self; + size_t oldlen = _cstr_rep(self)->size, newlen = oldlen + n; + if (newlen > _cstr_rep(self)->cap) { + size_t off = (size_t) (str - self->str); /* handle self append */ + cstr_reserve(self, newlen*3/2); + if (off <= oldlen) str = self->str + off; + } + memcpy(&self->str[oldlen], str, n); + self->str[_cstr_rep(self)->size = newlen] = '\0'; + return self; +} + +STC_INLINE void _cstr_internal_move(cstr* self, size_t pos1, size_t pos2) { + if (pos1 == pos2) + return; + size_t len = _cstr_rep(self)->size, newlen = len + pos2 - pos1; + if (newlen > _cstr_rep(self)->cap) + cstr_reserve(self, newlen*3/2); + memmove(&self->str[pos2], &self->str[pos1], len - pos1); + self->str[_cstr_rep(self)->size = newlen] = '\0'; +} + +STC_DEF void +cstr_replace_n(cstr* self, size_t pos, size_t len, const char* str, size_t n) { + size_t sz = cstr_size(*self); + if (len > sz - pos) len = sz - pos; + c_withbuf (xstr, char, n) { + memcpy(xstr, str, n); + _cstr_internal_move(self, pos + len, pos + n); + memcpy(&self->str[pos], xstr, n); + } +} + +STC_DEF size_t +cstr_replace_all(cstr* self, const char* find, const char* replace) { + cstr out = cstr_null; + size_t find_len = strlen(find), repl_len = strlen(replace), from = 0, n = 0, pos; + while ((pos = cstr_find_n(*self, find, from, cstr_npos)) != cstr_npos) { + cstr_append_n(&out, self->str + from, pos - from ); + cstr_append_n(&out, replace, repl_len); + from = pos + find_len; ++n; + } + if (!n) return 0; + cstr_append_n(&out, self->str + from, cstr_size(*self) - from); + cstr_del(self); *self = out; + return n; +} + +STC_DEF void +cstr_erase_n(cstr* self, size_t pos, size_t n) { + size_t len = _cstr_rep(self)->size; + if (n > len - pos) n = len - pos; + if (len) { + memmove(&self->str[pos], &self->str[pos + n], len - (pos + n)); + self->str[_cstr_rep(self)->size -= n] = '\0'; + } +} + +STC_DEF bool +cstr_getdelim(cstr *self, int delim, FILE *fp) { + size_t pos = 0, cap = _cstr_rep(self)->cap; + int c = fgetc(fp); + if (c == EOF) + return false; + for (;;) { + if (pos == cap) + cap = cstr_reserve(self, cap*3/2 + 16); + if (c == delim || c == EOF) { + self->str[_cstr_rep(self)->size = pos] = '\0'; + return true; + } + self->str[pos++] = (char) c; + c = fgetc(fp); + } +} + +STC_DEF size_t +cstr_find(cstr s, const char* needle) { + char* res = strstr(s.str, needle); + return res ? res - s.str : cstr_npos; +} + +STC_DEF size_t +cstr_find_n(cstr s, const char* needle, size_t pos, size_t nmax) { + if (pos > _cstr_rep(&s)->size) return cstr_npos; + char* res = c_strnstrn(s.str + pos, needle, _cstr_rep(&s)->size - pos, nmax); + return res ? res - s.str : cstr_npos; +} + +STC_DEF size_t +cstr_ifind_n(cstr s, const char* needle, size_t pos, size_t nmax) { + if (pos > _cstr_rep(&s)->size) return cstr_npos; + char* res = c_strncasestrn(s.str + pos, needle, _cstr_rep(&s)->size - pos, nmax); + return res ? res - s.str : cstr_npos; +} + +STC_DEF int +c_strncasecmp(const char* s1, const char* s2, size_t nmax) { + int ret = 0; + while (nmax-- && (ret = tolower(*s1++) - tolower(*s2)) == 0 && *s2++) ; + return ret; +} + +STC_DEF char* +c_strnstrn(const char *s, const char *needle, size_t slen, size_t nmax) { + size_t n = strlen(needle); + if (nmax < n) n = nmax; + if (n > slen) return NULL; + slen -= n; + do { + if (*s == *needle && !memcmp(s, needle, n)) return (char *)s; + ++s; + } while (slen--); + return NULL; +} + +STC_DEF char* +c_strncasestrn(const char *s, const char *needle, size_t slen, size_t nmax) { + size_t n = strlen(needle); + if (nmax < n) n = nmax; + if (n > slen) return NULL; + int c = tolower(*needle); slen -= n; + do { + if (tolower(*s) == c && !c_strncasecmp(s, needle, n)) return (char *)s; + ++s; + } while (slen--); + return NULL; +} + +#endif +#endif \ No newline at end of file diff --git a/include/stc/csview.h b/include/stc/csview.h new file mode 100644 index 00000000..d4d3f65d --- /dev/null +++ b/include/stc/csview.h @@ -0,0 +1,161 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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 CSVIEW_H_INCLUDED +#define CSVIEW_H_INCLUDED + +#include "cstr.h" + +typedef struct { const char* str; size_t size; } csview; +typedef struct { const char *ref; } csview_iter_t; +typedef char csview_value_t; +#define csview_null c_make(csview){"", 0} +#define csview_ARG(sv) (int)(sv).size, (sv).str + +#define c_lit(literal) \ + csview_lit(literal) +STC_INLINE csview c_sv(cstr s) + { return c_make(csview){s.str, _cstr_rep(&s)->size}; } +STC_INLINE csview csview_from(const char* str) + { return c_make(csview){str, strlen(str)}; } +STC_INLINE csview csview_from_n(const char* str, size_t n) + { return c_make(csview){str, n}; } +#define csview_lit(literal) \ + c_make(csview){literal, sizeof c_make(strlit_t){literal} - 1} +STC_INLINE csview csview_from_s(cstr s) + { return c_make(csview){s.str, _cstr_rep(&s)->size}; } + +STC_INLINE csview csview_trimmed(csview sv, size_t left, size_t right) + { sv.str += left, sv.size -= left + right; return sv; } +STC_INLINE csview csview_trimmed_s(cstr s, size_t left, size_t right) + { return c_make(csview){s.str + left, _cstr_rep(&s)->size - right - left}; } + +STC_INLINE size_t csview_size(csview sv) { return sv.size; } +STC_INLINE size_t csview_length(csview sv) { return sv.size; } +STC_INLINE bool csview_empty(csview sv) { return sv.size == 0; } +STC_INLINE void csview_clear(csview* self) { *self = csview_null; } +STC_INLINE const char* csview_front(const csview* self) { return self->str; } +STC_INLINE const char* csview_back(const csview* self) { return self->str + self->size - 1; } + +STC_INLINE bool csview_equals(csview sv, csview sv2) + { return sv.size == sv2.size && !memcmp(sv.str, sv2.str, sv.size); } +STC_INLINE size_t csview_find(csview sv, csview needle) + { char* res = c_strnstrn(sv.str, needle.str, sv.size, needle.size); + return res ? res - sv.str : cstr_npos; } +STC_INLINE bool csview_contains(csview sv, csview needle) + { return c_strnstrn(sv.str, needle.str, sv.size, needle.size) != NULL; } +STC_INLINE bool csview_begins_with(csview sv, csview sub) + { if (sub.size > sv.size) return false; + return !memcmp(sv.str, sub.str, sub.size); } +STC_INLINE bool csview_ends_with(csview sv, csview sub) + { if (sub.size > sv.size) return false; + return !memcmp(sv.str + sv.size - sub.size, sub.str, sub.size); } +STC_INLINE csview_iter_t csview_begin(const csview* self) + { return c_make(csview_iter_t){self->str}; } +STC_INLINE csview_iter_t csview_end(const csview* self) + { return c_make(csview_iter_t){self->str + self->size}; } +STC_INLINE void csview_next(csview_iter_t* it) { ++it->ref; } + +/* cstr interaction with csview: */ + +STC_INLINE cstr cstr_from_v(csview sv) + { return cstr_from_n(sv.str, sv.size); } +STC_INLINE csview cstr_to_v(const cstr* self) + { return c_make(csview){self->str, _cstr_rep(self)->size}; } +STC_INLINE cstr* cstr_assign_v(cstr* self, csview sv) + { return cstr_assign_n(self, sv.str, sv.size); } +STC_INLINE cstr* cstr_append_v(cstr* self, csview sv) + { return cstr_append_n(self, sv.str, sv.size); } +STC_INLINE void cstr_insert_v(cstr* self, size_t pos, csview sv) + { cstr_replace_n(self, pos, 0, sv.str, sv.size); } +STC_INLINE void cstr_replace_v(cstr* self, size_t pos, size_t len, csview sv) + { cstr_replace_n(self, pos, len, sv.str, sv.size); } +STC_INLINE bool cstr_equals_v(cstr s, csview sv) + { return sv.size == cstr_size(s) && !memcmp(s.str, sv.str, sv.size); } +STC_INLINE size_t cstr_find_v(cstr s, csview needle) + { char* res = c_strnstrn(s.str, needle.str, cstr_size(s), needle.size); + return res ? res - s.str : cstr_npos; } +STC_INLINE bool cstr_contains_v(cstr s, csview needle) + { return c_strnstrn(s.str, needle.str, cstr_size(s), needle.size) != NULL; } +STC_INLINE bool cstr_begins_with_v(cstr s, csview sub) + { if (sub.size > cstr_size(s)) return false; + return !memcmp(s.str, sub.str, sub.size); } +STC_INLINE bool cstr_ends_with_v(cstr s, csview sub) + { if (sub.size > cstr_size(s)) return false; + return !memcmp(s.str + cstr_size(s) - sub.size, sub.str, sub.size); } + + +/* ---- Adaptor functions ---- */ + +#define csview_compare_ref(xp, yp) strcmp((xp)->str, (yp)->str) +STC_INLINE bool csview_equals_ref(const csview* a, const csview* b) + { return a->size == b->size && !memcmp(a->str, b->str, a->size); } +#define csview_hash_ref(xp, none) c_default_hash((xp)->str, (xp)->size) + +/* ---- Containers ---- */ + +#define using_cvec_sv() \ + using_cvec(sv, cstr, csview_compare_ref, cstr_del, cstr_from_v, cstr_to_v, csview) +#define using_cdeq_sv() \ + using_cdeq(sv, cstr, csview_compare_ref, cstr_del, cstr_from_v, cstr_to_v, csview) +#define using_clist_sv() \ + using_clist(sv, cstr, csview_compare_ref, cstr_del, cstr_from_v, cstr_to_v, csview) + + +#define using_csmap_svkey(...) c_MACRO_OVERLOAD(using_csmap_svkey, __VA_ARGS__) + +#define using_csmap_svkey_2(X, Mapped) \ + using_csmap_svkey_4(X, Mapped, c_default_del, c_default_fromraw) +#define using_csmap_svkey_3(X, Mapped, mappedDel) \ + using_csmap_svkey_4(X, Mapped, mappedDel, c_no_clone) +#define using_csmap_svkey_4(X, Mapped, mappedDel, mappedClone) \ + using_csmap_svkey_6(X, Mapped, mappedDel, mappedClone, c_default_toraw, Mapped) +#define using_csmap_svkey_6(X, Mapped, mappedDel, mappedFromRaw, mappedToRaw, RawMapped) \ + _c_using_aatree(csmap_##X, csmap_, cstr, Mapped, csview_compare_ref, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + cstr_del, cstr_from_v, cstr_to_v, csview) +#define using_csmap_sv() \ + using_csmap_svkey_6(sv, cstr, cstr_del, cstr_from_v, cstr_to_v, csview) +#define using_csset_sv() \ + _c_using_aatree(csset_sv, csset_, cstr, cstr, csview_compare_ref, \ + @@, @@, @@, void, cstr_del, cstr_from_v, cstr_to_v, csview) + + +#define using_cmap_svkey(...) c_MACRO_OVERLOAD(using_cmap_svkey, __VA_ARGS__) + +#define using_cmap_svkey_2(X, Mapped) \ + using_cmap_svkey_4(X, Mapped, c_default_del, c_default_fromraw) +#define using_cmap_svkey_3(X, Mapped, mappedDel) \ + using_cmap_svkey_4(X, Mapped, mappedDel, c_no_clone) +#define using_cmap_svkey_4(X, Mapped, mappedDel, mappedClone) \ + using_cmap_svkey_6(X, Mapped, mappedDel, mappedClone, c_default_toraw, Mapped) +#define using_cmap_svkey_6(X, Mapped, mappedDel, mappedFromRaw, mappedToRaw, RawMapped) \ + _c_using_chash(cmap_##X, cmap_, cstr, Mapped, csview_equals_ref, csview_hash_ref, \ + mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ + cstr_del, cstr_from_v, cstr_to_v, csview) +#define using_cmap_sv() \ + using_cmap_svkey_6(sv, cstr, cstr_del, cstr_from_v, cstr_to_v, csview) +#define using_cset_sv() \ + _c_using_chash(cset_sv, cset_, cstr, cstr, csview_equals_ref, csview_hash_ref, \ + @@, @@, @@, void, cstr_del, cstr_from_v, cstr_to_v, csview) + +#endif \ No newline at end of file diff --git a/include/stc/cvec.h b/include/stc/cvec.h new file mode 100644 index 00000000..dc090dae --- /dev/null +++ b/include/stc/cvec.h @@ -0,0 +1,345 @@ +/* MIT License + * + * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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 CVEC_H_INCLUDED +#define CVEC_H_INCLUDED + +#include "ccommon.h" +#include +#include + +#define using_cvec(...) c_MACRO_OVERLOAD(using_cvec, __VA_ARGS__) + +#define using_cvec_2(X, Value) \ + using_cvec_3(X, Value, c_default_compare) +#define using_cvec_3(X, Value, valueCompare) \ + using_cvec_5(X, Value, valueCompare, c_default_del, c_default_fromraw) +#define using_cvec_4(X, Value, valueCompare, valueDel) \ + using_cvec_5(X, Value, valueCompare, valueDel, c_no_clone) +#define using_cvec_5(X, Value, valueCompare, valueDel, valueClone) \ + using_cvec_7(X, Value, valueCompare, valueDel, valueClone, c_default_toraw, Value) +#define using_cvec_7(X, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) \ + _c_using_cvec(cvec_##X, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) + +#define using_cvec_str() \ + _c_using_cvec(cvec_str, cstr, c_rawstr_compare, cstr_del, cstr_from, cstr_toraw, const char*) + + +struct cvec_rep { size_t size, cap; void* data[]; }; +#define _cvec_rep(self) c_container_of((self)->data, struct cvec_rep, data) + + +#define _c_using_cvec(CX, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) \ +\ + typedef Value CX##_value_t; \ + typedef RawValue CX##_rawvalue_t; \ + typedef struct {CX##_value_t *ref;} CX##_iter_t; \ + typedef struct {CX##_value_t *data;} CX; \ +\ + STC_API CX CX##_init(void); \ + STC_API CX CX##_clone(CX cx); \ + STC_API void CX##_del(CX* self); \ + STC_API void CX##_clear(CX* self); \ + STC_API void CX##_reserve(CX* self, size_t cap); \ + STC_API void CX##_resize(CX* self, size_t size, Value fill_val); \ + STC_API int CX##_value_compare(const CX##_value_t* x, const CX##_value_t* y); \ + STC_API CX##_iter_t CX##_find_in(CX##_iter_t it1, CX##_iter_t it2, RawValue raw); \ + STC_API CX##_iter_t CX##_bsearch_in(CX##_iter_t it1, CX##_iter_t it2, RawValue raw); \ + STC_API void CX##_push_back(CX* self, Value value); \ + STC_API CX##_iter_t CX##_erase_range_p(CX* self, CX##_value_t* p1, CX##_value_t* p2); \ + STC_API CX##_iter_t CX##_insert_range_p(CX* self, CX##_value_t* pos, \ + const CX##_value_t* p1, const CX##_value_t* p2, bool clone); \ + STC_API CX##_iter_t CX##_emplace_range_p(CX* self, CX##_value_t* pos, \ + const CX##_rawvalue_t* p1, const CX##_rawvalue_t* p2); \ +\ + STC_INLINE size_t CX##_size(CX cx) { return _cvec_rep(&cx)->size; } \ + STC_INLINE size_t CX##_capacity(CX cx) { return _cvec_rep(&cx)->cap; } \ + STC_INLINE bool CX##_empty(CX cx) {return !_cvec_rep(&cx)->size;} \ + STC_INLINE Value CX##_value_fromraw(RawValue raw) {return valueFromRaw(raw);} \ + STC_INLINE void CX##_swap(CX* a, CX* b) {c_swap(CX, *a, *b);} \ + STC_INLINE CX##_value_t*CX##_front(const CX* self) {return self->data;} \ + STC_INLINE CX##_value_t*CX##_back(const CX* self) \ + {return self->data + _cvec_rep(self)->size - 1;} \ + STC_INLINE void CX##_emplace_back(CX* self, RawValue raw) \ + {CX##_push_back(self, valueFromRaw(raw));} \ + STC_INLINE void CX##_pop_back(CX* self) \ + {valueDel(&self->data[--_cvec_rep(self)->size]);} \ + STC_INLINE Value CX##_value_clone(CX##_value_t val) \ + {return valueFromRaw(valueToRaw(&val));} \ + STC_INLINE CX##_iter_t CX##_begin(const CX* self) \ + {return c_make(CX##_iter_t){self->data};} \ + STC_INLINE CX##_iter_t CX##_end(const CX* self) \ + {return c_make(CX##_iter_t){self->data + _cvec_rep(self)->size};} \ + STC_INLINE void CX##_next(CX##_iter_t* it) {++it->ref;} \ + STC_INLINE CX##_iter_t CX##_adv(CX##_iter_t it, intptr_t offs) {it.ref += offs; return it;} \ + STC_INLINE size_t CX##_idx(CX cx, CX##_iter_t it) {return it.ref - cx.data;} \ +\ + STC_INLINE CX \ + CX##_with_size(size_t size, Value null_val) { \ + CX cx = CX##_init(); \ + CX##_resize(&cx, size, null_val); \ + return cx; \ + } \ +\ + STC_INLINE CX \ + CX##_with_capacity(size_t size) { \ + CX cx = CX##_init(); \ + CX##_reserve(&cx, size); \ + return cx; \ + } \ +\ + STC_INLINE void \ + CX##_shrink_to_fit(CX *self) { \ + CX cx = CX##_clone(*self); \ + CX##_del(self); *self = cx; \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_insert(CX* self, size_t idx, Value value) { \ + return CX##_insert_range_p(self, self->data + idx, &value, &value + 1, false); \ + } \ + STC_INLINE CX##_iter_t \ + CX##_insert_n(CX* self, size_t idx, const CX##_value_t arr[], size_t n) { \ + return CX##_insert_range_p(self, self->data + idx, arr, arr + n, false); \ + } \ + STC_INLINE CX##_iter_t \ + CX##_insert_at(CX* self, CX##_iter_t it, Value value) { \ + return CX##_insert_range_p(self, it.ref, &value, &value + 1, false); \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_emplace(CX* self, size_t idx, RawValue raw) { \ + return CX##_emplace_range_p(self, self->data + idx, &raw, &raw + 1); \ + } \ + STC_INLINE CX##_iter_t \ + CX##_emplace_n(CX* self, size_t idx, const CX##_rawvalue_t arr[], size_t n) { \ + return CX##_emplace_range_p(self, self->data + idx, arr, arr + n); \ + } \ + STC_INLINE CX##_iter_t \ + CX##_emplace_at(CX* self, CX##_iter_t it, RawValue raw) { \ + return CX##_emplace_range_p(self, it.ref, &raw, &raw + 1); \ + } \ + STC_INLINE CX##_iter_t \ + CX##_emplace_range(CX* self, CX##_iter_t it, CX##_iter_t it1, CX##_iter_t it2) { \ + return CX##_insert_range_p(self, it.ref, it1.ref, it2.ref, true); \ + } \ + STC_INLINE void \ + CX##_emplace_items(CX *self, const CX##_rawvalue_t arr[], size_t n) { \ + CX##_emplace_range_p(self, self->data + _cvec_rep(self)->size, arr, arr + n); \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_erase(CX* self, size_t idx) { \ + return CX##_erase_range_p(self, self->data + idx, self->data + idx + 1); \ + } \ + STC_INLINE CX##_iter_t \ + CX##_erase_n(CX* self, size_t idx, size_t n) { \ + return CX##_erase_range_p(self, self->data + idx, self->data + idx + n); \ + } \ + STC_INLINE CX##_iter_t \ + CX##_erase_at(CX* self, CX##_iter_t it) { \ + return CX##_erase_range_p(self, it.ref, it.ref + 1); \ + } \ + STC_INLINE CX##_iter_t \ + CX##_erase_range(CX* self, CX##_iter_t it1, CX##_iter_t it2) { \ + return CX##_erase_range_p(self, it1.ref, it2.ref); \ + } \ +\ + STC_INLINE CX##_value_t* \ + CX##_at(const CX* self, size_t idx) { \ + assert(idx < _cvec_rep(self)->size); \ + return self->data + idx; \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_find(const CX* self, RawValue raw) { \ + return CX##_find_in(CX##_begin(self), CX##_end(self), raw); \ + } \ +\ + STC_INLINE CX##_value_t* \ + CX##_get(const CX* self, RawValue raw) { \ + CX##_iter_t end = CX##_end(self); \ + CX##_value_t* val = CX##_find_in(CX##_begin(self), end, raw).ref; \ + return val == end.ref ? NULL : val; \ + } \ +\ + STC_INLINE CX##_iter_t \ + CX##_bsearch(const CX* self, RawValue raw) { \ + return CX##_bsearch_in(CX##_begin(self), CX##_end(self), raw); \ + } \ + STC_INLINE void \ + CX##_sort_range(CX##_iter_t i1, CX##_iter_t i2, \ + int(*_cmp_)(const CX##_value_t*, const CX##_value_t*)) { \ + qsort(i1.ref, i2.ref - i1.ref, sizeof(CX##_value_t), (int(*)(const void*, const void*)) _cmp_); \ + } \ + STC_INLINE void \ + CX##_sort(CX* self) { \ + CX##_sort_range(CX##_begin(self), CX##_end(self), CX##_value_compare); \ + } \ +\ + _c_implement_cvec(CX, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) \ + struct stc_trailing_semicolon + +/* -------------------------- IMPLEMENTATION ------------------------- */ + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) +static struct cvec_rep _cvec_inits = {0, 0}; + +#define _c_implement_cvec(CX, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) \ +\ + STC_DEF CX \ + CX##_init(void) { \ + CX cx = {(CX##_value_t *) _cvec_inits.data}; \ + return cx; \ + } \ +\ + STC_DEF void \ + CX##_clear(CX* self) { \ + struct cvec_rep* rep = _cvec_rep(self); if (rep->cap) { \ + for (CX##_value_t *p = self->data, *q = p + rep->size; p != q; ++p) \ + valueDel(p); \ + rep->size = 0; \ + } \ + } \ +\ + STC_DEF void \ + CX##_del(CX* self) { \ + CX##_clear(self); \ + if (_cvec_rep(self)->cap) \ + c_free(_cvec_rep(self)); \ + } \ +\ + STC_DEF void \ + CX##_reserve(CX* self, size_t cap) { \ + struct cvec_rep* rep = _cvec_rep(self); \ + size_t len = rep->size, oldcap = rep->cap; \ + if (cap > oldcap) { \ + rep = (struct cvec_rep*) c_realloc(oldcap ? rep : NULL, \ + offsetof(struct cvec_rep, data) + cap*sizeof(Value)); \ + self->data = (CX##_value_t*) rep->data; \ + rep->size = len; \ + rep->cap = cap; \ + } \ + } \ +\ + STC_DEF void \ + CX##_resize(CX* self, size_t len, Value null_val) { \ + CX##_reserve(self, len); \ + struct cvec_rep* rep = _cvec_rep(self); \ + size_t i, n = rep->size; \ + for (i = len; i < n; ++i) valueDel(self->data + i); \ + for (i = n; i < len; ++i) self->data[i] = null_val; \ + if (rep->cap) rep->size = len; \ + } \ +\ + STC_DEF void \ + CX##_push_back(CX* self, Value value) { \ + size_t len = _cvec_rep(self)->size; \ + if (len == CX##_capacity(*self)) \ + CX##_reserve(self, 4 + len*1.5); \ + self->data[_cvec_rep(self)->size++] = value; \ + } \ +\ + STC_DEF CX \ + CX##_clone(CX cx) { \ + size_t len = _cvec_rep(&cx)->size; \ + CX out = CX##_with_capacity(len); \ + CX##_insert_range_p(&out, out.data, cx.data, cx.data + len, true); \ + return out; \ + } \ +\ + STC_DEF CX##_value_t* \ + CX##_insert_space_(CX* self, CX##_value_t* pos, size_t len) { \ + size_t idx = pos - self->data, size = _cvec_rep(self)->size; \ + if (len == 0) return pos; \ + if (size + len > CX##_capacity(*self)) \ + CX##_reserve(self, 4 + (size + len)*1.5), \ + pos = self->data + idx; \ + _cvec_rep(self)->size += len; \ + memmove(pos + len, pos, (size - idx) * sizeof(Value)); \ + return pos; \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_insert_range_p(CX* self, CX##_value_t* pos, const CX##_value_t* p1, \ + const CX##_value_t* p2, bool clone) { \ + pos = CX##_insert_space_(self, pos, p2 - p1); \ + CX##_iter_t it = {pos}; \ + if (clone) while (p1 != p2) *pos++ = valueFromRaw(valueToRaw(p1++)); \ + else memcpy(pos, p1, (p2 - p1)*sizeof *p1); \ + return it; \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_emplace_range_p(CX* self, CX##_value_t* pos, const CX##_rawvalue_t* p1, const CX##_rawvalue_t* p2) { \ + pos = CX##_insert_space_(self, pos, p2 - p1); \ + CX##_iter_t it = {pos}; \ + while (p1 != p2) *pos++ = valueFromRaw(*p1++); \ + return it; \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_erase_range_p(CX* self, CX##_value_t* p1, CX##_value_t* p2) { \ + intptr_t len = p2 - p1; \ + if (len > 0) { \ + CX##_value_t* p = p1, *end = self->data + _cvec_rep(self)->size; \ + while (p != p2) valueDel(p++); \ + memmove(p1, p2, (end - p2) * sizeof(Value)); \ + _cvec_rep(self)->size -= len; \ + } \ + return c_make(CX##_iter_t){.ref = p1}; \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_find_in(CX##_iter_t i1, CX##_iter_t i2, RawValue raw) { \ + for (; i1.ref != i2.ref; ++i1.ref) { \ + RawValue r = valueToRaw(i1.ref); \ + if (valueCompareRaw(&raw, &r) == 0) return i1; \ + } \ + return i2; \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_bsearch_in(CX##_iter_t i1, CX##_iter_t i2, RawValue raw) { \ + CX##_iter_t mid, last = i2; \ + while (i1.ref != i2.ref) { \ + mid.ref = i1.ref + ((i2.ref - i1.ref)>>1); \ + int c; RawValue m = valueToRaw(mid.ref); \ + if ((c = valueCompareRaw(&raw, &m)) == 0) return mid; \ + else if (c < 0) i2.ref = mid.ref; \ + else i1.ref = mid.ref + 1; \ + } \ + return last; \ + } \ +\ + STC_DEF int \ + CX##_value_compare(const CX##_value_t* x, const CX##_value_t* y) { \ + RawValue rx = valueToRaw(x); \ + RawValue ry = valueToRaw(y); \ + return valueCompareRaw(&rx, &ry); \ + } + +#else +#define _c_implement_cvec(CX, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) +#endif + +#endif \ No newline at end of file -- cgit v1.2.3