From 2bed88914afe24dc3a245f398b321e8f236d23d7 Mon Sep 17 00:00:00 2001 From: tylo Date: Fri, 17 Sep 2021 11:24:39 +0200 Subject: Moved tests and v1 files --- include/stc/alt/clist.h | 367 +++++++++++++++++++++++++++++++++++++++ include/stc/alt/csmap.h | 404 +++++++++++++++++++++++++++++++++++++++++++ include/stc/clist_v1.h | 367 --------------------------------------- include/stc/csmap_v1.h | 404 ------------------------------------------- include/stc/test_new_carr.c | 47 ----- include/stc/test_new_csptr.c | 45 ----- include/stc/test_new_deq.c | 57 ------ include/stc/test_new_list.c | 57 ------ include/stc/test_new_map.c | 60 ------- include/stc/test_new_pque.c | 63 ------- include/stc/test_new_queue.c | 43 ----- include/stc/test_new_smap.c | 67 ------- include/stc/test_new_vec.c | 57 ------ 13 files changed, 771 insertions(+), 1267 deletions(-) create mode 100644 include/stc/alt/clist.h create mode 100644 include/stc/alt/csmap.h delete mode 100644 include/stc/clist_v1.h delete mode 100644 include/stc/csmap_v1.h delete mode 100644 include/stc/test_new_carr.c delete mode 100644 include/stc/test_new_csptr.c delete mode 100644 include/stc/test_new_deq.c delete mode 100644 include/stc/test_new_list.c delete mode 100644 include/stc/test_new_map.c delete mode 100644 include/stc/test_new_pque.c delete mode 100644 include/stc/test_new_queue.c delete mode 100644 include/stc/test_new_smap.c delete mode 100644 include/stc/test_new_vec.c (limited to 'include') diff --git a/include/stc/alt/clist.h b/include/stc/alt/clist.h new file mode 100644 index 00000000..10d8092e --- /dev/null +++ b/include/stc/alt/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 + #include + #include + 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 +#include + + + +_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; ilast && 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/include/stc/alt/csmap.h b/include/stc/alt/csmap.h new file mode 100644 index 00000000..88c3967a --- /dev/null +++ b/include/stc/alt/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 +#include +using_csmap(mx, int, char); // Sorted map + +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 +#include +#include +#include + +#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; isecond = 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 diff --git a/include/stc/clist_v1.h b/include/stc/clist_v1.h deleted file mode 100644 index 10d8092e..00000000 --- a/include/stc/clist_v1.h +++ /dev/null @@ -1,367 +0,0 @@ -/* MIT License - * - * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in all - * copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ -#ifndef CLIST_H_INCLUDED -#define CLIST_H_INCLUDED - -/* Circular Singly-linked Lists. - - This implements a std::forward_list-like class in C, but because it is circular, - it also support push* and splice* at both ends of the list. This makes it ideal - for being used as a queue, unlike std::forward_list. Basic usage is similar to cvec: - - #include - #include - #include - using_clist(ix, int64_t); - - int main() { - 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 -#include - - - -_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; ilast && 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/include/stc/csmap_v1.h b/include/stc/csmap_v1.h deleted file mode 100644 index 88c3967a..00000000 --- a/include/stc/csmap_v1.h +++ /dev/null @@ -1,404 +0,0 @@ -/* MIT License - * - * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in all - * copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ -#ifndef CSMAP_H_INCLUDED -#define CSMAP_H_INCLUDED - -// Sorted/Ordered set and map - implemented as an AA-tree. -/* -#include -#include -using_csmap(mx, int, char); // Sorted map - -int main(void) { - c_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 -#include -#include -#include - -#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; isecond = 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 diff --git a/include/stc/test_new_carr.c b/include/stc/test_new_carr.c deleted file mode 100644 index 7513903f..00000000 --- a/include/stc/test_new_carr.c +++ /dev/null @@ -1,47 +0,0 @@ -#include - -#define i_tag i -#define i_val int -#include - -#define i_val int -#include -#include - -int main() -{ - int w = 7, h = 5, d = 3; - - c_forvar (carr2_i image = carr2_i_init(w, h), carr2_i_del(&image)) - { - int *dat = carr2_i_data(&image); - for (int i = 0; i < carr2_i_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(""); - - c_foreach (i, carr2_i, image) - printf(" %d", *i.ref); - } - puts("\n"); - - c_forvar (carr3_int image = carr3_int_init(w, h, d), carr3_int_del(&image)) - { - int *dat = carr3_int_data(&image); - for (int i = 0; i < carr3_int_size(image); ++i) - dat[i] = i; - - for (int x = 0; x < image.xdim; ++x) - for (int y = 0; y < image.ydim; ++y) - for (int z = 0; z < image.zdim; ++z) - printf(" %d", image.data[x][y][z]); - puts(""); - - c_foreach (i, carr3_int, image) - printf(" %d", *i.ref); - } - puts(""); -} diff --git a/include/stc/test_new_csptr.c b/include/stc/test_new_csptr.c deleted file mode 100644 index 2ef31790..00000000 --- a/include/stc/test_new_csptr.c +++ /dev/null @@ -1,45 +0,0 @@ -#include - -#include -forward_csptr(person, struct Person); - -struct Person { cstr name, last; } typedef Person; - -Person Person_init(const char* name, const char* last) { - return (Person){.name = cstr_from(name), .last = cstr_from(last)}; -} -void Person_del(Person* p) { - printf("del: %s %s\n", p->name.str, p->last.str); - c_del(cstr, &p->name, &p->last); -} - -#define F_tag person -#define i_val Person -#define i_valdel Person_del -#define i_cmp c_no_compare -#include - -#define i_val int -#include - -#define i_tag iptr -#define i_key csptr_int -#define i_cmp csptr_int_compare -#include - -int main(void) { - c_forvar (csptr_person p = csptr_person_make(Person_init("John", "Smiths")), csptr_person_del(&p)) - c_forvar (csptr_person q = csptr_person_clone(p), csptr_person_del(&q)) // share the pointer - { - printf("%s %s. uses: %zu\n", q.get->name.str, q.get->last.str, *q.use_count); - - c_forauto (csset_iptr, map) { - csset_iptr_insert(&map, csptr_int_make(2021)); - csset_iptr_insert(&map, csptr_int_make(2033)); - - c_foreach (i, csset_iptr, map) - printf(" %d", *i.ref->get); - puts(""); - } - } -} \ No newline at end of file diff --git a/include/stc/test_new_deq.c b/include/stc/test_new_deq.c deleted file mode 100644 index d1a5c2a6..00000000 --- a/include/stc/test_new_deq.c +++ /dev/null @@ -1,57 +0,0 @@ -#include -#include - -forward_cdeq(i32, int); -forward_cdeq(pnt, struct Point); - -struct MyStruct { - cdeq_i32 intvec; - cdeq_pnt pntvec; -} typedef MyStruct; - - -#define F_tag i32 -#define i_val int -#include - -struct Point { int x, y; } typedef Point; -int point_compare(const Point* a, const Point* b) { - int c = c_default_compare(&a->x, &b->x); - return c ? c : c_default_compare(&a->y, &b->y); -} -#define F_tag pnt -#define i_val Point -#define i_cmp point_compare -#include - -#define i_val float -#include - -#define i_val_str -#include - - -int main() -{ - cdeq_i32 vec = cdeq_i32_init(); - cdeq_i32_push_back(&vec, 123); - cdeq_i32_del(&vec); - - cdeq_float fvec = cdeq_float_init(); - cdeq_float_push_back(&fvec, 123.3); - cdeq_float_del(&fvec); - - cdeq_pnt pvec = cdeq_pnt_init(); - cdeq_pnt_push_back(&pvec, (Point){42, 14}); - cdeq_pnt_push_back(&pvec, (Point){32, 94}); - cdeq_pnt_push_front(&pvec, (Point){62, 81}); - cdeq_pnt_sort(&pvec); - c_foreach (i, cdeq_pnt, pvec) - printf(" (%d %d)", i.ref->x, i.ref->y); - puts(""); - cdeq_pnt_del(&pvec); - - cdeq_str svec = cdeq_str_init(); - cdeq_str_emplace_back(&svec, "Hello, friend"); - cdeq_str_del(&svec); -} \ No newline at end of file diff --git a/include/stc/test_new_list.c b/include/stc/test_new_list.c deleted file mode 100644 index f0983b76..00000000 --- a/include/stc/test_new_list.c +++ /dev/null @@ -1,57 +0,0 @@ -#include "cstr.h" -#include "forward.h" - -forward_clist(i32, int); -forward_clist(pnt, struct Point); - -struct MyStruct { - clist_i32 intlst; - clist_pnt pntlst; -} typedef MyStruct; - - -#define F_tag i32 -#define i_val int -#include "clist.h" - -struct Point { int x, y; } typedef Point; -int point_compare(const Point* a, const Point* b) { - int c = c_default_compare(&a->x, &b->x); - return c ? c : c_default_compare(&a->y, &b->y); -} -#define F_tag pnt -#define i_val Point -#define i_cmp point_compare -#include "clist.h" - -#define i_val float -#include "clist.h" - -#define i_val_str -#include "clist.h" - - -int main() -{ - clist_i32 lst = clist_i32_init(); - clist_i32_push_back(&lst, 123); - clist_i32_del(&lst); - - clist_float flst = clist_float_init(); - clist_float_push_back(&flst, 123.3); - clist_float_del(&flst); - - clist_pnt plst = clist_pnt_init(); - clist_pnt_push_back(&plst, (Point){42, 14}); - clist_pnt_push_back(&plst, (Point){32, 94}); - clist_pnt_push_back(&plst, (Point){62, 81}); - clist_pnt_sort(&plst); - c_foreach (i, clist_pnt, plst) - printf(" (%d %d)", i.ref->x, i.ref->y); - puts(""); - clist_pnt_del(&plst); - - clist_str slst = clist_str_init(); - clist_str_emplace_back(&slst, "Hello, friend"); - clist_str_del(&slst); -} \ No newline at end of file diff --git a/include/stc/test_new_map.c b/include/stc/test_new_map.c deleted file mode 100644 index 2c4ee3bb..00000000 --- a/include/stc/test_new_map.c +++ /dev/null @@ -1,60 +0,0 @@ -#include -#include - -forward_cmap(pnt, struct Point, int); - -struct MyStruct { - cmap_pnt pntmap; - cstr name; -} typedef MyStruct; - -// int => int map -#define i_key int -#define i_val int -#include - -// Point => int map -struct Point { int x, y; } typedef Point; -int point_compare(const Point* a, const Point* b) { - int c = c_default_compare(&a->x, &b->x); - return c ? c : c_default_compare(&a->y, &b->y); -} -#define F_tag pnt // F=forward declared -#define i_key Point -#define i_val int -#define i_cmp point_compare -#include - -// int => int map -#define i_key_str -#define i_val_str -#include - -// string set -#define i_key_str -#include - - -int main() -{ - cmap_int map = cmap_int_init(); - cmap_int_insert(&map, 123, 321); - cmap_int_del(&map); - - cmap_pnt pmap = cmap_pnt_init(); - cmap_pnt_insert(&pmap, (Point){42, 14}, 1); - cmap_pnt_insert(&pmap, (Point){32, 94}, 2); - cmap_pnt_insert(&pmap, (Point){62, 81}, 3); - c_foreach (i, cmap_pnt, pmap) - printf(" (%d,%d: %d)", i.ref->first.x, i.ref->first.y, i.ref->second); - puts(""); - cmap_pnt_del(&pmap); - - cmap_str smap = cmap_str_init(); - cmap_str_emplace(&smap, "Hello, friend", "this is the mapped value"); - cmap_str_del(&smap); - - cset_str sset = cset_str_init(); - cset_str_emplace(&sset, "Hello, friend"); - cset_str_del(&sset); -} \ No newline at end of file diff --git a/include/stc/test_new_pque.c b/include/stc/test_new_pque.c deleted file mode 100644 index b9750c44..00000000 --- a/include/stc/test_new_pque.c +++ /dev/null @@ -1,63 +0,0 @@ -#include - -forward_cpque(pnt, struct Point); - -struct MyStruct { - cpque_pnt priority_queue; - int id; -}; - -#define i_val int -#include "cstack.h" - -#define i_val int -#include "cpque.h" - -struct Point { int x, y; } typedef Point; - -int Point_cmp(const Point* a, const Point* b) { - int c = c_default_compare(&a->x, &b->x); - return c ? c : c_default_compare(&a->y, &b->y); -} -#define F_tag pnt // F: was forward declared. -#define i_val Point -#define i_cmp Point_cmp -#include "cpque.h" - -#include - -int main() -{ - cstack_int istk = cstack_int_init(); - cstack_int_push(&istk, 123); - cstack_int_push(&istk, 321); - // print - c_foreach (i, cstack_int, istk) - printf(" %d", *i.ref); - cstack_int_del(&istk); - puts(""); - - cpque_pnt pque = cpque_pnt_init(); - cpque_pnt_push(&pque, (Point){23, 80}); - cpque_pnt_push(&pque, (Point){12, 32}); - cpque_pnt_push(&pque, (Point){54, 74}); - cpque_pnt_push(&pque, (Point){12, 62}); - // print - while (!cpque_pnt_empty(pque)) { - cpque_pnt_value_t *v = cpque_pnt_top(&pque); - printf(" (%d,%d)", v->x, v->y); - cpque_pnt_pop(&pque); - } - // free - cpque_pnt_del(&pque); - puts(""); - - cpque_int ique = cpque_int_init(); - cpque_int_push(&ique, 123); - cpque_int_push(&ique, 321); - // print - for (int i=0; i -#include -#include - -forward_cqueue(pnt, struct Point); - -struct Point { int x, y; } typedef Point; -int point_compare(const Point* a, const Point* b) { - int c = c_default_compare(&a->x, &b->x); - return c ? c : c_default_compare(&a->y, &b->y); -} -#define F_tag pnt -#define i_val Point -#define i_cmp point_compare -#include - -#define i_val int -#include -#include - -int main() { - int n = 60000000; - stc64_t rng = stc64_init(time(NULL)); - stc64_uniform_t dist = stc64_uniform_init(0, n); - - c_forauto (cqueue_int, Q) - { - // Push eight million random numbers onto the queue. - for (int i=0; i0; --i) { - int r = stc64_uniform(&rng, &dist); - if (r & 1) - cqueue_int_push(&Q, r); - else - cqueue_int_pop(&Q); - } - printf("after: size %zu, capacity %zu\n", cqueue_int_size(Q), cqueue_int_capacity(Q)); - } -} \ No newline at end of file diff --git a/include/stc/test_new_smap.c b/include/stc/test_new_smap.c deleted file mode 100644 index 033749ce..00000000 --- a/include/stc/test_new_smap.c +++ /dev/null @@ -1,67 +0,0 @@ -#include -#include - -forward_csmap(pnt, struct Point, int); - -struct MyStruct { - csmap_pnt pntmap; - cstr name; -} typedef MyStruct; - -// int => int map -#define i_key int -#define i_val int -#include - -// Point => int map -struct Point { int x, y; } typedef Point; -int point_compare(const Point* a, const Point* b) { - int c = c_default_compare(&a->x, &b->x); - return c ? c : c_default_compare(&a->y, &b->y); -} - -#define i_fwd -#define i_tag pnt -#define i_key Point -#define i_val int -#define i_cmp point_compare -#include - -// int => int map -#define i_key_str -#define i_val_str -#include - -// string set -#define i_key_str -#include - - -int main() -{ - c_forauto (csmap_int, map) - csmap_int_insert(&map, 123, 321); - - c_forauto (csmap_pnt, pmap) { - csmap_pnt_insert(&pmap, (Point){42, 14}, 1); - csmap_pnt_insert(&pmap, (Point){32, 94}, 2); - csmap_pnt_insert(&pmap, (Point){62, 81}, 3); - c_foreach (i, csmap_pnt, pmap) - printf(" (%d,%d: %d)", i.ref->first.x, i.ref->first.y, i.ref->second); - puts(""); - } - - c_forauto (csmap_str, smap) { - csmap_str_emplace(&smap, "Hello, friend", "this is the mapped value"); - csmap_str_emplace(&smap, "The brown fox", "jumped"); - csmap_str_emplace(&smap, "This is the time", "for all good things"); - c_foreach (i, csmap_str, smap) - printf(" (%s: %s)\n", i.ref->first.str, i.ref->second.str); - } - - c_forauto (csset_str, sset) { - csset_str_emplace(&sset, "Hello, friend"); - csset_str_emplace(&sset, "Goodbye, foe"); - printf("Found? %s\n", csset_str_contains(&sset, "Hello, friend") ? "true" : "false"); - } -} \ No newline at end of file diff --git a/include/stc/test_new_vec.c b/include/stc/test_new_vec.c deleted file mode 100644 index ae1fd155..00000000 --- a/include/stc/test_new_vec.c +++ /dev/null @@ -1,57 +0,0 @@ -#include -#include - -forward_cvec(i32, int); -forward_cvec(pnt, struct Point); - -struct MyStruct { - cvec_i32 intvec; - cvec_pnt pntvec; -} typedef MyStruct; - - -#define F_tag i32 -#define i_val int -#include - -struct Point { int x, y; } typedef Point; -int point_compare(const Point* a, const Point* b) { - int c = c_default_compare(&a->x, &b->x); - return c ? c : c_default_compare(&a->y, &b->y); -} -#define F_tag pnt -#define i_val Point -#define i_cmp point_compare -#include - -#define i_val float -#include - -#define i_val_str -#include - - -int main() -{ - cvec_i32 vec = cvec_i32_init(); - cvec_i32_push_back(&vec, 123); - cvec_i32_del(&vec); - - cvec_float fvec = cvec_float_init(); - cvec_float_push_back(&fvec, 123.3); - cvec_float_del(&fvec); - - cvec_pnt pvec = cvec_pnt_init(); - cvec_pnt_push_back(&pvec, (Point){42, 14}); - cvec_pnt_push_back(&pvec, (Point){32, 94}); - cvec_pnt_push_back(&pvec, (Point){62, 81}); - cvec_pnt_sort(&pvec); - c_foreach (i, cvec_pnt, pvec) - printf(" (%d %d)", i.ref->x, i.ref->y); - puts(""); - cvec_pnt_del(&pvec); - - cvec_str svec = cvec_str_init(); - cvec_str_emplace_back(&svec, "Hello, friend"); - cvec_str_del(&svec); -} \ No newline at end of file -- cgit v1.2.3