diff options
Diffstat (limited to 'include/stc/clist.h')
| -rw-r--r-- | include/stc/clist.h | 112 |
1 files changed, 31 insertions, 81 deletions
diff --git a/include/stc/clist.h b/include/stc/clist.h index f8a21f40..f7fb4152 100644 --- a/include/stc/clist.h +++ b/include/stc/clist.h @@ -26,7 +26,7 @@ it also support both push_back() and push_front(), unlike std::forward_list: #include <stdio.h> - #include <stc/crandom.h> + #include <stc/crand.h> #define i_key int64_t #define i_tag ix @@ -38,12 +38,12 @@ { int n; for (int i = 0; i < 1000000; ++i) // one million - clist_ix_push_back(&list, crandom() >> 32); + clist_ix_push_back(&list, crand() >> 32); n = 0; c_foreach (i, clist_ix, list) if (++n % 10000 == 0) printf("%8d: %10zu\n", n, *i.ref); // Sort them... - clist_ix_sort(&list); // mergesort O(n*log n) + clist_ix_sort(&list); // qsort O(n*log n) n = 0; puts("sorted"); c_foreach (i, clist_ix, list) @@ -66,11 +66,6 @@ #define _clist_tonode(vp) c_container_of(vp, _cx_node, value) -_c_clist_types(clist_VOID, int); -_c_clist_complete_types(clist_VOID, dummy); -typedef int clist_VOID_comp(const clist_VOID_node*, const clist_VOID_node*); -extern clist_VOID_node* _clist_mergesort(clist_VOID_node*, clist_VOID_comp*); - #define _c_clist_insert_entry_after(ref, val) \ _cx_node *entry = (_cx_node *)i_malloc(c_sizeof *entry); entry->value = val; \ _c_clist_insert_after_node(ref, entry) @@ -87,7 +82,7 @@ extern clist_VOID_node* _clist_mergesort(clist_VOID_node*, clist_VOID_comp*); #endif #include "priv/template.h" -#if !c_option(c_is_forward) +#ifndef i_is_forward _cx_deftypes(_c_clist_types, _cx_self, i_key); #endif _cx_deftypes(_c_clist_complete_types, _cx_self, dummy); @@ -104,7 +99,10 @@ STC_API _cx_iter _cx_memb(_find_in)(_cx_iter it1, _cx_iter it2, _cx_raw v STC_API intptr_t _cx_memb(_remove)(_cx_self* self, _cx_raw val); #endif #ifndef i_no_cmp -STC_API int _cx_memb(_sort_cmp_)(const _cx_node* x, const _cx_node* y); +STC_API bool _cx_memb(_sort_with)(_cx_self* self, int(*cmp)(const _cx_value*, const _cx_value*)); +STC_API int _cx_memb(_sort_cmp_)(const _cx_value*, const _cx_value*); +STC_INLINE bool _cx_memb(_sort)(_cx_self* self) + { return _cx_memb(_sort_with)(self, _cx_memb(_sort_cmp_)); } #endif STC_API void _cx_memb(_reverse)(_cx_self* self); STC_API _cx_iter _cx_memb(_splice)(_cx_self* self, _cx_iter it, _cx_self* other); @@ -206,9 +204,8 @@ _cx_memb(_get_mut)(_cx_self* self, _cx_raw val) { return _cx_memb(_find_in)(_cx_memb(_begin)(self), _cx_memb(_end)(self), val).ref; } -STC_INLINE bool -_cx_memb(_eq)(const _cx_self* x, const _cx_self* y) { - _cx_iter i = _cx_memb(_begin)(x), j = _cx_memb(_begin)(y); +STC_INLINE bool _cx_memb(_eq)(const _cx_self* self, const _cx_self* other) { + _cx_iter i = _cx_memb(_begin)(self), j = _cx_memb(_begin)(other); for (; i.ref && j.ref; _cx_memb(_next)(&i), _cx_memb(_next)(&j)) { const _cx_raw _rx = i_keyto(i.ref), _ry = i_keyto(j.ref); if (!(i_eq((&_rx), (&_ry)))) return false; @@ -216,68 +213,6 @@ _cx_memb(_eq)(const _cx_self* x, const _cx_self* y) { return !(i.ref || j.ref); } #endif -#ifndef i_no_cmp - -STC_INLINE void -_cx_memb(_sort)(_cx_self* self) { - if (self->last) - self->last = (_cx_node *)_clist_mergesort((clist_VOID_node *)self->last->next, - (clist_VOID_comp *)_cx_memb(_sort_cmp_)); -} -STC_INLINE void -_cx_memb(_sort_with)(_cx_self* self, int(*cmp)(const _cx_node*, const _cx_node*)) { - if (self->last) - self->last = (_cx_node *)_clist_mergesort((clist_VOID_node *)self->last->next, - (clist_VOID_comp *)cmp); -} -#endif - -#if defined(i_extern) -/* Implement non-templated extern functions */ -// Singly linked list Mergesort implementation by Simon Tatham. O(n*log n). -// https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html -clist_VOID_node * -_clist_mergesort(clist_VOID_node *list, clist_VOID_comp* cmp) { - clist_VOID_node *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 || (qsize && q)) { - if (psize && (!(qsize && q) || 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 // i_extern // -------------------------- IMPLEMENTATION ------------------------- #if defined(i_implement) @@ -443,15 +378,30 @@ _cx_memb(_remove)(_cx_self* self, _cx_raw val) { return n; } #endif -#ifndef i_no_cmp -STC_DEF int -_cx_memb(_sort_cmp_)(const _cx_node* x, const _cx_node* y) { - const _cx_raw a = i_keyto((&x->value)); - const _cx_raw b = i_keyto((&y->value)); +#ifndef i_no_cmp +STC_DEF int _cx_memb(_sort_cmp_)(const _cx_value* x, const _cx_value* y) { + const _cx_raw a = i_keyto(x), b = i_keyto(y); return i_cmp((&a), (&b)); } + +STC_DEF bool _cx_memb(_sort_with)(_cx_self* self, int(*cmp)(const _cx_value*, const _cx_value*)) { + size_t len = 0, cap = 0; + _cx_value *a = NULL, *p = NULL; + _cx_iter i; + for (i = _cx_memb(_begin)(self); i.ref; _cx_memb(_next)(&i)) { + if (len == cap) { + if ((p = (_cx_value *)i_realloc(a, (cap += cap/2 + 4)*sizeof *a))) a = p; + else { i_free(a); return false; } + } + a[len++] = *i.ref; + } + qsort(a, len, sizeof *a, (int(*)(const void*, const void*))cmp); + for (i = _cx_memb(_begin)(self); i.ref; _cx_memb(_next)(&i), ++p) + *i.ref = *p; + i_free(a); return true; +} #endif // !c_no_cmp #endif // i_implement #define CLIST_H_INCLUDED -#include "priv/template.h" +#include "priv/template2.h" |