From 444088e81d590946c80909386dfcd6b926362949 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Wed, 1 Jun 2022 15:22:24 +0200 Subject: Added src/libstc.c which implements all non-templated functions (e.g. from cstr, csview, cbits, crandom), but also clist.h mergesort. - Linking with this object file eliminates the need to define i_implement in one file for these types (or i_extern for non-templated functions in templated container, currently only clist.h) --- examples/list.c | 6 ++- include/stc/cbits.h | 1 + include/stc/ccommon.h | 3 ++ include/stc/clist.h | 130 ++++++++++++++++++++++++------------------------- include/stc/crandom.h | 4 ++ include/stc/cstr.h | 1 + include/stc/csview.h | 1 + include/stc/template.h | 1 + src/libstc.c | 12 +++++ 9 files changed, 91 insertions(+), 68 deletions(-) create mode 100644 src/libstc.c diff --git a/examples/list.c b/examples/list.c index a0dbd49f..7d6d1a50 100644 --- a/examples/list.c +++ b/examples/list.c @@ -1,11 +1,13 @@ #include #include -#define i_implement -#include + +#define STC_IMPLEMENT +#define STC_EXTERN #define i_val double #define i_tag fx #include +#include int main() { int k; diff --git a/include/stc/cbits.h b/include/stc/cbits.h index 9c7081f7..b3f5ac4d 100644 --- a/include/stc/cbits.h +++ b/include/stc/cbits.h @@ -325,3 +325,4 @@ STC_DEF bool _cbits_disjoint(const uint64_t* set, const uint64_t* other, const s #undef i_header #undef i_implement #undef i_static +#undef i_exterm diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index 2ebcf7c1..b67fb598 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -261,6 +261,9 @@ STC_INLINE char* c_strnstrn(const char *s, const char *needle, # define STC_API static inline # define STC_DEF static inline #endif +#if defined(STC_EXTERN) +# define i_extern +#endif #if defined(i_static) || defined(STC_IMPLEMENT) # define i_implement #endif diff --git a/include/stc/clist.h b/include/stc/clist.h index 2cc74824..9380dc11 100644 --- a/include/stc/clist.h +++ b/include/stc/clist.h @@ -105,7 +105,7 @@ STC_API _cx_iter _cx_memb(_erase_range)(_cx_self* self, _cx_iter it1, _cx STC_API size_t _cx_memb(_remove)(_cx_self* self, _cx_raw val); STC_API _cx_iter _cx_memb(_find_in)(_cx_iter it1, _cx_iter it2, _cx_raw val); STC_API int _cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y); -STC_API void _cx_memb(_sort)(_cx_self* self); +STC_API int _cx_memb(_sort_cmp_)(const clist_VOID_node* x, const clist_VOID_node* y); #endif STC_API _cx_iter _cx_memb(_splice)(_cx_self* self, _cx_iter it, _cx_self* other); STC_API _cx_self _cx_memb(_split_off)(_cx_self* self, _cx_iter it1, _cx_iter it2); @@ -196,8 +196,70 @@ STC_INLINE _cx_value* _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 void +_cx_memb(_sort)(_cx_self* self) { + extern clist_VOID_node* + _clist_mergesort(clist_VOID_node *list, int (*cmp)(const clist_VOID_node*, const clist_VOID_node*)); + + if (self->last) + self->last = (_cx_node *)_clist_mergesort((clist_VOID_node *)self->last->next, _cx_memb(_sort_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, int (*cmp)(const clist_VOID_node*, const clist_VOID_node*)) { + 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 > 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 // i_extern + // -------------------------- IMPLEMENTATION ------------------------- #if defined(i_implement) @@ -343,22 +405,13 @@ _cx_memb(_remove)(_cx_self* self, _cx_raw val) { return n; } -static int +STC_DEF int _cx_memb(_sort_cmp_)(const clist_VOID_node* x, const clist_VOID_node* y) { const _cx_raw a = i_keyto((&((const _cx_node *) x)->value)); const _cx_raw b = i_keyto((&((const _cx_node *) y)->value)); return i_cmp((&a), (&b)); } -static clist_VOID_node* -_clist_mergesort(clist_VOID_node *list, int (*cmp)(const clist_VOID_node*, const clist_VOID_node*)); - -STC_DEF void -_cx_memb(_sort)(_cx_self* self) { - if (self->last) - self->last = (_cx_node *)_clist_mergesort((clist_VOID_node *)self->last->next, _cx_memb(_sort_cmp_)); -} - STC_DEF int _cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y) { const _cx_raw rx = i_keyto(x); @@ -366,61 +419,6 @@ _cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y) { return i_cmp((&rx), (&ry)); } #endif // !c_no_cmp - -#ifndef CLIST_H_INCLUDED - -#if !c_option(c_no_cmp) -// Singly linked list Mergesort implementation by Simon Tatham. O(n*log n). -// https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html -static clist_VOID_node * -_clist_mergesort(clist_VOID_node *list, int (*cmp)(const clist_VOID_node*, const clist_VOID_node*)) { - 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 > 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 // !c_no_cmp -#endif // !CLIST_H_INCLUDED #endif // i_implement #define CLIST_H_INCLUDED #include "template.h" diff --git a/include/stc/crandom.h b/include/stc/crandom.h index a3f68279..88ac3af6 100644 --- a/include/stc/crandom.h +++ b/include/stc/crandom.h @@ -189,3 +189,7 @@ STC_DEF double stc64_normalf(stc64_t* rng, stc64_normalf_t* dist) { #endif #endif #undef i_opt +#undef i_static +#undef i_header +#undef i_implement +#undef i_extern \ No newline at end of file diff --git a/include/stc/cstr.h b/include/stc/cstr.h index 41e29a84..7dabd0c0 100644 --- a/include/stc/cstr.h +++ b/include/stc/cstr.h @@ -551,4 +551,5 @@ STC_DEF int cstr_printf(cstr* self, const char* fmt, ...) { #undef i_header #undef i_static #undef i_implement +#undef i_extern #endif // !STC_CSTR_V1 diff --git a/include/stc/csview.h b/include/stc/csview.h index 8508db4f..36e6ad7b 100644 --- a/include/stc/csview.h +++ b/include/stc/csview.h @@ -216,3 +216,4 @@ csview_token(csview sv, csview sep, size_t* start) { #undef i_header #undef i_implement #undef i_static +#undef i_extern diff --git a/include/stc/template.h b/include/stc/template.h index db50a6ca..9bf7e378 100644 --- a/include/stc/template.h +++ b/include/stc/template.h @@ -284,6 +284,7 @@ #undef i_header #undef i_implement #undef i_static +#undef i_extern #undef _i_prefix #undef _i_has_from diff --git a/src/libstc.c b/src/libstc.c new file mode 100644 index 00000000..0c78272d --- /dev/null +++ b/src/libstc.c @@ -0,0 +1,12 @@ +#define STC_EXTERN // implement common extern, non-templated functions, e.g. _clist_mergesort(). +#define STC_HEADER // don't implement clist_int itself, just dummy declare it. + +#define i_val int +#include "../include/stc/clist.h" + +#define STC_IMPLEMENT // implement the following. + +#include "../include/stc/cstr.h" +#include "../include/stc/csview.h" +#include "../include/stc/cbits.h" +#include "../include/stc/crandom.h" -- cgit v1.2.3