From d122c77b5a755cd5b3211c26346a84bb2b27cdce Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 21 Apr 2022 13:47:54 +0200 Subject: Switched to use i_key as primary template type parameter for all containers. Only maps will actually use i_val. Users can still specify i_val for non-maps, so there are no usability changes, other than the option to use i_key always, which makes the implementation and switching between container types simpler. --- examples/city.c | 75 ++++++++++++++++++ include/stc/carc.h | 28 +++---- include/stc/carr2.h | 12 +-- include/stc/carr3.h | 12 +-- include/stc/cbox.h | 37 ++++----- include/stc/cdeq.h | 84 ++++++++++----------- include/stc/clist.h | 64 ++++++++-------- include/stc/cmap.h | 8 +- include/stc/cpque.h | 18 ++--- include/stc/cqueue.h | 2 +- include/stc/csmap.h | 2 + include/stc/cstack.h | 26 +++---- include/stc/cvec.h | 86 ++++++++++----------- include/stc/template.h | 201 ++++++++++++++++++++++++++----------------------- 14 files changed, 374 insertions(+), 281 deletions(-) create mode 100644 examples/city.c diff --git a/examples/city.c b/examples/city.c new file mode 100644 index 00000000..16c9b6f1 --- /dev/null +++ b/examples/city.c @@ -0,0 +1,75 @@ +#include + +typedef struct +{ + cstr name; + cstr country; + float lat, lon; + int population; +} City; + +static inline int City_cmp(const City* a, const City* b) { + int c = cstr_cmp(&a->name, &b->name); + return c ? c : cstr_cmp(&a->country, &b->country); +} + +static inline City City_clone(City c) { + c.name = cstr_clone(c.name); + c.country = cstr_clone(c.country); + return c; +} + +static inline void City_drop(City* c) { + printf("drop %s\n", cstr_str(&c->name)); + c_drop(cstr, &c->name, &c->country); +} + +#define i_type CityArc +#define i_val_bind City +//#include +#include + +#define i_type Cities +#define i_val_arcbox CityArc +#include + +#define i_type CityMap +#define i_key int +#define i_val_arcbox CityArc +#include + + +int main(void) +{ + c_auto (Cities, cities, copy) + c_auto (CityMap, map) + { + struct City_s { const char *name, *country; float lat, lon; int pop; }; + + c_apply(c, Cities_push(&cities, CityArc_from((City){cstr_from(c.name), cstr_from(c.country), + c.lat, c.lon, c.pop})), struct City_s, { + {"New York", "US", 4.3, 23.2, 9000000}, + {"Paris", "France", 4.3, 23.2, 9000000}, + {"Berlin", "Germany", 4.3, 23.2, 9000000}, + {"London", "UK", 4.3, 23.2, 9000000}, + }); + + copy = Cities_clone(cities); // share each element! + + int k = 0, id[] = {8, 4, 3, 9, 2, 5}; + c_foreach (i, Cities, cities) + CityMap_insert(&map, id[k++], CityArc_clone(*i.ref)); + + Cities_pop(&cities); + Cities_pop(&cities); + + printf("Vec:\n"); + c_foreach (c, Cities, cities) + printf("city:%s, %d, use:%ld\n", cstr_str(&c.ref->get->name), c.ref->get->population, CityArc_use_count(*c.ref)); + + printf("\nMap:\n"); + c_forpair (id, city, CityMap, map) + printf("id:%d, city:%s, %d, use:%ld\n", _.id, cstr_str(&_.city.get->name), _.city.get->population, CityArc_use_count(_.city)); + puts(""); + } +} diff --git a/include/stc/carc.h b/include/stc/carc.h index 7f9c4390..54ba3159 100644 --- a/include/stc/carc.h +++ b/include/stc/carc.h @@ -35,8 +35,8 @@ void Person_drop(Person* p) { } #define i_tag person -#define i_val Person -#define i_valdrop Person_drop +#define i_key Person +#define i_keydrop Person_drop #include int main() { @@ -75,7 +75,7 @@ int main() { #define _i_prefix carc_ #endif #include "template.h" -typedef i_valraw _cx_raw; +typedef i_keyraw _cx_raw; #if !c_option(c_no_atomic) #define _i_atomic_inc(v) c_atomic_inc(v) @@ -85,9 +85,9 @@ typedef i_valraw _cx_raw; #define _i_atomic_dec_and_test(v) !(--*(v)) #endif #if !c_option(c_is_fwd) -_cx_deftypes(_c_carc_types, _cx_self, i_val); +_cx_deftypes(_c_carc_types, _cx_self, i_key); #endif -_cx_carc_rep { long counter; i_val value; }; +_cx_carc_rep { long counter; i_key value; }; STC_INLINE _cx_self _cx_memb(_init)(void) { return c_make(_cx_self){NULL, NULL}; } @@ -103,14 +103,14 @@ _cx_memb(_from_ptr)(_cx_value* p) { } STC_INLINE _cx_self -_cx_memb(_from)(i_val val) { // c++: std::make_shared(val) +_cx_memb(_from)(i_key val) { // c++: std::make_shared(val) _cx_self ptr; _cx_carc_rep *rep = c_alloc(_cx_carc_rep); *(ptr.use_count = &rep->counter) = 1; *(ptr.get = &rep->value) = val; return ptr; } -STC_INLINE i_val _cx_memb(_toraw)(const _cx_self* self) { +STC_INLINE i_key _cx_memb(_toraw)(const _cx_self* self) { return *self->get; } @@ -124,7 +124,7 @@ _cx_memb(_move)(_cx_self* self) { STC_INLINE void _cx_memb(_drop)(_cx_self* self) { if (self->use_count && _i_atomic_dec_and_test(self->use_count)) { - i_valdrop(self->get); + i_keydrop(self->get); if (self->get != &((_cx_carc_rep *)self->use_count)->value) c_free(self->get); c_free(self->use_count); @@ -138,17 +138,17 @@ _cx_memb(_reset)(_cx_self* self) { } STC_INLINE void -_cx_memb(_reset_from)(_cx_self* self, i_val val) { +_cx_memb(_reset_from)(_cx_self* self, i_key val) { _cx_memb(_drop)(self); *self = _cx_memb(_from)(val); } #if !defined _i_no_clone STC_INLINE _cx_self - _cx_memb(_make)(_cx_raw raw) { return _cx_memb(_from)(i_valfrom(raw)); } + _cx_memb(_make)(_cx_raw raw) { return _cx_memb(_from)(i_keyfrom(raw)); } #endif // !_i_no_clone -// does not use i_valfrom, so we can bypass c_no_clone +// does not use i_keyfrom, so we can bypass c_no_clone STC_INLINE _cx_self _cx_memb(_clone)(_cx_self ptr) { if (ptr.use_count) _i_atomic_inc(ptr.use_count); @@ -175,7 +175,7 @@ _cx_memb(_value_hash)(const _cx_value* x, size_t n) { #elif c_option(c_no_cmp) return c_hash32(&x, 4); #else - _cx_raw rx = i_valto(x); + _cx_raw rx = i_keyto(x); return i_hash((&rx), (sizeof rx)); #endif } @@ -185,7 +185,7 @@ _cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y) { #if c_option(c_no_cmp) return c_default_cmp(&x, &y); #else - _cx_raw rx = i_valto(x), ry = i_valto(y); + _cx_raw rx = i_keyto(x), ry = i_keyto(y); return i_cmp((&rx), (&ry)); #endif } @@ -195,7 +195,7 @@ _cx_memb(_value_eq)(const _cx_value* x, const _cx_value* y) { #if c_option(c_no_cmp) return x == y; #else - _cx_raw rx = i_valto(x), ry = i_valto(y); + _cx_raw rx = i_keyto(x), ry = i_keyto(y); return i_eq((&rx), (&ry)); #endif } diff --git a/include/stc/carr2.h b/include/stc/carr2.h index 93ab26bc..a9e9d9f8 100644 --- a/include/stc/carr2.h +++ b/include/stc/carr2.h @@ -29,7 +29,7 @@ #endif /* // carr2- 2D dynamic array in one memory block with easy indexing. -#define i_val int +#define i_key int #include #include @@ -58,10 +58,10 @@ int main() { #endif #include "template.h" #if !c_option(c_is_fwd) -_cx_deftypes(_c_carr2_types, _cx_self, i_val); +_cx_deftypes(_c_carr2_types, _cx_self, i_key); #endif -STC_API _cx_self _cx_memb(_with_values)(size_t xdim, size_t ydim, i_val value); +STC_API _cx_self _cx_memb(_with_values)(size_t xdim, size_t ydim, i_key value); STC_API _cx_self _cx_memb(_with_storage)(size_t xdim, size_t ydim, _cx_value* storage); STC_API _cx_value* _cx_memb(_release)(_cx_self* self); STC_API void _cx_memb(_drop)(_cx_self* self); @@ -107,7 +107,7 @@ STC_DEF _cx_self _cx_memb(_with_storage)(size_t xdim, size_t ydim, _cx_value* bl return _arr; } -STC_DEF _cx_self _cx_memb(_with_values)(size_t xdim, size_t ydim, i_val value) { +STC_DEF _cx_self _cx_memb(_with_values)(size_t xdim, size_t ydim, i_key value) { _cx_self _arr = _cx_memb(_init)(xdim, ydim); for (_cx_value* p = _arr.data[0], *e = p + xdim*ydim; p != e; ++p) *p = value; @@ -119,7 +119,7 @@ STC_DEF _cx_self _cx_memb(_with_values)(size_t xdim, size_t ydim, i_val value) { STC_DEF _cx_self _cx_memb(_clone)(_cx_self src) { _cx_self _arr = _cx_memb(_init)(src.xdim, src.ydim); for (_cx_value* p = _arr.data[0], *q = src.data[0], *e = p + _cx_memb(_size)(src); p != e; ++p, ++q) - *p = i_valclone((*q)); + *p = i_keyclone((*q)); return _arr; } @@ -139,7 +139,7 @@ STC_DEF _cx_value *_cx_memb(_release)(_cx_self* self) { STC_DEF void _cx_memb(_drop)(_cx_self* self) { if (!self->data) return; for (_cx_value* p = self->data[0], *q = p + _cx_memb(_size)(*self); p != q; ) { - --q; i_valdrop(q); + --q; i_keydrop(q); } c_free(self->data[0]); /* values */ c_free(self->data); /* pointers */ diff --git a/include/stc/carr3.h b/include/stc/carr3.h index a326105c..2b466b13 100644 --- a/include/stc/carr3.h +++ b/include/stc/carr3.h @@ -29,7 +29,7 @@ #endif /* // carr3 - 3D dynamic array in one memory block with easy indexing. -#define i_val int +#define i_key int #include #include @@ -60,10 +60,10 @@ int main() { #include "template.h" #if !c_option(c_is_fwd) -_cx_deftypes(_c_carr3_types, _cx_self, i_val); +_cx_deftypes(_c_carr3_types, _cx_self, i_key); #endif -STC_API _cx_self _cx_memb(_with_values)(size_t xdim, size_t ydim, size_t zdim, i_val value); +STC_API _cx_self _cx_memb(_with_values)(size_t xdim, size_t ydim, size_t zdim, i_key value); STC_API _cx_self _cx_memb(_with_storage)(size_t xdim, size_t ydim, size_t zdim, _cx_value* storage); STC_API _cx_value* _cx_memb(_release)(_cx_self* self); STC_API void _cx_memb(_drop)(_cx_self* self); @@ -112,7 +112,7 @@ STC_DEF _cx_self _cx_memb(_with_storage)(size_t xdim, size_t ydim, size_t zdim, return _arr; } -STC_DEF _cx_self _cx_memb(_with_values)(size_t xdim, size_t ydim, size_t zdim, i_val value) { +STC_DEF _cx_self _cx_memb(_with_values)(size_t xdim, size_t ydim, size_t zdim, i_key value) { _cx_self _arr = _cx_memb(_init)(xdim, ydim, zdim); for (_cx_value* p = **_arr.data, *e = p + xdim*ydim*zdim; p != e; ++p) *p = value; @@ -124,7 +124,7 @@ STC_DEF _cx_self _cx_memb(_with_values)(size_t xdim, size_t ydim, size_t zdim, i STC_DEF _cx_self _cx_memb(_clone)(_cx_self src) { _cx_self _arr = _cx_memb(_init)(src.xdim, src.ydim, src.zdim); for (_cx_value* p = **_arr.data, *q = **src.data, *e = p + _cx_memb(_size)(src); p != e; ++p, ++q) - *p = i_valclone((*q)); + *p = i_keyclone((*q)); return _arr; } @@ -144,7 +144,7 @@ STC_DEF _cx_value* _cx_memb(_release)(_cx_self* self) { STC_DEF void _cx_memb(_drop)(_cx_self* self) { if (!self->data) return; for (_cx_value* p = **self->data, *q = p + _cx_memb(_size)(*self); p != q; ) { - --q; i_valdrop(q); + --q; i_keydrop(q); } c_free(self->data[0][0]); /* data */ c_free(self->data); /* pointers */ diff --git a/include/stc/cbox.h b/include/stc/cbox.h index c2ecbae4..27536c21 100644 --- a/include/stc/cbox.h +++ b/include/stc/cbox.h @@ -39,7 +39,7 @@ void Person_drop(Person* p) { c_drop(cstr, &p->name, &p->email); } -#define i_val_bind Person // bind Person clone+drop fn's +#define i_key_bind Person // bind Person clone+drop fn's #define i_opt c_no_cmp // compare by .get addresses only #define i_type PBox #include @@ -71,32 +71,35 @@ int main() { #define _i_prefix cbox_ #endif #include "template.h" -typedef i_valraw _cx_raw; +typedef i_keyraw _cx_raw; #if !c_option(c_is_fwd) -_cx_deftypes(_c_cbox_types, _cx_self, i_val); +_cx_deftypes(_c_cbox_types, _cx_self, i_key); #endif // constructors (takes ownsership) STC_INLINE _cx_self _cx_memb(_init)(void) { return c_make(_cx_self){NULL}; } +STC_INLINE long +_cx_memb(_use_count)(_cx_self box) { return (long)(box.get != NULL); } + STC_INLINE _cx_self -_cx_memb(_from_ptr)(i_val* p) { return c_make(_cx_self){p}; } +_cx_memb(_from_ptr)(i_key* p) { return c_make(_cx_self){p}; } STC_INLINE _cx_self -_cx_memb(_from)(i_val val) { // c++: std::make_unique(val) - _cx_self ptr = {c_alloc(i_val)}; +_cx_memb(_from)(i_key val) { // c++: std::make_unique(val) + _cx_self ptr = {c_alloc(i_key)}; *ptr.get = val; return ptr; } -STC_INLINE i_val +STC_INLINE i_key _cx_memb(_toraw)(const _cx_self* self) { return *self->get; } // destructor STC_INLINE void _cx_memb(_drop)(_cx_self* self) { - if (self->get) { i_valdrop(self->get); c_free(self->get); } + if (self->get) { i_keydrop(self->get); c_free(self->get); } } STC_INLINE _cx_self @@ -112,20 +115,20 @@ _cx_memb(_reset)(_cx_self* self) { // take ownership of val STC_INLINE void -_cx_memb(_reset_from)(_cx_self* self, i_val val) { - if (self->get) { i_valdrop(self->get); *self->get = val; } - else self->get = c_new(i_val, val); +_cx_memb(_reset_from)(_cx_self* self, i_key val) { + if (self->get) { i_keydrop(self->get); *self->get = val; } + else self->get = c_new(i_key, val); } #if !defined _i_no_clone STC_INLINE _cx_self - _cx_memb(_make)(_cx_raw raw) { return _cx_memb(_from)(i_valfrom(raw)); } + _cx_memb(_make)(_cx_raw raw) { return _cx_memb(_from)(i_keyfrom(raw)); } STC_INLINE _cx_self _cx_memb(_clone)(_cx_self other) { if (!other.get) return other; - i_valraw r = i_valto(other.get); - return c_make(_cx_self){c_new(i_val, i_valfrom(r))}; + i_keyraw r = i_keyto(other.get); + return c_make(_cx_self){c_new(i_key, i_keyfrom(r))}; } STC_INLINE void @@ -149,7 +152,7 @@ _cx_memb(_value_hash)(const _cx_value* x, size_t n) { #elif c_option(c_no_cmp) return c_hash32(&x, 4); #else - _cx_raw rx = i_valto(x); + _cx_raw rx = i_keyto(x); return i_hash((&rx), (sizeof rx)); #endif } @@ -159,7 +162,7 @@ _cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y) { #if c_option(c_no_cmp) return c_default_cmp(&x, &y); #else - _cx_raw rx = i_valto(x), ry = i_valto(y); + _cx_raw rx = i_keyto(x), ry = i_keyto(y); return i_cmp((&rx), (&ry)); #endif } @@ -169,7 +172,7 @@ _cx_memb(_value_eq)(const _cx_value* x, const _cx_value* y) { #if c_option(c_no_cmp) return x == y; #else - _cx_raw rx = i_valto(x), ry = i_valto(y); + _cx_raw rx = i_keyto(x), ry = i_keyto(y); return i_eq((&rx), (&ry)); #endif } diff --git a/include/stc/cdeq.h b/include/stc/cdeq.h index 33747e02..7d6c0254 100644 --- a/include/stc/cdeq.h +++ b/include/stc/cdeq.h @@ -37,16 +37,16 @@ struct cdeq_rep { size_t size, cap; void* base[]; }; #include "template.h" #if !c_option(c_is_fwd) -_cx_deftypes(_c_cdeq_types, _cx_self, i_val); +_cx_deftypes(_c_cdeq_types, _cx_self, i_key); #endif -typedef i_valraw _cx_raw; +typedef i_keyraw _cx_raw; STC_API _cx_self _cx_memb(_init)(void); STC_API _cx_self _cx_memb(_with_capacity)(const size_t n); STC_API bool _cx_memb(_reserve)(_cx_self* self, const size_t n); STC_API void _cx_memb(_clear)(_cx_self* self); STC_API void _cx_memb(_drop)(_cx_self* self); -STC_API _cx_value* _cx_memb(_push_back)(_cx_self* self, i_val value); +STC_API _cx_value* _cx_memb(_push_back)(_cx_self* self, i_key value); STC_API void _cx_memb(_shrink_to_fit)(_cx_self *self); #if !defined _i_queue #if !defined _i_no_clone @@ -59,10 +59,10 @@ STC_API _cx_iter _cx_memb(_emplace_range_p)(_cx_self* self, _cx_value* po #endif // !_i_no_clone #if !c_option(c_no_cmp) -STC_API _cx_iter _cx_memb(_find_in)(_cx_iter p1, _cx_iter p2, i_valraw raw); +STC_API _cx_iter _cx_memb(_find_in)(_cx_iter p1, _cx_iter p2, i_keyraw raw); STC_API int _cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y); #endif -STC_API _cx_value* _cx_memb(_push_front)(_cx_self* self, i_val value); +STC_API _cx_value* _cx_memb(_push_front)(_cx_self* self, i_key value); STC_API _cx_iter _cx_memb(_erase_range_p)(_cx_self* self, _cx_value* p1, _cx_value* p2); STC_API _cx_iter _cx_memb(_insert_range_p)(_cx_self* self, _cx_value* pos, const _cx_value* p1, const _cx_value* p2); @@ -71,11 +71,11 @@ STC_API _cx_iter _cx_memb(_insert_range_p)(_cx_self* self, _cx_value* pos #if !defined _i_no_clone STC_API _cx_self _cx_memb(_clone)(_cx_self cx); #if !defined _i_no_emplace -STC_INLINE _cx_value* _cx_memb(_emplace_back)(_cx_self* self, i_valraw raw) - { return _cx_memb(_push_back)(self, i_valfrom(raw)); } +STC_INLINE _cx_value* _cx_memb(_emplace_back)(_cx_self* self, i_keyraw raw) + { return _cx_memb(_push_back)(self, i_keyfrom(raw)); } #endif -STC_INLINE i_val _cx_memb(_value_clone)(i_val val) - { return i_valclone(val); } +STC_INLINE i_key _cx_memb(_value_clone)(i_key val) + { return i_keyclone(val); } STC_INLINE void _cx_memb(_copy)(_cx_self *self, _cx_self other) { if (self->data == other.data) return; _cx_memb(_drop)(self); *self = _cx_memb(_clone)(other); @@ -85,11 +85,11 @@ STC_INLINE bool _cx_memb(_empty)(_cx_self cx) { return !cdeq_rep_(&cx)-> STC_INLINE size_t _cx_memb(_size)(_cx_self cx) { return cdeq_rep_(&cx)->size; } STC_INLINE size_t _cx_memb(_capacity)(_cx_self cx) { return cdeq_rep_(&cx)->cap; } STC_INLINE void _cx_memb(_swap)(_cx_self* a, _cx_self* b) {c_swap(_cx_self, *a, *b); } -STC_INLINE i_val _cx_memb(_value_fromraw)(i_valraw raw) { return i_valfrom(raw); } -STC_INLINE i_valraw _cx_memb(_value_toraw)(_cx_value* pval) { return i_valto(pval); } +STC_INLINE i_key _cx_memb(_value_fromraw)(i_keyraw raw) { return i_keyfrom(raw); } +STC_INLINE i_keyraw _cx_memb(_value_toraw)(_cx_value* pval) { return i_keyto(pval); } STC_INLINE void _cx_memb(_pop_front)(_cx_self* self) // == _pop() when _i_queue - { i_valdrop(self->data); ++self->data; --cdeq_rep_(self)->size; } + { i_keydrop(self->data); ++self->data; --cdeq_rep_(self)->size; } STC_INLINE _cx_value* _cx_memb(_back)(const _cx_self* self) { return self->data + cdeq_rep_(self)->size - 1; } STC_INLINE _cx_value* _cx_memb(_front)(const _cx_self* self) { return self->data; } @@ -106,7 +106,7 @@ STC_INLINE _cx_iter _cx_memb(_advance)(_cx_iter it, intptr_t offs) STC_INLINE size_t _cx_memb(_index)(_cx_self cx, _cx_iter it) { return it.ref - cx.data; } STC_INLINE void _cx_memb(_pop_back)(_cx_self* self) - { _cx_value* p = &self->data[--cdeq_rep_(self)->size]; i_valdrop(p); } + { _cx_value* p = &self->data[--cdeq_rep_(self)->size]; i_keydrop(p); } STC_INLINE const _cx_value* _cx_memb(_at)(const _cx_self* self, const size_t idx) { assert(idx < cdeq_rep_(self)->size); return self->data + idx; @@ -116,7 +116,7 @@ STC_INLINE _cx_value* _cx_memb(_at_mut)(_cx_self* self, const size_t idx) { } STC_INLINE _cx_iter -_cx_memb(_insert)(_cx_self* self, const size_t idx, i_val value) { +_cx_memb(_insert)(_cx_self* self, const size_t idx, i_key value) { return _cx_memb(_insert_range_p)(self, self->data + idx, &value, &value + 1); } STC_INLINE _cx_iter @@ -124,7 +124,7 @@ _cx_memb(_insert_n)(_cx_self* self, const size_t idx, const _cx_value arr[], con return _cx_memb(_insert_range_p)(self, self->data + idx, arr, arr + n); } STC_INLINE _cx_iter -_cx_memb(_insert_at)(_cx_self* self, _cx_iter it, i_val value) { +_cx_memb(_insert_at)(_cx_self* self, _cx_iter it, i_key value) { return _cx_memb(_insert_range_p)(self, it.ref, &value, &value + 1); } @@ -147,8 +147,8 @@ _cx_memb(_emplace_range)(_cx_self* self, _cx_iter it, _cx_iter it1, _cx_iter it2 return _cx_memb(_clone_range_p)(self, it.ref, it1.ref, it2.ref); } -STC_INLINE _cx_value* _cx_memb(_emplace_front)(_cx_self* self, i_valraw raw) { - return _cx_memb(_push_front)(self, i_valfrom(raw)); +STC_INLINE _cx_value* _cx_memb(_emplace_front)(_cx_self* self, i_keyraw raw) { + return _cx_memb(_push_front)(self, i_keyfrom(raw)); } STC_INLINE _cx_iter @@ -156,7 +156,7 @@ _cx_memb(_emplace_n)(_cx_self* self, const size_t idx, const _cx_raw arr[], cons return _cx_memb(_emplace_range_p)(self, self->data + idx, arr, arr + n); } STC_INLINE _cx_iter -_cx_memb(_emplace_at)(_cx_self* self, _cx_iter it, i_valraw raw) { +_cx_memb(_emplace_at)(_cx_self* self, _cx_iter it, i_keyraw raw) { return _cx_memb(_emplace_range_p)(self, it.ref, &raw, &raw + 1); } #endif // !_i_no_clone && !_i_no_emplace @@ -164,19 +164,19 @@ _cx_memb(_emplace_at)(_cx_self* self, _cx_iter it, i_valraw raw) { #if !c_option(c_no_cmp) STC_INLINE _cx_iter -_cx_memb(_find)(const _cx_self* self, i_valraw raw) { +_cx_memb(_find)(const _cx_self* self, i_keyraw raw) { return _cx_memb(_find_in)(_cx_memb(_begin)(self), _cx_memb(_end)(self), raw); } STC_INLINE const _cx_value* -_cx_memb(_get)(const _cx_self* self, i_valraw raw) { +_cx_memb(_get)(const _cx_self* self, i_keyraw raw) { _cx_iter end = _cx_memb(_end)(self); _cx_value* val = _cx_memb(_find_in)(_cx_memb(_begin)(self), end, raw).ref; return val == end.ref ? NULL : val; } STC_INLINE _cx_value* -_cx_memb(_get_mut)(_cx_self* self, i_valraw raw) +_cx_memb(_get_mut)(_cx_self* self, i_keyraw raw) { return (_cx_value *) _cx_memb(_get)(self, raw); } STC_INLINE void @@ -211,7 +211,7 @@ _cx_memb(_clear)(_cx_self* self) { struct cdeq_rep* rep = cdeq_rep_(self); if (rep->cap) { for (_cx_value *p = self->data, *q = p + rep->size; p != q; ) { - --q; i_valdrop(q); + --q; i_keydrop(q); } rep->size = 0; } @@ -222,8 +222,8 @@ _cx_memb(_shrink_to_fit)(_cx_self *self) { if (_cx_memb(_size)(*self) != _cx_memb(_capacity)(*self)) { struct cdeq_rep* rep = cdeq_rep_(self); const size_t sz = rep->size; - memmove(self->_base, self->data, sz*sizeof(i_val)); - rep = (struct cdeq_rep*) c_realloc(rep, offsetof(struct cdeq_rep, base) + sz*sizeof(i_val)); + memmove(self->_base, self->data, sz*sizeof(i_key)); + rep = (struct cdeq_rep*) c_realloc(rep, offsetof(struct cdeq_rep, base) + sz*sizeof(i_key)); if (rep) { self->_base = self->data = (_cx_value*) rep->base; rep->cap = sz; } } } @@ -243,7 +243,7 @@ _cx_memb(_realloc_)(_cx_self* self, const size_t n) { const size_t sz = rep->size, cap = (size_t) (sz*1.7) + n + 7; const size_t nfront = _cdeq_nfront(self); rep = (struct cdeq_rep*) c_realloc(rep->cap ? rep : NULL, - offsetof(struct cdeq_rep, base) + cap*sizeof(i_val)); + offsetof(struct cdeq_rep, base) + cap*sizeof(i_key)); if (!rep) return 0; rep->size = sz, rep->cap = cap; self->_base = (_cx_value *) rep->base; @@ -258,7 +258,7 @@ _cx_memb(_expand_right_half_)(_cx_self* self, const size_t idx, const size_t n) const size_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront; if (nback >= n || sz*1.3 + n > cap) { if (!_cx_memb(_realloc_)(self, n)) return false; - memmove(self->data + idx + n, self->data + idx, (sz - idx)*sizeof(i_val)); + memmove(self->data + idx + n, self->data + idx, (sz - idx)*sizeof(i_key)); } else { #if !defined _i_queue const size_t unused = cap - (sz + n); @@ -266,8 +266,8 @@ _cx_memb(_expand_right_half_)(_cx_self* self, const size_t idx, const size_t n) #else const size_t pos = 0; #endif - memmove(self->_base + pos, self->data, idx*sizeof(i_val)); - memmove(self->data + pos + idx + n, self->data + idx, (sz - idx)*sizeof(i_val)); + memmove(self->_base + pos, self->data, idx*sizeof(i_key)); + memmove(self->data + pos + idx + n, self->data + idx, (sz - idx)*sizeof(i_key)); self->data = self->_base + pos; } return true; @@ -287,7 +287,7 @@ _cx_memb(_reserve)(_cx_self* self, const size_t n) { } STC_DEF _cx_value* -_cx_memb(_push_back)(_cx_self* self, i_val value) { +_cx_memb(_push_back)(_cx_self* self, i_key value) { struct cdeq_rep* r = cdeq_rep_(self); if (_cdeq_nfront(self) + r->size == r->cap) { _cx_memb(_expand_right_half_)(self, r->size, 1); @@ -304,7 +304,7 @@ _cx_memb(_clone)(_cx_self cx) { _cx_self out = _cx_memb(_with_capacity)(sz); cdeq_rep_(&out)->size = sz; for (size_t i = 0; i < sz; ++i) - out.data[i] = i_valclone(cx.data[i]); + out.data[i] = i_keyclone(cx.data[i]); return out; } #endif @@ -318,13 +318,13 @@ _cx_memb(_expand_left_half_)(_cx_self* self, const size_t idx, const size_t n) { const size_t sz = rep->size; const size_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront; if (nfront >= n) { - self->data = (_cx_value *) memmove(self->data - n, self->data, idx*sizeof(i_val)); + self->data = (_cx_value *) memmove(self->data - n, self->data, idx*sizeof(i_key)); } else { if (sz*1.3 + n > cap) cap = _cx_memb(_realloc_)(self, n); const size_t unused = cap - (sz + n); const size_t pos = (nback*2 < unused) ? unused - nback : unused/2; - memmove(self->_base + pos + idx + n, self->data + idx, (sz - idx)*sizeof(i_val)); - self->data = (_cx_value *) memmove(self->_base + pos, self->data, idx*sizeof(i_val)); + memmove(self->_base + pos + idx + n, self->data + idx, (sz - idx)*sizeof(i_key)); + self->data = (_cx_value *) memmove(self->_base + pos, self->data, idx*sizeof(i_key)); } } @@ -338,7 +338,7 @@ _cx_memb(_insert_space_)(_cx_self* self, const _cx_value* pos, const size_t n) { } STC_DEF _cx_value* -_cx_memb(_push_front)(_cx_self* self, i_val value) { +_cx_memb(_push_front)(_cx_self* self, i_key value) { if (self->data == self->_base) _cx_memb(_expand_left_half_)(self, 0, 1); else @@ -362,9 +362,9 @@ _cx_memb(_erase_range_p)(_cx_self* self, _cx_value* p1, _cx_value* p2) { const size_t n = p2 - p1; if (n > 0) { _cx_value* p = p1, *end = self->data + cdeq_rep_(self)->size; - for (; p != p2; ++p) { i_valdrop(p); } + for (; p != p2; ++p) { i_keydrop(p); } if (p1 == self->data) self->data += n; - else memmove(p1, p2, (end - p2) * sizeof(i_val)); + else memmove(p1, p2, (end - p2) * sizeof(i_key)); cdeq_rep_(self)->size -= n; } return c_make(_cx_iter){p1}; @@ -376,7 +376,7 @@ STC_DEF _cx_iter _cx_memb(_emplace_range_p)(_cx_self* self, _cx_value* pos, const _cx_raw* p1, const _cx_raw* p2) { pos = _cx_memb(_insert_space_)(self, pos, p2 - p1); _cx_iter it = {pos}; - for (; p1 != p2; ++p1) *pos++ = i_valfrom((*p1)); + for (; p1 != p2; ++p1) *pos++ = i_keyfrom((*p1)); return it; } #endif // !_i_no_emplace @@ -387,7 +387,7 @@ _cx_memb(_clone_range_p)(_cx_self* self, _cx_value* pos, pos = _cx_memb(_insert_space_)(self, pos, p2 - p1); _cx_iter it = {pos}; for (; p1 != p2; ++p1) - *pos++ = i_valclone((*p1)); + *pos++ = i_keyclone((*p1)); return it; } #endif // !_i_no_clone @@ -395,9 +395,9 @@ _cx_memb(_clone_range_p)(_cx_self* self, _cx_value* pos, #if !c_option(c_no_cmp) STC_DEF _cx_iter -_cx_memb(_find_in)(_cx_iter i1, _cx_iter i2, i_valraw raw) { +_cx_memb(_find_in)(_cx_iter i1, _cx_iter i2, i_keyraw raw) { for (; i1.ref != i2.ref; ++i1.ref) { - i_valraw r = i_valto(i1.ref); + i_keyraw r = i_keyto(i1.ref); if (i_eq((&raw), (&r))) return i1; } return i2; @@ -405,8 +405,8 @@ _cx_memb(_find_in)(_cx_iter i1, _cx_iter i2, i_valraw raw) { STC_DEF int _cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y) { - i_valraw rx = i_valto(x); - i_valraw ry = i_valto(y); + i_keyraw rx = i_keyto(x); + i_keyraw ry = i_keyto(y); return i_cmp((&rx), (&ry)); } #endif // !c_no_cmp diff --git a/include/stc/clist.h b/include/stc/clist.h index b871dd3c..8247b04a 100644 --- a/include/stc/clist.h +++ b/include/stc/clist.h @@ -28,7 +28,7 @@ #include #include - #define i_val int64_t + #define i_key int64_t #define i_tag ix #include @@ -83,22 +83,22 @@ _c_clist_complete_types(clist_VOID, dummy); #include "template.h" #if !c_option(c_is_fwd) - _cx_deftypes(_c_clist_types, _cx_self, i_val); + _cx_deftypes(_c_clist_types, _cx_self, i_key); #endif _cx_deftypes(_c_clist_complete_types, _cx_self, dummy); -typedef i_valraw _cx_raw; +typedef i_keyraw _cx_raw; STC_API size_t _clist_count(const clist_VOID* self); STC_API void _cx_memb(_drop)(_cx_self* self); -STC_API _cx_value* _cx_memb(_push_back)(_cx_self* self, i_val value); -STC_API _cx_value* _cx_memb(_push_front)(_cx_self* self, i_val value); -STC_API _cx_iter _cx_memb(_insert_at)(_cx_self* self, _cx_iter it, i_val value); +STC_API _cx_value* _cx_memb(_push_back)(_cx_self* self, i_key value); +STC_API _cx_value* _cx_memb(_push_front)(_cx_self* self, i_key value); +STC_API _cx_iter _cx_memb(_insert_at)(_cx_self* self, _cx_iter it, i_key value); STC_API _cx_iter _cx_memb(_erase_at)(_cx_self* self, _cx_iter it); STC_API _cx_iter _cx_memb(_erase_range)(_cx_self* self, _cx_iter it1, _cx_iter it2); #if !c_option(c_no_cmp) -STC_API size_t _cx_memb(_remove)(_cx_self* self, i_valraw val); -STC_API _cx_iter _cx_memb(_find_in)(_cx_iter it1, _cx_iter it2, i_valraw val); +STC_API size_t _cx_memb(_remove)(_cx_self* self, i_keyraw val); +STC_API _cx_iter _cx_memb(_find_in)(_cx_iter it1, _cx_iter it2, i_keyraw 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); #endif @@ -108,20 +108,20 @@ STC_API _cx_node* _cx_memb(_erase_after_)(_cx_self* self, _cx_node* node); #if !defined _i_no_clone STC_API _cx_self _cx_memb(_clone)(_cx_self cx); -STC_INLINE i_val _cx_memb(_value_clone)(i_val val) - { return i_valclone(val); } +STC_INLINE i_key _cx_memb(_value_clone)(i_key val) + { return i_keyclone(val); } STC_INLINE void _cx_memb(_copy)(_cx_self *self, _cx_self other) { if (self->last == other.last) return; _cx_memb(_drop)(self); *self = _cx_memb(_clone)(other); } #if !defined _i_no_emplace -STC_INLINE _cx_value* _cx_memb(_emplace_back)(_cx_self* self, i_valraw raw) - { return _cx_memb(_push_back)(self, i_valfrom(raw)); } -STC_INLINE _cx_value* _cx_memb(_emplace_front)(_cx_self* self, i_valraw raw) - { return _cx_memb(_push_front)(self, i_valfrom(raw)); } -STC_INLINE _cx_iter _cx_memb(_emplace_at)(_cx_self* self, _cx_iter it, i_valraw raw) - { return _cx_memb(_insert_at)(self, it, i_valfrom(raw)); } +STC_INLINE _cx_value* _cx_memb(_emplace_back)(_cx_self* self, i_keyraw raw) + { return _cx_memb(_push_back)(self, i_keyfrom(raw)); } +STC_INLINE _cx_value* _cx_memb(_emplace_front)(_cx_self* self, i_keyraw raw) + { return _cx_memb(_push_front)(self, i_keyfrom(raw)); } +STC_INLINE _cx_iter _cx_memb(_emplace_at)(_cx_self* self, _cx_iter it, i_keyraw raw) + { return _cx_memb(_insert_at)(self, it, i_keyfrom(raw)); } #endif // !_i_no_emplace #endif // !_i_no_clone @@ -168,17 +168,17 @@ _cx_memb(_splice_range)(_cx_self* self, _cx_iter it, #if !c_option(c_no_cmp) STC_INLINE _cx_iter -_cx_memb(_find)(const _cx_self* self, i_valraw val) { +_cx_memb(_find)(const _cx_self* self, i_keyraw val) { return _cx_memb(_find_in)(_cx_memb(_begin)(self), _cx_memb(_end)(self), val); } STC_INLINE const _cx_value* -_cx_memb(_get)(const _cx_self* self, i_valraw val) { +_cx_memb(_get)(const _cx_self* self, i_keyraw val) { return _cx_memb(_find_in)(_cx_memb(_begin)(self), _cx_memb(_end)(self), val).ref; } STC_INLINE _cx_value* -_cx_memb(_get_mut)(_cx_self* self, i_valraw val) { +_cx_memb(_get_mut)(_cx_self* self, i_keyraw val) { return _cx_memb(_find_in)(_cx_memb(_begin)(self), _cx_memb(_end)(self), val).ref; } #endif @@ -191,7 +191,7 @@ STC_DEF _cx_self _cx_memb(_clone)(_cx_self cx) { _cx_self out = _cx_memb(_init)(); c_foreach (it, _cx_self, cx) - _cx_memb(_push_back)(&out, i_valclone((*it.ref))); + _cx_memb(_push_back)(&out, i_keyclone((*it.ref))); return out; } #endif @@ -202,21 +202,21 @@ _cx_memb(_drop)(_cx_self* self) { } STC_DEF _cx_value* -_cx_memb(_push_back)(_cx_self* self, i_val value) { +_cx_memb(_push_back)(_cx_self* self, i_key value) { _c_clist_insert_after(self, _cx_self, self->last, value); self->last = entry; return &entry->value; } STC_DEF _cx_value* -_cx_memb(_push_front)(_cx_self* self, i_val value) { +_cx_memb(_push_front)(_cx_self* self, i_key value) { _c_clist_insert_after(self, _cx_self, self->last, value); if (!self->last) self->last = entry; return &entry->value; } STC_DEF _cx_iter -_cx_memb(_insert_at)(_cx_self* self, _cx_iter it, i_val value) { +_cx_memb(_insert_at)(_cx_self* self, _cx_iter it, i_key value) { _cx_node* node = it.ref ? it.prev : self->last; _c_clist_insert_after(self, _cx_self, node, value); if (!self->last || !it.ref) { @@ -250,7 +250,7 @@ _cx_memb(_erase_after_)(_cx_self* self, _cx_node* node) { node->next = next; if (del == next) self->last = node = NULL; else if (self->last == del) self->last = node, node = NULL; - i_valdrop((&del->value)); c_free(del); + i_keydrop((&del->value)); c_free(del); return node; } @@ -283,21 +283,21 @@ _cx_memb(_split_off)(_cx_self* self, _cx_iter it1, _cx_iter it2) { #if !c_option(c_no_cmp) STC_DEF _cx_iter -_cx_memb(_find_in)(_cx_iter it1, _cx_iter it2, i_valraw val) { +_cx_memb(_find_in)(_cx_iter it1, _cx_iter it2, i_keyraw val) { c_foreach (it, _cx_self, it1, it2) { - i_valraw r = i_valto(it.ref); + i_keyraw r = i_keyto(it.ref); if (i_eq((&r), (&val))) return it; } it2.ref = NULL; return it2; } STC_DEF size_t -_cx_memb(_remove)(_cx_self* self, i_valraw val) { +_cx_memb(_remove)(_cx_self* self, i_keyraw val) { size_t n = 0; _cx_node* prev = self->last, *node; while (prev) { node = prev->next; - i_valraw r = i_valto((&node->value)); + i_keyraw r = i_keyto((&node->value)); if (i_eq((&r), (&val))) prev = _cx_memb(_erase_after_)(self, prev), ++n; else @@ -308,8 +308,8 @@ _cx_memb(_remove)(_cx_self* self, i_valraw val) { static int _cx_memb(_sort_cmp_)(const clist_VOID_node* x, const clist_VOID_node* y) { - i_valraw a = i_valto((&((const _cx_node *) x)->value)); - i_valraw b = i_valto((&((const _cx_node *) y)->value)); + i_keyraw a = i_keyto((&((const _cx_node *) x)->value)); + i_keyraw b = i_keyto((&((const _cx_node *) y)->value)); return i_cmp((&a), (&b)); } @@ -324,8 +324,8 @@ _cx_memb(_sort)(_cx_self* self) { STC_DEF int _cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y) { - i_valraw rx = i_valto(x); - i_valraw ry = i_valto(y); + i_keyraw rx = i_keyto(x); + i_keyraw ry = i_keyto(y); return i_cmp((&rx), (&ry)); } #endif // !c_no_cmp diff --git a/include/stc/cmap.h b/include/stc/cmap.h index 07ba9fe5..c5172f3b 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -65,15 +65,15 @@ typedef struct { size_t idx; uint8_t hx; } chash_bucket_t; #define _i_SET_ONLY c_true #define _i_keyref(vp) (vp) #else + #define _i_ismap #define _i_MAP_ONLY c_true #define _i_SET_ONLY c_false #define _i_keyref(vp) (&(vp)->first) #endif +#define _i_ishash #include "template.h" -#if _i_no_hash == 1 +#ifdef _i_no_hash #error "i_hash must be defined if i_cmp, i_eq or i_keyfrom is defined for cmap/cset. For basic types c_default_hash may be used." -#elif _i_no_hash == 2 - #error "i_cmp or i_eq must be defined if i_hash is defined. For basic types c_default_cmp may be used." #endif #if !c_option(c_is_fwd) _cx_deftypes(_c_chash_types, _cx_self, i_key, i_val, i_size, _i_MAP_ONLY, _i_SET_ONLY); @@ -392,6 +392,8 @@ _cx_memb(_erase_entry)(_cx_self* self, _cx_value* _val) { #endif // _i_implement #undef _i_isset +#undef _i_ismap +#undef _i_ishash #undef _i_keyref #undef _i_MAP_ONLY #undef _i_SET_ONLY diff --git a/include/stc/cpque.h b/include/stc/cpque.h index 9844fc93..4b330707 100644 --- a/include/stc/cpque.h +++ b/include/stc/cpque.h @@ -34,9 +34,9 @@ #include "template.h" #if !c_option(c_is_fwd) - _cx_deftypes(_c_cpque_types, _cx_self, i_val); + _cx_deftypes(_c_cpque_types, _cx_self, i_key); #endif -typedef i_valraw _cx_raw; +typedef i_keyraw _cx_raw; STC_API void _cx_memb(_make_heap)(_cx_self* self); STC_API void _cx_memb(_erase_at)(_cx_self* self, size_t idx); @@ -59,7 +59,7 @@ STC_INLINE _cx_self _cx_memb(_with_capacity)(const size_t cap) { return out; } -STC_INLINE _cx_self _cx_memb(_with_size)(const size_t size, i_val null) { +STC_INLINE _cx_self _cx_memb(_with_size)(const size_t size, i_key null) { _cx_self out = {NULL}; _cx_memb(_reserve)(&out, size); while (out.size < size) out.data[out.size++] = null; return out; @@ -67,7 +67,7 @@ STC_INLINE _cx_self _cx_memb(_with_size)(const size_t size, i_val null) { STC_INLINE void _cx_memb(_clear)(_cx_self* self) { size_t i = self->size; self->size = 0; - while (i--) { i_valdrop((self->data + i)); } + while (i--) { i_keydrop((self->data + i)); } } STC_INLINE void _cx_memb(_drop)(_cx_self* self) @@ -95,12 +95,12 @@ STC_INLINE void _cx_memb(_copy)(_cx_self *self, _cx_self other) { if (self->data == other.data) return; _cx_memb(_drop)(self); *self = _cx_memb(_clone)(other); } -STC_INLINE i_val _cx_memb(_value_clone)(_cx_value val) - { return i_valclone(val); } +STC_INLINE i_key _cx_memb(_value_clone)(_cx_value val) + { return i_keyclone(val); } #if !defined _i_no_emplace STC_INLINE void _cx_memb(_emplace)(_cx_self* self, _cx_raw raw) - { _cx_memb(_push)(self, i_valfrom(raw)); } + { _cx_memb(_push)(self, i_keyfrom(raw)); } #endif // !_i_no_emplace #endif // !_i_no_clone @@ -128,14 +128,14 @@ _cx_memb(_make_heap)(_cx_self* self) { STC_DEF _cx_self _cx_memb(_clone)(_cx_self q) { _cx_self out = _cx_memb(_with_capacity)(q.size); for (; out.size < out.capacity; ++q.data) - out.data[out.size++] = i_valclone((*q.data)); + out.data[out.size++] = i_keyclone((*q.data)); return out; } #endif STC_DEF void _cx_memb(_erase_at)(_cx_self* self, const size_t idx) { - i_valdrop((self->data + idx)); + i_keydrop((self->data + idx)); const size_t n = --self->size; self->data[idx] = self->data[n]; _cx_memb(_sift_down_)(self->data - 1, idx + 1, n); diff --git a/include/stc/cqueue.h b/include/stc/cqueue.h index a9a2fbfa..b07582e0 100644 --- a/include/stc/cqueue.h +++ b/include/stc/cqueue.h @@ -25,7 +25,7 @@ #include #include -#define i_val int +#define i_key int #include int main() { diff --git a/include/stc/csmap.h b/include/stc/csmap.h index d89a9fdc..eba9a591 100644 --- a/include/stc/csmap.h +++ b/include/stc/csmap.h @@ -67,6 +67,7 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; #define _i_SET_ONLY c_true #define _i_keyref(vp) (vp) #else + #define _i_ismap #define _i_MAP_ONLY c_true #define _i_SET_ONLY c_false #define _i_keyref(vp) (&(vp)->first) @@ -533,6 +534,7 @@ _cx_memb(_drop)(_cx_self* self) { #endif // _i_implement #undef _i_isset +#undef _i_ismap #undef _i_keyref #undef _i_MAP_ONLY #undef _i_SET_ONLY diff --git a/include/stc/cstack.h b/include/stc/cstack.h index 7e20a632..f2412184 100644 --- a/include/stc/cstack.h +++ b/include/stc/cstack.h @@ -34,19 +34,19 @@ #include "template.h" #if !c_option(c_is_fwd) -_cx_deftypes(_c_cstack_types, _cx_self, i_val); +_cx_deftypes(_c_cstack_types, _cx_self, i_key); #endif -typedef i_valraw _cx_raw; +typedef i_keyraw _cx_raw; STC_INLINE _cx_self _cx_memb(_init)(void) { return c_make(_cx_self){0, 0, 0}; } STC_INLINE _cx_self _cx_memb(_with_capacity)(size_t cap) { - _cx_self out = {(_cx_value *) c_malloc(cap*sizeof(i_val)), 0, cap}; + _cx_self out = {(_cx_value *) c_malloc(cap*sizeof(i_key)), 0, cap}; return out; } -STC_INLINE _cx_self _cx_memb(_with_size)(size_t size, i_val null) { +STC_INLINE _cx_self _cx_memb(_with_size)(size_t size, i_key null) { _cx_self out = {(_cx_value *) c_malloc(size*sizeof null), size, size}; while (size) out.data[--size] = null; return out; @@ -54,7 +54,7 @@ STC_INLINE _cx_self _cx_memb(_with_size)(size_t size, i_val null) { STC_INLINE void _cx_memb(_clear)(_cx_self* self) { _cx_value *p = self->data + self->size; - while (p-- != self->data) { i_valdrop(p); } + while (p-- != self->data) { i_keydrop(p); } self->size = 0; } @@ -92,7 +92,7 @@ STC_INLINE _cx_value* _cx_memb(_push_back)(_cx_self* self, _cx_value val) { return _cx_memb(_push)(self, val); } STC_INLINE void _cx_memb(_pop)(_cx_self* self) - { _cx_value* p = &self->data[--self->size]; i_valdrop(p); } + { _cx_value* p = &self->data[--self->size]; i_keydrop(p); } STC_INLINE void _cx_memb(_pop_back)(_cx_self* self) { _cx_memb(_pop)(self); } @@ -104,15 +104,15 @@ STC_INLINE _cx_value* _cx_memb(_at_mut)(_cx_self* self, size_t idx) #if !defined _i_no_clone #if !defined _i_no_emplace STC_INLINE _cx_value* _cx_memb(_emplace)(_cx_self* self, _cx_raw raw) - { return _cx_memb(_push)(self, i_valfrom(raw)); } + { return _cx_memb(_push)(self, i_keyfrom(raw)); } STC_INLINE _cx_value* _cx_memb(_emplace_back)(_cx_self* self, _cx_raw raw) - { return _cx_memb(_push)(self, i_valfrom(raw)); } + { return _cx_memb(_push)(self, i_keyfrom(raw)); } #endif // !_i_no_emplace STC_INLINE _cx_self _cx_memb(_clone)(_cx_self v) { _cx_self out = {(_cx_value *) c_malloc(v.size*sizeof(_cx_value)), v.size, v.size}; for (size_t i = 0; i < v.size; ++v.data) - out.data[i++] = i_valclone((*v.data)); + out.data[i++] = i_keyclone((*v.data)); return out; } @@ -121,11 +121,11 @@ STC_INLINE void _cx_memb(_copy)(_cx_self *self, _cx_self other) { _cx_memb(_drop)(self); *self = _cx_memb(_clone)(other); } -STC_INLINE i_val _cx_memb(_value_clone)(_cx_value val) - { return i_valclone(val); } +STC_INLINE i_key _cx_memb(_value_clone)(_cx_value val) + { return i_keyclone(val); } -STC_INLINE i_valraw _cx_memb(_value_toraw)(_cx_value* val) - { return i_valto(val); } +STC_INLINE i_keyraw _cx_memb(_value_toraw)(_cx_value* val) + { return i_keyto(val); } #endif // !_i_no_clone STC_INLINE _cx_iter _cx_memb(_begin)(const _cx_self* self) diff --git a/include/stc/cvec.h b/include/stc/cvec.h index b666e791..b98ecbd9 100644 --- a/include/stc/cvec.h +++ b/include/stc/cvec.h @@ -32,13 +32,13 @@ struct MyStruct { cstr name; } typedef MyStruct; -#define i_val float +#define i_key float #include -#define i_val_str // special for cstr +#define i_key_str // special for cstr #include -#define i_val int +#define i_key int #define i_opt c_is_fwd // forward declared #define i_tag i32 #include @@ -74,31 +74,31 @@ struct cvec_rep { size_t size, cap; void* data[]; }; #include "template.h" #if !c_option(c_is_fwd) - _cx_deftypes(_c_cvec_types, _cx_self, i_val); + _cx_deftypes(_c_cvec_types, _cx_self, i_key); #endif -typedef i_valraw _cx_raw; +typedef i_keyraw _cx_raw; STC_API _cx_self _cx_memb(_init)(void); STC_API void _cx_memb(_drop)(_cx_self* self); STC_API void _cx_memb(_clear)(_cx_self* self); STC_API bool _cx_memb(_reserve)(_cx_self* self, size_t cap); -STC_API bool _cx_memb(_resize)(_cx_self* self, size_t size, i_val null); -STC_API _cx_value* _cx_memb(_push)(_cx_self* self, i_val value); +STC_API bool _cx_memb(_resize)(_cx_self* self, size_t size, i_key null); +STC_API _cx_value* _cx_memb(_push)(_cx_self* self, i_key value); STC_API _cx_iter _cx_memb(_erase_range_p)(_cx_self* self, _cx_value* p1, _cx_value* p2); STC_API _cx_iter _cx_memb(_insert_range_p)(_cx_self* self, _cx_value* pos, const _cx_value* p1, const _cx_value* p2); #if !c_option(c_no_cmp) STC_API int _cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y); -STC_API _cx_iter _cx_memb(_find_in)(_cx_iter it1, _cx_iter it2, i_valraw raw); -STC_API _cx_iter _cx_memb(_bsearch_in)(_cx_iter it1, _cx_iter it2, i_valraw raw, _cx_iter* lower_bound); +STC_API _cx_iter _cx_memb(_find_in)(_cx_iter it1, _cx_iter it2, i_keyraw raw); +STC_API _cx_iter _cx_memb(_bsearch_in)(_cx_iter it1, _cx_iter it2, i_keyraw raw, _cx_iter* lower_bound); #endif #if !defined _i_no_clone STC_API _cx_self _cx_memb(_clone)(_cx_self cx); STC_API _cx_iter _cx_memb(_clone_range_p)(_cx_self* self, _cx_value* pos, const _cx_value* p1, const _cx_value* p2); -STC_INLINE i_val _cx_memb(_value_clone)(_cx_value val) - { return i_valclone(val); } -STC_INLINE i_val _cx_memb(_value_fromraw)(i_valraw raw) { return i_valfrom(raw); } +STC_INLINE i_key _cx_memb(_value_clone)(_cx_value val) + { return i_keyclone(val); } +STC_INLINE i_key _cx_memb(_value_fromraw)(i_keyraw raw) { return i_keyfrom(raw); } STC_INLINE void _cx_memb(_copy)(_cx_self *self, _cx_self other) { if (self->data == other.data) return; _cx_memb(_drop)(self); @@ -107,16 +107,16 @@ STC_INLINE void _cx_memb(_copy)(_cx_self *self, _cx_self other) { #if !defined _i_no_emplace STC_API _cx_iter _cx_memb(_emplace_range_p)(_cx_self* self, _cx_value* pos, const _cx_raw* p1, const _cx_raw* p2); -STC_INLINE _cx_value* _cx_memb(_emplace)(_cx_self* self, i_valraw raw) - { return _cx_memb(_push)(self, i_valfrom(raw)); } -STC_INLINE _cx_value* _cx_memb(_emplace_back)(_cx_self* self, i_valraw raw) - { return _cx_memb(_push)(self, i_valfrom(raw)); } +STC_INLINE _cx_value* _cx_memb(_emplace)(_cx_self* self, i_keyraw raw) + { return _cx_memb(_push)(self, i_keyfrom(raw)); } +STC_INLINE _cx_value* _cx_memb(_emplace_back)(_cx_self* self, i_keyraw raw) + { return _cx_memb(_push)(self, i_keyfrom(raw)); } STC_INLINE _cx_iter _cx_memb(_emplace_n)(_cx_self* self, const size_t idx, const _cx_raw arr[], const size_t n) { return _cx_memb(_emplace_range_p)(self, self->data + idx, arr, arr + n); } STC_INLINE _cx_iter -_cx_memb(_emplace_at)(_cx_self* self, _cx_iter it, i_valraw raw) { +_cx_memb(_emplace_at)(_cx_self* self, _cx_iter it, i_keyraw raw) { return _cx_memb(_emplace_range_p)(self, it.ref, &raw, &raw + 1); } STC_INLINE _cx_iter @@ -129,14 +129,14 @@ _cx_memb(_emplace_range)(_cx_self* self, _cx_iter it, _cx_iter it1, _cx_iter it2 STC_INLINE size_t _cx_memb(_size)(_cx_self cx) { return cvec_rep_(&cx)->size; } STC_INLINE size_t _cx_memb(_capacity)(_cx_self cx) { return cvec_rep_(&cx)->cap; } STC_INLINE bool _cx_memb(_empty)(_cx_self cx) { return !cvec_rep_(&cx)->size; } -STC_INLINE i_valraw _cx_memb(_value_toraw)(_cx_value* val) { return i_valto(val); } +STC_INLINE i_keyraw _cx_memb(_value_toraw)(_cx_value* val) { return i_keyto(val); } STC_INLINE void _cx_memb(_swap)(_cx_self* a, _cx_self* b) { c_swap(_cx_self, *a, *b); } STC_INLINE _cx_value* _cx_memb(_front)(const _cx_self* self) { return self->data; } STC_INLINE _cx_value* _cx_memb(_back)(const _cx_self* self) { return self->data + cvec_rep_(self)->size - 1; } STC_INLINE void _cx_memb(_pop)(_cx_self* self) - { _cx_value* p = &self->data[--cvec_rep_(self)->size]; i_valdrop(p); } -STC_INLINE _cx_value* _cx_memb(_push_back)(_cx_self* self, i_val value) + { _cx_value* p = &self->data[--cvec_rep_(self)->size]; i_keydrop(p); } +STC_INLINE _cx_value* _cx_memb(_push_back)(_cx_self* self, i_key value) { return _cx_memb(_push)(self, value); } STC_INLINE void _cx_memb(_pop_back)(_cx_self* self) { _cx_memb(_pop)(self); } STC_INLINE _cx_iter _cx_memb(_begin)(const _cx_self* self) @@ -149,7 +149,7 @@ STC_INLINE _cx_iter _cx_memb(_advance)(_cx_iter it, intptr_t offs) STC_INLINE size_t _cx_memb(_index)(_cx_self cx, _cx_iter it) { return it.ref - cx.data; } STC_INLINE _cx_self -_cx_memb(_with_size)(const size_t size, i_val null) { +_cx_memb(_with_size)(const size_t size, i_key null) { _cx_self cx = _cx_memb(_init)(); _cx_memb(_resize)(&cx, size, null); return cx; @@ -168,7 +168,7 @@ _cx_memb(_shrink_to_fit)(_cx_self *self) { } STC_INLINE _cx_iter -_cx_memb(_insert)(_cx_self* self, const size_t idx, i_val value) { +_cx_memb(_insert)(_cx_self* self, const size_t idx, i_key value) { return _cx_memb(_insert_range_p)(self, self->data + idx, &value, &value + 1); } STC_INLINE _cx_iter @@ -176,7 +176,7 @@ _cx_memb(_insert_n)(_cx_self* self, const size_t idx, const _cx_value arr[], con return _cx_memb(_insert_range_p)(self, self->data + idx, arr, arr + n); } STC_INLINE _cx_iter -_cx_memb(_insert_at)(_cx_self* self, _cx_iter it, i_val value) { +_cx_memb(_insert_at)(_cx_self* self, _cx_iter it, i_key value) { return _cx_memb(_insert_range_p)(self, it.ref, &value, &value + 1); } @@ -205,29 +205,29 @@ _cx_memb(_at_mut)(_cx_self* self, const size_t idx) { #if !c_option(c_no_cmp) STC_INLINE _cx_iter -_cx_memb(_find)(const _cx_self* self, i_valraw raw) { +_cx_memb(_find)(const _cx_self* self, i_keyraw raw) { return _cx_memb(_find_in)(_cx_memb(_begin)(self), _cx_memb(_end)(self), raw); } STC_INLINE const _cx_value* -_cx_memb(_get)(const _cx_self* self, i_valraw raw) { +_cx_memb(_get)(const _cx_self* self, i_keyraw raw) { _cx_iter end = _cx_memb(_end)(self); _cx_value* val = _cx_memb(_find)(self, raw).ref; return val == end.ref ? NULL : val; } STC_INLINE _cx_value* -_cx_memb(_get_mut)(const _cx_self* self, i_valraw raw) +_cx_memb(_get_mut)(const _cx_self* self, i_keyraw raw) { return (_cx_value*) _cx_memb(_get)(self, raw); } STC_INLINE _cx_iter -_cx_memb(_bsearch)(const _cx_self* self, i_valraw raw) { +_cx_memb(_bsearch)(const _cx_self* self, i_keyraw raw) { _cx_iter lower; return _cx_memb(_bsearch_in)(_cx_memb(_begin)(self), _cx_memb(_end)(self), raw, &lower); } STC_INLINE _cx_iter -_cx_memb(_lower_bound)(const _cx_self* self, i_valraw raw) { +_cx_memb(_lower_bound)(const _cx_self* self, i_keyraw raw) { _cx_iter lower; _cx_memb(_bsearch_in)(_cx_memb(_begin)(self), _cx_memb(_end)(self), raw, &lower); return lower; @@ -261,7 +261,7 @@ _cx_memb(_clear)(_cx_self* self) { struct cvec_rep* rep = cvec_rep_(self); if (rep->cap) { for (_cx_value *p = self->data, *q = p + rep->size; p != q; ) { - --q; i_valdrop(q); + --q; i_keydrop(q); } rep->size = 0; } @@ -282,7 +282,7 @@ _cx_memb(_reserve)(_cx_self* self, const size_t cap) { const size_t len = rep->size; if (cap > rep->cap || (cap && cap == len)) { rep = (struct cvec_rep*) c_realloc(rep->cap ? rep : NULL, - offsetof(struct cvec_rep, data) + cap*sizeof(i_val)); + offsetof(struct cvec_rep, data) + cap*sizeof(i_key)); if (!rep) return false; self->data = (_cx_value*) rep->data; rep->size = len; @@ -292,18 +292,18 @@ _cx_memb(_reserve)(_cx_self* self, const size_t cap) { } STC_DEF bool -_cx_memb(_resize)(_cx_self* self, const size_t len, i_val null) { +_cx_memb(_resize)(_cx_self* self, const size_t len, i_key null) { if (!_cx_memb(_reserve)(self, len)) return false; struct cvec_rep *rep = cvec_rep_(self); const size_t n = rep->size; - for (size_t i = len; i < n; ++i) { i_valdrop((self->data + i)); } + for (size_t i = len; i < n; ++i) { i_keydrop((self->data + i)); } for (size_t i = n; i < len; ++i) self->data[i] = null; if (rep->cap) rep->size = len; return true; } STC_DEF _cx_value* -_cx_memb(_push)(_cx_self* self, i_val value) { +_cx_memb(_push)(_cx_self* self, i_key value) { struct cvec_rep *r = cvec_rep_(self); if (r->size == r->cap) { _cx_memb(_reserve)(self, (r->size*3 >> 1) + 4); @@ -342,8 +342,8 @@ _cx_memb(_erase_range_p)(_cx_self* self, _cx_value* p1, _cx_value* p2) { intptr_t len = p2 - p1; if (len > 0) { _cx_value* p = p1, *end = self->data + cvec_rep_(self)->size; - for (; p != p2; ++p) { i_valdrop(p); } - memmove(p1, p2, (end - p2) * sizeof(i_val)); + for (; p != p2; ++p) { i_keydrop(p); } + memmove(p1, p2, (end - p2) * sizeof(i_key)); cvec_rep_(self)->size -= len; } return c_make(_cx_iter){.ref = p1}; @@ -364,7 +364,7 @@ _cx_memb(_clone_range_p)(_cx_self* self, _cx_value* pos, pos = _cx_memb(_insert_space_)(self, pos, p2 - p1); _cx_iter it = {pos}; for (; p1 != p2; ++p1) - *pos++ = i_valclone((*p1)); + *pos++ = i_keyclone((*p1)); return it; } @@ -374,7 +374,7 @@ _cx_memb(_emplace_range_p)(_cx_self* self, _cx_value* pos, const _cx_raw* p1, const _cx_raw* p2) { pos = _cx_memb(_insert_space_)(self, pos, p2 - p1); _cx_iter it = {pos}; - for (; p1 != p2; ++p1) *pos++ = i_valfrom((*p1)); + for (; p1 != p2; ++p1) *pos++ = i_keyfrom((*p1)); return it; } #endif // !_i_no_emplace @@ -382,20 +382,20 @@ _cx_memb(_emplace_range_p)(_cx_self* self, _cx_value* pos, #if !c_option(c_no_cmp) STC_DEF _cx_iter -_cx_memb(_find_in)(_cx_iter i1, _cx_iter i2, i_valraw raw) { +_cx_memb(_find_in)(_cx_iter i1, _cx_iter i2, i_keyraw raw) { for (; i1.ref != i2.ref; ++i1.ref) { - i_valraw r = i_valto(i1.ref); + i_keyraw r = i_keyto(i1.ref); if (i_eq((&raw), (&r))) return i1; } return i2; } STC_DEF _cx_iter -_cx_memb(_bsearch_in)(_cx_iter i1, _cx_iter i2, i_valraw raw, _cx_iter* lower_bound) { +_cx_memb(_bsearch_in)(_cx_iter i1, _cx_iter i2, i_keyraw raw, _cx_iter* lower_bound) { _cx_iter mid, last = i2; while (i1.ref != i2.ref) { mid.ref = i1.ref + ((i2.ref - i1.ref) >> 1); - int c; i_valraw m = i_valto(mid.ref); + int c; i_keyraw m = i_keyto(mid.ref); if (!(c = i_cmp((&raw), (&m)))) return *lower_bound = mid; else if (c < 0) i2.ref = mid.ref; else i1.ref = mid.ref + 1; @@ -406,8 +406,8 @@ _cx_memb(_bsearch_in)(_cx_iter i1, _cx_iter i2, i_valraw raw, _cx_iter* lower_bo STC_DEF int _cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y) { - i_valraw rx = i_valto(x); - i_valraw ry = i_valto(y); + i_keyraw rx = i_keyto(x); + i_keyraw ry = i_keyto(y); return i_cmp((&rx), (&ry)); } #endif // !c_no_cmp diff --git a/include/stc/template.h b/include/stc/template.h index 8d8bd6dc..6f784c35 100644 --- a/include/stc/template.h +++ b/include/stc/template.h @@ -54,6 +54,41 @@ #include "cstr.h" #endif +#if !(defined i_key || defined i_key_str || defined i_key_bind || defined i_key_arcbox) + #define _i_key_from_val + #if defined _i_ismap + #error "i_key* must be defined for maps." + #endif + + #if defined i_val_str + #define i_key_str i_val_str + #endif + #if defined i_val_arcbox + #define i_key_arcbox i_val_arcbox + #endif + #if defined i_val_bind + #define i_key_bind i_val_bind + #endif + #if defined i_val + #define i_key i_val + #endif + #if defined i_valraw + #define i_keyraw i_valraw + #endif + #if defined i_valclone + #define i_keyclone i_valclone + #endif + #if defined i_valfrom + #define i_keyfrom i_valfrom + #endif + #if defined i_valto + #define i_keyto i_valto + #endif + #if defined i_valdrop + #define i_keydrop i_valdrop + #endif +#endif + #ifdef i_key_str #define i_key_bind cstr #define i_keyraw crawstr @@ -63,6 +98,7 @@ #elif defined i_key_arcbox #define i_key_bind i_key_arcbox #define i_keyraw c_paste(i_key_arcbox, _value) + // smart pointers have special clone, so override: #define i_keyclone c_paste(i_key_arcbox, _clone) #define _i_no_emplace #endif @@ -81,21 +117,25 @@ #define i_keyto c_paste(i_key, _toraw) #endif #endif + #ifndef i_keydrop + #define i_keydrop c_paste(i_key, _drop) + #endif #ifndef i_cmp #define i_cmp c_paste(i_keyraw, _cmp) #endif - #ifndef i_eq - #define i_eq c_paste(i_keyraw, _eq) - #endif - #ifndef i_hash - #define i_hash c_paste(i_keyraw, _hash) - #endif - #ifndef i_keydrop - #define i_keydrop c_paste(i_key, _drop) + #if defined _i_ishash + #ifndef i_eq + #define i_eq c_paste(i_keyraw, _eq) + #endif + #if !defined i_hash + #define i_hash c_paste(i_keyraw, _hash) + #endif #endif #endif -#if defined i_keyraw && !defined i_keyfrom +#if !defined i_key + #error "no i_key or i_val provided" +#elif defined i_keyraw && !defined i_keyfrom #error "if i_keyraw is defined, i_keyfrom (and normally i_keyto) must be defined" #elif defined i_drop #error "i_drop not supported. Define i_keydrop/i_valdrop instead." @@ -103,12 +143,49 @@ #error "i_from not supported. Define i_keyfrom/i_valfrom instead." #endif +#ifndef i_tag + #define i_tag i_key +#endif +#if (!defined i_keyfrom && defined i_keydrop) || c_option(c_no_clone) + #define _i_no_clone +#endif +#if !defined i_hash && (defined i_keyfrom || defined i_keyclone || defined i_cmp || defined i_eq) + #define _i_no_hash +#endif +#ifndef i_keyfrom + #define i_keyfrom c_default_from +#endif +#ifndef i_keyraw + #define i_keyraw i_key +#else + #define _i_has_raw +#endif +#ifndef i_keyto + #define i_keyto c_default_toraw +#endif +#ifndef i_keyclone + #define i_keyclone(key) i_keyfrom((i_keyto((&(key))))) +#endif +#ifndef i_keydrop + #define i_keydrop c_default_drop +#endif +#if !defined i_eq && defined i_cmp + #define i_eq(x, y) !(i_cmp(x, y)) +#elif !defined i_eq + #define i_eq c_default_eq +#endif +#ifndef i_cmp + #define i_cmp c_default_cmp +#endif +#ifndef i_hash + #define i_hash c_default_hash +#endif + +#if defined _i_ismap // ---- process cmap/csmap value i_val, ... ---- + #ifdef i_val_str #define i_val_bind cstr #define i_valraw crawstr - #if !defined i_tag && !defined i_key - #define i_tag str - #endif #elif defined i_val_arcbox #define i_val_bind i_val_arcbox #define i_valraw c_paste(i_val_arcbox, _value) @@ -130,15 +207,6 @@ #define i_valto c_paste(i_val, _toraw) #endif #endif - #if !defined i_cmp && !defined i_key - #define i_cmp c_paste(i_valraw, _cmp) - #endif - #if !defined i_hash && c_option(c_hash) - #define i_hash c_paste(i_val, _hash) - #endif - #if !defined i_eq && c_option(c_eq) - #define i_eq c_paste(i_val, _eq) - #endif #ifndef i_valdrop #define i_valdrop c_paste(i_val, _drop) #endif @@ -148,69 +216,7 @@ #error "if i_valraw is defined, i_valfrom (and normally i_valto) must be defined" #endif -#if !defined i_keyraw && !defined i_valraw - #define _i_no_emplace -#endif - -/* Copy i_val* macros to i_key* if _i_isset */ -#if defined _i_isset && defined i_val - #if !defined i_key - #define i_key i_val - #endif - #if defined i_valraw && !defined i_keyraw - #define i_keyraw i_valraw - #endif - #if defined i_valclone && !defined i_keyclone - #define i_keyclone i_valclone - #endif - #if defined i_valfrom && !defined i_keyfrom - #define i_keyfrom i_valfrom - #endif - #if defined i_valto && !defined i_keyto - #define i_keyto i_valto - #endif - #if defined i_valdrop && !defined i_keydrop - #define i_keydrop i_valdrop - #endif -#endif - -#ifdef i_key - #if defined _i_isset && !defined i_val - #define i_val i_key - #endif - #ifndef i_tag - #define i_tag i_key - #endif - #if !defined i_keyfrom && defined i_keydrop - #define _i_no_clone - #endif - #if !defined i_hash && (defined i_keyfrom || defined i_cmp || defined i_eq) - #define _i_no_hash 1 - #endif - #if !defined i_cmp && !defined i_eq && defined i_hash - #define _i_no_hash 2 - #endif - #ifndef i_keyfrom - #define i_keyfrom c_default_from - #endif - #ifndef i_keyraw - #define i_keyraw i_key - #endif - #ifndef i_keyto - #define i_keyto c_default_toraw - #endif - #ifndef i_keyclone - #define i_keyclone(key) i_keyfrom((i_keyto((&(key))))) - #endif - #ifndef i_keydrop - #define i_keydrop c_default_drop - #endif -#endif - -#ifndef i_tag - #define i_tag i_val -#endif -#if (!defined i_valfrom && defined i_valdrop) || c_option(c_no_clone) +#if !defined i_valfrom && defined i_valdrop #define _i_no_clone #endif #ifndef i_valfrom @@ -218,6 +224,8 @@ #endif #ifndef i_valraw #define i_valraw i_val +#else + #define _i_has_raw #endif #ifndef i_valto #define i_valto c_default_toraw @@ -228,19 +236,20 @@ #ifndef i_valdrop #define i_valdrop c_default_drop #endif -#if !defined i_eq && defined i_cmp - #define i_eq(x, y) !(i_cmp(x, y)) -#elif !defined i_eq - #define i_eq c_default_eq + +#endif // !_i_ismap + +#ifndef i_val + #define i_val i_key #endif -#ifndef i_cmp - #define i_cmp c_default_cmp +#ifndef i_valraw + #define i_valraw i_keyraw #endif -#ifndef i_hash - #define i_hash c_default_hash +#ifndef _i_has_raw + #define _i_no_emplace #endif -#else // ------------------------------------------------------- +#else // ============================================================ #undef i_type #undef i_tag @@ -256,22 +265,24 @@ #undef i_val_arcbox #undef i_val_bind #undef i_valraw +#undef i_valclone #undef i_valfrom #undef i_valto #undef i_valdrop -#undef i_valclone #undef i_key #undef i_key_str #undef i_key_arcbox #undef i_key_bind #undef i_keyraw +#undef i_keyclone #undef i_keyfrom #undef i_keyto #undef i_keydrop -#undef i_keyclone #undef _i_prefix +#undef _i_has_raw +#undef _i_key_from_val #undef _i_no_clone #undef _i_no_emplace #undef _i_no_hash -- cgit v1.2.3 From 0e8bca60bd74ff7c6dfca88aca824f8d5907a992 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 21 Apr 2022 16:58:03 +0200 Subject: Fix for i_key_bind hash and eq functions. --- include/stc/template.h | 12 +++++------- 1 file changed, 5 insertions(+), 7 deletions(-) diff --git a/include/stc/template.h b/include/stc/template.h index 6f784c35..f614cd58 100644 --- a/include/stc/template.h +++ b/include/stc/template.h @@ -123,13 +123,11 @@ #ifndef i_cmp #define i_cmp c_paste(i_keyraw, _cmp) #endif - #if defined _i_ishash - #ifndef i_eq - #define i_eq c_paste(i_keyraw, _eq) - #endif - #if !defined i_hash - #define i_hash c_paste(i_keyraw, _hash) - #endif + #if !defined i_eq && (defined _i_ishash || c_option(c_eq)) + #define i_eq c_paste(i_keyraw, _eq) + #endif + #if !defined i_hash && (defined _i_ishash || c_option(c_hash)) + #define i_hash c_paste(i_keyraw, _hash) #endif #endif -- cgit v1.2.3 From 182099800f230f876fb46dac9f1f49a4fe3c3981 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 22 Apr 2022 00:18:56 +0200 Subject: Swapped cstr.h with alt/cstr.h with SSO (short string optimization). #define STC_OLD_CSTR 1 to use previous string (only 8 byte rep). --- include/stc/alt/cstr.h | 590 +++++++++++++++++++++--------------------------- include/stc/cstr.h | 591 ++++++++++++++++++++++++++++--------------------- include/stc/forward.h | 2 +- 3 files changed, 591 insertions(+), 592 deletions(-) diff --git a/include/stc/alt/cstr.h b/include/stc/alt/cstr.h index d6fed8e6..437ce5f9 100644 --- a/include/stc/alt/cstr.h +++ b/include/stc/alt/cstr.h @@ -20,106 +20,125 @@ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ - -/* A string type with short string optimization in C99 with optimal short string - * utilization (23 characters with 24 bytes string representation). - */ #ifndef CSTR_H_INCLUDED #define CSTR_H_INCLUDED -#define STC_USE_SSO 1 +#define STC_OLD_CSTR 1 #include #include #include /* malloc */ +#include #include #include /* vsnprintf */ #include -/**************************** PRIVATE API **********************************/ - -#if defined __GNUC__ && !defined __clang__ -# pragma GCC diagnostic push -# pragma GCC diagnostic ignored "-Warray-bounds" -# pragma GCC diagnostic ignored "-Wstringop-overflow=" -#endif - -enum { cstr_s_cap = sizeof(cstr_rep_t) - 1 }; -#define cstr_s_size(s) ((size_t)(cstr_s_cap - (s)->sml.last)) -#define cstr_s_set_size(s, len) ((s)->sml.last = cstr_s_cap - (len), (s)->sml.data[len] = 0) -#define cstr_s_data(s) (s)->sml.data -#define cstr_s_end(s) ((s)->sml.data + cstr_s_size(s)) - -#if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ - #define byte_rotl_(x, b) ((x) << (b)*8 | (x) >> (sizeof(x) - (b))*8) - #define cstr_l_cap(s) (~byte_rotl_((s)->lon.ncap, sizeof((s)->lon.ncap) - 1)) - #define cstr_l_set_cap(s, cap) ((s)->lon.ncap = ~byte_rotl_(cap, 1)) +#define cstr_npos (SIZE_MAX >> 1) +typedef struct { size_t size, cap; char chr[1]; } cstr_priv; +#define _cstr_p(self) c_container_of((self)->str, cstr_priv, chr) +#ifdef _i_static + static cstr_priv _cstr_nullrep = {0, 0, {0}}; + static const cstr cstr_null = {_cstr_nullrep.chr}; #else - #define cstr_l_cap(s) (~(s)->lon.ncap) - #define cstr_l_set_cap(s, cap) ((s)->lon.ncap = ~(cap)) + extern const cstr cstr_null; #endif -#define cstr_l_size(s) ((s)->lon.size) -#define cstr_l_set_size(s, len) ((s)->lon.data[(s)->lon.size = (len)] = 0) -#define cstr_l_data(s) (s)->lon.data -#define cstr_l_end(s) ((s)->lon.data + cstr_l_size(s)) -#define cstr_l_drop(s) c_free((s)->lon.data) - -#define cstr_is_long(s) ((s)->sml.last > 127) -STC_API char* _cstr_init(cstr* self, size_t len, size_t cap); -STC_API char* _cstr_internal_move(cstr* self, size_t pos1, size_t pos2); - -/**************************** PUBLIC API **********************************/ - -#define cstr_new(literal) cstr_from_n(literal, c_strlen_lit(literal)) -#define cstr_npos (SIZE_MAX >> 1) -#define cstr_null (c_make(cstr){.sml = {.last = cstr_s_cap}}) -#define cstr_toraw(self) cstr_str(self) - -STC_API char* cstr_reserve(cstr* self, size_t cap); -STC_API void cstr_shrink_to_fit(cstr* self); -STC_API void cstr_resize(cstr* self, size_t size, char value); -STC_API size_t cstr_find_n(cstr s, const char* needle, size_t pos, size_t nmax); -STC_API cstr* cstr_assign_n(cstr* self, const char* str, size_t n); -STC_API cstr* cstr_append_n(cstr* self, const char* str, size_t n); -STC_API bool cstr_getdelim(cstr *self, int delim, FILE *fp); -STC_API void cstr_erase_n(cstr* self, size_t pos, size_t n); -STC_API cstr cstr_from_fmt(const char* fmt, ...); -STC_API int cstr_printf(cstr* self, const char* fmt, ...); -STC_API void cstr_replace_all(cstr* self, const char* find, const char* repl); - -STC_INLINE cstr_rep_t cstr_rep(cstr* s) { - return cstr_is_long(s) - ? c_make(cstr_rep_t){s->lon.data, cstr_l_size(s), cstr_l_cap(s)} - : c_make(cstr_rep_t){s->sml.data, cstr_s_size(s), cstr_s_cap}; -} - -STC_INLINE cstr cstr_init(void) - { return cstr_null; } - -STC_INLINE cstr cstr_from_n(const char* str, const size_t n) { - cstr s; - memcpy(_cstr_init(&s, n, n), str, n); - return s; +/* optimal memory: based on malloc_usable_size() sequence: 24, 40, 56, ... */ +#define _cstr_opt_mem(cap) ((((offsetof(cstr_priv, chr) + (cap) + 8)>>4)<<4) + 8) +/* optimal string capacity: 7, 23, 39, ... */ +#define _cstr_opt_cap(cap) (_cstr_opt_mem(cap) - offsetof(cstr_priv, chr) - 1) + +STC_API cstr cstr_from_n(const char* str, size_t n); +STC_API cstr cstr_from_fmt(const char* fmt, ...); +STC_API cstr cstr_from_replace_all(const char* str, size_t str_len, + const char* find, size_t find_len, + const char* repl, size_t repl_len); +STC_API char* cstr_reserve(cstr* self, size_t cap); +STC_API void cstr_resize(cstr* self, size_t len, char fill); +STC_API cstr* cstr_assign_n(cstr* self, const char* str, size_t n); +STC_API int cstr_printf(cstr* self, const char* fmt, ...); +STC_API cstr* cstr_append_n(cstr* self, const char* str, size_t n); +STC_API void cstr_replace_n(cstr* self, size_t pos, size_t len, const char* str, size_t n); +STC_API void cstr_replace_all(cstr* self, const char* find, const char* replace); +STC_API void cstr_erase_n(cstr* self, size_t pos, size_t n); +STC_API size_t cstr_find(cstr s, const char* needle); +STC_API size_t cstr_find_n(cstr s, const char* needle, size_t pos, size_t nmax); +STC_API bool cstr_getdelim(cstr *self, int delim, FILE *stream); +STC_API void cstr_replace_all(cstr* self, const char* find, const char* repl); + +STC_INLINE cstr cstr_init() { return cstr_null; } +#define cstr_toraw(self) (self)->str +#define cstr_new(literal) \ + cstr_from_n(literal, c_strlen_lit(literal)) +STC_INLINE cstr cstr_from(const char* str) + { return cstr_from_n(str, strlen(str)); } +STC_INLINE const char* cstr_str(const cstr* self) { return self->str; } +STC_INLINE char* cstr_data(cstr* self) { return self->str; } +STC_INLINE size_t cstr_size(cstr s) { return _cstr_p(&s)->size; } +STC_INLINE size_t cstr_length(cstr s) { return _cstr_p(&s)->size; } +STC_INLINE size_t cstr_capacity(cstr s) { return _cstr_p(&s)->cap; } +STC_INLINE bool cstr_empty(cstr s) { return _cstr_p(&s)->size == 0; } +STC_INLINE void cstr_drop(cstr* self) + { if (_cstr_p(self)->cap) c_free(_cstr_p(self)); } +STC_INLINE cstr cstr_clone(cstr s) + { return cstr_from_n(s.str, _cstr_p(&s)->size); } +STC_INLINE void cstr_clear(cstr* self) + { self->str[_cstr_p(self)->size = 0] = '\0'; } +STC_INLINE cstr* cstr_assign(cstr* self, const char* str) + { return cstr_assign_n(self, str, strlen(str)); } +STC_INLINE cstr* cstr_copy(cstr* self, cstr s) + { return cstr_assign_n(self, s.str, _cstr_p(&s)->size); } +STC_INLINE cstr* cstr_append(cstr* self, const char* str) + { return cstr_append_n(self, str, strlen(str)); } +STC_INLINE cstr* cstr_append_s(cstr* self, cstr s) + { return cstr_append_n(self, s.str, _cstr_p(&s)->size); } +STC_INLINE void cstr_push_back(cstr* self, char value) + { cstr_append_n(self, &value, 1); } +STC_INLINE void cstr_pop_back(cstr* self) + { self->str[ --_cstr_p(self)->size ] = '\0'; } +STC_INLINE void cstr_insert_n(cstr* self, const size_t pos, const char* str, const size_t n) + { cstr_replace_n(self, pos, 0, str, n); } +STC_INLINE void cstr_insert(cstr* self, const size_t pos, const char* str) + { cstr_replace_n(self, pos, 0, str, strlen(str)); } +STC_INLINE void cstr_insert_s(cstr* self, const size_t pos, cstr s) + { cstr_replace_n(self, pos, 0, s.str, _cstr_p(&s)->size); } +STC_INLINE void cstr_replace(cstr* self, const size_t pos, const size_t len, const char* str) + { cstr_replace_n(self, pos, len, str, strlen(str)); } +STC_INLINE void cstr_replace_s(cstr* self, const size_t pos, const size_t len, cstr s) + { cstr_replace_n(self, pos, len, s.str, _cstr_p(&s)->size); } +STC_INLINE void cstr_erase(cstr* self, const size_t pos) + { cstr_erase_n(self, pos, 1); } +STC_INLINE char* cstr_front(cstr* self) { return self->str; } +STC_INLINE char* cstr_back(cstr* self) + { return self->str + _cstr_p(self)->size - 1; } +STC_INLINE bool cstr_equals(cstr s, const char* str) + { return strcmp(s.str, str) == 0; } +STC_INLINE bool cstr_equals_s(cstr s1, cstr s2) + { return strcmp(s1.str, s2.str) == 0; } +STC_INLINE bool cstr_contains(cstr s, const char* needle) + { return strstr(s.str, needle) != NULL; } +STC_INLINE bool cstr_getline(cstr *self, FILE *stream) + { return cstr_getdelim(self, '\n', stream); } + +STC_INLINE cstr_rep_t cstr_rep(cstr* s) { + cstr_priv* p = _cstr_p(s); + return c_make(cstr_rep_t){s->str, p->size, p->cap}; } -STC_INLINE cstr cstr_from(const char* str) - { return cstr_from_n(str, strlen(str)); } - -STC_INLINE cstr cstr_with_size(const size_t size, const char value) { - cstr s; - memset(_cstr_init(&s, size, size), value, size); +STC_INLINE cstr cstr_with_capacity(const size_t cap) { + cstr s = cstr_null; + cstr_reserve(&s, cap); return s; } -STC_INLINE cstr cstr_with_capacity(const size_t cap) { - cstr s; - _cstr_init(&s, 0, cap); +STC_INLINE cstr cstr_with_size(const size_t len, const char fill) { + cstr s = cstr_null; + cstr_resize(&s, len, fill); return s; } -STC_INLINE cstr* cstr_take(cstr* self, const cstr s) { - if (cstr_is_long(self) && self->lon.data != s.lon.data) - cstr_l_drop(self); - *self = s; +STC_INLINE cstr* cstr_take(cstr* self, cstr s) { + if (self->str != s.str && _cstr_p(self)->cap) + c_free(_cstr_p(self)); + self->str = s.str; return self; } @@ -129,253 +148,155 @@ STC_INLINE cstr cstr_move(cstr* self) { return tmp; } -STC_INLINE cstr cstr_clone(cstr s) { - cstr_rep_t r = cstr_rep(&s); - return cstr_from_n(r.data, r.size); -} - -STC_INLINE void cstr_drop(cstr* self) { - if (cstr_is_long(self)) - cstr_l_drop(self); -} - -STC_INLINE void cstr_clear(cstr* self) { - cstr_drop(self); - cstr_s_set_size(self, 0); -} - -#define SSO_CALL(s, call) (cstr_is_long(s) ? cstr_l_##call : cstr_s_##call) - -STC_INLINE void _cstr_set_size(cstr* self, size_t len) - { SSO_CALL(self, set_size(self, len)); } - -STC_INLINE char* cstr_data(cstr* self) - { return SSO_CALL(self, data(self)); } - -STC_INLINE const char* cstr_str(const cstr* self) - { return SSO_CALL(self, data(self)); } - -STC_INLINE bool cstr_empty(cstr s) - { return s.sml.last == cstr_s_cap; } - -STC_INLINE size_t cstr_size(cstr s) - { return SSO_CALL(&s, size(&s)); } - -STC_INLINE size_t cstr_length(cstr s) - { return SSO_CALL(&s, size(&s)); } - -STC_INLINE size_t cstr_capacity(cstr s) - { return cstr_is_long(&s) ? cstr_l_cap(&s) : cstr_s_cap; } - -STC_INLINE bool cstr_equals(cstr s1, const char* str) - { return strcmp(cstr_str(&s1), str) == 0; } - -STC_INLINE bool cstr_equals_s(cstr s1, cstr s2) - { return strcmp(cstr_str(&s1), cstr_str(&s2)) == 0; } - -STC_INLINE bool cstr_eq(const cstr* s1, const cstr* s2) - { return strcmp(cstr_str(s1), cstr_str(s2)) == 0; } - -STC_INLINE int cstr_cmp(const cstr* s1, const cstr* s2) - { return strcmp(cstr_str(s1), cstr_str(s2)); } - -STC_INLINE size_t cstr_find(cstr s, const char* needle) { - const char *str = cstr_str(&s), *res = strstr(str, needle); - return res ? res - str : cstr_npos; -} - -STC_INLINE bool cstr_find_s(cstr s, cstr needle) - { return cstr_find(s, cstr_str(&needle)); } - -STC_INLINE bool cstr_contains(cstr s, const char* needle) - { return strstr(cstr_str(&s), needle) != NULL; } - -STC_INLINE bool cstr_contains_s(cstr s, cstr needle) - { return strstr(cstr_str(&s), cstr_str(&needle)) != NULL; } - STC_INLINE bool cstr_starts_with(cstr s, const char* sub) { - const char* str = cstr_str(&s); - while (*sub && *str == *sub) ++str, ++sub; + while (*sub && *s.str == *sub) ++s.str, ++sub; return *sub == 0; } -STC_INLINE bool cstr_starts_with_s(cstr s, cstr sub) - { return cstr_starts_with(s, cstr_str(&sub)); } - STC_INLINE bool cstr_ends_with(cstr s, const char* sub) { - cstr_rep_t r = cstr_rep(&s); size_t n = strlen(sub); - return n <= r.size && memcmp(r.data + r.size - n, sub, n) == 0; -} - -STC_INLINE bool cstr_ends_with_s(cstr s, cstr sub) - { return cstr_ends_with(s, cstr_str(&sub)); } - -STC_INLINE void cstr_assign(cstr* self, const char* str) - { cstr_assign_n(self, str, strlen(str)); } - -STC_INLINE void cstr_copy(cstr* self, cstr s) { - cstr_rep_t r = cstr_rep(&s); - cstr_assign_n(self, r.data, r.size); -} - -STC_INLINE void cstr_append(cstr* self, const char* str) - { cstr_append_n(self, str, strlen(str)); } - -STC_INLINE void cstr_append_s(cstr* self, cstr s) { - cstr_rep_t r = cstr_rep(&s); - cstr_append_n(self, r.data, r.size); -} - -STC_INLINE void cstr_replace_n(cstr* self, size_t pos, size_t len, const char* str, size_t n) { - char* d = _cstr_internal_move(self, pos + len, pos + n); - memcpy(d + pos, str, n); -} - -STC_INLINE void cstr_replace(cstr* self, size_t pos, size_t len, const char* str) - { cstr_replace_n(self, pos, len, str, strlen(str)); } - -STC_INLINE void cstr_replace_s(cstr* self, size_t pos, size_t len, cstr s) { - cstr_rep_t r = cstr_rep(&s); - cstr_replace_n(self, pos, len, r.data, r.size); + const size_t n = strlen(sub), sz = _cstr_p(&s)->size; + return n <= sz && !memcmp(s.str + sz - n, sub, n); } -STC_INLINE void cstr_insert_n(cstr* self, size_t pos, const char* str, size_t n) - { cstr_replace_n(self, pos, 0, str, n); } - -STC_INLINE void cstr_insert(cstr* self, size_t pos, const char* str) - { cstr_replace_n(self, pos, 0, str, strlen(str)); } - -STC_INLINE void cstr_insert_s(cstr* self, size_t pos, cstr s) { - cstr_rep_t r = cstr_rep(&s); - cstr_replace_n(self, pos, 0, r.data, r.size); +STC_INLINE int c_strncasecmp(const char* s1, const char* s2, size_t nmax) { + int ret = 0; + while (nmax-- && (ret = tolower(*s1++) - tolower(*s2)) == 0 && *s2++) + ; + return ret; } -STC_INLINE bool cstr_getline(cstr *self, FILE *fp) - { return cstr_getdelim(self, '\n', fp); } - /* container adaptor functions: */ -#define cstr_cmp(xp, yp) strcmp(cstr_str(xp), cstr_str(yp)) +#define cstr_cmp(xp, yp) strcmp((xp)->str, (yp)->str) #define cstr_eq(xp, yp) (!cstr_cmp(xp, yp)) -#define cstr_hash(xp, dummy) c_strhash(cstr_str(xp)) +#define cstr_hash(xp, dummy) c_strhash((xp)->str) /* -------------------------- IMPLEMENTATION ------------------------- */ #if defined(_i_implement) -STC_DEF char* _cstr_internal_move(cstr* self, const size_t pos1, const size_t pos2) { - cstr_rep_t r = cstr_rep(self); - if (pos1 != pos2) { - const size_t newlen = r.size + pos2 - pos1; - if (newlen > r.cap) - r.data = cstr_reserve(self, (r.size*3 >> 1) + pos2 - pos1); - memmove(&r.data[pos2], &r.data[pos1], r.size - pos1); - _cstr_set_size(self, newlen); +#ifndef _i_static +static cstr_priv _cstr_nullrep = {0, 0, {0}}; +const cstr cstr_null = {_cstr_nullrep.chr}; +#endif + +STC_DEF char* +cstr_reserve(cstr* self, const size_t cap) { + cstr_priv* p = _cstr_p(self); + const size_t oldcap = p->cap; + if (cap > oldcap) { + p = (cstr_priv*) c_realloc(((oldcap != 0) & (p != &_cstr_nullrep)) ? p : NULL, _cstr_opt_mem(cap)); + self->str = p->chr; + if (oldcap == 0) self->str[p->size = 0] = '\0'; + p->cap = _cstr_opt_cap(cap); } - return r.data; + return self->str; } -STC_DEF char* _cstr_init(cstr* self, const size_t len, const size_t cap) { - if (cap > cstr_s_cap) { - self->lon.data = (char *)c_malloc(cap + 1); - cstr_l_set_size(self, len); - cstr_l_set_cap(self, cap); - return self->lon.data; - } - cstr_s_set_size(self, len); - return self->sml.data; +STC_DEF void +cstr_resize(cstr* self, const size_t len, const char fill) { + const size_t n = _cstr_p(self)->size; + cstr_reserve(self, len); + if (len > n) memset(self->str + n, fill, len - n); + if (len | n) self->str[_cstr_p(self)->size = len] = '\0'; } -STC_DEF void cstr_shrink_to_fit(cstr* self) { - cstr_rep_t r = cstr_rep(self); - if (r.size == r.cap) - return; - if (r.size > cstr_s_cap) { - self->lon.data = (char *)c_realloc(self->lon.data, r.size + 1); - cstr_l_set_cap(self, r.size); - } else if (r.cap > cstr_s_cap) { - memcpy(self->sml.data, r.data, r.size + 1); - cstr_s_set_size(self, r.size); - c_free(r.data); - } +STC_DEF cstr +cstr_from_n(const char* str, const size_t n) { + if (n == 0) return cstr_null; + cstr_priv* prv = (cstr_priv*) c_malloc(_cstr_opt_mem(n)); + cstr s = {(char *) memcpy(prv->chr, str, n)}; + s.str[prv->size = n] = '\0'; + prv->cap = _cstr_opt_cap(n); + return s; } -STC_DEF char* cstr_reserve(cstr* self, const size_t cap) { - if (cstr_is_long(self)) { - if (cap > cstr_l_cap(self)) { - self->lon.data = (char *)c_realloc(self->lon.data, cap + 1); - cstr_l_set_cap(self, cap); - } - return self->lon.data; - } - /* from short to long: */ - if (cap > cstr_s_cap) { - char* data = (char *)c_malloc(cap + 1); - const size_t len = cstr_s_size(self); - memcpy(data, self->sml.data, len); - self->lon.data = data; - cstr_l_set_size(self, len); - cstr_l_set_cap(self, cap); - return data; - } - return self->sml.data; +#if defined(__clang__) +# pragma clang diagnostic push +# pragma clang diagnostic ignored "-Wdeprecated-declarations" +#elif defined(_MSC_VER) +# pragma warning(push) +# pragma warning(disable: 4996) +#endif + +STC_DEF int +cstr_vfmt(cstr* self, const char* fmt, va_list args) { + va_list args2; + va_copy(args2, args); + int len = vsnprintf(NULL, (size_t)0, fmt, args); + cstr_reserve(self, len); + vsprintf(self->str, fmt, args2); + va_end(args2); + return _cstr_p(self)->size = len; } -STC_DEF void cstr_resize(cstr* self, const size_t size, const char value) { - cstr_rep_t r = cstr_rep(self); - if (size > r.size) { - if (size > r.cap) r.data = cstr_reserve(self, size); - memset(r.data + r.size, value, size - r.size); - } - _cstr_set_size(self, size); +#if defined(__clang__) +# pragma clang diagnostic pop +#elif defined(_MSC_VER) +# pragma warning(pop) +#endif + +STC_DEF cstr +cstr_from_fmt(const char* fmt, ...) { + cstr ret = cstr_null; + va_list args; va_start(args, fmt); + cstr_vfmt(&ret, fmt, args); + va_end(args); + return ret; } -STC_DEF size_t cstr_find_n(cstr s, const char* needle, const size_t pos, const size_t nmax) { - cstr_rep_t r = cstr_rep(&s); - const size_t nlen = (size_t) strlen(needle); - if (pos > r.size) return cstr_npos; - char* res = c_strnstrn(r.data + pos, needle, r.size, nmax < nlen ? nmax : nlen); - return res ? res - r.data : cstr_npos; +STC_DEF int +cstr_printf(cstr* self, const char* fmt, ...) { + cstr ret = cstr_null; + va_list args; + va_start(args, fmt); + int n = cstr_vfmt(&ret, fmt, args); + va_end(args); + cstr_drop(self); + *self = ret; + return n; } -STC_DEF cstr* cstr_assign_n(cstr* self, const char* str, const size_t n) { - cstr_rep_t r = cstr_rep(self); - if (n > r.cap) { - r.data = (char *)c_realloc(cstr_is_long(self) ? r.data : NULL, n + 1); - cstr_l_set_cap(self, n); +STC_DEF cstr* +cstr_assign_n(cstr* self, const char* str, const size_t n) { + if (n || _cstr_p(self)->cap) { + cstr_reserve(self, n); + memmove(self->str, str, n); + self->str[_cstr_p(self)->size = n] = '\0'; } - memmove(r.data, str, n); - _cstr_set_size(self, n); return self; } -STC_DEF cstr* cstr_append_n(cstr* self, const char* str, const size_t n) { - cstr_rep_t r = cstr_rep(self); - if (r.size + n > r.cap) { - const size_t off = (size_t)(str - r.data); - r.data = cstr_reserve(self, (r.size*3 >> 1) + n); - if (off <= r.size) str = r.data + off; /* handle self append */ +STC_DEF cstr* +cstr_append_n(cstr* self, const char* str, const size_t n) { + if (n == 0) return self; + const size_t oldlen = _cstr_p(self)->size, newlen = oldlen + n; + if (newlen > _cstr_p(self)->cap) { + const size_t off = (size_t) (str - self->str); /* handle self append */ + cstr_reserve(self, (oldlen*3 >> 1) + n); + if (off <= oldlen) str = self->str + off; } - memcpy(r.data + r.size, str, n); - _cstr_set_size(self, r.size + n); + memcpy(&self->str[oldlen], str, n); + self->str[_cstr_p(self)->size = newlen] = '\0'; return self; } -STC_DEF bool cstr_getdelim(cstr *self, const int delim, FILE *fp) { - int c = fgetc(fp); - if (c == EOF) - return false; - size_t pos = 0; - cstr_rep_t r = cstr_rep(self); - for (;;) { - if (c == delim || c == EOF) { - _cstr_set_size(self, pos); - return true; - } - if (pos == r.cap) { - _cstr_set_size(self, pos); - r.data = cstr_reserve(self, (r.cap = (r.cap*3 >> 1) + 16)); - } - r.data[pos++] = (char) c; - c = fgetc(fp); +STC_INLINE void _cstr_internal_move(cstr* self, const size_t pos1, const size_t pos2) { + if (pos1 == pos2) + return; + const size_t len = _cstr_p(self)->size, newlen = len + pos2 - pos1; + if (newlen > _cstr_p(self)->cap) + cstr_reserve(self, (len*3 >> 1) + pos2 - pos1); + memmove(&self->str[pos2], &self->str[pos1], len - pos1); + self->str[_cstr_p(self)->size = newlen] = '\0'; +} + +STC_DEF void +cstr_replace_n(cstr* self, const size_t pos, size_t len, const char* str, const size_t n) { + const size_t sz = cstr_size(*self); + if (len > sz - pos) len = sz - pos; + c_autobuf (xstr, char, n) { + memcpy(xstr, str, n); + _cstr_internal_move(self, pos + len, pos + n); + memcpy(&self->str[pos], xstr, n); } } @@ -398,62 +319,55 @@ cstr_from_replace_all(const char* str, const size_t str_len, STC_DEF void cstr_replace_all(cstr* self, const char* find, const char* repl) { - cstr_rep_t r = cstr_rep(self); - cstr_take(self, cstr_from_replace_all(r.data, r.size, find, strlen(find), - repl, strlen(repl))); + cstr_take(self, cstr_from_replace_all(self->str, _cstr_p(self)->size, + find, strlen(find), repl, strlen(repl))); } -STC_DEF void cstr_erase_n(cstr* self, const size_t pos, size_t n) { - cstr_rep_t r = cstr_rep(self); - if (n > r.size - pos) n = r.size - pos; - memmove(&r.data[pos], &r.data[pos + n], r.size - (pos + n)); - _cstr_set_size(self, r.size - n); +STC_DEF void +cstr_erase_n(cstr* self, const size_t pos, size_t n) { + const size_t len = _cstr_p(self)->size; + if (n > len - pos) n = len - pos; + if (len) { + memmove(&self->str[pos], &self->str[pos + n], len - (pos + n)); + self->str[_cstr_p(self)->size -= n] = '\0'; + } } -#if defined(__clang__) -# pragma clang diagnostic push -# pragma clang diagnostic ignored "-Wdeprecated-declarations" -#elif defined(_MSC_VER) -# pragma warning(push) -# pragma warning(disable: 4996) -#endif - -STC_DEF int cstr_vfmt(cstr* self, const char* fmt, va_list args) { - va_list args2; - va_copy(args2, args); - const int n = vsnprintf(NULL, (size_t)0, fmt, args); - cstr_reserve(self, n); - vsprintf(cstr_data(self), fmt, args2); - va_end(args2); - _cstr_set_size(self, n); - return n; +STC_DEF bool +cstr_getdelim(cstr *self, const int delim, FILE *fp) { + size_t pos = 0, cap = _cstr_p(self)->cap; + char* d = self->str; + int c = fgetc(fp); + if (c == EOF) + return false; + for (;;) { + if (c == delim || c == EOF) { + if (cap) d[_cstr_p(self)->size = pos] = '\0'; + return true; + } + if (pos == cap) { + d = cstr_reserve(self, (cap*3 >> 1) + 16); + cap = cstr_capacity(*self); + } + d[pos++] = (char) c; + c = fgetc(fp); + } } -#if defined(__clang__) -# pragma clang diagnostic pop -#elif defined(_MSC_VER) -# pragma warning(pop) -#endif -STC_DEF cstr cstr_from_fmt(const char* fmt, ...) { - cstr s = cstr_null; - va_list args; va_start(args, fmt); - cstr_vfmt(&s, fmt, args); - va_end(args); - return s; +STC_DEF size_t +cstr_find(cstr s, const char* needle) { + char* res = strstr(s.str, needle); + return res ? res - s.str : cstr_npos; } -STC_DEF int cstr_printf(cstr* self, const char* fmt, ...) { - cstr s = cstr_null; - va_list args; va_start(args, fmt); - const int n = cstr_vfmt(&s, fmt, args); - va_end(args); - cstr_drop(self); *self = s; - return n; +STC_DEF size_t +cstr_find_n(cstr s, const char* needle, const size_t pos, const size_t nmax) { + if (pos > _cstr_p(&s)->size) return cstr_npos; + const size_t nlen = strlen(needle); + char* res = c_strnstrn(s.str + pos, needle, _cstr_p(&s)->size - pos, nmax < nlen ? nmax : nlen); + return res ? res - s.str : cstr_npos; } -#endif // _i_implement -#if defined __GNUC__ && !defined __clang__ -# pragma GCC diagnostic pop #endif -#endif // CSTR_H_INCLUDED +#endif #undef i_opt diff --git a/include/stc/cstr.h b/include/stc/cstr.h index 6a46791c..d5b7e5bd 100644 --- a/include/stc/cstr.h +++ b/include/stc/cstr.h @@ -21,7 +21,10 @@ * SOFTWARE. */ -#ifdef STC_USE_SSO +/* A string type with short string optimization in C99 with optimal short string + * utilization (23 characters with 24 bytes string representation). + */ +#ifdef STC_OLD_CSTR #include "alt/cstr.h" #else #ifndef CSTR_H_INCLUDED @@ -30,118 +33,95 @@ #include "ccommon.h" #include "forward.h" #include /* malloc */ -#include #include #include /* vsnprintf */ #include -#define cstr_npos (SIZE_MAX >> 1) -typedef struct { size_t size, cap; char chr[1]; } cstr_priv; -#define _cstr_p(self) c_container_of((self)->str, cstr_priv, chr) -#ifdef _i_static - static cstr_priv _cstr_nullrep = {0, 0, {0}}; - static const cstr cstr_null = {_cstr_nullrep.chr}; +/**************************** PRIVATE API **********************************/ + +#if defined __GNUC__ && !defined __clang__ +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Warray-bounds" +# pragma GCC diagnostic ignored "-Wstringop-overflow=" +#endif + +enum { cstr_s_cap = sizeof(cstr_rep_t) - 1 }; +#define cstr_s_size(s) ((size_t)(cstr_s_cap - (s)->sml.last)) +#define cstr_s_set_size(s, len) ((s)->sml.last = cstr_s_cap - (len), (s)->sml.data[len] = 0) +#define cstr_s_data(s) (s)->sml.data +#define cstr_s_end(s) ((s)->sml.data + cstr_s_size(s)) + +#if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ + #define byte_rotl_(x, b) ((x) << (b)*8 | (x) >> (sizeof(x) - (b))*8) + #define cstr_l_cap(s) (~byte_rotl_((s)->lon.ncap, sizeof((s)->lon.ncap) - 1)) + #define cstr_l_set_cap(s, cap) ((s)->lon.ncap = ~byte_rotl_(cap, 1)) #else - extern const cstr cstr_null; + #define cstr_l_cap(s) (~(s)->lon.ncap) + #define cstr_l_set_cap(s, cap) ((s)->lon.ncap = ~(cap)) #endif -/* optimal memory: based on malloc_usable_size() sequence: 24, 40, 56, ... */ -#define _cstr_opt_mem(cap) ((((offsetof(cstr_priv, chr) + (cap) + 8)>>4)<<4) + 8) -/* optimal string capacity: 7, 23, 39, ... */ -#define _cstr_opt_cap(cap) (_cstr_opt_mem(cap) - offsetof(cstr_priv, chr) - 1) - -STC_API cstr cstr_from_n(const char* str, size_t n); -STC_API cstr cstr_from_fmt(const char* fmt, ...); -STC_API cstr cstr_from_replace_all(const char* str, size_t str_len, - const char* find, size_t find_len, - const char* repl, size_t repl_len); -STC_API char* cstr_reserve(cstr* self, size_t cap); -STC_API void cstr_resize(cstr* self, size_t len, char fill); -STC_API cstr* cstr_assign_n(cstr* self, const char* str, size_t n); -STC_API int cstr_printf(cstr* self, const char* fmt, ...); -STC_API cstr* cstr_append_n(cstr* self, const char* str, size_t n); -STC_API void cstr_replace_n(cstr* self, size_t pos, size_t len, const char* str, size_t n); -STC_API void cstr_replace_all(cstr* self, const char* find, const char* replace); -STC_API void cstr_erase_n(cstr* self, size_t pos, size_t n); -STC_API size_t cstr_find(cstr s, const char* needle); -STC_API size_t cstr_find_n(cstr s, const char* needle, size_t pos, size_t nmax); -STC_API bool cstr_getdelim(cstr *self, int delim, FILE *stream); -STC_API void cstr_replace_all(cstr* self, const char* find, const char* repl); - -STC_INLINE cstr cstr_init() { return cstr_null; } -#define cstr_toraw(self) (self)->str -#define cstr_new(literal) \ - cstr_from_n(literal, c_strlen_lit(literal)) -STC_INLINE cstr cstr_from(const char* str) - { return cstr_from_n(str, strlen(str)); } -STC_INLINE const char* cstr_str(const cstr* self) { return self->str; } -STC_INLINE char* cstr_data(cstr* self) { return self->str; } -STC_INLINE size_t cstr_size(cstr s) { return _cstr_p(&s)->size; } -STC_INLINE size_t cstr_length(cstr s) { return _cstr_p(&s)->size; } -STC_INLINE size_t cstr_capacity(cstr s) { return _cstr_p(&s)->cap; } -STC_INLINE bool cstr_empty(cstr s) { return _cstr_p(&s)->size == 0; } -STC_INLINE void cstr_drop(cstr* self) - { if (_cstr_p(self)->cap) c_free(_cstr_p(self)); } -STC_INLINE cstr cstr_clone(cstr s) - { return cstr_from_n(s.str, _cstr_p(&s)->size); } -STC_INLINE void cstr_clear(cstr* self) - { self->str[_cstr_p(self)->size = 0] = '\0'; } -STC_INLINE cstr* cstr_assign(cstr* self, const char* str) - { return cstr_assign_n(self, str, strlen(str)); } -STC_INLINE cstr* cstr_copy(cstr* self, cstr s) - { return cstr_assign_n(self, s.str, _cstr_p(&s)->size); } -STC_INLINE cstr* cstr_append(cstr* self, const char* str) - { return cstr_append_n(self, str, strlen(str)); } -STC_INLINE cstr* cstr_append_s(cstr* self, cstr s) - { return cstr_append_n(self, s.str, _cstr_p(&s)->size); } -STC_INLINE void cstr_push_back(cstr* self, char value) - { cstr_append_n(self, &value, 1); } -STC_INLINE void cstr_pop_back(cstr* self) - { self->str[ --_cstr_p(self)->size ] = '\0'; } -STC_INLINE void cstr_insert_n(cstr* self, const size_t pos, const char* str, const size_t n) - { cstr_replace_n(self, pos, 0, str, n); } -STC_INLINE void cstr_insert(cstr* self, const size_t pos, const char* str) - { cstr_replace_n(self, pos, 0, str, strlen(str)); } -STC_INLINE void cstr_insert_s(cstr* self, const size_t pos, cstr s) - { cstr_replace_n(self, pos, 0, s.str, _cstr_p(&s)->size); } -STC_INLINE void cstr_replace(cstr* self, const size_t pos, const size_t len, const char* str) - { cstr_replace_n(self, pos, len, str, strlen(str)); } -STC_INLINE void cstr_replace_s(cstr* self, const size_t pos, const size_t len, cstr s) - { cstr_replace_n(self, pos, len, s.str, _cstr_p(&s)->size); } -STC_INLINE void cstr_erase(cstr* self, const size_t pos) - { cstr_erase_n(self, pos, 1); } -STC_INLINE char* cstr_front(cstr* self) { return self->str; } -STC_INLINE char* cstr_back(cstr* self) - { return self->str + _cstr_p(self)->size - 1; } -STC_INLINE bool cstr_equals(cstr s, const char* str) - { return strcmp(s.str, str) == 0; } -STC_INLINE bool cstr_equals_s(cstr s1, cstr s2) - { return strcmp(s1.str, s2.str) == 0; } -STC_INLINE bool cstr_contains(cstr s, const char* needle) - { return strstr(s.str, needle) != NULL; } -STC_INLINE bool cstr_getline(cstr *self, FILE *stream) - { return cstr_getdelim(self, '\n', stream); } - -STC_INLINE cstr_rep_t cstr_rep(cstr* s) { - cstr_priv* p = _cstr_p(s); - return c_make(cstr_rep_t){s->str, p->size, p->cap}; +#define cstr_l_size(s) ((s)->lon.size) +#define cstr_l_set_size(s, len) ((s)->lon.data[(s)->lon.size = (len)] = 0) +#define cstr_l_data(s) (s)->lon.data +#define cstr_l_end(s) ((s)->lon.data + cstr_l_size(s)) +#define cstr_l_drop(s) c_free((s)->lon.data) + +#define cstr_is_long(s) ((s)->sml.last > 127) +STC_API char* _cstr_init(cstr* self, size_t len, size_t cap); +STC_API char* _cstr_internal_move(cstr* self, size_t pos1, size_t pos2); + +/**************************** PUBLIC API **********************************/ + +#define cstr_new(literal) cstr_from_n(literal, c_strlen_lit(literal)) +#define cstr_npos (SIZE_MAX >> 1) +#define cstr_null (c_make(cstr){.sml = {.last = cstr_s_cap}}) +#define cstr_toraw(self) cstr_str(self) + +STC_API char* cstr_reserve(cstr* self, size_t cap); +STC_API void cstr_shrink_to_fit(cstr* self); +STC_API void cstr_resize(cstr* self, size_t size, char value); +STC_API size_t cstr_find_n(cstr s, const char* needle, size_t pos, size_t nmax); +STC_API cstr* cstr_assign_n(cstr* self, const char* str, size_t n); +STC_API cstr* cstr_append_n(cstr* self, const char* str, size_t n); +STC_API bool cstr_getdelim(cstr *self, int delim, FILE *fp); +STC_API void cstr_erase_n(cstr* self, size_t pos, size_t n); +STC_API cstr cstr_from_fmt(const char* fmt, ...); +STC_API int cstr_printf(cstr* self, const char* fmt, ...); +STC_API void cstr_replace_all(cstr* self, const char* find, const char* repl); + +STC_INLINE cstr_rep_t cstr_rep(cstr* s) { + return cstr_is_long(s) + ? c_make(cstr_rep_t){s->lon.data, cstr_l_size(s), cstr_l_cap(s)} + : c_make(cstr_rep_t){s->sml.data, cstr_s_size(s), cstr_s_cap}; } -STC_INLINE cstr cstr_with_capacity(const size_t cap) { - cstr s = cstr_null; - cstr_reserve(&s, cap); +STC_INLINE cstr cstr_init(void) + { return cstr_null; } + +STC_INLINE cstr cstr_from_n(const char* str, const size_t n) { + cstr s; + memcpy(_cstr_init(&s, n, n), str, n); return s; } -STC_INLINE cstr cstr_with_size(const size_t len, const char fill) { - cstr s = cstr_null; - cstr_resize(&s, len, fill); +STC_INLINE cstr cstr_from(const char* str) + { return cstr_from_n(str, strlen(str)); } + +STC_INLINE cstr cstr_with_size(const size_t size, const char value) { + cstr s; + memset(_cstr_init(&s, size, size), value, size); + return s; +} + +STC_INLINE cstr cstr_with_capacity(const size_t cap) { + cstr s; + _cstr_init(&s, 0, cap); return s; } -STC_INLINE cstr* cstr_take(cstr* self, cstr s) { - if (self->str != s.str && _cstr_p(self)->cap) - c_free(_cstr_p(self)); - self->str = s.str; +STC_INLINE cstr* cstr_take(cstr* self, const cstr s) { + if (cstr_is_long(self) && self->lon.data != s.lon.data) + cstr_l_drop(self); + *self = s; return self; } @@ -151,155 +131,253 @@ STC_INLINE cstr cstr_move(cstr* self) { return tmp; } +STC_INLINE cstr cstr_clone(cstr s) { + cstr_rep_t r = cstr_rep(&s); + return cstr_from_n(r.data, r.size); +} + +STC_INLINE void cstr_drop(cstr* self) { + if (cstr_is_long(self)) + cstr_l_drop(self); +} + +STC_INLINE void cstr_clear(cstr* self) { + cstr_drop(self); + cstr_s_set_size(self, 0); +} + +#define SSO_CALL(s, call) (cstr_is_long(s) ? cstr_l_##call : cstr_s_##call) + +STC_INLINE void _cstr_set_size(cstr* self, size_t len) + { SSO_CALL(self, set_size(self, len)); } + +STC_INLINE char* cstr_data(cstr* self) + { return SSO_CALL(self, data(self)); } + +STC_INLINE const char* cstr_str(const cstr* self) + { return SSO_CALL(self, data(self)); } + +STC_INLINE bool cstr_empty(cstr s) + { return s.sml.last == cstr_s_cap; } + +STC_INLINE size_t cstr_size(cstr s) + { return SSO_CALL(&s, size(&s)); } + +STC_INLINE size_t cstr_length(cstr s) + { return SSO_CALL(&s, size(&s)); } + +STC_INLINE size_t cstr_capacity(cstr s) + { return cstr_is_long(&s) ? cstr_l_cap(&s) : cstr_s_cap; } + +STC_INLINE bool cstr_equals(cstr s1, const char* str) + { return strcmp(cstr_str(&s1), str) == 0; } + +STC_INLINE bool cstr_equals_s(cstr s1, cstr s2) + { return strcmp(cstr_str(&s1), cstr_str(&s2)) == 0; } + +STC_INLINE bool cstr_eq(const cstr* s1, const cstr* s2) + { return strcmp(cstr_str(s1), cstr_str(s2)) == 0; } + +STC_INLINE int cstr_cmp(const cstr* s1, const cstr* s2) + { return strcmp(cstr_str(s1), cstr_str(s2)); } + +STC_INLINE size_t cstr_find(cstr s, const char* needle) { + const char *str = cstr_str(&s), *res = strstr(str, needle); + return res ? res - str : cstr_npos; +} + +STC_INLINE bool cstr_find_s(cstr s, cstr needle) + { return cstr_find(s, cstr_str(&needle)); } + +STC_INLINE bool cstr_contains(cstr s, const char* needle) + { return strstr(cstr_str(&s), needle) != NULL; } + +STC_INLINE bool cstr_contains_s(cstr s, cstr needle) + { return strstr(cstr_str(&s), cstr_str(&needle)) != NULL; } + STC_INLINE bool cstr_starts_with(cstr s, const char* sub) { - while (*sub && *s.str == *sub) ++s.str, ++sub; + const char* str = cstr_str(&s); + while (*sub && *str == *sub) ++str, ++sub; return *sub == 0; } +STC_INLINE bool cstr_starts_with_s(cstr s, cstr sub) + { return cstr_starts_with(s, cstr_str(&sub)); } + STC_INLINE bool cstr_ends_with(cstr s, const char* sub) { - const size_t n = strlen(sub), sz = _cstr_p(&s)->size; - return n <= sz && !memcmp(s.str + sz - n, sub, n); + cstr_rep_t r = cstr_rep(&s); size_t n = strlen(sub); + return n <= r.size && memcmp(r.data + r.size - n, sub, n) == 0; +} + +STC_INLINE bool cstr_ends_with_s(cstr s, cstr sub) + { return cstr_ends_with(s, cstr_str(&sub)); } + +STC_INLINE void cstr_assign(cstr* self, const char* str) + { cstr_assign_n(self, str, strlen(str)); } + +STC_INLINE void cstr_copy(cstr* self, cstr s) { + cstr_rep_t r = cstr_rep(&s); + cstr_assign_n(self, r.data, r.size); +} + +STC_INLINE void cstr_append(cstr* self, const char* str) + { cstr_append_n(self, str, strlen(str)); } + +STC_INLINE void cstr_append_s(cstr* self, cstr s) { + cstr_rep_t r = cstr_rep(&s); + cstr_append_n(self, r.data, r.size); +} + +STC_INLINE void cstr_replace_n(cstr* self, size_t pos, size_t len, const char* str, size_t n) { + char* d = _cstr_internal_move(self, pos + len, pos + n); + memcpy(d + pos, str, n); +} + +STC_INLINE void cstr_replace(cstr* self, size_t pos, size_t len, const char* str) + { cstr_replace_n(self, pos, len, str, strlen(str)); } + +STC_INLINE void cstr_replace_s(cstr* self, size_t pos, size_t len, cstr s) { + cstr_rep_t r = cstr_rep(&s); + cstr_replace_n(self, pos, len, r.data, r.size); } -STC_INLINE int c_strncasecmp(const char* s1, const char* s2, size_t nmax) { - int ret = 0; - while (nmax-- && (ret = tolower(*s1++) - tolower(*s2)) == 0 && *s2++) - ; - return ret; +STC_INLINE void cstr_insert_n(cstr* self, size_t pos, const char* str, size_t n) + { cstr_replace_n(self, pos, 0, str, n); } + +STC_INLINE void cstr_insert(cstr* self, size_t pos, const char* str) + { cstr_replace_n(self, pos, 0, str, strlen(str)); } + +STC_INLINE void cstr_insert_s(cstr* self, size_t pos, cstr s) { + cstr_rep_t r = cstr_rep(&s); + cstr_replace_n(self, pos, 0, r.data, r.size); } +STC_INLINE bool cstr_getline(cstr *self, FILE *fp) + { return cstr_getdelim(self, '\n', fp); } + /* container adaptor functions: */ -#define cstr_cmp(xp, yp) strcmp((xp)->str, (yp)->str) +#define cstr_cmp(xp, yp) strcmp(cstr_str(xp), cstr_str(yp)) #define cstr_eq(xp, yp) (!cstr_cmp(xp, yp)) -#define cstr_hash(xp, dummy) c_strhash((xp)->str) +#define cstr_hash(xp, dummy) c_strhash(cstr_str(xp)) /* -------------------------- IMPLEMENTATION ------------------------- */ #if defined(_i_implement) -#ifndef _i_static -static cstr_priv _cstr_nullrep = {0, 0, {0}}; -const cstr cstr_null = {_cstr_nullrep.chr}; -#endif - -STC_DEF char* -cstr_reserve(cstr* self, const size_t cap) { - cstr_priv* p = _cstr_p(self); - const size_t oldcap = p->cap; - if (cap > oldcap) { - p = (cstr_priv*) c_realloc(((oldcap != 0) & (p != &_cstr_nullrep)) ? p : NULL, _cstr_opt_mem(cap)); - self->str = p->chr; - if (oldcap == 0) self->str[p->size = 0] = '\0'; - p->cap = _cstr_opt_cap(cap); +STC_DEF char* _cstr_internal_move(cstr* self, const size_t pos1, const size_t pos2) { + cstr_rep_t r = cstr_rep(self); + if (pos1 != pos2) { + const size_t newlen = r.size + pos2 - pos1; + if (newlen > r.cap) + r.data = cstr_reserve(self, (r.size*3 >> 1) + pos2 - pos1); + memmove(&r.data[pos2], &r.data[pos1], r.size - pos1); + _cstr_set_size(self, newlen); } - return self->str; + return r.data; } -STC_DEF void -cstr_resize(cstr* self, const size_t len, const char fill) { - const size_t n = _cstr_p(self)->size; - cstr_reserve(self, len); - if (len > n) memset(self->str + n, fill, len - n); - if (len | n) self->str[_cstr_p(self)->size = len] = '\0'; +STC_DEF char* _cstr_init(cstr* self, const size_t len, const size_t cap) { + if (cap > cstr_s_cap) { + self->lon.data = (char *)c_malloc(cap + 1); + cstr_l_set_size(self, len); + cstr_l_set_cap(self, cap); + return self->lon.data; + } + cstr_s_set_size(self, len); + return self->sml.data; } -STC_DEF cstr -cstr_from_n(const char* str, const size_t n) { - if (n == 0) return cstr_null; - cstr_priv* prv = (cstr_priv*) c_malloc(_cstr_opt_mem(n)); - cstr s = {(char *) memcpy(prv->chr, str, n)}; - s.str[prv->size = n] = '\0'; - prv->cap = _cstr_opt_cap(n); - return s; +STC_DEF void cstr_shrink_to_fit(cstr* self) { + cstr_rep_t r = cstr_rep(self); + if (r.size == r.cap) + return; + if (r.size > cstr_s_cap) { + self->lon.data = (char *)c_realloc(self->lon.data, r.size + 1); + cstr_l_set_cap(self, r.size); + } else if (r.cap > cstr_s_cap) { + memcpy(self->sml.data, r.data, r.size + 1); + cstr_s_set_size(self, r.size); + c_free(r.data); + } } -#if defined(__clang__) -# pragma clang diagnostic push -# pragma clang diagnostic ignored "-Wdeprecated-declarations" -#elif defined(_MSC_VER) -# pragma warning(push) -# pragma warning(disable: 4996) -#endif - -STC_DEF int -cstr_vfmt(cstr* self, const char* fmt, va_list args) { - va_list args2; - va_copy(args2, args); - int len = vsnprintf(NULL, (size_t)0, fmt, args); - cstr_reserve(self, len); - vsprintf(self->str, fmt, args2); - va_end(args2); - return _cstr_p(self)->size = len; +STC_DEF char* cstr_reserve(cstr* self, const size_t cap) { + if (cstr_is_long(self)) { + if (cap > cstr_l_cap(self)) { + self->lon.data = (char *)c_realloc(self->lon.data, cap + 1); + cstr_l_set_cap(self, cap); + } + return self->lon.data; + } + /* from short to long: */ + if (cap > cstr_s_cap) { + char* data = (char *)c_malloc(cap + 1); + const size_t len = cstr_s_size(self); + memcpy(data, self->sml.data, len); + self->lon.data = data; + cstr_l_set_size(self, len); + cstr_l_set_cap(self, cap); + return data; + } + return self->sml.data; } -#if defined(__clang__) -# pragma clang diagnostic pop -#elif defined(_MSC_VER) -# pragma warning(pop) -#endif - -STC_DEF cstr -cstr_from_fmt(const char* fmt, ...) { - cstr ret = cstr_null; - va_list args; va_start(args, fmt); - cstr_vfmt(&ret, fmt, args); - va_end(args); - return ret; +STC_DEF void cstr_resize(cstr* self, const size_t size, const char value) { + cstr_rep_t r = cstr_rep(self); + if (size > r.size) { + if (size > r.cap) r.data = cstr_reserve(self, size); + memset(r.data + r.size, value, size - r.size); + } + _cstr_set_size(self, size); } -STC_DEF int -cstr_printf(cstr* self, const char* fmt, ...) { - cstr ret = cstr_null; - va_list args; - va_start(args, fmt); - int n = cstr_vfmt(&ret, fmt, args); - va_end(args); - cstr_drop(self); - *self = ret; - return n; +STC_DEF size_t cstr_find_n(cstr s, const char* needle, const size_t pos, const size_t nmax) { + cstr_rep_t r = cstr_rep(&s); + const size_t nlen = (size_t) strlen(needle); + if (pos > r.size) return cstr_npos; + char* res = c_strnstrn(r.data + pos, needle, r.size, nmax < nlen ? nmax : nlen); + return res ? res - r.data : cstr_npos; } -STC_DEF cstr* -cstr_assign_n(cstr* self, const char* str, const size_t n) { - if (n || _cstr_p(self)->cap) { - cstr_reserve(self, n); - memmove(self->str, str, n); - self->str[_cstr_p(self)->size = n] = '\0'; +STC_DEF cstr* cstr_assign_n(cstr* self, const char* str, const size_t n) { + cstr_rep_t r = cstr_rep(self); + if (n > r.cap) { + r.data = (char *)c_realloc(cstr_is_long(self) ? r.data : NULL, n + 1); + cstr_l_set_cap(self, n); } + memmove(r.data, str, n); + _cstr_set_size(self, n); return self; } -STC_DEF cstr* -cstr_append_n(cstr* self, const char* str, const size_t n) { - if (n == 0) return self; - const size_t oldlen = _cstr_p(self)->size, newlen = oldlen + n; - if (newlen > _cstr_p(self)->cap) { - const size_t off = (size_t) (str - self->str); /* handle self append */ - cstr_reserve(self, (oldlen*3 >> 1) + n); - if (off <= oldlen) str = self->str + off; +STC_DEF cstr* cstr_append_n(cstr* self, const char* str, const size_t n) { + cstr_rep_t r = cstr_rep(self); + if (r.size + n > r.cap) { + const size_t off = (size_t)(str - r.data); + r.data = cstr_reserve(self, (r.size*3 >> 1) + n); + if (off <= r.size) str = r.data + off; /* handle self append */ } - memcpy(&self->str[oldlen], str, n); - self->str[_cstr_p(self)->size = newlen] = '\0'; + memcpy(r.data + r.size, str, n); + _cstr_set_size(self, r.size + n); return self; } -STC_INLINE void _cstr_internal_move(cstr* self, const size_t pos1, const size_t pos2) { - if (pos1 == pos2) - return; - const size_t len = _cstr_p(self)->size, newlen = len + pos2 - pos1; - if (newlen > _cstr_p(self)->cap) - cstr_reserve(self, (len*3 >> 1) + pos2 - pos1); - memmove(&self->str[pos2], &self->str[pos1], len - pos1); - self->str[_cstr_p(self)->size = newlen] = '\0'; -} - -STC_DEF void -cstr_replace_n(cstr* self, const size_t pos, size_t len, const char* str, const size_t n) { - const size_t sz = cstr_size(*self); - if (len > sz - pos) len = sz - pos; - c_autobuf (xstr, char, n) { - memcpy(xstr, str, n); - _cstr_internal_move(self, pos + len, pos + n); - memcpy(&self->str[pos], xstr, n); +STC_DEF bool cstr_getdelim(cstr *self, const int delim, FILE *fp) { + int c = fgetc(fp); + if (c == EOF) + return false; + size_t pos = 0; + cstr_rep_t r = cstr_rep(self); + for (;;) { + if (c == delim || c == EOF) { + _cstr_set_size(self, pos); + return true; + } + if (pos == r.cap) { + _cstr_set_size(self, pos); + r.data = cstr_reserve(self, (r.cap = (r.cap*3 >> 1) + 16)); + } + r.data[pos++] = (char) c; + c = fgetc(fp); } } @@ -322,56 +400,63 @@ cstr_from_replace_all(const char* str, const size_t str_len, STC_DEF void cstr_replace_all(cstr* self, const char* find, const char* repl) { - cstr_take(self, cstr_from_replace_all(self->str, _cstr_p(self)->size, - find, strlen(find), repl, strlen(repl))); + cstr_rep_t r = cstr_rep(self); + cstr_take(self, cstr_from_replace_all(r.data, r.size, find, strlen(find), + repl, strlen(repl))); } -STC_DEF void -cstr_erase_n(cstr* self, const size_t pos, size_t n) { - const size_t len = _cstr_p(self)->size; - if (n > len - pos) n = len - pos; - if (len) { - memmove(&self->str[pos], &self->str[pos + n], len - (pos + n)); - self->str[_cstr_p(self)->size -= n] = '\0'; - } +STC_DEF void cstr_erase_n(cstr* self, const size_t pos, size_t n) { + cstr_rep_t r = cstr_rep(self); + if (n > r.size - pos) n = r.size - pos; + memmove(&r.data[pos], &r.data[pos + n], r.size - (pos + n)); + _cstr_set_size(self, r.size - n); } -STC_DEF bool -cstr_getdelim(cstr *self, const int delim, FILE *fp) { - size_t pos = 0, cap = _cstr_p(self)->cap; - char* d = self->str; - int c = fgetc(fp); - if (c == EOF) - return false; - for (;;) { - if (c == delim || c == EOF) { - if (cap) d[_cstr_p(self)->size = pos] = '\0'; - return true; - } - if (pos == cap) { - d = cstr_reserve(self, (cap*3 >> 1) + 16); - cap = cstr_capacity(*self); - } - d[pos++] = (char) c; - c = fgetc(fp); - } +#if defined(__clang__) +# pragma clang diagnostic push +# pragma clang diagnostic ignored "-Wdeprecated-declarations" +#elif defined(_MSC_VER) +# pragma warning(push) +# pragma warning(disable: 4996) +#endif + +STC_DEF int cstr_vfmt(cstr* self, const char* fmt, va_list args) { + va_list args2; + va_copy(args2, args); + const int n = vsnprintf(NULL, (size_t)0, fmt, args); + cstr_reserve(self, n); + vsprintf(cstr_data(self), fmt, args2); + va_end(args2); + _cstr_set_size(self, n); + return n; } +#if defined(__clang__) +# pragma clang diagnostic pop +#elif defined(_MSC_VER) +# pragma warning(pop) +#endif -STC_DEF size_t -cstr_find(cstr s, const char* needle) { - char* res = strstr(s.str, needle); - return res ? res - s.str : cstr_npos; +STC_DEF cstr cstr_from_fmt(const char* fmt, ...) { + cstr s = cstr_null; + va_list args; va_start(args, fmt); + cstr_vfmt(&s, fmt, args); + va_end(args); + return s; } -STC_DEF size_t -cstr_find_n(cstr s, const char* needle, const size_t pos, const size_t nmax) { - if (pos > _cstr_p(&s)->size) return cstr_npos; - const size_t nlen = strlen(needle); - char* res = c_strnstrn(s.str + pos, needle, _cstr_p(&s)->size - pos, nmax < nlen ? nmax : nlen); - return res ? res - s.str : cstr_npos; +STC_DEF int cstr_printf(cstr* self, const char* fmt, ...) { + cstr s = cstr_null; + va_list args; va_start(args, fmt); + const int n = cstr_vfmt(&s, fmt, args); + va_end(args); + cstr_drop(self); *self = s; + return n; } +#endif // _i_implement +#if defined __GNUC__ && !defined __clang__ +# pragma GCC diagnostic pop #endif +#endif // CSTR_H_INCLUDED #endif -#endif -#undef i_opt \ No newline at end of file +#undef i_opt diff --git a/include/stc/forward.h b/include/stc/forward.h index 0cefd271..a62c8af4 100644 --- a/include/stc/forward.h +++ b/include/stc/forward.h @@ -44,7 +44,7 @@ typedef struct { char* data; size_t size, cap; } cstr_rep_t; typedef char cstr_value; -#ifdef STC_USE_SSO +#ifndef STC_OLD_CSTR typedef union { struct { char data[sizeof(cstr_rep_t) - 1]; unsigned char last; } sml; struct { char* data; size_t size, ncap; } lon; -- cgit v1.2.3 From 8f57f3d331de4cb4aa7d06862c2de3424eb1ba5b Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 22 Apr 2022 12:20:31 +0200 Subject: Readded push()/emplace() to all containers missing them. Made _hash function required for i_key_bind, _eq is derived from _cmp. --- docs/cdeq_api.md | 2 ++ docs/cmap_api.md | 18 ++++++++++-------- docs/cset_api.md | 1 + docs/csmap_api.md | 3 +-- docs/csset_api.md | 1 + examples/box.c | 4 ++++ examples/city.c | 7 +++++-- examples/person_arc.c | 4 ++++ examples/rawptr_elements.c | 4 ++-- examples/vikings.c | 7 ++++--- include/stc/cdeq.h | 15 +++++++++++---- include/stc/clist.h | 4 ++++ include/stc/cmap.h | 11 +++++------ include/stc/cqueue.h | 4 ---- include/stc/csmap.h | 12 +++++------- include/stc/template.h | 5 +---- 16 files changed, 60 insertions(+), 42 deletions(-) diff --git a/docs/cdeq_api.md b/docs/cdeq_api.md index 3cd4fece..aa528aa2 100644 --- a/docs/cdeq_api.md +++ b/docs/cdeq_api.md @@ -51,7 +51,9 @@ cdeq_X_value* cdeq_X_emplace_front(cdeq_X* self, i_valraw raw); void cdeq_X_pop_front(cdeq_X* self); cdeq_X_value* cdeq_X_push_back(cdeq_X* self, i_val value); +cdeq_X_value* cdeq_X_push(cdeq_X* self, i_val value); // alias for push_back() cdeq_X_value* cdeq_X_emplace_back(cdeq_X* self, i_valraw raw); +cdeq_X_value* cdeq_X_emplace(cdeq_X* self, i_valraw raw); // alias for emplace_back() void cdeq_X_pop_back(cdeq_X* self); cdeq_X_iter cdeq_X_insert(cdeq_X* self, size_t idx, i_val value); // move value diff --git a/docs/cmap_api.md b/docs/cmap_api.md index 69257779..645b0bd0 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -67,11 +67,10 @@ cmap_X_iter cmap_X_find(const cmap_X* self, i_keyraw rkey); cmap_X_result cmap_X_insert(cmap_X* self, i_key key, i_val mapped); // no change if key in map cmap_X_result cmap_X_insert_or_assign(cmap_X* self, i_key key, i_val mapped); // always update mapped -cmap_X_result cmap_X_put(cmap_X* self, i_key key, i_val mapped); // alias for insert_or_assign +cmap_X_result cmap_X_push(cmap_X* self, i_key key, i_val mapped); // alias for insert cmap_X_result cmap_X_emplace(cmap_X* self, i_keyraw rkey, i_valraw rmapped); // no change if rkey in map cmap_X_result cmap_X_emplace_or_assign(cmap_X* self, i_keyraw rkey, i_valraw rmapped); // always update rmapped -cmap_X_result cmap_X_put_raw(cmap_X* self, i_keyraw rkey, i_valraw rmapped); // alias for emplace_or_assign size_t cmap_X_erase(cmap_X* self, i_keyraw rkey); // return 0 or 1 cmap_X_iter cmap_X_erase_at(cmap_X* self, cmap_X_iter it); // return iter after it @@ -276,8 +275,9 @@ typedef struct { #define Viking_init() ((Viking){cstr_null, cstr_null}) -static inline bool Viking_eq(const Viking* a, const Viking* b) { - return cstr_equals_s(a->name, b->name) && cstr_equals_s(a->country, b->country); +static inline int Viking_cmp(const Viking* a, const Viking* b) { + int c = cstr_cmp(&a->name, &b->name); + return c ? c : cstr_cmp(&a->country, &b->country); } static inline uint32_t Viking_hash(const Viking* a, int ignored) { @@ -298,7 +298,7 @@ static inline void Viking_drop(Viking* vk) { #define i_key_bind Viking #define i_val int // i_key_bind auto-binds: -// #define i_eq Viking_eq +// #define i_cmp Viking_cmp // #define i_hash Viking_hash // #define i_keyfrom Viking_clone // #define i_keydrop Viking_drop @@ -361,8 +361,10 @@ static inline uint64_t RViking_hash(const RViking* raw, size_t ignore) { uint64_t hash = c_strhash(raw->name) ^ (c_strhash(raw->country) >> 15); return hash; } -static inline bool RViking_eq(const RViking* rx, const RViking* ry) { - return strcmp(rx->name, ry->name) == 0 && strcmp(rx->country, ry->country) == 0; + +static inline int RViking_cmp(const RViking* rx, const RViking* ry) { + int c = strcmp(rx->name, ry->name); + return c ? c : strcmp(rx->country, ry->country); } static inline Viking Viking_from(RViking raw) { @@ -379,7 +381,7 @@ static inline RViking Viking_toraw(const Viking* vk) { #define i_keyraw RViking // i_key_bind macro will make these functions auto-bind: // #define i_hash RViking_hash -// #define i_eq RViking_eq +// #define i_cmp RViking_cmp // #define i_keyfrom Viking_from // uses _from because i_keyraw is defined // #define i_keyto Viking_toraw // #define i_keydrop Viking_drop diff --git a/docs/cset_api.md b/docs/cset_api.md index e429c5ae..d9b412da 100644 --- a/docs/cset_api.md +++ b/docs/cset_api.md @@ -46,6 +46,7 @@ cset_X_value* cset_X_get_mut(cset_X* self, i_keyraw rkey); cset_X_iter cset_X_find(const cset_X* self, i_keyraw rkey); cset_X_result cset_X_insert(cset_X* self, i_key key); +cset_X_result cset_X_push(cset_X* self, i_key key); // alias for insert. cset_X_result cset_X_emplace(cset_X* self, i_keyraw rkey); size_t cset_X_erase(cset_X* self, i_keyraw rkey); // return 0 or 1 diff --git a/docs/csmap_api.md b/docs/csmap_api.md index 012a7d58..e73e6562 100644 --- a/docs/csmap_api.md +++ b/docs/csmap_api.md @@ -63,11 +63,10 @@ csmap_X_value* csmap_X_back(const csmap_X* self); csmap_X_result csmap_X_insert(csmap_X* self, i_key key, i_val mapped); // no change if key in map csmap_X_result csmap_X_insert_or_assign(csmap_X* self, i_key key, i_val mapped); // always update mapped -csmap_X_result csmap_X_put(csmap_X* self, i_key key, i_val mapped); // alias for insert_or_assign() +csmap_X_result csmap_X_push(csmap_X* self, i_key key, i_val mapped); // alias for insert() csmap_X_result csmap_X_emplace(csmap_X* self, i_keyraw rkey, i_valraw rmapped); // no change if rkey in map csmap_X_result csmap_X_emplace_or_assign(csmap_X* self, i_keyraw rkey, i_valraw rmapped); // always update rmapped -csmap_X_result csmap_X_put_raw(csmap_X* self, i_keyraw rkey, i_valraw rmapped); // alias for emplace_or_assign size_t csmap_X_erase(csmap_X* self, i_keyraw rkey); csmap_X_iter csmap_X_erase_at(csmap_X* self, csmap_X_iter it); // returns iter after it diff --git a/docs/csset_api.md b/docs/csset_api.md index 0ce8e811..57d23ee6 100644 --- a/docs/csset_api.md +++ b/docs/csset_api.md @@ -42,6 +42,7 @@ csset_X_value* csset_X_find_it(const csset_X* self, i_keyraw rkey, csset_X csset_X_iter csset_X_lower_bound(const csset_X* self, i_keyraw rkey); // find closest entry >= rkey csset_X_result csset_X_insert(csset_X* self, i_key key); +csset_X_result csset_X_push(csset_X* self, i_key key); // alias for insert() csset_X_result csset_X_emplace(csset_X* self, i_keyraw rkey); size_t csset_X_erase(csset_X* self, i_keyraw rkey); diff --git a/examples/box.c b/examples/box.c index d2d98218..4a43b149 100644 --- a/examples/box.c +++ b/examples/box.c @@ -7,6 +7,10 @@ Person Person_new(const char* name, const char* last) { return (Person){.name = cstr_from(name), .last = cstr_from(last)}; } +uint64_t Person_hash(const Person* a, size_t n) { + return cstr_hash(&a->name, 0) ^ cstr_hash(&a->last, 0); +} + int Person_cmp(const Person* a, const Person* b) { int c = cstr_cmp(&a->name, &b->name); return c ? c : cstr_cmp(&a->last, &b->last); diff --git a/examples/city.c b/examples/city.c index 16c9b6f1..0e1cbe96 100644 --- a/examples/city.c +++ b/examples/city.c @@ -1,7 +1,6 @@ #include -typedef struct -{ +typedef struct { cstr name; cstr country; float lat, lon; @@ -13,6 +12,10 @@ static inline int City_cmp(const City* a, const City* b) { return c ? c : cstr_cmp(&a->country, &b->country); } +static inline uint64_t City_hash(const City* a, size_t n) { + return cstr_hash(&a->name, 0) ^ cstr_hash(&a->country, 0); +} + static inline City City_clone(City c) { c.name = cstr_clone(c.name); c.country = cstr_clone(c.country); diff --git a/examples/person_arc.c b/examples/person_arc.c index 2fb51be5..9d245340 100644 --- a/examples/person_arc.c +++ b/examples/person_arc.c @@ -12,6 +12,10 @@ int Person_cmp(const Person* a, const Person* b) { return c ? c : cstr_cmp(&a->last, &b->last); } +uint64_t Person_hash(const Person* a, size_t n) { + return cstr_hash(&a->name, 0) ^ cstr_hash(&a->last, 0); +} + Person Person_clone(Person p) { p.name = cstr_clone(p.name); p.last = cstr_clone(p.last); diff --git a/examples/rawptr_elements.c b/examples/rawptr_elements.c index b0878941..20231528 100644 --- a/examples/rawptr_elements.c +++ b/examples/rawptr_elements.c @@ -8,8 +8,8 @@ struct { double x, y; } typedef Point; #define i_key Point* #define i_keydrop(x) c_free(*(x)) #define i_keyfrom(x) c_new(Point, *(x)) -#define i_hash(x, n) c_default_hash(*(x), sizeof *(x)) -#define i_eq(x, y) c_memcmp_eq(*(x), *(y)) +#define i_hash(x, n) c_default_hash(*(x), sizeof **(x)) +#define i_cmp(x, y) memcmp(*(x), *(y), sizeof **(x)) // not good! #define i_tag pnt #include diff --git a/examples/vikings.c b/examples/vikings.c index b093ff9b..ff2fe8ab 100644 --- a/examples/vikings.c +++ b/examples/vikings.c @@ -22,8 +22,9 @@ uint64_t RViking_hash(const RViking* raw, size_t ignore) { uint64_t hash = c_strhash(raw->name) ^ (c_strhash(raw->country) >> 15); return hash; } -static inline bool RViking_eq(const RViking* rx, const RViking* ry) { - return strcmp(rx->name, ry->name) == 0 && strcmp(rx->country, ry->country) == 0; +static inline int RViking_cmp(const RViking* rx, const RViking* ry) { + int c = strcmp(rx->name, ry->name); + return c ? c : strcmp(rx->country, ry->country); } static inline Viking Viking_from(RViking raw) { // note: parameter is by value @@ -40,7 +41,7 @@ static inline RViking Viking_toraw(const Viking* vk) { #define i_val int // i_key_bind auto-binds these functions: // i_hash => Viking_hash -// i_eq => Viking_eq +// i_cmp => Viking_cmp // i_keyfrom => Viking_from // not _clone because i_keyraw is defined // i_keyto => Viking_toraw // i_keydrop => Viking_drop diff --git a/include/stc/cdeq.h b/include/stc/cdeq.h index 7d6c0254..2c0df8c3 100644 --- a/include/stc/cdeq.h +++ b/include/stc/cdeq.h @@ -46,7 +46,7 @@ STC_API _cx_self _cx_memb(_with_capacity)(const size_t n); STC_API bool _cx_memb(_reserve)(_cx_self* self, const size_t n); STC_API void _cx_memb(_clear)(_cx_self* self); STC_API void _cx_memb(_drop)(_cx_self* self); -STC_API _cx_value* _cx_memb(_push_back)(_cx_self* self, i_key value); +STC_API _cx_value* _cx_memb(_push)(_cx_self* self, i_key value); STC_API void _cx_memb(_shrink_to_fit)(_cx_self *self); #if !defined _i_queue #if !defined _i_no_clone @@ -71,8 +71,8 @@ STC_API _cx_iter _cx_memb(_insert_range_p)(_cx_self* self, _cx_value* pos #if !defined _i_no_clone STC_API _cx_self _cx_memb(_clone)(_cx_self cx); #if !defined _i_no_emplace -STC_INLINE _cx_value* _cx_memb(_emplace_back)(_cx_self* self, i_keyraw raw) - { return _cx_memb(_push_back)(self, i_keyfrom(raw)); } +STC_INLINE _cx_value* _cx_memb(_emplace)(_cx_self* self, i_keyraw raw) + { return _cx_memb(_push)(self, i_keyfrom(raw)); } #endif STC_INLINE i_key _cx_memb(_value_clone)(i_key val) { return i_keyclone(val); } @@ -115,6 +115,9 @@ STC_INLINE _cx_value* _cx_memb(_at_mut)(_cx_self* self, const size_t idx) { assert(idx < cdeq_rep_(self)->size); return self->data + idx; } +STC_INLINE _cx_value* _cx_memb(_push_back)(_cx_self* self, i_key value) { + return _cx_memb(_push)(self, value); +} STC_INLINE _cx_iter _cx_memb(_insert)(_cx_self* self, const size_t idx, i_key value) { return _cx_memb(_insert_range_p)(self, self->data + idx, &value, &value + 1); @@ -151,6 +154,10 @@ STC_INLINE _cx_value* _cx_memb(_emplace_front)(_cx_self* self, i_keyraw raw) { return _cx_memb(_push_front)(self, i_keyfrom(raw)); } +STC_INLINE _cx_value* _cx_memb(_emplace_back)(_cx_self* self, i_keyraw raw) { + return _cx_memb(_push)(self, i_keyfrom(raw)); +} + STC_INLINE _cx_iter _cx_memb(_emplace_n)(_cx_self* self, const size_t idx, const _cx_raw arr[], const size_t n) { return _cx_memb(_emplace_range_p)(self, self->data + idx, arr, arr + n); @@ -287,7 +294,7 @@ _cx_memb(_reserve)(_cx_self* self, const size_t n) { } STC_DEF _cx_value* -_cx_memb(_push_back)(_cx_self* self, i_key value) { +_cx_memb(_push)(_cx_self* self, i_key value) { struct cdeq_rep* r = cdeq_rep_(self); if (_cdeq_nfront(self) + r->size == r->cap) { _cx_memb(_expand_right_half_)(self, r->size, 1); diff --git a/include/stc/clist.h b/include/stc/clist.h index 8247b04a..33aa6feb 100644 --- a/include/stc/clist.h +++ b/include/stc/clist.h @@ -122,6 +122,8 @@ STC_INLINE _cx_value* _cx_memb(_emplace_front)(_cx_self* self, i_keyraw raw) { return _cx_memb(_push_front)(self, i_keyfrom(raw)); } STC_INLINE _cx_iter _cx_memb(_emplace_at)(_cx_self* self, _cx_iter it, i_keyraw raw) { return _cx_memb(_insert_at)(self, it, i_keyfrom(raw)); } +STC_INLINE _cx_value* _cx_memb(_emplace)(_cx_self* self, i_keyraw raw) + { return _cx_memb(_push_back)(self, i_keyfrom(raw)); } #endif // !_i_no_emplace #endif // !_i_no_clone @@ -131,6 +133,8 @@ STC_INLINE bool _cx_memb(_empty)(_cx_self cx) { return cx.last == NULL; STC_INLINE size_t _cx_memb(_count)(_cx_self cx) { return _clist_count((const clist_VOID*) &cx); } STC_INLINE void _cx_memb(_clear)(_cx_self* self) { _cx_memb(_drop)(self); } +STC_INLINE _cx_value* _cx_memb(_push)(_cx_self* self, i_key value) + { return _cx_memb(_push_back)(self, value); } STC_INLINE void _cx_memb(_pop_front)(_cx_self* self) { _cx_memb(_erase_after_)(self, self->last); } STC_INLINE _cx_value* _cx_memb(_front)(const _cx_self* self) { return &self->last->next->value; } diff --git a/include/stc/cmap.h b/include/stc/cmap.h index c5172f3b..16041094 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -118,14 +118,8 @@ STC_INLINE bool _cx_memb(_contains)(const _cx_self* self, i_keyraw rkey) STC_API _cx_result _cx_memb(_insert_or_assign)(_cx_self* self, i_key _key, i_val _mapped); #if !defined _i_no_clone && !defined _i_no_emplace STC_API _cx_result _cx_memb(_emplace_or_assign)(_cx_self* self, i_keyraw rkey, i_valraw rmapped); - STC_INLINE _cx_result _cx_memb(_put_raw)(_cx_self* self, i_keyraw rkey, i_valraw rmapped) - { return _cx_memb(_emplace_or_assign)(self, rkey, rmapped); } // alias #endif - STC_INLINE _cx_result - _cx_memb(_put)(_cx_self* self, i_key _key, i_val _mapped) - { return _cx_memb(_insert_or_assign)(self, _key, _mapped); } - STC_INLINE const _cx_mapped* _cx_memb(_at)(const _cx_self* self, i_keyraw rkey) { chash_bucket_t b = _cx_memb(_bucket_)(self, &rkey); @@ -183,6 +177,11 @@ _cx_memb(_insert)(_cx_self* self, i_key _key _i_MAP_ONLY(, i_val _mapped)) { return _res; } +STC_INLINE _cx_result +_cx_memb(_push)(_cx_self* self, i_key _key _i_MAP_ONLY(, i_val _mapped)) { + return _cx_memb(_insert)(self, _key _i_MAP_ONLY(, _mapped)); +} + STC_INLINE _cx_iter _cx_memb(_find)(const _cx_self* self, i_keyraw rkey) { _cx_size idx; diff --git a/include/stc/cqueue.h b/include/stc/cqueue.h index b07582e0..920f8eac 100644 --- a/include/stc/cqueue.h +++ b/include/stc/cqueue.h @@ -57,13 +57,9 @@ int main() { #define _i_prefix cqueue_ #endif #define _i_queue -#define _push_back _push -#define _emplace_back _emplace #define _pop_front _pop #include "cdeq.h" -#undef _push_back -#undef _emplace_back #undef _pop_front #undef _i_queue diff --git a/include/stc/csmap.h b/include/stc/csmap.h index eba9a591..700aa4c2 100644 --- a/include/stc/csmap.h +++ b/include/stc/csmap.h @@ -159,15 +159,8 @@ _cx_memb(_value_drop)(_cx_value* val) { #ifndef _i_isset #if !defined _i_no_clone && !defined _i_no_emplace STC_API _cx_result _cx_memb(_emplace_or_assign)(_cx_self* self, i_keyraw rkey, i_valraw rmapped); - STC_INLINE _cx_result - _cx_memb(_put_raw)(_cx_self* self, i_keyraw rkey, i_valraw rmapped) - { return _cx_memb(_emplace_or_assign)(self, rkey, rmapped); } // alias #endif STC_API _cx_result _cx_memb(_insert_or_assign)(_cx_self* self, i_key key, i_val mapped); - - STC_INLINE _cx_result - _cx_memb(_put)(_cx_self* self, i_key _key, i_val _mapped) - { return _cx_memb(_insert_or_assign)(self, _key, _mapped); } STC_INLINE const _cx_mapped* _cx_memb(_at)(const _cx_self* self, i_keyraw rkey) @@ -177,6 +170,11 @@ _cx_memb(_value_drop)(_cx_value* val) { { _cx_iter it; return &_cx_memb(_find_it)(self, rkey, &it)->second; } #endif // !_i_isset +STC_INLINE _cx_result +_cx_memb(_push)(_cx_self* self, i_key _key _i_MAP_ONLY(, i_val _mapped)) { + return _cx_memb(_insert)(self, _key _i_MAP_ONLY(, _mapped)); +} + STC_INLINE _cx_iter _cx_memb(_find)(const _cx_self* self, i_keyraw rkey) { _cx_iter it; diff --git a/include/stc/template.h b/include/stc/template.h index f614cd58..d47b06ec 100644 --- a/include/stc/template.h +++ b/include/stc/template.h @@ -123,10 +123,7 @@ #ifndef i_cmp #define i_cmp c_paste(i_keyraw, _cmp) #endif - #if !defined i_eq && (defined _i_ishash || c_option(c_eq)) - #define i_eq c_paste(i_keyraw, _eq) - #endif - #if !defined i_hash && (defined _i_ishash || c_option(c_hash)) + #if !defined i_hash #define i_hash c_paste(i_keyraw, _hash) #endif #endif -- cgit v1.2.3 From dd5551dec268da39ad1c5c66de014e4621d24748 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 22 Apr 2022 12:44:57 +0200 Subject: Changed API for c*map_X_push() to take a entry pair (c*map_X_value) argument instead of key + val. --- docs/cmap_api.md | 2 +- docs/csmap_api.md | 2 +- include/stc/cmap.h | 6 ++++-- include/stc/csmap.h | 13 ++++++++----- 4 files changed, 14 insertions(+), 9 deletions(-) diff --git a/docs/cmap_api.md b/docs/cmap_api.md index 645b0bd0..03ee11a9 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -67,7 +67,7 @@ cmap_X_iter cmap_X_find(const cmap_X* self, i_keyraw rkey); cmap_X_result cmap_X_insert(cmap_X* self, i_key key, i_val mapped); // no change if key in map cmap_X_result cmap_X_insert_or_assign(cmap_X* self, i_key key, i_val mapped); // always update mapped -cmap_X_result cmap_X_push(cmap_X* self, i_key key, i_val mapped); // alias for insert +cmap_X_result cmap_X_push(cmap_X* self, cmap_X_value entry); // similar to insert cmap_X_result cmap_X_emplace(cmap_X* self, i_keyraw rkey, i_valraw rmapped); // no change if rkey in map cmap_X_result cmap_X_emplace_or_assign(cmap_X* self, i_keyraw rkey, i_valraw rmapped); // always update rmapped diff --git a/docs/csmap_api.md b/docs/csmap_api.md index e73e6562..ab9eb2ee 100644 --- a/docs/csmap_api.md +++ b/docs/csmap_api.md @@ -63,7 +63,7 @@ csmap_X_value* csmap_X_back(const csmap_X* self); csmap_X_result csmap_X_insert(csmap_X* self, i_key key, i_val mapped); // no change if key in map csmap_X_result csmap_X_insert_or_assign(csmap_X* self, i_key key, i_val mapped); // always update mapped -csmap_X_result csmap_X_push(csmap_X* self, i_key key, i_val mapped); // alias for insert() +csmap_X_result csmap_X_push(csmap_X* self, csmap_X_value entry); // similar to insert() csmap_X_result csmap_X_emplace(csmap_X* self, i_keyraw rkey, i_valraw rmapped); // no change if rkey in map csmap_X_result csmap_X_emplace_or_assign(csmap_X* self, i_keyraw rkey, i_valraw rmapped); // always update rmapped diff --git a/include/stc/cmap.h b/include/stc/cmap.h index 16041094..6cde2532 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -178,8 +178,10 @@ _cx_memb(_insert)(_cx_self* self, i_key _key _i_MAP_ONLY(, i_val _mapped)) { } STC_INLINE _cx_result -_cx_memb(_push)(_cx_self* self, i_key _key _i_MAP_ONLY(, i_val _mapped)) { - return _cx_memb(_insert)(self, _key _i_MAP_ONLY(, _mapped)); +_cx_memb(_push)(_cx_self* self, _cx_value _val) { + _cx_result _res = _cx_memb(_insert_entry_)(self, i_keyto(_i_keyref(&_val))); + if (_res.inserted) *_res.ref = _val; else _cx_memb(_value_drop)(&_val); + return _res; } STC_INLINE _cx_iter diff --git a/include/stc/csmap.h b/include/stc/csmap.h index 700aa4c2..25f66d79 100644 --- a/include/stc/csmap.h +++ b/include/stc/csmap.h @@ -104,6 +104,7 @@ STC_API _cx_result _cx_memb(_emplace)(_cx_self* self, i_keyraw rkey _i_MAP_ #endif // !_i_no_clone STC_API _cx_self _cx_memb(_init)(void); STC_API _cx_result _cx_memb(_insert)(_cx_self* self, i_key key _i_MAP_ONLY(, i_val mapped)); +STC_API _cx_result _cx_memb(_push)(_cx_self* self, _cx_value _val); STC_API void _cx_memb(_drop)(_cx_self* self); STC_API bool _cx_memb(_reserve)(_cx_self* self, size_t cap); STC_API _cx_value* _cx_memb(_find_it)(const _cx_self* self, i_keyraw rkey, _cx_iter* out); @@ -170,11 +171,6 @@ _cx_memb(_value_drop)(_cx_value* val) { { _cx_iter it; return &_cx_memb(_find_it)(self, rkey, &it)->second; } #endif // !_i_isset -STC_INLINE _cx_result -_cx_memb(_push)(_cx_self* self, i_key _key _i_MAP_ONLY(, i_val _mapped)) { - return _cx_memb(_insert)(self, _key _i_MAP_ONLY(, _mapped)); -} - STC_INLINE _cx_iter _cx_memb(_find)(const _cx_self* self, i_keyraw rkey) { _cx_iter it; @@ -273,6 +269,13 @@ _cx_memb(_insert)(_cx_self* self, i_key key _i_MAP_ONLY(, i_val mapped)) { return res; } +STC_DEF _cx_result +_cx_memb(_push)(_cx_self* self, _cx_value _val) { + _cx_result _res = _cx_memb(_insert_entry_)(self, i_keyto(_i_keyref(&_val))); + if (_res.inserted) *_res.ref = _val; else _cx_memb(_value_drop)(&_val); + return _res; +} + #ifndef _i_isset STC_DEF _cx_result _cx_memb(_insert_or_assign)(_cx_self* self, i_key key, i_val mapped) { -- cgit v1.2.3 From 2b74b8a880d48232892ca84ac29efacd66905cd4 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sat, 23 Apr 2022 14:00:47 +0200 Subject: Integrated (and removed) c_hash32 and c_hash64 into c_default_hash, which is improved. Added i_key_ssv and i_val_ssv (cstr with csview as raw-type). --- benchmarks/build_all.sh | 1 - benchmarks/misc/sso_bench.c | 2 +- benchmarks/misc/sso_bench2.cpp | 1 - benchmarks/picobench/picobench_cmap.cpp | 2 -- benchmarks/plotbench/cmap_benchmark.cpp | 1 - benchmarks/shootout_hashmaps.cpp | 1 - docs/clist_api.md | 1 + docs/cmap_api.md | 2 -- examples/make.sh | 2 +- examples/read.c | 2 +- examples/sso_map.c | 1 - examples/sso_substr.c | 1 - include/stc/carc.h | 6 ++---- include/stc/cbox.h | 6 ++---- include/stc/ccommon.h | 18 ++++++++++-------- include/stc/cmap.h | 3 --- include/stc/cstr.h | 7 ++++--- include/stc/csview.h | 15 ++++++++------- include/stc/template.h | 32 ++++++++++++++++++++++++++------ 19 files changed, 56 insertions(+), 48 deletions(-) diff --git a/benchmarks/build_all.sh b/benchmarks/build_all.sh index fda58f69..348a79dd 100644 --- a/benchmarks/build_all.sh +++ b/benchmarks/build_all.sh @@ -1,6 +1,5 @@ #!/bin/bash cc='g++ -std=c++17' -#cc='g++ -std=c++17 -DSTC_USE_SSO' #cc='clang' #cc='clang -c -DSTC_HEADER' #cc='cl -nologo' diff --git a/benchmarks/misc/sso_bench.c b/benchmarks/misc/sso_bench.c index 450884f3..f2714be1 100644 --- a/benchmarks/misc/sso_bench.c +++ b/benchmarks/misc/sso_bench.c @@ -1,5 +1,5 @@ // https://gobyexample.com/maps -#include +#include #define i_type Map #define i_key_str #define i_val int diff --git a/benchmarks/misc/sso_bench2.cpp b/benchmarks/misc/sso_bench2.cpp index 87b701b5..1355a727 100644 --- a/benchmarks/misc/sso_bench2.cpp +++ b/benchmarks/misc/sso_bench2.cpp @@ -2,7 +2,6 @@ #include #include #include -#define STC_USE_SSO 1 #define i_type svec #define i_val_str #include diff --git a/benchmarks/picobench/picobench_cmap.cpp b/benchmarks/picobench/picobench_cmap.cpp index 02daad51..d72ea12f 100644 --- a/benchmarks/picobench/picobench_cmap.cpp +++ b/benchmarks/picobench/picobench_cmap.cpp @@ -37,13 +37,11 @@ DEFMAP(map_s, ); #define i_key int32_t #define i_val int32_t -#define i_hash c_hash32 #define i_tag i #include #define i_key uint64_t #define i_val uint64_t -#define i_hash c_hash64 #define i_tag x #include diff --git a/benchmarks/plotbench/cmap_benchmark.cpp b/benchmarks/plotbench/cmap_benchmark.cpp index 0554ae9c..a22aee86 100644 --- a/benchmarks/plotbench/cmap_benchmark.cpp +++ b/benchmarks/plotbench/cmap_benchmark.cpp @@ -17,7 +17,6 @@ static float secs(Range s) { return (float)(s.t2 - s.t1) / CLOCKS_PER_SEC; } #define i_key uint64_t #define i_val uint64_t -#define i_hash c_hash64 #define i_tag x #include diff --git a/benchmarks/shootout_hashmaps.cpp b/benchmarks/shootout_hashmaps.cpp index 57bd3383..4ed961e7 100644 --- a/benchmarks/shootout_hashmaps.cpp +++ b/benchmarks/shootout_hashmaps.cpp @@ -26,7 +26,6 @@ KHASH_MAP_INIT_INT64(ii, int64_t) // cmap and khash template expansion #define i_key int64_t #define i_val int64_t -#define i_hash c_hash64 #define i_tag ii #include diff --git a/docs/clist_api.md b/docs/clist_api.md index cae3e66b..c785fbe5 100644 --- a/docs/clist_api.md +++ b/docs/clist_api.md @@ -57,6 +57,7 @@ void clist_X_pop_front(clist_X* self); void clist_X_push_back(clist_X* self, i_val value); // note: no pop_back() void clist_X_push(clist_X* self, i_val value); // alias for push_back() void clist_X_emplace_back(clist_X* self, i_valraw raw); +void clist_X_emplace(clist_X* self, i_valraw raw); // alias for emplace_back() clist_X_iter clist_X_insert_at(clist_X* self, clist_X_iter it, i_val value); // return iter to new elem clist_X_iter clist_X_emplace_at(clist_X* self, clist_X_iter it, i_valraw raw); diff --git a/docs/cmap_api.md b/docs/cmap_api.md index 03ee11a9..07f1c140 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -89,8 +89,6 @@ uint64_t c_strhash(const char *str); / // hash template parameter functions: uint64_t c_default_hash(const void *data, size_t len); // key is any integral type -uint64_t c_hash32(const void* data, size_t is4); // key is one 32-bit int -uint64_t c_hash64(const void* data, size_t is8); // key is one 64-bit int // equalto template parameter functions: bool c_default_eq(const i_keyraw* a, const i_keyraw* b); // *a == *b diff --git a/examples/make.sh b/examples/make.sh index ef0468c7..4687ed97 100644 --- a/examples/make.sh +++ b/examples/make.sh @@ -1,7 +1,7 @@ #!/bin/bash cc='gcc -s -O2 -Wall -std=c99 -pedantic' #cc='gcc -x c++ -s -O2 -Wall -std=c++20' -#cc='clang -s -O2 -Wall -std=c99 -pedantic -DSTC_USE_SSO' +#cc='clang -s -O2 -Wall -std=c99 -pedantic -DSTC_OLD_CSTR' #cc='clang' #cc='clang -c -DSTC_HEADER' #cc='cl -O2 -nologo -W2 -MD' diff --git a/examples/read.c b/examples/read.c index 127373b1..5f31e357 100644 --- a/examples/read.c +++ b/examples/read.c @@ -1,4 +1,4 @@ -#include +#include #define i_val_str #include #include diff --git a/examples/sso_map.c b/examples/sso_map.c index a70722f7..d6174da8 100644 --- a/examples/sso_map.c +++ b/examples/sso_map.c @@ -1,4 +1,3 @@ -#define STC_USE_SSO 1 #include #define i_key_str #define i_val_str diff --git a/examples/sso_substr.c b/examples/sso_substr.c index 60fb9997..fdb53d0b 100644 --- a/examples/sso_substr.c +++ b/examples/sso_substr.c @@ -1,4 +1,3 @@ -#define STC_USE_SSO 1 #include #include diff --git a/include/stc/carc.h b/include/stc/carc.h index 54ba3159..1cdca419 100644 --- a/include/stc/carc.h +++ b/include/stc/carc.h @@ -170,10 +170,8 @@ _cx_memb(_take)(_cx_self* self, _cx_self ptr) { STC_INLINE uint64_t _cx_memb(_value_hash)(const _cx_value* x, size_t n) { - #if c_option(c_no_cmp) && UINTPTR_MAX == UINT64_MAX - return c_hash64(&x, 8); - #elif c_option(c_no_cmp) - return c_hash32(&x, 4); + #if c_option(c_no_cmp) + return c_default_hash(&x, sizeof x); #else _cx_raw rx = i_keyto(x); return i_hash((&rx), (sizeof rx)); diff --git a/include/stc/cbox.h b/include/stc/cbox.h index 27536c21..fa6ef2a9 100644 --- a/include/stc/cbox.h +++ b/include/stc/cbox.h @@ -147,10 +147,8 @@ _cx_memb(_take)(_cx_self* self, _cx_self other) { STC_INLINE uint64_t _cx_memb(_value_hash)(const _cx_value* x, size_t n) { - #if c_option(c_no_cmp) && UINTPTR_MAX == UINT64_MAX - return c_hash64(&x, 8); - #elif c_option(c_no_cmp) - return c_hash32(&x, 4); + #if c_option(c_no_cmp) + return c_default_hash(&x, sizeof x); #else _cx_raw rx = i_keyto(x); return i_hash((&rx), (sizeof rx)); diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index d7351611..56dd501e 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -117,19 +117,21 @@ STC_INLINE uint64_t c_strhash(const char *s) { if (h) while ((c = *s++)) h = (h << 10) - h + c; return _c_ROTL(h, 26) ^ h; } + STC_INLINE uint64_t c_default_hash(const void* key, size_t len) { - if (!len) return 1; + uint64_t u8, h = 1; + uint32_t u4; const uint8_t *x = (const uint8_t*) key; - uint64_t h = *x++; + for (size_t n = len >> 3; n--; ) + memcpy(&u8, x, 8), x += 8, h += u8*0xc6a4a7935bd1e99d; + switch (len &= 7) { + case 0: return h; + case 4: memcpy(&u4, x, 4); return h + u4*0xc6a4a7935bd1e99d; + } + h += *x++; while (--len) h = (h << 10) - h + *x++; return _c_ROTL(h, 26) ^ h; } -STC_INLINE uint64_t c_hash32(const void* key, size_t n) { - return *(uint32_t *)key*0xc6a4a7935bd1e99d; -} -STC_INLINE uint64_t c_hash64(const void* key, size_t n) { - return *(uint64_t *)key*0xc6a4a7935bd1e99d; -} STC_INLINE char* c_strnstrn(const char *s, const char *needle, size_t slen, const size_t nlen) { if (!nlen) return (char *)s; diff --git a/include/stc/cmap.h b/include/stc/cmap.h index 6cde2532..978d624a 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -72,9 +72,6 @@ typedef struct { size_t idx; uint8_t hx; } chash_bucket_t; #endif #define _i_ishash #include "template.h" -#ifdef _i_no_hash - #error "i_hash must be defined if i_cmp, i_eq or i_keyfrom is defined for cmap/cset. For basic types c_default_hash may be used." -#endif #if !c_option(c_is_fwd) _cx_deftypes(_c_chash_types, _cx_self, i_key, i_val, i_size, _i_MAP_ONLY, _i_SET_ONLY); #endif diff --git a/include/stc/cstr.h b/include/stc/cstr.h index d5b7e5bd..9c6568f7 100644 --- a/include/stc/cstr.h +++ b/include/stc/cstr.h @@ -256,9 +256,10 @@ STC_INLINE bool cstr_getline(cstr *self, FILE *fp) { return cstr_getdelim(self, '\n', fp); } /* container adaptor functions: */ -#define cstr_cmp(xp, yp) strcmp(cstr_str(xp), cstr_str(yp)) -#define cstr_eq(xp, yp) (!cstr_cmp(xp, yp)) -#define cstr_hash(xp, dummy) c_strhash(cstr_str(xp)) +#define cstr_cmp(xp, yp) strcmp(cstr_str(xp), cstr_str(yp)) +#define cstr_eq(xp, yp) (!cstr_cmp(xp, yp)) +STC_INLINE uint64_t cstr_hash(const cstr *self, size_t dummylen) + { return c_default_hash(cstr_str(self), cstr_size(*self)); } /* -------------------------- IMPLEMENTATION ------------------------- */ #if defined(_i_implement) diff --git a/include/stc/csview.h b/include/stc/csview.h index c4b88f4d..59e853ca 100644 --- a/include/stc/csview.h +++ b/include/stc/csview.h @@ -127,13 +127,14 @@ STC_INLINE bool cstr_ends_with_sv(cstr s, csview sub) #endif /* ---- Container helper functions ---- */ -STC_INLINE int csview_cmp(const csview* x, const csview* y) { - const size_t m = x->size < y->size ? x->size : y->size; - const int c = memcmp(x->str, y->str, m); - return c ? c : x->size - y->size; - } -#define csview_hash(xp, dummy) c_default_hash((xp)->str, (xp)->size) -#define csview_eq(xp, yp) (!csview_cmp(xp, yp)) +STC_INLINE int csview_cmp(const csview* x, const csview* y) { + const size_t m = x->size < y->size ? x->size : y->size; + const int c = memcmp(x->str, y->str, m); + return c ? c : x->size - y->size; + } +#define csview_eq(xp, yp) (!csview_cmp(xp, yp)) +STC_INLINE uint64_t csview_hash(const csview *self, size_t sz) + { return c_default_hash(self->str, self->size); } /* -------------------------- IMPLEMENTATION ------------------------- */ #if defined(_i_implement) diff --git a/include/stc/template.h b/include/stc/template.h index d47b06ec..48881edf 100644 --- a/include/stc/template.h +++ b/include/stc/template.h @@ -50,11 +50,15 @@ #define i_size uint32_t #endif -#if defined i_key_str || defined i_val_str +#if defined i_key_str || defined i_val_str || defined i_key_ssv || defined i_val_ssv #include "cstr.h" + #if defined i_key_ssv || defined i_val_ssv + #include "csview.h" + #endif #endif -#if !(defined i_key || defined i_key_str || defined i_key_bind || defined i_key_arcbox) +#if !(defined i_key || defined i_key_str || defined i_key_ssv || \ + defined i_key_bind || defined i_key_arcbox) #define _i_key_from_val #if defined _i_ismap #error "i_key* must be defined for maps." @@ -63,6 +67,9 @@ #if defined i_val_str #define i_key_str i_val_str #endif + #if defined i_val_ssv + #define i_key_ssv i_val_ssv + #endif #if defined i_val_arcbox #define i_key_arcbox i_val_arcbox #endif @@ -89,12 +96,20 @@ #endif #endif -#ifdef i_key_str +#if defined i_key_str #define i_key_bind cstr #define i_keyraw crawstr #ifndef i_tag #define i_tag str #endif +#elif defined i_key_ssv + #define i_key_bind cstr + #define i_keyraw csview + #define i_keyfrom cstr_from_sv + #define i_keyto cstr_to_sv + #ifndef i_tag + #define i_tag ssv + #endif #elif defined i_key_arcbox #define i_key_bind i_key_arcbox #define i_keyraw c_paste(i_key_arcbox, _value) @@ -144,9 +159,6 @@ #if (!defined i_keyfrom && defined i_keydrop) || c_option(c_no_clone) #define _i_no_clone #endif -#if !defined i_hash && (defined i_keyfrom || defined i_keyclone || defined i_cmp || defined i_eq) - #define _i_no_hash -#endif #ifndef i_keyfrom #define i_keyfrom c_default_from #endif @@ -181,6 +193,12 @@ #ifdef i_val_str #define i_val_bind cstr #define i_valraw crawstr +#elif defined i_val_ssv + #define i_val cstr + #define i_valraw csview + #define i_valfrom cstr_from_sv + #define i_valto cstr_to_sv + #define i_valdrop cstr_drop #elif defined i_val_arcbox #define i_val_bind i_val_arcbox #define i_valraw c_paste(i_val_arcbox, _value) @@ -257,6 +275,7 @@ #undef i_val #undef i_val_str +#undef i_val_ssv #undef i_val_arcbox #undef i_val_bind #undef i_valraw @@ -267,6 +286,7 @@ #undef i_key #undef i_key_str +#undef i_key_ssv #undef i_key_arcbox #undef i_key_bind #undef i_keyraw -- cgit v1.2.3 From 6d8406e66c029d4c672bb7531aabec7eb1d079d8 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 24 Apr 2022 13:31:11 +0200 Subject: Created VERSION 3.5. See News section in docs for changes. --- README.md | 13 +- benchmarks/misc/sso_bench.c | 52 ----- benchmarks/misc/sso_bench.cpp | 115 +++++++++++ benchmarks/misc/sso_bench2.cpp | 114 ----------- benchmarks/misc/string_bench.c | 153 --------------- benchmarks/misc/string_bench.cpp | 199 ------------------- benchmarks/misc/string_bench_STC.cpp | 298 ++++++++++++++++++++++++++++ benchmarks/misc/string_bench_STD.cpp | 370 +++++++++++++++++++++++++++++++++++ docs/cstr_api.md | 1 + docs/csview_api.md | 2 +- include/stc/ccommon.h | 19 +- include/stc/cstr.h | 74 ++++--- include/stc/csview.h | 17 +- include/stc/template.h | 5 +- 14 files changed, 852 insertions(+), 580 deletions(-) delete mode 100644 benchmarks/misc/sso_bench.c create mode 100644 benchmarks/misc/sso_bench.cpp delete mode 100644 benchmarks/misc/sso_bench2.cpp delete mode 100644 benchmarks/misc/string_bench.c delete mode 100644 benchmarks/misc/string_bench.cpp create mode 100644 benchmarks/misc/string_bench_STC.cpp create mode 100644 benchmarks/misc/string_bench_STD.cpp diff --git a/README.md b/README.md index 754f58f4..8bc3e7fa 100644 --- a/README.md +++ b/README.md @@ -3,12 +3,13 @@ STC - Smart Template Containers for C ===================================== -News: Version 3 released (Jan 2022) ------------------------------------ -This version introduces lots of enhancements, bugfixes and additions. There are also -a number of [breaking changes](#brief-summary-of-changes) and [a migration guide from version 2 to 3](#migration-guide-from-version-2-to-3). -With version 3, the API is freezed as far as possible. Any changes will be handled with long -lasting deprecations, so you may develop production code using it. +News: Version 3.5 released (Mar 2022) +------------------------------------- +- Swapped to new **cstr** (*short string optimized*, aka SSO). Note that `cstr_str(&s)` must be used, `s.str` is no longer usable. +- Added general `i_clone` template parameter: containers with smart pointers (**carc**, **cbox**) can now be correctly cloned. +- Optimized *c_default_hash()*. Therefore *c_hash32()* and *c_hash64()* are removed (same speed). +- Added *.._push()* and *.._emplace()* function to all containers to allow for more generic coding. +- Added some examples and benchmarks for SSO and heterogenous lookup comparison with c++20 (string_bench_*.cpp). Introduction ------------ diff --git a/benchmarks/misc/sso_bench.c b/benchmarks/misc/sso_bench.c deleted file mode 100644 index f2714be1..00000000 --- a/benchmarks/misc/sso_bench.c +++ /dev/null @@ -1,52 +0,0 @@ -// https://gobyexample.com/maps -#include -#define i_type Map -#define i_key_str -#define i_val int -#include -#define i_type Vec -#define i_val_str -#include - -#include -#include - -void rndstr(char buf[64], int max) { - unsigned n = crandom() % max; - static char chr[64] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_"; - c_forrange (i, n) - buf[i] = chr[crandom() & 63]; - buf[n] = '\0'; -} - -enum {N = 10000000}; - -int main(void) { - - c_auto (Vec, vec) - c_auto (Map, map) { - char buf[128]; - - csrandom(time(NULL)); - printf("map\n"); - clock_t t0 = clock(), t1, t2; - c_forrange (i, int, N) { - rndstr(buf, 64); - Map_emplace(&map, buf, i); - } - t1 = clock(); - printf("vec\n"); - c_apply_cnt(v, Vec_push(&vec, cstr_clone(v->first)), Map, map); - t2 = clock(); - puts("map items:"); - int k = 0; - c_forpair (k, v, Map, map) - if (k++ == 5) break; else printf(" %s: %d\n", cstr_str(&_.k), _.v); - puts("vec items:"); - k = 0; - c_foreach (i, Vec, vec) - if (k++ == 5) break; else printf(" %s\n", cstr_str(i.ref)); - - printf("\nmap insert: %d ms\nvec pushes: %d ms\n", (int)((t1 - t0)*10000/CLOCKS_PER_SEC), (int)((t2 - t1)*10000/CLOCKS_PER_SEC)); - } -} diff --git a/benchmarks/misc/sso_bench.cpp b/benchmarks/misc/sso_bench.cpp new file mode 100644 index 00000000..08444320 --- /dev/null +++ b/benchmarks/misc/sso_bench.cpp @@ -0,0 +1,115 @@ +#include +#include +#include +#include +#define i_type svec +#define i_val_str +#include + +#define ROTL_(x, k) (x << (k) | x >> (8*sizeof(x) - (k))) + +static uint64_t g_romutrio[3] = { + 0x26aa069ea2fb1a4dULL, 0x70c72c95cd592d04ULL, + 0x504f333d3aa0b359ULL, +}; + +static inline uint64_t romutrio(void) { + uint64_t *s = g_romutrio, xp = s[0], yp = s[1], zp = s[2]; + s[0] = 15241094284759029579u * zp; + s[1] = yp - xp; s[1] = ROTL_(s[1], 12); + s[2] = zp - yp; s[2] = ROTL_(s[2], 44); + return xp; +} + +static void sromutrio(uint64_t seed) { + uint64_t *s = g_romutrio; + s[0] = 0x26aa069ea2fb1a4dULL + seed; + s[1] = 0x70c72c95cd592d04ULL + seed; + s[2] = 0x504f333d3aa0b359ULL + seed; +} + + +static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz=+-"; + +static const int BENCHMARK_SIZE = 5000000; +static const int MAX_STRING_LENGTH = 25; + +using time_point = std::chrono::high_resolution_clock::time_point; + +void addRandomString_STD(std::vector& vec, const int length) { + std::string s(length, 0); + char* p = &s[0]; + for (int i = 0; i < length; ++i) { + p[i] = CHARS[romutrio() & 63]; + } + s.append(s); + vec.push_back(s); +} + +void addRandomString_STC(svec& vec, const int length) { + cstr s = cstr_with_size(length, 0); + char* p = cstr_data(&s); + for (int i = 0; i < length; ++i) { + p[i] = CHARS[romutrio() & 63]; + } + cstr_append_s(&s, s); + svec_push_back(&vec, s); +} + +template +void benchmark(L& vec, const int length, R addRandomString) { + time_point t1 = std::chrono::high_resolution_clock::now(); + + if (length == 0) + for (int i = 0; i < BENCHMARK_SIZE; i++) + addRandomString(vec, (i*13 & 31) + 1); + else + for (int i = 0; i < BENCHMARK_SIZE; i++) + addRandomString(vec, length); + + time_point t2 = std::chrono::high_resolution_clock::now(); + const auto duration = std::chrono::duration_cast(t2 - t1).count(); + std::cerr << length*2 << "\t" << duration; +} + + +int main() { + uint64_t seed = 4321; + sromutrio(seed); + std::cerr << "length\ttime\tstd::string\n"; + for (int k = 0; k < 4; k++) { + std::vector vec; vec.reserve(BENCHMARK_SIZE); + benchmark(vec, 0, addRandomString_STD); + std::cout << '\t' << vec[0] << '\n'; + } + + sromutrio(seed); + std::cerr << "\nlength\ttime\tSTC string\n"; + for (int k = 0; k < 4; k++) { + svec vec = svec_with_capacity(BENCHMARK_SIZE); + benchmark(vec, 0, addRandomString_STC); + std::cout << '\t' << cstr_str(&vec.data[0]) << '\n'; + svec_drop(&vec); + } + + sromutrio(seed); + std::cerr << "length\ttime\tstd::string\n"; + for (int length = 1; length <= MAX_STRING_LENGTH; length++) { + std::vector vec; vec.reserve(BENCHMARK_SIZE); + benchmark(vec, length, addRandomString_STD); + std::cout << '\t' << vec[0] << '\n'; + } + + sromutrio(seed); + std::cerr << "\nlength\ttime\tSTC string\n"; + for (int length = 1; length <= MAX_STRING_LENGTH; length++) { + svec vec = svec_with_capacity(BENCHMARK_SIZE); + benchmark(vec, length, addRandomString_STC); + std::cout << '\t' << cstr_str(&vec.data[0]) << '\n'; + svec_drop(&vec); + } + + std::cerr << "sizeof std::string : " << sizeof(std::string) << std::endl + << "sizeof STC string : " << sizeof(cstr) << std::endl; + return 0; +} diff --git a/benchmarks/misc/sso_bench2.cpp b/benchmarks/misc/sso_bench2.cpp deleted file mode 100644 index 1355a727..00000000 --- a/benchmarks/misc/sso_bench2.cpp +++ /dev/null @@ -1,114 +0,0 @@ -#include -#include -#include -#include -#define i_type svec -#define i_val_str -#include - -#define ROTL_(x, k) (x << (k) | x >> (8*sizeof(x) - (k))) - -static uint64_t g_romutrio[3] = { - 0x26aa069ea2fb1a4dULL, 0x70c72c95cd592d04ULL, - 0x504f333d3aa0b359ULL, -}; - -static inline uint64_t romutrio(void) { - uint64_t *s = g_romutrio, xp = s[0], yp = s[1], zp = s[2]; - s[0] = 15241094284759029579u * zp; - s[1] = yp - xp; s[1] = ROTL_(s[1], 12); - s[2] = zp - yp; s[2] = ROTL_(s[2], 44); - return xp; -} - -static void sromutrio(uint64_t seed) { - uint64_t *s = g_romutrio; - s[0] = 0x26aa069ea2fb1a4dULL + seed; - s[1] = 0x70c72c95cd592d04ULL + seed; - s[2] = 0x504f333d3aa0b359ULL + seed; -} - - -static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz=+-"; - -static const int BENCHMARK_SIZE = 5000000; -static const int MAX_STRING_LENGTH = 20; - -using time_point = std::chrono::high_resolution_clock::time_point; - -void addRandomString_STD(std::vector& vec, const int length) { - std::string s(length, 0); - char* p = &s[0]; - for (int i = 0; i < length; ++i) { - p[i] = CHARS[romutrio() & 63]; - } - s.append(s); - vec.push_back(s); -} - -void addRandomString_STC(svec& vec, const int length) { - cstr s = cstr_with_size(length, 0); - char* p = cstr_data(&s); - for (int i = 0; i < length; ++i) { - p[i] = CHARS[romutrio() & 63]; - } - cstr_append_s(&s, s); - svec_push(&vec, s); -} - -template -void benchmark(L& vec, const int length, R addRandomString) { - time_point t1 = std::chrono::high_resolution_clock::now(); - - if (length == 0) - for (int i = 0; i < BENCHMARK_SIZE; i++) - addRandomString(vec, (i*13 & 31) + 1); - else - for (int i = 0; i < BENCHMARK_SIZE; i++) - addRandomString(vec, length); - - time_point t2 = std::chrono::high_resolution_clock::now(); - const auto duration = std::chrono::duration_cast(t2 - t1).count(); - std::cerr << length*2 << "\t" << duration; -} - - -int main() { - sromutrio(1234); - std::cerr << "length\ttime\tstd::string\n"; - for (int k = 0; k < 4; k++) { - std::vector vec; vec.reserve(BENCHMARK_SIZE); - benchmark(vec, 0, addRandomString_STD); - std::cout << '\t' << vec[0] << '\n'; - } - - sromutrio(1234); - std::cerr << "\nlength\ttime\tSTC string\n"; - for (int k = 0; k < 4; k++) { - svec vec = svec_with_capacity(BENCHMARK_SIZE); - benchmark(vec, 0, addRandomString_STC); - std::cout << '\t' << cstr_str(&vec.data[0]) << '\n'; - svec_drop(&vec); - } - - sromutrio(1234); - std::cerr << "length\ttime\tstd::string\n"; - for (int length = 1; length <= MAX_STRING_LENGTH; length++) { - std::vector vec; vec.reserve(BENCHMARK_SIZE); - benchmark(vec, length, addRandomString_STD); - std::cout << '\t' << vec[0] << '\n'; - } - - sromutrio(1234); - std::cerr << "\nlength\ttime\tSTC string\n"; - for (int length = 1; length <= MAX_STRING_LENGTH; length++) { - svec vec = svec_with_capacity(BENCHMARK_SIZE); - benchmark(vec, length, addRandomString_STC); - std::cout << '\t' << cstr_str(&vec.data[0]) << '\n'; - svec_drop(&vec); - } - - std::cerr << "size std::string : " << sizeof(std::string) << std::endl - << "size STC string : " << sizeof(cstr) << std::endl; - return 0; -} diff --git a/benchmarks/misc/string_bench.c b/benchmarks/misc/string_bench.c deleted file mode 100644 index fb2a70b2..00000000 --- a/benchmarks/misc/string_bench.c +++ /dev/null @@ -1,153 +0,0 @@ -// https://www.codeproject.com/Tips/5255442/Cplusplus14-20-Heterogeneous-Lookup-Benchmark -// https://github.com/shaovoon/cpp_hetero_lookup_bench - -#include - -#define i_val_str -#include - -#define i_key_str -#define i_val size_t -#include - -#define i_key_str -#define i_val size_t -#include - - -cvec_str read_file(const char* name) -{ - cvec_str data = cvec_str_init(); - c_auto (cstr, line) - c_autovar (FILE* f = fopen(name, "r"), fclose(f)) - while (cstr_getline(&line, f)) - cvec_str_emplace_back(&data, cstr_str(&line)); - return data; -} - -void initShortStringVec(cvec_str* vs) -{ - cvec_str_clear(vs); - - *vs = read_file("names.txt"); - size_t lengths = 0; - c_foreach (i, cvec_str, *vs) - { - cstr_append_s(i.ref, *i.ref); - cstr_append_s(i.ref, *i.ref); - lengths += cstr_size(*i.ref); - } - printf("avg len: %f\n", (float)lengths / cvec_str_size(*vs)); -} - -void initLongStringVec(cvec_str* vs) -{ - cvec_str_clear(vs); - *vs = read_file("names.txt"); - cstr* s = vs->data; - size_t lengths = 0; - cstr_append_s(s, s[1]); - cstr_append_s(s, s[2]); - cstr_append_s(s, s[3]); - for (int i=1; i < cvec_str_size(*vs); ++i) - { - cstr* t = vs->data + i; - cstr_append_s(t, *t); - cstr_append_s(t, *t); - cstr_append_s(t, *s); - cstr_append_s(t, *t); - cstr_append_s(t, *t); - lengths += cstr_size(*t); - } - printf("avg len: %f\n", (float)lengths / cvec_str_size(*vs)); -} - -struct Maps { - csmap_str* snormal; - cmap_str* unormal; -}; - -void initMaps(cvec_str vs, struct Maps maps) -{ - csmap_str_clear(maps.snormal); - cmap_str_clear(maps.unormal); - - for (size_t i = 0; i < cvec_str_size(vs); ++i) - { - cstr str = *cvec_str_at(&vs, i); - csmap_str_insert(maps.snormal, cstr_clone(str), i); - cmap_str_insert(maps.unormal, cstr_clone(str), i); - } -} - -void benchmark(cvec_str vec_string, struct Maps maps); - -static const size_t MAX_LOOP = 2000; - -int main() -{ - c_auto (cvec_str, vec_string) - c_auto (csmap_str, snormal) - c_auto (cmap_str, unormal) - { - struct Maps maps = { &snormal, &unormal }; - - initShortStringVec(&vec_string); - initMaps(vec_string, maps); - - puts("Short String Benchmark"); - puts("======================"); - - benchmark(vec_string, maps); - - puts("\nLong String Benchmark"); - puts("======================"); - - initLongStringVec(&vec_string); - initMaps(vec_string, maps); - - benchmark(vec_string, maps); - } -} - -void benchmark(cvec_str vec_string, struct Maps maps) -{ - size_t grandtotal = 0; - size_t total; - clock_t stopwatch; - - total = 0; - printf("%32s", "Trans Map with char*"); - stopwatch = clock(); - for (size_t i = 0; i < MAX_LOOP; ++i) - { - csmap_str_iter it, end = csmap_str_end(maps.snormal); - for (size_t j = 0; j < cvec_str_size(vec_string); ++j) - { - csmap_str_find_it(maps.snormal, cstr_str(&vec_string.data[j]), &it); - if (it.ref != end.ref) - total += it.ref->second; - } - } - grandtotal += total; - printf(" timing:%5.0fms\n", (clock() - stopwatch) / (float)CLOCKS_PER_SEC * 1000.0f); - - - total = 0; - printf("%32s", "Trans Unord Map with char*"); - stopwatch = clock(); - for (size_t i = 0; i < MAX_LOOP; ++i) - { - cmap_str_iter it, end = cmap_str_end(maps.unormal); - for (size_t j = 0; j < cvec_str_size(vec_string); ++j) - { - it = cmap_str_find(maps.unormal, cstr_str(&vec_string.data[j])); - if (it.ref != end.ref) - total += it.ref->second; - } - } - grandtotal += total; - printf(" timing:%5.0fms\n", (clock() - stopwatch) / (float)CLOCKS_PER_SEC * 1000.0f); - - printf("C grandtotal: %" PRIuMAX " <--- Ignore this\n", grandtotal); -} diff --git a/benchmarks/misc/string_bench.cpp b/benchmarks/misc/string_bench.cpp deleted file mode 100644 index 65bf7a0e..00000000 --- a/benchmarks/misc/string_bench.cpp +++ /dev/null @@ -1,199 +0,0 @@ -// https://www.codeproject.com/Tips/5255442/Cplusplus14-20-Heterogeneous-Lookup-Benchmark -// https://github.com/shaovoon/cpp_hetero_lookup_bench - -#include -#include -#include -#include -#include -#include -#include - -#define i_val_str -#include - - -std::vector read_file(const char* name) -{ - std::vector data; - c_auto (cstr, line) - c_autovar (FILE* f = fopen(name, "r"), fclose(f)) - while (cstr_getline(&line, f)) - data.emplace_back(cstr_str(&line)); - return data; -} - -class timer -{ -public: - timer() = default; - void start(const std::string& text_) - { - text = text_; - begin = std::chrono::high_resolution_clock::now(); - } - void stop() - { - auto end = std::chrono::high_resolution_clock::now(); - auto dur = end - begin; - auto ms = std::chrono::duration_cast(dur).count(); - std::cout << std::setw(32) << text << " timing:" << std::setw(5) << ms << "ms" << std::endl; - } - -private: - std::string text; - std::chrono::high_resolution_clock::time_point begin; -}; - -void initShortStringVec(std::vector& vs) -{ - vs.clear(); - vs = read_file("names.txt"); - size_t num = 0; - - for (size_t i = 0; i < vs.size(); ++i) - { - num += vs[i].size(); - } - printf("avg len: %f\n", (float)num / vs.size()); -} - -void initLongStringVec(std::vector& vs) -{ - vs.clear(); - vs = read_file("names.txt"); - size_t num = 0; - vs[0] += vs[1]; - vs[0] += vs[2]; - vs[0] += vs[3]; - for (size_t i = 1; i < vs.size(); ++i) - { - vs[i] += vs[i]; - vs[i] += vs[i]; - vs[i] += vs[0]; - vs[i] += vs[i]; - vs[i] += vs[i]; - num += vs[i].size(); - } - printf("avg len: %f\n", (float)num / vs.size()); -} - -void initMapNormal(const std::vector& vs, - std::map& mapNormal, - std::unordered_map& unordmapNormal) -{ - mapNormal.clear(); - unordmapNormal.clear(); - for (size_t i = 0; i < vs.size(); ++i) - { - mapNormal.insert(std::make_pair(vs.at(i), i)); - unordmapNormal.insert(std::make_pair(vs.at(i), i)); - } -} -/* -struct string_hash { - using is_transparent = void; - using hash_type = std::hash; // just a helper local type - size_t operator()(const std::string& txt) const { return hash_type{}(txt); } - size_t operator()(const char* txt) const { return hash_type{}(txt); } -};*/ - -void benchmark( - const std::vector& vec_string, - const std::map& mapNormal, - const std::unordered_map& unordmapNormal); - -const size_t MAX_LOOP = 2000; - -int main() -{ - std::vector vec_string; - - std::map mapNormal; - std::unordered_map unordmapNormal; - - initShortStringVec(vec_string); - initMapNormal(vec_string, mapNormal, unordmapNormal); - - std::cout << "Short String Benchmark" << std::endl; - std::cout << "======================" << std::endl; - - benchmark(vec_string, mapNormal, unordmapNormal); - - std::cout << "Long String Benchmark" << std::endl; - std::cout << "=====================" << std::endl; - - initLongStringVec(vec_string); - initMapNormal(vec_string, mapNormal, unordmapNormal); - - benchmark(vec_string, mapNormal, unordmapNormal); - return 0; -} - -void benchmark( - const std::vector& vec_string, - const std::map& mapNormal, - const std::unordered_map& unordmapNormal) -{ - size_t grandtotal = 0; - size_t total = 0; - timer stopwatch; - - total = 0; - stopwatch.start("Normal Map with string"); - for (size_t i = 0; i < MAX_LOOP; ++i) - { - for (size_t j = 0; j < vec_string.size(); ++j) - { - const auto& it = mapNormal.find(vec_string[j]); - if(it!=mapNormal.cend()) - total += it->second; - } - } - grandtotal += total; - stopwatch.stop(); - - total = 0; - stopwatch.start("Normal Map with char*"); - for (size_t i = 0; i < MAX_LOOP; ++i) - { - for (size_t j = 0; j < vec_string.size(); ++j) - { - const auto& it = mapNormal.find(vec_string[j].c_str()); - if (it != mapNormal.cend()) - total += it->second; - } - } - grandtotal += total; - stopwatch.stop(); - - total = 0; - stopwatch.start("Normal Unord Map with string"); - for (size_t i = 0; i < MAX_LOOP; ++i) - { - for (size_t j = 0; j < vec_string.size(); ++j) - { - const auto& it = unordmapNormal.find(vec_string[j]); - if (it != unordmapNormal.cend()) - total += it->second; - } - } - grandtotal += total; - stopwatch.stop(); - - total = 0; - stopwatch.start("Normal Unord Map with char*"); - for (size_t i = 0; i < MAX_LOOP; ++i) - { - for (size_t j = 0; j < vec_string.size(); ++j) - { - const auto& it = unordmapNormal.find(vec_string[j].c_str()); - if (it != unordmapNormal.cend()) - total += it->second; - } - } - grandtotal += total; - stopwatch.stop(); - - std::cout << "C++ grandtotal:" << grandtotal << " <--- Ignore this\n" << std::endl; -} \ No newline at end of file diff --git a/benchmarks/misc/string_bench_STC.cpp b/benchmarks/misc/string_bench_STC.cpp new file mode 100644 index 00000000..ed0e3243 --- /dev/null +++ b/benchmarks/misc/string_bench_STC.cpp @@ -0,0 +1,298 @@ +// https://www.codeproject.com/Tips/5255442/Cplusplus14-20-Heterogeneous-Lookup-Benchmark +// https://github.com/shaovoon/cpp_hetero_lookup_bench + +#include +#include +#include +#include // string +#include // string_view + +#define i_key_str +#include // vec of cstr with const char* lookup + +#define i_type cvec_sv // override default type name (cvec_csview) +#define i_key csview +#define i_cmp csview_cmp +#include // cvec_vs: vec of csview + +#define i_key_str +#define i_val size_t +#include // sorted map of cstr, const char* lookup + +#define i_key_ssv +#define i_val size_t +#include // sorted map of cstr, csview lookup + +#define i_key_str +#define i_val size_t +#include // unordered map of cstr, const char* lookup + +#define i_key_ssv +#define i_val size_t +#include // unordered map of cstr, csview lookup + + +cvec_str read_file(const char* name) +{ + cvec_str data = cvec_str_init(); + c_auto (cstr, line) + c_autovar (FILE* f = fopen(name, "r"), fclose(f)) + while (cstr_getline(&line, f)) + cvec_str_emplace_back(&data, cstr_str(&line)); + return data; +} + +class timer +{ +public: + timer() = default; + void start(const std::string& text_) + { + text = text_; + begin = std::chrono::high_resolution_clock::now(); + } + void stop() + { + auto end = std::chrono::high_resolution_clock::now(); + auto dur = end - begin; + auto ms = std::chrono::duration_cast(dur).count(); + std::cout << std::setw(32) << text << " timing:" << std::setw(5) << ms << "ms" << std::endl; + } + +private: + std::string text; + std::chrono::high_resolution_clock::time_point begin; +}; + +void initShortStringVec(cvec_str* vs, cvec_sv* vsv) +{ + cvec_str_clear(vs); + cvec_sv_clear(vsv); + + *vs = read_file("names.txt"); +/* + cvec_str_emplace_back(vs, "Susan"); + cvec_str_emplace_back(vs, "Jason"); + cvec_str_emplace_back(vs, "Lily"); + cvec_str_emplace_back(vs, "Michael"); + cvec_str_emplace_back(vs, "Mary"); + + cvec_str_emplace_back(vs, "Jerry"); + cvec_str_emplace_back(vs, "Jenny"); + cvec_str_emplace_back(vs, "Klaus"); + cvec_str_emplace_back(vs, "Celine"); + cvec_str_emplace_back(vs, "Kenny"); + + cvec_str_emplace_back(vs, "Kelly"); + cvec_str_emplace_back(vs, "Jackson"); + cvec_str_emplace_back(vs, "Mandy"); + cvec_str_emplace_back(vs, "Terry"); + cvec_str_emplace_back(vs, "Sandy"); + + cvec_str_emplace_back(vs, "Billy"); + cvec_str_emplace_back(vs, "Cindy"); + cvec_str_emplace_back(vs, "Phil"); + cvec_str_emplace_back(vs, "Lindy"); + cvec_str_emplace_back(vs, "David"); +*/ + size_t num = 0; + c_foreach (i, cvec_str, *vs) + { + cvec_sv_push_back(vsv, csview_from_s(i.ref)); + num += cstr_size(*i.ref); + } + std::cout << "num strings: " << cvec_sv_size(*vsv) << std::endl; + std::cout << "avg str len: " << num / (float)cvec_sv_size(*vsv) << std::endl; +} + +void initLongStringVec(cvec_str* vs, cvec_sv* vsv) +{ + cvec_str_clear(vs); + cvec_sv_clear(vsv); + + *vs = read_file("names.txt"); + c_foreach (i, cvec_str, *vs) { + cstr_append_s(i.ref, *i.ref); + cstr_append_s(i.ref, *i.ref); + cstr_append_s(i.ref, *i.ref); + } +/* + cvec_str_emplace_back(vs, "Susan Susan Susan Susan Susan Susan"); + cvec_str_emplace_back(vs, "Jason Jason Jason Jason Jason Jason"); + cvec_str_emplace_back(vs, "Lily Lily Lily Lily Lily Lily"); + cvec_str_emplace_back(vs, "Michael Michael Michael Michael Michael Michael"); + cvec_str_emplace_back(vs, "Mary Mary Mary Mary Mary Mary"); + + cvec_str_emplace_back(vs, "Jerry Jerry Jerry Jerry Jerry Jerry"); + cvec_str_emplace_back(vs, "Jenny Jenny Jenny Jenny Jenny Jenny"); + cvec_str_emplace_back(vs, "Klaus Klaus Klaus Klaus Klaus Klaus"); + cvec_str_emplace_back(vs, "Celine Celine Celine Celine Celine Celine"); + cvec_str_emplace_back(vs, "Kenny Kenny Kenny Kenny Kenny Kenny"); + + cvec_str_emplace_back(vs, "Kelly Kelly Kelly Kelly Kelly Kelly"); + cvec_str_emplace_back(vs, "Jackson Jackson Jackson Jackson Jackson Jackson"); + cvec_str_emplace_back(vs, "Mandy Mandy Mandy Mandy Mandy Mandy"); + cvec_str_emplace_back(vs, "Terry Terry Terry Terry Terry Terry"); + cvec_str_emplace_back(vs, "Sandy Sandy Sandy Sandy Sandy Sandy"); + + cvec_str_emplace_back(vs, "Billy Billy Billy Billy Billy Billy"); + cvec_str_emplace_back(vs, "Cindy Cindy Cindy Cindy Cindy Cindy"); + cvec_str_emplace_back(vs, "Phil Phil Phil Phil Phil Phil"); + cvec_str_emplace_back(vs, "Lindy Lindy Lindy Lindy Lindy Lindy"); + cvec_str_emplace_back(vs, "David David David David David David"); +*/ + size_t num = 0; + c_foreach (i, cvec_str, *vs) + { + cvec_sv_push_back(vsv, csview_from_s(i.ref)); + num += cstr_size(*i.ref); + } + std::cout << "num strings: " << cvec_sv_size(*vsv) << std::endl; + std::cout << "avg str len: " << num / (float)cvec_sv_size(*vsv) << std::endl; +} + +void initMaps(const cvec_str* vs, csmap_str* mapTrans, csmap_ssv* mapSview, + cmap_str* unordmapTrans, cmap_ssv* unordmapSview) +{ + csmap_str_clear(mapTrans); + csmap_ssv_clear(mapSview); + cmap_str_clear(unordmapTrans); + cmap_ssv_clear(unordmapSview); + + size_t n = 0; + c_foreach (i, cvec_str, *vs) + { + csmap_str_insert(mapTrans, cstr_clone(*i.ref), n); + csmap_ssv_insert(mapSview, cstr_clone(*i.ref), n); + cmap_str_insert(unordmapTrans, cstr_clone(*i.ref), n); + cmap_ssv_insert(unordmapSview, cstr_clone(*i.ref), n); + ++n; + } +} + +void benchmark( + const cvec_str* vec_string, + const cvec_sv* vec_stringview, + const csmap_str* mapTrans, + const csmap_ssv* mapSview, + const cmap_str* unordmapTrans, + const cmap_ssv* unordmapSview); + +//const size_t MAX_LOOP = 1000000; +const size_t MAX_LOOP = 2000; + +int main() +{ + c_auto (cvec_str, vec_string) + c_auto (cvec_sv, vec_stringview) + c_auto (csmap_str, mapTrans) + c_auto (csmap_ssv, mapSview) + c_auto (cmap_str, unordmapTrans) + c_auto (cmap_ssv, unordmapSview) + { + std::cout << "Short String Benchmark" << std::endl; + std::cout << "======================" << std::endl; + + initShortStringVec(&vec_string, &vec_stringview); + initMaps(&vec_string, &mapTrans, &mapSview, + &unordmapTrans, &unordmapSview); + + for (int i=0; i<3; ++i) + benchmark( + &vec_string, + &vec_stringview, + &mapTrans, + &mapSview, + &unordmapTrans, + &unordmapSview); + + std::cout << "Long String Benchmark" << std::endl; + std::cout << "=====================" << std::endl; + + initLongStringVec(&vec_string, &vec_stringview); + initMaps(&vec_string, &mapTrans, &mapSview, + &unordmapTrans, &unordmapSview); + for (int i=0; i<3; ++i) + benchmark( + &vec_string, + &vec_stringview, + &mapTrans, + &mapSview, + &unordmapTrans, + &unordmapSview); + } + return 0; +} + +void benchmark( + const cvec_str* vec_string, + const cvec_sv* vec_stringview, + const csmap_str* mapTrans, + const csmap_ssv* mapSview, + const cmap_str* unordmapTrans, + const cmap_ssv* unordmapSview) +{ + size_t grandtotal = 0; + + size_t total = 0; + + timer stopwatch; + total = 0; + stopwatch.start("Trans Map with char*"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + c_foreach (j, cvec_str, *vec_string) + { + const csmap_str_value* v = csmap_str_get(mapTrans, cstr_str(j.ref)); + if (v) + total += v->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Trans Map with string_view"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + c_foreach (j, cvec_sv, *vec_stringview) + { + const csmap_ssv_value* v = csmap_ssv_get(mapSview, *j.ref); + if (v) + total += v->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Trans Unord Map with char*"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + c_foreach (j, cvec_str, *vec_string) + { + const cmap_str_value* v = cmap_str_get(unordmapTrans, cstr_str(j.ref)); + if (v) + total += v->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Trans Unord Map with string_view"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + c_foreach (j, cvec_sv, *vec_stringview) + { + const cmap_ssv_value* v = cmap_ssv_get(unordmapSview, *j.ref); + if (v) + total += v->second; + } + } + grandtotal += total; + stopwatch.stop(); + + std::cout << "grandtotal:" << grandtotal << " <--- Ignore this\n" << std::endl; + +} diff --git a/benchmarks/misc/string_bench_STD.cpp b/benchmarks/misc/string_bench_STD.cpp new file mode 100644 index 00000000..595ab632 --- /dev/null +++ b/benchmarks/misc/string_bench_STD.cpp @@ -0,0 +1,370 @@ +// https://www.codeproject.com/Tips/5255442/Cplusplus14-20-Heterogeneous-Lookup-Benchmark +// https://github.com/shaovoon/cpp_hetero_lookup_bench +// Requires c++20, e.g. g++ -std=c++20 + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +std::vector read_file(const char* name) +{ + std::vector data; + c_auto (cstr, line) + c_autovar (FILE* f = fopen(name, "r"), fclose(f)) + while (cstr_getline(&line, f)) + data.emplace_back(cstr_str(&line)); + return data; +} + +class timer +{ +public: + timer() = default; + void start(const std::string& text_) + { + text = text_; + begin = std::chrono::high_resolution_clock::now(); + } + void stop() + { + auto end = std::chrono::high_resolution_clock::now(); + auto dur = end - begin; + auto ms = std::chrono::duration_cast(dur).count(); + std::cout << std::setw(32) << text << " timing:" << std::setw(5) << ms << "ms" << std::endl; + } + +private: + std::string text; + std::chrono::high_resolution_clock::time_point begin; +}; + +void initShortStringVec(std::vector& vs, std::vector& vsv) +{ + vs.clear(); + vsv.clear(); + + vs = read_file("names.txt"); +/* + vs.push_back("Susan"); + vs.push_back("Jason"); + vs.push_back("Lily"); + vs.push_back("Michael"); + vs.push_back("Mary"); + + vs.push_back("Jerry"); + vs.push_back("Jenny"); + vs.push_back("Klaus"); + vs.push_back("Celine"); + vs.push_back("Kenny"); + + vs.push_back("Kelly"); + vs.push_back("Jackson"); + vs.push_back("Mandy"); + vs.push_back("Terry"); + vs.push_back("Sandy"); + + vs.push_back("Billy"); + vs.push_back("Cindy"); + vs.push_back("Phil"); + vs.push_back("Lindy"); + vs.push_back("David"); +*/ + size_t num = 0; + for (size_t i = 0; i < vs.size(); ++i) + { + vsv.push_back(vs.at(i)); + num += vs.at(i).size(); + } + std::cout << "num strings: " << vsv.size() << std::endl; + std::cout << "avg str len: " << num / (float)vsv.size() << std::endl; +} + +void initLongStringVec(std::vector& vs, std::vector& vsv) +{ + vs.clear(); + vsv.clear(); + + vs = read_file("names.txt"); + for (size_t i = 1; i < vs.size(); ++i) { + vs[i] += vs[i]; + vs[i] += vs[i]; + vs[i] += vs[i]; + } +/* + vs.push_back("Susan Susan Susan Susan Susan Susan"); + vs.push_back("Jason Jason Jason Jason Jason Jason"); + vs.push_back("Lily Lily Lily Lily Lily Lily"); + vs.push_back("Michael Michael Michael Michael Michael Michael"); + vs.push_back("Mary Mary Mary Mary Mary Mary"); + + vs.push_back("Jerry Jerry Jerry Jerry Jerry Jerry"); + vs.push_back("Jenny Jenny Jenny Jenny Jenny Jenny"); + vs.push_back("Klaus Klaus Klaus Klaus Klaus Klaus"); + vs.push_back("Celine Celine Celine Celine Celine Celine"); + vs.push_back("Kenny Kenny Kenny Kenny Kenny Kenny"); + + vs.push_back("Kelly Kelly Kelly Kelly Kelly Kelly"); + vs.push_back("Jackson Jackson Jackson Jackson Jackson Jackson"); + vs.push_back("Mandy Mandy Mandy Mandy Mandy Mandy"); + vs.push_back("Terry Terry Terry Terry Terry Terry"); + vs.push_back("Sandy Sandy Sandy Sandy Sandy Sandy"); + + vs.push_back("Billy Billy Billy Billy Billy Billy"); + vs.push_back("Cindy Cindy Cindy Cindy Cindy Cindy"); + vs.push_back("Phil Phil Phil Phil Phil Phil"); + vs.push_back("Lindy Lindy Lindy Lindy Lindy Lindy"); + vs.push_back("David David David David David David"); +*/ + size_t num = 0; + for (size_t i = 0; i < vs.size(); ++i) + { + vsv.push_back(vs.at(i)); + num += vs.at(i).size(); + } + std::cout << "num strings: " << vsv.size() << std::endl; + std::cout << "avg str len: " << num / (float)vsv.size() << std::endl; +} + +void initMapNormal(const std::vector& vs, std::map& mapNormal) +{ + mapNormal.clear(); + for (size_t i = 0; i < vs.size(); ++i) + { + mapNormal.insert(std::make_pair(vs.at(i), i)); + } +} + +void initMapTrans(const std::vector& vs, std::map >& mapTrans) +{ + mapTrans.clear(); + for (size_t i = 0; i < vs.size(); ++i) + { + mapTrans.insert(std::make_pair(vs.at(i), i)); + } +} + +struct MyEqual : public std::equal_to<> +{ + using is_transparent = void; +}; + +struct string_hash { + using is_transparent = void; + using key_equal = std::equal_to<>; // Pred to use + using hash_type = std::hash; // just a helper local type + size_t operator()(std::string_view txt) const { return hash_type{}(txt); } + size_t operator()(const std::string& txt) const { return hash_type{}(txt); } + size_t operator()(const char* txt) const { return hash_type{}(txt); } +}; + +void initUnorderedMapNormal(const std::vector& vs, std::unordered_map& unordmapNormal) +{ + unordmapNormal.clear(); + for (size_t i = 0; i < vs.size(); ++i) + { + unordmapNormal.insert(std::make_pair(vs.at(i), i)); + } +} + +void initUnorderedMapTrans(const std::vector& vs, std::unordered_map& unordmapTrans) +{ + unordmapTrans.clear(); + for (size_t i = 0; i < vs.size(); ++i) + { + unordmapTrans.insert(std::make_pair(vs.at(i), i)); + } +} + +void benchmark( + const std::vector& vec_shortstr, + const std::vector& vec_shortstrview, + const std::map& mapNormal, + const std::map >& mapTrans, + const std::unordered_map& unordmapNormal, + const std::unordered_map& unordmapTrans); + +//const size_t MAX_LOOP = 1000000; +const size_t MAX_LOOP = 2000; + +int main() +{ + std::vector vec_shortstr; + std::vector vec_shortstrview; + + std::map mapNormal; + std::map > mapTrans; + initShortStringVec(vec_shortstr, vec_shortstrview); + initMapNormal(vec_shortstr, mapNormal); + initMapTrans(vec_shortstr, mapTrans); + + std::unordered_map unordmapNormal; + std::unordered_map unordmapTrans; + initUnorderedMapNormal(vec_shortstr, unordmapNormal); + initUnorderedMapTrans(vec_shortstr, unordmapTrans); + + std::cout << "Short String Benchmark" << std::endl; + std::cout << "======================" << std::endl; + + for (int i=0; i<3; ++i) benchmark( + vec_shortstr, + vec_shortstrview, + mapNormal, + mapTrans, + unordmapNormal, + unordmapTrans); + + std::cout << "Long String Benchmark" << std::endl; + std::cout << "=====================" << std::endl; + + initLongStringVec(vec_shortstr, vec_shortstrview); + initMapNormal(vec_shortstr, mapNormal); + initMapTrans(vec_shortstr, mapTrans); + + initUnorderedMapNormal(vec_shortstr, unordmapNormal); + initUnorderedMapTrans(vec_shortstr, unordmapTrans); + + for (int i=0; i<3; ++i) benchmark( + vec_shortstr, + vec_shortstrview, + mapNormal, + mapTrans, + unordmapNormal, + unordmapTrans); + + return 0; +} + +void benchmark( + const std::vector& vec_shortstr, + const std::vector& vec_shortstrview, + const std::map& mapNormal, + const std::map >& mapTrans, + const std::unordered_map& unordmapNormal, + const std::unordered_map& unordmapTrans) +{ + size_t grandtotal = 0; + size_t total = 0; + timer stopwatch; +/* + total = 0; + stopwatch.start("Normal Map with string"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_shortstr.size(); ++j) + { + const auto& it = mapNormal.find(vec_shortstr[j]); + if(it!=mapNormal.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Normal Map with char*"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_shortstr.size(); ++j) + { + const auto& it = mapNormal.find(vec_shortstr[j].c_str()); + if (it != mapNormal.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); +*/ + total = 0; + stopwatch.start("Trans Map with char*"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_shortstr.size(); ++j) + { + const auto& it = mapTrans.find(vec_shortstr[j].c_str()); + if (it != mapTrans.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Trans Map with string_view"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_shortstrview.size(); ++j) + { + const auto& it = mapTrans.find(vec_shortstrview[j]); + if (it != mapTrans.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); +/* + total = 0; + stopwatch.start("Normal Unord Map with string"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_shortstr.size(); ++j) + { + const auto& it = unordmapNormal.find(vec_shortstr[j]); + if (it != unordmapNormal.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Normal Unord Map with char*"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_shortstr.size(); ++j) + { + const auto& it = unordmapNormal.find(vec_shortstr[j].c_str()); + if (it != unordmapNormal.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); +*/ + total = 0; + stopwatch.start("Trans Unord Map with char*"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_shortstr.size(); ++j) + { + const auto& it = unordmapTrans.find(vec_shortstr[j].c_str()); + if (it != unordmapTrans.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Trans Unord Map with string_view"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_shortstrview.size(); ++j) + { + const auto& it = unordmapTrans.find(vec_shortstrview[j]); + if (it != unordmapTrans.cend()) + total += it->second; + } + } + grandtotal += total; + + stopwatch.stop(); + + std::cout << "grandtotal:" << grandtotal << " <--- Ignore this\n" << std::endl; + +} diff --git a/docs/cstr_api.md b/docs/cstr_api.md index 4f7c689e..85a872fe 100644 --- a/docs/cstr_api.md +++ b/docs/cstr_api.md @@ -22,6 +22,7 @@ cstr cstr_from_n(const char* str, size_t n); // constru cstr cstr_with_capacity(size_t cap); cstr cstr_with_size(size_t len, char fill); // repeat fill len times cstr cstr_from_fmt(const char* fmt, ...); // printf() formatting +cstr cstr_from_replace_all_sv(csview sv, csview find, csview repl); cstr cstr_clone(cstr s); cstr* cstr_take(cstr* self, cstr s); // take the constructed or moved string diff --git a/docs/csview_api.md b/docs/csview_api.md index a472194f..5211e2f6 100644 --- a/docs/csview_api.md +++ b/docs/csview_api.md @@ -76,7 +76,7 @@ uint32_t utf8_decode(uint32_t *state, uint32_t *codep, const uint32_t byt #### Extended cstr methods ```c cstr cstr_from_sv(csview sv); // construct cstr from csview -csview cstr_to_sv(const cstr* self); // convert to csview from const cstr* +csview cstr_sv(const cstr* self); // convert to csview from const cstr* cstr cstr_from_replace_all_sv(csview sv, csview find, csview replace); csview cstr_substr(const cstr* s, intptr_t pos, size_t n); // negative pos count from end diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index 56dd501e..1c19bde7 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -112,27 +112,24 @@ typedef const char* crawstr; #define _c_ROTL(x, k) (x << (k) | x >> (8*sizeof(x) - (k))) -STC_INLINE uint64_t c_strhash(const char *s) { - int c; uint64_t h = *s++; - if (h) while ((c = *s++)) h = (h << 10) - h + c; - return _c_ROTL(h, 26) ^ h; -} - STC_INLINE uint64_t c_default_hash(const void* key, size_t len) { - uint64_t u8, h = 1; + uint64_t u8, h = 1; size_t n = len >> 3; uint32_t u4; const uint8_t *x = (const uint8_t*) key; - for (size_t n = len >> 3; n--; ) - memcpy(&u8, x, 8), x += 8, h += u8*0xc6a4a7935bd1e99d; + while (n--) + memcpy(&u8, x, 8), x += 8, h += (h << 10) ^ (u8*0xc6a4a7935bd1e99d); switch (len &= 7) { - case 0: return h; - case 4: memcpy(&u4, x, 4); return h + u4*0xc6a4a7935bd1e99d; + case 0: return h; + case 4: memcpy(&u4, x, 4); return h + u4*0xc6a4a7935bd1e99d; } h += *x++; while (--len) h = (h << 10) - h + *x++; return _c_ROTL(h, 26) ^ h; } +STC_INLINE uint64_t c_strhash(const char *s) + { return c_default_hash(s, strlen(s)); } + STC_INLINE char* c_strnstrn(const char *s, const char *needle, size_t slen, const size_t nlen) { if (!nlen) return (char *)s; if (nlen > slen) return NULL; diff --git a/include/stc/cstr.h b/include/stc/cstr.h index 9c6568f7..b669b6d5 100644 --- a/include/stc/cstr.h +++ b/include/stc/cstr.h @@ -87,12 +87,17 @@ STC_API void cstr_erase_n(cstr* self, size_t pos, size_t n); STC_API cstr cstr_from_fmt(const char* fmt, ...); STC_API int cstr_printf(cstr* self, const char* fmt, ...); STC_API void cstr_replace_all(cstr* self, const char* find, const char* repl); +STC_API cstr cstr_from_replace_all_sv(csview sv, csview find, csview repl); STC_INLINE cstr_rep_t cstr_rep(cstr* s) { return cstr_is_long(s) ? c_make(cstr_rep_t){s->lon.data, cstr_l_size(s), cstr_l_cap(s)} : c_make(cstr_rep_t){s->sml.data, cstr_s_size(s), cstr_s_cap}; } +STC_INLINE csview cstr_sv(const cstr* s) { + return cstr_is_long(s) ? c_make(csview){s->lon.data, cstr_l_size(s)} + : c_make(csview){s->sml.data, cstr_s_size(s)}; +} STC_INLINE cstr cstr_init(void) { return cstr_null; } @@ -132,8 +137,8 @@ STC_INLINE cstr cstr_move(cstr* self) { } STC_INLINE cstr cstr_clone(cstr s) { - cstr_rep_t r = cstr_rep(&s); - return cstr_from_n(r.data, r.size); + csview sv = cstr_sv(&s); + return cstr_from_n(sv.str, sv.size); } STC_INLINE void cstr_drop(cstr* self) { @@ -169,17 +174,19 @@ STC_INLINE size_t cstr_length(cstr s) STC_INLINE size_t cstr_capacity(cstr s) { return cstr_is_long(&s) ? cstr_l_cap(&s) : cstr_s_cap; } +STC_INLINE int cstr_cmp(const cstr* s1, const cstr* s2) + { return strcmp(cstr_str(s1), cstr_str(s2)); } + +STC_INLINE bool cstr_eq(const cstr* s1, const cstr* s2) { + csview x = cstr_sv(s1), y = cstr_sv(s2); + return x.size == y.size && !memcmp(x.str, y.str, x.size); +} + STC_INLINE bool cstr_equals(cstr s1, const char* str) { return strcmp(cstr_str(&s1), str) == 0; } STC_INLINE bool cstr_equals_s(cstr s1, cstr s2) - { return strcmp(cstr_str(&s1), cstr_str(&s2)) == 0; } - -STC_INLINE bool cstr_eq(const cstr* s1, const cstr* s2) - { return strcmp(cstr_str(s1), cstr_str(s2)) == 0; } - -STC_INLINE int cstr_cmp(const cstr* s1, const cstr* s2) - { return strcmp(cstr_str(s1), cstr_str(s2)); } + { return cstr_cmp(&s1, &s2) == 0; } STC_INLINE size_t cstr_find(cstr s, const char* needle) { const char *str = cstr_str(&s), *res = strstr(str, needle); @@ -205,8 +212,8 @@ STC_INLINE bool cstr_starts_with_s(cstr s, cstr sub) { return cstr_starts_with(s, cstr_str(&sub)); } STC_INLINE bool cstr_ends_with(cstr s, const char* sub) { - cstr_rep_t r = cstr_rep(&s); size_t n = strlen(sub); - return n <= r.size && memcmp(r.data + r.size - n, sub, n) == 0; + csview sv = cstr_sv(&s); size_t n = strlen(sub); + return n <= sv.size && memcmp(sv.str + sv.size - n, sub, n) == 0; } STC_INLINE bool cstr_ends_with_s(cstr s, cstr sub) @@ -216,16 +223,16 @@ STC_INLINE void cstr_assign(cstr* self, const char* str) { cstr_assign_n(self, str, strlen(str)); } STC_INLINE void cstr_copy(cstr* self, cstr s) { - cstr_rep_t r = cstr_rep(&s); - cstr_assign_n(self, r.data, r.size); + csview sv = cstr_sv(&s); + cstr_assign_n(self, sv.str, sv.size); } STC_INLINE void cstr_append(cstr* self, const char* str) { cstr_append_n(self, str, strlen(str)); } STC_INLINE void cstr_append_s(cstr* self, cstr s) { - cstr_rep_t r = cstr_rep(&s); - cstr_append_n(self, r.data, r.size); + csview sv = cstr_sv(&s); + cstr_append_n(self, sv.str, sv.size); } STC_INLINE void cstr_replace_n(cstr* self, size_t pos, size_t len, const char* str, size_t n) { @@ -237,8 +244,8 @@ STC_INLINE void cstr_replace(cstr* self, size_t pos, size_t len, const char* str { cstr_replace_n(self, pos, len, str, strlen(str)); } STC_INLINE void cstr_replace_s(cstr* self, size_t pos, size_t len, cstr s) { - cstr_rep_t r = cstr_rep(&s); - cstr_replace_n(self, pos, len, r.data, r.size); + csview sv = cstr_sv(&s); + cstr_replace_n(self, pos, len, sv.str, sv.size); } STC_INLINE void cstr_insert_n(cstr* self, size_t pos, const char* str, size_t n) @@ -248,18 +255,17 @@ STC_INLINE void cstr_insert(cstr* self, size_t pos, const char* str) { cstr_replace_n(self, pos, 0, str, strlen(str)); } STC_INLINE void cstr_insert_s(cstr* self, size_t pos, cstr s) { - cstr_rep_t r = cstr_rep(&s); - cstr_replace_n(self, pos, 0, r.data, r.size); + csview sv = cstr_sv(&s); + cstr_replace_n(self, pos, 0, sv.str, sv.size); } STC_INLINE bool cstr_getline(cstr *self, FILE *fp) { return cstr_getdelim(self, '\n', fp); } -/* container adaptor functions: */ -#define cstr_cmp(xp, yp) strcmp(cstr_str(xp), cstr_str(yp)) -#define cstr_eq(xp, yp) (!cstr_cmp(xp, yp)) -STC_INLINE uint64_t cstr_hash(const cstr *self, size_t dummylen) - { return c_default_hash(cstr_str(self), cstr_size(*self)); } +STC_INLINE uint64_t cstr_hash(const cstr *self, size_t dummylen) { + csview sv = cstr_sv(self); + return c_default_hash(sv.str, sv.size); +} /* -------------------------- IMPLEMENTATION ------------------------- */ #if defined(_i_implement) @@ -332,11 +338,11 @@ STC_DEF void cstr_resize(cstr* self, const size_t size, const char value) { } STC_DEF size_t cstr_find_n(cstr s, const char* needle, const size_t pos, const size_t nmax) { - cstr_rep_t r = cstr_rep(&s); + csview sv = cstr_sv(&s); const size_t nlen = (size_t) strlen(needle); - if (pos > r.size) return cstr_npos; - char* res = c_strnstrn(r.data + pos, needle, r.size, nmax < nlen ? nmax : nlen); - return res ? res - r.data : cstr_npos; + if (pos > sv.size) return cstr_npos; + char* res = c_strnstrn(sv.str + pos, needle, sv.size, nmax < nlen ? nmax : nlen); + return res ? res - sv.str : cstr_npos; } STC_DEF cstr* cstr_assign_n(cstr* self, const char* str, const size_t n) { @@ -401,9 +407,15 @@ cstr_from_replace_all(const char* str, const size_t str_len, STC_DEF void cstr_replace_all(cstr* self, const char* find, const char* repl) { - cstr_rep_t r = cstr_rep(self); - cstr_take(self, cstr_from_replace_all(r.data, r.size, find, strlen(find), - repl, strlen(repl))); + csview sv = cstr_sv(self); + cstr_take(self, cstr_from_replace_all(sv.str, sv.size, find, strlen(find), + repl, strlen(repl))); +} + +STC_DEF cstr +cstr_from_replace_all_sv(csview sv, csview find, csview repl) { + return cstr_from_replace_all(sv.str, sv.size, find.str, find.size, + repl.str, repl.size); } STC_DEF void cstr_erase_n(cstr* self, const size_t pos, size_t n) { diff --git a/include/stc/csview.h b/include/stc/csview.h index 59e853ca..be430a79 100644 --- a/include/stc/csview.h +++ b/include/stc/csview.h @@ -94,11 +94,6 @@ STC_INLINE csview csview_from_s(const cstr* self) STC_INLINE cstr cstr_from_sv(csview sv) { return cstr_from_n(sv.str, sv.size); } -/*STC_INLINE cstr cstr_from_replace_all_sv(csview sv, csview find, csview repl) - { return cstr_from_replace_all(sv.str, sv.size, find.str, find.size, - repl.str, repl.size); }*/ -STC_INLINE csview cstr_to_sv(const cstr* self) - { return c_make(csview){cstr_str(self), cstr_size(*self)}; } STC_INLINE csview cstr_substr(const cstr* self, intptr_t pos, size_t n) { return csview_substr(csview_from_s(self), pos, n); } STC_INLINE csview cstr_slice(const cstr* self, intptr_t p1, intptr_t p2) @@ -127,12 +122,12 @@ STC_INLINE bool cstr_ends_with_sv(cstr s, csview sub) #endif /* ---- Container helper functions ---- */ -STC_INLINE int csview_cmp(const csview* x, const csview* y) { - const size_t m = x->size < y->size ? x->size : y->size; - const int c = memcmp(x->str, y->str, m); - return c ? c : x->size - y->size; - } -#define csview_eq(xp, yp) (!csview_cmp(xp, yp)) +STC_INLINE int csview_cmp(const csview* x, const csview* y) + { return strcmp(x->str, y->str); } + +STC_INLINE bool csview_eq(const csview* x, const csview* y) + { return x->size == y->size && !memcmp(x->str, y->str, x->size); } + STC_INLINE uint64_t csview_hash(const csview *self, size_t sz) { return c_default_hash(self->str, self->size); } diff --git a/include/stc/template.h b/include/stc/template.h index 48881edf..659f6a72 100644 --- a/include/stc/template.h +++ b/include/stc/template.h @@ -106,7 +106,8 @@ #define i_key_bind cstr #define i_keyraw csview #define i_keyfrom cstr_from_sv - #define i_keyto cstr_to_sv + #define i_keyto cstr_sv + #define i_eq csview_eq #ifndef i_tag #define i_tag ssv #endif @@ -197,7 +198,7 @@ #define i_val cstr #define i_valraw csview #define i_valfrom cstr_from_sv - #define i_valto cstr_to_sv + #define i_valto cstr_sv #define i_valdrop cstr_drop #elif defined i_val_arcbox #define i_val_bind i_val_arcbox -- cgit v1.2.3 From 8aeec88bd7f15069a388f7fc8fe0008af4d1ab44 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 24 Apr 2022 20:24:29 +0200 Subject: Fixed unfair comparison; std::move must be used in c++ push_back(). STC has almost identical performance to c++ STL, but STC cstr has 23 chars short strings vs typically 15 for c++ std::string, so STC is faster in this range. --- benchmarks/misc/sso_bench.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/benchmarks/misc/sso_bench.cpp b/benchmarks/misc/sso_bench.cpp index 08444320..5ff54be9 100644 --- a/benchmarks/misc/sso_bench.cpp +++ b/benchmarks/misc/sso_bench.cpp @@ -32,7 +32,7 @@ static void sromutrio(uint64_t seed) { static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz=+-"; static const int BENCHMARK_SIZE = 5000000; -static const int MAX_STRING_LENGTH = 25; +static const int MAX_STRING_LENGTH = 30; using time_point = std::chrono::high_resolution_clock::time_point; @@ -43,7 +43,7 @@ void addRandomString_STD(std::vector& vec, const int length) { p[i] = CHARS[romutrio() & 63]; } s.append(s); - vec.push_back(s); + vec.push_back(std::move(s)); } void addRandomString_STC(svec& vec, const int length) { -- cgit v1.2.3