From 1ea2043900095c3548d30ba4520fda6f854263c1 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 5 Feb 2021 23:03:50 +0100 Subject: Rewrote to use c_container_of() instead of size_t offset. --- benchmarks/cmap_benchmark2.cpp | 2 +- stc/ccommon.h | 4 +- stc/cdeq.h | 88 +++++++++++++++++++++--------------------- stc/cmap.h | 13 +++---- stc/csmap.h | 80 ++++++++++++++++++-------------------- stc/cstr.h | 70 +++++++++++++-------------------- stc/cvec.h | 83 +++++++++++++++++++-------------------- 7 files changed, 159 insertions(+), 181 deletions(-) diff --git a/benchmarks/cmap_benchmark2.cpp b/benchmarks/cmap_benchmark2.cpp index be8a47a6..4d6db980 100644 --- a/benchmarks/cmap_benchmark2.cpp +++ b/benchmarks/cmap_benchmark2.cpp @@ -228,7 +228,7 @@ static void ins_and_access_s(picobench::state& s) map.erase(it); } } - s.set_result(result); + s.set_result(result + map.size()); } static void ins_and_access_cmap_s(picobench::state& s) diff --git a/stc/ccommon.h b/stc/ccommon.h index bea528bc..acf6e1e6 100644 --- a/stc/ccommon.h +++ b/stc/ccommon.h @@ -61,9 +61,9 @@ #define _c_OVERLOAD_SELECT(NAME, NUM) _c_CAT( NAME ## _, NUM) #define c_MACRO_OVERLOAD(NAME, ...) _c_OVERLOAD_SELECT(NAME, _c_VA_ARG_SIZE(__VA_ARGS__))(__VA_ARGS__) -#define c_static_assert(cond, msg) typedef char static_assert_##msg[(cond) ? 1 : -1] +#define c_static_assert(cond) typedef char _static_assert_[(cond) ? 1 : -1] #define c_container_of(ptr, type, member) \ - ((type *)((char *)(ptr) - offsetof(type, member))) + ((type *)((char *)(ptr) - offsetof(type, member))) #define c_new(...) c_MACRO_OVERLOAD(c_new, __VA_ARGS__) #define c_new_1(T) ((T *) c_malloc(sizeof(T))) diff --git a/stc/cdeq.h b/stc/cdeq.h index 2ce7d398..8cce8188 100644 --- a/stc/cdeq.h +++ b/stc/cdeq.h @@ -45,17 +45,20 @@ cdeq_##X##_value_t *base, *data; \ } cdeq_##X +struct cdeq_rep { size_t size, cap; void* base[]; }; +#define _cdeq_rep(self) c_container_of((self)->base, struct cdeq_rep, base) + #define using_cdeq_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue) \ typedefs_cdeq(X, Value, RawValue); \ \ STC_API cdeq_##X \ cdeq_##X##_init(void); \ STC_INLINE bool \ - cdeq_##X##_empty(cdeq_##X deq) {return !_cdeq_size(&deq);} \ + cdeq_##X##_empty(cdeq_##X deq) {return !_cdeq_rep(&deq)->size;} \ STC_INLINE size_t \ - cdeq_##X##_size(cdeq_##X deq) {return _cdeq_size(&deq);} \ + cdeq_##X##_size(cdeq_##X deq) {return _cdeq_rep(&deq)->size;} \ STC_INLINE size_t \ - cdeq_##X##_capacity(cdeq_##X deq) {return _cdeq_cap(&deq);} \ + cdeq_##X##_capacity(cdeq_##X deq) {return _cdeq_rep(&deq)->cap;} \ STC_INLINE Value \ cdeq_##X##_value_from_raw(RawValue raw) {return valueFromRaw(raw);} \ STC_INLINE cdeq_##X##_value_t \ @@ -102,7 +105,7 @@ } \ STC_INLINE void \ cdeq_##X##_pop_back(cdeq_##X* self) { \ - valueDestroy(&self->data[--_cdeq_size(self)]); \ + valueDestroy(&self->data[--_cdeq_rep(self)->size]); \ } \ \ STC_API void \ @@ -114,7 +117,7 @@ STC_INLINE void \ cdeq_##X##_pop_front(cdeq_##X* self) { \ valueDestroy(self->data++); \ - --_cdeq_size(self); \ + --_cdeq_rep(self)->size; \ } \ \ STC_API cdeq_##X##_iter_t \ @@ -165,10 +168,10 @@ STC_INLINE cdeq_##X##_value_t* \ cdeq_##X##_front(cdeq_##X* self) {return self->data;} \ STC_INLINE cdeq_##X##_value_t* \ - cdeq_##X##_back(cdeq_##X* self) {return self->data + _cdeq_size(self) - 1;} \ + cdeq_##X##_back(cdeq_##X* self) {return self->data + _cdeq_rep(self)->size - 1;} \ STC_INLINE cdeq_##X##_value_t* \ cdeq_##X##_at(cdeq_##X* self, size_t i) { \ - assert(i < _cdeq_size(self)); \ + assert(i < _cdeq_rep(self)->size); \ return self->data + i; \ } \ \ @@ -180,7 +183,7 @@ } \ STC_INLINE void \ cdeq_##X##_sort(cdeq_##X* self) { \ - cdeq_##X##_sort_with(self, 0, _cdeq_size(self), cdeq_##X##_value_compare); \ + cdeq_##X##_sort_with(self, 0, _cdeq_rep(self)->size, cdeq_##X##_value_compare); \ } \ \ STC_INLINE cdeq_##X##_iter_t \ @@ -189,7 +192,7 @@ } \ STC_INLINE cdeq_##X##_iter_t \ cdeq_##X##_end(const cdeq_##X* self) { \ - cdeq_##X##_iter_t it = {self->data + _cdeq_size(self)}; return it; \ + cdeq_##X##_iter_t it = {self->data + _cdeq_rep(self)->size}; return it; \ } \ STC_INLINE void \ cdeq_##X##_next(cdeq_##X##_iter_t* it) {++it->ref;} \ @@ -204,66 +207,73 @@ /* -------------------------- IMPLEMENTATION ------------------------- */ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) + +static struct cdeq_rep _cdeq_inits = {0, 0}; +#define _cdeq_nfront(self) ((self)->data - (self)->base) +static inline double _minf(double x, double y) {return x < y ? x : y;} +static inline double _maxf(double x, double y) {return x > y ? x : y;} + #define _c_implement_cdeq_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue) \ \ STC_DEF cdeq_##X \ cdeq_##X##_init(void) { \ - cdeq_##X##_value_t *t = (cdeq_##X##_value_t *) (_cdeq_inits + 2); \ - cdeq_##X deq = {t, t}; return deq; \ + cdeq_##X##_value_t *b = (cdeq_##X##_value_t *) _cdeq_inits.base; \ + cdeq_##X deq = {b, b}; return deq; \ } \ \ STC_DEF void \ cdeq_##X##_push_n(cdeq_##X *self, const cdeq_##X##_rawvalue_t arr[], size_t n) { \ _cdeq_##X##_expand(self, n, false); \ - cdeq_##X##_value_t* p = self->data + _cdeq_size(self); \ + cdeq_##X##_value_t* p = self->data + _cdeq_rep(self)->size; \ for (size_t i=0; i < n; ++i) *p++ = valueFromRaw(arr[i]); \ - _cdeq_size(self) += n; \ + _cdeq_rep(self)->size += n; \ } \ \ STC_DEF void \ cdeq_##X##_clear(cdeq_##X* self) { \ cdeq_##X##_value_t* p = self->data; if (p) { \ - for (cdeq_##X##_value_t* q = p + _cdeq_size(self); p != q; ++p) \ + for (cdeq_##X##_value_t* q = p + _cdeq_rep(self)->size; p != q; ++p) \ valueDestroy(p); \ - _cdeq_size(self) = 0; \ + _cdeq_rep(self)->size = 0; \ } \ } \ STC_DEF void \ cdeq_##X##_del(cdeq_##X* self) { \ cdeq_##X##_clear(self); \ - if (_cdeq_alloced(self) != _cdeq_inits) \ - c_free(_cdeq_alloced(self)); \ + if (_cdeq_rep(self)->cap) \ + c_free(_cdeq_rep(self)); \ } \ \ STC_DEF void \ _cdeq_##X##_expand(cdeq_##X* self, size_t n, bool at_front) { \ - size_t len = _cdeq_size(self), cap = _cdeq_cap(self); \ + struct cdeq_rep* rep = _cdeq_rep(self); \ + size_t len = rep->size, cap = rep->cap; \ size_t nfront = self->data - self->base, nback = cap - (nfront + len); \ if (at_front && nfront >= n || !at_front && nback >= n) \ return; \ if ((len + n)*1.3 > cap) { \ cap = (len + n + 6)*1.8; \ - size_t* rep = (size_t *) c_realloc(_cdeq_alloced(self) != _cdeq_inits ? _cdeq_alloced(self) : NULL, \ - 2*sizeof(size_t) + cap*sizeof(Value)); \ - rep[0] = len, rep[1] = cap; \ - self->base = (cdeq_##X##_value_t *) (rep + 2); \ + rep = (struct cdeq_rep*) c_realloc(rep->cap ? rep : NULL, \ + sizeof(struct cdeq_rep) + cap*sizeof(Value)); \ + rep->size = len, rep->cap = cap; \ + self->base = (cdeq_##X##_value_t *) rep->base; \ self->data = self->base + nfront; \ _cdeq_##X##_expand(self, n, at_front); \ return; \ } \ size_t unused = cap - (len + n); \ - size_t pos = at_front ? c_maxf(unused*0.5, (float) unused - nback) + n \ - : c_minf(unused*0.5, nfront); \ + size_t pos = at_front ? _maxf(unused*0.5, (float) unused - nback) + n \ + : _minf(unused*0.5, nfront); \ self->data = (cdeq_##X##_value_t *) memmove(self->base + pos, self->data, len*sizeof(Value)); \ } \ \ STC_DEF void \ cdeq_##X##_resize(cdeq_##X* self, size_t size, Value null_val) { \ _cdeq_##X##_expand(self, size, false); \ - size_t i, n = _cdeq_size(self); \ + size_t i, n = _cdeq_rep(self)->size; \ for (i=size; idata + i); \ for (i=n; idata[i] = null_val; \ - if (self->data) _cdeq_size(self) = size; \ + if (self->data) _cdeq_rep(self)->size = size; \ } \ \ STC_DEF void \ @@ -271,18 +281,18 @@ if (self->data == self->base) \ _cdeq_##X##_expand(self, 1, true); \ *--self->data = value; \ - ++_cdeq_size(self); \ + ++_cdeq_rep(self)->size; \ } \ STC_DEF void \ cdeq_##X##_push_back(cdeq_##X* self, Value value) { \ - if (_cdeq_nfront(self) + _cdeq_size(self) == _cdeq_cap(self)) \ + if (_cdeq_nfront(self) + _cdeq_rep(self)->size == _cdeq_rep(self)->cap) \ _cdeq_##X##_expand(self, 1, false); \ - self->data[_cdeq_size(self)++] = value; \ + self->data[_cdeq_rep(self)->size++] = value; \ } \ \ STC_DEF cdeq_##X \ cdeq_##X##_clone(cdeq_##X vec) { \ - size_t len = _cdeq_size(&vec); \ + size_t len = _cdeq_rep(&vec)->size; \ cdeq_##X out = cdeq_##X##_with_capacity(len); \ cdeq_##X##_insert_range_p(&out, out.data, vec.data, vec.data + len); \ return out; \ @@ -291,7 +301,7 @@ STC_DEF cdeq_##X##_iter_t \ cdeq_##X##_insert_range_p(cdeq_##X* self, cdeq_##X##_value_t* pos, \ const cdeq_##X##_value_t* first, const cdeq_##X##_value_t* finish) { \ - size_t n = finish - first, idx = pos - self->data, size = _cdeq_size(self); \ + size_t n = finish - first, idx = pos - self->data, size = _cdeq_rep(self)->size; \ bool at_front = (idx < size/2); \ _cdeq_##X##_expand(self, n, at_front); \ if (at_front) { \ @@ -302,7 +312,7 @@ memmove(pos + n, pos, (size - idx)*sizeof(Value)); \ } \ cdeq_##X##_iter_t it = {pos}; \ - if (n) _cdeq_size(self) += n; \ + if (n) _cdeq_rep(self)->size += n; \ while (first != finish) \ *pos++ = valueFromRaw(valueToRaw(first++)); \ return it; \ @@ -312,11 +322,11 @@ cdeq_##X##_erase_range_p(cdeq_##X* self, cdeq_##X##_value_t* first, cdeq_##X##_value_t* finish) { \ intptr_t len = finish - first; \ if (len > 0) { \ - cdeq_##X##_value_t* p = first, *end = self->data + _cdeq_size(self); \ + cdeq_##X##_value_t* p = first, *end = self->data + _cdeq_rep(self)->size; \ while (p != finish) valueDestroy(p++); \ if (first == self->data) self->data += len; \ else memmove(first, finish, (end - finish) * sizeof(Value)); \ - _cdeq_size(self) -= len; \ + _cdeq_rep(self)->size -= len; \ } \ cdeq_##X##_iter_t it = {first}; return it; \ } \ @@ -341,9 +351,6 @@ return valueCompareRaw(&rx, &ry); \ } -static size_t _cdeq_inits[2] = {0, 0}; -#define _cdeq_alloced(self) (((size_t *) (self)->base) - 2) - #else #define _c_implement_cdeq_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue) #endif @@ -357,11 +364,4 @@ static size_t _cdeq_inits[2] = {0, 0}; typedef int(*_cdeq_cmp)(const void*, const void*); STC_EXTERN_IMPORT void qsort(void *start, size_t nitems, size_t size, _cdeq_cmp cmp); -#define _cdeq_size(self) ((size_t *) (self)->base)[-2] -#define _cdeq_cap(self) ((size_t *) (self)->base)[-1] -#define _cdeq_nfront(self) ((self)->data - (self)->base) - -static inline double c_minf(double x, double y) { return x < y ? x : y; } -static inline double c_maxf(double x, double y) { return x > y ? x : y; } - #endif diff --git a/stc/cmap.h b/stc/cmap.h index 888718d4..5123dd2b 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -56,12 +56,6 @@ int main(void) { #include #define _cmap_inits {NULL, NULL, 0, 0, 0.15f, 0.85f} - -/* https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction */ -#define chash_reduce(x, N) ((uint32_t) (((uint64_t) (x) * (N)) >> 32)) -#define chash_entry_index(h, entryPtr) ((entryPtr) - (h).table) - -enum {chash_HASH = 0x7f, chash_USED = 0x80}; typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; #define using_cmap(...) \ @@ -313,6 +307,11 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; /* -------------------------- IMPLEMENTATION ------------------------- */ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) + +#define chash_reduce(x, N) ((uint32_t) (((uint64_t) (x) * (N)) >> 32)) +#define chash_entry_index(h, entryPtr) ((entryPtr) - (h).table) +enum {chash_HASH = 0x7f, chash_USED = 0x80}; + #define _implement_CHASH(X, C, Key, Mapped, keyEqualsRaw, keyHashRaw, mappedDel, keyDel, \ keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ STC_DEF C##_##X \ @@ -447,8 +446,6 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; C##_##X##_reserve(self, k*1.2); \ } -/* https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ */ - STC_DEF uint32_t c_default_hash(const void *data, size_t len) { const volatile uint16_t *key = (const uint16_t *) data; uint64_t x = *key++ * 11400714819323198485llu; diff --git a/stc/csmap.h b/stc/csmap.h index 3755e2ca..ac51589c 100644 --- a/stc/csmap.h +++ b/stc/csmap.h @@ -150,6 +150,9 @@ int main(void) { C##_##X##_size_t _tn, _st[48]; \ } C##_##X##_iter_t +struct csmap_rep { size_t root, disp, size, cap; void* data[]; }; +#define _csmap_rep(self) c_container_of((self)->data, struct csmap_rep, data) + #define _using_AATREE(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \ keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ _using_AATREE_types(X, C, Key, Mapped); \ @@ -182,9 +185,9 @@ int main(void) { return x; \ } \ STC_INLINE bool \ - C##_##X##_empty(C##_##X m) {return _smap_size(&m) == 0;} \ + C##_##X##_empty(C##_##X m) {return _csmap_rep(&m)->size == 0;} \ STC_INLINE size_t \ - C##_##X##_size(C##_##X m) {return _smap_size(&m);} \ + C##_##X##_size(C##_##X m) {return _csmap_rep(&m)->size;} \ STC_API void \ C##_##X##_del(C##_##X* self); \ STC_INLINE void \ @@ -267,7 +270,7 @@ int main(void) { \ STC_INLINE C##_##X##_iter_t \ C##_##X##_begin(C##_##X* self) { \ - C##_##X##_iter_t it = {NULL, self->data, 0, (C##_##X##_size_t) _smap_root(self)}; \ + C##_##X##_iter_t it = {NULL, self->data, 0, (C##_##X##_size_t) _csmap_rep(self)->root}; \ if (it._tn) C##_##X##_next(&it); \ return it; \ } \ @@ -293,49 +296,52 @@ int main(void) { /* -------------------------- IMPLEMENTATION ------------------------- */ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) +static struct csmap_rep _smap_inits = {0, 0, 0, 0}; + #define _implement_AATREE(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \ keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ STC_DEF C##_##X \ C##_##X##_init(void) { \ - C##_##X m = {(C##_##X##_node_t *) (_smap_inits + 4)}; \ + C##_##X m = {(C##_##X##_node_t *) _smap_inits.data}; \ return m; \ } \ \ STC_DEF C##_##X##_value_t* \ C##_##X##_front(C##_##X* self) { \ C##_##X##_node_t *d = self->data; \ - C##_##X##_size_t tn = (C##_##X##_size_t) _smap_root(self); \ + C##_##X##_size_t tn = (C##_##X##_size_t) _csmap_rep(self)->root; \ while (d[tn].link[0]) tn = d[tn].link[0]; \ return &d[tn].value; \ } \ STC_DEF C##_##X##_value_t* \ C##_##X##_back(C##_##X* self) { \ C##_##X##_node_t *d = self->data; \ - C##_##X##_size_t tn = (C##_##X##_size_t) _smap_root(self); \ + C##_##X##_size_t tn = (C##_##X##_size_t) _csmap_rep(self)->root; \ while (d[tn].link[1]) tn = d[tn].link[1]; \ return &d[tn].value; \ } \ \ STC_DEF void \ C##_##X##_reserve(C##_##X* self, size_t cap) { \ - C##_##X##_size_t oldcap = _smap_cap(self); \ + struct csmap_rep* rep = _csmap_rep(self); \ + C##_##X##_size_t oldcap = rep->cap; \ if (cap > oldcap) { \ - size_t* rep = (size_t *) c_realloc(oldcap ? _smap_rep(self) : NULL, \ - 4*sizeof(size_t) + (cap + 1)*sizeof(C##_##X##_node_t)); \ + rep = (struct csmap_rep*) c_realloc(oldcap ? rep : NULL, \ + sizeof(struct csmap_rep) + (cap + 1)*sizeof(C##_##X##_node_t)); \ if (oldcap == 0) \ - memset(rep, 0, sizeof(size_t)*4 + sizeof(C##_##X##_node_t)); \ - rep[_smap_CAP] = cap; \ - self->data = (C##_##X##_node_t *) (rep + 4); \ + memset(rep, 0, sizeof(struct csmap_rep) + sizeof(C##_##X##_node_t)); \ + rep->cap = cap; \ + self->data = (C##_##X##_node_t *) rep->data; \ } \ } \ \ STC_DEF C##_##X##_size_t \ C##_##X##_node_new_(C##_##X* self) { \ - size_t tn, *rep = _smap_rep(self); \ - if (rep[_smap_DISP]) { \ - tn = rep[_smap_DISP]; \ - rep[_smap_DISP] = self->data[tn].link[1]; \ - } else if ((tn = rep[_smap_SIZE] + 1) > rep[_smap_CAP]) \ + size_t tn; struct csmap_rep *rep = _csmap_rep(self); \ + if (rep->disp) { \ + tn = rep->disp; \ + rep->disp = self->data[tn].link[1]; \ + } else if ((tn = rep->size + 1) > rep->cap) \ C##_##X##_reserve(self, 4 + tn*3/2); \ C##_##X##_node_t* dn = &self->data[tn]; \ dn->link[0] = dn->link[1] = 0; dn->level = 1; \ @@ -344,15 +350,15 @@ int main(void) { \ STC_DEF void \ C##_##X##_node_del_(C##_##X##_node_t *d, C##_##X##_size_t tn) { \ - size_t *rep = ((size_t *) d) - 4; \ + struct csmap_rep *rep = c_container_of(d, struct csmap_rep, data); \ keyDel(KEY_REF_##C(&d[tn].value)); \ - d[tn].link[1] = (C##_##X##_size_t) rep[_smap_DISP]; \ - rep[_smap_DISP] = tn; \ + d[tn].link[1] = (C##_##X##_size_t) rep->disp; \ + rep->disp = tn; \ } \ \ STC_DEF C##_##X##_value_t* \ C##_##X##_find_it(const C##_##X* self, C##_##X##_rawkey_t rkey, C##_##X##_iter_t* out) { \ - C##_##X##_size_t tn = _smap_root(self); \ + C##_##X##_size_t tn = _csmap_rep(self)->root; \ C##_##X##_node_t *d = out->_d = self->data; \ out->_top = 0; \ while (tn) { \ @@ -432,9 +438,9 @@ int main(void) { STC_DEF C##_##X##_result_t \ C##_##X##_insert_key(C##_##X* self, RawKey rkey) { \ C##_##X##_result_t res = {NULL, false}; \ - C##_##X##_size_t tn = C##_##X##_insert_key_i_(self, (C##_##X##_size_t) _smap_root(self), &rkey, &res); \ - _smap_root(self) = tn; \ - _smap_size(self) += res.second; \ + C##_##X##_size_t tn = C##_##X##_insert_key_i_(self, (C##_##X##_size_t) _csmap_rep(self)->root, &rkey, &res); \ + _csmap_rep(self)->root = tn; \ + _csmap_rep(self)->size += res.second; \ return res; \ } \ \ @@ -476,8 +482,8 @@ int main(void) { STC_DEF int \ C##_##X##_erase(C##_##X* self, RawKey rkey) { \ int erased = 0; \ - C##_##X##_size_t root = C##_##X##_erase_r_(self->data, (C##_##X##_size_t) _smap_root(self), &rkey, &erased); \ - if (erased) {_smap_root(self) = root; --_smap_size(self);} \ + C##_##X##_size_t root = C##_##X##_erase_r_(self->data, (C##_##X##_size_t) _csmap_rep(self)->root, &rkey, &erased); \ + if (erased) {_csmap_rep(self)->root = root; --_csmap_rep(self)->size;} \ return erased; \ } \ \ @@ -494,9 +500,9 @@ int main(void) { } \ STC_DEF C##_##X \ C##_##X##_clone(C##_##X bst) { \ - C##_##X clone = C##_##X##_with_capacity(_smap_size(&bst)); \ - C##_##X##_size_t root = C##_##X##_clone_r_(&clone, bst.data, (C##_##X##_size_t) _smap_root(&bst)); \ - _smap_root(&clone) = root; \ + C##_##X clone = C##_##X##_with_capacity(_csmap_rep(&bst)->size); \ + C##_##X##_size_t root = C##_##X##_clone_r_(&clone, bst.data, (C##_##X##_size_t) _csmap_rep(&bst)->root); \ + _csmap_rep(&clone)->root = root; \ return clone; \ } \ \ @@ -510,25 +516,15 @@ int main(void) { } \ STC_DEF void \ C##_##X##_del(C##_##X* self) { \ - if (_smap_root(self)) { \ - C##_##X##_del_r_(self->data, (C##_##X##_size_t) _smap_root(self)); \ - c_free(_smap_rep(self)); \ + if (_csmap_rep(self)->root) { \ + C##_##X##_del_r_(self->data, (C##_##X##_size_t) _csmap_rep(self)->root); \ + c_free(_csmap_rep(self)); \ } \ } -_using_AATREE_types(_, csmap, int, int); -static size_t _smap_inits[4] = {0, 0, 0, 0}; - #else #define _implement_AATREE(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \ keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) #endif -enum {_smap_ROOT=0, _smap_DISP=1, _smap_SIZE=2, _smap_CAP=3}; -#define _smap_rep(self) (((size_t *)(self)->data) - 4) -#define _smap_root(self) _smap_rep(self)[_smap_ROOT] -#define _smap_disp(self) _smap_rep(self)[_smap_DISP] -#define _smap_size(self) _smap_rep(self)[_smap_SIZE] -#define _smap_cap(self) _smap_rep(self)[_smap_CAP] - #endif diff --git a/stc/cstr.h b/stc/cstr.h index 2a49bbda..369d6034 100644 --- a/stc/cstr.h +++ b/stc/cstr.h @@ -35,43 +35,26 @@ typedef struct { char *ref; } cstr_iter_t; typedef char cstr_value_t; #define cstr_npos ((size_t) (-1)) +STC_API cstr_t cstr_from_n(const char* str, size_t len); +STC_API cstr_t cstr_from_fmt(const char* fmt, ...); +STC_API void cstr_fmt(cstr_t* self, const char* fmt, ...); +STC_API size_t cstr_reserve(cstr_t* self, size_t cap); +STC_API void cstr_resize(cstr_t* self, size_t len, char fill); +STC_API cstr_t* cstr_assign_n(cstr_t* self, const char* str, size_t len); +STC_API cstr_t* cstr_append_n(cstr_t* self, const char* str, size_t len); +STC_API void cstr_replace_n(cstr_t* self, size_t pos, size_t len, const char* str, size_t n); +STC_API void cstr_erase_n(cstr_t* self, size_t pos, size_t n); +STC_API bool cstr_getdelim(cstr_t *self, int delim, FILE *stream); +STC_API size_t cstr_find(cstr_t s, const char* needle); +STC_API size_t cstr_find_n(cstr_t s, const char* needle, size_t pos, size_t nlen); +STC_API size_t cstr_ifind_n(cstr_t s, const char* needle, size_t pos, size_t nlen); + +STC_API int c_strncasecmp(const char* s1, const char* s2, size_t n); +STC_API char* c_strnfind(const char* s, const char* needle, size_t nmax); +STC_DEF char* c_istrnfind(const char* s, const char* needle, size_t nmax); + struct cstr_rep { size_t size, cap; char str[sizeof(size_t)]; }; #define _cstr_rep(self) c_container_of((self)->str, struct cstr_rep, str) - -STC_API cstr_t -cstr_from_n(const char* str, size_t len); -STC_API cstr_t -cstr_from_fmt(const char* fmt, ...); -STC_API void -cstr_fmt(cstr_t* self, const char* fmt, ...); -STC_API size_t -cstr_reserve(cstr_t* self, size_t cap); -STC_API void -cstr_resize(cstr_t* self, size_t len, char fill); -STC_API cstr_t* -cstr_assign_n(cstr_t* self, const char* str, size_t len); -STC_API cstr_t* -cstr_append_n(cstr_t* self, const char* str, size_t len); -STC_API void -cstr_replace_n(cstr_t* self, size_t pos, size_t len, const char* str, size_t n); -STC_API void -cstr_erase_n(cstr_t* self, size_t pos, size_t n); -STC_API bool -cstr_getdelim(cstr_t *self, int delim, FILE *stream); -STC_API size_t -cstr_find(cstr_t s, const char* needle); -STC_API size_t -cstr_find_n(cstr_t s, const char* needle, size_t pos, size_t nlen); -STC_API size_t -cstr_ifind_n(cstr_t s, const char* needle, size_t pos, size_t nlen); - -STC_API int -c_strncasecmp(const char* s1, const char* s2, size_t n); -STC_API char* -c_strnfind(const char* s, const char* needle, size_t nmax); -STC_DEF char* -c_istrnfind(const char* s, const char* needle, size_t nmax); - /* optimal memory: based on malloc_usable_size() sequence: 24, 40, 56, ... */ #define _cstr_opt_mem(cap) ((((offsetof(struct cstr_rep, str) + (cap) + 8)>>4)<<4) + 8) /* optimal string capacity: 7, 23, 39, ... */ @@ -106,12 +89,10 @@ STC_INLINE cstr_t cstr_from(const char* str) { return cstr_from_n(str, strlen(str)); } - STC_INLINE cstr_t cstr_clone(cstr_t s) { return cstr_from_n(s.str, _cstr_rep(&s)->size); } - STC_INLINE void cstr_clear(cstr_t* self) { self->str[_cstr_rep(self)->size = 0] = '\0'; @@ -158,7 +139,6 @@ STC_INLINE void cstr_push_back(cstr_t* self, char value) { cstr_append_n(self, &value, 1); } - STC_INLINE void cstr_pop_back(cstr_t* self) { self->str[ --_cstr_rep(self)->size ] = '\0'; @@ -186,10 +166,14 @@ cstr_getline(cstr_t *self, FILE *stream) { /* readonly */ -STC_INLINE size_t cstr_size(cstr_t s) {return _cstr_rep(&s)->size;} -STC_INLINE size_t cstr_capacity(cstr_t s) {return _cstr_rep(&s)->cap;} -STC_INLINE size_t cstr_empty(cstr_t s) {return _cstr_rep(&s)->size == 0;} -STC_INLINE size_t cstr_length(cstr_t s) { return _cstr_rep(&s)->size; } +STC_INLINE size_t +cstr_size(cstr_t s) {return _cstr_rep(&s)->size;} +STC_INLINE size_t +cstr_capacity(cstr_t s) {return _cstr_rep(&s)->cap;} +STC_INLINE size_t +cstr_empty(cstr_t s) {return _cstr_rep(&s)->size == 0;} +STC_INLINE size_t +cstr_length(cstr_t s) { return _cstr_rep(&s)->size; } STC_INLINE bool cstr_equals(cstr_t s1, const char* str) { @@ -258,7 +242,7 @@ uint32_t cstr_hash_raw(const char* const* p, size_t none) { #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -STC_LIBRARY_ONLY( struct cstr_rep _cstr_nullrep = {0, 0, {0}}; +STC_LIBRARY_ONLY( static struct cstr_rep _cstr_nullrep = {0, 0, {0}}; const cstr_t cstr_inits = {_cstr_nullrep.str}; ) STC_DEF size_t diff --git a/stc/cvec.h b/stc/cvec.h index edfd77e9..77ed6c09 100644 --- a/stc/cvec.h +++ b/stc/cvec.h @@ -44,6 +44,9 @@ typedef struct { \ cvec_##X##_value_t* data; \ } cvec_##X + +struct cvec_rep { size_t size, cap; void* data[]; }; +#define _cvec_rep(self) c_container_of((self)->data, struct cvec_rep, data) #define using_cvec_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue) \ typedefs_cvec(X, Value, RawValue); \ @@ -51,11 +54,11 @@ STC_API cvec_##X \ cvec_##X##_init(void); \ STC_INLINE size_t \ - cvec_##X##_size(cvec_##X vec) { return _cvec_size(&vec); } \ + cvec_##X##_size(cvec_##X vec) { return _cvec_rep(&vec)->size; } \ STC_INLINE size_t \ - cvec_##X##_capacity(cvec_##X vec) { return _cvec_cap(&vec); } \ + cvec_##X##_capacity(cvec_##X vec) { return _cvec_rep(&vec)->cap; } \ STC_INLINE bool \ - cvec_##X##_empty(cvec_##X vec) {return !_cvec_size(&vec);} \ + cvec_##X##_empty(cvec_##X vec) {return !_cvec_rep(&vec)->size;} \ STC_INLINE Value \ cvec_##X##_value_from_raw(RawValue raw) {return valueFromRaw(raw);} \ STC_INLINE cvec_##X##_value_t \ @@ -101,7 +104,7 @@ } \ STC_INLINE void \ cvec_##X##_pop_back(cvec_##X* self) { \ - valueDestroy(&self->data[--_cvec_size(self)]); \ + valueDestroy(&self->data[--_cvec_rep(self)->size]); \ } \ \ STC_API cvec_##X##_iter_t \ @@ -152,10 +155,10 @@ STC_INLINE cvec_##X##_value_t* \ cvec_##X##_front(cvec_##X* self) {return self->data;} \ STC_INLINE cvec_##X##_value_t* \ - cvec_##X##_back(cvec_##X* self) {return self->data + _cvec_size(self) - 1;} \ + cvec_##X##_back(cvec_##X* self) {return self->data + _cvec_rep(self)->size - 1;} \ STC_INLINE cvec_##X##_value_t* \ cvec_##X##_at(cvec_##X* self, size_t i) { \ - assert(i < _cvec_size(self)); \ + assert(i < _cvec_rep(self)->size); \ return self->data + i; \ } \ \ @@ -167,7 +170,7 @@ } \ STC_INLINE void \ cvec_##X##_sort(cvec_##X* self) { \ - cvec_##X##_sort_with(self, 0, _cvec_size(self), cvec_##X##_value_compare); \ + cvec_##X##_sort_with(self, 0, _cvec_rep(self)->size, cvec_##X##_value_compare); \ } \ \ STC_INLINE cvec_##X##_iter_t \ @@ -176,7 +179,7 @@ } \ STC_INLINE cvec_##X##_iter_t \ cvec_##X##_end(const cvec_##X* self) { \ - cvec_##X##_iter_t it = {self->data + _cvec_size(self)}; return it; \ + cvec_##X##_iter_t it = {self->data + _cvec_rep(self)->size}; return it; \ } \ STC_INLINE void \ cvec_##X##_next(cvec_##X##_iter_t* it) {++it->ref;} \ @@ -191,66 +194,70 @@ /* -------------------------- IMPLEMENTATION ------------------------- */ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) +static struct cvec_rep _cvec_inits = {0, 0}; + #define _c_implement_cvec_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue) \ \ STC_DEF cvec_##X \ cvec_##X##_init(void) { \ - cvec_##X vec = {(cvec_##X##_value_t *) (_cvec_inits + 2)}; return vec; \ + cvec_##X vec = {(cvec_##X##_value_t *) _cvec_inits.data}; return vec; \ } \ \ STC_DEF void \ cvec_##X##_push_n(cvec_##X *self, const cvec_##X##_rawvalue_t arr[], size_t n) { \ - cvec_##X##_reserve(self, _cvec_size(self) + n); \ - cvec_##X##_value_t* p = self->data + _cvec_size(self); \ + cvec_##X##_reserve(self, _cvec_rep(self)->size + n); \ + cvec_##X##_value_t* p = self->data + _cvec_rep(self)->size; \ for (size_t i=0; i < n; ++i) *p++ = valueFromRaw(arr[i]); \ - _cvec_size(self) += n; \ + _cvec_rep(self)->size += n; \ } \ \ STC_DEF void \ cvec_##X##_clear(cvec_##X* self) { \ cvec_##X##_value_t* p = self->data; if (p) { \ - for (cvec_##X##_value_t* q = p + _cvec_size(self); p != q; ++p) valueDestroy(p); \ - _cvec_size(self) = 0; \ + for (cvec_##X##_value_t* q = p + _cvec_rep(self)->size; p != q; ++p) valueDestroy(p); \ + _cvec_rep(self)->size = 0; \ } \ } \ STC_DEF void \ cvec_##X##_del(cvec_##X* self) { \ cvec_##X##_clear(self); \ - if (_cvec_rep(self) != _cvec_inits) \ + if (_cvec_rep(self)->cap) \ c_free(_cvec_rep(self)); \ } \ \ STC_DEF void \ cvec_##X##_reserve(cvec_##X* self, size_t cap) { \ - size_t len = _cvec_size(self); \ - if (cap > _cvec_cap(self)) { \ - size_t* rep = (size_t *) c_realloc(_cvec_rep(self) != _cvec_inits ? _cvec_rep(self) : NULL, \ - 2*sizeof(size_t) + cap*sizeof(Value)); \ - self->data = (cvec_##X##_value_t*) (rep + 2); \ - rep[0] = len; \ - rep[1] = cap; \ + struct cvec_rep* rep = _cvec_rep(self); \ + size_t len = rep->size, oldcap = rep->cap; \ + if (cap > oldcap) { \ + rep = (struct cvec_rep*) c_realloc(oldcap ? rep : NULL, \ + sizeof(struct cvec_rep) + cap*sizeof(Value)); \ + self->data = (cvec_##X##_value_t*) rep->data; \ + rep->size = len; \ + rep->cap = cap; \ } \ } \ STC_DEF void \ - cvec_##X##_resize(cvec_##X* self, size_t size, Value null_val) { \ - cvec_##X##_reserve(self, size); \ - size_t i, n = _cvec_size(self); \ - for (i=size; idata + i); \ - for (i=n; idata[i] = null_val; \ - if (self->data) _cvec_size(self) = size; \ + cvec_##X##_resize(cvec_##X* self, size_t len, Value null_val) { \ + cvec_##X##_reserve(self, len); \ + struct cvec_rep* rep = _cvec_rep(self); \ + size_t i, n = rep->size; \ + for (i = len; i < n; ++i) valueDestroy(self->data + i); \ + for (i = n; i < len; ++i) self->data[i] = null_val; \ + if (rep->cap) rep->size = len; \ } \ \ STC_DEF void \ cvec_##X##_push_back(cvec_##X* self, Value value) { \ - size_t len = _cvec_size(self); \ + size_t len = _cvec_rep(self)->size; \ if (len == cvec_##X##_capacity(*self)) \ cvec_##X##_reserve(self, 4 + len*3/2); \ - self->data[_cvec_size(self)++] = value; \ + self->data[_cvec_rep(self)->size++] = value; \ } \ \ STC_DEF cvec_##X \ cvec_##X##_clone(cvec_##X vec) { \ - size_t len = _cvec_size(&vec); \ + size_t len = _cvec_rep(&vec)->size; \ cvec_##X out = cvec_##X##_with_capacity(len); \ cvec_##X##_insert_range_p(&out, out.data, vec.data, vec.data + len); \ return out; \ @@ -258,13 +265,13 @@ \ STC_DEF cvec_##X##_iter_t \ cvec_##X##_insert_range_p(cvec_##X* self, cvec_##X##_value_t* pos, const cvec_##X##_value_t* first, const cvec_##X##_value_t* finish) { \ - size_t len = finish - first, idx = pos - self->data, size = _cvec_size(self); \ + size_t len = finish - first, idx = pos - self->data, size = _cvec_rep(self)->size; \ cvec_##X##_iter_t it = {pos}; \ if (len == 0) return it; \ if (size + len > cvec_##X##_capacity(*self)) \ cvec_##X##_reserve(self, 4 + (size + len)*3/2), \ it.ref = pos = self->data + idx; \ - _cvec_size(self) += len; \ + _cvec_rep(self)->size += len; \ memmove(pos + len, pos, (size - idx) * sizeof(Value)); \ while (first != finish) \ *pos++ = valueFromRaw(valueToRaw(first++)); \ @@ -275,10 +282,10 @@ cvec_##X##_erase_range_p(cvec_##X* self, cvec_##X##_value_t* first, cvec_##X##_value_t* finish) { \ intptr_t len = finish - first; \ if (len > 0) { \ - cvec_##X##_value_t* p = first, *end = self->data + _cvec_size(self); \ + cvec_##X##_value_t* p = first, *end = self->data + _cvec_rep(self)->size; \ while (p != finish) valueDestroy(p++); \ memmove(first, finish, (end - finish) * sizeof(Value)); \ - _cvec_size(self) -= len; \ + _cvec_rep(self)->size -= len; \ } \ cvec_##X##_iter_t it = {first}; return it; \ } \ @@ -303,9 +310,6 @@ return valueCompareRaw(&rx, &ry); \ } -static size_t _cvec_inits[2] = {0, 0}; -#define _cvec_rep(self) (((size_t *) (self)->data) - 2) - #else #define _c_implement_cvec_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue) #endif @@ -315,10 +319,7 @@ static size_t _cvec_inits[2] = {0, 0}; #else #define STC_EXTERN_IMPORT extern #endif - typedef int(*_cvec_cmp)(const void*, const void*); STC_EXTERN_IMPORT void qsort(void *base, size_t nitems, size_t size, _cvec_cmp cmp); -#define _cvec_size(self) ((size_t *) (self)->data)[-2] -#define _cvec_cap(self) ((size_t *) (self)->data)[-1] #endif -- cgit v1.2.3