From eb0d095d7cdf5c5018d37be4319c99e2fdbfa9c5 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 30 Dec 2021 10:14:44 +0100 Subject: Update docs and impl. of cpque.h --- docs/cpque_api.md | 22 +++++++++++++--------- include/stc/cpque.h | 46 +++++++++++++++++++++------------------------- 2 files changed, 34 insertions(+), 34 deletions(-) diff --git a/docs/cpque_api.md b/docs/cpque_api.md index 7a6ef00f..fbc1786d 100644 --- a/docs/cpque_api.md +++ b/docs/cpque_api.md @@ -11,10 +11,13 @@ See the c++ class [std::priority_queue](https://en.cppreference.com/w/cpp/contai ```c #define i_val // value: REQUIRED -#define i_cmp // three-way compare two i_val* : REQUIRED IF i_val is a non-integral type +#define i_cmp // three-way compare two i_val* : REQUIRED IF i_val/i_valraw is a non-integral type #define i_drop // destroy value func - defaults to empty destruct -#define i_valfrom // convertion func i_val => i_val - defaults to plain copy +#define i_valraw // convertion type +#define i_valfrom // convertion func i_valraw => i_val - defaults to plain copy +#define i_valto // convertion func i_val* => i_valraw. #define i_tag // defaults to i_val +#define i_type // container type name #include ``` `X` should be replaced by the value of `i_tag` in all of the following documentation. @@ -22,7 +25,9 @@ See the c++ class [std::priority_queue](https://en.cppreference.com/w/cpp/contai ## Methods ```c -cpque_X cpque_X_init(void); +cpque_X cpque_X_init(void); // create empty pri-queue. +cpque_X cpque_X_with_capacity(size_t cap); +cpque_X cpque_X_with_size(size_t size, i_val null); cpque_X cpque_X_clone(cpque_X pq); void cpque_X_clear(cpque_X* self); @@ -33,17 +38,16 @@ void cpque_X_drop(cpque_X* self); // destructor size_t cpque_X_size(cpque_X pq); bool cpque_X_empty(cpque_X pq); -cpque_X_value* cpque_X_top(const cpque_X* self); +i_val* cpque_X_top(const cpque_X* self); -void cpque_X_make_heap(cpque_X* self); // call after using push_back(). -void cpque_X_push(cpque_X* self, cpque_X_value value); -void cpque_X_emplace(cpque_X* self, cpque_X_value val); // clones value +void cpque_X_make_heap(cpque_X* self); // heapify the vector. +void cpque_X_push(cpque_X* self, i_val value); +void cpque_X_emplace(cpque_X* self, i_valraw raw); // converts from raw void cpque_X_pop(cpque_X* self); void cpque_X_erase_at(cpque_X* self, size_t idx); -void cpque_X_push_back(cpque_X* self, cpque_X_value value); // breaks heap-property -cpque_X_value cpque_X_value_clone(cpque_X_value val); +i_val cpque_X_value_clone(i_val value); ``` ## Types diff --git a/include/stc/cpque.h b/include/stc/cpque.h index 2ca57289..73494cbd 100644 --- a/include/stc/cpque.h +++ b/include/stc/cpque.h @@ -43,29 +43,25 @@ STC_API void _cx_memb(_erase_at)(_cx_self* self, size_t idx); STC_API void _cx_memb(_push)(_cx_self* self, _cx_value value); STC_INLINE _cx_self _cx_memb(_init)(void) - { return c_make(_cx_self){0}; } + { return c_make(_cx_self){NULL}; } -STC_INLINE bool _cx_memb(_reserve)(_cx_self* self, size_t n) { - if (n != self->size && n <= self->capacity) return true; - _cx_value *d = (_cx_value *)c_realloc(self->data, n*sizeof *d); - return d ? (self->data = d, self->capacity = n, true) : false; -} - -STC_INLINE bool -_cx_memb(_resize)(_cx_self* self, const size_t len, i_val null) { - if (!_cx_memb(_reserve)(self, len)) return false; - const size_t n = self->size; - for (size_t i = len; i < n; ++i) { i_valdrop(&self->data[i]); } - for (size_t i = n; i < len; ++i) self->data[i] = null; - self->size = len; - return true; +STC_INLINE bool _cx_memb(_reserve)(_cx_self* self, const size_t cap) { + if (cap != self->size && cap <= self->capacity) return true; + _cx_value *d = (_cx_value *)c_realloc(self->data, cap*sizeof *d); + return d ? (self->data = d, self->capacity = cap, true) : false; } STC_INLINE void _cx_memb(_shrink_to_fit)(_cx_self* self) { _cx_memb(_reserve)(self, self->size); } -STC_INLINE _cx_self _cx_memb(_with_capacity)(size_t cap) { - _cx_self out = {0}; _cx_memb(_reserve)(&out, cap); +STC_INLINE _cx_self _cx_memb(_with_capacity)(const size_t cap) { + _cx_self out = {NULL}; _cx_memb(_reserve)(&out, cap); + return out; +} + +STC_INLINE _cx_self _cx_memb(_with_size)(const size_t size, i_val null) { + _cx_self out = {NULL}; _cx_memb(_reserve)(&out, size); + while (out.size < size) out.data[out.size++] = null; return out; } @@ -100,10 +96,11 @@ STC_INLINE void _cx_memb(_copy)(_cx_self *self, _cx_self other) { _cx_memb(_drop)(self); *self = _cx_memb(_clone)(other); } STC_INLINE i_val _cx_memb(_value_clone)(_cx_value val) - { return i_valfrom(val); } + { return i_valfrom(i_valto(&val)); } + #if !defined _i_no_raw -STC_INLINE void _cx_memb(_emplace)(_cx_self* self, _cx_value val) - { _cx_memb(_push)(self, i_valfrom(val)); } +STC_INLINE void _cx_memb(_emplace)(_cx_self* self, _cx_raw raw) + { _cx_memb(_push)(self, i_valfrom(raw)); } #endif #endif @@ -111,7 +108,7 @@ STC_INLINE void _cx_memb(_emplace)(_cx_self* self, _cx_value val) #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) || defined(i_imp) STC_DEF void -_cx_memb(_sift_down_)(_cx_value* arr, size_t idx, size_t n) { +_cx_memb(_sift_down_)(_cx_value* arr, const size_t idx, const size_t n) { for (size_t r = idx, c = idx << 1; c <= n; c <<= 1) { c += (c < n && i_cmp(&arr[c], &arr[c + 1]) < 0); if (i_cmp(&arr[r], &arr[c]) >= 0) return; @@ -128,19 +125,18 @@ _cx_memb(_make_heap)(_cx_self* self) { } #if !c_option(c_no_clone) - STC_DEF _cx_self _cx_memb(_clone)(_cx_self q) { _cx_self out = _cx_memb(_with_capacity)(q.size); for (; out.size < out.capacity; ++out.size, ++q.data) - out.data[out.size] = i_valfrom(*q.data); + out.data[out.size] = i_valfrom(i_valto(q.data)); return out; } #endif STC_DEF void -_cx_memb(_erase_at)(_cx_self* self, size_t idx) { +_cx_memb(_erase_at)(_cx_self* self, const size_t idx) { i_valdrop(&self->data[idx]); - size_t n = --self->size; + const size_t n = --self->size; self->data[idx] = self->data[n]; _cx_memb(_sift_down_)(self->data - 1, idx + 1, n); } -- cgit v1.2.3