From 1f9b7525f825fff1a0c62548c6a0e39ea9bfed43 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 4 Apr 2021 21:04:11 +0200 Subject: Fixed bugs in clist_X_erase_at() and clist_X_erase_range(). Renamed clist_X_size() to clist_X_distance() because it is O(n). --- docs/clist_api.md | 10 +++++----- stc/clist.h | 14 ++++++++------ 2 files changed, 13 insertions(+), 11 deletions(-) diff --git a/docs/clist_api.md b/docs/clist_api.md index c14104f5..49656ea5 100644 --- a/docs/clist_api.md +++ b/docs/clist_api.md @@ -7,15 +7,15 @@ Fast random access is not supported. Unlike the c++ class *std::forward_list*, **clist** has an API similar to *std::list*, and also supports *push_back()* (**O**(1) time). It is still implemented as a singly-linked list. A **clist** object occupies only one pointer in memory, and like *std::forward_list* the length of the list is not stored. -The method *clist_X_size()* is available, however computed in **O**(*n*) time. +The method *clist_X_distance()* returns size of list, computed in **O**(*n*) time. ***Iterator invalidation***: Adding, removing and moving the elements within the list, or across several lists will invalidate other iterators currently refering to these elements and their immediate succesive elements. However, an iterator to a succesive element can both be dereferenced and advanced. After advancing (using *clist_X_next(&it)* or *it = cslist_X_fwd(it, n)*), the iterator is in a valid state. This implies: -- `clist_X_insert(&L, clist_X_fwd(it,1))` is valid, unless `*it.ref` was removed. -- `clist_X_erase_at(&L, clist_X_fwd(it,1))` is valid, unless `*it.ref`was removed or `clist_X_fwd(it,1)` is `end`. +- `clist_X_insert(&L, clist_X_fwd(it,1))` (insert_after) is well formed if element at `it` exists. +- `clist_X_erase_at(&L, clist_X_fwd(it,1))` (erase_after) is well formed if element at `it` exists and is not last in list. - Iterators returned from *clist_X_insert()* and *clist_X_erase_at()* are always valid or `end`. - Elements can be safely removed from a list via multiple iterators if done in back to front order. @@ -50,7 +50,7 @@ void clist_X_clear(clist_X* self); void clist_X_del(clist_X* self); // destructor bool clist_X_empty(clist_X list); -size_t clist_X_size(clist_X list); // note: O(n) +size_t clist_X_distance(clist_X list); // size() in O(n) clist_X_value_t* clist_X_front(const clist_X* self); clist_X_value_t* clist_X_back(const clist_X* self); @@ -87,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: return iterator advanced n elements forward: + // non-std: iterator advanced n elements forward. returns end if `it` == 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/clist.h b/stc/clist.h index d6129bcb..4de4a4ab 100644 --- a/stc/clist.h +++ b/stc/clist.h @@ -95,11 +95,11 @@ STC_API size_t _clist_size(const clist_void* self); typedef RawValue clist_##X##_rawvalue_t; \ \ STC_INLINE clist_##X \ - clist_##X##_init(void) {clist_##X x = {NULL}; return x;} \ + clist_##X##_init(void) {clist_##X lst = {NULL}; return lst;} \ STC_INLINE bool \ - clist_##X##_empty(clist_##X ls) {return ls.last == NULL;} \ + clist_##X##_empty(clist_##X lst) {return lst.last == NULL;} \ STC_INLINE size_t \ - clist_##X##_size(clist_##X ls) {return _clist_size((const clist_void*) &ls);} \ + clist_##X##_distance(clist_##X lst) {return _clist_size((const clist_void*) &lst);} \ STC_INLINE Value \ clist_##X##_value_fromraw(RawValue raw) {return valueFromRaw(raw);} \ STC_INLINE clist_##X##_value_t \ @@ -242,15 +242,17 @@ STC_API size_t _clist_size(const clist_void* self); \ STC_DEF clist_##X##_iter_t \ clist_##X##_erase_at(clist_##X* self, clist_##X##_iter_t pos) { \ - clist_##X##_node_t* node = pos._prev; clist_##X##_next(&pos); \ - return _clist_##X##_erase_after(self, node) ? pos : clist_##X##_end(self); \ + clist_##X##_node_t* node = pos._prev; \ + if (pos.ref == self->last) pos.ref = pos._prev = NULL; \ + else pos.ref = &_clist_node(X, pos.ref)->next->value; \ + _clist_##X##_erase_after(self, node); return pos; \ } \ STC_DEF clist_##X##_iter_t \ clist_##X##_erase_range(clist_##X* self, clist_##X##_iter_t first, clist_##X##_iter_t finish) { \ clist_##X##_node_t* node = first._prev, *done = finish.ref ? _clist_node(X, finish.ref) : NULL; \ while (node && node->next != done) \ node = _clist_##X##_erase_after(self, node); \ - return node ? finish : clist_##X##_end(self); \ + return finish; \ } \ \ STC_DEF clist_##X##_iter_t \ -- cgit v1.2.3