diff options
| author | Tyge Løvset <[email protected]> | 2021-05-20 17:46:35 +0200 |
|---|---|---|
| committer | Tyge Løvset <[email protected]> | 2021-05-20 17:46:35 +0200 |
| commit | 0c64fe64f7fb3df211e87094962e1c2a9e08a6c8 (patch) | |
| tree | 2d659b26edebdd5a41635cc3a85ca36817bc4cf2 /include | |
| parent | 079aa69a085ddb478c15f20f6f0f4b0d790022b8 (diff) | |
| download | STC-modified-0c64fe64f7fb3df211e87094962e1c2a9e08a6c8.tar.gz STC-modified-0c64fe64f7fb3df211e87094962e1c2a9e08a6c8.zip | |
Moved stc folder into include folder.
Diffstat (limited to 'include')
| -rw-r--r-- | include/stc/carray.h | 218 | ||||
| -rw-r--r-- | include/stc/cbits.h | 230 | ||||
| -rw-r--r-- | include/stc/ccommon.h | 163 | ||||
| -rw-r--r-- | include/stc/cdeq.h | 359 | ||||
| -rw-r--r-- | include/stc/clist.h | 395 | ||||
| -rw-r--r-- | include/stc/cmap.h | 470 | ||||
| -rw-r--r-- | include/stc/cpque.h | 146 | ||||
| -rw-r--r-- | include/stc/cqueue.h | 93 | ||||
| -rw-r--r-- | include/stc/crandom.h | 149 | ||||
| -rw-r--r-- | include/stc/cset.h | 71 | ||||
| -rw-r--r-- | include/stc/csmap.h | 571 | ||||
| -rw-r--r-- | include/stc/csptr.h | 164 | ||||
| -rw-r--r-- | include/stc/csset.h | 71 | ||||
| -rw-r--r-- | include/stc/cstack.h | 82 | ||||
| -rw-r--r-- | include/stc/cstr.h | 412 | ||||
| -rw-r--r-- | include/stc/csview.h | 161 | ||||
| -rw-r--r-- | include/stc/cvec.h | 345 |
17 files changed, 4100 insertions, 0 deletions
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 <stdlib.h>
+/*
+// carray2 and carray3 - 2D and 3D dynamic arrays in one memory block with easy indexing.
+#include <stc/carray.h>
+#include <stdio.h>
+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 <stdio.h>
+#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 <stdlib.h>
+#include <string.h>
+#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; i<n; ++i) self->data64[i] = pattern;
+}
+
+STC_INLINE void cbits_flip_all(cbits *self) {
+ size_t n = (self->size + 63) >> 6;
+ for (size_t i=0; i<n; ++i) self->data64[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; i<n; ++i) self->data64[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; i<n; ++i) self->data64[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; i<n; ++i) self->data64[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 <intrin.h>
+ 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<set.size; ++i) if (str[i] == '1') cbits_set(&set, i);
+ return set;
+}
+STC_DEF char* cbits_to_str(cbits set, char* out, size_t start, intptr_t stop) {
+ size_t end = stop < 0 ? set.size : stop;
+ for (size_t i=start; i<end; ++i) out[i] = cbits_test(set, i) ? '1' : '0';
+ out[end] = '\0'; return out;
+}
+STC_DEF cbits cbits_clone(cbits other) {
+ size_t bytes = ((other.size + 63) >> 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 <stdint.h>
+#include <stddef.h>
+#include <stdbool.h>
+#include <assert.h>
+
+#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<T*>(c_malloc(sizeof(T)))
+#define c_new_n(T, n) static_cast<T*>(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 <intrin.h>
+ #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 <stdlib.h>
+#include <string.h>
+
+#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 <stdio.h>
+ #include <stc/clist.h>
+ #include <stc/crandom.h>
+ 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 <stdlib.h>
+
+#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; i<n; ++i) CX##_push_back(self, valueFromRaw(arr[i])); \
+ } \
+\
+ STC_DEF CX##_iter_t \
+ CX##_insert(CX* self, CX##_iter_t it, Value value) { \
+ CX##_node_t* node = it.ref ? it.prev : self->last; \
+ _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 <stc/cmap.h>
+#include <stdio.h>
+
+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 <stdlib.h>
+#include <string.h>
+
+#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; i<n; ++i) SET_ONLY_##C( CX##_emplace(self, arr[i]); ) \
+ MAP_ONLY_##C( CX##_emplace(self, arr[i].first, arr[i].second); ) \
+ } \
+\
+ STC_INLINE CX##_result_t \
+ CX##_insert(CX* self, Key _key MAP_ONLY_##C(, Mapped _mapped)) { \
+ CX##_result_t _res = CX##_insert_entry_(self, keyToRaw(&_key)); \
+ if (_res.inserted) {*(CX##_key_t*) KEY_REF_##C(_res.ref) = _key; MAP_ONLY_##C( _res.ref->second = _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 <stc/crandom.h>
+ #include <stc/cpque.h>
+ 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 <stc/crandom.h>
+ #include <stc/cqueue.h>
+ 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; i<n; ++i)
+ cqueue_i_push(&queue, stc64_uniform(&dist));
+
+ // Push or pop on the queue ten million times
+ printf("%d\n", n);
+ for (int i=n; i>0; --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 <string.h>
+#include <math.h>
+
+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 <stc/cset.h>
+#include <stdio.h>
+
+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 <stdio.h>
+#include <stc/csmap.h>
+using_csmap(mx, int, char); // Sorted map<int, char>
+
+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 <stdlib.h>
+#include <string.h>
+
+#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; i<n; ++i) SET_ONLY_##C( CX##_emplace(self, arr[i]); ) \
+ MAP_ONLY_##C( CX##_emplace(self, arr[i].first, arr[i].second); ) \
+ } \
+\
+ STC_INLINE CX##_result_t \
+ CX##_insert(CX* self, Key key MAP_ONLY_##C(, Mapped mapped)) { \
+ CX##_result_t res = CX##_insert_entry_(self, keyToRaw(&key)); \
+ if (res.inserted) {*(CX##_key_t*) KEY_REF_##C(res.ref) = key; MAP_ONLY_##C( res.ref->second = 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 <stc/csptr.h>
+#include <stc/cstr.h>
+
+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 <intrin.h>
+ 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 <stc/csset.h>
+#include <stdio.h>
+
+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 <stc/cstack.h>
+ #include <stdio.h>
+
+ 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 <stdlib.h> /* malloc */
+#include <string.h>
+#include <stdarg.h>
+#include <stdio.h> /* vsnprintf */
+#include <ctype.h>
+
+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 <stdlib.h>
+#include <string.h>
+
+#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 |