From f8e48cd1b7189a8da7ce25087ab61fba03755246 Mon Sep 17 00:00:00 2001 From: Tyge Date: Sun, 19 Apr 2020 20:19:04 +0200 Subject: Renamed clist to cfwdlist, as it implements std::forward_list specs. --- stc/cfwdlist.h | 205 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ stc/clist.h | 206 --------------------------------------------------------- 2 files changed, 205 insertions(+), 206 deletions(-) create mode 100644 stc/cfwdlist.h delete mode 100644 stc/clist.h diff --git a/stc/cfwdlist.h b/stc/cfwdlist.h new file mode 100644 index 00000000..0671fa0f --- /dev/null +++ b/stc/cfwdlist.h @@ -0,0 +1,205 @@ +/* MIT License + * + * Copyright (c) 2020 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 CFWDLIST__H__ +#define CFWDLIST__H__ + +#include "cdefs.h" + +/* Circular Singly-linked Lists */ + +#define cfwdlist_init {NULL} + +#define declare_CFwdList(...) c_MACRO_OVERLOAD(declare_CFwdList, __VA_ARGS__) + +#define declare_CFwdList_2(tag, Value) \ + declare_CFwdList_3(tag, Value, c_defaultDestroy) +#define declare_CFwdList_3(tag, Value, valueDestroy) \ + declare_CFwdList_4(tag, Value, valueDestroy, c_defaultCompare) +#define declare_CFwdList_4(tag, Value, valueDestroy, valueCompare) \ + declare_CFwdList_6(tag, Value, valueDestroy, valueCompare, Value, c_defaultGetRaw) +#define declare_CFwdList_string(tag) \ + declare_CFwdList_6(tag, CString, cstring_destroy, cstring_compareRaw, const char*, cstring_getRaw) + + +#define declare_CFwdListTypes(tag, Value) \ + c_struct (CFwdListNode_##tag) { \ + CFwdListNode_##tag *next; \ + Value value; \ + }; \ + \ + c_struct (CFwdList_##tag) { \ + CFwdListNode_##tag* last; \ + }; \ + \ + c_struct (cfwdlist_##tag##_iter_t) { \ + CFwdListNode_##tag *item, *head; \ + } + + +#define declare_CFwdList_6(tag, Value, valueDestroy, valueCompare, ValueRaw, valueGetRaw) \ + \ + declare_CFwdListTypes(tag, Value); \ + \ + static inline void \ + cfwdlist_##tag##_pushFront(CFwdList_##tag* self, Value value) { \ + _cfwdlist_insertAfter(tag, self->last, value); \ + if (!self->last) self->last = entry; \ + } \ + static inline void \ + cfwdlist_##tag##_pushBack(CFwdList_##tag* self, Value value) { \ + _cfwdlist_insertAfter(tag, self->last, value); \ + self->last = entry; \ + } \ + static inline void \ + cfwdlist_##tag##_insertAfter(CFwdList_##tag* self, cfwdlist_##tag##_iter_t pos, Value value) { \ + _cfwdlist_insertAfter(tag, pos.item, value); \ + if (!self->last || pos.item == self->last) self->last = entry; \ + } \ + static inline void \ + cfwdlist_##tag##_eraseAfter(CFwdList_##tag* self, cfwdlist_##tag##_iter_t pos) { \ + _cfwdlist_eraseAfter(tag, pos.item, valueDestroy); \ + } \ + \ + static inline void \ + cfwdlist_##tag##_popFront(CFwdList_##tag* self) { \ + _cfwdlist_eraseAfter(tag, self->last, valueDestroy); \ + } \ + \ + static inline void \ + cfwdlist_##tag##_destroy(CFwdList_##tag* self) { \ + while (self->last) \ + cfwdlist_##tag##_popFront(self); \ + } \ + \ + static inline cfwdlist_##tag##_iter_t \ + cfwdlist_##tag##_begin(CFwdList_##tag lst) { \ + CFwdListNode_##tag *head = lst.last ? lst.last->next : NULL; \ + return (cfwdlist_##tag##_iter_t) {head, head}; \ + } \ + \ + static inline cfwdlist_##tag##_iter_t \ + cfwdlist_##tag##_next(cfwdlist_##tag##_iter_t it) { \ + CFwdListNode_##tag *next = it.item->next; \ + it.item = next != it.head ? next : NULL; \ + return it; \ + } \ + \ + static inline cfwdlist_##tag##_iter_t \ + cfwdlist_##tag##_end(CFwdList_##tag lst) { \ + return (cfwdlist_##tag##_iter_t) {NULL}; \ + } \ + \ + static inline int \ + cfwdlist_##tag##_sortCmp(const void* x, const void* y) { \ + CFwdListNode_##tag *a = (CFwdListNode_##tag *)x, *b = (CFwdListNode_##tag *)y; \ + return valueCompare(valueGetRaw(&a->value), valueGetRaw(&b->value)); \ + } \ + \ + static inline void \ + cfwdlist_##tag##_sort(CFwdList_##tag* self) { \ + CFwdListNode__base* last = cfwdlist_sort_base((CFwdListNode__base *) self->last, cfwdlist_##tag##_sortCmp); \ + self->last = (CFwdListNode_##tag *) last; \ + } \ + \ + typedef Value cfwdlist_##tag##_value_t + + +#define _cfwdlist_insertAfter(tag, node, val) \ + CFwdListNode_##tag *entry = c_new_1(CFwdListNode_##tag), \ + *next = self->last ? node->next : entry; \ + entry->value = val; \ + entry->next = next; \ + if (node) node->next = entry \ + /* +: set self->last based on node */ + + +#define _cfwdlist_eraseAfter(tag, node, valueDestroy) \ + CFwdListNode_##tag* del = node->next, *next = del->next; \ + node->next = next; \ + if (del == next) self->last = NULL; \ + else if (self->last == del) self->last = node; \ + valueDestroy(&del->value); \ + free(del) + + +declare_CFwdListTypes(_base, int); + +/* + * Singly linked list Mergesort implementation by Simon Tatham. O(n*log(n)). + * https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html + */ +static CFwdListNode__base * +cfwdlist_sort_base(CFwdListNode__base *list, int (*cmp)(const void*, const void*)) { + CFwdListNode__base *p, *q, *e, *tail, *oldhead; + int insize = 1, nmerges, psize, qsize, i; + if (!list) return NULL; + + while (1) { + p = list; + 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; + } +} + +#endif diff --git a/stc/clist.h b/stc/clist.h deleted file mode 100644 index 13798318..00000000 --- a/stc/clist.h +++ /dev/null @@ -1,206 +0,0 @@ -/* MIT License - * - * Copyright (c) 2020 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__ -#define CLIST__H__ - -#include "cdefs.h" - -/* Circular Singly-linked Lists */ - -#define clist_init {NULL, 0} -#define clist_size(list) ((size_t) (list).size) - -#define declare_CList(...) c_MACRO_OVERLOAD(declare_CList, __VA_ARGS__) - -#define declare_CList_2(tag, Value) \ - declare_CList_3(tag, Value, c_defaultDestroy) -#define declare_CList_3(tag, Value, valueDestroy) \ - declare_CList_4(tag, Value, valueDestroy, c_defaultCompare) -#define declare_CList_4(tag, Value, valueDestroy, valueCompare) \ - declare_CList_6(tag, Value, valueDestroy, valueCompare, Value, c_defaultGetRaw) -#define declare_CList_string(tag) \ - declare_CList_6(tag, CString, cstring_destroy, cstring_compareRaw, const char*, cstring_getRaw) - - -#define declare_CListTypes(tag, Value) \ - c_struct (CListNode_##tag) { \ - CListNode_##tag *next; \ - Value value; \ - }; \ - \ - c_struct (CList_##tag) { \ - CListNode_##tag* last; \ - size_t size; \ - }; \ - \ - c_struct (clist_##tag##_iter_t) { \ - CListNode_##tag *item, *head; \ - } - - -#define declare_CList_6(tag, Value, valueDestroy, valueCompare, ValueRaw, valueGetRaw) \ - \ - declare_CListTypes(tag, Value); \ - \ - static inline void \ - clist_##tag##_pushFront(CList_##tag* self, Value value) { \ - _clist_insertAfter(tag, self->last, value); \ - if (!self->last) self->last = entry; \ - } \ - static inline void \ - clist_##tag##_pushBack(CList_##tag* self, Value value) { \ - _clist_insertAfter(tag, self->last, value); \ - self->last = entry; \ - } \ - static inline void \ - clist_##tag##_insertAfter(CList_##tag* self, clist_##tag##_iter_t pos, Value value) { \ - _clist_insertAfter(tag, pos.item, value); \ - if (!self->last || pos.item == self->last) self->last = entry; \ - } \ - static inline void \ - clist_##tag##_eraseAfter(CList_##tag* self, clist_##tag##_iter_t pos) { \ - _clist_eraseAfter(tag, pos.item, valueDestroy); \ - } \ - \ - static inline void \ - clist_##tag##_popFront(CList_##tag* self) { \ - _clist_eraseAfter(tag, self->last, valueDestroy); \ - } \ - \ - static inline void \ - clist_##tag##_destroy(CList_##tag* self) { \ - while (clist_size(*self)) \ - clist_##tag##_popFront(self); \ - } \ - \ - static inline clist_##tag##_iter_t \ - clist_##tag##_begin(CList_##tag lst) { \ - CListNode_##tag *head = lst.last ? lst.last->next : NULL; \ - return (clist_##tag##_iter_t) {head, head}; \ - } \ - \ - static inline clist_##tag##_iter_t \ - clist_##tag##_next(clist_##tag##_iter_t it) { \ - CListNode_##tag *next = it.item->next; \ - it.item = next != it.head ? next : NULL; \ - return it; \ - } \ - \ - static inline clist_##tag##_iter_t \ - clist_##tag##_end(CList_##tag lst) { \ - return (clist_##tag##_iter_t) {NULL}; \ - } \ - \ - static inline int \ - clist_##tag##_sortCompare(const void* x, const void* y) { \ - CListNode_##tag *a = (CListNode_##tag *)x, *b = (CListNode_##tag *)y; \ - return valueCompare(valueGetRaw(&a->value), valueGetRaw(&b->value)); \ - } \ - \ - static inline void \ - clist_##tag##_sort(CList_##tag* self) { \ - CListNode__i* last = clist_sort((CListNode__i *) self->last, clist_##tag##_sortCompare); \ - self->last = (CListNode_##tag *) last; \ - } \ - \ - typedef Value clist_##tag##_value_t - - -#define _clist_insertAfter(tag, node, val) \ - CListNode_##tag *entry = c_new_1(CListNode_##tag), \ - *next = self->last ? node->next : entry; \ - entry->value = val; \ - entry->next = next; \ - ++self->size; \ - if (node) node->next = entry - -#define _clist_eraseAfter(tag, node, valueDestroy) \ - CListNode_##tag* del = node->next, *next = del->next; \ - node->next = next; \ - if (--self->size == 0) self->last = NULL; \ - else if (self->last == del) self->last = node; \ - valueDestroy(&del->value); \ - free(del) - - -declare_CListTypes(_i, int); - -/* - * Singly linked list Mergesort implementation by Simon Tatham. O(n*log(n)). - * https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html - */ -static CListNode__i * -clist_sort(CListNode__i *list, int (*cmp)(const void*, const void*)) { - CListNode__i *p, *q, *e, *tail, *oldhead; - int insize = 1, nmerges, psize, qsize, i; - if (!list) return NULL; - - while (1) { - p = list; - 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; - } -} - -#endif -- cgit v1.2.3