diff options
Diffstat (limited to 'include/stc/cqueue.h')
| -rw-r--r-- | include/stc/cqueue.h | 247 |
1 files changed, 212 insertions, 35 deletions
diff --git a/include/stc/cqueue.h b/include/stc/cqueue.h index 1934305a..5d38ca89 100644 --- a/include/stc/cqueue.h +++ b/include/stc/cqueue.h @@ -20,46 +20,223 @@ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ -// STC queue -/* -#include <stc/crand.h> -#include <stdio.h> +#include "priv/linkage.h" -#define i_key int -#include <stc/cqueue.h> +#ifndef CQUEUE_H_INCLUDED +#include "ccommon.h" +#include "forward.h" +#include <stdlib.h> +#include <string.h> +#endif // CQUEUE_H_INCLUDED -int main() { - int n = 10000000; - crand_t rng = crand_init(1234); - crand_unif_t dist = crand_unif_init(0, n); +#ifndef _i_prefix +#define _i_prefix cqueue_ +#endif +#include "priv/template.h" - c_auto (cqueue_int, Q) - { - // Push ten million random numbers onto the queue. - for (int i=0; i<n; ++i) - cqueue_int_push(&Q, crand_unif(&rng, &dist)); - - // Push or pop on the queue ten million times - printf("before: size, capacity: %d, %d\n", n, cqueue_int_size(&Q), cqueue_int_capacity(&Q)); - for (int i=n; i>0; --i) { - int r = crand_unif(&rng, &dist); - if (r & 1) - ++n, cqueue_int_push(&Q, r); - else - --n, cqueue_int_pop(&Q); - } - printf("after: size, capacity: %d, %d\n", n, cqueue_int_size(&Q), cqueue_int_capacity(&Q)); +#ifndef i_is_forward +_cx_DEFTYPES(_c_cdeq_types, _cx_Self, i_key); +#endif +typedef i_keyraw _cx_raw; + +STC_API _cx_Self _cx_MEMB(_with_capacity)(const intptr_t n); +STC_API bool _cx_MEMB(_reserve)(_cx_Self* self, const intptr_t n); +STC_API void _cx_MEMB(_clear)(_cx_Self* self); +STC_API void _cx_MEMB(_drop)(_cx_Self* self); +STC_API _cx_value* _cx_MEMB(_push)(_cx_Self* self, i_key value); // push_back +STC_API void _cx_MEMB(_shrink_to_fit)(_cx_Self *self); +STC_API _cx_iter _cx_MEMB(_advance)(_cx_iter it, intptr_t n); + +#define _cdeq_toidx(self, pos) (((pos) - (self)->start) & (self)->capmask) +#define _cdeq_topos(self, idx) (((self)->start + (idx)) & (self)->capmask) + +STC_INLINE _cx_Self _cx_MEMB(_init)(void) + { _cx_Self cx = {0}; return cx; } +STC_INLINE void _cx_MEMB(_put_n)(_cx_Self* self, const _cx_raw* raw, intptr_t n) + { while (n--) _cx_MEMB(_push)(self, i_keyfrom(*raw++)); } +STC_INLINE _cx_Self _cx_MEMB(_from_n)(const _cx_raw* raw, intptr_t n) + { _cx_Self cx = {0}; _cx_MEMB(_put_n)(&cx, raw, n); return cx; } +STC_INLINE void _cx_MEMB(_value_drop)(_cx_value* val) { i_keydrop(val); } + +#if !defined i_no_emplace +STC_INLINE _cx_value* _cx_MEMB(_emplace)(_cx_Self* self, _cx_raw raw) + { return _cx_MEMB(_push)(self, i_keyfrom(raw)); } +#endif + +#if defined _i_has_eq || defined _i_has_cmp +STC_API bool _cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other); +#endif + +#if !defined i_no_clone +STC_API _cx_Self _cx_MEMB(_clone)(_cx_Self cx); +STC_INLINE i_key _cx_MEMB(_value_clone)(i_key val) + { return i_keyclone(val); } +#endif // !i_no_clone +STC_INLINE intptr_t _cx_MEMB(_size)(const _cx_Self* self) + { return _cdeq_toidx(self, self->end); } +STC_INLINE intptr_t _cx_MEMB(_capacity)(const _cx_Self* self) + { return self->capmask; } +STC_INLINE bool _cx_MEMB(_empty)(const _cx_Self* self) + { return self->start == self->end; } +STC_INLINE _cx_raw _cx_MEMB(_value_toraw)(const _cx_value* pval) + { return i_keyto(pval); } + +STC_INLINE _cx_value* _cx_MEMB(_front)(const _cx_Self* self) + { return self->data + self->start; } + +STC_INLINE _cx_value* _cx_MEMB(_back)(const _cx_Self* self) + { return self->data + ((self->end - 1) & self->capmask); } + +STC_INLINE void _cx_MEMB(_pop)(_cx_Self* self) { // pop_front + c_assert(!_cx_MEMB(_empty)(self)); + i_keydrop((self->data + self->start)); + self->start = (self->start + 1) & self->capmask; +} + +STC_INLINE _cx_value _cx_MEMB(_pull)(_cx_Self* self) { // move front out of queue + c_assert(!_cx_MEMB(_empty)(self)); + intptr_t s = self->start; + self->start = (s + 1) & self->capmask; + return self->data[s]; +} + +STC_INLINE void _cx_MEMB(_copy)(_cx_Self* self, const _cx_Self* other) { + if (self->data == other->data) return; + _cx_MEMB(_drop)(self); + *self = _cx_MEMB(_clone)(*other); +} + +STC_INLINE _cx_iter _cx_MEMB(_begin)(const _cx_Self* self) { + return c_LITERAL(_cx_iter){ + _cx_MEMB(_empty)(self) ? NULL : self->data + self->start, + self->start, self + }; +} + +STC_INLINE _cx_iter _cx_MEMB(_end)(const _cx_Self* self) + { return c_LITERAL(_cx_iter){.pos=self->end, ._s=self}; } + +STC_INLINE void _cx_MEMB(_next)(_cx_iter* it) { + if (it->pos != it->_s->capmask) { ++it->ref; ++it->pos; } + else { it->ref -= it->pos; it->pos = 0; } + if (it->pos == it->_s->end) it->ref = NULL; +} + +STC_INLINE intptr_t _cx_MEMB(_index)(const _cx_Self* self, _cx_iter it) + { return _cdeq_toidx(self, it.pos); } + +STC_INLINE void _cx_MEMB(_adjust_end_)(_cx_Self* self, intptr_t n) + { self->end = (self->end + n) & self->capmask; } + +/* -------------------------- IMPLEMENTATION ------------------------- */ +#if defined(i_implement) || defined(i_static) + +STC_DEF _cx_iter _cx_MEMB(_advance)(_cx_iter it, intptr_t n) { + intptr_t len = _cx_MEMB(_size)(it._s); + intptr_t pos = it.pos, idx = _cdeq_toidx(it._s, pos); + it.pos = (pos + n) & it._s->capmask; + it.ref += it.pos - pos; + if (!c_LTu(idx + n, len)) it.ref = NULL; + return it; +} + +STC_DEF void +_cx_MEMB(_clear)(_cx_Self* self) { + c_foreach (i, _cx_Self, *self) + { i_keydrop(i.ref); } + self->start = 0, self->end = 0; +} + +STC_DEF void +_cx_MEMB(_drop)(_cx_Self* self) { + _cx_MEMB(_clear)(self); + i_free(self->data); +} + +STC_DEF _cx_Self +_cx_MEMB(_with_capacity)(const intptr_t n) { + _cx_Self cx = {0}; + _cx_MEMB(_reserve)(&cx, n); + return cx; +} + +STC_DEF bool +_cx_MEMB(_reserve)(_cx_Self* self, const intptr_t n) { + if (n <= self->capmask) + return true; + intptr_t oldcap = self->capmask + 1, newcap = cnextpow2(n + 1); + _cx_value* d = (_cx_value *)i_realloc(self->data, newcap*c_sizeof *self->data); + if (!d) + return false; + intptr_t head = oldcap - self->start; + if (self->start <= self->end) + ; + else if (head < self->end) { + self->start = newcap - head; + c_memmove(d + self->start, d + oldcap - head, head*c_sizeof *d); + } else { + c_memmove(d + oldcap, d, self->end*c_sizeof *d); + self->end += oldcap; } + self->capmask = newcap - 1; + self->data = d; + return true; } -*/ -#ifndef _i_prefix -#define _i_prefix cqueue_ -#endif -#define _i_queue -#define _pop_front _pop +STC_DEF _cx_value* +_cx_MEMB(_push)(_cx_Self* self, i_key value) { // push_back + intptr_t end = (self->end + 1) & self->capmask; + if (end == self->start) { // full + _cx_MEMB(_reserve)(self, self->capmask + 3); // => 2x expand + end = (self->end + 1) & self->capmask; + } + _cx_value *v = self->data + self->end; + self->end = end; + *v = value; + return v; +} + +STC_DEF void +_cx_MEMB(_shrink_to_fit)(_cx_Self *self) { + intptr_t sz = _cx_MEMB(_size)(self), j = 0; + if (sz > self->capmask/2) + return; + _cx_Self out = _cx_MEMB(_with_capacity)(sz); + if (!out.data) + return; + c_foreach (i, _cx_Self, *self) + out.data[j++] = *i.ref; + out.end = sz; + i_free(self->data); + *self = out; +} -#include "cdeq.h" +#if !defined i_no_clone +STC_DEF _cx_Self +_cx_MEMB(_clone)(_cx_Self cx) { + intptr_t sz = _cx_MEMB(_size)(&cx), j = 0; + _cx_Self out = _cx_MEMB(_with_capacity)(sz); + if (out.data) + c_foreach (i, _cx_Self, cx) + out.data[j++] = i_keyclone((*i.ref)); + out.end = sz; + return out; +} +#endif // i_no_clone -#undef _pop_front -#undef _i_queue +#if defined _i_has_eq || defined _i_has_cmp +STC_DEF bool +_cx_MEMB(_eq)(const _cx_Self* self, const _cx_Self* other) { + if (_cx_MEMB(_size)(self) != _cx_MEMB(_size)(other)) return false; + for (_cx_iter i = _cx_MEMB(_begin)(self), j = _cx_MEMB(_begin)(other); + i.ref; _cx_MEMB(_next)(&i), _cx_MEMB(_next)(&j)) + { + const _cx_raw _rx = i_keyto(i.ref), _ry = i_keyto(j.ref); + if (!(i_eq((&_rx), (&_ry)))) return false; + } + return true; +} +#endif +#endif // IMPLEMENTATION +#include "priv/template2.h" +#define CQUEUE_H_INCLUDED |