From 0491562d75ecb039f3c12c36b12c1c4e01a808ef Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 18 Dec 2020 23:13:12 +0100 Subject: Fixed issues in cdeq and cvec. Added shrink_to_fit() too. --- docs/cvec_api.md | 13 ++++++------ stc/cdeq.h | 62 ++++++++++++++++++++++++++++++++++++++++---------------- stc/cvec.h | 18 +++++++++++----- 3 files changed, 64 insertions(+), 29 deletions(-) diff --git a/docs/cvec_api.md b/docs/cvec_api.md index 628d5acd..413b49c3 100644 --- a/docs/cvec_api.md +++ b/docs/cvec_api.md @@ -58,6 +58,7 @@ cvec_X cvec_X_with_capacity(size_t size); cvec_X cvec_X_clone(cvec_X vec); void cvec_X_clear(cvec_X* self); +void cvec_X_shrink_to_fit(cvec_X* self); void cvec_X_reserve(cvec_X* self, size_t cap); void cvec_X_resize(cvec_X* self, size_t size, Value fill); void cvec_X_swap(cvec_X* a, cvec_X* b); @@ -73,12 +74,12 @@ cvec_X_value_t* cvec_X_front(cvec_X* self); cvec_X_value_t* cvec_X_back(cvec_X* self); void cvec_X_push_n(cvec_X *self, const cvec_X_input_t arr[], size_t size); -void cvec_X_emplace_back(cvec_X* self, RawValue ref); +void cvec_X_emplace_back(cvec_X* self, RawValue raw); void cvec_X_push_back(cvec_X* self, Value value); void cvec_X_pop_back(cvec_X* self); -cvec_X_iter_t cvec_X_emplace(cvec_X* self, cvec_X_iter_t pos, RawValue ref); -cvec_X_iter_t cvec_X_emplace_at(cvec_X* self, size_t idx, RawValue ref); +cvec_X_iter_t cvec_X_emplace(cvec_X* self, cvec_X_iter_t pos, RawValue raw); +cvec_X_iter_t cvec_X_emplace_at(cvec_X* self, size_t idx, RawValue raw); cvec_X_iter_t cvec_X_insert(cvec_X* self, cvec_X_iter_t pos, Value value); cvec_X_iter_t cvec_X_insert_at(cvec_X* self, size_t idx, Value value); cvec_X_iter_t cvec_X_insert_range(cvec_X* self, cvec_X_iter_t pos, @@ -91,9 +92,9 @@ cvec_X_iter_t cvec_X_erase_n(cvec_X* self, size_t idx, size_t n); cvec_X_iter_t cvec_X_erase_range(cvec_X* self, cvec_X_iter_t first, cvec_X_iter_t finish); cvec_X_iter_t cvec_X_erase_range_p(cvec_X* self, cvec_X_value_t* pfirst, cvec_X_value_t* pfinish); -cvec_X_iter_t cvec_X_find(const cvec_X* self, RawValue ref); +cvec_X_iter_t cvec_X_find(const cvec_X* self, RawValue raw); cvec_X_iter_t cvec_X_find_in_range(const cvec_X* self, - cvec_X_iter_t first, cvec_X_iter_t finish, RawValue ref); + cvec_X_iter_t first, cvec_X_iter_t finish, RawValue raw); void cvec_X_sort(cvec_X* self); void cvec_X_sort_with(cvec_X* self, size_t ifirst, size_t ifinish, @@ -105,7 +106,7 @@ void cvec_X_next(cvec_X_iter_t* it); cvec_X_value_t* cvec_X_itval(cvec_X_iter_t it); size_t cvec_X_index(const cvec_X vec, cvec_X_iter_t it); -Value cvec_X_value_from_raw(RawValue ref); +Value cvec_X_value_from_raw(RawValue raw); ``` ## Examples diff --git a/stc/cdeq.h b/stc/cdeq.h index edfa5e72..8620f676 100644 --- a/stc/cdeq.h +++ b/stc/cdeq.h @@ -68,7 +68,7 @@ STC_API void \ cdeq_##X##_resize(cdeq_##X* self, size_t size, Value fill_val); \ STC_API void \ - cdeq_##X##_expand(cdeq_##X* self, size_t n, bool front); \ + _cdeq_##X##_expand(cdeq_##X* self, size_t n, bool front); \ STC_INLINE void \ cdeq_##X##_swap(cdeq_##X* a, cdeq_##X* b) {c_swap(cdeq_##X, *a, *b);} \ \ @@ -81,14 +81,20 @@ STC_INLINE cdeq_##X \ cdeq_##X##_with_capacity(size_t size) { \ cdeq_##X x = cdeq_inits; \ - cdeq_##X##_expand(&x, size, false); \ + _cdeq_##X##_expand(&x, size, false); \ return x; \ } \ -\ STC_API cdeq_##X \ cdeq_##X##_clone(cdeq_##X vec); \ +\ + STC_INLINE void \ + cdeq_##X##_shrink_to_fit(cdeq_##X *self) { \ + cdeq_##X x = cdeq_##X##_clone(*self); \ + cdeq_##X##_del(self); *self = x; \ + } \ +\ STC_API void \ - cdeq_##X##_push_n(cdeq_##X *self, const cdeq_##X##_input_t arr[], size_t size); \ + cdeq_##X##_push_n(cdeq_##X *self, const cdeq_##X##_input_t arr[], size_t n); \ STC_API void \ cdeq_##X##_push_back(cdeq_##X* self, Value value); \ STC_INLINE void \ @@ -99,6 +105,18 @@ cdeq_##X##_pop_back(cdeq_##X* self) { \ valueDestroy(&self->data[--_cdeq_size(self)]); \ } \ +\ + STC_INLINE void \ + cdeq_##X##_push_front(cdeq_##X* self, Value value); \ + STC_INLINE void \ + cdeq_##X##_emplace_front(cdeq_##X* self, RawValue rawValue) { \ + cdeq_##X##_push_front(self, valueFromRaw(rawValue)); \ + } \ + STC_INLINE void \ + cdeq_##X##_pop_front(cdeq_##X* self) { \ + valueDestroy(self->data++); \ + --_cdeq_size(self); \ + } \ \ STC_API cdeq_##X##_iter_t \ cdeq_##X##_insert_range_p(cdeq_##X* self, cdeq_##X##_value_t* pos, const cdeq_##X##_value_t* pfirst, const cdeq_##X##_value_t* pfinish); \ @@ -190,8 +208,11 @@ #define _c_implement_cdeq_7(X, Value, valueDestroy, RawValue, valueCompareRaw, valueToRaw, valueFromRaw) \ \ STC_DEF void \ - cdeq_##X##_push_n(cdeq_##X *self, const cdeq_##X##_input_t arr[], size_t size) { \ - cdeq_##X##_insert_range_p(self, self->data + cdeq_size(*self), arr, arr + size); \ + cdeq_##X##_push_n(cdeq_##X *self, const cdeq_##X##_input_t arr[], size_t n) { \ + _cdeq_##X##_expand(self, n, false); \ + _cdeq_size(self) += n; \ + cdeq_##X##_value_t* p = self->data + cdeq_size(*self); \ + for (size_t i=0; i < n; ++i) *p++ = valueFromRaw(arr[i]); \ } \ \ STC_DEF void \ @@ -209,7 +230,7 @@ } \ \ STC_DEF void \ - cdeq_##X##_expand(cdeq_##X* self, size_t n, bool front) { \ + _cdeq_##X##_expand(cdeq_##X* self, size_t n, bool front) { \ size_t len = cdeq_size(*self), cap = _cdeq_capacity(self); \ size_t nfront = self->data - self->base, nback = cap - (nfront + len); \ if (front && nfront >= n || !front && nback >= n) \ @@ -222,16 +243,16 @@ rep[0] = len; \ rep[1] = cap; \ } \ - size_t k = cap - (len + n); \ - size_t pos = front ? c_maxf(k*0.7, (float) k - nback) + n \ - : c_minf(k*0.3, nfront); \ + size_t unused = cap - (len + n); \ + size_t pos = front ? c_maxf(unused*0.7, (float) unused - nback) + n \ + : c_minf(unused*0.3, nfront); \ memmove(self->base + pos, self->data, len*sizeof(Value)); \ self->data = self->base + pos; \ } \ \ STC_DEF void \ cdeq_##X##_resize(cdeq_##X* self, size_t size, Value null_val) { \ - cdeq_##X##_expand(self, size, false); \ + _cdeq_##X##_expand(self, size, false); \ for (size_t i=cdeq_size(*self); idata[i] = null_val; \ if (self->data) _cdeq_size(self) = size; \ } \ @@ -239,14 +260,14 @@ STC_DEF void \ cdeq_##X##_push_front(cdeq_##X* self, Value value) { \ if (self->data == self->base) \ - cdeq_##X##_expand(self, 1, true); \ + _cdeq_##X##_expand(self, 1, true); \ _cdeq_size(self)++, --self->data; \ *self->data = value; \ } \ STC_DEF void \ cdeq_##X##_push_back(cdeq_##X* self, Value value) { \ if ((self->data - self->base) + cdeq_size(*self) == _cdeq_capacity(self)) \ - cdeq_##X##_expand(self, 1, false); \ + _cdeq_##X##_expand(self, 1, false); \ self->data[_cdeq_size(self)++] = value; \ } \ \ @@ -260,12 +281,17 @@ \ STC_DEF cdeq_##X##_iter_t \ cdeq_##X##_insert_range_p(cdeq_##X* self, cdeq_##X##_value_t* pos, const cdeq_##X##_value_t* first, const cdeq_##X##_value_t* finish) { \ - size_t len = finish - first, idx = pos - self->data, size = cdeq_size(*self); \ - cdeq_##X##_expand(self, len, false); \ - pos = self->data + idx; \ + size_t n = finish - first, idx = pos - self->data, size = cdeq_size(*self); \ + bool is_front = (pos == self->data); \ + _cdeq_##X##_expand(self, n, is_front); \ + if (is_front) \ + pos = (self->data -= n); \ + else { \ + pos = self->data + idx; \ + memmove(pos + n, pos, (size - idx)*sizeof(Value)); \ + } \ cdeq_##X##_iter_t it = {pos}; \ - memmove(pos + len, pos, (size - idx) * sizeof(Value)); \ - _cdeq_size(self) += len; \ + _cdeq_size(self) += n; \ while (first != finish) \ *pos++ = valueFromRaw(valueToRaw(first++)); \ return it; \ diff --git a/stc/cvec.h b/stc/cvec.h index 049efade..05963cae 100644 --- a/stc/cvec.h +++ b/stc/cvec.h @@ -87,9 +87,14 @@ cvec_##X##_reserve(&x, size); \ return x; \ } \ -\ STC_API cvec_##X \ cvec_##X##_clone(cvec_##X vec); \ +\ + STC_INLINE void \ + cvec_##X##_shrink_to_fit(cvec_##X *self) { \ + cvec_##X x = cvec_##X##_clone(*self); \ + cvec_##X##_del(self); *self = x; \ + } \ STC_API void \ cvec_##X##_push_n(cvec_##X *self, const cvec_##X##_input_t arr[], size_t size); \ STC_API void \ @@ -193,8 +198,11 @@ #define _c_implement_cvec_7(X, Value, valueDestroy, RawValue, valueCompareRaw, valueToRaw, valueFromRaw) \ \ STC_DEF void \ - cvec_##X##_push_n(cvec_##X *self, const cvec_##X##_input_t arr[], size_t size) { \ - cvec_##X##_insert_range_p(self, self->data + cvec_size(*self), arr, arr + size); \ + cvec_##X##_push_n(cvec_##X *self, const cvec_##X##_input_t arr[], size_t n) { \ + cvec_##X##_reserve(self, cvec_size(*self) + n); \ + _cvec_size(self) += n; \ + cvec_##X##_value_t* p = self->data + cvec_size(*self); \ + for (size_t i=0; i < n; ++i) *p++ = valueFromRaw(arr[i]); \ } \ \ STC_DEF void \ @@ -212,8 +220,8 @@ \ STC_DEF void \ cvec_##X##_reserve(cvec_##X* self, size_t cap) { \ - size_t len = cvec_size(*self); \ - if (cap >= len) { \ + if (cap > cvec_capacity(*self)) { \ + size_t len = cvec_size(*self); \ size_t* rep = (size_t *) c_realloc(_cvec_alloced(self->data), 2 * sizeof(size_t) + cap * sizeof(Value)); \ self->data = (Value *) (rep + 2); \ rep[0] = len; \ -- cgit v1.2.3