diff options
| author | Tyge Løvset <[email protected]> | 2021-09-19 09:54:47 +0200 |
|---|---|---|
| committer | Tyge Løvset <[email protected]> | 2021-09-19 09:54:47 +0200 |
| commit | cf212f7cdeec662def0c3b99be6f73638419962f (patch) | |
| tree | 94f707daa7aa49f3250606d517896431cc596b25 /benchmarks | |
| parent | 9ddc57529865a54bf964702034ff41f938e8538a (diff) | |
| download | STC-modified-cf212f7cdeec662def0c3b99be6f73638419962f.tar.gz STC-modified-cf212f7cdeec662def0c3b99be6f73638419962f.zip | |
Preparation for merging in V2.0 to master branch.
Diffstat (limited to 'benchmarks')
| -rw-r--r-- | benchmarks/others/old/clist.h | 367 | ||||
| -rw-r--r-- | benchmarks/others/old/csmap.h | 404 |
2 files changed, 771 insertions, 0 deletions
diff --git a/benchmarks/others/old/clist.h b/benchmarks/others/old/clist.h new file mode 100644 index 00000000..10d8092e --- /dev/null +++ b/benchmarks/others/old/clist.h @@ -0,0 +1,367 @@ +/* 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() {
+ clist_ix list = clist_ix_init();
+ 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);
+ clist_ix_del(&list);
+ }
+*/
+#include <stc/ccommon.h>
+#include <stdlib.h>
+
+
+
+_c_clist_types(clist_VOID, int);
+STC_API size_t _clist_count(const clist_VOID* self);
+#define _clist_node(Self, vp) c_container_of(vp, cx_node_t, value)
+
+#define _c_using_clist(Self, i_val, i_cmp, i_valdel, i_valfrom, i_valto, i_valraw, defTypes) \
+\
+ defTypes( _c_clist_types(Self, i_val); ) \
+ typedef i_valraw cx_rawvalue_t; \
+\
+ STC_API Self cx_memb(_clone)(Self lst); \
+ STC_API void cx_memb(_del)(Self* self); \
+ STC_API void cx_memb(_push_back)(Self* self, i_val value); \
+ STC_API void cx_memb(_push_front)(Self* self, i_val value); \
+ STC_API void cx_memb(_emplace_items)(Self *self, const cx_rawvalue_t arr[], size_t n); \
+ STC_API Self cx_memb(_split_after)(Self* self, cx_iter_t pos1, cx_iter_t pos2); \
+ STC_API void cx_memb(_splice_after)(Self* self, cx_iter_t pos, Self* other); \
+ STC_DEF void cx_memb(_splice_after_range)(Self* self, cx_iter_t pos, Self* other, cx_iter_t i1, cx_iter_t i2); \
+ STC_API cx_iter_t cx_memb(_find)(const Self* self, i_valraw val); \
+ STC_API cx_iter_t cx_memb(_find_before)(const Self* self, i_valraw val); \
+ STC_API cx_iter_t cx_memb(_find_before_in)(cx_iter_t it1, cx_iter_t it2, i_valraw val); \
+ STC_API void cx_memb(_sort)(Self* self); \
+ STC_API size_t cx_memb(_remove)(Self* self, i_valraw val); \
+ STC_API cx_iter_t cx_memb(_insert_after)(Self* self, cx_iter_t pos, i_val value); \
+ STC_API cx_iter_t cx_memb(_erase_after)(Self* self, cx_iter_t pos); \
+ STC_API cx_iter_t cx_memb(_erase_range_after)(Self* self, cx_iter_t pos, cx_iter_t it2); \
+ STC_API cx_node_t* cx_memb(_erase_after_)(Self* self, cx_node_t* node); \
+\
+ STC_INLINE Self cx_memb(_init)(void) {Self lst = {NULL}; return lst; } \
+ STC_INLINE bool cx_memb(_empty)(Self lst) { return lst.last == NULL; } \
+ STC_INLINE size_t cx_memb(_count)(Self lst) { return _clist_count((const clist_VOID*) &lst); } \
+ STC_INLINE i_val cx_memb(_value_fromraw)(i_valraw raw) { return i_valfrom(raw); } \
+ STC_INLINE i_val cx_memb(_value_clone)(i_val val) { return i_valfrom(i_valto(&val)); } \
+ STC_INLINE void cx_memb(_clear)(Self* self) { cx_memb(_del)(self); } \
+ STC_INLINE void cx_memb(_emplace_back)(Self* self, i_valraw raw) \
+ { cx_memb(_push_back)(self, i_valfrom(raw)); } \
+ STC_INLINE void cx_memb(_emplace_front)(Self* self, i_valraw raw) \
+ { cx_memb(_push_front)(self, i_valfrom(raw)); } \
+ STC_INLINE cx_value_t* \
+ cx_memb(_front)(const Self* self) { return &self->last->next->value; } \
+ STC_INLINE cx_value_t* \
+ cx_memb(_back)(const Self* self) { return &self->last->value; } \
+ STC_INLINE void cx_memb(_pop_front)(Self* self) { cx_memb(_erase_after_)(self, self->last); } \
+ STC_INLINE void cx_memb(_splice_front)(Self* self, Self* other) \
+ { cx_memb(_splice_after)(self, cx_memb(_before_begin)(self), other); } \
+ STC_INLINE void cx_memb(_splice_back)(Self* self, Self* other) \
+ { cx_memb(_splice_after)(self, cx_memb(_last)(self), other); } \
+\
+ STC_INLINE cx_iter_t \
+ cx_memb(_emplace_after)(Self* self, cx_iter_t pos, i_valraw raw) { \
+ return cx_memb(_insert_after)(self, pos, i_valfrom(raw)); \
+ } \
+\
+ STC_INLINE cx_iter_t \
+ cx_memb(_before_begin)(const Self* self) { \
+ cx_value_t *last = self->last ? &self->last->value : NULL; \
+ cx_iter_t it = {&self->last, last, -1}; return it; \
+ } \
+\
+ STC_INLINE cx_iter_t \
+ cx_memb(_begin)(const Self* self) { \
+ cx_value_t* head = self->last ? &self->last->next->value : NULL; \
+ cx_iter_t it = {&self->last, head, 0}; return it; \
+ } \
+\
+ STC_INLINE cx_iter_t \
+ cx_memb(_last)(const Self* self) { \
+ cx_value_t *last = self->last ? &self->last->value : NULL; \
+ cx_iter_t it = {&self->last, last, 0}; return it; \
+ } \
+\
+ STC_INLINE cx_iter_t \
+ cx_memb(_end)(const Self* self) { \
+ cx_iter_t it = {NULL, NULL}; return it; \
+ } \
+\
+ STC_INLINE void \
+ cx_memb(_next)(cx_iter_t* it) { \
+ cx_node_t* node = _clist_node(Self, it->ref); \
+ it->ref = ((it->_state += node == *it->_last) == 1) ? NULL : &node->next->value; \
+ } \
+\
+ STC_INLINE cx_iter_t \
+ cx_memb(_advance)(cx_iter_t it, size_t n) { \
+ while (n-- && it.ref) cx_memb(_next)(&it); return it; \
+ } \
+ \
+ _c_implement_clist(Self, i_val, i_cmp, i_valdel, i_valfrom, i_valto, i_valraw) \
+ struct stc_trailing_semicolon
+
+/* -------------------------- IMPLEMENTATION ------------------------- */
+
+#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION)
+#define _c_implement_clist(Self, i_val, i_cmp, i_valdel, i_valfrom, i_valto, i_valraw) \
+\
+ STC_DEF Self \
+ cx_memb(_clone)(Self lst) { \
+ Self out = cx_memb(_init)(); \
+ c_foreach_3 (i, Self, lst) \
+ cx_memb(_emplace_back)(&out, i_valto(i.ref)); \
+ return out; \
+ } \
+\
+ STC_DEF void \
+ cx_memb(_del)(Self* self) { \
+ while (self->last) cx_memb(_erase_after_)(self, self->last); \
+ } \
+\
+ STC_DEF void \
+ cx_memb(_push_back)(Self* self, i_val value) { \
+ _c_clist_insert_after(self, Self, self->last, value); \
+ self->last = entry; \
+ } \
+ STC_DEF void \
+ cx_memb(_push_front)(Self* self, i_val value) { \
+ _c_clist_insert_after(self, Self, self->last, value); \
+ if (!self->last) self->last = entry; \
+ } \
+\
+ STC_DEF void \
+ cx_memb(_emplace_items)(Self *self, const cx_rawvalue_t arr[], size_t n) { \
+ for (size_t i=0; i<n; ++i) cx_memb(_push_back)(self, i_valfrom(arr[i])); \
+ } \
+\
+ STC_DEF cx_iter_t \
+ cx_memb(_insert_after)(Self* self, cx_iter_t pos, i_val value) { \
+ cx_node_t* node = pos.ref ? _clist_node(Self, pos.ref) : NULL; \
+ _c_clist_insert_after(self, Self, node, value); \
+ if (!node || node == self->last && pos._state == 0) self->last = entry; \
+ pos.ref = &entry->value, pos._state = 0; return pos; \
+ } \
+\
+ STC_DEF cx_iter_t \
+ cx_memb(_erase_after)(Self* self, cx_iter_t pos) { \
+ cx_memb(_erase_after_)(self, _clist_node(Self, pos.ref)); \
+ cx_memb(_next)(&pos); return pos; \
+ } \
+\
+ STC_DEF cx_iter_t \
+ cx_memb(_erase_range_after)(Self* self, cx_iter_t it1, cx_iter_t it2) { \
+ cx_node_t* node = _clist_node(Self, it1.ref), *done = it2.ref ? _clist_node(Self, it2.ref) : NULL; \
+ while (node && node->next != done) \
+ node = cx_memb(_erase_after_)(self, node); \
+ cx_memb(_next)(&it1); return it1; \
+ } \
+\
+ STC_DEF cx_iter_t \
+ cx_memb(_find_before_in)(cx_iter_t it1, cx_iter_t it2, i_valraw val) { \
+ cx_iter_t i = it1; \
+ for (cx_memb(_next)(&i); i.ref != it2.ref; cx_memb(_next)(&i)) { \
+ i_valraw r = i_valto(i.ref); \
+ if (i_cmp(&r, &val) == 0) return it1; \
+ it1 = i; \
+ } \
+ it1.ref = NULL; return it1; \
+ } \
+\
+ STC_DEF cx_iter_t \
+ cx_memb(_find_before)(const Self* self, i_valraw val) { \
+ cx_iter_t it = cx_memb(_find_before_in)(cx_memb(_before_begin)(self), cx_memb(_end)(self), val); \
+ return it; \
+ } \
+\
+ STC_DEF cx_iter_t \
+ cx_memb(_find)(const Self* self, i_valraw val) { \
+ cx_iter_t it = cx_memb(_find_before_in)(cx_memb(_before_begin)(self), cx_memb(_end)(self), val); \
+ if (it.ref != cx_memb(_end)(self).ref) cx_memb(_next)(&it); \
+ return it; \
+ } \
+\
+ STC_DEF cx_node_t* \
+ cx_memb(_erase_after_)(Self* 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; \
+ i_valdel(&del->value); c_free(del); \
+ return node; \
+ } \
+\
+ STC_DEF size_t \
+ cx_memb(_remove)(Self* self, i_valraw val) { \
+ size_t n = 0; \
+ cx_node_t* prev = self->last, *node; \
+ while (prev) { \
+ node = prev->next; \
+ i_valraw r = i_valto(&node->value); \
+ if (i_cmp(&r, &val) == 0) \
+ prev = cx_memb(_erase_after_)(self, prev), ++n; \
+ else \
+ prev = (node == self->last ? NULL : node); \
+ } \
+ return n; \
+ } \
+\
+ STC_DEF Self \
+ cx_memb(_split_after)(Self* self, cx_iter_t pos1, cx_iter_t pos2) { \
+ cx_node_t *node1 = _clist_node(Self, pos1.ref), *next1 = node1->next, \
+ *node2 = _clist_node(Self, pos2.ref); \
+ node1->next = node2->next, node2->next = next1; \
+ if (self->last == node2) self->last = node1; \
+ Self lst = {node2}; return lst; \
+ } \
+\
+ STC_DEF void \
+ cx_memb(_splice_after)(Self* self, cx_iter_t pos, Self* other) { \
+ if (!pos.ref) \
+ self->last = other->last; \
+ else if (other->last) { \
+ cx_node_t *node = _clist_node(Self, pos.ref), *next = node->next; \
+ node->next = other->last->next; \
+ other->last->next = next; \
+ if (node == self->last && pos._state == 0) self->last = other->last; \
+ } \
+ other->last = NULL; \
+ } \
+\
+ STC_DEF void \
+ cx_memb(_splice_after_range)(Self* self, cx_iter_t pos, Self* other, cx_iter_t pos1, cx_iter_t pos2) { \
+ Self tmp = cx_memb(_split_after)(other, pos1, pos2); \
+ cx_memb(_splice_after)(self, pos, &tmp); \
+ } \
+\
+ STC_DEF int \
+ cx_memb(_sort_cmp_)(const void* x, const void* y) { \
+ i_valraw a = i_valto(&((cx_node_t *) x)->value); \
+ i_valraw b = i_valto(&((cx_node_t *) y)->value); \
+ return i_cmp(&a, &b); \
+ } \
+\
+ STC_DEF void \
+ cx_memb(_sort)(Self* self) { \
+ if (self->last) \
+ self->last = (cx_node_t *) _clist_mergesort((clist_VOID_node_t *) self->last->next, cx_memb(_sort_cmp_)); \
+ }
+
+
+#define _c_clist_insert_after(self, Self, 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 *nd = self->last;
+ if (!nd) return 0;
+ size_t n = 1;
+ while ((nd = nd->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 void*, const void*)) {
+ 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(Self, i_val, i_cmp, i_valdel, i_valfrom, i_valto, i_valraw)
+#endif
+
+#endif
diff --git a/benchmarks/others/old/csmap.h b/benchmarks/others/old/csmap.h new file mode 100644 index 00000000..88c3967a --- /dev/null +++ b/benchmarks/others/old/csmap.h @@ -0,0 +1,404 @@ +/* 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_forvar (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 <stc/ccommon.h>
+#include <stc/template.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define KEY_REF_csmap_(vp) (&(vp)->first)
+#define _c_aatree_complete_types(Self, C) \
+ cx_MAP_ONLY( struct cx_value_t { \
+ cx_key_t first; \
+ cx_mapped_t second; \
+ }; ) \
+ struct cx_node_t { \
+ struct cx_node_t *link[2]; \
+ uint8_t level; \
+ cx_value_t value; \
+ }
+
+#ifndef cx_forwarded
+ _c_aatree_types(Self, C, i_key, i_val);
+#endif
+
+ _c_aatree_complete_types(Self, C); \
+\
+ typedef i_keyraw cx_rawkey_t; \
+ typedef i_valraw cx_memb(_rawmapped_t); \
+ typedef cx_SET_ONLY( cx_rawkey_t ) \
+ cx_MAP_ONLY( struct { cx_rawkey_t first; \
+ cx_memb(_rawmapped_t) second; } ) \
+ cx_rawvalue_t; \
+\
+ STC_API Self cx_memb(_init)(void); \
+ STC_API cx_value_t* cx_memb(_find_it)(const Self* self, i_keyraw rkey, cx_iter_t* out); \
+ STC_API cx_iter_t cx_memb(_lower_bound)(const Self* self, i_keyraw rkey); \
+ STC_API cx_value_t* cx_memb(_front)(const Self* self); \
+ STC_API cx_value_t* cx_memb(_back)(const Self* self); \
+ STC_API cx_iter_t cx_memb(_erase_at)(Self* self, cx_iter_t it); \
+ STC_API cx_iter_t cx_memb(_erase_range)(Self* self, cx_iter_t it1, cx_iter_t it2); \
+ STC_API cx_node_t* cx_memb(_erase_r_)(cx_node_t *tn, const cx_rawkey_t* rkey, int *erased); \
+ STC_API void cx_memb(_del_r_)(cx_node_t* tn); \
+ STC_API cx_node_t* cx_memb(_clone_r_)(cx_node_t *tn); \
+ STC_API cx_result_t cx_memb(_insert_entry_)(Self* self, i_keyraw rkey); \
+ STC_API void cx_memb(_next)(cx_iter_t* it); \
+\
+ STC_INLINE bool cx_memb(_empty)(Self cx) { return cx.size == 0; } \
+ STC_INLINE size_t cx_memb(_size)(Self cx) { return cx.size; } \
+ STC_INLINE void cx_memb(_del)(Self* self) { cx_memb(_del_r_)(self->root); } \
+ STC_INLINE void cx_memb(_clear)(Self* self) { cx_memb(_del)(self); *self = cx_memb(_init)(); } \
+ STC_INLINE void cx_memb(_swap)(Self* a, Self* b) {c_swap(Self, *a, *b); } \
+ STC_INLINE Self cx_memb(_clone)(Self cx) { return c_make(Self){ cx_memb(_clone_r_)(cx.root), cx.size}; } \
+ STC_INLINE cx_iter_t cx_memb(_find)(const Self* self, i_keyraw rkey) \
+ {cx_iter_t it; cx_memb(_find_it)(self, rkey, &it); return it; } \
+ STC_INLINE bool cx_memb(_contains)(const Self* self, i_keyraw rkey) \
+ {cx_iter_t it; return cx_memb(_find_it)(self, rkey, &it) != NULL; } \
+ STC_INLINE cx_value_t* cx_memb(_get)(const Self* self, i_keyraw rkey) \
+ {cx_iter_t it; return cx_memb(_find_it)(self, rkey, &it); } \
+\
+ STC_INLINE void \
+ cx_memb(_value_del)(cx_value_t* val) { \
+ i_keydel(cx_keyref(val)); \
+ cx_MAP_ONLY( i_valdel(&val->second); ) \
+ } \
+\
+ STC_INLINE void \
+ cx_memb(_value_clone)(cx_value_t* dst, cx_value_t* val) { \
+ *cx_keyref(dst) = i_keyfrom(i_keyto(cx_keyref(val))); \
+ cx_MAP_ONLY( dst->second = i_valfrom(i_valto(&val->second)); ) \
+ } \
+\
+ STC_INLINE cx_result_t \
+ cx_memb(_emplace)(Self* self, i_keyraw rkey cx_MAP_ONLY(, i_valraw rmapped)) { \
+ cx_result_t res = cx_memb(_insert_entry_)(self, rkey); \
+ if (res.inserted) { \
+ *cx_keyref(res.ref) = i_keyfrom(rkey); \
+ cx_MAP_ONLY(res.ref->second = i_valfrom(rmapped);) \
+ } \
+ return res; \
+ } \
+\
+ STC_INLINE void \
+ cx_memb(_emplace_items)(Self* self, const cx_rawvalue_t arr[], size_t n) { \
+ for (size_t i=0; i<n; ++i) cx_SET_ONLY( cx_memb(_emplace)(self, arr[i]); ) \
+ cx_MAP_ONLY( cx_memb(_emplace)(self, arr[i].first, arr[i].second); ) \
+ } \
+\
+ STC_INLINE cx_result_t \
+ cx_memb(_insert)(Self* self, i_key key cx_MAP_ONLY(, i_val mapped)) { \
+ cx_result_t res = cx_memb(_insert_entry_)(self, i_keyto(&key)); \
+ if (res.inserted) {*cx_keyref(res.ref) = key; cx_MAP_ONLY( res.ref->second = mapped; )} \
+ else {i_keydel(&key); cx_MAP_ONLY( i_valdel(&mapped); )} \
+ return res; \
+ } \
+\
+ cx_MAP_ONLY( \
+ STC_INLINE cx_result_t \
+ cx_memb(_insert_or_assign)(Self* self, i_key key, i_val mapped) { \
+ cx_result_t res = cx_memb(_insert_entry_)(self, i_keyto(&key)); \
+ if (res.inserted) res.ref->first = key; \
+ else {i_keydel(&key); i_valdel(&res.ref->second); } \
+ res.ref->second = mapped; return res; \
+ } \
+ \
+ STC_INLINE cx_result_t \
+ cx_memb(_put)(Self* self, i_key key, i_val mapped) { \
+ return cx_memb(_insert_or_assign)(self, key, mapped); \
+ } \
+ \
+ STC_INLINE cx_result_t \
+ cx_memb(_emplace_or_assign)(Self* self, i_keyraw rkey, i_valraw rmapped) { \
+ cx_result_t res = cx_memb(_insert_entry_)(self, rkey); \
+ if (res.inserted) res.ref->first = i_keyfrom(rkey); \
+ else i_valdel(&res.ref->second); \
+ res.ref->second = i_valfrom(rmapped); return res; \
+ } \
+ \
+ STC_INLINE cx_mapped_t* \
+ cx_memb(_at)(const Self* self, i_keyraw rkey) { \
+ cx_iter_t it; \
+ return &cx_memb(_find_it)(self, rkey, &it)->second; \
+ }) \
+\
+ STC_INLINE cx_iter_t \
+ cx_memb(_begin)(const Self* self) { \
+ cx_iter_t it = {NULL, 0, self->root}; \
+ cx_memb(_next)(&it); return it; \
+ } \
+\
+ STC_INLINE cx_iter_t \
+ cx_memb(_end)(const Self* self) {\
+ cx_iter_t it = {NULL}; return it; \
+ } \
+\
+ STC_INLINE size_t \
+ cx_memb(_erase)(Self* self, i_keyraw rkey) { \
+ int erased = 0; \
+ self->root = cx_memb(_erase_r_)(self->root, &rkey, &erased); \
+ self->size -= erased; return erased; \
+ } \
+\
+ STC_INLINE cx_iter_t \
+ cx_memb(_advance)(cx_iter_t it, size_t n) { \
+ while (n-- && it.ref) cx_memb(_next)(&it); \
+ return it; \
+ } \
+\
+ _c_implement_aatree(Self, C, i_key, i_val, i_cmp, \
+ i_valdel, i_valfrom, i_valto, i_valraw, \
+ i_keydel, i_keyfrom, i_keyto, i_keyraw) \
+ struct stc_trailing_semicolon
+
+/* -------------------------- IMPLEMENTATION ------------------------- */
+
+#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION)
+
+_c_aatree_types(csmap_SENTINEL, csmap_, int, int);
+_c_aatree_complete_types(csmap_SENTINEL, csmap_);
+static csmap_SENTINEL_node_t _aatree_sentinel = {&_aatree_sentinel, &_aatree_sentinel, 0};
+
+#define _c_implement_aatree(Self, C, i_key, i_val, i_cmp, \
+ i_valdel, i_valfrom, i_valto, i_valraw, \
+ i_keydel, i_keyfrom, i_keyto, i_keyraw) \
+ STC_DEF Self \
+ cx_memb(_init)(void) { \
+ Self cx = {(cx_node_t *) &_aatree_sentinel, 0}; \
+ return cx; \
+ } \
+\
+ STC_DEF cx_value_t* \
+ cx_memb(_front)(const Self* self) { \
+ cx_node_t *tn = self->root; \
+ while (tn->link[0]->level) tn = tn->link[0]; \
+ return &tn->value; \
+ } \
+\
+ STC_DEF cx_value_t* \
+ cx_memb(_back)(const Self* self) { \
+ cx_node_t *tn = self->root; \
+ while (tn->link[1]->level) tn = tn->link[1]; \
+ return &tn->value; \
+ } \
+\
+ STC_DEF cx_value_t* \
+ cx_memb(_find_it)(const Self* self, cx_rawkey_t rkey, cx_iter_t* out) { \
+ cx_node_t *tn = self->root; \
+ out->_top = 0; \
+ while (tn->level) { \
+ int c; cx_rawkey_t rx = i_keyto(cx_keyref(&tn->value)); \
+ if ((c = i_cmp(&rx, &rkey)) < 0) tn = tn->link[1]; \
+ else if (c > 0) {out->_st[out->_top++] = tn; tn = tn->link[0]; } \
+ else {out->_tn = tn->link[1]; return (out->ref = &tn->value); } \
+ } \
+ return (out->ref = NULL); \
+ } \
+\
+ STC_DEF cx_iter_t \
+ cx_memb(_lower_bound)(const Self* self, i_keyraw rkey) { \
+ cx_iter_t it; \
+ cx_memb(_find_it)(self, rkey, &it); \
+ if (!it.ref && it._top) { \
+ cx_node_t *tn = it._st[--it._top]; \
+ it._tn = tn->link[1]; \
+ it.ref = &tn->value; \
+ } \
+ return it; \
+ } \
+\
+ STC_DEF void \
+ cx_memb(_next)(cx_iter_t *it) { \
+ cx_node_t *tn = it->_tn; \
+ if (it->_top || tn->level) { \
+ while (tn->level) { \
+ it->_st[it->_top++] = tn; \
+ tn = tn->link[0]; \
+ } \
+ tn = it->_st[--it->_top]; \
+ it->_tn = tn->link[1]; \
+ it->ref = &tn->value; \
+ } else \
+ it->ref = NULL; \
+ } \
+\
+ static cx_node_t * \
+ cx_memb(_skew_)(cx_node_t *tn) { \
+ if (tn && tn->link[0]->level == tn->level && tn->level) { \
+ cx_node_t *tmp = tn->link[0]; \
+ tn->link[0] = tmp->link[1]; \
+ tmp->link[1] = tn; \
+ tn = tmp; \
+ } \
+ return tn; \
+ } \
+\
+ static cx_node_t * \
+ cx_memb(_split_)(cx_node_t *tn) { \
+ if (tn->link[1]->link[1]->level == tn->level && tn->level) { \
+ cx_node_t *tmp = tn->link[1]; \
+ tn->link[1] = tmp->link[0]; \
+ tmp->link[0] = tn; \
+ tn = tmp; \
+ ++tn->level; \
+ } \
+ return tn; \
+ } \
+\
+ static inline cx_node_t* \
+ cx_memb(_insert_entry_i_)(cx_node_t* tn, const cx_rawkey_t* rkey, cx_result_t* res) { \
+ cx_node_t *up[64], *tx = tn; \
+ int c, top = 0, dir = 0; \
+ while (tx->level) { \
+ up[top++] = tx; \
+ cx_rawkey_t r = i_keyto(cx_keyref(&tx->value)); \
+ if (!(c = i_cmp(&r, rkey))) {res->ref = &tx->value; return tn; } \
+ tx = tx->link[(dir = (c < 0))]; \
+ } \
+ tn = c_new(cx_node_t); \
+ res->ref = &tn->value, res->inserted = true; \
+ tn->link[0] = tn->link[1] = (cx_node_t*) &_aatree_sentinel, tn->level = 1; \
+ if (top == 0) return tn; \
+ up[top - 1]->link[dir] = tn; \
+ while (top--) { \
+ if (top) dir = (up[top - 1]->link[1] == up[top]); \
+ up[top] = cx_memb(_skew_)(up[top]); \
+ up[top] = cx_memb(_split_)(up[top]); \
+ if (top) up[top - 1]->link[dir] = up[top]; \
+ } \
+ return up[0]; \
+ } \
+\
+ STC_DEF cx_result_t \
+ cx_memb(_insert_entry_)(Self* self, i_keyraw rkey) { \
+ cx_result_t res = {NULL, false}; \
+ self->root = cx_memb(_insert_entry_i_)(self->root, &rkey, &res); \
+ self->size += res.inserted; \
+ return res; \
+ } \
+\
+ STC_DEF cx_node_t* \
+ cx_memb(_erase_r_)(cx_node_t *tn, const cx_rawkey_t* rkey, int *erased) { \
+ if (tn->level == 0) \
+ return tn; \
+ cx_rawkey_t raw = i_keyto(cx_keyref(&tn->value)); \
+ cx_node_t *tx; int c = i_cmp(&raw, rkey); \
+ if (c != 0) \
+ tn->link[c < 0] = cx_memb(_erase_r_)(tn->link[c < 0], rkey, erased); \
+ else { \
+ if (!*erased) { cx_memb(_value_del)(&tn->value); *erased = 1; } \
+ if (tn->link[0]->level && tn->link[1]->level) { \
+ tx = tn->link[0]; \
+ while (tx->link[1]->level) \
+ tx = tx->link[1]; \
+ tn->value = tx->value; \
+ raw = i_keyto(cx_keyref(&tn->value)); \
+ tn->link[0] = cx_memb(_erase_r_)(tn->link[0], &raw, erased); \
+ } else { \
+ tx = tn; \
+ tn = tn->link[tn->link[0]->level == 0]; \
+ c_free(tx); \
+ } \
+ } \
+ if (tn->link[0]->level < tn->level - 1 || tn->link[1]->level < tn->level - 1) { \
+ if (tn->link[1]->level > --tn->level) \
+ tn->link[1]->level = tn->level; \
+ tn = cx_memb(_skew_)(tn); \
+ tx = tn->link[0] = cx_memb(_skew_)(tn->link[0]); \
+ tx->link[0] = cx_memb(_skew_)(tx->link[0]); \
+ tn = cx_memb(_split_)(tn); \
+ tn->link[0] = cx_memb(_split_)(tn->link[0]); \
+ } \
+ return tn; \
+ } \
+ STC_DEF cx_iter_t \
+ cx_memb(_erase_at)(Self* self, cx_iter_t it) { \
+ cx_rawkey_t raw = i_keyto(cx_keyref(it.ref)), nxt; \
+ cx_memb(_next)(&it); \
+ if (it.ref) nxt = i_keyto(cx_keyref(it.ref)); \
+ cx_memb(_erase)(self, raw); \
+ if (it.ref) cx_memb(_find_it)(self, nxt, &it); \
+ return it; \
+ } \
+\
+ STC_DEF cx_iter_t \
+ cx_memb(_erase_range)(Self* self, cx_iter_t it1, cx_iter_t it2) { \
+ if (!it2.ref) { while (it1.ref) it1 = cx_memb(_erase_at)(self, it1); \
+ return it1; } \
+ cx_key_t k1 = *cx_keyref(it1.ref), k2 = *cx_keyref(it2.ref); \
+ cx_rawkey_t r1 = i_keyto(&k1); \
+ for (;;) { \
+ if (memcmp(&k1, &k2, sizeof k1) == 0) return it1; \
+ cx_memb(_next)(&it1); k1 = *cx_keyref(it1.ref); \
+ cx_memb(_erase)(self, r1); \
+ cx_memb(_find_it)(self, (r1 = i_keyto(&k1)), &it1); \
+ } \
+ } \
+\
+ STC_DEF cx_node_t* \
+ cx_memb(_clone_r_)(cx_node_t *tn) { \
+ if (! tn->level) return tn; \
+ cx_node_t *cn = c_new(cx_node_t); \
+ cn->link[0] = cx_memb(_clone_r_)(tn->link[0]); \
+ cn->link[1] = cx_memb(_clone_r_)(tn->link[1]); \
+ cn->level = tn->level; \
+ cx_memb(_value_clone)(&cn->value, &tn->value); \
+ return cn; \
+ } \
+\
+ STC_DEF void \
+ cx_memb(_del_r_)(cx_node_t* tn) { \
+ if (tn->level != 0) { \
+ cx_memb(_del_r_)(tn->link[0]); \
+ cx_memb(_del_r_)(tn->link[1]); \
+ cx_memb(_value_del)(&tn->value); \
+ c_free(tn); \
+ } \
+ }
+
+#endif
+#endif
|