From e30a59bd3fe84c6a65604a6b7ac9e5dcadc5637e Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 9 Apr 2021 08:56:46 +0200 Subject: Added csmap_X_erase_range(). --- docs/clist_api.md | 3 +- stc/csmap.h | 84 +++++++++++++++++++++++++++++-------------------------- 2 files changed, 45 insertions(+), 42 deletions(-) diff --git a/docs/clist_api.md b/docs/clist_api.md index f09de26c..5d665c83 100644 --- a/docs/clist_api.md +++ b/docs/clist_api.md @@ -60,7 +60,6 @@ void clist_X_push_front(clist_X* self, Value value); void clist_X_emplace_front(clist_X* self, RawValue raw); void clist_X_pop_front(clist_X* self); - // non-std: void clist_X_push_back(clist_X* self, Value value); void clist_X_emplace_back(clist_X* self, RawValue raw); void clist_X_emplace_n(clist_X *self, const clist_X_rawvalue_t arr[], size_t size); @@ -88,7 +87,7 @@ clist_X_iter_t clist_X_begin(const clist_X* self); clist_X_iter_t clist_X_end(const clist_X* self); void clist_X_next(clist_X_iter_t* it); - // non-std: iterator advanced n elements forward. returns end if `it` == end. + // advance iter n elements forward. accepts and can return end. clist_X_iter_t clist_X_fwd(clist_X_iter it, size_t n); clist_X_value_t clist_X_value_clone(clist_X_value_t val); ``` diff --git a/stc/csmap.h b/stc/csmap.h index a96eac83..b026d019 100644 --- a/stc/csmap.h +++ b/stc/csmap.h @@ -175,29 +175,30 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; CX##_size_t _tn, _st[48]; \ } CX##_iter_t; \ \ - STC_API CX CX##_init(void); \ - STC_API CX CX##_clone(CX tree); \ + STC_API CX CX##_init(void); \ + STC_API CX CX##_clone(CX tree); \ + STC_API void CX##_del(CX* self); \ + STC_API void CX##_reserve(CX* self, size_t cap); \ + STC_INLINE bool CX##_empty(CX tree) {return _csmap_rep(&tree)->size == 0;} \ + STC_INLINE size_t CX##_size(CX tree) {return _csmap_rep(&tree)->size;} \ + STC_INLINE size_t CX##_capacity(CX tree) {return _csmap_rep(&tree)->cap;} \ + STC_INLINE void CX##_clear(CX* self) {CX##_del(self); *self = CX##_init();} \ + STC_INLINE void CX##_swap(CX* a, CX* b) {c_swap(CX, *a, *b);} \ + STC_API CX##_value_t* CX##_find_it(const CX* self, RawKey rkey, CX##_iter_t* out); \ + STC_API CX##_iter_t CX##_lower_bound(const CX* self, RawKey rkey); \ + STC_API CX##_value_t* CX##_front(const CX* self); \ + STC_API CX##_value_t* CX##_back(const CX* self); \ + STC_API int CX##_erase(CX* self, RawKey rkey); \ + STC_API CX##_iter_t CX##_erase_at(CX* self, CX##_iter_t pos); \ + STC_API CX##_iter_t CX##_erase_range(CX* self, CX##_iter_t it1, CX##_iter_t it2); \ + STC_API CX##_result_t CX##_insert_entry_(CX* self, RawKey rkey); \ \ - STC_API void \ - CX##_reserve(CX* self, size_t cap); \ STC_INLINE CX \ CX##_with_capacity(size_t size) { \ CX x = CX##_init(); \ CX##_reserve(&x, size); \ return x; \ } \ - STC_INLINE bool \ - CX##_empty(CX tree) {return _csmap_rep(&tree)->size == 0;} \ - STC_INLINE size_t \ - CX##_size(CX tree) {return _csmap_rep(&tree)->size;} \ - STC_INLINE size_t \ - CX##_capacity(CX tree) {return _csmap_rep(&tree)->cap;} \ - STC_API void \ - CX##_del(CX* self); \ - STC_INLINE void \ - CX##_clear(CX* self) {CX##_del(self); *self = CX##_init();} \ - STC_INLINE void \ - CX##_swap(CX* a, CX* b) {c_swap(CX, *a, *b);} \ \ STC_INLINE void \ CX##_value_del(CX##_value_t* val) { \ @@ -210,12 +211,6 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; MAP_ONLY_##C( val.second = mappedFromRaw(mappedToRaw(&val.second)); ) \ return val; \ } \ -\ - STC_API CX##_value_t* \ - CX##_find_it(const CX* self, RawKey rkey, CX##_iter_t* out); \ -\ - STC_API CX##_iter_t \ - CX##_lower_bound(const CX* self, RawKey rkey); \ \ STC_INLINE CX##_iter_t \ CX##_find(const CX* self, RawKey rkey) { \ @@ -229,9 +224,6 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; CX##_iter_t it; \ return CX##_find_it(self, rkey, &it) != NULL; \ } \ -\ - STC_API CX##_result_t \ - CX##_insert_entry_(CX* self, RawKey rkey); \ \ STC_INLINE CX##_result_t \ CX##_emplace(CX* self, RawKey rkey MAP_ONLY_##C(, RawMapped rmapped)) { \ @@ -242,6 +234,7 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; } \ return res; \ } \ +\ STC_INLINE void \ CX##_emplace_n(CX* self, const CX##_rawvalue_t arr[], size_t n) { \ for (size_t i=0; isecond); \ res.ref->second = mappedFromRaw(rmapped); return res; \ } \ +\ STC_INLINE CX##_mapped_t* \ CX##_at(const CX* self, RawKey rkey) { \ CX##_iter_t it; \ return &CX##_find_it(self, rkey, &it)->second; \ }) \ \ - STC_API CX##_value_t* CX##_front(const CX* self); \ - STC_API CX##_value_t* CX##_back(const CX* self); \ - STC_API void CX##_next(CX##_iter_t* it); \ + STC_API void \ + CX##_next(CX##_iter_t* it); \ \ STC_INLINE CX##_iter_t \ CX##_begin(const CX* self) { \ - CX##_iter_t it = {NULL, self->nodes, 0, (CX##_size_t) _csmap_rep(self)->root}; \ + CX##_iter_t it; it._d = self->nodes, it._top = 0; \ + it._tn = (CX##_size_t) _csmap_rep(self)->root; \ if (it._tn) CX##_next(&it); \ return it; \ } \ STC_INLINE CX##_iter_t \ CX##_end(const CX* self) {\ - CX##_iter_t it = {NULL}; return it; \ + CX##_iter_t it; it.ref = NULL; return it; \ } \ - STC_API int \ - CX##_erase(CX* self, RawKey rkey); \ -\ - STC_API CX##_iter_t \ - CX##_erase_at(CX* self, CX##_iter_t pos); \ \ _c_implement_aatree(CX, C, Key, Mapped, keyCompareRaw, \ mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ @@ -511,12 +501,26 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; } \ \ STC_DEF CX##_iter_t \ - CX##_erase_at(CX* self, CX##_iter_t pos) { \ - RawKey raw = keyToRaw(KEY_REF_##C(pos.ref)); CX##_next(&pos); \ - RawKey nxt = keyToRaw(KEY_REF_##C(pos.ref)); \ + CX##_erase_at(CX* self, CX##_iter_t it) { \ + RawKey raw = keyToRaw(KEY_REF_##C(it.ref)); CX##_next(&it); \ + RawKey nxt = keyToRaw(KEY_REF_##C(it.ref)); \ CX##_erase(self, raw); \ - CX##_find_it(self, nxt, &pos); \ - return pos; \ + CX##_find_it(self, nxt, &it); \ + return it; \ + } \ +\ + STC_DEF CX##_iter_t \ + CX##_erase_range(CX* self, CX##_iter_t it1, CX##_iter_t it2) { \ + CX##_rawkey_t *arr = NULL, nxt; size_t sz=0, cap=0; \ + for (; it1.ref != it2.ref; CX##_next(&it1), ++sz) { \ + if (sz == cap) arr = (CX##_rawkey_t*) c_realloc(arr, sizeof arr[0]*(cap = (sz + 6)*1.5)); \ + arr[sz] = keyToRaw(KEY_REF_##C(it1.ref)); \ + } \ + if (it2.ref) nxt = keyToRaw(KEY_REF_##C(it2.ref)); \ + for (size_t i=0; i