From bf0bbb610c0efb1d832cf33d325a77b1ad6c1c54 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Mon, 6 Sep 2021 22:09:04 +0200 Subject: Added support for cmap and cset. --- include/stc/ccommon.h | 3 +- include/stc/cdeq.h | 4 +- include/stc/clist.h | 8 +- include/stc/clist_v1.h | 12 +- include/stc/cmap.h | 588 ++++++++++++++++++++++---------------------- include/stc/cpque.h | 4 +- include/stc/cset.h | 14 +- include/stc/csmap.h | 54 ++-- include/stc/csmap_v1.h | 56 ++--- include/stc/forward.h | 32 +-- include/stc/list_test_new.c | 57 ----- include/stc/template.h | 32 +-- include/stc/test_new_list.c | 57 +++++ include/stc/test_new_map.c | 58 +++++ include/stc/test_new_vec.c | 57 +++++ include/stc/vec_test_new.c | 57 ----- 16 files changed, 570 insertions(+), 523 deletions(-) delete mode 100644 include/stc/list_test_new.c create mode 100644 include/stc/test_new_list.c create mode 100644 include/stc/test_new_map.c create mode 100644 include/stc/test_new_vec.c delete mode 100644 include/stc/vec_test_new.c diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index 8cd9802c..a2dd32a6 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -53,8 +53,7 @@ /* Macro overloading feature support based on: https://rextester.com/ONP80107 */ #define c_MACRO_OVERLOAD(name, ...) \ - c_SELECT(name, c_NUM_ARGS(__VA_ARGS__))(__VA_ARGS__) -#define c_SELECT(name, num) c_CONCAT3(name, _, num) + c_PASTE(name ## _, c_NUM_ARGS(__VA_ARGS__))(__VA_ARGS__) #define c_CONCAT(a, b) a##b #define c_PASTE(a, b) c_CONCAT(a, b) #define c_CONCAT3(a, b, c) a##b##c diff --git a/include/stc/cdeq.h b/include/stc/cdeq.h index a5853301..6eca970a 100644 --- a/include/stc/cdeq.h +++ b/include/stc/cdeq.h @@ -55,9 +55,9 @@ STC_INLINE i_VAL cx_memb(_value_clone)(i_VAL val) \ { return i_VALFROM(i_VALTO(&val)); } \ STC_INLINE void cx_memb(_emplace_back)(Self* self, i_VALRAW raw) \ - {cx_memb(_push_back)(self, i_VALFROM(raw)); } \ + { cx_memb(_push_back)(self, i_VALFROM(raw)); } \ STC_INLINE void cx_memb(_emplace_front)(Self* self, i_VALRAW raw) \ - {cx_memb(_push_front)(self, i_VALFROM(raw)); } \ + { cx_memb(_push_front)(self, i_VALFROM(raw)); } \ STC_INLINE void cx_memb(_pop_back)(Self* self) \ {i_VALDEL(&self->data[--_cdeq_rep(self)->size]); } \ STC_INLINE void cx_memb(_pop_front)(Self* self) \ diff --git a/include/stc/clist.h b/include/stc/clist.h index b64eeac5..63633e55 100644 --- a/include/stc/clist.h +++ b/include/stc/clist.h @@ -174,19 +174,19 @@ STC_INLINE Self cx_memb(_init)(void) { return c_make(Self){NULL}; } STC_INLINE bool cx_memb(_empty)(Self cx) { return cx.last == NULL; } STC_INLINE size_t cx_memb(_count)(Self cx) { return _clist_count((const clist_VOID*) &cx); } -STC_INLINE void cx_memb(_clear)(Self* self) {cx_memb(_del)(self); } +STC_INLINE void cx_memb(_clear)(Self* self) { cx_memb(_del)(self); } 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_t* pval) { return i_VALTO(pval); } STC_INLINE i_VAL cx_memb(_value_clone)(i_VAL val) { return i_VALFROM(i_VALTO(&val)); } STC_INLINE void cx_memb(_pop_front)(Self* self) - {cx_memb(_erase_after_)(self, self->last); } + { cx_memb(_erase_after_)(self, self->last); } STC_INLINE cx_iter_t cx_memb(_erase)(Self* self, cx_iter_t it) { return cx_memb(_erase_at)(self, it); } STC_INLINE void cx_memb(_emplace_back)(Self* self, i_VALRAW raw) - {cx_memb(_push_back)(self, i_VALFROM(raw)); } + { cx_memb(_push_back)(self, i_VALFROM(raw)); } STC_INLINE void cx_memb(_emplace_front)(Self* self, i_VALRAW raw) - {cx_memb(_push_front)(self, i_VALFROM(raw)); } + { cx_memb(_push_front)(self, i_VALFROM(raw)); } STC_INLINE cx_iter_t cx_memb(_emplace)(Self* self, cx_iter_t it, i_VALRAW raw) { return cx_memb(_insert)(self, it, i_VALFROM(raw)); } STC_INLINE cx_value_t* cx_memb(_front)(const Self* self) { return &self->last->next->value; } diff --git a/include/stc/clist_v1.h b/include/stc/clist_v1.h index 34544c18..8a3d6cb7 100644 --- a/include/stc/clist_v1.h +++ b/include/stc/clist_v1.h @@ -89,20 +89,20 @@ STC_API size_t _clist_count(const clist_VOID* self); STC_INLINE size_t cx_memb(_count)(Self lst) { return _clist_count((const clist_VOID*) &lst); } \ STC_INLINE i_VAL cx_memb(_value_fromraw)(i_VALRAW raw) { return i_VALFROM(raw); } \ STC_INLINE i_VAL cx_memb(_value_clone)(i_VAL val) { return i_VALFROM(i_VALTO(&val)); } \ - STC_INLINE void cx_memb(_clear)(Self* self) {cx_memb(_del)(self); } \ + STC_INLINE void cx_memb(_clear)(Self* self) { cx_memb(_del)(self); } \ STC_INLINE void cx_memb(_emplace_back)(Self* self, i_VALRAW raw) \ - {cx_memb(_push_back)(self, i_VALFROM(raw)); } \ + { cx_memb(_push_back)(self, i_VALFROM(raw)); } \ STC_INLINE void cx_memb(_emplace_front)(Self* self, i_VALRAW raw) \ - {cx_memb(_push_front)(self, i_VALFROM(raw)); } \ + { cx_memb(_push_front)(self, i_VALFROM(raw)); } \ STC_INLINE cx_value_t* \ cx_memb(_front)(const Self* self) { return &self->last->next->value; } \ STC_INLINE cx_value_t* \ cx_memb(_back)(const Self* self) { return &self->last->value; } \ - STC_INLINE void cx_memb(_pop_front)(Self* self) {cx_memb(_erase_after_)(self, self->last); } \ + STC_INLINE void cx_memb(_pop_front)(Self* self) { cx_memb(_erase_after_)(self, self->last); } \ STC_INLINE void cx_memb(_splice_front)(Self* self, Self* other) \ - {cx_memb(_splice_after)(self, cx_memb(_before_begin)(self), other); } \ + { cx_memb(_splice_after)(self, cx_memb(_before_begin)(self), other); } \ STC_INLINE void cx_memb(_splice_back)(Self* self, Self* other) \ - {cx_memb(_splice_after)(self, cx_memb(_last)(self), other); } \ + { cx_memb(_splice_after)(self, cx_memb(_last)(self), other); } \ \ STC_INLINE cx_iter_t \ cx_memb(_emplace_after)(Self* self, cx_iter_t pos, i_VALRAW raw) { \ diff --git a/include/stc/cmap.h b/include/stc/cmap.h index 39d9fce8..3853bb74 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -20,15 +20,15 @@ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ -#ifndef CMAP_H_INCLUDED -#define CMAP_H_INCLUDED // Unordered set/map - implemented as closed hashing with linear probing and no tombstones. /* -#include #include -using_cmap(mx, int, char); // Map of int -> char +#define i_TAG mx +#define i_KEY int +#define i_VAL char // Map of int -> char +#include int main(void) { c_forvar (cmap_mx m = cmap_mx_init(), cmap_mx_del(&m)) @@ -47,16 +47,36 @@ int main(void) { } } */ + +#ifndef CMAP_H_INCLUDED +#define CMAP_H_INCLUDED #include "ccommon.h" +#include "forward.h" #include #include - -#define KEY_REF_cmap_(vp) (&(vp)->first) #define _cmap_inits {NULL, NULL, 0, 0, 0.85f} -typedef struct {size_t idx; uint_fast8_t hx; } chash_bucket_t; \ +typedef struct { size_t idx; uint_fast8_t hx; } chash_bucket_t; + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) || defined(i_IMP) + +STC_INLINE uint64_t c_default_hash(const void *key, size_t len) { + const uint64_t m = 0xb5ad4eceda1ce2a9; + uint64_t k, h = m + len; + const uint8_t *p = (const uint8_t *)key, *end = p + (len & ~7ull); + for (; p != end; p += 8) {memcpy(&k, p, 8); h ^= m*k; } + switch (len & 7) { + case 7: h ^= (uint64_t) p[6] << 48; + case 6: h ^= (uint64_t) p[5] << 40; + case 5: h ^= (uint64_t) p[4] << 32; + case 4: h ^= (uint64_t) p[3] << 24; + case 3: h ^= (uint64_t) p[2] << 16; + case 2: h ^= (uint64_t) p[1] << 8; + case 1: h ^= (uint64_t) p[0]; h *= m; + } + return h ^ (h >> 15); +} -STC_API uint64_t c_default_hash(const void *data, size_t len); STC_INLINE uint64_t c_string_hash(const char *s) { return c_default_hash(s, strlen(s)); } STC_INLINE uint64_t c_default_hash32(const void* data, size_t ignored) @@ -64,305 +84,283 @@ STC_INLINE uint64_t c_default_hash32(const void* data, size_t ignored) STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored) { return *(const uint64_t *)data * 0xc6a4a7935bd1e99d; } +#endif +#endif // CMAP_H_INCLUDED + +#ifndef i_MODULE +#define i_MODULE cmap +#define cx_MAP_ONLY c_true +#define cx_SET_ONLY c_false +#define cx_keyref(vp) (&(vp)->first) +#endif +#include "template.h" +#ifndef i_FWD +cx_deftypes(_c_chash_types, Self, i_KEY, i_VAL, cx_MAP_ONLY, cx_SET_ONLY); +#endif + +cx_MAP_ONLY( struct cx_value_t { + cx_key_t first; + cx_mapped_t second; +}; ) + +typedef i_KEYRAW cx_rawkey_t; +typedef i_VALRAW cx_memb(_rawmapped_t); +typedef cx_SET_ONLY( i_KEYRAW ) + cx_MAP_ONLY( struct { i_KEYRAW first; + i_VALRAW second; } ) +cx_rawvalue_t; + +STC_API Self cx_memb(_with_capacity)(size_t cap); +STC_API Self cx_memb(_clone)(Self map); +STC_API void cx_memb(_del)(Self* self); +STC_API void cx_memb(_clear)(Self* self); +STC_API void cx_memb(_reserve)(Self* self, size_t capacity); +STC_API chash_bucket_t cx_memb(_bucket_)(const Self* self, const cx_rawkey_t* rkeyptr); +STC_API cx_result_t cx_memb(_insert_entry_)(Self* self, i_KEYRAW rkey); +STC_API void cx_memb(_erase_entry)(Self* self, cx_value_t* val); +cx_MAP_ONLY( + STC_API cx_result_t cx_memb(_insert_or_assign)(Self* self, i_KEY _key, i_VAL _mapped); + STC_API cx_result_t cx_memb(_emplace_or_assign)(Self* self, i_KEYRAW rkey, i_VALRAW rmapped); +) +STC_INLINE Self cx_memb(_init)(void) { return c_make(Self)_cmap_inits; } +STC_INLINE void cx_memb(_shrink_to_fit)(Self* self) { cx_memb(_reserve)(self, self->size); } +STC_INLINE void cx_memb(_max_load_factor)(Self* self, float ml) {self->max_load_factor = ml; } +STC_INLINE bool cx_memb(_empty)(Self m) { return m.size == 0; } +STC_INLINE size_t cx_memb(_size)(Self m) { return m.size; } +STC_INLINE size_t cx_memb(_bucket_count)(Self map) { return map.bucket_count; } +STC_INLINE size_t cx_memb(_capacity)(Self map) + { return (size_t) (map.bucket_count * map.max_load_factor); } +STC_INLINE void cx_memb(_swap)(Self *map1, Self *map2) {c_swap(Self, *map1, *map2); } +STC_INLINE bool cx_memb(_contains)(const Self* self, i_KEYRAW rkey) + { return self->size && self->_hashx[cx_memb(_bucket_)(self, &rkey).idx]; } + +STC_INLINE void +cx_memb(_value_clone)(cx_value_t* _dst, cx_value_t* _val) { + *cx_keyref(_dst) = i_KEYFROM(i_KEYTO(cx_keyref(_val))); + cx_MAP_ONLY( _dst->second = i_VALFROM(i_VALTO(&_val->second)); ) +} + +STC_INLINE cx_rawvalue_t +cx_memb(_value_toraw)(cx_value_t* val) { + return cx_SET_ONLY( i_KEYTO(val) ) + cx_MAP_ONLY( c_make(cx_rawvalue_t){i_KEYTO(&val->first), i_VALTO(&val->second)} ); +} + +STC_INLINE void +cx_memb(_value_del)(cx_value_t* _val) { + i_KEYDEL(cx_keyref(_val)); + cx_MAP_ONLY( i_VALDEL(&_val->second); ) +} - defTypes( _c_chash_types(Self, C, i_KEY, i_VAL); ) \ -\ - MAP_ONLY_##C( struct cx_value_t { \ - cx_key_t first; \ - cx_mapped_t second; \ - }; ) \ -\ - typedef i_KEYRAW cx_rawkey_t; \ - typedef i_VALRAW cx_memb(_rawmapped_t); \ - typedef SET_ONLY_##C( i_KEYRAW ) \ - MAP_ONLY_##C( struct { i_KEYRAW first; \ - i_VALRAW second; } ) \ - cx_rawvalue_t; \ -\ - STC_API Self cx_memb(_with_capacity)(size_t cap); \ - STC_API Self cx_memb(_clone)(Self map); \ - STC_API void cx_memb(_del)(Self* self); \ - STC_API void cx_memb(_clear)(Self* self); \ - STC_API void cx_memb(_reserve)(Self* self, size_t capacity); \ - STC_API chash_bucket_t cx_memb(_bucket_)(const Self* self, const cx_rawkey_t* rkeyptr); \ - STC_API cx_result_t cx_memb(_insert_entry_)(Self* self, i_KEYRAW rkey); \ - STC_API void cx_memb(_erase_entry)(Self* self, cx_value_t* val); \ -\ - STC_INLINE Self cx_memb(_init)(void) { return c_make(Self)_cmap_inits; } \ - STC_INLINE void cx_memb(_shrink_to_fit)(Self* self) {cx_memb(_reserve)(self, self->size); } \ - STC_INLINE void cx_memb(_max_load_factor)(Self* self, float ml) {self->max_load_factor = ml; } \ - STC_INLINE bool cx_memb(_empty)(Self m) { return m.size == 0; } \ - STC_INLINE size_t cx_memb(_size)(Self m) { return m.size; } \ - STC_INLINE size_t cx_memb(_bucket_count)(Self map) { return map.bucket_count; } \ - STC_INLINE size_t cx_memb(_capacity)(Self map) \ - { return (size_t) (map.bucket_count * map.max_load_factor); } \ - STC_INLINE void cx_memb(_swap)(Self *map1, Self *map2) {c_swap(Self, *map1, *map2); } \ - STC_INLINE bool cx_memb(_contains)(const Self* self, i_KEYRAW rkey) \ - { return self->size && self->_hashx[cx_memb(_bucket_)(self, &rkey).idx]; } \ -\ - STC_INLINE void \ - cx_memb(_value_clone)(cx_value_t* _dst, cx_value_t* _val) { \ - *KEY_REF_##C(_dst) = i_KEYFROM(i_KEYTO(KEY_REF_##C(_val))); \ - MAP_ONLY_##C( _dst->second = i_VALFROM(i_VALTO(&_val->second)); ) \ - } \ -\ - STC_INLINE cx_rawvalue_t \ - cx_memb(_value_toraw)(cx_value_t* val) { \ - return SET_ONLY_##C( i_KEYTO(val) ) \ - MAP_ONLY_##C( c_make(cx_rawvalue_t){i_KEYTO(&val->first), i_VALTO(&val->second)} ); \ - } \ -\ - STC_INLINE void \ - cx_memb(_value_del)(cx_value_t* _val) { \ - i_KEYDEL(KEY_REF_##C(_val)); \ - MAP_ONLY_##C( i_VALDEL(&_val->second); ) \ - } \ -\ - STC_INLINE cx_result_t \ - cx_memb(_emplace)(Self* self, i_KEYRAW rkey MAP_ONLY_##C(, i_VALRAW rmapped)) { \ - cx_result_t _res = cx_memb(_insert_entry_)(self, rkey); \ - if (_res.inserted) { \ - *KEY_REF_##C(_res.ref) = i_KEYFROM(rkey); \ - MAP_ONLY_##C(_res.ref->second = i_VALFROM(rmapped);) \ - } \ - return _res; \ - } \ -\ - STC_INLINE void \ - cx_memb(_emplace_items)(Self* self, const cx_rawvalue_t arr[], size_t n) { \ - for (size_t i=0; isecond = _mapped; )} \ - else {i_KEYDEL(&_key); MAP_ONLY_##C( i_VALDEL(&_mapped); )} \ - return _res; \ - } \ -\ - MAP_ONLY_##C( \ - STC_INLINE cx_result_t \ - cx_memb(_insert_or_assign)(Self* self, i_KEY _key, i_VAL _mapped) { \ - cx_result_t _res = cx_memb(_insert_entry_)(self, i_KEYTO(&_key)); \ - if (_res.inserted) _res.ref->first = _key; \ - else {i_KEYDEL(&_key); i_VALDEL(&_res.ref->second); } \ - _res.ref->second = _mapped; return _res; \ - } \ - \ - STC_INLINE cx_result_t \ - cx_memb(_put)(Self* self, i_KEY k, i_VAL m) { /* shorter, like operator[] */ \ - return cx_memb(_insert_or_assign)(self, k, m); \ - } \ - \ - STC_INLINE cx_result_t \ - cx_memb(_emplace_or_assign)(Self* self, i_KEYRAW rkey, i_VALRAW rmapped) { \ - cx_result_t _res = cx_memb(_insert_entry_)(self, rkey); \ - if (_res.inserted) _res.ref->first = i_KEYFROM(rkey); \ - else i_VALDEL(&_res.ref->second); \ - _res.ref->second = i_VALFROM(rmapped); return _res; \ - } \ - \ - STC_INLINE cx_mapped_t* \ - cx_memb(_at)(const Self* self, i_KEYRAW rkey) { \ - chash_bucket_t b = cx_memb(_bucket_)(self, &rkey); \ - return &self->table[b.idx].second; \ - }) \ -\ - STC_INLINE cx_iter_t \ - cx_memb(_find)(const Self* self, i_KEYRAW rkey) { \ - cx_iter_t it = {NULL}; \ - if (self->size == 0) return it; \ - chash_bucket_t b = cx_memb(_bucket_)(self, &rkey); \ - if (*(it._hx = self->_hashx+b.idx)) it.ref = self->table+b.idx; \ - return it; \ - } \ -\ - STC_INLINE cx_value_t* \ - cx_memb(_get)(const Self* self, i_KEYRAW rkey) \ - { return cx_memb(_find)(self, rkey).ref; } \ -\ - STC_INLINE cx_iter_t \ - cx_memb(_begin)(const Self* self) { \ - cx_iter_t it = {self->table, self->_hashx}; \ - if (it._hx) while (*it._hx == 0) ++it.ref, ++it._hx; \ - return it; \ - } \ -\ - STC_INLINE cx_iter_t \ - cx_memb(_end)(const Self* self) \ - { return c_make(cx_iter_t){self->table + self->bucket_count}; } \ -\ - STC_INLINE void \ - cx_memb(_next)(cx_iter_t* it) \ - {while ((++it->ref, *++it->_hx == 0)) ; } \ -\ - STC_INLINE size_t \ - cx_memb(_erase)(Self* self, i_KEYRAW rkey) { \ - if (self->size == 0) return 0; \ - chash_bucket_t b = cx_memb(_bucket_)(self, &rkey); \ - return self->_hashx[b.idx] ? cx_memb(_erase_entry)(self, self->table + b.idx), 1 : 0; \ - } \ -\ - STC_INLINE cx_iter_t \ - cx_memb(_erase_at)(Self* self, cx_iter_t it) { \ - cx_memb(_erase_entry)(self, it.ref); \ - if (*it._hx == 0) cx_memb(_next)(&it); \ - return it; \ - } \ -\ - _c_implement_chash(Self, C, i_KEY, i_VAL, i_EQU, i_HASH, \ - i_VALDEL, i_VALFROM, i_VALTO, i_VALRAW, \ - i_KEYDEL, i_KEYFROM, i_KEYTO, i_KEYRAW) \ - struct stc_trailing_semicolon +STC_INLINE cx_result_t +cx_memb(_emplace)(Self* self, i_KEYRAW rkey cx_MAP_ONLY(, i_VALRAW rmapped)) { + cx_result_t _res = cx_memb(_insert_entry_)(self, rkey); + if (_res.inserted) { + *cx_keyref(_res.ref) = i_KEYFROM(rkey); + cx_MAP_ONLY(_res.ref->second = i_VALFROM(rmapped);) + } + return _res; +} + +STC_INLINE void +cx_memb(_emplace_items)(Self* self, const cx_rawvalue_t arr[], size_t n) { + for (size_t i=0; isecond = _mapped; )} + else { i_KEYDEL(&_key); cx_MAP_ONLY( i_VALDEL(&_mapped); )} + return _res; +} + +STC_INLINE cx_iter_t +cx_memb(_find)(const Self* self, i_KEYRAW rkey) { + cx_iter_t it = {NULL}; + if (self->size == 0) return it; + chash_bucket_t b = cx_memb(_bucket_)(self, &rkey); + if (*(it._hx = self->_hashx+b.idx)) it.ref = self->table+b.idx; + return it; +} + +STC_INLINE cx_value_t* +cx_memb(_get)(const Self* self, i_KEYRAW rkey) + { return cx_memb(_find)(self, rkey).ref; } + +STC_INLINE cx_iter_t +cx_memb(_begin)(const Self* self) { + cx_iter_t it = {self->table, self->_hashx}; + if (it._hx) while (*it._hx == 0) ++it.ref, ++it._hx; + return it; +} + +STC_INLINE cx_iter_t +cx_memb(_end)(const Self* self) + { return c_make(cx_iter_t){self->table + self->bucket_count}; } + +STC_INLINE void +cx_memb(_next)(cx_iter_t* it) + {while ((++it->ref, *++it->_hx == 0)) ; } + +STC_INLINE size_t +cx_memb(_erase)(Self* self, i_KEYRAW rkey) { + if (self->size == 0) return 0; + chash_bucket_t b = cx_memb(_bucket_)(self, &rkey); + return self->_hashx[b.idx] ? cx_memb(_erase_entry)(self, self->table + b.idx), 1 : 0; +} + +STC_INLINE cx_iter_t +cx_memb(_erase_at)(Self* self, cx_iter_t it) { + cx_memb(_erase_entry)(self, it.ref); + if (*it._hx == 0) cx_memb(_next)(&it); + return it; +} /* -------------------------- IMPLEMENTATION ------------------------- */ -#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) || defined(i_IMP) -#ifdef c_umul128 -STC_INLINE size_t fastrange_uint64_t(uint64_t x, uint64_t n) \ - {uint64_t l, h; c_umul128(x, n, &l, &h); return h; } -#endif +//STC_INLINE size_t fastrange_uint64_t(uint64_t x, uint64_t n) +// { uint64_t lo, hi; c_umul128(x, n, &lo, &hi); return hi; } #define fastrange_uint32_t(x, n) ((size_t) (((uint32_t)(x)*(uint64_t)(n)) >> 32)) #define chash_index_(h, entryPtr) ((entryPtr) - (h).table) +STC_DEF Self +cx_memb(_with_capacity)(size_t cap) { + Self h = _cmap_inits; + cx_memb(_reserve)(&h, cap); + return h; +} + +STC_INLINE void cx_memb(_wipe_)(Self* self) { + if (self->size == 0) return; + cx_value_t* e = self->table, *end = e + self->bucket_count; + uint8_t *hx = self->_hashx; + for (; e != end; ++e) if (*hx++) cx_memb(_value_del)(e); +} -#define _c_implement_chash(Self, C, i_KEY, i_VAL, i_EQU, i_HASH, \ - i_VALDEL, i_VALFROM, i_VALTO, i_VALRAW, \ - i_KEYDEL, i_KEYFROM, i_KEYTO, i_KEYRAW) \ - STC_DEF Self \ - cx_memb(_with_capacity)(size_t cap) { \ - Self h = _cmap_inits; \ - cx_memb(_reserve)(&h, cap); \ - return h; \ - } \ -\ - STC_INLINE void cx_memb(_wipe_)(Self* self) { \ - if (self->size == 0) return; \ - cx_value_t* e = self->table, *end = e + self->bucket_count; \ - uint8_t *hx = self->_hashx; \ - for (; e != end; ++e) if (*hx++) cx_memb(_value_del)(e); \ - } \ -\ - STC_DEF void cx_memb(_del)(Self* self) { \ - cx_memb(_wipe_)(self); \ - c_free(self->_hashx); \ - c_free((void *) self->table); \ - } \ -\ - STC_DEF void cx_memb(_clear)(Self* self) { \ - cx_memb(_wipe_)(self); \ - self->size = 0; \ - memset(self->_hashx, 0, self->bucket_count); \ - } \ -\ - STC_DEF chash_bucket_t \ - cx_memb(_bucket_)(const Self* self, const cx_rawkey_t* rkeyptr) { \ - const uint64_t _hash = i_HASH(rkeyptr, sizeof *rkeyptr); \ - uint_fast8_t _hx; size_t _cap = self->bucket_count; \ - chash_bucket_t b = {c_SELECT(fastrange,CMAP_SIZE_T)(_hash, _cap), (uint_fast8_t)(_hash | 0x80)}; \ - const uint8_t* _hashx = self->_hashx; \ - while ((_hx = _hashx[b.idx])) { \ - if (_hx == b.hx) { \ - cx_rawkey_t _raw = i_KEYTO(KEY_REF_##C(self->table + b.idx)); \ - if (i_EQU(&_raw, rkeyptr)) break; \ - } \ - if (++b.idx == _cap) b.idx = 0; \ - } \ - return b; \ - } \ -\ - STC_DEF cx_result_t \ - cx_memb(_insert_entry_)(Self* self, i_KEYRAW rkey) { \ - if (self->size + 1 >= (cx_memb(_size_t)) (self->bucket_count * self->max_load_factor)) \ - cx_memb(_reserve)(self, 8 + (self->size*13ull >> 3)); \ - chash_bucket_t b = cx_memb(_bucket_)(self, &rkey); \ - cx_result_t res = {&self->table[b.idx], !self->_hashx[b.idx]}; \ - if (res.inserted) { \ - self->_hashx[b.idx] = b.hx; \ - ++self->size; \ - } \ - return res; \ - } \ -\ - STC_DEF Self \ - cx_memb(_clone)(Self m) { \ - Self clone = { \ - c_new_n(cx_value_t, m.bucket_count), \ - (uint8_t *) memcpy(c_malloc(m.bucket_count + 1), m._hashx, m.bucket_count + 1), \ - m.size, m.bucket_count, \ - m.max_load_factor \ - }; \ - cx_value_t *e = m.table, *end = e + m.bucket_count, *dst = clone.table; \ - for (uint8_t *hx = m._hashx; e != end; ++hx, ++e, ++dst) \ - if (*hx) cx_memb(_value_clone)(dst, e); \ - return clone; \ - } \ -\ - STC_DEF void \ - cx_memb(_reserve)(Self* self, size_t _newcap) { \ - if (_newcap < self->size) return; \ - size_t _oldcap = self->bucket_count; \ - _newcap = (size_t) (2 + _newcap / self->max_load_factor) | 1; \ - Self _tmp = { \ - c_new_n(cx_value_t, _newcap), \ - (uint8_t *) c_calloc(_newcap + 1, sizeof(uint8_t)), \ - self->size, (cx_memb(_size_t)) _newcap, \ - self->max_load_factor \ - }; \ - /* Rehash: */ \ - _tmp._hashx[_newcap] = 0xff; c_swap(Self, *self, _tmp); \ - cx_value_t* e = _tmp.table, *_slot = self->table; \ - uint8_t* _hashx = self->_hashx; \ - for (size_t i = 0; i < _oldcap; ++i, ++e) \ - if (_tmp._hashx[i]) { \ - cx_rawkey_t _raw = i_KEYTO(KEY_REF_##C(e)); \ - chash_bucket_t b = cx_memb(_bucket_)(self, &_raw); \ - memcpy((void *) &_slot[b.idx], e, sizeof *e); \ - _hashx[b.idx] = (uint8_t) b.hx; \ - } \ - c_free(_tmp._hashx); \ - c_free((void *) _tmp.table); \ - } \ -\ - STC_DEF void \ - cx_memb(_erase_entry)(Self* self, cx_value_t* _val) { \ - size_t i = chash_index_(*self, _val), j = i, k, _cap = self->bucket_count; \ - cx_value_t* _slot = self->table; \ - uint8_t* _hashx = self->_hashx; \ - cx_memb(_value_del)(&_slot[i]); \ - for (;;) { /* delete without leaving tombstone */ \ - if (++j == _cap) j = 0; \ - if (! _hashx[j]) \ - break; \ - cx_rawkey_t _raw = i_KEYTO(KEY_REF_##C(_slot+j)); \ - k = c_SELECT(fastrange,CMAP_SIZE_T)(i_HASH(&_raw, sizeof _raw), _cap); \ - if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ \ - memcpy((void *) &_slot[i], &_slot[j], sizeof *_slot), _hashx[i] = _hashx[j], i = j; \ - } \ - _hashx[i] = 0; \ - --self->size; \ +STC_DEF void cx_memb(_del)(Self* self) { + cx_memb(_wipe_)(self); + c_free(self->_hashx); + c_free((void *) self->table); +} + +STC_DEF void cx_memb(_clear)(Self* self) { + cx_memb(_wipe_)(self); + self->size = 0; + memset(self->_hashx, 0, self->bucket_count); +} + +cx_MAP_ONLY( + STC_DEF cx_result_t + cx_memb(_insert_or_assign)(Self* self, i_KEY _key, i_VAL _mapped) { + cx_result_t _res = cx_memb(_insert_entry_)(self, i_KEYTO(&_key)); + if (_res.inserted) _res.ref->first = _key; + else { i_KEYDEL(&_key); i_VALDEL(&_res.ref->second); } + _res.ref->second = _mapped; return _res; } + STC_DEF cx_result_t + cx_memb(_emplace_or_assign)(Self* self, i_KEYRAW rkey, i_VALRAW rmapped) { + cx_result_t _res = cx_memb(_insert_entry_)(self, rkey); + if (_res.inserted) _res.ref->first = i_KEYFROM(rkey); + else i_VALDEL(&_res.ref->second); + _res.ref->second = i_VALFROM(rmapped); return _res; + } +) -STC_DEF uint64_t c_default_hash(const void *key, size_t len) { - const uint64_t m = 0xb5ad4eceda1ce2a9; - uint64_t k, h = m + len; - const uint8_t *p = (const uint8_t *)key, *end = p + (len & ~7ull); - for (; p != end; p += 8) {memcpy(&k, p, 8); h ^= m*k; } - switch (len & 7) { - case 7: h ^= (uint64_t) p[6] << 48; - case 6: h ^= (uint64_t) p[5] << 40; - case 5: h ^= (uint64_t) p[4] << 32; - case 4: h ^= (uint64_t) p[3] << 24; - case 3: h ^= (uint64_t) p[2] << 16; - case 2: h ^= (uint64_t) p[1] << 8; - case 1: h ^= (uint64_t) p[0]; h *= m; +STC_DEF chash_bucket_t +cx_memb(_bucket_)(const Self* self, const cx_rawkey_t* rkeyptr) { + const uint64_t _hash = i_HASH(rkeyptr, sizeof *rkeyptr); + uint_fast8_t _hx; size_t _cap = self->bucket_count; + chash_bucket_t b = {c_PASTE(fastrange_,MAP_SIZE_T)(_hash, _cap), (uint_fast8_t)(_hash | 0x80)}; + const uint8_t* _hashx = self->_hashx; + while ((_hx = _hashx[b.idx])) { + if (_hx == b.hx) { + cx_rawkey_t _raw = i_KEYTO(cx_keyref(self->table + b.idx)); + if (i_EQU(&_raw, rkeyptr)) break; + } + if (++b.idx == _cap) b.idx = 0; } - return h ^ (h >> 15); + return b; } -#endif -#endif +STC_DEF cx_result_t +cx_memb(_insert_entry_)(Self* self, i_KEYRAW rkey) { + if (self->size + 1 >= (cx_memb(_size_t)) (self->bucket_count * self->max_load_factor)) + cx_memb(_reserve)(self, 8 + (self->size*13ull >> 3)); + chash_bucket_t b = cx_memb(_bucket_)(self, &rkey); + cx_result_t res = {&self->table[b.idx], !self->_hashx[b.idx]}; + if (res.inserted) { + self->_hashx[b.idx] = b.hx; + ++self->size; + } + return res; +} + +STC_DEF Self +cx_memb(_clone)(Self m) { + Self clone = { + c_new_n(cx_value_t, m.bucket_count), + (uint8_t *) memcpy(c_malloc(m.bucket_count + 1), m._hashx, m.bucket_count + 1), + m.size, m.bucket_count, + m.max_load_factor + }; + cx_value_t *e = m.table, *end = e + m.bucket_count, *dst = clone.table; + for (uint8_t *hx = m._hashx; e != end; ++hx, ++e, ++dst) + if (*hx) cx_memb(_value_clone)(dst, e); + return clone; +} + +STC_DEF void +cx_memb(_reserve)(Self* self, size_t _newcap) { + if (_newcap < self->size) return; + size_t _oldcap = self->bucket_count; + _newcap = (size_t) (2 + _newcap / self->max_load_factor) | 1; + Self _tmp = { + c_new_n(cx_value_t, _newcap), + (uint8_t *) c_calloc(_newcap + 1, sizeof(uint8_t)), + self->size, (cx_memb(_size_t)) _newcap, + self->max_load_factor + }; + /* Rehash: */ + _tmp._hashx[_newcap] = 0xff; c_swap(Self, *self, _tmp); + cx_value_t* e = _tmp.table, *_slot = self->table; + uint8_t* _hashx = self->_hashx; + for (size_t i = 0; i < _oldcap; ++i, ++e) + if (_tmp._hashx[i]) { + cx_rawkey_t _raw = i_KEYTO(cx_keyref(e)); + chash_bucket_t b = cx_memb(_bucket_)(self, &_raw); + memcpy((void *) &_slot[b.idx], e, sizeof *e); + _hashx[b.idx] = (uint8_t) b.hx; + } + c_free(_tmp._hashx); + c_free((void *) _tmp.table); +} + +STC_DEF void +cx_memb(_erase_entry)(Self* self, cx_value_t* _val) { + size_t i = chash_index_(*self, _val), j = i, k, _cap = self->bucket_count; + cx_value_t* _slot = self->table; + uint8_t* _hashx = self->_hashx; + cx_memb(_value_del)(&_slot[i]); + for (;;) { /* delete without leaving tombstone */ + if (++j == _cap) j = 0; + if (! _hashx[j]) + break; + cx_rawkey_t _raw = i_KEYTO(cx_keyref(_slot+j)); + k = c_PASTE(fastrange_,MAP_SIZE_T)(i_HASH(&_raw, sizeof _raw), _cap); + if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ + memcpy((void *) &_slot[i], &_slot[j], sizeof *_slot), _hashx[i] = _hashx[j], i = j; + } + _hashx[i] = 0; + --self->size; +} + +#endif // IMPLEMENTATION +#undef cx_keyref +#undef cx_MAP_ONLY +#undef cx_SET_ONLY +#include "template.h" diff --git a/include/stc/cpque.h b/include/stc/cpque.h index 1958628c..102cf0aa 100644 --- a/include/stc/cpque.h +++ b/include/stc/cpque.h @@ -77,11 +77,11 @@ STC_API void cx_memb(_erase_at)(Self* self, size_t idx); \ STC_INLINE \ const cx_value_t* cx_memb(_top)(const Self* self) { return &self->data[0]; } \ - STC_INLINE void cx_memb(_pop)(Self* self) {cx_memb(_erase_at)(self, 0); } \ + STC_INLINE void cx_memb(_pop)(Self* self) { cx_memb(_erase_at)(self, 0); } \ \ STC_API void cx_memb(_push)(Self* self, cx_value_t value); \ STC_INLINE void cx_memb(_emplace)(Self* self, cx_rawvalue_t raw) \ - {cx_memb(_push)(self, ctype##_value_fromraw(raw)); } \ + { cx_memb(_push)(self, ctype##_value_fromraw(raw)); } \ STC_API void cx_memb(_emplace_items)(Self *self, const cx_rawvalue_t arr[], size_t n); \ \ _c_implement_cpque(Self, ctype, i_CMP) \ diff --git a/include/stc/cset.h b/include/stc/cset.h index e1ea8497..aaa42e46 100644 --- a/include/stc/cset.h +++ b/include/stc/cset.h @@ -20,16 +20,14 @@ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ -#ifndef CSET_H_INCLUDED -#define CSET_H_INCLUDED // Unordered set - implemented as closed hashing with linear probing and no tombstones. /* +#define i_TAG sx +#define i_KEY int #include #include -using_cset(sx, int); // Set of int - int main(void) { cset_sx s = cset_sx_init(); cset_sx_insert(&s, 5); @@ -41,8 +39,8 @@ int main(void) { } */ -#define i_CNT cmap -#define KEY_REF_cset(vp) (vp) +#define i_MODULE cset +#define cx_MAP_ONLY c_false +#define cx_SET_ONLY c_true +#define cx_keyref(vp) (vp) #include "cmap.h" - -#endif diff --git a/include/stc/csmap.h b/include/stc/csmap.h index 4437757d..38608991 100644 --- a/include/stc/csmap.h +++ b/include/stc/csmap.h @@ -60,7 +60,7 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; #endif \ - MAP_ONLY_##C( struct cx_value_t { \ + cx_MAP_ONLY( struct cx_value_t { \ cx_key_t first; \ cx_mapped_t second; \ }; ) \ @@ -73,8 +73,8 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; \ typedef i_KEYRAW cx_rawkey_t; \ typedef i_VALRAW cx_memb(_rawmapped_t); \ - typedef SET_ONLY_##C( i_KEYRAW ) \ - MAP_ONLY_##C( struct { i_KEYRAW first; \ + typedef cx_SET_ONLY( i_KEYRAW ) \ + cx_MAP_ONLY( struct { i_KEYRAW first; \ i_VALRAW second; } ) \ cx_rawvalue_t; \ \ @@ -95,7 +95,7 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; STC_INLINE bool cx_memb(_empty)(Self tree) { return _csmap_rep(&tree)->size == 0; } \ STC_INLINE size_t cx_memb(_size)(Self tree) { return _csmap_rep(&tree)->size; } \ STC_INLINE size_t cx_memb(_capacity)(Self tree) { return _csmap_rep(&tree)->cap; } \ - STC_INLINE void cx_memb(_clear)(Self* self) {cx_memb(_del)(self); *self = cx_memb(_init)(); } \ + STC_INLINE void cx_memb(_clear)(Self* self) { cx_memb(_del)(self); *self = cx_memb(_init)(); } \ STC_INLINE void cx_memb(_swap)(Self* a, Self* b) {c_swap(Self, *a, *b); } \ STC_INLINE bool cx_memb(_contains)(const Self* self, i_KEYRAW rkey) \ {cx_iter_t it; return cx_memb(_find_it)(self, rkey, &it) != NULL; } \ @@ -111,18 +111,18 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; \ STC_INLINE cx_rawvalue_t \ cx_memb(_value_toraw)(cx_value_t* val) { \ - return SET_ONLY_##C( i_KEYTO(val) ) \ - MAP_ONLY_##C( c_make(cx_rawvalue_t){i_KEYTO(&val->first), i_VALTO(&val->second)} ); \ + return cx_SET_ONLY( i_KEYTO(val) ) \ + cx_MAP_ONLY( c_make(cx_rawvalue_t){i_KEYTO(&val->first), i_VALTO(&val->second)} ); \ } \ STC_INLINE void \ cx_memb(_value_del)(cx_value_t* val) { \ - i_KEYDEL(KEY_REF_##C(val)); \ - MAP_ONLY_##C( i_VALDEL(&val->second); ) \ + i_KEYDEL(cx_keyref(val)); \ + cx_MAP_ONLY( i_VALDEL(&val->second); ) \ } \ STC_INLINE void \ cx_memb(_value_clone)(cx_value_t* dst, cx_value_t* val) { \ - *KEY_REF_##C(dst) = i_KEYFROM(i_KEYTO(KEY_REF_##C(val))); \ - MAP_ONLY_##C( dst->second = i_VALFROM(i_VALTO(&val->second)); ) \ + *cx_keyref(dst) = i_KEYFROM(i_KEYTO(cx_keyref(val))); \ + cx_MAP_ONLY( dst->second = i_VALFROM(i_VALTO(&val->second)); ) \ } \ \ STC_INLINE cx_iter_t \ @@ -133,30 +133,30 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; } \ \ STC_INLINE cx_result_t \ - cx_memb(_emplace)(Self* self, i_KEYRAW rkey MAP_ONLY_##C(, i_VALRAW rmapped)) { \ + cx_memb(_emplace)(Self* self, i_KEYRAW rkey cx_MAP_ONLY(, i_VALRAW rmapped)) { \ cx_result_t res = cx_memb(_insert_entry_)(self, rkey); \ if (res.inserted) { \ - *KEY_REF_##C(res.ref) = i_KEYFROM(rkey); \ - MAP_ONLY_##C(res.ref->second = i_VALFROM(rmapped);) \ + *cx_keyref(res.ref) = i_KEYFROM(rkey); \ + cx_MAP_ONLY(res.ref->second = i_VALFROM(rmapped);) \ } \ return res; \ } \ \ STC_INLINE void \ cx_memb(_emplace_items)(Self* self, const cx_rawvalue_t arr[], size_t n) { \ - for (size_t i=0; isecond = mapped; )} \ - else {i_KEYDEL(&key); MAP_ONLY_##C( i_VALDEL(&mapped); )} \ + if (res.inserted) {*cx_keyref(res.ref) = key; cx_MAP_ONLY( res.ref->second = mapped; )} \ + else {i_KEYDEL(&key); cx_MAP_ONLY( i_VALDEL(&mapped); )} \ return res; \ } \ \ - MAP_ONLY_##C( \ + cx_MAP_ONLY( \ STC_INLINE cx_result_t \ cx_memb(_insert_or_assign)(Self* self, i_KEY key, i_VAL mapped) { \ cx_result_t res = cx_memb(_insert_entry_)(self, i_KEYTO(&key)); \ @@ -273,7 +273,7 @@ static struct csmap_rep _csmap_sentinel = {0, 0, 0, 0, 0}; cx_node_t *d = out->_d = self->nodes; \ out->_top = 0; \ while (tn) { \ - int c; cx_rawkey_t raw = i_KEYTO(KEY_REF_##C(&d[tn].value)); \ + int c; cx_rawkey_t raw = i_KEYTO(cx_keyref(&d[tn].value)); \ if ((c = i_CMP(&raw, &rkey)) < 0) \ tn = d[tn].link[1]; \ else if (c > 0) \ @@ -340,7 +340,7 @@ static struct csmap_rep _csmap_sentinel = {0, 0, 0, 0, 0}; int c, top = 0, dir = 0; \ while (tx) { \ up[top++] = tx; \ - i_KEYRAW raw = i_KEYTO(KEY_REF_##C(&d[tx].value)); \ + i_KEYRAW raw = i_KEYTO(cx_keyref(&d[tx].value)); \ if ((c = i_CMP(&raw, rkey)) == 0) {res->ref = &d[tx].value; return tn; } \ dir = (c < 0); \ tx = d[tx].link[dir]; \ @@ -370,7 +370,7 @@ static struct csmap_rep _csmap_sentinel = {0, 0, 0, 0, 0}; STC_DEF cx_memb(_size_t) \ cx_memb(_erase_r_)(cx_node_t *d, cx_memb(_size_t) tn, const cx_rawkey_t* rkey, int *erased) { \ if (tn == 0) return 0; \ - i_KEYRAW raw = i_KEYTO(KEY_REF_##C(&d[tn].value)); \ + i_KEYRAW raw = i_KEYTO(cx_keyref(&d[tn].value)); \ cx_memb(_size_t) tx; int c = i_CMP(&raw, rkey); \ if (c != 0) \ d[tn].link[c < 0] = cx_memb(_erase_r_)(d, d[tn].link[c < 0], rkey, erased); \ @@ -381,7 +381,7 @@ static struct csmap_rep _csmap_sentinel = {0, 0, 0, 0, 0}; while (d[tx].link[1]) \ tx = d[tx].link[1]; \ memcpy((void *) &d[tn].value, &d[tx].value, sizeof d[0].value); /* move */ \ - raw = i_KEYTO(KEY_REF_##C(&d[tn].value)); \ + raw = i_KEYTO(cx_keyref(&d[tn].value)); \ d[tn].link[0] = cx_memb(_erase_r_)(d, d[tn].link[0], &raw, erased); \ } else { /* unlink node */ \ tx = tn; \ @@ -414,9 +414,9 @@ static struct csmap_rep _csmap_sentinel = {0, 0, 0, 0, 0}; \ STC_DEF cx_iter_t \ cx_memb(_erase_at)(Self* self, cx_iter_t it) { \ - cx_rawkey_t raw = i_KEYTO(KEY_REF_##C(it.ref)), nxt; \ + cx_rawkey_t raw = i_KEYTO(cx_keyref(it.ref)), nxt; \ cx_memb(_next)(&it); \ - if (it.ref) nxt = i_KEYTO(KEY_REF_##C(it.ref)); \ + if (it.ref) nxt = i_KEYTO(cx_keyref(it.ref)); \ cx_memb(_erase)(self, raw); \ if (it.ref) cx_memb(_find_it)(self, nxt, &it); \ return it; \ @@ -426,11 +426,11 @@ static struct csmap_rep _csmap_sentinel = {0, 0, 0, 0, 0}; cx_memb(_erase_range)(Self* self, cx_iter_t it1, cx_iter_t it2) { \ if (!it2.ref) { while (it1.ref) it1 = cx_memb(_erase_at)(self, it1); \ return it1; } \ - cx_key_t k1 = *KEY_REF_##C(it1.ref), k2 = *KEY_REF_##C(it2.ref); \ + cx_key_t k1 = *cx_keyref(it1.ref), k2 = *cx_keyref(it2.ref); \ cx_rawkey_t r1 = i_KEYTO(&k1); \ for (;;) { \ if (memcmp(&k1, &k2, sizeof k1) == 0) return it1; \ - cx_memb(_next)(&it1); k1 = *KEY_REF_##C(it1.ref); \ + cx_memb(_next)(&it1); k1 = *cx_keyref(it1.ref); \ cx_memb(_erase)(self, r1); \ cx_memb(_find_it)(self, (r1 = i_KEYTO(&k1)), &it1); \ } \ diff --git a/include/stc/csmap_v1.h b/include/stc/csmap_v1.h index 2fb1093a..e5f35944 100644 --- a/include/stc/csmap_v1.h +++ b/include/stc/csmap_v1.h @@ -53,7 +53,7 @@ int main(void) { #define KEY_REF_csmap_(vp) (&(vp)->first) #define _c_aatree_complete_types(Self, C) \ - MAP_ONLY_##C( struct cx_value_t { \ + cx_MAP_ONLY( struct cx_value_t { \ cx_key_t first; \ cx_mapped_t second; \ }; ) \ @@ -71,8 +71,8 @@ int main(void) { \ typedef i_KEYRAW cx_rawkey_t; \ typedef i_VALRAW cx_memb(_rawmapped_t); \ - typedef SET_ONLY_##C( cx_rawkey_t ) \ - MAP_ONLY_##C( struct { cx_rawkey_t first; \ + typedef cx_SET_ONLY( cx_rawkey_t ) \ + cx_MAP_ONLY( struct { cx_rawkey_t first; \ cx_memb(_rawmapped_t) second; } ) \ cx_rawvalue_t; \ \ @@ -91,10 +91,10 @@ int main(void) { \ STC_INLINE bool cx_memb(_empty)(Self cx) { return cx.size == 0; } \ STC_INLINE size_t cx_memb(_size)(Self cx) { return cx.size; } \ - STC_INLINE void cx_memb(_del)(Self* self) {cx_memb(_del_r_)(self->root); } \ - STC_INLINE void cx_memb(_clear)(Self* self) {cx_memb(_del)(self); *self = cx_memb(_init)(); } \ + STC_INLINE void cx_memb(_del)(Self* self) { cx_memb(_del_r_)(self->root); } \ + STC_INLINE void cx_memb(_clear)(Self* self) { cx_memb(_del)(self); *self = cx_memb(_init)(); } \ STC_INLINE void cx_memb(_swap)(Self* a, Self* b) {c_swap(Self, *a, *b); } \ - STC_INLINE Self cx_memb(_clone)(Self cx) { return c_make(Self){cx_memb(_clone_r_)(cx.root), cx.size}; } \ + STC_INLINE Self cx_memb(_clone)(Self cx) { return c_make(Self){ cx_memb(_clone_r_)(cx.root), cx.size}; } \ STC_INLINE cx_iter_t cx_memb(_find)(const Self* self, i_KEYRAW rkey) \ {cx_iter_t it; cx_memb(_find_it)(self, rkey, &it); return it; } \ STC_INLINE bool cx_memb(_contains)(const Self* self, i_KEYRAW rkey) \ @@ -104,41 +104,41 @@ int main(void) { \ STC_INLINE void \ cx_memb(_value_del)(cx_value_t* val) { \ - i_KEYDEL(KEY_REF_##C(val)); \ - MAP_ONLY_##C( i_VALDEL(&val->second); ) \ + i_KEYDEL(cx_keyref(val)); \ + cx_MAP_ONLY( i_VALDEL(&val->second); ) \ } \ \ STC_INLINE void \ cx_memb(_value_clone)(cx_value_t* dst, cx_value_t* val) { \ - *KEY_REF_##C(dst) = i_KEYFROM(i_KEYTO(KEY_REF_##C(val))); \ - MAP_ONLY_##C( dst->second = i_VALFROM(i_VALTO(&val->second)); ) \ + *cx_keyref(dst) = i_KEYFROM(i_KEYTO(cx_keyref(val))); \ + cx_MAP_ONLY( dst->second = i_VALFROM(i_VALTO(&val->second)); ) \ } \ \ STC_INLINE cx_result_t \ - cx_memb(_emplace)(Self* self, i_KEYRAW rkey MAP_ONLY_##C(, i_VALRAW rmapped)) { \ + cx_memb(_emplace)(Self* self, i_KEYRAW rkey cx_MAP_ONLY(, i_VALRAW rmapped)) { \ cx_result_t res = cx_memb(_insert_entry_)(self, rkey); \ if (res.inserted) { \ - *KEY_REF_##C(res.ref) = i_KEYFROM(rkey); \ - MAP_ONLY_##C(res.ref->second = i_VALFROM(rmapped);) \ + *cx_keyref(res.ref) = i_KEYFROM(rkey); \ + cx_MAP_ONLY(res.ref->second = i_VALFROM(rmapped);) \ } \ return res; \ } \ \ STC_INLINE void \ cx_memb(_emplace_items)(Self* self, const cx_rawvalue_t arr[], size_t n) { \ - for (size_t i=0; isecond = mapped; )} \ - else {i_KEYDEL(&key); MAP_ONLY_##C( i_VALDEL(&mapped); )} \ + if (res.inserted) {*cx_keyref(res.ref) = key; cx_MAP_ONLY( res.ref->second = mapped; )} \ + else {i_KEYDEL(&key); cx_MAP_ONLY( i_VALDEL(&mapped); )} \ return res; \ } \ \ - MAP_ONLY_##C( \ + cx_MAP_ONLY( \ STC_INLINE cx_result_t \ cx_memb(_insert_or_assign)(Self* self, i_KEY key, i_VAL mapped) { \ cx_result_t res = cx_memb(_insert_entry_)(self, i_KEYTO(&key)); \ @@ -231,7 +231,7 @@ static csmap_SENTINEL_node_t _aatree_sentinel = {&_aatree_sentinel, &_aatree_sen cx_node_t *tn = self->root; \ out->_top = 0; \ while (tn->level) { \ - int c; cx_rawkey_t rx = i_KEYTO(KEY_REF_##C(&tn->value)); \ + int c; cx_rawkey_t rx = i_KEYTO(cx_keyref(&tn->value)); \ if ((c = i_CMP(&rx, &rkey)) < 0) tn = tn->link[1]; \ else if (c > 0) {out->_st[out->_top++] = tn; tn = tn->link[0]; } \ else {out->_tn = tn->link[1]; return (out->ref = &tn->value); } \ @@ -295,7 +295,7 @@ static csmap_SENTINEL_node_t _aatree_sentinel = {&_aatree_sentinel, &_aatree_sen int c, top = 0, dir = 0; \ while (tx->level) { \ up[top++] = tx; \ - cx_rawkey_t r = i_KEYTO(KEY_REF_##C(&tx->value)); \ + cx_rawkey_t r = i_KEYTO(cx_keyref(&tx->value)); \ if (!(c = i_CMP(&r, rkey))) {res->ref = &tx->value; return tn; } \ tx = tx->link[(dir = (c < 0))]; \ } \ @@ -325,18 +325,18 @@ static csmap_SENTINEL_node_t _aatree_sentinel = {&_aatree_sentinel, &_aatree_sen cx_memb(_erase_r_)(cx_node_t *tn, const cx_rawkey_t* rkey, int *erased) { \ if (tn->level == 0) \ return tn; \ - cx_rawkey_t raw = i_KEYTO(KEY_REF_##C(&tn->value)); \ + cx_rawkey_t raw = i_KEYTO(cx_keyref(&tn->value)); \ cx_node_t *tx; int c = i_CMP(&raw, rkey); \ if (c != 0) \ tn->link[c < 0] = cx_memb(_erase_r_)(tn->link[c < 0], rkey, erased); \ else { \ - if (!*erased) {cx_memb(_value_del)(&tn->value); *erased = 1; } \ + if (!*erased) { cx_memb(_value_del)(&tn->value); *erased = 1; } \ if (tn->link[0]->level && tn->link[1]->level) { \ tx = tn->link[0]; \ while (tx->link[1]->level) \ tx = tx->link[1]; \ tn->value = tx->value; \ - raw = i_KEYTO(KEY_REF_##C(&tn->value)); \ + raw = i_KEYTO(cx_keyref(&tn->value)); \ tn->link[0] = cx_memb(_erase_r_)(tn->link[0], &raw, erased); \ } else { \ tx = tn; \ @@ -357,9 +357,9 @@ static csmap_SENTINEL_node_t _aatree_sentinel = {&_aatree_sentinel, &_aatree_sen } \ STC_DEF cx_iter_t \ cx_memb(_erase_at)(Self* self, cx_iter_t it) { \ - cx_rawkey_t raw = i_KEYTO(KEY_REF_##C(it.ref)), nxt; \ + cx_rawkey_t raw = i_KEYTO(cx_keyref(it.ref)), nxt; \ cx_memb(_next)(&it); \ - if (it.ref) nxt = i_KEYTO(KEY_REF_##C(it.ref)); \ + if (it.ref) nxt = i_KEYTO(cx_keyref(it.ref)); \ cx_memb(_erase)(self, raw); \ if (it.ref) cx_memb(_find_it)(self, nxt, &it); \ return it; \ @@ -369,11 +369,11 @@ static csmap_SENTINEL_node_t _aatree_sentinel = {&_aatree_sentinel, &_aatree_sen cx_memb(_erase_range)(Self* self, cx_iter_t it1, cx_iter_t it2) { \ if (!it2.ref) { while (it1.ref) it1 = cx_memb(_erase_at)(self, it1); \ return it1; } \ - cx_key_t k1 = *KEY_REF_##C(it1.ref), k2 = *KEY_REF_##C(it2.ref); \ + cx_key_t k1 = *cx_keyref(it1.ref), k2 = *cx_keyref(it2.ref); \ cx_rawkey_t r1 = i_KEYTO(&k1); \ for (;;) { \ if (memcmp(&k1, &k2, sizeof k1) == 0) return it1; \ - cx_memb(_next)(&it1); k1 = *KEY_REF_##C(it1.ref); \ + cx_memb(_next)(&it1); k1 = *cx_keyref(it1.ref); \ cx_memb(_erase)(self, r1); \ cx_memb(_find_it)(self, (r1 = i_KEYTO(&k1)), &it1); \ } \ diff --git a/include/stc/forward.h b/include/stc/forward.h index 2c904aa7..be05108a 100644 --- a/include/stc/forward.h +++ b/include/stc/forward.h @@ -27,29 +27,21 @@ #define forward_carray3(TAG, VAL) _c_carray3_types(carray2##TAG, VAL) #define forward_cdeq(TAG, VAL) _c_cdeq_types(cdeq_##TAG, VAL) #define forward_clist(TAG, VAL) _c_clist_types(clist_##TAG, VAL) -#define forward_cmap(TAG, KEY, VAL) _c_chash_types(csmap_##TAG, cmap, KEY, VAL) -#define forward_csmap(TAG, KEY, VAL) _c_aatree_types(csmap_##TAG, csmap, KEY, VAL) -#define forward_cset(TAG, KEY) _c_chash_types(cset_##TAG, cset, KEY, KEY) -#define forward_csset(TAG, KEY) _c_aatree_types(csset_##TAG, csset, KEY, KEY) +#define forward_cmap(TAG, KEY, VAL) _c_chash_types(cmap_##TAG, KEY, VAL, c_true, c_false) +#define forward_csmap(TAG, KEY, VAL) _c_aatree_types(csmap_##TAG, KEY, VAL, c_true, c_false) +#define forward_cset(TAG, KEY) _c_chash_types(cset_##TAG, cset, KEY, KEY, c_false, c_true) +#define forward_csset(TAG, KEY) _c_aatree_types(csset_##TAG, KEY, KEY, c_false, c_true) #define forward_csptr(TAG, VAL) _csptr_types(csptr_##TAG, VAL) #define forward_cpque(TAG, ctype) _c_cpque_types(cpque_##TAG, ctype) #define forward_cqueue(TAG, ctype) _c_cqueue_types(cqueue_##TAG, ctype) #define forward_cstack(TAG, ctype) _c_cstack_types(cstack_##TAG, ctype) #define forward_cvec(TAG, VAL) _c_cvec_types(cvec_##TAG, VAL) -#define SET_ONLY_cmap_(...) -#define MAP_ONLY_cmap_(...) __VA_ARGS__ -#define SET_ONLY_cset_(...) __VA_ARGS__ -#define MAP_ONLY_cset_(...) - -#define SET_ONLY_csmap_(...) -#define MAP_ONLY_csmap_(...) __VA_ARGS__ -#define SET_ONLY_csset_(...) __VA_ARGS__ -#define MAP_ONLY_csset_(...) - #ifndef MAP_SIZE_T #define MAP_SIZE_T uint32_t #endif +#define c_true(...) __VA_ARGS__ +#define c_false(...) #define _c_carray2_types(SELF, VAL) \ typedef VAL SELF##_value_t; \ @@ -79,13 +71,13 @@ SELF##_node_t *last; \ } SELF -#define _c_chash_types(SELF, C, KEY, VAL) \ +#define _c_chash_types(SELF, KEY, VAL, MAP_ONLY, SET_ONLY) \ typedef KEY SELF##_key_t; \ typedef VAL SELF##_mapped_t; \ typedef MAP_SIZE_T SELF##_size_t; \ \ - typedef SET_ONLY_##C( SELF##_key_t ) \ - MAP_ONLY_##C( struct SELF##_value_t ) \ + typedef SET_ONLY( SELF##_key_t ) \ + MAP_ONLY( struct SELF##_value_t ) \ SELF##_value_t; \ \ typedef struct { \ @@ -105,13 +97,13 @@ float max_load_factor; \ } SELF -#define _c_aatree_types(SELF, C, KEY, VAL) \ +#define _c_aatree_types(SELF, KEY, VAL, MAP_ONLY, SET_ONLY) \ typedef KEY SELF##_key_t; \ typedef VAL SELF##_mapped_t; \ typedef MAP_SIZE_T SELF##_size_t; \ \ - typedef SET_ONLY_##C( SELF##_key_t ) \ - MAP_ONLY_##C( struct SELF##_value_t ) \ + typedef SET_ONLY( SELF##_key_t ) \ + MAP_ONLY( struct SELF##_value_t ) \ SELF##_value_t; \ \ typedef struct { \ diff --git a/include/stc/list_test_new.c b/include/stc/list_test_new.c deleted file mode 100644 index 83f6107c..00000000 --- a/include/stc/list_test_new.c +++ /dev/null @@ -1,57 +0,0 @@ -#include "cstr.h" -#include "forward.h" - -forward_clist(i32, int); -forward_clist(pnt, struct Point); - -struct MyStruct { - clist_i32 intlst; - clist_pnt pntlst; -} typedef MyStruct; - - -#define f_TAG i32 -#define i_VAL int -#include "clist.h" - -struct Point { int x, y; } typedef Point; -int point_compare(const Point* a, const Point* b) { - int c = c_default_compare(&a->x, &b->x); - return c ? c : c_default_compare(&a->y, &b->y); -} -#define f_TAG pnt -#define i_VAL Point -#define i_CMP point_compare -#include "clist.h" - -#define i_VAL float -#include "clist.h" - -#define i_VAL_str -#include "clist.h" - - -int main() -{ - clist_i32 lst = clist_i32_init(); - clist_i32_push_back(&lst, 123); - clist_i32_del(&lst); - - clist_float flst = clist_float_init(); - clist_float_push_back(&flst, 123.3); - clist_float_del(&flst); - - clist_pnt plst = clist_pnt_init(); - clist_pnt_push_back(&plst, (Point){42, 14}); - clist_pnt_push_back(&plst, (Point){32, 94}); - clist_pnt_push_back(&plst, (Point){62, 81}); - clist_pnt_sort(&plst); - c_foreach (i, clist_pnt, plst) - printf(" (%d %d)", i.ref->x, i.ref->y); - puts(""); - clist_pnt_del(&plst); - - clist_str slst = clist_str_init(); - clist_str_emplace_back(&slst, "Hello, friend"); - clist_str_del(&slst); -} \ No newline at end of file diff --git a/include/stc/template.h b/include/stc/template.h index c601d359..0aabed0b 100644 --- a/include/stc/template.h +++ b/include/stc/template.h @@ -25,20 +25,20 @@ #ifndef STC_TEMPLATE_H_INCLUDED #define STC_TEMPLATE_H_INCLUDED -#define cx_memb(name) c_PASTE(Self, name) -#define Self c_PASTE3(i_MODULE, _, i_TAG) -// typedef container types defined in forward.h -#define cx_deftypes(macro, SELF, ...) macro(SELF, __VA_ARGS__) - -#define cx_value_t cx_memb(_value_t) -#define cx_key_t cx_memb(_key_t) -#define cx_mapped_t cx_memb(_mapped_t) -#define cx_rawvalue_t cx_memb(_rawvalue_t) -#define cx_rawkey_t cx_memb(_rawkey_t) -#define cx_rawmapped_t cx_memb(_rawmapped_t) -#define cx_iter_t cx_memb(_iter_t) -#define cx_result_t cx_memb(_result_t) -#define cx_node_t cx_memb(_node_t) + #define cx_memb(name) c_PASTE(Self, name) + #define Self c_PASTE3(i_MODULE, _, i_TAG) + // typedef container types defined in forward.h + #define cx_deftypes(macro, SELF, ...) macro(SELF, __VA_ARGS__) + + #define cx_value_t cx_memb(_value_t) + #define cx_key_t cx_memb(_key_t) + #define cx_mapped_t cx_memb(_mapped_t) + #define cx_rawvalue_t cx_memb(_rawvalue_t) + #define cx_rawkey_t cx_memb(_rawkey_t) + #define cx_rawmapped_t cx_memb(_rawmapped_t) + #define cx_iter_t cx_memb(_iter_t) + #define cx_result_t cx_memb(_result_t) + #define cx_node_t cx_memb(_node_t) #endif #if defined f_TAG @@ -66,7 +66,9 @@ #define i_VALTO cstr_str #define i_VALRAW const char* #endif - +#if defined i_KEY && !defined i_VAL + #define i_VAL i_KEY +#endif #if !defined i_TAG && defined i_KEY_str #define i_TAG str #elif !defined i_TAG && defined i_KEY diff --git a/include/stc/test_new_list.c b/include/stc/test_new_list.c new file mode 100644 index 00000000..83f6107c --- /dev/null +++ b/include/stc/test_new_list.c @@ -0,0 +1,57 @@ +#include "cstr.h" +#include "forward.h" + +forward_clist(i32, int); +forward_clist(pnt, struct Point); + +struct MyStruct { + clist_i32 intlst; + clist_pnt pntlst; +} typedef MyStruct; + + +#define f_TAG i32 +#define i_VAL int +#include "clist.h" + +struct Point { int x, y; } typedef Point; +int point_compare(const Point* a, const Point* b) { + int c = c_default_compare(&a->x, &b->x); + return c ? c : c_default_compare(&a->y, &b->y); +} +#define f_TAG pnt +#define i_VAL Point +#define i_CMP point_compare +#include "clist.h" + +#define i_VAL float +#include "clist.h" + +#define i_VAL_str +#include "clist.h" + + +int main() +{ + clist_i32 lst = clist_i32_init(); + clist_i32_push_back(&lst, 123); + clist_i32_del(&lst); + + clist_float flst = clist_float_init(); + clist_float_push_back(&flst, 123.3); + clist_float_del(&flst); + + clist_pnt plst = clist_pnt_init(); + clist_pnt_push_back(&plst, (Point){42, 14}); + clist_pnt_push_back(&plst, (Point){32, 94}); + clist_pnt_push_back(&plst, (Point){62, 81}); + clist_pnt_sort(&plst); + c_foreach (i, clist_pnt, plst) + printf(" (%d %d)", i.ref->x, i.ref->y); + puts(""); + clist_pnt_del(&plst); + + clist_str slst = clist_str_init(); + clist_str_emplace_back(&slst, "Hello, friend"); + clist_str_del(&slst); +} \ No newline at end of file diff --git a/include/stc/test_new_map.c b/include/stc/test_new_map.c new file mode 100644 index 00000000..4c1c7a0a --- /dev/null +++ b/include/stc/test_new_map.c @@ -0,0 +1,58 @@ +#include "cstr.h" +#include "forward.h" + +forward_cmap(pnt, struct Point, int); + +struct MyStruct { + cmap_pnt pntmap; + cstr name; +} typedef MyStruct; + + +#define i_KEY int +#define i_VAL int +#include "cmap.h" + +struct Point { int x, y; } typedef Point; +int point_compare(const Point* a, const Point* b) { + int c = c_default_compare(&a->x, &b->x); + return c ? c : c_default_compare(&a->y, &b->y); +} +#define f_TAG pnt +#define i_KEY Point +#define i_VAL int +#define i_CMP point_compare +#include "cmap.h" + +#define i_KEY_str +#define i_VAL_str +#include "cmap.h" + + +#define i_KEY_str +#include "cset.h" + + +int main() +{ + cmap_int map = cmap_int_init(); + cmap_int_insert(&map, 123, 321); + cmap_int_del(&map); + + cmap_pnt pmap = cmap_pnt_init(); + cmap_pnt_insert(&pmap, (Point){42, 14}, 1); + cmap_pnt_insert(&pmap, (Point){32, 94}, 2); + cmap_pnt_insert(&pmap, (Point){62, 81}, 3); + c_foreach (i, cmap_pnt, pmap) + printf(" (%d,%d: %d)", i.ref->first.x, i.ref->first.y, i.ref->second); + puts(""); + cmap_pnt_del(&pmap); + + cmap_str smap = cmap_str_init(); + cmap_str_emplace(&smap, "Hello, friend", "this is the mapped value"); + cmap_str_del(&smap); + + cset_str sset = cset_str_init(); + cset_str_emplace(&sset, "Hello, friend"); + cset_str_del(&sset); + } \ No newline at end of file diff --git a/include/stc/test_new_vec.c b/include/stc/test_new_vec.c new file mode 100644 index 00000000..c64f633c --- /dev/null +++ b/include/stc/test_new_vec.c @@ -0,0 +1,57 @@ +#include "cstr.h" +#include "forward.h" + +forward_cvec(i32, int); +forward_cvec(pnt, struct Point); + +struct MyStruct { + cvec_i32 intvec; + cvec_pnt pntvec; +} typedef MyStruct; + + +#define f_TAG i32 +#define i_VAL int +#include "cvec.h" + +struct Point { int x, y; } typedef Point; +int point_compare(const Point* a, const Point* b) { + int c = c_default_compare(&a->x, &b->x); + return c ? c : c_default_compare(&a->y, &b->y); +} +#define f_TAG pnt +#define i_VAL Point +#define i_CMP point_compare +#include "cvec.h" + +#define i_VAL float +#include "cvec.h" + +#define i_VAL_str +#include "cvec.h" + + +int main() +{ + cvec_i32 vec = cvec_i32_init(); + cvec_i32_push_back(&vec, 123); + cvec_i32_del(&vec); + + cvec_float fvec = cvec_float_init(); + cvec_float_push_back(&fvec, 123.3); + cvec_float_del(&fvec); + + cvec_pnt pvec = cvec_pnt_init(); + cvec_pnt_push_back(&pvec, (Point){42, 14}); + cvec_pnt_push_back(&pvec, (Point){32, 94}); + cvec_pnt_push_back(&pvec, (Point){62, 81}); + cvec_pnt_sort(&pvec); + c_foreach (i, cvec_pnt, pvec) + printf(" (%d %d)", i.ref->x, i.ref->y); + puts(""); + cvec_pnt_del(&pvec); + + cvec_str svec = cvec_str_init(); + cvec_str_emplace_back(&svec, "Hello, friend"); + cvec_str_del(&svec); +} \ No newline at end of file diff --git a/include/stc/vec_test_new.c b/include/stc/vec_test_new.c deleted file mode 100644 index c64f633c..00000000 --- a/include/stc/vec_test_new.c +++ /dev/null @@ -1,57 +0,0 @@ -#include "cstr.h" -#include "forward.h" - -forward_cvec(i32, int); -forward_cvec(pnt, struct Point); - -struct MyStruct { - cvec_i32 intvec; - cvec_pnt pntvec; -} typedef MyStruct; - - -#define f_TAG i32 -#define i_VAL int -#include "cvec.h" - -struct Point { int x, y; } typedef Point; -int point_compare(const Point* a, const Point* b) { - int c = c_default_compare(&a->x, &b->x); - return c ? c : c_default_compare(&a->y, &b->y); -} -#define f_TAG pnt -#define i_VAL Point -#define i_CMP point_compare -#include "cvec.h" - -#define i_VAL float -#include "cvec.h" - -#define i_VAL_str -#include "cvec.h" - - -int main() -{ - cvec_i32 vec = cvec_i32_init(); - cvec_i32_push_back(&vec, 123); - cvec_i32_del(&vec); - - cvec_float fvec = cvec_float_init(); - cvec_float_push_back(&fvec, 123.3); - cvec_float_del(&fvec); - - cvec_pnt pvec = cvec_pnt_init(); - cvec_pnt_push_back(&pvec, (Point){42, 14}); - cvec_pnt_push_back(&pvec, (Point){32, 94}); - cvec_pnt_push_back(&pvec, (Point){62, 81}); - cvec_pnt_sort(&pvec); - c_foreach (i, cvec_pnt, pvec) - printf(" (%d %d)", i.ref->x, i.ref->y); - puts(""); - cvec_pnt_del(&pvec); - - cvec_str svec = cvec_str_init(); - cvec_str_emplace_back(&svec, "Hello, friend"); - cvec_str_del(&svec); -} \ No newline at end of file -- cgit v1.2.3