From 9c5db584ab6bd8ecab600c755ad5443fe4b65d21 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 8 Apr 2021 09:23:03 +0200 Subject: clist_X_count() returns size of vector in O(n) time. --- docs/clist_api.md | 9 +++++---- stc/clist.h | 6 +++--- 2 files changed, 8 insertions(+), 7 deletions(-) diff --git a/docs/clist_api.md b/docs/clist_api.md index 857e49a2..cd8c5ed8 100644 --- a/docs/clist_api.md +++ b/docs/clist_api.md @@ -1,4 +1,4 @@ -# STC [clist](../stc/clist.h): Forward List +# STC [clist](../stc/clist.h): Singly Linked List ![List](pics/list.jpg) The **clist** container supports fast insertion and removal of elements from anywhere in the container. @@ -7,7 +7,7 @@ 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_distance()* returns size of list, computed in **O**(*n*) time. +The method *clist_X_count()* 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. @@ -19,7 +19,8 @@ However, an iterator to a succesive element can both be dereferenced and advance - 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. -See the c++ class [std::forward_list](https://en.cppreference.com/w/cpp/container/forward_list) for a functional description. +See the c++ class [std::list](https://en.cppreference.com/w/cpp/container/list) for similar API and +[std::forward_list](https://en.cppreference.com/w/cpp/container/forward_list) for a functional description. ## Header file and declaration @@ -50,7 +51,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_distance(clist_X list); // size() in O(n) +size_t clist_X_count(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); diff --git a/stc/clist.h b/stc/clist.h index 170e2dc5..027f5e9c 100644 --- a/stc/clist.h +++ b/stc/clist.h @@ -99,7 +99,7 @@ STC_API size_t _clist_size(const clist_void* self); STC_INLINE bool \ clist_##X##_empty(clist_##X lst) {return lst.last == NULL;} \ STC_INLINE size_t \ - clist_##X##_distance(clist_##X lst) {return _clist_size((const clist_void*) &lst);} \ + clist_##X##_count(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 \ @@ -243,11 +243,11 @@ 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 = _clist_node(X, pos.ref); \ - if (node == self->last) pos.ref = NULL; \ - else pos.ref = &node->next->value; \ + pos.ref = (node == self->last) ? NULL : &node->next->value; \ _clist_##X##_erase_after(self, pos._prev); \ 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.ref ? first._prev : NULL, \ -- cgit v1.2.3