diff options
Diffstat (limited to 'include/stc/cmap.h')
| -rw-r--r-- | include/stc/cmap.h | 458 |
1 files changed, 223 insertions, 235 deletions
diff --git a/include/stc/cmap.h b/include/stc/cmap.h index 14782b71..c069fbd8 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -47,43 +47,32 @@ int main(void) { cmap_ichar_drop(&m); } */ -#include "ccommon.h" +#include "priv/linkage.h" #ifndef CMAP_H_INCLUDED +#include "ccommon.h" #include "forward.h" #include <stdlib.h> #include <string.h> -typedef struct { int64_t idx; uint8_t hx; } chash_bucket_t; +struct chash_slot { uint8_t hashx; }; #endif // CMAP_H_INCLUDED #ifndef _i_prefix -#define _i_prefix cmap_ -#endif -#ifdef _i_isset - #define _i_MAP_ONLY c_false - #define _i_SET_ONLY c_true - #define _i_keyref(vp) (vp) -#else + #define _i_prefix cmap_ #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 -#ifndef i_max_load_factor - #define i_max_load_factor 0.85f -#endif -#ifndef i_ssize - #define i_ssize int32_t - #define _i_size intptr_t - #define _i_expandby 1 #else - #define _i_expandby 2 - #define _i_size i_ssize + #define _i_isset + #define _i_MAP_ONLY c_false + #define _i_SET_ONLY c_true + #define _i_keyref(vp) (vp) #endif +#define _i_ishash #include "priv/template.h" #ifndef i_is_forward - _cx_deftypes(_c_chash_types, _cx_self, i_key, i_val, i_ssize, _i_MAP_ONLY, _i_SET_ONLY); + _cx_DEFTYPES(_c_chash_types, _cx_Self, i_key, i_val, _i_MAP_ONLY, _i_SET_ONLY); #endif _i_MAP_ONLY( struct _cx_value { @@ -92,61 +81,61 @@ _i_MAP_ONLY( struct _cx_value { }; ) typedef i_keyraw _cx_keyraw; -typedef i_valraw _cx_memb(_rmapped); +typedef i_valraw _cx_MEMB(_rmapped); typedef _i_SET_ONLY( i_keyraw ) _i_MAP_ONLY( struct { i_keyraw first; i_valraw second; } ) _cx_raw; -STC_API _cx_self _cx_memb(_with_capacity)(_i_size cap); +STC_API _cx_Self _cx_MEMB(_with_capacity)(intptr_t cap); #if !defined i_no_clone -STC_API _cx_self _cx_memb(_clone)(_cx_self map); +STC_API _cx_Self _cx_MEMB(_clone)(_cx_Self map); #endif -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, _i_size capacity); -STC_API chash_bucket_t _cx_memb(_bucket_)(const _cx_self* self, const _cx_keyraw* rkeyptr); -STC_API _cx_result _cx_memb(_insert_entry_)(_cx_self* self, _cx_keyraw rkey); -STC_API void _cx_memb(_erase_entry)(_cx_self* self, _cx_value* val); - -STC_INLINE _cx_self _cx_memb(_init)(void) { _cx_self map = {0}; return map; } -STC_INLINE void _cx_memb(_shrink_to_fit)(_cx_self* self) { _cx_memb(_reserve)(self, self->size); } -STC_INLINE float _cx_memb(_max_load_factor)(const _cx_self* self) { return (float)(i_max_load_factor); } -STC_INLINE bool _cx_memb(_empty)(const _cx_self* map) { return !map->size; } -STC_INLINE _i_size _cx_memb(_size)(const _cx_self* map) { return map->size; } -STC_INLINE _i_size _cx_memb(_bucket_count)(_cx_self* map) { return map->bucket_count; } -STC_INLINE _i_size _cx_memb(_capacity)(const _cx_self* map) - { return (_i_size)((float)map->bucket_count * (i_max_load_factor)); } -STC_INLINE bool _cx_memb(_contains)(const _cx_self* self, _cx_keyraw rkey) - { return self->size && self->_hashx[_cx_memb(_bucket_)(self, &rkey).idx]; } - -#ifndef _i_isset - STC_API _cx_result _cx_memb(_insert_or_assign)(_cx_self* self, i_key key, i_val mapped); +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, intptr_t capacity); +STC_API _cx_result _cx_MEMB(_bucket_)(const _cx_Self* self, const _cx_keyraw* rkeyptr); +STC_API _cx_result _cx_MEMB(_insert_entry_)(_cx_Self* self, _cx_keyraw rkey); +STC_API void _cx_MEMB(_erase_entry)(_cx_Self* self, _cx_value* val); +STC_API float _cx_MEMB(_max_load_factor)(const _cx_Self* self); +STC_API intptr_t _cx_MEMB(_capacity)(const _cx_Self* map); + +STC_INLINE _cx_Self _cx_MEMB(_init)(void) { _cx_Self map = {0}; return map; } +STC_INLINE void _cx_MEMB(_shrink_to_fit)(_cx_Self* self) { _cx_MEMB(_reserve)(self, (intptr_t)self->size); } +STC_INLINE bool _cx_MEMB(_empty)(const _cx_Self* map) { return !map->size; } +STC_INLINE intptr_t _cx_MEMB(_size)(const _cx_Self* map) { return (intptr_t)map->size; } +STC_INLINE intptr_t _cx_MEMB(_bucket_count)(_cx_Self* map) { return map->bucket_count; } +STC_INLINE bool _cx_MEMB(_contains)(const _cx_Self* self, _cx_keyraw rkey) + { return self->size && !_cx_MEMB(_bucket_)(self, &rkey).inserted; } + +#ifdef _i_ismap + STC_API _cx_result _cx_MEMB(_insert_or_assign)(_cx_Self* self, i_key key, i_val mapped); #if !defined i_no_emplace - STC_API _cx_result _cx_memb(_emplace_or_assign)(_cx_self* self, _cx_keyraw rkey, i_valraw rmapped); + STC_API _cx_result _cx_MEMB(_emplace_or_assign)(_cx_Self* self, _cx_keyraw rkey, i_valraw rmapped); #endif STC_INLINE const _cx_mapped* - _cx_memb(_at)(const _cx_self* self, _cx_keyraw rkey) { - chash_bucket_t b = _cx_memb(_bucket_)(self, &rkey); - assert(self->_hashx[b.idx]); - return &self->table[b.idx].second; + _cx_MEMB(_at)(const _cx_Self* self, _cx_keyraw rkey) { + _cx_result b = _cx_MEMB(_bucket_)(self, &rkey); + c_assert(!b.inserted); + return &b.ref->second; } + STC_INLINE _cx_mapped* - _cx_memb(_at_mut)(_cx_self* self, _cx_keyraw rkey) - { return (_cx_mapped*)_cx_memb(_at)(self, rkey); } -#endif // !_i_isset + _cx_MEMB(_at_mut)(_cx_Self* self, _cx_keyraw rkey) + { return (_cx_mapped*)_cx_MEMB(_at)(self, rkey); } +#endif // _i_ismap #if !defined i_no_clone -STC_INLINE void _cx_memb(_copy)(_cx_self *self, const _cx_self* other) { - if (self->table == other->table) +STC_INLINE void _cx_MEMB(_copy)(_cx_Self *self, const _cx_Self* other) { + if (self->data == other->data) return; - _cx_memb(_drop)(self); - *self = _cx_memb(_clone)(*other); + _cx_MEMB(_drop)(self); + *self = _cx_MEMB(_clone)(*other); } STC_INLINE _cx_value -_cx_memb(_value_clone)(_cx_value _val) { +_cx_MEMB(_value_clone)(_cx_value _val) { *_i_keyref(&_val) = i_keyclone((*_i_keyref(&_val))); _i_MAP_ONLY( _val.second = i_valclone(_val.second); ) return _val; @@ -155,31 +144,39 @@ _cx_memb(_value_clone)(_cx_value _val) { #if !defined i_no_emplace STC_INLINE _cx_result -_cx_memb(_emplace)(_cx_self* self, _cx_keyraw rkey _i_MAP_ONLY(, i_valraw rmapped)) { - _cx_result _res = _cx_memb(_insert_entry_)(self, rkey); +_cx_MEMB(_emplace)(_cx_Self* self, _cx_keyraw rkey _i_MAP_ONLY(, i_valraw rmapped)) { + _cx_result _res = _cx_MEMB(_insert_entry_)(self, rkey); if (_res.inserted) { *_i_keyref(_res.ref) = i_keyfrom(rkey); _i_MAP_ONLY( _res.ref->second = i_valfrom(rmapped); ) } return _res; } + +#ifdef _i_ismap + STC_INLINE _cx_result + _cx_MEMB(_emplace_key)(_cx_Self* self, _cx_keyraw rkey) { + _cx_result _res = _cx_MEMB(_insert_entry_)(self, rkey); + if (_res.inserted) + _res.ref->first = i_keyfrom(rkey); + return _res; + } +#endif // _i_ismap #endif // !i_no_emplace -STC_INLINE _cx_raw -_cx_memb(_value_toraw)(const _cx_value* val) { +STC_INLINE _cx_raw _cx_MEMB(_value_toraw)(const _cx_value* val) { return _i_SET_ONLY( i_keyto(val) ) _i_MAP_ONLY( c_LITERAL(_cx_raw){i_keyto((&val->first)), i_valto((&val->second))} ); } -STC_INLINE void -_cx_memb(_value_drop)(_cx_value* _val) { +STC_INLINE void _cx_MEMB(_value_drop)(_cx_value* _val) { i_keydrop(_i_keyref(_val)); _i_MAP_ONLY( i_valdrop((&_val->second)); ) } STC_INLINE _cx_result -_cx_memb(_insert)(_cx_self* self, i_key _key _i_MAP_ONLY(, i_val _mapped)) { - _cx_result _res = _cx_memb(_insert_entry_)(self, i_keyto((&_key))); +_cx_MEMB(_insert)(_cx_Self* self, i_key _key _i_MAP_ONLY(, i_val _mapped)) { + _cx_result _res = _cx_MEMB(_insert_entry_)(self, i_keyto((&_key))); if (_res.inserted) { *_i_keyref(_res.ref) = _key; _i_MAP_ONLY( _res.ref->second = _mapped; )} else @@ -187,157 +184,150 @@ _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, _cx_value _val) { - _cx_result _res = _cx_memb(_insert_entry_)(self, i_keyto(_i_keyref(&_val))); +STC_INLINE _cx_value* _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; + _cx_MEMB(_value_drop)(&_val); + return _res.ref; } -STC_INLINE void _cx_memb(_put_n)(_cx_self* self, const _cx_raw* raw, _i_size n) { +STC_INLINE void _cx_MEMB(_put_n)(_cx_Self* self, const _cx_raw* raw, intptr_t n) { while (n--) #if defined _i_isset && defined i_no_emplace - _cx_memb(_insert)(self, *raw++); + _cx_MEMB(_insert)(self, *raw++); #elif defined _i_isset - _cx_memb(_emplace)(self, *raw++); + _cx_MEMB(_emplace)(self, *raw++); #elif defined i_no_emplace - _cx_memb(_insert_or_assign)(self, raw->first, raw->second), ++raw; + _cx_MEMB(_insert_or_assign)(self, raw->first, raw->second), ++raw; #else - _cx_memb(_emplace_or_assign)(self, raw->first, raw->second), ++raw; + _cx_MEMB(_emplace_or_assign)(self, raw->first, raw->second), ++raw; #endif } -STC_INLINE _cx_self _cx_memb(_from_n)(const _cx_raw* raw, _i_size n) - { _cx_self cx = {0}; _cx_memb(_put_n)(&cx, raw, n); return cx; } +STC_INLINE _cx_Self _cx_MEMB(_from_n)(const _cx_raw* raw, intptr_t n) + { _cx_Self cx = {0}; _cx_MEMB(_put_n)(&cx, raw, n); return cx; } -STC_INLINE _cx_iter _cx_memb(_begin)(const _cx_self* self) { - _cx_iter it = {self->table, self->table+self->bucket_count, self->_hashx}; - if (it._hx) - while (*it._hx == 0) - ++it.ref, ++it._hx; - if (it.ref == it._end) it.ref = NULL; - return it; -} +STC_API _cx_iter _cx_MEMB(_begin)(const _cx_Self* self); -STC_INLINE _cx_iter -_cx_memb(_end)(const _cx_self* self) +STC_INLINE _cx_iter _cx_MEMB(_end)(const _cx_Self* self) { return c_LITERAL(_cx_iter){NULL}; } -STC_INLINE void -_cx_memb(_next)(_cx_iter* it) { - while ((++it->ref, *++it->_hx == 0)) ; +STC_INLINE void _cx_MEMB(_next)(_cx_iter* it) { + while ((++it->ref, (++it->sref)->hashx == 0)) ; if (it->ref == it->_end) it->ref = NULL; } -STC_INLINE _cx_iter -_cx_memb(_advance)(_cx_iter it, size_t n) { - while (n-- && it.ref) _cx_memb(_next)(&it); +STC_INLINE _cx_iter _cx_MEMB(_advance)(_cx_iter it, size_t n) { + while (n-- && it.ref) _cx_MEMB(_next)(&it); return it; } STC_INLINE _cx_iter -_cx_memb(_find)(const _cx_self* self, _cx_keyraw rkey) { - int64_t idx; - if (self->size && self->_hashx[idx = _cx_memb(_bucket_)(self, &rkey).idx]) - return c_LITERAL(_cx_iter){self->table + idx, - self->table + self->bucket_count, - self->_hashx + idx}; - return _cx_memb(_end)(self); +_cx_MEMB(_find)(const _cx_Self* self, _cx_keyraw rkey) { + _cx_result b; + if (self->size && !(b = _cx_MEMB(_bucket_)(self, &rkey)).inserted) + return c_LITERAL(_cx_iter){b.ref, + self->data + self->bucket_count, + self->slot + (b.ref - self->data)}; + return _cx_MEMB(_end)(self); } STC_INLINE const _cx_value* -_cx_memb(_get)(const _cx_self* self, _cx_keyraw rkey) { - int64_t idx; - if (self->size && self->_hashx[idx = _cx_memb(_bucket_)(self, &rkey).idx]) - return self->table + idx; +_cx_MEMB(_get)(const _cx_Self* self, _cx_keyraw rkey) { + _cx_result b; + if (self->size && !(b = _cx_MEMB(_bucket_)(self, &rkey)).inserted) + return b.ref; return NULL; } STC_INLINE _cx_value* -_cx_memb(_get_mut)(_cx_self* self, _cx_keyraw rkey) - { return (_cx_value*)_cx_memb(_get)(self, rkey); } +_cx_MEMB(_get_mut)(_cx_Self* self, _cx_keyraw rkey) + { return (_cx_value*)_cx_MEMB(_get)(self, rkey); } STC_INLINE int -_cx_memb(_erase)(_cx_self* self, _cx_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; +_cx_MEMB(_erase)(_cx_Self* self, _cx_keyraw rkey) { + _cx_result b; + if (self->size && !(b = _cx_MEMB(_bucket_)(self, &rkey)).inserted) + { _cx_MEMB(_erase_entry)(self, b.ref); return 1; } + return 0; } STC_INLINE _cx_iter -_cx_memb(_erase_at)(_cx_self* self, _cx_iter it) { - _cx_memb(_erase_entry)(self, it.ref); - if (*it._hx == 0) - _cx_memb(_next)(&it); +_cx_MEMB(_erase_at)(_cx_Self* self, _cx_iter it) { + _cx_MEMB(_erase_entry)(self, it.ref); + if (it.sref->hashx == 0) + _cx_MEMB(_next)(&it); return it; } STC_INLINE bool -_cx_memb(_eq)(const _cx_self* self, const _cx_self* other) { - if (_cx_memb(_size)(self) != _cx_memb(_size)(other)) return false; - for (_cx_iter i = _cx_memb(_begin)(self); i.ref; _cx_memb(_next)(&i)) { +_cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { + if (_cx_MEMB(_size)(self) != _cx_MEMB(_size)(other)) return false; + for (_cx_iter i = _cx_MEMB(_begin)(self); i.ref; _cx_MEMB(_next)(&i)) { const _cx_keyraw _raw = i_keyto(_i_keyref(i.ref)); - if (!_cx_memb(_contains)(other, _raw)) return false; + if (!_cx_MEMB(_contains)(other, _raw)) return false; } return true; } /* -------------------------- IMPLEMENTATION ------------------------- */ -#if defined(i_implement) +#if defined(i_implement) || defined(i_static) +#ifndef i_max_load_factor + #define i_max_load_factor 0.80f +#endif +#define fastrange_2(x, n) (intptr_t)((x) & (size_t)((n) - 1)) // n power of 2. -#ifndef CMAP_H_INCLUDED -STC_INLINE int64_t fastrange_1(uint64_t x, uint64_t n) - { return (int64_t)((uint32_t)x*n >> 32); } // n < 2^32 - -STC_INLINE int64_t fastrange_2(uint64_t x, uint64_t n) - { return (int64_t)(x & (n - 1)); } // n power of 2. - -STC_INLINE uint64_t next_power_of_2(uint64_t n) { - n--; - n |= n >> 1, n |= n >> 2; - n |= n >> 4, n |= n >> 8; - n |= n >> 16, n |= n >> 32; - return n + 1; +STC_DEF _cx_iter _cx_MEMB(_begin)(const _cx_Self* self) { + _cx_iter it = {self->data, self->data+self->bucket_count, self->slot}; + if (it.sref) + while (it.sref->hashx == 0) + ++it.ref, ++it.sref; + if (it.ref == it._end) it.ref = NULL; + return it; +} + +STC_DEF float _cx_MEMB(_max_load_factor)(const _cx_Self* self) { + return (float)(i_max_load_factor); +} + +STC_DEF intptr_t _cx_MEMB(_capacity)(const _cx_Self* map) { + return (intptr_t)((float)map->bucket_count * (i_max_load_factor)); } -#endif // CMAP_H_INCLUDED -STC_DEF _cx_self -_cx_memb(_with_capacity)(const _i_size cap) { - _cx_self h = {0}; - _cx_memb(_reserve)(&h, cap); - return h; +STC_DEF _cx_Self _cx_MEMB(_with_capacity)(const intptr_t cap) { + _cx_Self map = {0}; + _cx_MEMB(_reserve)(&map, cap); + return map; } -STC_INLINE void _cx_memb(_wipe_)(_cx_self* self) { +STC_INLINE void _cx_MEMB(_wipe_)(_cx_Self* self) { if (self->size == 0) return; - _cx_value* e = self->table, *end = e + self->bucket_count; - uint8_t *hx = self->_hashx; - for (; e != end; ++e) - if (*hx++) - _cx_memb(_value_drop)(e); + _cx_value* d = self->data, *_end = d + self->bucket_count; + struct chash_slot* s = self->slot; + for (; d != _end; ++d) + if ((s++)->hashx) + _cx_MEMB(_value_drop)(d); } -STC_DEF void _cx_memb(_drop)(_cx_self* self) { - _cx_memb(_wipe_)(self); - i_free(self->_hashx); - i_free((void *) self->table); +STC_DEF void _cx_MEMB(_drop)(_cx_Self* self) { + _cx_MEMB(_wipe_)(self); + i_free(self->slot); + i_free(self->data); } -STC_DEF void _cx_memb(_clear)(_cx_self* self) { - _cx_memb(_wipe_)(self); +STC_DEF void _cx_MEMB(_clear)(_cx_Self* self) { + _cx_MEMB(_wipe_)(self); self->size = 0; - c_memset(self->_hashx, 0, self->bucket_count); + c_memset(self->slot, 0, c_sizeof(struct chash_slot)*self->bucket_count); } -#ifndef _i_isset +#ifdef _i_ismap STC_DEF _cx_result - _cx_memb(_insert_or_assign)(_cx_self* self, i_key _key, i_val _mapped) { - _cx_result _res = _cx_memb(_insert_entry_)(self, i_keyto((&_key))); + _cx_MEMB(_insert_or_assign)(_cx_Self* self, i_key _key, i_val _mapped) { + _cx_result _res = _cx_MEMB(_insert_entry_)(self, i_keyto((&_key))); _cx_mapped* _mp = _res.ref ? &_res.ref->second : &_mapped; if (_res.inserted) _res.ref->first = _key; @@ -349,8 +339,8 @@ STC_DEF void _cx_memb(_clear)(_cx_self* self) { #if !defined i_no_emplace STC_DEF _cx_result - _cx_memb(_emplace_or_assign)(_cx_self* self, _cx_keyraw rkey, i_valraw rmapped) { - _cx_result _res = _cx_memb(_insert_entry_)(self, rkey); + _cx_MEMB(_emplace_or_assign)(_cx_Self* self, _cx_keyraw rkey, i_valraw rmapped) { + _cx_result _res = _cx_MEMB(_insert_entry_)(self, rkey); if (_res.inserted) _res.ref->first = i_keyfrom(rkey); else { @@ -361,119 +351,117 @@ STC_DEF void _cx_memb(_clear)(_cx_self* self) { return _res; } #endif // !i_no_emplace -#endif // !_i_isset +#endif // _i_ismap -STC_DEF chash_bucket_t -_cx_memb(_bucket_)(const _cx_self* self, const _cx_keyraw* rkeyptr) { +STC_DEF _cx_result +_cx_MEMB(_bucket_)(const _cx_Self* self, const _cx_keyraw* rkeyptr) { const uint64_t _hash = i_hash(rkeyptr); - int64_t _cap = self->bucket_count; - chash_bucket_t b = {c_PASTE(fastrange_,_i_expandby)(_hash, (uint64_t)_cap), (uint8_t)(_hash | 0x80)}; - const uint8_t* _hx = self->_hashx; - while (_hx[b.idx]) { - if (_hx[b.idx] == b.hx) { - const _cx_keyraw _raw = i_keyto(_i_keyref(self->table + b.idx)); - if (i_eq((&_raw), rkeyptr)) + intptr_t _cap = self->bucket_count; + intptr_t _idx = fastrange_2(_hash, _cap); + _cx_result b = {NULL, true, (uint8_t)(_hash | 0x80)}; + const struct chash_slot* s = self->slot; + while (s[_idx].hashx) { + if (s[_idx].hashx == b.hashx) { + const _cx_keyraw _raw = i_keyto(_i_keyref(self->data + _idx)); + if (i_eq((&_raw), rkeyptr)) { + b.inserted = false; break; + } } - if (++b.idx == _cap) - b.idx = 0; + if (++_idx == _cap) _idx = 0; } + b.ref = self->data + _idx; return b; } STC_DEF _cx_result -_cx_memb(_insert_entry_)(_cx_self* self, _cx_keyraw rkey) { - _cx_result res = {NULL}; - if (self->size + 2 > (i_ssize)((float)self->bucket_count * (i_max_load_factor))) - if (!_cx_memb(_reserve)(self, self->size*3/2)) - return res; - - chash_bucket_t b = _cx_memb(_bucket_)(self, &rkey); - res.ref = &self->table[b.idx]; - if ((res.inserted = !self->_hashx[b.idx])) { - self->_hashx[b.idx] = b.hx; +_cx_MEMB(_insert_entry_)(_cx_Self* self, _cx_keyraw rkey) { + if (self->size >= (intptr_t)((float)self->bucket_count * (i_max_load_factor))) + if (!_cx_MEMB(_reserve)(self, (intptr_t)(self->size*3/2 + 2))) + return c_LITERAL(_cx_result){NULL}; + + _cx_result b = _cx_MEMB(_bucket_)(self, &rkey); + if (b.inserted) { + self->slot[b.ref - self->data].hashx = b.hashx; ++self->size; } - return res; + return b; } #if !defined i_no_clone -STC_DEF _cx_self -_cx_memb(_clone)(_cx_self m) { - if (m.table) { - _cx_value *t = (_cx_value *)i_malloc(c_sizeof(_cx_value)*m.bucket_count), - *dst = t, *m_end = m.table + m.bucket_count; - uint8_t *h = (uint8_t *)c_memcpy(i_malloc(m.bucket_count + 1), m._hashx, m.bucket_count + 1); - if (!(t && h)) - { i_free(t), i_free(h), t = 0, h = 0, m.bucket_count = 0; } +STC_DEF _cx_Self +_cx_MEMB(_clone)(_cx_Self m) { + if (m.data) { + _cx_value *d = (_cx_value *)i_malloc(c_sizeof(_cx_value)*m.bucket_count), + *_dst = d, *_end = m.data + m.bucket_count; + const intptr_t _mem = c_sizeof(struct chash_slot)*(m.bucket_count + 1); + struct chash_slot *s = (struct chash_slot *)c_memcpy(i_malloc(_mem), m.slot, _mem); + if (!(d && s)) + { i_free(d), i_free(s), d = 0, s = 0, m.bucket_count = 0; } else - for (; m.table != m_end; ++m.table, ++m._hashx, ++dst) - if (*m._hashx) - *dst = _cx_memb(_value_clone)(*m.table); - m.table = t, m._hashx = h; + for (; m.data != _end; ++m.data, ++m.slot, ++_dst) + if (m.slot->hashx) + *_dst = _cx_MEMB(_value_clone)(*m.data); + m.data = d, m.slot = s; } return m; } #endif STC_DEF bool -_cx_memb(_reserve)(_cx_self* self, const _i_size newcap) { - const i_ssize _oldbuckets = self->bucket_count, _newcap = (i_ssize)newcap; - if (_newcap != self->size && _newcap <= _oldbuckets) +_cx_MEMB(_reserve)(_cx_Self* self, const intptr_t _newcap) { + const intptr_t _oldbucks = self->bucket_count; + if (_newcap != self->size && _newcap <= _oldbucks) return true; - i_ssize _nbuckets = (i_ssize)((float)_newcap / (i_max_load_factor)) + 4; - #if _i_expandby == 2 - _nbuckets = (i_ssize)next_power_of_2(_nbuckets); - #else - _nbuckets |= 1; - #endif - _cx_self m = { - (_cx_value *)i_malloc(c_sizeof(_cx_value)*_nbuckets), - (uint8_t *)i_calloc(_nbuckets + 1, 1), - self->size, _nbuckets, + intptr_t _newbucks = (intptr_t)((float)_newcap / (i_max_load_factor)) + 4; + _newbucks = stc_nextpow2(_newbucks); + _cx_Self m = { + (_cx_value *)i_malloc(_newbucks*c_sizeof(_cx_value)), + (struct chash_slot *)i_calloc(_newbucks + 1, c_sizeof(struct chash_slot)), + self->size, _newbucks }; - bool ok = m.table && m._hashx; - if (ok) { /* Rehash: */ - m._hashx[_nbuckets] = 0xff; - const _cx_value* e = self->table; - const uint8_t* h = self->_hashx; - for (i_ssize i = 0; i < _oldbuckets; ++i, ++e) if (*h++) { - _cx_keyraw r = i_keyto(_i_keyref(e)); - chash_bucket_t b = _cx_memb(_bucket_)(&m, &r); - m.table[b.idx] = *e; - m._hashx[b.idx] = b.hx; + bool ok = m.data && m.slot; + if (ok) { // Rehash: + m.slot[_newbucks].hashx = 0xff; + const _cx_value* d = self->data; + const struct chash_slot* s = self->slot; + for (intptr_t i = 0; i < _oldbucks; ++i, ++d) if ((s++)->hashx) { + _cx_keyraw r = i_keyto(_i_keyref(d)); + _cx_result b = _cx_MEMB(_bucket_)(&m, &r); + m.slot[b.ref - m.data].hashx = b.hashx; + *b.ref = *d; // move } - c_swap(_cx_self, self, &m); + c_swap(_cx_Self, self, &m); } - i_free(m._hashx); - i_free(m.table); + i_free(m.slot); + i_free(m.data); return ok; } STC_DEF void -_cx_memb(_erase_entry)(_cx_self* self, _cx_value* _val) { - i_ssize i = (i_ssize)(_val - self->table), j = i, k; - const i_ssize _cap = self->bucket_count; - _cx_value* _slot = self->table; - uint8_t* _hashx = self->_hashx; - _cx_memb(_value_drop)(_val); - for (;;) { /* delete without leaving tombstone */ - if (++j == _cap) - j = 0; - if (! _hashx[j]) +_cx_MEMB(_erase_entry)(_cx_Self* self, _cx_value* _val) { + _cx_value* d = self->data; + struct chash_slot* s = self->slot; + intptr_t i = _val - d, j = i, k; + const intptr_t _cap = self->bucket_count; + _cx_MEMB(_value_drop)(_val); + for (;;) { // delete without leaving tombstone + if (++j == _cap) j = 0; + if (! s[j].hashx) break; - const _cx_keyraw _raw = i_keyto(_i_keyref(_slot + j)); - k = (i_ssize)c_PASTE(fastrange_,_i_expandby)(i_hash((&_raw)), (uint64_t)_cap); - if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ - _slot[i] = _slot[j], _hashx[i] = _hashx[j], i = j; + const _cx_keyraw _raw = i_keyto(_i_keyref(d + j)); + k = fastrange_2(i_hash((&_raw)), _cap); + if ((j < i) ^ (k <= i) ^ (k > j)) { // is k outside (i, j]? + d[i] = d[j]; + s[i] = s[j]; + i = j; + } } - _hashx[i] = 0; + s[i].hashx = 0; --self->size; } - #endif // i_implement #undef i_max_load_factor -#undef _i_size #undef _i_isset #undef _i_ismap #undef _i_ishash |