From 939da174859515952108c49c206884d378704b11 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 2 Apr 2021 16:04:55 +0200 Subject: Rewrote clist API: Now in line with std::list API instead of std::forward_list, but still same single linked list rep. Weaker iterator validity, see updated docs. --- README.md | 21 ++- benchmarks/others/clist_v1.h | 416 +++++++++++++++++++++++++++++++++++++++++++ docs/clist_api.md | 119 +++++++------ examples/demos.c | 19 +- examples/list.c | 8 +- examples/list_erase.c | 12 +- stc/clist.h | 156 +++++++--------- 7 files changed, 580 insertions(+), 171 deletions(-) create mode 100644 benchmarks/others/clist_v1.h diff --git a/README.md b/README.md index d27771d7..82ed4e49 100644 --- a/README.md +++ b/README.md @@ -120,16 +120,16 @@ int main(void) { cset_i_iter_t i1 = cset_i_find(&set, 20); cvec_p_iter_t i2 = cvec_p_find(&vec, (struct Point) {20, 2}); cdeq_i_iter_t i3 = cdeq_i_find(&deq, 20); - clist_i_iter_t i4 = clist_i_find_before(&lst, 20); + clist_i_iter_t i4 = clist_i_find(&lst, 20); csmap_i_iter_t i5 = csmap_i_find(&map, 20); printf("\nFound: %d, (%g, %g), %d, %d, [%d: %d]\n", *i1.ref, i2.ref->x, i2.ref->y, - *i3.ref, *clist_i_fwd(i4, 1).ref, + *i3.ref, *i4.ref, i5.ref->first, i5.ref->second); // erase the elements found cset_i_erase_at(&set, i1); cvec_p_erase_at(&vec, i2); cdeq_i_erase_at(&deq, i3); - clist_i_erase_after(&lst, i4); + clist_i_erase_at(&lst, i4); csmap_i_erase_at(&map, i5); printf("After erasing elements found:"); @@ -191,14 +191,13 @@ with **emplace**, e.g. **cvec_X_emplace_back()**. This is a convenient alternati **cvec_X_push_back()** when dealing non-trivial container elements, e.g. smart pointers or elements using dynamic memory. -| Move and insert element | Construct element in-place | Container | -|:--------------------------|:-----------------------------|:-------------------------| -| insert() | emplace() | cmap, cset, csmap, csset | -| insert_or_assign(), put() | emplace_or_assign() | cmap, csmap | -| push() | emplace() | cstack, cqueue, cpque | -| push_back() | emplace_back() | cvec, cdeq, clist | -| push_front() | emplace_front() | cdeq, clist | -| insert_after() | emplace_after() | clist | +| Move and insert element | Construct element in-place | Container | +|:--------------------------|:-----------------------------|:--------------------------------| +| insert() | emplace() | cmap, cset, csmap, csset, clist | +| insert_or_assign(), put() | emplace_or_assign() | cmap, csmap | +| push() | emplace() | cstack, cqueue, cpque | +| push_back() | emplace_back() | cvec, cdeq, clist | +| push_front() | emplace_front() | cdeq, clist | For containers of integral or trivial element types, **emplace** and corresponding non-emplace methods are identical, so the following does not apply for those. diff --git a/benchmarks/others/clist_v1.h b/benchmarks/others/clist_v1.h new file mode 100644 index 00000000..ae70dacf --- /dev/null +++ b/benchmarks/others/clist_v1.h @@ -0,0 +1,416 @@ +/* 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 "ccommon.h" +#include + +#define using_clist(...) c_MACRO_OVERLOAD(using_clist, __VA_ARGS__) +#define using_clist_2(X, Value) \ + using_clist_3(X, Value, c_default_compare) +#define using_clist_3(X, Value, valueCompare) \ + using_clist_5(X, Value, valueCompare, c_trivial_del, c_trivial_fromraw) +#define using_clist_4(X, Value, valueCompare, valueDel) \ + using_clist_5(X, Value, valueCompare, valueDel, c_no_clone) +#define using_clist_5(X, Value, valueCompare, valueDel, valueClone) \ + using_clist_7(X, Value, valueCompare, valueDel, valueClone, c_trivial_toraw, Value) +#define using_clist_str() \ + using_clist_7(str, cstr_t, cstr_compare_raw, cstr_del, cstr_from, cstr_c_str, const char*) + +#define using_clist_types(X, Value) \ + typedef Value clist_##X##_value_t; \ +\ + typedef struct clist_##X##_node { \ + struct clist_##X##_node* next; \ + clist_##X##_value_t value; \ + } clist_##X##_node_t; \ +\ + typedef struct { \ + clist_##X##_node_t* last; \ + } clist_##X; \ +\ + typedef struct { \ + clist_##X##_node_t* const* _last; \ + clist_##X##_value_t* ref; \ + int _state; \ + } clist_##X##_iter_t + + +using_clist_types(void, int); +STC_API size_t _clist_size(const clist_void* self); +#define _clist_node(X, vp) c_container_of(vp, clist_##X##_node_t, value) + +#define using_clist_7(X, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) \ +\ + using_clist_types(X, Value); \ + typedef RawValue clist_##X##_rawvalue_t; \ +\ + STC_INLINE clist_##X \ + clist_##X##_init(void) {clist_##X x = {NULL}; return x;} \ + STC_INLINE bool \ + clist_##X##_empty(clist_##X ls) {return ls.last == NULL;} \ + STC_INLINE size_t \ + clist_##X##_size(clist_##X ls) {return _clist_size((const clist_void*) &ls);} \ + STC_INLINE Value \ + clist_##X##_value_fromraw(RawValue raw) {return valueFromRaw(raw);} \ + STC_INLINE clist_##X##_value_t \ + clist_##X##_value_clone(clist_##X##_value_t val) {return valueFromRaw(valueToRaw(&val));} \ +\ + STC_API void \ + clist_##X##_del(clist_##X* self); \ + STC_API clist_##X \ + clist_##X##_clone(clist_##X list); \ + STC_INLINE void \ + clist_##X##_clear(clist_##X* self) {clist_##X##_del(self);} \ +\ + STC_API void \ + clist_##X##_emplace_n(clist_##X *self, const clist_##X##_rawvalue_t arr[], size_t size); \ + STC_API void \ + clist_##X##_push_back(clist_##X* self, Value value); \ + STC_INLINE void \ + clist_##X##_emplace_back(clist_##X* self, RawValue raw) { \ + clist_##X##_push_back(self, valueFromRaw(raw)); \ + } \ + STC_API void \ + clist_##X##_push_front(clist_##X* self, Value value); \ + STC_INLINE void \ + clist_##X##_emplace_front(clist_##X* self, RawValue raw) { \ + clist_##X##_push_front(self, valueFromRaw(raw)); \ + } \ +\ + STC_API clist_##X##_node_t* \ + _clist_##X##_erase_after(clist_##X* self, clist_##X##_node_t* node); \ + STC_INLINE void \ + clist_##X##_pop_front(clist_##X* self) { \ + _clist_##X##_erase_after(self, self->last); \ + } \ + STC_INLINE clist_##X##_iter_t \ + clist_##X##_before_begin(const clist_##X* self) { \ + clist_##X##_value_t *last = self->last ? &self->last->value : NULL; \ + clist_##X##_iter_t it = {&self->last, last, -1}; return it; \ + } \ + STC_INLINE clist_##X##_iter_t \ + clist_##X##_begin(const clist_##X* self) { \ + clist_##X##_value_t* head = self->last ? &self->last->next->value : NULL; \ + clist_##X##_iter_t it = {&self->last, head, 0}; return it; \ + } \ + STC_INLINE clist_##X##_iter_t \ + clist_##X##_last(const clist_##X* self) { \ + clist_##X##_value_t *last = self->last ? &self->last->value : NULL; \ + clist_##X##_iter_t it = {&self->last, last, 0}; return it; \ + } \ + STC_INLINE clist_##X##_iter_t \ + clist_##X##_end(const clist_##X* self) { \ + clist_##X##_iter_t it = {NULL, NULL}; return it; \ + } \ + STC_INLINE void \ + clist_##X##_next(clist_##X##_iter_t* it) { \ + clist_##X##_node_t* node = _clist_node(X, it->ref); \ + it->ref = ((it->_state += node == *it->_last) == 1) ? NULL : &node->next->value; \ + } \ + STC_INLINE clist_##X##_iter_t \ + clist_##X##_fwd(clist_##X##_iter_t it, size_t n) { \ + while (n-- && it.ref) clist_##X##_next(&it); return it; \ + } \ + STC_INLINE clist_##X##_value_t* \ + clist_##X##_itval(clist_##X##_iter_t it) {return it.ref;} \ + \ + STC_API clist_##X##_iter_t \ + clist_##X##_insert_after(clist_##X* self, clist_##X##_iter_t pos, Value value); \ + STC_INLINE clist_##X##_iter_t \ + clist_##X##_emplace_after(clist_##X* self, clist_##X##_iter_t pos, RawValue raw) { \ + return clist_##X##_insert_after(self, pos, valueFromRaw(raw)); \ + } \ + STC_API clist_##X##_iter_t \ + clist_##X##_erase_after(clist_##X* self, clist_##X##_iter_t pos); \ + STC_API clist_##X##_iter_t \ + clist_##X##_erase_range_after(clist_##X* self, clist_##X##_iter_t pos, clist_##X##_iter_t finish); \ +\ + STC_API clist_##X##_iter_t \ + clist_##X##_splice_after(clist_##X* self, clist_##X##_iter_t pos, clist_##X* other); \ + STC_INLINE clist_##X##_iter_t \ + clist_##X##_splice_front(clist_##X* self, clist_##X* other) { \ + return clist_##X##_splice_after(self, clist_##X##_before_begin(self), other); \ + } \ + STC_INLINE clist_##X##_iter_t \ + clist_##X##_splice_back(clist_##X* self, clist_##X* other) { \ + return clist_##X##_splice_after(self, clist_##X##_last(self), other); \ + } \ +\ + STC_API clist_##X##_iter_t \ + clist_##X##_find_before_in_range(const clist_##X* self, clist_##X##_iter_t first, clist_##X##_iter_t finish, RawValue val); \ + STC_API clist_##X##_iter_t \ + clist_##X##_find_before(const clist_##X* self, RawValue val); \ + STC_API clist_##X##_iter_t \ + clist_##X##_find(const clist_##X* self, RawValue val); \ + STC_API size_t \ + clist_##X##_remove(clist_##X* self, RawValue val); \ + STC_API void \ + clist_##X##_sort(clist_##X* self); \ +\ + STC_INLINE Value* \ + clist_##X##_front(const clist_##X* self) {return &self->last->next->value;} \ + STC_INLINE Value* \ + clist_##X##_back(const clist_##X* self) {return &self->last->value;} \ +\ + _c_implement_clist_7(X, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) \ + typedef clist_##X clist_##X##_t + +/* -------------------------- IMPLEMENTATION ------------------------- */ + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) +#define _c_implement_clist_7(X, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) \ +\ + STC_DEF clist_##X \ + clist_##X##_clone(clist_##X list) { \ + clist_##X out = clist_##X##_init(); \ + c_foreach_3 (i, clist_##X, list) \ + clist_##X##_emplace_back(&out, valueToRaw(i.ref)); \ + return out; \ + } \ + STC_DEF void \ + clist_##X##_del(clist_##X* self) { \ + while (self->last) _clist_##X##_erase_after(self, self->last); \ + } \ +\ + STC_DEF void \ + clist_##X##_push_back(clist_##X* self, Value value) { \ + _c_clist_insert_after(self, X, self->last, value); \ + self->last = entry; \ + } \ + STC_DEF void \ + clist_##X##_push_front(clist_##X* self, Value value) { \ + _c_clist_insert_after(self, X, self->last, value); \ + if (!self->last) self->last = entry; \ + } \ + STC_DEF void \ + clist_##X##_emplace_n(clist_##X *self, const clist_##X##_rawvalue_t arr[], size_t size) { \ + for (size_t i=0; ilast && pos._state == 0) self->last = entry; \ + pos.ref = &entry->value, pos._state = 0; return pos; \ + } \ + STC_DEF clist_##X##_iter_t \ + clist_##X##_erase_after(clist_##X* self, clist_##X##_iter_t pos) { \ + _clist_##X##_erase_after(self, _clist_node(X, pos.ref)); \ + clist_##X##_next(&pos); return pos; \ + } \ + STC_DEF clist_##X##_iter_t \ + clist_##X##_erase_range_after(clist_##X* self, clist_##X##_iter_t first, clist_##X##_iter_t finish) { \ + clist_##X##_node_t* node = _clist_node(X, first.ref), *done = finish.ref ? _clist_node(X, finish.ref) : NULL; \ + while (node && node->next != done) \ + node = _clist_##X##_erase_after(self, node); \ + clist_##X##_next(&first); return first; \ + } \ +\ + STC_DEF clist_##X##_iter_t \ + clist_##X##_find_before_in_range(const clist_##X* self, clist_##X##_iter_t first, clist_##X##_iter_t finish, RawValue val) { \ + clist_##X##_iter_t i = first; \ + for (clist_##X##_next(&i); i.ref != finish.ref; clist_##X##_next(&i)) { \ + RawValue r = valueToRaw(i.ref); \ + if (valueCompareRaw(&r, &val) == 0) return first; \ + first = i; \ + } \ + return clist_##X##_end(self); \ + } \ + STC_DEF clist_##X##_iter_t \ + clist_##X##_find_before(const clist_##X* self, RawValue val) { \ + clist_##X##_iter_t it = clist_##X##_find_before_in_range(self, clist_##X##_before_begin(self), clist_##X##_end(self), val); \ + return it; \ + } \ + STC_DEF clist_##X##_iter_t \ + clist_##X##_find(const clist_##X* self, RawValue val) { \ + clist_##X##_iter_t it = clist_##X##_find_before_in_range(self, clist_##X##_before_begin(self), clist_##X##_end(self), val); \ + if (it.ref != clist_##X##_end(self).ref) clist_##X##_next(&it); \ + return it; \ + } \ +\ + STC_DEF clist_##X##_node_t* \ + _clist_##X##_erase_after(clist_##X* self, clist_##X##_node_t* node) { \ + clist_##X##_node_t* del = node->next, *next = del->next; \ + node->next = next; \ + if (del == next) self->last = node = NULL; \ + else if (self->last == del) self->last = node, node = NULL; \ + valueDel(&del->value); c_free(del); \ + return node; \ + } \ +\ + STC_DEF size_t \ + clist_##X##_remove(clist_##X* self, RawValue val) { \ + size_t n = 0; \ + clist_##X##_node_t* prev = self->last, *node; \ + while (prev) { \ + node = prev->next; \ + RawValue r = valueToRaw(&node->value); \ + if (valueCompareRaw(&r, &val) == 0) \ + prev = _clist_##X##_erase_after(self, prev), ++n; \ + else \ + prev = (node == self->last ? NULL : node); \ + } \ + return n; \ + } \ +\ + STC_DEF clist_##X##_iter_t \ + clist_##X##_splice_after(clist_##X* self, clist_##X##_iter_t pos, clist_##X* other) { \ + clist_##X##_iter_t it = clist_##X##_last(other); \ + if (!pos.ref) \ + self->last = other->last; \ + else if (other->last) { \ + clist_##X##_node_t *node = _clist_node(X, 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; \ + it._last = &self->last; return it; \ + } \ +\ + STC_DEF clist_##X \ + clist_##X##_splice_out(clist_##X* self, clist_##X##_iter_t pos1, clist_##X##_iter_t pos2) { \ + clist_##X##_node_t *node1 = _clist_node(X, pos1.ref), *next1 = node1->next, \ + *node2 = _clist_node(X, pos2.ref); \ + node1->next = node2->next, node2->next = next1; \ + if (self->last == node2) self->last = node1; \ + clist_##X list = {node2}; return list; \ + } \ +\ + STC_INLINE int \ + clist_##X##_sort_compare(const void* x, const void* y) { \ + RawValue a = valueToRaw(&((clist_##X##_node_t *) x)->value); \ + RawValue b = valueToRaw(&((clist_##X##_node_t *) y)->value); \ + return valueCompareRaw(&a, &b); \ + } \ + STC_DEF void \ + clist_##X##_sort(clist_##X* self) { \ + if (self->last) \ + self->last = (clist_##X##_node_t *) _clist_mergesort((clist_void_node_t *) self->last->next, clist_##X##_sort_compare); \ + } + + +#define _c_clist_insert_after(self, X, node, val) \ + clist_##X##_node_t *entry = c_new_1 (clist_##X##_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_size(const clist_void* self) { + const clist_void_node_t *i = self->last; + if (!i) return 0; + size_t n = 1; + while ((i = i->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_7(X, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue) +#endif + +#endif diff --git a/docs/clist_api.md b/docs/clist_api.md index ed4ca21b..1e4613b3 100644 --- a/docs/clist_api.md +++ b/docs/clist_api.md @@ -2,15 +2,22 @@ ![List](pics/list.jpg) The **clist** container supports fast insertion and removal of elements from anywhere in the container. -Fast random access is not supported. Adding, removing and moving the elements within the list, or across -several lists, does not invalidate the iterators currently referring to other elements in the list. However, -an iterator or reference referring to an element is invalidated when the corresponding element is removed -(via *erase_after*) from the list. +Fast random access is not supported. -Unlike the similar c++ class *std::forward_list*, **clist** also supports *push_back()* (**O**(1) time). -It is implemented as a circular singly-linked list. A **clist** object occupies only one pointer in memory, -and like *std::forward_list* the length of the list is not stored. The method *clist_X_size()* is available, -however computed in **O**(*n*) time. +Unlike the c++ class *std::forward_list*, **clist** has an API similar to *std::list*, and also supports +*push_back()* (**O**(1) time). It is still implemented as a singly-linked list. A **clist** object +occupies only one pointer in memory, and like *std::forward_list* the length of the list is not stored. +The method *clist_X_size()* is available, however computed in **O**(*n*) time. + +Iterator invalidation: Adding, removing and moving the elements within the list, or across several lists +will invalidate other iterators currently refering to these elements and their immediate succesive elements. +However, an iterator to a succesive element can both be dereferenced and advanced. After advancing (using +*clist_X_next(&it)* or *it = cslist_X_fwd(it, n)*), the iterator is in a fully valid state. This implies: + +- `clist_X_insert(&L, clist_X_fwd(it,1))`, is valid only unless `*it.ref` was removed. +- `clist_X_erase_at(&L, clist_X_fwd(it,1))` is valid only unless `*it.ref`was removed or `clist_X_fwd(it,1)` is `end`. +- Iterators returned from *clist_X_insert()* and *clist_X_erase_at()* are either valid or `end`. +- Multiple elements can be safely removed from a list via multiple iterators if done in back to front order. See the c++ class [std::forward_list](https://en.cppreference.com/w/cpp/container/forward_list) for a functional description. @@ -24,7 +31,7 @@ using_clist(X, Value, valueCompare); using_clist(X, Value, valueCompare, valueDel, valueClone = c_no_clone); using_clist(X, Value, valueCompareRaw, valueDel, valueFromRaw, valueToRaw, RawValue); -using_clist_str() // using_clist(str, cstr, ...) +using_clist_str() ``` The macro `using_clist()` must be instantiated in the global scope. `X` is a type tag name and will affect the names of all clist types and methods. E.g. declaring `using_clist(i, int);`, `X` should @@ -40,58 +47,48 @@ clist_X clist_X_init(void); clist_X clist_X_clone(clist_X list); void clist_X_clear(clist_X* self); -void clist_X_del(clist_X* self); // destructor +void clist_X_del(clist_X* self); // destructor bool clist_X_empty(clist_X list); -size_t clist_X_size(clist_X list); // note: O(n) +size_t clist_X_size(clist_X list); // note: O(n) clist_X_value_t* clist_X_front(const clist_X* self); clist_X_value_t* clist_X_back(const clist_X* self); void clist_X_push_front(clist_X* self, Value value); void clist_X_emplace_front(clist_X* self, RawValue raw); +void clist_X_pop_front(clist_X* self); // non-std: void clist_X_push_back(clist_X* self, Value value); void clist_X_emplace_back(clist_X* self, RawValue raw); void clist_X_emplace_n(clist_X *self, const clist_X_rawvalue_t arr[], size_t size); -void clist_X_pop_front(clist_X* self); - -clist_X_iter_t clist_X_insert_after(clist_X* self, clist_X_iter_t it, Value value); -clist_X_iter_t clist_X_emplace_after(clist_X* self, clist_X_iter_t it, RawValue raw); - -clist_X_iter_t clist_X_erase_after(clist_X* self, clist_X_iter_t it); -clist_X_iter_t clist_X_erase_range_after(clist_X* self, clist_X_iter_t it1, clist_X_iter_t it2); +clist_X_iter_t clist_X_insert(clist_X* self, clist_X_iter_t it, Value value); // return iter to new elem; `it` may be end +clist_X_iter_t clist_X_emplace(clist_X* self, clist_X_iter_t it, RawValue raw); -clist_X_iter_t clist_X_splice_after(clist_X* self, clist_X_iter_t it, clist_X* other); - // non-std: -clist_X_iter_t clist_X_splice_front(clist_X* self, clist_X* other); -clist_X_iter_t clist_X_splice_back(clist_X* self, clist_X* other); +clist_X_iter_t clist_X_erase_at(clist_X* self, clist_X_iter_t it); // return iter before it +clist_X_iter_t clist_X_erase_range(clist_X* self, clist_X_iter_t it1, clist_X_iter_t it2); +size_t clist_X_remove(clist_X* self, RawValue raw); // removes all elements equal to raw - // non-std: note: returns range (it1, it2] - excluding it1, including it2: +void clist_X_splice(clist_X* self, clist_X_iter_t it, clist_X* other); +void clist_X_splice_range(clist_X* self, clist_X_iter_t it, + clist_X* other, clist_X_iter_t it1, clist_X_iter_t it2); + // non-std: splice [it1, it2) out of self, returned as clist clist_X clist_X_splice_out(clist_X* self, clist_X_iter_t it1, clist_X_iter_t it2); clist_X_iter_t clist_X_find(const clist_X* self, RawValue raw); -clist_X_iter_t clist_X_find_before(const clist_X* self, RawValue raw); -clist_X_iter_t clist_X_find_before_in_range(const clist_X* self, - clist_X_iter_t it1, clist_X_iter_t it2, RawValue raw); - - // std: removes all elements equal to raw -size_t clist_X_remove(clist_X* self, RawValue raw); +clist_X_iter_t clist_X_find_in_range(const clist_X* self, + clist_X_iter_t it1, clist_X_iter_t it2, RawValue raw); void clist_X_sort(clist_X* self); -clist_X_iter_t clist_X_before_begin(const clist_X* self); -clist_X_iter_t clist_X_last(const clist_X* self); clist_X_iter_t clist_X_begin(const clist_X* self); clist_X_iter_t clist_X_end(const clist_X* self); void clist_X_next(clist_X_iter_t* it); -clist_X_value_t* clist_X_itval(clist_X_iter_t it); - // non-std: return iterator n elements forward: + // non-std: return iterator advanced n elements forward: clist_X_iter_t clist_X_fwd(clist_X_iter it, size_t n); - clist_X_value_t clist_X_value_clone(clist_X_value_t val); ``` @@ -104,23 +101,6 @@ clist_X_value_t clist_X_value_clone(clist_X_value_t val); | `clist_X_rawvalue_t` | `RawValue` | clist raw value type | | `clist_X_iter_t` | `struct { clist_value_t *ref; ... }`| clist iterator | -The `clist_X_splice_out(self, it1, it2)` can be combined with `clist_X_splice_after(self, it, other)` to mimic c++ `std::forward_list::splice_after(it, other, it1, it2)`. Note however that *it2* is included in elements to be spliced, unlike with *std::forward_list()*. E.g. splice in `[2, 3]` from *L1* after `10` in *L2*: -```c -c_init (clist_i, L1, {1, 2, 3, 4, 5}); -c_init (clist_i, L2, {10, 20, 30, 40, 50}); - -clist_i_iter_t it = clist_i_fwd(clist_i_begin(&L1), 2); -clist_i tmp = clist_i_splice_out(&L1, clist_i_begin(&L1), it); -clist_i_splice_after(&L2, clist_i_begin(&L2), &tmp); - -// C++: -// auto it = L1.begin(); std::advance(it, 3); -// L2.splice_after(L2.cbegin(), L1, L1.cbegin(), it); - -// L1: 1 4 5 -// L2: 10 2 3 20 30 40 50 -``` - ## Example Interleave *push_front()* / *push_back()* then *sort()*: @@ -159,7 +139,8 @@ initial: 9 7 5 3 1 10 20 30 40 50 60 70 80 90 2 4 6 8 sorted: 1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90 ``` ### Example 2 -Show *erase_after()*, *erase_range_after()*: + +Use of *erase_at()* and *erase_range()*: ```c // erasing from clist #include @@ -172,10 +153,12 @@ int main () c_init (clist_i, L, {10, 20, 30, 40, 50}); // 10 20 30 40 50 clist_i_iter_t it = clist_i_begin(&L); // ^ - it = clist_i_erase_after(&L, it); // 10 30 40 50 + clist_i_next(&it); + it = clist_i_erase_at(&L, it); // 10 30 40 50 // ^ clist_i_iter_t end = clist_i_end(&L); // - it = clist_i_erase_range_after(&L, it, end); // 10 30 + clist_i_next(&it); + it = clist_i_erase_range(&L, it, end); // 10 30 // ^ printf("mylist contains:"); c_foreach (x, clist_i, L) printf(" %d", *x.ref); @@ -188,3 +171,31 @@ Output: ``` mylist contains: 10 30 ``` + +### Example 3 + +Splice `[30, 40]` from *L2* into *L1* before `3`: +```c +#include +#include + +using_clist(i, int); + +int main() { + c_init (clist_i, L1, {1, 2, 3, 4, 5}); + c_init (clist_i, L2, {10, 20, 30, 40, 50}); + + clist_i_iter_t i = clist_i_fwd(clist_i_begin(&L1), 2); + clist_i_iter_t j1 = clist_i_fwd(clist_i_begin(&L2), 2), j2 = clist_i_fwd(j1, 2); + + clist_i_splice_range(&L1, i, &L2, j1, j2); + + c_foreach (i, clist_i, L1) printf(" %d", *i.ref); puts(""); + c_foreach (i, clist_i, L2) printf(" %d", *i.ref); puts(""); +} +``` +Output: +``` +1 2 30 40 3 4 5 +10 20 50 +``` \ No newline at end of file diff --git a/examples/demos.c b/examples/demos.c index d8228b4e..14bf20d4 100644 --- a/examples/demos.c +++ b/examples/demos.c @@ -86,18 +86,21 @@ void listdemo1() clist_ix_push_back(&nums, i); for (int i = 100; i < 110; ++i) clist_ix_push_back(&nums2, i); - c_foreach (i, clist_ix, nums) - printf("value: %d\n", *i.ref); - /* merge/append nums2 to nums */ - clist_ix_splice_front(&nums, &nums2); + + /* splice nums2 to front of nums */ + clist_ix_splice(&nums, clist_ix_begin(&nums), &nums2); c_foreach (i, clist_ix, nums) printf("spliced: %d\n", *i.ref); + puts(""); - *clist_ix_find(&nums, 100).ref *= 10; - clist_ix_sort(&nums); // Sort the array - clist_ix_remove(&nums, 105); + *clist_ix_find(&nums, 104).ref += 50; + clist_ix_remove(&nums, 103); + clist_ix_iter_t it = clist_ix_begin(&nums); + clist_ix_erase_range(&nums, clist_ix_fwd(it, 5), clist_ix_fwd(it, 15)); clist_ix_pop_front(&nums); - clist_ix_push_front(&nums, -99); + clist_ix_push_back(&nums, -99); + clist_ix_sort(&nums); + c_foreach (i, clist_ix, nums) printf("sorted: %d\n", *i.ref); clist_ix_del(&nums); diff --git a/examples/list.c b/examples/list.c index 7ac49e19..2bc493b9 100644 --- a/examples/list.c +++ b/examples/list.c @@ -38,17 +38,17 @@ int main() { puts(""); int removed = clist_fx_remove(&list, 30); - clist_fx_insert_after(&list, clist_fx_before_begin(&list), 5); // same as push_front() + clist_fx_insert(&list, clist_fx_begin(&list), 5); // same as push_front() clist_fx_push_back(&list, 500); clist_fx_push_front(&list, 1964); - clist_fx_iter_t it = clist_fx_before_begin(&list); + clist_fx_iter_t it = clist_fx_begin(&list); printf("Full: "); c_foreach (i, clist_fx, list) printf(" %g", *i.ref); - for (int i=0; i<4; ++i) clist_fx_next(&it); printf("\nSubs: "); - c_foreach (i, clist_fx, it, clist_fx_end(&list)) + c_foreach (i, clist_fx, clist_fx_fwd(it, 4), clist_fx_end(&list)) printf(" %g", *i.ref); puts(""); + clist_fx_del(&list); } \ No newline at end of file diff --git a/examples/list_erase.c b/examples/list_erase.c index d0bdc2df..6e70b103 100644 --- a/examples/list_erase.c +++ b/examples/list_erase.c @@ -7,18 +7,18 @@ using_clist(i, int); int main () { c_init (clist_i, L, {10, 20, 30, 40, 50}); - clist_i_iter_t end; // 10 20 30 40 50 clist_i_iter_t it = clist_i_begin(&L); // ^ - it = clist_i_erase_after(&L, it); // 10 30 40 50 + clist_i_next(&it); + it = clist_i_erase_at(&L, it); // 10 30 40 50 // ^ - end = clist_i_end(&L); // - it = clist_i_erase_range_after(&L, it, end); // 10 30 + clist_i_iter_t end = clist_i_end(&L); // + clist_i_next(&it); + it = clist_i_erase_range(&L, it, end); // 10 30 // ^ - printf("mylist contains:"); c_foreach (x, clist_i, L) printf(" %d", *x.ref); puts(""); clist_i_del(&L); -} \ No newline at end of file +} diff --git a/stc/clist.h b/stc/clist.h index ec431370..d6129bcb 100644 --- a/stc/clist.h +++ b/stc/clist.h @@ -80,9 +80,8 @@ } clist_##X; \ \ typedef struct { \ - clist_##X##_node_t* const* _last; \ + clist_##X##_node_t* const *_last, *_prev; \ clist_##X##_value_t* ref; \ - int _state; \ } clist_##X##_iter_t @@ -130,74 +129,65 @@ STC_API size_t _clist_size(const clist_void* self); \ STC_API clist_##X##_node_t* \ _clist_##X##_erase_after(clist_##X* self, clist_##X##_node_t* node); \ +\ STC_INLINE void \ clist_##X##_pop_front(clist_##X* self) { \ _clist_##X##_erase_after(self, self->last); \ } \ STC_INLINE clist_##X##_iter_t \ - clist_##X##_before_begin(const clist_##X* self) { \ - clist_##X##_value_t *last = self->last ? &self->last->value : NULL; \ - clist_##X##_iter_t it = {&self->last, last, -1}; return it; \ - } \ - STC_INLINE clist_##X##_iter_t \ clist_##X##_begin(const clist_##X* self) { \ clist_##X##_value_t* head = self->last ? &self->last->next->value : NULL; \ - clist_##X##_iter_t it = {&self->last, head, 0}; return it; \ - } \ - STC_INLINE clist_##X##_iter_t \ - clist_##X##_last(const clist_##X* self) { \ - clist_##X##_value_t *last = self->last ? &self->last->value : NULL; \ - clist_##X##_iter_t it = {&self->last, last, 0}; return it; \ + clist_##X##_iter_t it = {&self->last, self->last, head}; return it; \ } \ STC_INLINE clist_##X##_iter_t \ clist_##X##_end(const clist_##X* self) { \ - clist_##X##_iter_t it = {NULL, NULL}; return it; \ + clist_##X##_iter_t it = {&self->last, NULL, NULL}; return it; \ } \ STC_INLINE void \ clist_##X##_next(clist_##X##_iter_t* it) { \ - clist_##X##_node_t* node = _clist_node(X, it->ref); \ - it->ref = ((it->_state += node == *it->_last) == 1) ? NULL : &node->next->value; \ + clist_##X##_node_t* node = it->_prev = _clist_node(X, it->ref); \ + it->ref = (node == *it->_last ? NULL : &node->next->value); \ } \ STC_INLINE clist_##X##_iter_t \ clist_##X##_fwd(clist_##X##_iter_t it, size_t n) { \ - c_forrange_1 (n) clist_##X##_next(&it); return it; \ + while (n-- && it.ref) clist_##X##_next(&it); \ + return it; \ } \ - STC_INLINE clist_##X##_value_t* \ - clist_##X##_itval(clist_##X##_iter_t it) {return it.ref;} \ \ STC_API clist_##X##_iter_t \ - clist_##X##_insert_after(clist_##X* self, clist_##X##_iter_t pos, Value value); \ + clist_##X##_insert(clist_##X* self, clist_##X##_iter_t pos, Value value); \ STC_INLINE clist_##X##_iter_t \ - clist_##X##_emplace_after(clist_##X* self, clist_##X##_iter_t pos, RawValue raw) { \ - return clist_##X##_insert_after(self, pos, valueFromRaw(raw)); \ + clist_##X##_emplace(clist_##X* self, clist_##X##_iter_t pos, RawValue raw) { \ + return clist_##X##_insert(self, pos, valueFromRaw(raw)); \ } \ STC_API clist_##X##_iter_t \ - clist_##X##_erase_after(clist_##X* self, clist_##X##_iter_t pos); \ + clist_##X##_erase_at(clist_##X* self, clist_##X##_iter_t pos); \ STC_API clist_##X##_iter_t \ - clist_##X##_erase_range_after(clist_##X* self, clist_##X##_iter_t pos, clist_##X##_iter_t finish); \ + clist_##X##_erase_range(clist_##X* self, clist_##X##_iter_t pos, clist_##X##_iter_t finish); \ \ - STC_API clist_##X##_iter_t \ - clist_##X##_splice_after(clist_##X* self, clist_##X##_iter_t pos, clist_##X* other); \ - STC_INLINE clist_##X##_iter_t \ - clist_##X##_splice_front(clist_##X* self, clist_##X* other) { \ - return clist_##X##_splice_after(self, clist_##X##_before_begin(self), other); \ - } \ - STC_INLINE clist_##X##_iter_t \ - clist_##X##_splice_back(clist_##X* self, clist_##X* other) { \ - return clist_##X##_splice_after(self, clist_##X##_last(self), other); \ + STC_API void \ + clist_##X##_splice(clist_##X* self, clist_##X##_iter_t pos, clist_##X* other); \ + STC_API clist_##X \ + clist_##X##_splice_out(clist_##X* self, clist_##X##_iter_t pos1, clist_##X##_iter_t pos2); \ +\ + STC_INLINE void \ + clist_##X##_splice_range(clist_##X* self, clist_##X##_iter_t pos, \ + clist_##X* other, clist_##X##_iter_t pos1, clist_##X##_iter_t pos2) { \ + clist_##X tmp = clist_##X##_splice_out(other, pos1, pos2); \ + clist_##X##_splice(self, pos, &tmp); \ } \ \ - STC_API clist_##X##_iter_t \ - clist_##X##_find_before_in_range(const clist_##X* self, clist_##X##_iter_t first, clist_##X##_iter_t finish, RawValue val); \ - STC_API clist_##X##_iter_t \ - clist_##X##_find_before(const clist_##X* self, RawValue val); \ - STC_API clist_##X##_iter_t \ - clist_##X##_find(const clist_##X* self, RawValue val); \ STC_API size_t \ clist_##X##_remove(clist_##X* self, RawValue val); \ STC_API void \ clist_##X##_sort(clist_##X* self); \ + STC_API clist_##X##_iter_t \ + clist_##X##_find_in_range(const clist_##X* self, clist_##X##_iter_t first, clist_##X##_iter_t finish, RawValue val); \ \ + STC_INLINE clist_##X##_iter_t \ + clist_##X##_find(const clist_##X* self, RawValue val) { \ + return clist_##X##_find_in_range(self, clist_##X##_begin(self), clist_##X##_end(self), val); \ + } \ STC_INLINE Value* \ clist_##X##_front(const clist_##X* self) {return &self->last->next->value;} \ STC_INLINE Value* \ @@ -234,51 +224,43 @@ STC_API size_t _clist_size(const clist_void* self); if (!self->last) self->last = entry; \ } \ STC_DEF void \ - clist_##X##_emplace_n(clist_##X *self, const clist_##X##_rawvalue_t arr[], size_t size) { \ - for (size_t i=0; ilast; \ _c_clist_insert_after(self, X, node, value); \ - if (!node || node == self->last && pos._state == 0) self->last = entry; \ - pos.ref = &entry->value, pos._state = 0; return pos; \ + pos.ref = &entry->value; \ + if (!self->last || !pos._prev) { \ + pos._prev = self->last ? self->last : entry; \ + self->last = entry; \ + } \ + return pos; \ } \ +\ STC_DEF clist_##X##_iter_t \ - clist_##X##_erase_after(clist_##X* self, clist_##X##_iter_t pos) { \ - _clist_##X##_erase_after(self, _clist_node(X, pos.ref)); \ - clist_##X##_next(&pos); return pos; \ + clist_##X##_erase_at(clist_##X* self, clist_##X##_iter_t pos) { \ + clist_##X##_node_t* node = pos._prev; clist_##X##_next(&pos); \ + return _clist_##X##_erase_after(self, node) ? pos : clist_##X##_end(self); \ } \ STC_DEF clist_##X##_iter_t \ - clist_##X##_erase_range_after(clist_##X* self, clist_##X##_iter_t first, clist_##X##_iter_t finish) { \ - clist_##X##_node_t* node = _clist_node(X, first.ref), *done = finish.ref ? _clist_node(X, finish.ref) : NULL; \ + clist_##X##_erase_range(clist_##X* self, clist_##X##_iter_t first, clist_##X##_iter_t finish) { \ + clist_##X##_node_t* node = first._prev, *done = finish.ref ? _clist_node(X, finish.ref) : NULL; \ while (node && node->next != done) \ node = _clist_##X##_erase_after(self, node); \ - clist_##X##_next(&first); return first; \ + return node ? finish : clist_##X##_end(self); \ } \ \ STC_DEF clist_##X##_iter_t \ - clist_##X##_find_before_in_range(const clist_##X* self, clist_##X##_iter_t first, clist_##X##_iter_t finish, RawValue val) { \ - clist_##X##_iter_t i = first; \ - for (clist_##X##_next(&i); i.ref != finish.ref; clist_##X##_next(&i)) { \ + clist_##X##_find_in_range(const clist_##X* self, clist_##X##_iter_t first, clist_##X##_iter_t finish, RawValue val) { \ + c_foreach_4 (i, clist_##X, first, finish) { \ RawValue r = valueToRaw(i.ref); \ - if (valueCompareRaw(&r, &val) == 0) return first; \ - first = i; \ + if (valueCompareRaw(&r, &val) == 0) return i; \ } \ return clist_##X##_end(self); \ } \ - STC_DEF clist_##X##_iter_t \ - clist_##X##_find_before(const clist_##X* self, RawValue val) { \ - clist_##X##_iter_t it = clist_##X##_find_before_in_range(self, clist_##X##_before_begin(self), clist_##X##_end(self), val); \ - return it; \ - } \ - STC_DEF clist_##X##_iter_t \ - clist_##X##_find(const clist_##X* self, RawValue val) { \ - clist_##X##_iter_t it = clist_##X##_find_before_in_range(self, clist_##X##_before_begin(self), clist_##X##_end(self), val); \ - if (it.ref != clist_##X##_end(self).ref) clist_##X##_next(&it); \ - return it; \ - } \ \ STC_DEF clist_##X##_node_t* \ _clist_##X##_erase_after(clist_##X* self, clist_##X##_node_t* node) { \ @@ -305,28 +287,28 @@ STC_API size_t _clist_size(const clist_void* self); return n; \ } \ \ - STC_DEF clist_##X##_iter_t \ - clist_##X##_splice_after(clist_##X* self, clist_##X##_iter_t pos, clist_##X* other) { \ - clist_##X##_iter_t it = clist_##X##_last(other); \ - if (!pos.ref) \ + STC_DEF void \ + clist_##X##_splice(clist_##X* self, clist_##X##_iter_t pos, clist_##X* other) { \ + if (!self->last) \ self->last = other->last; \ else if (other->last) { \ - clist_##X##_node_t *node = _clist_node(X, pos.ref), *next = node->next; \ - node->next = other->last->next; \ + clist_##X##_node_t *p = pos._prev ? pos._prev : self->last, *next = p->next; \ + p->next = other->last->next; \ other->last->next = next; \ - if (node == self->last && pos._state == 0) self->last = other->last; \ + if (!pos._prev) self->last = other->last; \ } \ other->last = NULL; \ - it._last = &self->last; return it; \ } \ \ STC_DEF clist_##X \ clist_##X##_splice_out(clist_##X* self, clist_##X##_iter_t pos1, clist_##X##_iter_t pos2) { \ - clist_##X##_node_t *node1 = _clist_node(X, pos1.ref), *next1 = node1->next, \ - *node2 = _clist_node(X, pos2.ref); \ - node1->next = node2->next, node2->next = next1; \ - if (self->last == node2) self->last = node1; \ - clist_##X list = {node2}; return list; \ + clist_##X##_node_t *p1 = pos1._prev, *next1 = _clist_node(X, pos1.ref), \ + *p2 = pos2._prev ? pos2._prev : self->last; \ + clist_##X list = {p2}; \ + if (!(p1 && p2)) return list; \ + p1->next = p2->next, p2->next = next1; \ + if (self->last == p2) self->last = p1; \ + return list; \ } \ \ STC_INLINE int \ @@ -337,17 +319,16 @@ STC_API size_t _clist_size(const clist_void* self); } \ STC_DEF void \ clist_##X##_sort(clist_##X* self) { \ - clist_void_node_t* last = _clist_mergesort((clist_void_node_t *) self->last->next, clist_##X##_sort_compare); \ - self->last = (clist_##X##_node_t *) last; \ + if (self->last) \ + self->last = (clist_##X##_node_t *) _clist_mergesort((clist_void_node_t *) self->last->next, clist_##X##_sort_compare); \ } #define _c_clist_insert_after(self, X, node, val) \ - clist_##X##_node_t *entry = c_new_1 (clist_##X##_node_t), \ - *next = self->last ? node->next : entry; \ - entry->value = val; \ - entry->next = next; \ - if (node) node->next = entry + clist_##X##_node_t *entry = c_new_1 (clist_##X##_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 @@ -366,7 +347,6 @@ 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; - if (!list) return NULL; while (1) { p = oldhead = list; -- cgit v1.2.3