From 07bb3643447806fed65329ca4a0da0460bf7e7b9 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 10 Sep 2020 10:05:27 +0200 Subject: Reformatting only. --- stc/carray.h | 203 ++++++++++++----------- stc/clist.h | 38 ++--- stc/cmap.h | 516 +++++++++++++++++++++++++++++----------------------------- stc/cpqueue.h | 155 +++++++++--------- stc/cqueue.h | 84 +++++----- stc/cstack.h | 80 ++++----- stc/cvec.h | 428 ++++++++++++++++++++++++------------------------ 7 files changed, 752 insertions(+), 752 deletions(-) diff --git a/stc/carray.h b/stc/carray.h index ca18b8d9..a7f15ddd 100644 --- a/stc/carray.h +++ b/stc/carray.h @@ -69,28 +69,27 @@ STC_INLINE size_t _carray3_size(const size_t* zdim) { #define declare_carray_common(D, X, Value, valueDestroy) \ + typedef struct { Value *item; } carray##D##X##_iter_t; \ \ -typedef struct { Value *item; } carray##D##X##_iter_t; \ -\ -STC_INLINE carray##D##X##_iter_t \ -carray##D##X##_begin(carray##D##X* a) { \ - carray##D##X##_iter_t it = {a->data}; return it; \ -} \ -STC_INLINE carray##D##X##_iter_t \ -carray##D##X##_end(carray##D##X* a) { \ - carray##D##X##_iter_t it = {a->data + carray##D##_size(*a)}; return it; \ -} \ -STC_INLINE void \ -carray##D##X##_next(carray##D##X##_iter_t* it) {++it->item;} \ -\ -STC_INLINE void \ -carray##D##X##_destroy(carray##D##X* self) { \ - if (self->_xdim & _carray_OWN) { \ - c_foreach_3 (i, carray##D##X, *self) \ - valueDestroy(i.item); \ - free(self->data); \ + STC_INLINE carray##D##X##_iter_t \ + carray##D##X##_begin(carray##D##X* a) { \ + carray##D##X##_iter_t it = {a->data}; return it; \ } \ -} + STC_INLINE carray##D##X##_iter_t \ + carray##D##X##_end(carray##D##X* a) { \ + carray##D##X##_iter_t it = {a->data + carray##D##_size(*a)}; return it; \ + } \ + STC_INLINE void \ + carray##D##X##_next(carray##D##X##_iter_t* it) {++it->item;} \ +\ + STC_INLINE void \ + carray##D##X##_destroy(carray##D##X* self) { \ + if (self->_xdim & _carray_OWN) { \ + c_foreach_3 (i, carray##D##X, *self) \ + valueDestroy(i.item); \ + free(self->data); \ + } \ + } #define declare_carray(...) c_MACRO_OVERLOAD(declare_carray, __VA_ARGS__) #define declare_carray_2(X, Value) \ @@ -99,95 +98,95 @@ carray##D##X##_destroy(carray##D##X* self) { \ #define declare_carray_3(X, Value, valueDestroy) \ \ -typedef Value carray1##X##_value_t; \ -typedef carray1##X##_value_t carray2##X##_value_t, carray3##X##_value_t; \ + typedef Value carray1##X##_value_t; \ + typedef carray1##X##_value_t carray2##X##_value_t, carray3##X##_value_t; \ \ -typedef struct carray1##X { \ - Value *data; \ - size_t _xdim; \ -} carray1##X; \ + typedef struct carray1##X { \ + Value *data; \ + size_t _xdim; \ + } carray1##X; \ \ -typedef struct carray2##X { \ - Value *data; \ - size_t _xdim, _yxdim; \ -} carray2##X; \ + typedef struct carray2##X { \ + Value *data; \ + size_t _xdim, _yxdim; \ + } carray2##X; \ \ -typedef struct carray3##X { \ - Value *data; \ - size_t _xdim, _yxdim, _zdim; \ -} carray3##X; \ + typedef struct carray3##X { \ + Value *data; \ + size_t _xdim, _yxdim, _zdim; \ + } carray3##X; \ \ -declare_carray_common(1, X, Value, valueDestroy) \ -declare_carray_common(2, X, Value, valueDestroy) \ -declare_carray_common(3, X, Value, valueDestroy) \ + declare_carray_common(1, X, Value, valueDestroy) \ + declare_carray_common(2, X, Value, valueDestroy) \ + declare_carray_common(3, X, Value, valueDestroy) \ \ -STC_INLINE carray1##X \ -carray1##X##_make(size_t xdim, Value val) { \ - Value* m = c_new_n(Value, xdim); \ - for (size_t i=0; idata + x; } \ + STC_INLINE carray1##X \ + carray1##X##_from(size_t xdim, Value* array, bool own) { \ + carray1##X a = {array, xdim | (own ? _carray_OWN : 0)}; \ + return a; \ + } \ + STC_INLINE carray2##X \ + carray2##X##_from(size_t ydim, size_t xdim, Value* array, bool own) { \ + carray2##X a = {array, xdim | (own ? _carray_OWN : 0), ydim * xdim}; \ + return a; \ + } \ + STC_INLINE carray3##X \ + carray3##X##_from(size_t zdim, size_t ydim, size_t xdim, Value* array, bool own) { \ + carray3##X a = {array, xdim | (own ? _carray_OWN : 0), ydim * xdim, zdim}; \ + return a; \ + } \ \ -STC_INLINE carray1##X \ -carray2##X##_at1(carray2##X *a, size_t y) { \ - carray1##X sub = {a->data + y*carray2_xdim(*a), carray2_xdim(*a)}; \ - return sub; \ -} \ -STC_INLINE Value* \ -carray2##X##_at(carray2##X *a, size_t y, size_t x) { \ - return a->data + y*carray2_xdim(*a) + x; \ -} \ + STC_INLINE Value* \ + carray1##X##_at(carray1##X *a, size_t x) { return a->data + x; } \ + \ + STC_INLINE carray1##X \ + carray2##X##_at1(carray2##X *a, size_t y) { \ + carray1##X sub = {a->data + y*carray2_xdim(*a), carray2_xdim(*a)}; \ + return sub; \ + } \ + STC_INLINE Value* \ + carray2##X##_at(carray2##X *a, size_t y, size_t x) { \ + return a->data + y*carray2_xdim(*a) + x; \ + } \ \ -STC_INLINE carray2##X \ -carray3##X##_at1(carray3##X *a, size_t z) { \ - carray2##X sub = {a->data + z*a->_yxdim, carray3_xdim(*a), a->_yxdim}; \ - return sub; \ -} \ -STC_INLINE carray1##X \ -carray3##X##_at2(carray3##X *a, size_t z, size_t y) { \ - carray1##X sub = {a->data + z*a->_yxdim + y*carray3_xdim(*a), carray3_xdim(*a)}; \ - return sub; \ -} \ -STC_INLINE Value* \ -carray3##X##_at(carray3##X *a, size_t z, size_t y, size_t x) { \ - return a->data + z*a->_yxdim + y*carray3_xdim(*a) + x; \ -} \ -typedef int carray1##X##_dud + STC_INLINE carray2##X \ + carray3##X##_at1(carray3##X *a, size_t z) { \ + carray2##X sub = {a->data + z*a->_yxdim, carray3_xdim(*a), a->_yxdim}; \ + return sub; \ + } \ + STC_INLINE carray1##X \ + carray3##X##_at2(carray3##X *a, size_t z, size_t y) { \ + carray1##X sub = {a->data + z*a->_yxdim + y*carray3_xdim(*a), carray3_xdim(*a)}; \ + return sub; \ + } \ + STC_INLINE Value* \ + carray3##X##_at(carray3##X *a, size_t z, size_t y, size_t x) { \ + return a->data + z*a->_yxdim + y*carray3_xdim(*a) + x; \ + } \ + typedef int carray1##X##_dud #endif diff --git a/stc/clist.h b/stc/clist.h index dfb88db4..3c5f8a10 100644 --- a/stc/clist.h +++ b/stc/clist.h @@ -73,11 +73,11 @@ struct clist_##X##_node* next; \ Value value; \ } clist_##X##_node_t; \ - \ +\ typedef struct clist_##X { \ clist_##X##_node_t* last; \ } clist_##X; \ - \ +\ typedef struct { \ clist_##X##_node_t* const* _last; \ clist_##X##_node_t* item; \ @@ -92,12 +92,12 @@ declare_clist_types(void, int); STC_API size_t _clist_size(const clist_void* self); #define declare_clist_7(X, Value, valueDestroy, RawValue, valueCompareRaw, valueToRaw, valueFromRaw) \ - \ +\ declare_clist_types(X, Value); \ typedef Value clist_##X##_value_t; \ typedef RawValue clist_##X##_rawvalue_t; \ typedef clist_##X##_rawvalue_t clist_##X##_input_t; \ - \ +\ STC_INLINE clist_##X \ clist_##X##_init(void) {clist_##X x = clist_ini; return x;} \ STC_INLINE bool \ @@ -106,12 +106,12 @@ STC_API size_t _clist_size(const clist_void* self); clist_##X##_size(clist_##X ls) {return _clist_size((const clist_void*) &ls);} \ STC_INLINE Value \ clist_##X##_value_from_raw(RawValue rawValue) {return valueFromRaw(rawValue);} \ - \ +\ STC_API void \ clist_##X##_destroy(clist_##X* self); \ STC_INLINE void \ clist_##X##_clear(clist_##X* self) {clist_##X##_destroy(self);} \ - \ +\ STC_API void \ clist_##X##_push_n(clist_##X *self, const clist_##X##_input_t in[], size_t size); \ STC_API void \ @@ -128,7 +128,7 @@ STC_API size_t _clist_size(const clist_void* self); } \ STC_API void \ clist_##X##_pop_front(clist_##X* self); \ - \ +\ STC_INLINE clist_##X##_iter_t \ clist_##X##_before_begin(const clist_##X* self) { \ clist_##X##_iter_t it = {&self->last, self->last, -1}; return it; \ @@ -148,7 +148,7 @@ STC_API size_t _clist_size(const clist_void* self); } \ STC_INLINE clist_##X##_value_t* \ clist_##X##_itval(clist_##X##_iter_t it) {return &it.item->value;} \ - \ +\ STC_API clist_##X##_iter_t \ clist_##X##_insert_after(clist_##X* self, clist_##X##_iter_t it, Value value); \ STC_INLINE clist_##X##_iter_t \ @@ -157,7 +157,7 @@ STC_API size_t _clist_size(const clist_void* self); } \ STC_API clist_##X##_iter_t \ clist_##X##_erase_after(clist_##X* self, clist_##X##_iter_t it); \ - \ +\ STC_INLINE void \ clist_##X##_splice_after(clist_##X* self, clist_##X##_iter_t it, clist_##X* other) { \ _clist_splice_after((clist_void *) self, *(clist_void_iter_t *) &it, (clist_void *) other); \ @@ -171,7 +171,7 @@ STC_API size_t _clist_size(const clist_void* self); clist_##X##_iter_t last = {&self->last, self->last, 0}; \ clist_##X##_splice_after(self, last, other); \ } \ - \ +\ STC_API clist_##X##_iter_t \ clist_##X##_find_before(const clist_##X* self, clist_##X##_iter_t first, clist_##X##_iter_t last, RawValue val); \ STC_API clist_##X##_iter_t \ @@ -180,12 +180,12 @@ STC_API size_t _clist_size(const clist_void* self); clist_##X##_remove(clist_##X* self, RawValue val); \ STC_API void \ clist_##X##_sort(clist_##X* self); \ - \ +\ STC_INLINE Value* \ clist_##X##_front(clist_##X* self) {return &self->last->next->value;} \ STC_INLINE Value* \ clist_##X##_back(clist_##X* self) {return &self->last->value;} \ - \ +\ implement_clist_7(X, Value, valueDestroy, RawValue, valueCompareRaw, valueToRaw, valueFromRaw) @@ -193,13 +193,13 @@ STC_API size_t _clist_size(const clist_void* self); #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) #define implement_clist_7(X, Value, valueDestroy, RawValue, valueCompareRaw, valueToRaw, valueFromRaw) \ - \ +\ STC_API void \ clist_##X##_destroy(clist_##X* self) { \ while (self->last) \ clist_##X##_pop_front(self); \ } \ - \ +\ STC_API void \ clist_##X##_push_back(clist_##X* self, Value value) { \ _clist_insert_after(self, X, self->last, value); \ @@ -218,7 +218,7 @@ STC_API size_t _clist_size(const clist_void* self); clist_##X##_pop_front(clist_##X* self) { \ _clist_erase_after(self, X, self->last, valueDestroy); \ } \ - \ +\ STC_API clist_##X##_iter_t \ clist_##X##_insert_after(clist_##X* self, clist_##X##_iter_t it, Value value) { \ _clist_insert_after(self, X, it.item, value); \ @@ -230,7 +230,7 @@ STC_API size_t _clist_size(const clist_void* self); _clist_erase_after(self, X, it.item, valueDestroy); \ clist_##X##_next(&it); return it; \ } \ - \ +\ STC_API clist_##X##_iter_t \ clist_##X##_find_before(const clist_##X* self, clist_##X##_iter_t first, clist_##X##_iter_t last, RawValue val) { \ clist_##X##_iter_t i = first; \ @@ -241,14 +241,14 @@ STC_API size_t _clist_size(const clist_void* self); } \ return clist_##X##_end(self); \ } \ - \ +\ STC_API clist_##X##_iter_t \ clist_##X##_find(const clist_##X* self, RawValue val) { \ clist_##X##_iter_t it = clist_##X##_find_before(self, clist_##X##_before_begin(self), clist_##X##_end(self), val); \ if (it.item != clist_##X##_end(self).item) clist_##X##_next(&it); \ return it; \ } \ - \ +\ STC_API size_t \ clist_##X##_remove(clist_##X* self, RawValue val) { \ size_t n = 0; \ @@ -257,7 +257,7 @@ STC_API size_t _clist_size(const clist_void* self); clist_##X##_erase_after(self, it), ++n; \ return n; \ } \ - \ +\ static inline int \ clist_##X##_sort_compare(const void* x, const void* y) { \ RawValue a = valueToRaw(&((clist_##X##_node_t *) x)->value); \ diff --git a/stc/cmap.h b/stc/cmap.h index 21d5a394..ec437f1f 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -150,274 +150,274 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; /* CHASH full: use 'void' for Value if ctype is cset */ #define declare_CHASH(X, ctype, Key, Value, valueDestroy, keyEqualsRaw, keyHashRaw, \ keyDestroy, RawKey, keyToRaw, keyFromRaw, RawValue, valueFromRaw) \ -typedef struct { \ - Key key; \ - CMAP_ONLY_##ctype(Value value;) \ -} ctype##_##X##_entry_t; \ - \ -STC_INLINE void \ -ctype##_##X##_entry_destroy(ctype##_##X##_entry_t* e) { \ - keyDestroy(&e->key); \ - CMAP_ONLY_##ctype(valueDestroy(&e->value);) \ -} \ -typedef struct { \ - RawKey key; \ - CMAP_ONLY_##ctype(RawValue value;) \ -} ctype##_##X##_input_t; \ - \ -typedef struct { \ - ctype##_##X##_entry_t *item; \ - bool inserted; \ -} ctype##_##X##_result_t; \ - \ -typedef Key ctype##_##X##_key_t; \ -typedef Value ctype##_##X##_value_t; \ -typedef RawKey ctype##_##X##_rawkey_t; \ -typedef RawValue ctype##_##X##_rawvalue_t; \ - \ -typedef struct ctype##_##X { \ - ctype##_##X##_entry_t* table; \ - uint8_t* _hashx; \ - uint32_t size, bucket_count; \ - float max_load_factor; \ - float shrink_limit_factor; \ -} ctype##_##X; \ - \ -typedef struct { \ - ctype##_##X##_entry_t *item; \ - uint8_t* _hx; \ -} ctype##_##X##_iter_t; \ - \ -STC_INLINE ctype##_##X \ -ctype##_##X##_init(void) {ctype##_##X m = cmap_ini; return m;} \ -STC_INLINE bool \ -ctype##_##X##_empty(ctype##_##X m) {return m.size == 0;} \ -STC_INLINE size_t \ -ctype##_##X##_size(ctype##_##X m) {return (size_t) m.size;} \ -STC_INLINE size_t \ -ctype##_##X##_capacity(ctype##_##X m) {return (size_t) (m.bucket_count * m.max_load_factor);} \ -STC_INLINE void \ -ctype##_##X##_swap(ctype##_##X* a, ctype##_##X* b) {c_swap(ctype##_##X, *a, *b);} \ -STC_INLINE void \ -ctype##_##X##_set_load_factors(ctype##_##X* self, float max, float shrink) { \ - self->max_load_factor = max; self->shrink_limit_factor = shrink; \ -} \ -STC_API ctype##_##X \ -ctype##_##X##_with_capacity(size_t cap); \ -STC_API void \ -ctype##_##X##_push_n(ctype##_##X* self, const ctype##_##X##_input_t in[], size_t size); \ -STC_API void \ -ctype##_##X##_destroy(ctype##_##X* self); \ -STC_API void \ -ctype##_##X##_clear(ctype##_##X* self); \ -STC_API ctype##_##X##_entry_t* \ -ctype##_##X##_find(const ctype##_##X* self, ctype##_##X##_rawkey_t rawKey); \ -STC_API bool \ -ctype##_##X##_contains(const ctype##_##X* self, ctype##_##X##_rawkey_t rawKey); \ - \ -STC_API ctype##_##X##_result_t \ -ctype##_##X##_insert_key_(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey); \ - \ -STC_INLINE ctype##_##X##_result_t \ -ctype##_##X##_emplace(ctype##_##X* self, CMAP_ARGS_##ctype(ctype##_##X##_rawkey_t rawKey, RawValue rawValue)) { \ - ctype##_##X##_result_t res = ctype##_##X##_insert_key_(self, rawKey); \ - CMAP_ONLY_##ctype( if (res.inserted) res.item->value = valueFromRaw(rawValue); ) \ - return res; \ -} \ -STC_INLINE ctype##_##X##_result_t \ -ctype##_##X##_insert(ctype##_##X* self, CMAP_ARGS_##ctype(ctype##_##X##_rawkey_t rawKey, RawValue rawValue)) { \ - return ctype##_##X##_emplace(self, CMAP_ARGS_##ctype(rawKey, rawValue)); \ -} \ -CMAP_ONLY_##ctype( \ -STC_INLINE ctype##_##X##_result_t \ -ctype##_##X##_insert_or_assign(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey, RawValue rawValue) { \ - ctype##_##X##_result_t res = ctype##_##X##_insert_key_(self, rawKey); \ - if (!res.inserted) valueDestroy(&res.item->value); \ - res.item->value = valueFromRaw(rawValue); return res; \ -} \ -STC_INLINE ctype##_##X##_result_t \ -ctype##_##X##_putv(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey, Value value) { \ - ctype##_##X##_result_t res = ctype##_##X##_insert_key_(self, rawKey); \ - if (!res.inserted) valueDestroy(&res.item->value); \ - res.item->value = value; return res; \ -}) \ - \ -STC_INLINE ctype##_##X##_result_t \ -ctype##_##X##_put(ctype##_##X* self, CMAP_ARGS_##ctype(ctype##_##X##_rawkey_t rawKey, RawValue rawValue)) { \ - CMAP_ONLY_##ctype( return ctype##_##X##_insert_or_assign(self, rawKey, rawValue); ) \ - CSET_ONLY_##ctype( return ctype##_##X##_insert_key_(self, rawKey); ) \ -} \ - \ -STC_API size_t \ -ctype##_##X##_reserve(ctype##_##X* self, size_t size); \ -STC_API bool \ -ctype##_##X##_erase_entry(ctype##_##X* self, ctype##_##X##_entry_t* item); \ -STC_API bool \ -ctype##_##X##_erase(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey); \ - \ -STC_INLINE ctype##_##X##_iter_t \ -ctype##_##X##_begin(ctype##_##X* self) { \ - ctype##_##X##_iter_t it = {self->table, self->_hashx}; \ - if (it._hx) while (*it._hx == 0) ++it.item, ++it._hx; \ - return it; \ -} \ -STC_INLINE ctype##_##X##_iter_t \ -ctype##_##X##_end(ctype##_##X* self) {\ - ctype##_##X##_iter_t it = {self->table + self->bucket_count}; return it; \ -} \ -STC_INLINE void \ -ctype##_##X##_next(ctype##_##X##_iter_t* it) { \ - while ((++it->item, *++it->_hx == 0)) ; \ -} \ -CMAP_ONLY_##ctype( STC_INLINE ctype##_##X##_value_t* \ -ctype##_##X##_itval(ctype##_##X##_iter_t it) {return &it.item->value;} ) \ - \ -STC_API uint32_t c_default_hash16(const void *data, size_t len); \ -STC_API uint32_t c_default_hash32(const void* data, size_t len); \ - \ -implement_CHASH(X, ctype, Key, Value, valueDestroy, keyEqualsRaw, keyHashRaw, \ - keyDestroy, RawKey, keyToRaw, keyFromRaw, RawValue, valueFromRaw) + typedef struct { \ + Key key; \ + CMAP_ONLY_##ctype(Value value;) \ + } ctype##_##X##_entry_t; \ +\ + STC_INLINE void \ + ctype##_##X##_entry_destroy(ctype##_##X##_entry_t* e) { \ + keyDestroy(&e->key); \ + CMAP_ONLY_##ctype(valueDestroy(&e->value);) \ + } \ + typedef struct { \ + RawKey key; \ + CMAP_ONLY_##ctype(RawValue value;) \ + } ctype##_##X##_input_t; \ +\ + typedef struct { \ + ctype##_##X##_entry_t *item; \ + bool inserted; \ + } ctype##_##X##_result_t; \ +\ + typedef Key ctype##_##X##_key_t; \ + typedef Value ctype##_##X##_value_t; \ + typedef RawKey ctype##_##X##_rawkey_t; \ + typedef RawValue ctype##_##X##_rawvalue_t; \ +\ + typedef struct ctype##_##X { \ + ctype##_##X##_entry_t* table; \ + uint8_t* _hashx; \ + uint32_t size, bucket_count; \ + float max_load_factor; \ + float shrink_limit_factor; \ + } ctype##_##X; \ +\ + typedef struct { \ + ctype##_##X##_entry_t *item; \ + uint8_t* _hx; \ + } ctype##_##X##_iter_t; \ +\ + STC_INLINE ctype##_##X \ + ctype##_##X##_init(void) {ctype##_##X m = cmap_ini; return m;} \ + STC_INLINE bool \ + ctype##_##X##_empty(ctype##_##X m) {return m.size == 0;} \ + STC_INLINE size_t \ + ctype##_##X##_size(ctype##_##X m) {return (size_t) m.size;} \ + STC_INLINE size_t \ + ctype##_##X##_capacity(ctype##_##X m) {return (size_t) (m.bucket_count * m.max_load_factor);} \ + STC_INLINE void \ + ctype##_##X##_swap(ctype##_##X* a, ctype##_##X* b) {c_swap(ctype##_##X, *a, *b);} \ + STC_INLINE void \ + ctype##_##X##_set_load_factors(ctype##_##X* self, float max, float shrink) { \ + self->max_load_factor = max; self->shrink_limit_factor = shrink; \ + } \ + STC_API ctype##_##X \ + ctype##_##X##_with_capacity(size_t cap); \ + STC_API void \ + ctype##_##X##_push_n(ctype##_##X* self, const ctype##_##X##_input_t in[], size_t size); \ + STC_API void \ + ctype##_##X##_destroy(ctype##_##X* self); \ + STC_API void \ + ctype##_##X##_clear(ctype##_##X* self); \ + STC_API ctype##_##X##_entry_t* \ + ctype##_##X##_find(const ctype##_##X* self, ctype##_##X##_rawkey_t rawKey); \ + STC_API bool \ + ctype##_##X##_contains(const ctype##_##X* self, ctype##_##X##_rawkey_t rawKey); \ +\ + STC_API ctype##_##X##_result_t \ + ctype##_##X##_insert_key_(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey); \ +\ + STC_INLINE ctype##_##X##_result_t \ + ctype##_##X##_emplace(ctype##_##X* self, CMAP_ARGS_##ctype(ctype##_##X##_rawkey_t rawKey, RawValue rawValue)) { \ + ctype##_##X##_result_t res = ctype##_##X##_insert_key_(self, rawKey); \ + CMAP_ONLY_##ctype( if (res.inserted) res.item->value = valueFromRaw(rawValue); ) \ + return res; \ + } \ + STC_INLINE ctype##_##X##_result_t \ + ctype##_##X##_insert(ctype##_##X* self, CMAP_ARGS_##ctype(ctype##_##X##_rawkey_t rawKey, RawValue rawValue)) { \ + return ctype##_##X##_emplace(self, CMAP_ARGS_##ctype(rawKey, rawValue)); \ + } \ + CMAP_ONLY_##ctype( \ + STC_INLINE ctype##_##X##_result_t \ + ctype##_##X##_insert_or_assign(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey, RawValue rawValue) { \ + ctype##_##X##_result_t res = ctype##_##X##_insert_key_(self, rawKey); \ + if (!res.inserted) valueDestroy(&res.item->value); \ + res.item->value = valueFromRaw(rawValue); return res; \ + } \ + STC_INLINE ctype##_##X##_result_t \ + ctype##_##X##_putv(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey, Value value) { \ + ctype##_##X##_result_t res = ctype##_##X##_insert_key_(self, rawKey); \ + if (!res.inserted) valueDestroy(&res.item->value); \ + res.item->value = value; return res; \ + }) \ +\ + STC_INLINE ctype##_##X##_result_t \ + ctype##_##X##_put(ctype##_##X* self, CMAP_ARGS_##ctype(ctype##_##X##_rawkey_t rawKey, RawValue rawValue)) { \ + CMAP_ONLY_##ctype( return ctype##_##X##_insert_or_assign(self, rawKey, rawValue); ) \ + CSET_ONLY_##ctype( return ctype##_##X##_insert_key_(self, rawKey); ) \ + } \ +\ + STC_API size_t \ + ctype##_##X##_reserve(ctype##_##X* self, size_t size); \ + STC_API bool \ + ctype##_##X##_erase_entry(ctype##_##X* self, ctype##_##X##_entry_t* item); \ + STC_API bool \ + ctype##_##X##_erase(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey); \ +\ + STC_INLINE ctype##_##X##_iter_t \ + ctype##_##X##_begin(ctype##_##X* self) { \ + ctype##_##X##_iter_t it = {self->table, self->_hashx}; \ + if (it._hx) while (*it._hx == 0) ++it.item, ++it._hx; \ + return it; \ + } \ + STC_INLINE ctype##_##X##_iter_t \ + ctype##_##X##_end(ctype##_##X* self) {\ + ctype##_##X##_iter_t it = {self->table + self->bucket_count}; return it; \ + } \ + STC_INLINE void \ + ctype##_##X##_next(ctype##_##X##_iter_t* it) { \ + while ((++it->item, *++it->_hx == 0)) ; \ + } \ + CMAP_ONLY_##ctype( STC_INLINE ctype##_##X##_value_t* \ + ctype##_##X##_itval(ctype##_##X##_iter_t it) {return &it.item->value;} ) \ +\ + STC_API uint32_t c_default_hash16(const void *data, size_t len); \ + STC_API uint32_t c_default_hash32(const void* data, size_t len); \ +\ + implement_CHASH(X, ctype, Key, Value, valueDestroy, keyEqualsRaw, keyHashRaw, \ + keyDestroy, RawKey, keyToRaw, keyFromRaw, RawValue, valueFromRaw) /* -------------------------- IMPLEMENTATION ------------------------- */ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) #define implement_CHASH(X, ctype, Key, Value, valueDestroy, keyEqualsRaw, keyHashRaw, \ keyDestroy, RawKey, keyToRaw, keyFromRaw, RawValue, valueFromRaw) \ -STC_API ctype##_##X \ -ctype##_##X##_with_capacity(size_t cap) { \ - ctype##_##X h = ctype##_ini; \ - ctype##_##X##_reserve(&h, cap); \ - return h; \ -} \ -STC_API void \ -ctype##_##X##_push_n(ctype##_##X* self, const ctype##_##X##_input_t in[], size_t size) { \ - for (size_t i=0; isize == 0) return; \ - ctype##_##X##_entry_t* e = self->table, *end = e + self->bucket_count; \ - uint8_t *hx = self->_hashx; \ - for (; e != end; ++e) if (*hx++) ctype##_##X##_entry_destroy(e); \ -} \ - \ -STC_API void ctype##_##X##_destroy(ctype##_##X* self) { \ - ctype##_##X##_wipe_(self); \ - free(self->_hashx); \ - free(self->table); \ -} \ - \ -STC_API void ctype##_##X##_clear(ctype##_##X* self) { \ - ctype##_##X##_wipe_(self); \ - self->size = 0; \ - memset(self->_hashx, 0, self->bucket_count); \ -} \ - \ -STC_API ctype##_bucket_t \ -ctype##_##X##_bucket(const ctype##_##X* self, const ctype##_##X##_rawkey_t* rawKeyPtr) { \ - uint32_t sx, hash = keyHashRaw(rawKeyPtr, sizeof(ctype##_##X##_rawkey_t)); \ - size_t cap = self->bucket_count; \ - ctype##_bucket_t b = {chash_reduce(hash, cap), (hash & chash_HASH) | chash_USED}; \ - uint8_t* hashx = self->_hashx; \ - while ((sx = hashx[b.idx])) { \ - if (sx == b.hx) { \ - ctype##_##X##_rawkey_t r = keyToRaw(&self->table[b.idx].key); \ - if (keyEqualsRaw(&r, rawKeyPtr)) break; \ + STC_API ctype##_##X \ + ctype##_##X##_with_capacity(size_t cap) { \ + ctype##_##X h = ctype##_ini; \ + ctype##_##X##_reserve(&h, cap); \ + return h; \ + } \ + STC_API void \ + ctype##_##X##_push_n(ctype##_##X* self, const ctype##_##X##_input_t in[], size_t size) { \ + for (size_t i=0; isize == 0) return; \ + ctype##_##X##_entry_t* e = self->table, *end = e + self->bucket_count; \ + uint8_t *hx = self->_hashx; \ + for (; e != end; ++e) if (*hx++) ctype##_##X##_entry_destroy(e); \ + } \ +\ + STC_API void ctype##_##X##_destroy(ctype##_##X* self) { \ + ctype##_##X##_wipe_(self); \ + free(self->_hashx); \ + free(self->table); \ + } \ +\ + STC_API void ctype##_##X##_clear(ctype##_##X* self) { \ + ctype##_##X##_wipe_(self); \ + self->size = 0; \ + memset(self->_hashx, 0, self->bucket_count); \ + } \ +\ + STC_API ctype##_bucket_t \ + ctype##_##X##_bucket(const ctype##_##X* self, const ctype##_##X##_rawkey_t* rawKeyPtr) { \ + uint32_t sx, hash = keyHashRaw(rawKeyPtr, sizeof(ctype##_##X##_rawkey_t)); \ + size_t cap = self->bucket_count; \ + ctype##_bucket_t b = {chash_reduce(hash, cap), (hash & chash_HASH) | chash_USED}; \ + uint8_t* hashx = self->_hashx; \ + while ((sx = hashx[b.idx])) { \ + if (sx == b.hx) { \ + ctype##_##X##_rawkey_t r = keyToRaw(&self->table[b.idx].key); \ + if (keyEqualsRaw(&r, rawKeyPtr)) break; \ + } \ + if (++b.idx == cap) b.idx = 0; \ } \ - if (++b.idx == cap) b.idx = 0; \ + return b; \ + } \ +\ + STC_API ctype##_##X##_entry_t* \ + ctype##_##X##_find(const ctype##_##X* self, ctype##_##X##_rawkey_t rawKey) { \ + if (self->size == 0) return NULL; \ + ctype##_bucket_t b = ctype##_##X##_bucket(self, &rawKey); \ + return self->_hashx[b.idx] ? &self->table[b.idx] : NULL; \ } \ - return b; \ -} \ - \ -STC_API ctype##_##X##_entry_t* \ -ctype##_##X##_find(const ctype##_##X* self, ctype##_##X##_rawkey_t rawKey) { \ - if (self->size == 0) return NULL; \ - ctype##_bucket_t b = ctype##_##X##_bucket(self, &rawKey); \ - return self->_hashx[b.idx] ? &self->table[b.idx] : NULL; \ -} \ - \ -STC_INLINE void ctype##_##X##_reserve_expand(ctype##_##X* self) { \ - if (self->size + 1 >= self->bucket_count * self->max_load_factor) \ - ctype##_##X##_reserve(self, 5 + self->size * 3 / 2); \ -} \ -STC_API bool \ -ctype##_##X##_contains(const ctype##_##X* self, ctype##_##X##_rawkey_t rawKey) { \ - return self->size && self->_hashx[ctype##_##X##_bucket(self, &rawKey).idx]; \ -} \ - \ -STC_API ctype##_##X##_result_t \ -ctype##_##X##_insert_key_(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey) { \ - ctype##_##X##_reserve_expand(self); \ - ctype##_bucket_t b = ctype##_##X##_bucket(self, &rawKey); \ - ctype##_##X##_result_t res = {&self->table[b.idx], !self->_hashx[b.idx]}; \ - if (res.inserted) { \ - res.item->key = keyFromRaw(rawKey); \ - self->_hashx[b.idx] = (uint8_t) b.hx; \ - ++self->size; \ +\ + STC_INLINE void ctype##_##X##_reserve_expand(ctype##_##X* self) { \ + if (self->size + 1 >= self->bucket_count * self->max_load_factor) \ + ctype##_##X##_reserve(self, 5 + self->size * 3 / 2); \ } \ - return res; \ -} \ - \ -STC_API size_t \ -ctype##_##X##_reserve(ctype##_##X* self, size_t newcap) { \ - size_t oldcap = self->bucket_count; \ - if (self->size > newcap) return oldcap; \ - newcap = (size_t) (newcap / self->max_load_factor) | 1; \ - ctype##_##X tmp = { \ - c_new_n(ctype##_##X##_entry_t, newcap), \ - (uint8_t *) calloc(newcap + 1, sizeof(uint8_t)), \ - self->size, (uint32_t) newcap, \ - self->max_load_factor, self->shrink_limit_factor \ - }; \ - /* Rehash: */ \ - tmp._hashx[newcap] = 0xff; c_swap(ctype##_##X, *self, tmp); \ - ctype##_##X##_entry_t* e = tmp.table, *slot = self->table; \ - uint8_t* hashx = self->_hashx; \ - for (size_t i = 0; i < oldcap; ++i, ++e) \ - if (tmp._hashx[i]) { \ - ctype##_##X##_rawkey_t r = keyToRaw(&e->key); \ - ctype##_bucket_t b = ctype##_##X##_bucket(self, &r); \ - slot[b.idx] = *e, \ - hashx[b.idx] = (uint8_t) b.hx; \ + STC_API bool \ + ctype##_##X##_contains(const ctype##_##X* self, ctype##_##X##_rawkey_t rawKey) { \ + return self->size && self->_hashx[ctype##_##X##_bucket(self, &rawKey).idx]; \ + } \ +\ + STC_API ctype##_##X##_result_t \ + ctype##_##X##_insert_key_(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey) { \ + ctype##_##X##_reserve_expand(self); \ + ctype##_bucket_t b = ctype##_##X##_bucket(self, &rawKey); \ + ctype##_##X##_result_t res = {&self->table[b.idx], !self->_hashx[b.idx]}; \ + if (res.inserted) { \ + res.item->key = keyFromRaw(rawKey); \ + self->_hashx[b.idx] = (uint8_t) b.hx; \ + ++self->size; \ } \ - free(tmp._hashx); \ - free(tmp.table); \ - return newcap; \ -} \ - \ -STC_API bool \ -ctype##_##X##_erase_entry(ctype##_##X* self, ctype##_##X##_entry_t* item) { \ - size_t i = chash_entry_index(*self, item), j = i, k, cap = self->bucket_count; \ - ctype##_##X##_entry_t* slot = self->table; \ - uint8_t* hashx = self->_hashx; \ - ctype##_##X##_rawkey_t r; \ - if (! hashx[i]) \ - return false; \ - ctype##_##X##_entry_destroy(&slot[i]); \ - do { /* deletion from hash table without tombstone */ \ - if (++j == cap) j = 0; /* ++j; j %= cap; is slow */ \ - if (! hashx[j]) \ - break; \ - r = keyToRaw(&slot[j].key); \ - k = chash_reduce(keyHashRaw(&r, sizeof(ctype##_##X##_rawkey_t)), cap); \ - if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ \ - slot[i] = slot[j], hashx[i] = hashx[j], i = j; \ - } while (true); \ - hashx[i] = 0; \ - --self->size; \ - return true; \ -} \ - \ -STC_API bool \ -ctype##_##X##_erase(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey) { \ - if (self->size == 0) \ - return false; \ - if (self->size < self->bucket_count * self->shrink_limit_factor && self->bucket_count * sizeof(ctype##_##X##_entry_t) > 1024) \ - ctype##_##X##_reserve(self, self->size * 6 / 5); \ - ctype##_bucket_t b = ctype##_##X##_bucket(self, &rawKey); \ - return ctype##_##X##_erase_entry(self, self->table + b.idx); \ -} \ -typedef int ctype##_##X##_dud + return res; \ + } \ +\ + STC_API size_t \ + ctype##_##X##_reserve(ctype##_##X* self, size_t newcap) { \ + size_t oldcap = self->bucket_count; \ + if (self->size > newcap) return oldcap; \ + newcap = (size_t) (newcap / self->max_load_factor) | 1; \ + ctype##_##X tmp = { \ + c_new_n(ctype##_##X##_entry_t, newcap), \ + (uint8_t *) calloc(newcap + 1, sizeof(uint8_t)), \ + self->size, (uint32_t) newcap, \ + self->max_load_factor, self->shrink_limit_factor \ + }; \ + /* Rehash: */ \ + tmp._hashx[newcap] = 0xff; c_swap(ctype##_##X, *self, tmp); \ + ctype##_##X##_entry_t* e = tmp.table, *slot = self->table; \ + uint8_t* hashx = self->_hashx; \ + for (size_t i = 0; i < oldcap; ++i, ++e) \ + if (tmp._hashx[i]) { \ + ctype##_##X##_rawkey_t r = keyToRaw(&e->key); \ + ctype##_bucket_t b = ctype##_##X##_bucket(self, &r); \ + slot[b.idx] = *e, \ + hashx[b.idx] = (uint8_t) b.hx; \ + } \ + free(tmp._hashx); \ + free(tmp.table); \ + return newcap; \ + } \ +\ + STC_API bool \ + ctype##_##X##_erase_entry(ctype##_##X* self, ctype##_##X##_entry_t* item) { \ + size_t i = chash_entry_index(*self, item), j = i, k, cap = self->bucket_count; \ + ctype##_##X##_entry_t* slot = self->table; \ + uint8_t* hashx = self->_hashx; \ + ctype##_##X##_rawkey_t r; \ + if (! hashx[i]) \ + return false; \ + ctype##_##X##_entry_destroy(&slot[i]); \ + do { /* deletion from hash table without tombstone */ \ + if (++j == cap) j = 0; /* ++j; j %= cap; is slow */ \ + if (! hashx[j]) \ + break; \ + r = keyToRaw(&slot[j].key); \ + k = chash_reduce(keyHashRaw(&r, sizeof(ctype##_##X##_rawkey_t)), cap); \ + if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ \ + slot[i] = slot[j], hashx[i] = hashx[j], i = j; \ + } while (true); \ + hashx[i] = 0; \ + --self->size; \ + return true; \ + } \ +\ + STC_API bool \ + ctype##_##X##_erase(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey) { \ + if (self->size == 0) \ + return false; \ + if (self->size < self->bucket_count * self->shrink_limit_factor && self->bucket_count * sizeof(ctype##_##X##_entry_t) > 1024) \ + ctype##_##X##_reserve(self, self->size * 6 / 5); \ + ctype##_bucket_t b = ctype##_##X##_bucket(self, &rawKey); \ + return ctype##_##X##_erase_entry(self, self->table + b.idx); \ + } \ + typedef int ctype##_##X##_dud /* https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ */ diff --git a/stc/cpqueue.h b/stc/cpqueue.h index ea8bd0ed..47612e2c 100644 --- a/stc/cpqueue.h +++ b/stc/cpqueue.h @@ -51,88 +51,89 @@ #include "cvec.h" #define declare_cpqueue(X, ctype, cmpOpr) /* cmpOpr: < or > */ \ - \ -typedef struct ctype cpqueue_##X; \ -typedef ctype##_value_t cpqueue_##X##_value_t; \ -typedef ctype##_rawvalue_t cpqueue_##X##_rawvalue_t; \ -typedef ctype##_input_t cpqueue_##X##_input_t; \ -STC_INLINE cpqueue_##X \ -cpqueue_##X##_init() {return ctype##_init();} \ -STC_INLINE size_t \ -cpqueue_##X##_size(cpqueue_##X pq) {return ctype##_size(pq);} \ -STC_INLINE bool \ -cpqueue_##X##_empty(cpqueue_##X pq) {return ctype##_empty(pq);} \ -STC_INLINE void \ -cpqueue_##X##_destroy(cpqueue_##X* self) {ctype##_destroy(self);} \ -STC_API void \ -cpqueue_##X##_build(cpqueue_##X* self); \ -STC_API void \ -cpqueue_##X##_erase(cpqueue_##X* self, size_t i); \ -STC_INLINE const cpqueue_##X##_value_t* \ -cpqueue_##X##_top(const cpqueue_##X* self) {return &self->data[0];} \ -STC_INLINE void \ -cpqueue_##X##_pop(cpqueue_##X* self) {cpqueue_##X##_erase(self, 0);} \ -STC_API void \ -cpqueue_##X##_push(cpqueue_##X* self, cpqueue_##X##_value_t value); \ -STC_INLINE void \ -cpqueue_##X##_emplace(cpqueue_##X* self, cpqueue_##X##_rawvalue_t rawValue) { \ - cpqueue_##X##_push(self, ctype##_value_from_raw(rawValue)); \ -} \ -STC_API void \ -cpqueue_##X##_push_n(cpqueue_##X *self, const cpqueue_##X##_input_t in[], size_t size); \ - \ -implement_cpqueue(X, ctype, cmpOpr) - +\ + typedef struct ctype cpqueue_##X; \ + typedef ctype##_value_t cpqueue_##X##_value_t; \ + typedef ctype##_rawvalue_t cpqueue_##X##_rawvalue_t; \ + typedef ctype##_input_t cpqueue_##X##_input_t; \ + STC_INLINE cpqueue_##X \ + cpqueue_##X##_init() {return ctype##_init();} \ + STC_INLINE size_t \ + cpqueue_##X##_size(cpqueue_##X pq) {return ctype##_size(pq);} \ + STC_INLINE bool \ + cpqueue_##X##_empty(cpqueue_##X pq) {return ctype##_empty(pq);} \ + STC_INLINE void \ + cpqueue_##X##_destroy(cpqueue_##X* self) {ctype##_destroy(self);} \ + STC_API void \ + cpqueue_##X##_build(cpqueue_##X* self); \ + STC_API void \ + cpqueue_##X##_erase(cpqueue_##X* self, size_t i); \ + STC_INLINE const cpqueue_##X##_value_t* \ + cpqueue_##X##_top(const cpqueue_##X* self) {return &self->data[0];} \ + STC_INLINE void \ + cpqueue_##X##_pop(cpqueue_##X* self) {cpqueue_##X##_erase(self, 0);} \ + STC_API void \ + cpqueue_##X##_push(cpqueue_##X* self, cpqueue_##X##_value_t value); \ + STC_INLINE void \ + cpqueue_##X##_emplace(cpqueue_##X* self, cpqueue_##X##_rawvalue_t rawValue) { \ + cpqueue_##X##_push(self, ctype##_value_from_raw(rawValue)); \ + } \ + STC_API void \ + cpqueue_##X##_push_n(cpqueue_##X *self, const cpqueue_##X##_input_t in[], size_t size); \ +\ + implement_cpqueue(X, ctype, cmpOpr) + /* -------------------------- IMPLEMENTATION ------------------------- */ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) #define implement_cpqueue(X, ctype, cmpOpr) \ - \ -STC_INLINE void \ -_cpqueue_##X##_sift_down(cpqueue_##X##_value_t* arr, size_t i, size_t n) { \ - size_t r = i, c = i << 1; \ - while (c <= n) { \ - if (c < n && ctype##_value_compare(&arr[c], &arr[c + 1]) cmpOpr 0) \ - ++c; \ - if (ctype##_value_compare(&arr[r], &arr[c]) cmpOpr 0) { \ - cpqueue_##X##_value_t tmp = arr[r]; arr[r] = arr[c]; arr[r = c] = tmp; \ - } else \ - return; \ - c <<= 1; \ +\ + STC_INLINE void \ + _cpqueue_##X##_sift_down(cpqueue_##X##_value_t* arr, size_t i, size_t n) { \ + size_t r = i, c = i << 1; \ + while (c <= n) { \ + if (c < n && ctype##_value_compare(&arr[c], &arr[c + 1]) cmpOpr 0) \ + ++c; \ + if (ctype##_value_compare(&arr[r], &arr[c]) cmpOpr 0) { \ + cpqueue_##X##_value_t tmp = arr[r]; arr[r] = arr[c]; arr[r = c] = tmp; \ + } else \ + return; \ + c <<= 1; \ + } \ + } \ +\ + STC_API void \ + cpqueue_##X##_build(cpqueue_##X* self) { \ + size_t n = cpqueue_##X##_size(*self); \ + cpqueue_##X##_value_t *arr = self->data - 1; \ + for (size_t k = n >> 1; k != 0; --k) \ + _cpqueue_##X##_sift_down(arr, k, n); \ + } \ +\ + STC_API void \ + cpqueue_##X##_erase(cpqueue_##X* self, size_t i) { \ + size_t n = cpqueue_##X##_size(*self) - 1; \ + self->data[i] = self->data[n]; \ + ctype##_pop_back(self); \ + _cpqueue_##X##_sift_down(self->data - 1, i + 1, n); \ + } \ +\ + STC_API void \ + cpqueue_##X##_push(cpqueue_##X* self, cpqueue_##X##_value_t value) { \ + ctype##_push_back(self, value); /* sift-up the value */ \ + size_t n = cpqueue_##X##_size(*self), c = n; \ + cpqueue_##X##_value_t *arr = self->data - 1; \ + for (; c > 1 && ctype##_value_compare(&arr[c >> 1], &value) cmpOpr 0; c >>= 1) \ + arr[c] = arr[c >> 1]; \ + if (c != n) arr[c] = value; \ + } \ + STC_API void \ + cpqueue_##X##_push_n(cpqueue_##X *self, const cpqueue_##X##_input_t in[], size_t size) { \ + ctype##_reserve(self, cpqueue_##X##_size(*self) + size); \ + for (size_t i=0; idata - 1; \ - for (size_t k = n >> 1; k != 0; --k) \ - _cpqueue_##X##_sift_down(arr, k, n); \ -} \ - \ -STC_API void \ -cpqueue_##X##_erase(cpqueue_##X* self, size_t i) { \ - size_t n = cpqueue_##X##_size(*self) - 1; \ - self->data[i] = self->data[n]; \ - ctype##_pop_back(self); \ - _cpqueue_##X##_sift_down(self->data - 1, i + 1, n); \ -} \ - \ -STC_API void \ -cpqueue_##X##_push(cpqueue_##X* self, cpqueue_##X##_value_t value) { \ - ctype##_push_back(self, value); /* sift-up the value */ \ - size_t n = cpqueue_##X##_size(*self), c = n; \ - cpqueue_##X##_value_t *arr = self->data - 1; \ - for (; c > 1 && ctype##_value_compare(&arr[c >> 1], &value) cmpOpr 0; c >>= 1) \ - arr[c] = arr[c >> 1]; \ - if (c != n) arr[c] = value; \ -} \ -STC_API void \ -cpqueue_##X##_push_n(cpqueue_##X *self, const cpqueue_##X##_input_t in[], size_t size) { \ - ctype##_reserve(self, cpqueue_##X##_size(*self) + size); \ - for (size_t i=0; idata + ipos}, first = {pfirst}, last = {plast}; \ - return cvec_##X##_insert_range(self, pos, first, last); \ -} \ -STC_INLINE cvec_##X##_iter_t \ -cvec_##X##_insert(cvec_##X* self, cvec_##X##_iter_t pos, Value value) { \ - cvec_##X##_iter_t first = {&value}, last = {&value + 1}; \ - return cvec_##X##_insert_range(self, pos, first, last); \ -} \ -STC_INLINE cvec_##X##_iter_t \ -cvec_##X##_insert_ipos(cvec_##X* self, size_t ipos, Value value) { \ - cvec_##X##_iter_t pos = {self->data + ipos}, first = {&value}, last = {&value + 1}; \ - return cvec_##X##_insert_range(self, pos, first, last); \ -} \ -STC_INLINE cvec_##X##_iter_t \ -cvec_##X##_emplace(cvec_##X* self, cvec_##X##_iter_t pos, RawValue rawValue) { \ - cvec_##X##_insert(self, pos, valueFromRaw(rawValue)); \ -} \ -STC_INLINE cvec_##X##_iter_t \ -cvec_##X##_emplace_ipos(cvec_##X* self, size_t ipos, RawValue rawValue) { \ - cvec_##X##_insert_ipos(self, ipos, valueFromRaw(rawValue)); \ -} \ + STC_API cvec_##X##_iter_t \ + cvec_##X##_insert_range(cvec_##X* self, cvec_##X##_iter_t pos, cvec_##X##_iter_t first, cvec_##X##_iter_t last); \ + \ + STC_INLINE cvec_##X##_iter_t \ + cvec_##X##_insert_irange(cvec_##X* self, size_t ipos, Value* pfirst, Value* plast) { \ + cvec_##X##_iter_t pos = {self->data + ipos}, first = {pfirst}, last = {plast}; \ + return cvec_##X##_insert_range(self, pos, first, last); \ + } \ + STC_INLINE cvec_##X##_iter_t \ + cvec_##X##_insert(cvec_##X* self, cvec_##X##_iter_t pos, Value value) { \ + cvec_##X##_iter_t first = {&value}, last = {&value + 1}; \ + return cvec_##X##_insert_range(self, pos, first, last); \ + } \ + STC_INLINE cvec_##X##_iter_t \ + cvec_##X##_insert_ipos(cvec_##X* self, size_t ipos, Value value) { \ + cvec_##X##_iter_t pos = {self->data + ipos}, first = {&value}, last = {&value + 1}; \ + return cvec_##X##_insert_range(self, pos, first, last); \ + } \ + STC_INLINE cvec_##X##_iter_t \ + cvec_##X##_emplace(cvec_##X* self, cvec_##X##_iter_t pos, RawValue rawValue) { \ + cvec_##X##_insert(self, pos, valueFromRaw(rawValue)); \ + } \ + STC_INLINE cvec_##X##_iter_t \ + cvec_##X##_emplace_ipos(cvec_##X* self, size_t ipos, RawValue rawValue) { \ + cvec_##X##_insert_ipos(self, ipos, valueFromRaw(rawValue)); \ + } \ \ -STC_API cvec_##X##_iter_t \ -cvec_##X##_erase_range(cvec_##X* self, cvec_##X##_iter_t first, cvec_##X##_iter_t last); \ + STC_API cvec_##X##_iter_t \ + cvec_##X##_erase_range(cvec_##X* self, cvec_##X##_iter_t first, cvec_##X##_iter_t last); \ \ -STC_INLINE cvec_##X##_iter_t \ -cvec_##X##_erase(cvec_##X* self, cvec_##X##_iter_t pos) { \ - cvec_##X##_iter_t next = {pos.item + 1}; \ - return cvec_##X##_erase_range(self, pos, next); \ -} \ -STC_INLINE cvec_##X##_iter_t \ -cvec_##X##_erase_ipos(cvec_##X* self, size_t ipos) { \ - cvec_##X##_iter_t first = {self->data + ipos}, last = {first.item + 1}; \ - return cvec_##X##_erase_range(self, first, last); \ -} \ -STC_INLINE cvec_##X##_iter_t \ -cvec_##X##_erase_irange(cvec_##X* self, size_t ifirst, size_t ilast) { \ - cvec_##X##_iter_t first = {self->data + ifirst}, last = {self->data + ilast}; \ - return cvec_##X##_erase_range(self, first, last); \ -} \ + STC_INLINE cvec_##X##_iter_t \ + cvec_##X##_erase(cvec_##X* self, cvec_##X##_iter_t pos) { \ + cvec_##X##_iter_t next = {pos.item + 1}; \ + return cvec_##X##_erase_range(self, pos, next); \ + } \ + STC_INLINE cvec_##X##_iter_t \ + cvec_##X##_erase_ipos(cvec_##X* self, size_t ipos) { \ + cvec_##X##_iter_t first = {self->data + ipos}, last = {first.item + 1}; \ + return cvec_##X##_erase_range(self, first, last); \ + } \ + STC_INLINE cvec_##X##_iter_t \ + cvec_##X##_erase_irange(cvec_##X* self, size_t ifirst, size_t ilast) { \ + cvec_##X##_iter_t first = {self->data + ifirst}, last = {self->data + ilast}; \ + return cvec_##X##_erase_range(self, first, last); \ + } \ \ -STC_API void \ -cvec_##X##_sort(cvec_##X* self); \ -STC_API void \ -cvec_##X##_sort_with(cvec_##X* self, int(*cmp)(const Value*, const Value*)); \ -STC_API cvec_##X##_iter_t \ -cvec_##X##_find(const cvec_##X* self, RawValue rawValue); \ -STC_API cvec_##X##_iter_t \ -cvec_##X##_find_in_range(const cvec_##X* self, cvec_##X##_iter_t first, cvec_##X##_iter_t last, RawValue rawValue); \ -STC_API int \ -cvec_##X##_value_compare(const Value* x, const Value* y); \ + STC_API void \ + cvec_##X##_sort(cvec_##X* self); \ + STC_API void \ + cvec_##X##_sort_with(cvec_##X* self, int(*cmp)(const Value*, const Value*)); \ + STC_API cvec_##X##_iter_t \ + cvec_##X##_find(const cvec_##X* self, RawValue rawValue); \ + STC_API cvec_##X##_iter_t \ + cvec_##X##_find_in_range(const cvec_##X* self, cvec_##X##_iter_t first, cvec_##X##_iter_t last, RawValue rawValue); \ + STC_API int \ + cvec_##X##_value_compare(const Value* x, const Value* y); \ \ -STC_INLINE cvec_##X \ -cvec_##X##_with_size(size_t size, Value null_val) { \ - cvec_##X x = cvec_ini; \ - cvec_##X##_resize(&x, size, null_val); \ - return x; \ -} \ -STC_INLINE cvec_##X \ -cvec_##X##_with_capacity(size_t size) { \ - cvec_##X x = cvec_ini; \ - cvec_##X##_reserve(&x, size); \ - return x; \ -} \ -STC_INLINE void \ -cvec_##X##_pop_back(cvec_##X* self) { \ - valueDestroy(&self->data[--_cvec_size(self)]); \ -} \ -STC_INLINE Value* \ -cvec_##X##_front(cvec_##X* self) {return self->data;} \ -STC_INLINE Value* \ -cvec_##X##_back(cvec_##X* self) {return self->data + _cvec_size(self) - 1;} \ -STC_INLINE Value* \ -cvec_##X##_at(cvec_##X* self, size_t i) {return self->data + i;} \ -STC_INLINE void \ -cvec_##X##_swap(cvec_##X* a, cvec_##X* b) { \ - c_swap(Value*, a->data, b->data); \ -} \ -STC_INLINE void \ -cvec_##X##_sort(cvec_##X* self) { \ - qsort(self->data, cvec_size(*self), sizeof(Value), (_cvec_cmp) cvec_##X##_value_compare); \ -} \ -STC_INLINE void \ -cvec_##X##_sort_with(cvec_##X* self, int(*cmp)(const Value*, const Value*)) { \ - qsort(self->data, cvec_size(*self), sizeof(Value), (_cvec_cmp) cmp); \ -} \ + STC_INLINE cvec_##X \ + cvec_##X##_with_size(size_t size, Value null_val) { \ + cvec_##X x = cvec_ini; \ + cvec_##X##_resize(&x, size, null_val); \ + return x; \ + } \ + STC_INLINE cvec_##X \ + cvec_##X##_with_capacity(size_t size) { \ + cvec_##X x = cvec_ini; \ + cvec_##X##_reserve(&x, size); \ + return x; \ + } \ + STC_INLINE void \ + cvec_##X##_pop_back(cvec_##X* self) { \ + valueDestroy(&self->data[--_cvec_size(self)]); \ + } \ + STC_INLINE Value* \ + cvec_##X##_front(cvec_##X* self) {return self->data;} \ + STC_INLINE Value* \ + cvec_##X##_back(cvec_##X* self) {return self->data + _cvec_size(self) - 1;} \ + STC_INLINE Value* \ + cvec_##X##_at(cvec_##X* self, size_t i) {return self->data + i;} \ + STC_INLINE void \ + cvec_##X##_swap(cvec_##X* a, cvec_##X* b) { \ + c_swap(Value*, a->data, b->data); \ + } \ + STC_INLINE void \ + cvec_##X##_sort(cvec_##X* self) { \ + qsort(self->data, cvec_size(*self), sizeof(Value), (_cvec_cmp) cvec_##X##_value_compare); \ + } \ + STC_INLINE void \ + cvec_##X##_sort_with(cvec_##X* self, int(*cmp)(const Value*, const Value*)) { \ + qsort(self->data, cvec_size(*self), sizeof(Value), (_cvec_cmp) cmp); \ + } \ \ -STC_INLINE cvec_##X##_iter_t \ -cvec_##X##_begin(const cvec_##X* self) { \ - cvec_##X##_iter_t it = {self->data}; return it; \ -} \ -STC_INLINE cvec_##X##_iter_t \ -cvec_##X##_end(const cvec_##X* self) { \ - cvec_##X##_iter_t it = {self->data + cvec_size(*self)}; return it; \ -} \ -STC_INLINE void \ -cvec_##X##_next(cvec_##X##_iter_t* it) {++it->item;} \ -STC_INLINE cvec_##X##_value_t* \ -cvec_##X##_itval(cvec_##X##_iter_t it) {return it.item;} \ + STC_INLINE cvec_##X##_iter_t \ + cvec_##X##_begin(const cvec_##X* self) { \ + cvec_##X##_iter_t it = {self->data}; return it; \ + } \ + STC_INLINE cvec_##X##_iter_t \ + cvec_##X##_end(const cvec_##X* self) { \ + cvec_##X##_iter_t it = {self->data + cvec_size(*self)}; return it; \ + } \ + STC_INLINE void \ + cvec_##X##_next(cvec_##X##_iter_t* it) {++it->item;} \ + STC_INLINE cvec_##X##_value_t* \ + cvec_##X##_itval(cvec_##X##_iter_t it) {return it.item;} \ \ -implement_cvec_7(X, Value, valueDestroy, RawValue, valueCompareRaw, valueToRaw, valueFromRaw) + implement_cvec_7(X, Value, valueDestroy, RawValue, valueCompareRaw, valueToRaw, valueFromRaw) /* -------------------------- IMPLEMENTATION ------------------------- */ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) #define implement_cvec_7(X, Value, valueDestroy, RawValue, valueCompareRaw, valueToRaw, valueFromRaw) \ \ -STC_API void \ -cvec_##X##_push_n(cvec_##X *self, const cvec_##X##_input_t in[], size_t size) { \ - cvec_##X##_reserve(self, cvec_size(*self) + size); \ - _cvec_size(self) += size; \ - for (size_t i=0; idata[i] = valueFromRaw(in[i]); \ -} \ + STC_API void \ + cvec_##X##_push_n(cvec_##X *self, const cvec_##X##_input_t in[], size_t size) { \ + cvec_##X##_reserve(self, cvec_size(*self) + size); \ + _cvec_size(self) += size; \ + for (size_t i=0; idata[i] = valueFromRaw(in[i]); \ + } \ \ -STC_API void \ -cvec_##X##_clear(cvec_##X* self) { \ - Value* p = self->data; if (p) { \ - for (Value* q = p + _cvec_size(self); p != q; ++p) valueDestroy(p); \ - _cvec_size(self) = 0; \ + STC_API void \ + cvec_##X##_clear(cvec_##X* self) { \ + Value* p = self->data; if (p) { \ + for (Value* q = p + _cvec_size(self); p != q; ++p) valueDestroy(p); \ + _cvec_size(self) = 0; \ + } \ + } \ + STC_API void \ + cvec_##X##_destroy(cvec_##X* self) { \ + cvec_##X##_clear(self); \ + if (self->data) free(_cvec_alloced(self->data)); \ } \ -} \ -STC_API void \ -cvec_##X##_destroy(cvec_##X* self) { \ - cvec_##X##_clear(self); \ - if (self->data) free(_cvec_alloced(self->data)); \ -} \ \ -STC_API void \ -cvec_##X##_reserve(cvec_##X* self, size_t cap) { \ - size_t len = cvec_size(*self); \ - if (cap >= len) { \ - size_t* rep = (size_t *) realloc(_cvec_alloced(self->data), 2 * sizeof(size_t) + cap * sizeof(Value)); \ - self->data = (Value *) (rep + 2); \ - rep[0] = len; \ - rep[1] = cap; \ + STC_API void \ + cvec_##X##_reserve(cvec_##X* self, size_t cap) { \ + size_t len = cvec_size(*self); \ + if (cap >= len) { \ + size_t* rep = (size_t *) realloc(_cvec_alloced(self->data), 2 * sizeof(size_t) + cap * sizeof(Value)); \ + self->data = (Value *) (rep + 2); \ + rep[0] = len; \ + rep[1] = cap; \ + } \ + } \ + STC_API void \ + cvec_##X##_resize(cvec_##X* self, size_t size, Value null_val) { \ + cvec_##X##_reserve(self, size); \ + for (size_t i=cvec_size(*self); idata[i] = null_val; \ + if (self->data) _cvec_size(self) = size; \ } \ -} \ -STC_API void \ -cvec_##X##_resize(cvec_##X* self, size_t size, Value null_val) { \ - cvec_##X##_reserve(self, size); \ - for (size_t i=cvec_size(*self); idata[i] = null_val; \ - if (self->data) _cvec_size(self) = size; \ -} \ \ -STC_API void \ -cvec_##X##_push_back(cvec_##X* self, Value value) { \ - size_t len = cvec_size(*self); \ - if (len == cvec_capacity(*self)) \ - cvec_##X##_reserve(self, 4 + len * 3 / 2); \ - self->data[_cvec_size(self)++] = value; \ -} \ + STC_API void \ + cvec_##X##_push_back(cvec_##X* self, Value value) { \ + size_t len = cvec_size(*self); \ + if (len == cvec_capacity(*self)) \ + cvec_##X##_reserve(self, 4 + len * 3 / 2); \ + self->data[_cvec_size(self)++] = value; \ + } \ \ -STC_API cvec_##X##_iter_t \ -cvec_##X##_insert_range(cvec_##X* self, cvec_##X##_iter_t pos, cvec_##X##_iter_t first, cvec_##X##_iter_t last) { \ - enum {max_buf = c_max_alloca / sizeof(Value) + 1}; Value buf[max_buf]; \ - size_t len = last.item - first.item, ipos = pos.item - self->data, size = cvec_size(*self); \ - Value* xbuf = (Value *) memcpy(len > max_buf ? c_new_n(Value, len) : buf, first.item, len); \ - if (size + len > cvec_capacity(*self)) \ - cvec_##X##_reserve(self, 4 + (size + len) * 3 / 2); \ - pos.item = self->data + ipos; \ - memmove(pos.item + len, pos.item, (size - ipos) * sizeof(Value)); \ - memcpy(pos.item, xbuf, len * sizeof(Value)); \ - _cvec_size(self) += len; \ - if (len > max_buf) free(xbuf); \ - return pos; \ -} \ + STC_API cvec_##X##_iter_t \ + cvec_##X##_insert_range(cvec_##X* self, cvec_##X##_iter_t pos, cvec_##X##_iter_t first, cvec_##X##_iter_t last) { \ + enum {max_buf = c_max_alloca / sizeof(Value) + 1}; Value buf[max_buf]; \ + size_t len = last.item - first.item, ipos = pos.item - self->data, size = cvec_size(*self); \ + Value* xbuf = (Value *) memcpy(len > max_buf ? c_new_n(Value, len) : buf, first.item, len); \ + if (size + len > cvec_capacity(*self)) \ + cvec_##X##_reserve(self, 4 + (size + len) * 3 / 2); \ + pos.item = self->data + ipos; \ + memmove(pos.item + len, pos.item, (size - ipos) * sizeof(Value)); \ + memcpy(pos.item, xbuf, len * sizeof(Value)); \ + _cvec_size(self) += len; \ + if (len > max_buf) free(xbuf); \ + return pos; \ + } \ \ -STC_API cvec_##X##_iter_t \ -cvec_##X##_erase_range(cvec_##X* self, cvec_##X##_iter_t first, cvec_##X##_iter_t last) { \ - intptr_t len = last.item - first.item; \ - if (len > 0) { \ - Value* p = first.item, *end = p + _cvec_size(self); \ - while (p != last.item) valueDestroy(p++); \ - memmove(first.item, last.item, (end - last.item) * sizeof(Value)); \ - _cvec_size(self) -= len; \ + STC_API cvec_##X##_iter_t \ + cvec_##X##_erase_range(cvec_##X* self, cvec_##X##_iter_t first, cvec_##X##_iter_t last) { \ + intptr_t len = last.item - first.item; \ + if (len > 0) { \ + Value* p = first.item, *end = p + _cvec_size(self); \ + while (p != last.item) valueDestroy(p++); \ + memmove(first.item, last.item, (end - last.item) * sizeof(Value)); \ + _cvec_size(self) -= len; \ + } \ + return first; \ } \ - return first; \ -} \ \ -STC_API cvec_##X##_iter_t \ -cvec_##X##_find_in_range(const cvec_##X* self, cvec_##X##_iter_t first, cvec_##X##_iter_t last, RawValue rawValue) { \ - for (; first.item != last.item; cvec_##X##_next(&first)) { \ - RawValue r = valueToRaw(first.item); \ - if (valueCompareRaw(&r, &rawValue) == 0) return first; \ + STC_API cvec_##X##_iter_t \ + cvec_##X##_find_in_range(const cvec_##X* self, cvec_##X##_iter_t first, cvec_##X##_iter_t last, RawValue rawValue) { \ + for (; first.item != last.item; cvec_##X##_next(&first)) { \ + RawValue r = valueToRaw(first.item); \ + if (valueCompareRaw(&r, &rawValue) == 0) return first; \ + } \ + return cvec_##X##_end(self); \ + } \ + STC_API cvec_##X##_iter_t \ + cvec_##X##_find(const cvec_##X* self, RawValue rawValue) { \ + return cvec_##X##_find_in_range(self, cvec_##X##_begin(self), cvec_##X##_end(self), rawValue); \ } \ - return cvec_##X##_end(self); \ -} \ -STC_API cvec_##X##_iter_t \ -cvec_##X##_find(const cvec_##X* self, RawValue rawValue) { \ - return cvec_##X##_find_in_range(self, cvec_##X##_begin(self), cvec_##X##_end(self), rawValue); \ -} \ \ -STC_API int \ -cvec_##X##_value_compare(const Value* x, const Value* y) { \ - RawValue rx = valueToRaw(x); \ - RawValue ry = valueToRaw(y); \ - return valueCompareRaw(&rx, &ry); \ -} \ -typedef int cvec_##taq##_dud + STC_API int \ + cvec_##X##_value_compare(const Value* x, const Value* y) { \ + RawValue rx = valueToRaw(x); \ + RawValue ry = valueToRaw(y); \ + return valueCompareRaw(&rx, &ry); \ + } \ + typedef int cvec_##taq##_dud #else #define implement_cvec_7(X, Value, valueDestroy, valueCompareRaw, RawValue, valueToRaw, valueFromRaw) -- cgit v1.2.3