From fc19b966a73793e73a898af4d2974d289fbc555c Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Tue, 7 Sep 2021 18:23:52 +0200 Subject: Added cdeq.h + test. Unsure if the rest should be kept as oldstyle (using). --- include/stc/cdeq.h | 600 ++++++++++++++++++++++---------------------- include/stc/csmap.h | 26 +- include/stc/cvec.h | 17 +- include/stc/test_new_deq.c | 57 +++++ include/stc/test_new_smap.c | 45 ++-- 5 files changed, 406 insertions(+), 339 deletions(-) create mode 100644 include/stc/test_new_deq.c diff --git a/include/stc/cdeq.h b/include/stc/cdeq.h index 65e2cd0d..b941d6c5 100644 --- a/include/stc/cdeq.h +++ b/include/stc/cdeq.h @@ -20,317 +20,319 @@ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ -#ifndef CDEQ_H_INCLUDED -#define CDEQ_H_INCLUDED +#ifndef CDEQ_H_INCLUDED #include "ccommon.h" +#include "forward.h" #include #include -\ - defTypes( _c_cdeq_types(Self, i_val); ) \ - typedef i_valraw cx_rawvalue_t; \ -\ - STC_API Self cx_memb(_init)(void); \ - STC_API Self cx_memb(_clone)(Self cx); \ - STC_API void cx_memb(_clear)(Self* self); \ - STC_API void cx_memb(_del)(Self* self); \ - STC_API cx_iter_t cx_memb(_find_in)(cx_iter_t p1, cx_iter_t p2, i_valraw raw); \ - STC_API int cx_memb(_value_compare)(const cx_value_t* x, const cx_value_t* y); \ - STC_API void cx_memb(_push_back)(Self* self, i_val value); \ - STC_API void cx_memb(_push_front)(Self* self, i_val value); \ - STC_API cx_iter_t cx_memb(_erase_range_p)(Self* self, cx_value_t* p1, cx_value_t* p2); \ - STC_API cx_iter_t cx_memb(_insert_range_p)(Self* self, cx_value_t* pos, \ - const cx_value_t* p1, const cx_value_t* p2, bool clone); \ - STC_API cx_iter_t cx_memb(_emplace_range_p)(Self* self, cx_value_t* pos, \ - const cx_rawvalue_t* p1, const cx_rawvalue_t* p2); \ - STC_API void cx_memb(_expand_right_)(Self* self, size_t idx, size_t n); \ -\ - STC_INLINE bool cx_memb(_empty)(Self cx) { return !_cdeq_rep(&cx)->size; } \ - STC_INLINE size_t cx_memb(_size)(Self cx) { return _cdeq_rep(&cx)->size; } \ - STC_INLINE size_t cx_memb(_capacity)(Self cx) { return _cdeq_rep(&cx)->cap; } \ - STC_INLINE void cx_memb(_swap)(Self* a, Self* b) {c_swap(Self, *a, *b); } \ - STC_INLINE i_val cx_memb(_value_fromraw)(i_valraw raw) { return i_valfrom(raw); } \ - STC_INLINE i_valraw cx_memb(_value_toraw)(cx_value_t* pval) { return i_valto(pval); } \ - STC_INLINE i_val cx_memb(_value_clone)(i_val val) \ - { return i_valfrom(i_valto(&val)); } \ - STC_INLINE void cx_memb(_emplace_back)(Self* self, i_valraw raw) \ - { cx_memb(_push_back)(self, i_valfrom(raw)); } \ - STC_INLINE void cx_memb(_emplace_front)(Self* self, i_valraw raw) \ - { cx_memb(_push_front)(self, i_valfrom(raw)); } \ - STC_INLINE void cx_memb(_pop_back)(Self* self) \ - {i_valdel(&self->data[--_cdeq_rep(self)->size]); } \ - STC_INLINE void cx_memb(_pop_front)(Self* self) \ - {i_valdel(self->data++); --_cdeq_rep(self)->size; } \ - STC_INLINE cx_value_t* cx_memb(_front)(const Self* self) { return self->data; } \ - STC_INLINE cx_value_t* cx_memb(_back)(const Self* self) \ - { return self->data + _cdeq_rep(self)->size - 1; } \ - STC_INLINE cx_value_t* cx_memb(_at)(const Self* self, size_t idx) \ - {assert(idx < _cdeq_rep(self)->size); return self->data + idx; } \ - STC_INLINE cx_iter_t cx_memb(_begin)(const Self* self) \ - { return c_make(cx_iter_t){self->data}; } \ - STC_INLINE cx_iter_t cx_memb(_end)(const Self* self) \ - { return c_make(cx_iter_t){self->data + _cdeq_rep(self)->size}; } \ - STC_INLINE void cx_memb(_next)(cx_iter_t* it) {++it->ref; } \ - STC_INLINE cx_iter_t cx_memb(_adv)(cx_iter_t it, intptr_t offs) {it.ref += offs; return it; } \ - STC_INLINE size_t cx_memb(_idx)(Self cx, cx_iter_t it) { return it.ref - cx.data; } \ -\ - STC_INLINE Self \ - cx_memb(_with_capacity)(size_t n) { \ - Self cx = cx_memb(_init)(); \ - cx_memb(_expand_right_)(&cx, 0, n); \ - return cx; \ - } \ -\ - STC_INLINE void \ - cx_memb(_reserve)(Self* self, size_t n) { \ - size_t sz = _cdeq_rep(self)->size; \ - if (n > sz) cx_memb(_expand_right_)(self, sz, n - sz); \ - } \ -\ - STC_INLINE void \ - cx_memb(_shrink_to_fit)(Self *self) { \ - Self cx = cx_memb(_clone)(*self); \ - cx_memb(_del)(self); *self = cx; \ - } \ -\ - STC_INLINE cx_iter_t \ - cx_memb(_insert)(Self* self, size_t idx, i_val value) { \ - return cx_memb(_insert_range_p)(self, self->data + idx, &value, &value + 1, false); \ - } \ - STC_INLINE cx_iter_t \ - cx_memb(_insert_n)(Self* self, size_t idx, const cx_value_t arr[], size_t n) { \ - return cx_memb(_insert_range_p)(self, self->data + idx, arr, arr + n, false); \ - } \ - STC_INLINE cx_iter_t \ - cx_memb(_insert_at)(Self* self, cx_iter_t it, i_val value) { \ - return cx_memb(_insert_range_p)(self, it.ref, &value, &value + 1, false); \ - } \ -\ - STC_INLINE cx_iter_t \ - cx_memb(_emplace)(Self* self, size_t idx, i_valraw raw) { \ - return cx_memb(_emplace_range_p)(self, self->data + idx, &raw, &raw + 1); \ - } \ - STC_INLINE cx_iter_t \ - cx_memb(_emplace_n)(Self* self, size_t idx, const cx_rawvalue_t arr[], size_t n) { \ - return cx_memb(_emplace_range_p)(self, self->data + idx, arr, arr + n); \ - } \ - STC_INLINE cx_iter_t \ - cx_memb(_emplace_at)(Self* self, cx_iter_t it, i_valraw raw) { \ - return cx_memb(_emplace_range_p)(self, it.ref, &raw, &raw + 1); \ - } \ - STC_INLINE cx_iter_t \ - cx_memb(_emplace_range)(Self* self, cx_iter_t it, cx_iter_t it1, cx_iter_t it2) { \ - return cx_memb(_insert_range_p)(self, it.ref, it1.ref, it2.ref, true); \ - } \ - STC_INLINE void \ - cx_memb(_emplace_items)(Self *self, const cx_rawvalue_t arr[], size_t n) { \ - cx_memb(_emplace_range_p)(self, self->data + _cdeq_rep(self)->size, arr, arr + n); \ - } \ -\ - STC_INLINE cx_iter_t \ - cx_memb(_erase)(Self* self, size_t idx) { \ - return cx_memb(_erase_range_p)(self, self->data + idx, self->data + idx + 1); \ - } \ - STC_INLINE cx_iter_t \ - cx_memb(_erase_n)(Self* self, size_t idx, size_t n) { \ - return cx_memb(_erase_range_p)(self, self->data + idx, self->data + idx + n); \ - } \ - STC_INLINE cx_iter_t \ - cx_memb(_erase_at)(Self* self, cx_iter_t it) { \ - return cx_memb(_erase_range_p)(self, it.ref, it.ref + 1); \ - } \ - STC_INLINE cx_iter_t \ - cx_memb(_erase_range)(Self* self, cx_iter_t it1, cx_iter_t it2) { \ - return cx_memb(_erase_range_p)(self, it1.ref, it2.ref); \ - } \ -\ - STC_INLINE cx_iter_t \ - cx_memb(_find)(const Self* self, i_valraw raw) { \ - return cx_memb(_find_in)(cx_memb(_begin)(self), cx_memb(_end)(self), raw); \ - } \ -\ - STC_INLINE cx_value_t* \ - cx_memb(_get)(const Self* self, i_valraw raw) { \ - cx_iter_t end = cx_memb(_end)(self); \ - cx_value_t* val = cx_memb(_find_in)(cx_memb(_begin)(self), end, raw).ref; \ - return val == end.ref ? NULL : val; \ - } \ -\ - STC_INLINE void \ - cx_memb(_sort_range)(cx_iter_t i1, cx_iter_t i2, \ - int(*_cmp_)(const cx_value_t*, const cx_value_t*)) { \ - qsort(i1.ref, i2.ref - i1.ref, sizeof *i1.ref, (int(*)(const void*, const void*)) _cmp_); \ - } \ -\ - STC_INLINE void \ - cx_memb(_sort)(Self* self) { \ - cx_memb(_sort_range)(cx_memb(_begin)(self), cx_memb(_end)(self), cx_memb(_value_compare)); \ - } \ -\ - _c_implement_cdeq(Self, i_val, i_cmp, i_valdel, i_valfrom, i_valto, i_valraw) \ - struct stc_trailing_semicolon +struct cdeq_rep { size_t size, cap; void* base[]; }; +#define cdeq_rep_(self) c_container_of((self)->_base, struct cdeq_rep, base) +#endif // CDEQ_H_INCLUDED -/* -------------------------- IMPLEMENTATION ------------------------- */ +#define i_module cdeq +#include "template.h" + +#if !defined i_fwd + cx_deftypes(_c_cdeq_types, Self, i_val); +#endif +typedef i_valraw cx_rawvalue_t; + +STC_API Self cx_memb(_init)(void); +STC_API Self cx_memb(_clone)(Self cx); +STC_API void cx_memb(_clear)(Self* self); +STC_API void cx_memb(_del)(Self* self); +STC_API cx_iter_t cx_memb(_find_in)(cx_iter_t p1, cx_iter_t p2, i_valraw raw); +STC_API int cx_memb(_value_compare)(const cx_value_t* x, const cx_value_t* y); +STC_API void cx_memb(_push_back)(Self* self, i_val value); +STC_API void cx_memb(_push_front)(Self* self, i_val value); +STC_API cx_iter_t cx_memb(_erase_range_p)(Self* self, cx_value_t* p1, cx_value_t* p2); +STC_API cx_iter_t cx_memb(_insert_range_p)(Self* self, cx_value_t* pos, + const cx_value_t* p1, const cx_value_t* p2, bool clone); +STC_API cx_iter_t cx_memb(_emplace_range_p)(Self* self, cx_value_t* pos, + const cx_rawvalue_t* p1, const cx_rawvalue_t* p2); +STC_API void cx_memb(_expand_right_)(Self* self, size_t idx, size_t n); + +STC_INLINE bool cx_memb(_empty)(Self cx) { return !cdeq_rep_(&cx)->size; } +STC_INLINE size_t cx_memb(_size)(Self cx) { return cdeq_rep_(&cx)->size; } +STC_INLINE size_t cx_memb(_capacity)(Self cx) { return cdeq_rep_(&cx)->cap; } +STC_INLINE void cx_memb(_swap)(Self* a, Self* b) {c_swap(Self, *a, *b); } +STC_INLINE i_val cx_memb(_value_fromraw)(i_valraw raw) { return i_valfrom(raw); } +STC_INLINE i_valraw cx_memb(_value_toraw)(cx_value_t* pval) { return i_valto(pval); } +STC_INLINE i_val cx_memb(_value_clone)(i_val val) + { return i_valfrom(i_valto(&val)); } +STC_INLINE void cx_memb(_emplace_back)(Self* self, i_valraw raw) + { cx_memb(_push_back)(self, i_valfrom(raw)); } +STC_INLINE void cx_memb(_emplace_front)(Self* self, i_valraw raw) + { cx_memb(_push_front)(self, i_valfrom(raw)); } +STC_INLINE void cx_memb(_pop_back)(Self* self) + { i_valdel(&self->data[--cdeq_rep_(self)->size]); } +STC_INLINE void cx_memb(_pop_front)(Self* self) + { i_valdel(self->data++); --cdeq_rep_(self)->size; } +STC_INLINE cx_value_t* cx_memb(_front)(const Self* self) { return self->data; } +STC_INLINE cx_value_t* cx_memb(_back)(const Self* self) + { return self->data + cdeq_rep_(self)->size - 1; } +STC_INLINE cx_value_t* cx_memb(_at)(const Self* self, size_t idx) + { assert(idx < cdeq_rep_(self)->size); return self->data + idx; } +STC_INLINE cx_iter_t cx_memb(_begin)(const Self* self) + { return c_make(cx_iter_t){self->data}; } +STC_INLINE cx_iter_t cx_memb(_end)(const Self* self) + { return c_make(cx_iter_t){self->data + cdeq_rep_(self)->size}; } +STC_INLINE void cx_memb(_next)(cx_iter_t* it) { ++it->ref; } +STC_INLINE cx_iter_t cx_memb(_adv)(cx_iter_t it, intptr_t offs) { it.ref += offs; return it; } +STC_INLINE size_t cx_memb(_idx)(Self cx, cx_iter_t it) { return it.ref - cx.data; } + +STC_INLINE Self +cx_memb(_with_capacity)(size_t n) { + Self cx = cx_memb(_init)(); + cx_memb(_expand_right_)(&cx, 0, n); + return cx; +} + +STC_INLINE void +cx_memb(_reserve)(Self* self, size_t n) { + size_t sz = cdeq_rep_(self)->size; + if (n > sz) cx_memb(_expand_right_)(self, sz, n - sz); +} -#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) +STC_INLINE void +cx_memb(_shrink_to_fit)(Self *self) { + Self cx = cx_memb(_clone)(*self); + cx_memb(_del)(self); *self = cx; +} +STC_INLINE cx_iter_t +cx_memb(_insert)(Self* self, size_t idx, i_val value) { + return cx_memb(_insert_range_p)(self, self->data + idx, &value, &value + 1, false); +} +STC_INLINE cx_iter_t +cx_memb(_insert_n)(Self* self, size_t idx, const cx_value_t arr[], size_t n) { + return cx_memb(_insert_range_p)(self, self->data + idx, arr, arr + n, false); +} +STC_INLINE cx_iter_t +cx_memb(_insert_at)(Self* self, cx_iter_t it, i_val value) { + return cx_memb(_insert_range_p)(self, it.ref, &value, &value + 1, false); +} + +STC_INLINE cx_iter_t +cx_memb(_emplace)(Self* self, size_t idx, i_valraw raw) { + return cx_memb(_emplace_range_p)(self, self->data + idx, &raw, &raw + 1); +} +STC_INLINE cx_iter_t +cx_memb(_emplace_n)(Self* self, size_t idx, const cx_rawvalue_t arr[], size_t n) { + return cx_memb(_emplace_range_p)(self, self->data + idx, arr, arr + n); +} +STC_INLINE cx_iter_t +cx_memb(_emplace_at)(Self* self, cx_iter_t it, i_valraw raw) { + return cx_memb(_emplace_range_p)(self, it.ref, &raw, &raw + 1); +} +STC_INLINE cx_iter_t +cx_memb(_emplace_range)(Self* self, cx_iter_t it, cx_iter_t it1, cx_iter_t it2) { + return cx_memb(_insert_range_p)(self, it.ref, it1.ref, it2.ref, true); +} +STC_INLINE void +cx_memb(_emplace_items)(Self *self, const cx_rawvalue_t arr[], size_t n) { + cx_memb(_emplace_range_p)(self, self->data + cdeq_rep_(self)->size, arr, arr + n); +} + +STC_INLINE cx_iter_t +cx_memb(_erase)(Self* self, size_t idx) { + return cx_memb(_erase_range_p)(self, self->data + idx, self->data + idx + 1); +} +STC_INLINE cx_iter_t +cx_memb(_erase_n)(Self* self, size_t idx, size_t n) { + return cx_memb(_erase_range_p)(self, self->data + idx, self->data + idx + n); +} +STC_INLINE cx_iter_t +cx_memb(_erase_at)(Self* self, cx_iter_t it) { + return cx_memb(_erase_range_p)(self, it.ref, it.ref + 1); +} +STC_INLINE cx_iter_t +cx_memb(_erase_range)(Self* self, cx_iter_t it1, cx_iter_t it2) { + return cx_memb(_erase_range_p)(self, it1.ref, it2.ref); +} + +STC_INLINE cx_iter_t +cx_memb(_find)(const Self* self, i_valraw raw) { + return cx_memb(_find_in)(cx_memb(_begin)(self), cx_memb(_end)(self), raw); +} + +STC_INLINE cx_value_t* +cx_memb(_get)(const Self* self, i_valraw raw) { + cx_iter_t end = cx_memb(_end)(self); + cx_value_t* val = cx_memb(_find_in)(cx_memb(_begin)(self), end, raw).ref; + return val == end.ref ? NULL : val; +} + +STC_INLINE void +cx_memb(_sort_range)(cx_iter_t i1, cx_iter_t i2, + int(*_cmp_)(const cx_value_t*, const cx_value_t*)) { + qsort(i1.ref, i2.ref - i1.ref, sizeof *i1.ref, (int(*)(const void*, const void*)) _cmp_); +} + +STC_INLINE void +cx_memb(_sort)(Self* self) { + cx_memb(_sort_range)(cx_memb(_begin)(self), cx_memb(_end)(self), cx_memb(_value_compare)); +} + +/* -------------------------- IMPLEMENTATION ------------------------- */ +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) || defined(i_imp) + +#ifndef CDEQ_H_INCLUDED +#define CDEQ_H_INCLUDED static struct cdeq_rep _cdeq_sentinel = {0, 0}; #define _cdeq_nfront(self) ((self)->data - (self)->_base) +#endif + +STC_DEF Self +cx_memb(_init)(void) { + cx_value_t *b = (cx_value_t *) _cdeq_sentinel.base; + return c_make(Self){b, b}; +} -#define _c_implement_cdeq(Self, i_val, i_cmp, i_valdel, i_valfrom, i_valto, i_valraw) \ -\ - STC_DEF Self \ - cx_memb(_init)(void) { \ - cx_value_t *b = (cx_value_t *) _cdeq_sentinel.base; \ - return c_make(Self){b, b}; \ - } \ -\ - STC_DEF void \ - cx_memb(_clear)(Self* self) { \ - struct cdeq_rep* rep = _cdeq_rep(self); if (rep->cap) { \ - for (cx_value_t *p = self->data, *q = p + rep->size; p != q; ++p) \ - i_valdel(p); \ - rep->size = 0; \ - } \ - } \ -\ - STC_DEF void \ - cx_memb(_del)(Self* self) { \ - cx_memb(_clear)(self); \ - if (_cdeq_rep(self)->cap) \ - c_free(_cdeq_rep(self)); \ - } \ -\ - STC_DEF size_t \ - cx_memb(_realloc_)(Self* self, size_t n) { \ - struct cdeq_rep* rep = _cdeq_rep(self); \ - size_t sz = rep->size, cap = (size_t) (sz*1.7) + n + 7; \ - size_t nfront = _cdeq_nfront(self); \ - rep = (struct cdeq_rep*) c_realloc(rep->cap ? rep : NULL, \ - offsetof(struct cdeq_rep, base) + cap*sizeof(i_val)); \ - rep->size = sz, rep->cap = cap; \ - self->_base = (cx_value_t *) rep->base; \ - self->data = self->_base + nfront; \ - return cap; \ - } \ -\ - STC_DEF void \ - cx_memb(_expand_left_)(Self* self, size_t idx, size_t n) { \ - struct cdeq_rep* rep = _cdeq_rep(self); \ - size_t sz = rep->size, cap = rep->cap; \ - size_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront; \ - if (nfront >= n) { \ - self->data = (cx_value_t *) memmove(self->data - n, self->data, idx*sizeof(i_val)); \ - } else { \ - if (sz*1.3 + n > cap) cap = cx_memb(_realloc_)(self, n); \ - size_t unused = cap - (sz + n); \ - size_t pos = (nback*2 < unused) ? unused - nback : unused/2; \ - memmove(self->_base + pos + idx + n, self->data + idx, (sz - idx)*sizeof(i_val)); \ - self->data = (cx_value_t *) memmove(self->_base + pos, self->data, idx*sizeof(i_val)); \ - } \ - } \ -\ - STC_DEF void \ - cx_memb(_expand_right_)(Self* self, size_t idx, size_t n) { \ - struct cdeq_rep* rep = _cdeq_rep(self); \ - size_t sz = rep->size, cap = rep->cap; \ - size_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront; \ - if (nback >= n || sz*1.3 + n > cap && cx_memb(_realloc_)(self, n)) { \ - memmove(self->data + idx + n, self->data + idx, (sz - idx)*sizeof(i_val)); \ - } else { \ - size_t unused = cap - (sz + n); \ - size_t pos = (nfront*2 < unused) ? nfront : unused/2; \ - memmove(self->_base + pos, self->data, idx*sizeof(i_val)); \ - memmove(self->data + pos + idx + n, self->data + idx, (sz - idx)*sizeof(i_val)); \ - self->data = ((cx_value_t *) self->_base) + pos; \ - } \ - } \ -\ - STC_DEF cx_value_t* \ - cx_memb(_insert_space_)(Self* self, cx_value_t* pos, size_t n) { \ - size_t idx = pos - self->data; \ - if (idx*2 < _cdeq_rep(self)->size) cx_memb(_expand_left_)(self, idx, n); \ - else cx_memb(_expand_right_)(self, idx, n); \ - if (n) _cdeq_rep(self)->size += n; /* do only if size > 0 */ \ - return self->data + idx; \ - } \ -\ - STC_DEF void \ - cx_memb(_push_front)(Self* self, i_val value) { \ - if (self->data == self->_base) \ - cx_memb(_expand_left_)(self, 0, 1); \ - else \ - --self->data; \ - *self->data = value; \ - ++_cdeq_rep(self)->size; \ - } \ -\ - STC_DEF void \ - cx_memb(_push_back)(Self* self, i_val value) { \ - struct cdeq_rep* rep = _cdeq_rep(self); \ - if (_cdeq_nfront(self) + rep->size == rep->cap) \ - cx_memb(_expand_right_)(self, rep->size, 1); \ - self->data[_cdeq_rep(self)->size++] = value; \ - } \ -\ - STC_DEF Self \ - cx_memb(_clone)(Self cx) { \ - size_t sz = _cdeq_rep(&cx)->size; \ - Self out = cx_memb(_with_capacity)(sz); \ - cx_memb(_insert_range_p)(&out, out.data, cx.data, cx.data + sz, true); \ - return out; \ - } \ -\ - STC_DEF cx_iter_t \ - cx_memb(_insert_range_p)(Self* self, cx_value_t* pos, const cx_value_t* p1, \ - const cx_value_t* p2, bool clone) { \ - pos = cx_memb(_insert_space_)(self, pos, p2 - p1); \ - cx_iter_t it = {pos}; \ - if (clone) while (p1 != p2) *pos++ = i_valfrom(i_valto(p1++)); \ - else memcpy(pos, p1, (p2 - p1)*sizeof *p1); \ - return it; \ - } \ -\ - STC_DEF cx_iter_t \ - cx_memb(_emplace_range_p)(Self* self, cx_value_t* pos, const cx_rawvalue_t* p1, const cx_rawvalue_t* p2) { \ - pos = cx_memb(_insert_space_)(self, pos, p2 - p1); \ - cx_iter_t it = {pos}; \ - while (p1 != p2) *pos++ = i_valfrom(*p1++); \ - return it; \ - } \ -\ - STC_DEF cx_iter_t \ - cx_memb(_erase_range_p)(Self* self, cx_value_t* p1, cx_value_t* p2) { \ - size_t n = p2 - p1; \ - if (n > 0) { \ - cx_value_t* p = p1, *end = self->data + _cdeq_rep(self)->size; \ - while (p != p2) i_valdel(p++); \ - if (p1 == self->data) self->data += n; \ - else memmove(p1, p2, (end - p2) * sizeof(i_val)); \ - _cdeq_rep(self)->size -= n; \ - } \ - return c_make(cx_iter_t){p1}; \ - } \ -\ - STC_DEF cx_iter_t \ - cx_memb(_find_in)(cx_iter_t i1, cx_iter_t i2, i_valraw raw) { \ - for (; i1.ref != i2.ref; ++i1.ref) { \ - i_valraw r = i_valto(i1.ref); \ - if (i_cmp(&raw, &r) == 0) return i1; \ - } \ - return i2; \ - } \ -\ - STC_DEF int \ - cx_memb(_value_compare)(const cx_value_t* x, const cx_value_t* y) { \ - i_valraw rx = i_valto(x); \ - i_valraw ry = i_valto(y); \ - return i_cmp(&rx, &ry); \ +STC_DEF void +cx_memb(_clear)(Self* self) { + struct cdeq_rep* rep = cdeq_rep_(self); if (rep->cap) { + for (cx_value_t *p = self->data, *q = p + rep->size; p != q; ++p) + i_valdel(p); + rep->size = 0; } +} -#else -#define _c_implement_cdeq(Self, i_val, i_cmp, i_valdel, i_valfrom, i_valto, i_valraw) -#endif +STC_DEF void +cx_memb(_del)(Self* self) { + cx_memb(_clear)(self); + if (cdeq_rep_(self)->cap) + c_free(cdeq_rep_(self)); +} + +STC_DEF size_t +cx_memb(_realloc_)(Self* self, size_t n) { + struct cdeq_rep* rep = cdeq_rep_(self); + size_t sz = rep->size, cap = (size_t) (sz*1.7) + n + 7; + size_t nfront = _cdeq_nfront(self); + rep = (struct cdeq_rep*) c_realloc(rep->cap ? rep : NULL, + offsetof(struct cdeq_rep, base) + cap*sizeof(i_val)); + rep->size = sz, rep->cap = cap; + self->_base = (cx_value_t *) rep->base; + self->data = self->_base + nfront; + return cap; +} + +STC_DEF void +cx_memb(_expand_left_)(Self* self, size_t idx, size_t n) { + struct cdeq_rep* rep = cdeq_rep_(self); + size_t sz = rep->size, cap = rep->cap; + size_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront; + if (nfront >= n) { + self->data = (cx_value_t *) memmove(self->data - n, self->data, idx*sizeof(i_val)); + } else { + if (sz*1.3 + n > cap) cap = cx_memb(_realloc_)(self, n); + size_t unused = cap - (sz + n); + size_t pos = (nback*2 < unused) ? unused - nback : unused/2; + memmove(self->_base + pos + idx + n, self->data + idx, (sz - idx)*sizeof(i_val)); + self->data = (cx_value_t *) memmove(self->_base + pos, self->data, idx*sizeof(i_val)); + } +} + +STC_DEF void +cx_memb(_expand_right_)(Self* self, size_t idx, size_t n) { + struct cdeq_rep* rep = cdeq_rep_(self); + size_t sz = rep->size, cap = rep->cap; + size_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront; + if (nback >= n || sz*1.3 + n > cap && cx_memb(_realloc_)(self, n)) { + memmove(self->data + idx + n, self->data + idx, (sz - idx)*sizeof(i_val)); + } else { + size_t unused = cap - (sz + n); + size_t pos = (nfront*2 < unused) ? nfront : unused/2; + memmove(self->_base + pos, self->data, idx*sizeof(i_val)); + memmove(self->data + pos + idx + n, self->data + idx, (sz - idx)*sizeof(i_val)); + self->data = ((cx_value_t *) self->_base) + pos; + } +} + +STC_DEF cx_value_t* +cx_memb(_insert_space_)(Self* self, cx_value_t* pos, size_t n) { + size_t idx = pos - self->data; + if (idx*2 < cdeq_rep_(self)->size) cx_memb(_expand_left_)(self, idx, n); + else cx_memb(_expand_right_)(self, idx, n); + if (n) cdeq_rep_(self)->size += n; /* do only if size > 0 */ + return self->data + idx; +} + +STC_DEF void +cx_memb(_push_front)(Self* self, i_val value) { + if (self->data == self->_base) + cx_memb(_expand_left_)(self, 0, 1); + else + --self->data; + *self->data = value; + ++cdeq_rep_(self)->size; +} + +STC_DEF void +cx_memb(_push_back)(Self* self, i_val value) { + struct cdeq_rep* rep = cdeq_rep_(self); + if (_cdeq_nfront(self) + rep->size == rep->cap) + cx_memb(_expand_right_)(self, rep->size, 1); + self->data[cdeq_rep_(self)->size++] = value; +} + +STC_DEF Self +cx_memb(_clone)(Self cx) { + size_t sz = cdeq_rep_(&cx)->size; + Self out = cx_memb(_with_capacity)(sz); + cx_memb(_insert_range_p)(&out, out.data, cx.data, cx.data + sz, true); + return out; +} + +STC_DEF cx_iter_t +cx_memb(_insert_range_p)(Self* self, cx_value_t* pos, const cx_value_t* p1, + const cx_value_t* p2, bool clone) { + pos = cx_memb(_insert_space_)(self, pos, p2 - p1); + cx_iter_t it = {pos}; + if (clone) while (p1 != p2) *pos++ = i_valfrom(i_valto(p1++)); + else memcpy(pos, p1, (p2 - p1)*sizeof *p1); + return it; +} + +STC_DEF cx_iter_t +cx_memb(_emplace_range_p)(Self* self, cx_value_t* pos, const cx_rawvalue_t* p1, const cx_rawvalue_t* p2) { + pos = cx_memb(_insert_space_)(self, pos, p2 - p1); + cx_iter_t it = {pos}; + while (p1 != p2) *pos++ = i_valfrom(*p1++); + return it; +} + +STC_DEF cx_iter_t +cx_memb(_erase_range_p)(Self* self, cx_value_t* p1, cx_value_t* p2) { + size_t n = p2 - p1; + if (n > 0) { + cx_value_t* p = p1, *end = self->data + cdeq_rep_(self)->size; + while (p != p2) i_valdel(p++); + if (p1 == self->data) self->data += n; + else memmove(p1, p2, (end - p2) * sizeof(i_val)); + cdeq_rep_(self)->size -= n; + } + return c_make(cx_iter_t){p1}; +} + +STC_DEF cx_iter_t +cx_memb(_find_in)(cx_iter_t i1, cx_iter_t i2, i_valraw raw) { + for (; i1.ref != i2.ref; ++i1.ref) { + i_valraw r = i_valto(i1.ref); + if (i_cmp(&raw, &r) == 0) return i1; + } + return i2; +} + +STC_DEF int +cx_memb(_value_compare)(const cx_value_t* x, const cx_value_t* y) { + i_valraw rx = i_valto(x); + i_valraw ry = i_valto(y); + return i_cmp(&rx, &ry); +} #endif +#include "template.h" diff --git a/include/stc/csmap.h b/include/stc/csmap.h index 9896340c..dbee8fc9 100644 --- a/include/stc/csmap.h +++ b/include/stc/csmap.h @@ -24,23 +24,27 @@ // Sorted/Ordered set and map - implemented as an AA-tree. /* #include +#include + +#define i_tag sx // Sorted map +#define i_key_str +#define i_val double #include -using_csmap(mx, int, char); // Sorted map int main(void) { - c_forvar (csmap_mx m = csmap_mx_init(), csmap_mx_del(&m)) + c_forvar (csmap_sx m = csmap_sx_init(), csmap_sx_del(&m)) { - csmap_mx_insert(&m, 5, 'a'); - csmap_mx_insert(&m, 8, 'b'); - csmap_mx_insert(&m, 12, 'c'); + csmap_sx_emplace(&m, "Testing one", 1.234); + csmap_sx_emplace(&m, "Testing two", 12.34); + csmap_sx_emplace(&m, "Testing three", 123.4); - csmap_mx_iter_t it = csmap_mx_find(&m, 10); // none - char val = csmap_mx_find(&m, 5).ref->second; - csmap_mx_put(&m, 5, 'd'); // update - csmap_mx_erase(&m, 8); + csmap_sx_value_t *v = csmap_sx_get(&m, "Testing five"); // NULL + double num = *csmap_sx_at(&m, "Testing one"); + csmap_sx_emplace_or_assign(&m, "Testing three", 1000.0); // update + csmap_sx_erase(&m, "Testing two"); - c_foreach (i, csmap_mx, m) - printf("map %d: %c\n", i.ref->first, i.ref->second); + c_foreach (i, csmap_sx, m) + printf("map %s: %g\n", i.ref->first.str, i.ref->second); } } */ diff --git a/include/stc/cvec.h b/include/stc/cvec.h index b79191f9..513870ed 100644 --- a/include/stc/cvec.h +++ b/include/stc/cvec.h @@ -63,8 +63,8 @@ int main() { #include #include -struct cvec_Rep_ { size_t size, cap; void* data[]; }; -#define cvec_rep_(self) c_container_of((self)->data, struct cvec_Rep_, data) +struct cvec_rep { size_t size, cap; void* data[]; }; +#define cvec_rep_(self) c_container_of((self)->data, struct cvec_rep, data) #endif // CVEC_H_INCLUDED #define i_module cvec @@ -218,12 +218,11 @@ cx_memb(_sort)(Self* self) { } /* -------------------------- IMPLEMENTATION ------------------------- */ - #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) || defined(i_imp) #ifndef CVEC_H_INCLUDED #define CVEC_H_INCLUDED -static struct cvec_Rep_ _cvec_sentinel = {0, 0}; +static struct cvec_rep _cvec_sentinel = {0, 0}; #endif STC_DEF Self @@ -234,7 +233,7 @@ cx_memb(_init)(void) { STC_DEF void cx_memb(_clear)(Self* self) { - struct cvec_Rep_* rep = cvec_rep_(self); if (rep->cap) { + struct cvec_rep* rep = cvec_rep_(self); if (rep->cap) { for (cx_value_t *p = self->data, *q = p + rep->size; p != q; ++p) i_valdel(p); rep->size = 0; @@ -250,11 +249,11 @@ cx_memb(_del)(Self* self) { STC_DEF void cx_memb(_reserve)(Self* self, size_t cap) { - struct cvec_Rep_* rep = cvec_rep_(self); + struct cvec_rep* rep = cvec_rep_(self); size_t len = rep->size, oldcap = rep->cap; if (cap > oldcap) { - rep = (struct cvec_Rep_*) c_realloc(oldcap ? rep : NULL, - offsetof(struct cvec_Rep_, data) + cap*sizeof(i_val)); + rep = (struct cvec_rep*) c_realloc(oldcap ? rep : NULL, + offsetof(struct cvec_rep, data) + cap*sizeof(i_val)); self->data = (cx_value_t*) rep->data; rep->size = len; rep->cap = cap; @@ -264,7 +263,7 @@ cx_memb(_reserve)(Self* self, size_t cap) { STC_DEF void cx_memb(_resize)(Self* self, size_t len, i_val null_val) { cx_memb(_reserve)(self, len); - struct cvec_Rep_* rep = cvec_rep_(self); + struct cvec_rep* rep = cvec_rep_(self); size_t i, n = rep->size; for (i = len; i < n; ++i) i_valdel(self->data + i); for (i = n; i < len; ++i) self->data[i] = null_val; diff --git a/include/stc/test_new_deq.c b/include/stc/test_new_deq.c new file mode 100644 index 00000000..6c81714b --- /dev/null +++ b/include/stc/test_new_deq.c @@ -0,0 +1,57 @@ +#include +#include + +forward_cdeq(i32, int); +forward_cdeq(pnt, struct Point); + +struct MyStruct { + cdeq_i32 intvec; + cdeq_pnt pntvec; +} typedef MyStruct; + + +#define f_tag i32 +#define i_val int +#include + +struct Point { int x, y; } typedef Point; +int point_compare(const Point* a, const Point* b) { + int c = c_default_compare(&a->x, &b->x); + return c ? c : c_default_compare(&a->y, &b->y); +} +#define f_tag pnt +#define i_val Point +#define i_cmp point_compare +#include + +#define i_val float +#include + +#define i_val_str +#include + + +int main() +{ + cdeq_i32 vec = cdeq_i32_init(); + cdeq_i32_push_back(&vec, 123); + cdeq_i32_del(&vec); + + cdeq_float fvec = cdeq_float_init(); + cdeq_float_push_back(&fvec, 123.3); + cdeq_float_del(&fvec); + + cdeq_pnt pvec = cdeq_pnt_init(); + cdeq_pnt_push_back(&pvec, (Point){42, 14}); + cdeq_pnt_push_back(&pvec, (Point){32, 94}); + cdeq_pnt_push_front(&pvec, (Point){62, 81}); + cdeq_pnt_sort(&pvec); + c_foreach (i, cdeq_pnt, pvec) + printf(" (%d %d)", i.ref->x, i.ref->y); + puts(""); + cdeq_pnt_del(&pvec); + + cdeq_str svec = cdeq_str_init(); + cdeq_str_emplace_back(&svec, "Hello, friend"); + cdeq_str_del(&svec); +} \ No newline at end of file diff --git a/include/stc/test_new_smap.c b/include/stc/test_new_smap.c index c2e68d0e..bcb83c61 100644 --- a/include/stc/test_new_smap.c +++ b/include/stc/test_new_smap.c @@ -37,24 +37,29 @@ int point_compare(const Point* a, const Point* b) { int main() { - csmap_int map = csmap_int_init(); - csmap_int_insert(&map, 123, 321); - csmap_int_del(&map); - - csmap_pnt pmap = csmap_pnt_init(); - csmap_pnt_insert(&pmap, (Point){42, 14}, 1); - csmap_pnt_insert(&pmap, (Point){32, 94}, 2); - csmap_pnt_insert(&pmap, (Point){62, 81}, 3); - c_foreach (i, csmap_pnt, pmap) - printf(" (%d,%d: %d)", i.ref->first.x, i.ref->first.y, i.ref->second); - puts(""); - csmap_pnt_del(&pmap); - - csmap_str smap = csmap_str_init(); - csmap_str_emplace(&smap, "Hello, friend", "this is the mapped value"); - csmap_str_del(&smap); - - csset_str sset = csset_str_init(); - csset_str_emplace(&sset, "Hello, friend"); - csset_str_del(&sset); + c_forauto (csmap_int, map) + csmap_int_insert(&map, 123, 321); + + c_forauto (csmap_pnt, pmap) { + csmap_pnt_insert(&pmap, (Point){42, 14}, 1); + csmap_pnt_insert(&pmap, (Point){32, 94}, 2); + csmap_pnt_insert(&pmap, (Point){62, 81}, 3); + c_foreach (i, csmap_pnt, pmap) + printf(" (%d,%d: %d)", i.ref->first.x, i.ref->first.y, i.ref->second); + puts(""); + } + + c_forauto (csmap_str, smap) { + csmap_str_emplace(&smap, "Hello, friend", "this is the mapped value"); + csmap_str_emplace(&smap, "The brown fox", "jumped"); + csmap_str_emplace(&smap, "This is the time", "for all good things"); + c_foreach (i, csmap_str, smap) + printf(" (%s: %s)\n", i.ref->first.str, i.ref->second.str); + } + + c_forauto (csset_str, sset) { + csset_str_emplace(&sset, "Hello, friend"); + csset_str_emplace(&sset, "Goodbye, foe"); + printf("Found? %s\n", csset_str_contains(&sset, "Hello, friend") ? "true" : "false"); + } } \ No newline at end of file -- cgit v1.2.3