From c67a87749fb02c32e982dd309f62b54c1efde076 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 22 Apr 2021 15:18:29 +0200 Subject: clist_X_splice*() now returns updated input iter. Added list_splice.c example. --- benchmarks/shootout4_crand.cpp | 4 +++- docs/clist_api.md | 21 ++++++++++----------- examples/list_splice.c | 34 ++++++++++++++++++++++++++++++++++ stc/clist.h | 19 ++++++++++--------- 4 files changed, 57 insertions(+), 21 deletions(-) create mode 100644 examples/list_splice.c diff --git a/benchmarks/shootout4_crand.cpp b/benchmarks/shootout4_crand.cpp index df13befd..5d5fd3d7 100644 --- a/benchmarks/shootout4_crand.cpp +++ b/benchmarks/shootout4_crand.cpp @@ -98,7 +98,7 @@ using namespace std; int main(void) { - enum {N = 800000000}; + enum {N = 2000000000}; uint64_t* recipient = new uint64_t[N]; static stc64_t rng; init_state(rng.state, 12345123); @@ -109,6 +109,7 @@ int main(void) clock_t beg, end; for (size_t ti = 0; ti < 4; ti++) { + init_state(rng.state, 12345123); cout << endl << "ROUND " << ti+1 << endl; beg = clock(); for (size_t i = 0; i < N; i++) @@ -151,6 +152,7 @@ int main(void) cout << "Next we do random number computations only, doing no work." << endl; + init_state(rng.state, 12345123); uint64_t s = 0; beg = clock(); for (size_t i = 0; i < N; i++) diff --git a/docs/clist_api.md b/docs/clist_api.md index b2059c7e..035c5dcf 100644 --- a/docs/clist_api.md +++ b/docs/clist_api.md @@ -48,10 +48,10 @@ clist_X clist_X_init(void); clist_X clist_X_clone(clist_X list); void clist_X_clear(clist_X* self); -void clist_X_del(clist_X* self); // destructor +void clist_X_del(clist_X* self); // destructor bool clist_X_empty(clist_X list); -size_t clist_X_count(clist_X list); // size() in O(n) time +size_t clist_X_count(clist_X list); // size() in O(n) time clist_X_value_t* clist_X_front(const clist_X* self); clist_X_value_t* clist_X_back(const clist_X* self); @@ -60,22 +60,21 @@ 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); -void clist_X_push_back(clist_X* self, Value value); // note: no pop_back(). +void clist_X_push_back(clist_X* self, Value value); // note: no pop_back(). 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 n); -clist_X_iter_t clist_X_insert(clist_X* self, clist_X_iter_t it, Value value); // return iter to new elem +clist_X_iter_t clist_X_insert(clist_X* self, clist_X_iter_t it, Value value); // return iter to new elem clist_X_iter_t clist_X_emplace(clist_X* self, clist_X_iter_t it, RawValue raw); -clist_X_iter_t clist_X_erase_it(clist_X* self, clist_X_iter_t it); // return iter after it +clist_X_iter_t clist_X_erase_it(clist_X* self, clist_X_iter_t it); // return iter after it clist_X_iter_t clist_X_erase_range(clist_X* self, clist_X_iter_t it1, clist_X_iter_t it2); -size_t clist_X_remove(clist_X* self, RawValue raw); // removes all elements equal to raw +size_t clist_X_remove(clist_X* self, RawValue raw); // removes all elements equal to raw -void clist_X_splice(clist_X* self, clist_X_iter_t it, clist_X* other); -void clist_X_splice_range(clist_X* self, clist_X_iter_t it, // see std::list::splice() docs +clist_X clist_X_split(clist_X* self, clist_X_iter_t it1, clist_X_iter_t it2); // split out [it1, it2) +clist_X_iter_t clist_X_splice(clist_X* self, clist_X_iter_t it, clist_X* other); // return updated valid it +clist_X_iter_t clist_X_splice_range(clist_X* self, clist_X_iter_t it, // return updated valid it clist_X* other, clist_X_iter_t it1, clist_X_iter_t it2); - // split out [it1, it2) from self, and return as a clist -clist_X clist_X_split(clist_X* self, clist_X_iter_t it1, clist_X_iter_t it2); clist_X_iter_t clist_X_find(const clist_X* self, RawValue raw); clist_X_iter_t clist_X_find_in(const clist_X* self, @@ -87,7 +86,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); -clist_X_iter_t clist_X_fwd(clist_X_iter it, size_t n); // return it n elements ahead. End allowed. +clist_X_iter_t clist_X_fwd(clist_X_iter it, size_t n); // return it n elements ahead. End allowed. clist_X_value_t clist_X_value_clone(clist_X_value_t val); ``` diff --git a/examples/list_splice.c b/examples/list_splice.c new file mode 100644 index 00000000..06464c27 --- /dev/null +++ b/examples/list_splice.c @@ -0,0 +1,34 @@ +#include +#include + +using_clist(i, int); + +void print_ilist(const char* s, clist_i list) +{ + printf("%s", s); + c_foreach (i, clist_i, list) { + printf(" %d", *i.ref); + } + puts(""); +} + +int main () +{ + c_init (clist_i, list1, { 1, 2, 3, 4, 5 }); + c_init (clist_i, list2, { 10, 20, 30, 40, 50 }); + + clist_i_iter_t it = clist_i_fwd(clist_i_begin(&list1), 2); + it = clist_i_splice(&list1, it, &list2); + + puts("After splice"); + print_ilist("list1:", list1); + print_ilist("list2:", list2); + + clist_i_splice_range(&list2, clist_i_begin(&list2), &list1, it, clist_i_end(&list1)); + + puts("After splice_range"); + print_ilist("list1:", list1); + print_ilist("list2:", list2); + + c_del(clist_i, &list1, &list2); +} \ No newline at end of file diff --git a/stc/clist.h b/stc/clist.h index a2f7668c..d998dbe5 100644 --- a/stc/clist.h +++ b/stc/clist.h @@ -129,7 +129,7 @@ STC_API size_t _clist_size(const clist_VOID* self); STC_API CX##_iter_t CX##_erase_range(CX* self, CX##_iter_t it1, CX##_iter_t it2); \ STC_API size_t CX##_remove(CX* self, RawValue val); \ \ - STC_API void CX##_splice(CX* self, CX##_iter_t it, CX* other); \ + STC_API CX##_iter_t CX##_splice(CX* self, CX##_iter_t it, CX* other); \ STC_API CX CX##_split(CX* self, CX##_iter_t it1, CX##_iter_t it2); \ STC_API void CX##_sort(CX* self); \ STC_API CX##_iter_t CX##_find_in(const CX* self, CX##_iter_t it1, CX##_iter_t it2, RawValue val); \ @@ -160,11 +160,11 @@ STC_API size_t _clist_size(const clist_VOID* self); return it; \ } \ \ - STC_INLINE void \ + STC_INLINE CX##_iter_t \ CX##_splice_range(CX* self, CX##_iter_t it, \ CX* other, CX##_iter_t it1, CX##_iter_t it2) { \ CX tmp = CX##_split(other, it1, it2); \ - CX##_splice(self, it, &tmp); \ + return CX##_splice(self, it, &tmp); \ } \ \ STC_INLINE CX##_iter_t \ @@ -232,7 +232,7 @@ STC_API size_t _clist_size(const clist_VOID* self); STC_DEF CX##_iter_t \ CX##_erase_range(CX* self, CX##_iter_t it1, CX##_iter_t it2) { \ CX##_node_t *node = it1.ref ? it1._prev : NULL, \ - *done = it2.ref ? _clist_node(CX, it2.ref) : NULL; \ + *done = it2.ref ? _clist_node(CX, it2.ref) : NULL; \ while (node && node->next != done) \ node = CX##_erase_after_(self, node); \ return it2; \ @@ -272,17 +272,18 @@ STC_API size_t _clist_size(const clist_VOID* self); return n; \ } \ \ - STC_DEF void \ + STC_DEF CX##_iter_t \ CX##_splice(CX* self, CX##_iter_t it, CX* other) { \ if (!self->last) \ self->last = other->last; \ else if (other->last) { \ CX##_node_t *p = it.ref ? it._prev : self->last, *next = p->next; \ - p->next = other->last->next; \ - other->last->next = next; \ - if (!it.ref) self->last = other->last; \ + it._prev = other->last; \ + p->next = it._prev->next; \ + it._prev->next = next; \ + if (!it.ref) self->last = it._prev; \ } \ - other->last = NULL; \ + other->last = NULL; return it; \ } \ \ STC_DEF CX \ -- cgit v1.2.3