From a4e2ee22fd57665d2388d5debc17db896a4a389f Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 3 Sep 2020 12:59:41 +0200 Subject: Changed constant _init to _ini to avoid conflict with _init() method. Reverted name cprique back to cpqueue. --- stc/cbitset.h | 2 +- stc/clist.h | 6 +-- stc/cmap.h | 12 ++--- stc/coption.h | 6 +-- stc/cpqueue.h | 141 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ stc/cprique.h | 141 ---------------------------------------------------------- stc/cqueue.h | 4 +- stc/cstack.h | 4 +- stc/cstr.h | 29 +++++++----- stc/cvec.h | 8 ++-- 10 files changed, 179 insertions(+), 174 deletions(-) create mode 100644 stc/cpqueue.h delete mode 100644 stc/cprique.h (limited to 'stc') diff --git a/stc/cbitset.h b/stc/cbitset.h index 31dd3f18..32659a36 100644 --- a/stc/cbitset.h +++ b/stc/cbitset.h @@ -48,7 +48,7 @@ int main() { typedef struct cbitset { uint64_t* _arr; size_t size; } cbitset_t; -#define cbitset_init {NULL, 0} +#define cbitset_ini {NULL, 0} STC_API void cbitset_resize(cbitset_t* self, size_t size, bool value); STC_API size_t cbitset_count(cbitset_t set); diff --git a/stc/clist.h b/stc/clist.h index 39479a09..530cd222 100644 --- a/stc/clist.h +++ b/stc/clist.h @@ -38,7 +38,7 @@ declare_clist(ix, int64_t); int main() { - clist_ix list = clist_init; + clist_ix list = clist_ini; crand_rng32_t pcg = crand_rng32_init(12345); int n; for (int i=0; i<1000000; ++i) // one million @@ -82,7 +82,7 @@ clist_##tag##_node_t *item, *end, **_last; \ } clist_##tag##_iter_t -#define clist_init {NULL} +#define clist_ini {NULL} #define clist_empty(list) ((list).last == NULL) @@ -97,7 +97,7 @@ STC_API size_t _clist_size(const clist_void* self); typedef clist_##tag##_rawvalue_t clist_##tag##_input_t; \ \ STC_INLINE clist_##tag \ - clist_##tag##_init(void) {clist_##tag x = clist_init; return x;} \ + clist_##tag##_init(void) {clist_##tag x = clist_ini; return x;} \ STC_INLINE bool \ clist_##tag##_empty(clist_##tag ls) {return clist_empty(ls);} \ STC_INLINE size_t \ diff --git a/stc/cmap.h b/stc/cmap.h index 615ab7cb..44f39174 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -28,13 +28,13 @@ declare_cset(sx, int); // Set of int declare_cmap(mx, int, char); // Map of int -> char int main(void) { - cset_sx s = cset_init; + cset_sx s = cset_ini; cset_sx_put(&s, 5); cset_sx_put(&s, 8); c_foreach (i, cset_sx, s) printf("set %d\n", i.item->key); cset_sx_destroy(&s); - cmap_mx m = cmap_init; + cmap_mx m = cmap_ini; cmap_mx_put(&m, 5, 'a'); cmap_mx_put(&m, 8, 'b'); cmap_mx_put(&m, 12, 'c'); @@ -53,11 +53,11 @@ int main(void) { #include #include "cdefs.h" -#define cmap_init {NULL, NULL, 0, 0, 0.85f, 0.15f} +#define cmap_ini {NULL, NULL, 0, 0, 0.85f, 0.15f} #define cmap_empty(m) ((m).size == 0) #define cmap_size(m) ((size_t) (m).size) #define cmap_bucket_count(m) ((size_t) (m).bucket_count) -#define cset_init cmap_init +#define cset_ini cmap_ini #define cset_size(s) cmap_size(s) #define cset_bucket_count(s) cmap_bucket_count(s) #define cmap_try_emplace(tag, self, k, v) do { \ @@ -181,7 +181,7 @@ typedef struct { \ } ctype##_##tag##_iter_t; \ \ STC_INLINE ctype##_##tag \ -ctype##_##tag##_init(void) {ctype##_##tag m = cmap_init; return m;} \ +ctype##_##tag##_init(void) {ctype##_##tag m = cmap_ini; return m;} \ STC_INLINE bool \ ctype##_##tag##_empty(ctype##_##tag m) {return m.size == 0;} \ STC_INLINE size_t \ @@ -265,7 +265,7 @@ implement_CHASH(tag, ctype, Key, Value, valueDestroy, keyEqualsRaw, keyHashRaw, keyDestroy, RawKey, keyToRaw, keyFromRaw, RawValue, valueFromRaw) \ STC_API ctype##_##tag \ ctype##_##tag##_with_capacity(size_t cap) { \ - ctype##_##tag h = ctype##_init; \ + ctype##_##tag h = ctype##_ini; \ ctype##_##tag##_reserve(&h, cap); \ return h; \ } \ diff --git a/stc/coption.h b/stc/coption.h index e1c6e7cb..4b0712d6 100644 --- a/stc/coption.h +++ b/stc/coption.h @@ -43,7 +43,7 @@ Example: const char* optstr = "xy:z::123"; printf("program -x -y ARG -z [ARG] -1 -2 -3 --foo --bar ARG --opt [ARG] [ARGUMENTS]\n"); int c; - coption_t opt = coption_init; + coption_t opt = coption_ini; while ((c = coption_get(&opt, argc, argv, optstr, longopts)) != -1) { switch (c) { case '?': printf("error: unknown option: %s\n", opt.faulty); break; @@ -83,7 +83,7 @@ typedef struct { int val; } coption_long_t; -static const coption_t coption_init = {1, 0, NULL, NULL, -1, 1, 0, 0, {'-', '?', '\0'}}; +static const coption_t coption_ini = {1, 0, NULL, NULL, -1, 1, 0, 0, {'-', '?', '\0'}}; static void _coption_permute(char *argv[], int j, int n) { /* move argv[j] over n elements to the left */ int k; @@ -93,7 +93,7 @@ static void _coption_permute(char *argv[], int j, int n) { /* move argv[j] over argv[j - k] = p; } -/* @param opt output; must be initialized to coption_init on first call +/* @param opt output; must be initialized to coption_ini on first call * @return ASCII val for a short option; longopt.val for a long option; * -1 if argv[] is fully processed; '?' for an unknown option or * an ambiguous long option; ':' if an option argument is missing diff --git a/stc/cpqueue.h b/stc/cpqueue.h new file mode 100644 index 00000000..8873b0cd --- /dev/null +++ b/stc/cpqueue.h @@ -0,0 +1,141 @@ +/* MIT License + * + * Copyright (c) 2020 Tyge Løvset, NORCE, www.norceresearch.no + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +/* Priority Queue using heap, with adapter class (normally cvec). + + #include + #include + declare_cvec(f, float); + declare_cpqueue(f, cvec_f, >); // min-heap (increasing values) + + int main() { + crand_rng32_t gen = crand_rng32_init(1234); + crand_uniform_f32_t dist = crand_uniform_f32_init(10.0f, 100.0f); + + cpqueue_f queue = cpqueue_f_init(); + // Push ten million random numbers onto the queue. + for (int i=0; i<10000000; ++i) + cpqueue_f_push(&queue, crand_uniform_f32(&gen, dist)); + // Extract the 100 smallest. + for (int i=0; i<100; ++i) { + printf("%f ", *cpqueue_f_top(queue)); + cpqueue_f_pop(&queue); + } + cpqueue_f_destroy(&queue); + } +*/ + +#ifndef CPQUEUE__H__ +#define CPQUEUE__H__ + +#include "cvec.h" + +#define declare_cpqueue(tag, ctype, cmpOpr) /* cmpOpr: < or > */ \ + \ +typedef struct ctype cpqueue_##tag; \ +typedef ctype##_value_t cpqueue_##tag##_value_t; \ +typedef ctype##_rawvalue_t cpqueue_##tag##_rawvalue_t; \ +typedef ctype##_input_t cpqueue_##tag##_input_t; \ +STC_INLINE cpqueue_##tag \ +cpqueue_##tag##_init() {return ctype##_init();} \ +STC_INLINE size_t \ +cpqueue_##tag##_size(cpqueue_##tag pq) {return ctype##_size(pq);} \ +STC_INLINE bool \ +cpqueue_##tag##_empty(cpqueue_##tag pq) {return ctype##_empty(pq);} \ +STC_INLINE void \ +cpqueue_##tag##_destroy(cpqueue_##tag* self) {ctype##_destroy(self);} \ +STC_API void \ +cpqueue_##tag##_build(cpqueue_##tag* self); \ +STC_API void \ +cpqueue_##tag##_erase(cpqueue_##tag* self, size_t i); \ +STC_INLINE const cpqueue_##tag##_value_t* \ +cpqueue_##tag##_top(const cpqueue_##tag* self) {return &self->data[0];} \ +STC_INLINE void \ +cpqueue_##tag##_pop(cpqueue_##tag* self) {cpqueue_##tag##_erase(self, 0);} \ +STC_API void \ +cpqueue_##tag##_push_v(cpqueue_##tag* self, cpqueue_##tag##_value_t value); \ +STC_INLINE void \ +cpqueue_##tag##_push(cpqueue_##tag* self, cpqueue_##tag##_rawvalue_t rawValue) { \ + cpqueue_##tag##_push_v(self, ctype##_value_from_raw(rawValue)); \ +} \ +STC_API void \ +cpqueue_##tag##_push_n(cpqueue_##tag *self, const cpqueue_##tag##_input_t in[], size_t size); \ + \ +implement_cpqueue(tag, ctype, cmpOpr) + +/* -------------------------- IMPLEMENTATION ------------------------- */ + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) +#define implement_cpqueue(tag, ctype, cmpOpr) \ + \ +STC_INLINE void \ +_cpqueue_##tag##_sift_down(cpqueue_##tag##_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_##tag##_value_t t = arr[r]; arr[r] = arr[c]; arr[r = c] = t; \ + } else \ + return; \ + c <<= 1; \ + } \ +} \ + \ +STC_API void \ +cpqueue_##tag##_build(cpqueue_##tag* self) { \ + size_t n = cpqueue_##tag##_size(*self); \ + cpqueue_##tag##_value_t *arr = self->data - 1; \ + for (size_t k = n >> 1; k != 0; --k) \ + _cpqueue_##tag##_sift_down(arr, k, n); \ +} \ + \ +STC_API void \ +cpqueue_##tag##_erase(cpqueue_##tag* self, size_t i) { \ + size_t n = cpqueue_##tag##_size(*self) - 1; \ + self->data[i] = self->data[n]; \ + ctype##_pop_back(self); \ + _cpqueue_##tag##_sift_down(self->data - 1, i + 1, n); \ +} \ + \ +STC_API void \ +cpqueue_##tag##_push_v(cpqueue_##tag* self, cpqueue_##tag##_value_t value) { \ + ctype##_push_back(self, value); /* sift-up the value */ \ + size_t n = cpqueue_##tag##_size(*self), c = n; \ + cpqueue_##tag##_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_##tag##_push_n(cpqueue_##tag *self, const cpqueue_##tag##_input_t in[], size_t size) { \ + ctype##_reserve(self, cpqueue_##tag##_size(*self) + size); \ + for (size_t i=0; i - #include - declare_cvec(f, float); - declare_cprique(f, cvec_f, >); // min-heap (increasing values) - - int main() { - crand_rng32_t gen = crand_rng32_init(1234); - crand_uniform_f32_t dist = crand_uniform_f32_init(10.0f, 100.0f); - - cprique_f queue = cprique_f_init(); - // Push ten million random numbers onto the queue. - for (int i=0; i<10000000; ++i) - cprique_f_push(&queue, crand_uniform_f32(&gen, dist)); - // Extract the 100 smallest. - for (int i=0; i<100; ++i) { - printf("%f ", *cprique_f_top(queue)); - cprique_f_pop(&queue); - } - cprique_f_destroy(&queue); - } -*/ - -#ifndef CPRIQUE__H__ -#define CPRIQUE__H__ - -#include "cvec.h" - -#define declare_cprique(tag, ctype, cmpOpr) /* cmpOpr: < or > */ \ - \ -typedef ctype cprique_##tag; \ -typedef ctype##_value_t cprique_##tag##_value_t; \ -typedef ctype##_rawvalue_t cprique_##tag##_rawvalue_t; \ -typedef ctype##_input_t cprique_##tag##_input_t; \ -STC_INLINE cprique_##tag \ -cprique_##tag##_init() {return ctype##_init();} \ -STC_INLINE size_t \ -cprique_##tag##_size(cprique_##tag pq) {return ctype##_size(pq);} \ -STC_INLINE bool \ -cprique_##tag##_empty(cprique_##tag pq) {return ctype##_empty(pq);} \ -STC_INLINE void \ -cprique_##tag##_destroy(cprique_##tag* self) {ctype##_destroy(self);} \ -STC_API void \ -cprique_##tag##_build(cprique_##tag* self); \ -STC_API void \ -cprique_##tag##_erase(cprique_##tag* self, size_t i); \ -STC_INLINE const cprique_##tag##_value_t* \ -cprique_##tag##_top(const cprique_##tag* self) {return &self->data[0];} \ -STC_INLINE void \ -cprique_##tag##_pop(cprique_##tag* self) {cprique_##tag##_erase(self, 0);} \ -STC_API void \ -cprique_##tag##_push_v(cprique_##tag* self, cprique_##tag##_value_t value); \ -STC_INLINE void \ -cprique_##tag##_push(cprique_##tag* self, cprique_##tag##_rawvalue_t rawValue) { \ - cprique_##tag##_push_v(self, ctype##_value_from_raw(rawValue)); \ -} \ -STC_API void \ -cprique_##tag##_push_n(cprique_##tag *self, const cprique_##tag##_input_t in[], size_t size); \ - \ -implement_cprique(tag, ctype, cmpOpr) - -/* -------------------------- IMPLEMENTATION ------------------------- */ - -#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -#define implement_cprique(tag, ctype, cmpOpr) \ - \ -STC_INLINE void \ -_cprique_##tag##_sift_down(cprique_##tag##_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) { \ - cprique_##tag##_value_t t = arr[r]; arr[r] = arr[c]; arr[r = c] = t; \ - } else \ - return; \ - c <<= 1; \ - } \ -} \ - \ -STC_API void \ -cprique_##tag##_build(cprique_##tag* self) { \ - size_t n = cprique_##tag##_size(*self); \ - cprique_##tag##_value_t *arr = self->data - 1; \ - for (size_t k = n >> 1; k != 0; --k) \ - _cprique_##tag##_sift_down(arr, k, n); \ -} \ - \ -STC_API void \ -cprique_##tag##_erase(cprique_##tag* self, size_t i) { \ - size_t n = cprique_##tag##_size(*self) - 1; \ - self->data[i] = self->data[n]; \ - ctype##_pop_back(self); \ - _cprique_##tag##_sift_down(self->data - 1, i + 1, n); \ -} \ - \ -STC_API void \ -cprique_##tag##_push_v(cprique_##tag* self, cprique_##tag##_value_t value) { \ - ctype##_push_back(self, value); /* sift-up the value */ \ - size_t n = cprique_##tag##_size(*self), c = n; \ - cprique_##tag##_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 \ -cprique_##tag##_push_n(cprique_##tag *self, const cprique_##tag##_input_t in[], size_t size) { \ - ctype##_reserve(self, cprique_##tag##_size(*self) + size); \ - for (size_t i=0; i> 4) * 16 - 9) +STC_INLINE cstr_t +cstr_init() {return cstr_ini;} + STC_INLINE void cstr_destroy(cstr_t* self) { if (cstr_capacity(*self)) @@ -81,13 +84,13 @@ cstr_destroy(cstr_t* self) { STC_INLINE cstr_t cstr_with_capacity(size_t cap) { - cstr_t s = cstr_init; + cstr_t s = cstr_ini; cstr_reserve(&s, cap); return s; } STC_INLINE cstr_t cstr_with_size(size_t len, char fill) { - cstr_t s = cstr_init; + cstr_t s = cstr_ini; cstr_resize(&s, len, fill); return s; } @@ -106,6 +109,11 @@ cstr_clear(cstr_t* self) { self->str[_cstr_size(*self) = 0] = '\0'; } +STC_INLINE char* +cstr_front(cstr_t* self) {return self->str;} +STC_INLINE char* +cstr_back(cstr_t* self) {return self->str + _cstr_size(*self) - 1;} + STC_INLINE cstr_iter_t cstr_begin(cstr_t* self) { cstr_iter_t it = {self->str, self->str + cstr_size(*self)}; return it; @@ -128,7 +136,7 @@ cstr_take(cstr_t* self, cstr_t s) { STC_INLINE cstr_t cstr_move(cstr_t* self) { cstr_t tmp = *self; - *self = cstr_init; + *self = cstr_ini; return tmp; } @@ -136,14 +144,11 @@ STC_INLINE cstr_t* cstr_append(cstr_t* self, const char* str) { return cstr_append_n(self, str, strlen(str)); } -/*STC_INLINE void -cstr_push_n(cstr_t* self, const cstr_input_t[] in, size_t n) { - cstr_append_n(self, in, n); -}*/ STC_INLINE cstr_t* cstr_push_back(cstr_t* self, char value) { return cstr_append_n(self, &value, 1); } + STC_INLINE void cstr_pop_back(cstr_t* self) { self->str[ --_cstr_size(*self) ] = '\0'; @@ -228,7 +233,7 @@ cstr_resize(cstr_t* self, size_t len, char fill) { STC_API cstr_t cstr_make_n(const char* str, size_t len) { - if (len == 0) return cstr_init; + if (len == 0) return cstr_ini; size_t *rep = (size_t *) malloc(_cstr_mem(len)); cstr_t s = {(char *) memcpy(rep + 2, str, len)}; s.str[rep[0] = len] = '\0'; @@ -245,7 +250,7 @@ cstr_from(const char* fmt, ...) { # pragma warning(push) # pragma warning(disable: 4996) #endif - cstr_t tmp = cstr_init; + cstr_t tmp = cstr_ini; va_list args, args2; va_start(args, fmt); va_copy(args2, args); diff --git a/stc/cvec.h b/stc/cvec.h index 7a753b70..0e72b142 100644 --- a/stc/cvec.h +++ b/stc/cvec.h @@ -27,7 +27,7 @@ #include #include "cdefs.h" -#define cvec_init {NULL} +#define cvec_ini {NULL} #define cvec_size(v) _cvec_safe_size((v).data) #define cvec_capacity(v) _cvec_safe_capacity((v).data) #define cvec_empty(v) (_cvec_safe_size((v).data) == 0) @@ -55,7 +55,7 @@ typedef RawValue cvec_##tag##_rawvalue_t; \ typedef cvec_##tag##_rawvalue_t cvec_##tag##_input_t; \ \ STC_INLINE cvec_##tag \ -cvec_##tag##_init(void) {cvec_##tag v = cvec_init; return v;} \ +cvec_##tag##_init(void) {cvec_##tag v = cvec_ini; return v;} \ STC_INLINE bool \ cvec_##tag##_empty(cvec_##tag v) {return cvec_empty(v);} \ STC_INLINE size_t \ @@ -97,13 +97,13 @@ cvec_##tag##_value_compare(const Value* x, const Value* y); \ \ STC_INLINE cvec_##tag \ cvec_##tag##_with_size(size_t size, Value null_val) { \ - cvec_##tag x = cvec_init; \ + cvec_##tag x = cvec_ini; \ cvec_##tag##_resize(&x, size, null_val); \ return x; \ } \ STC_INLINE cvec_##tag \ cvec_##tag##_with_capacity(size_t size) { \ - cvec_##tag x = cvec_init; \ + cvec_##tag x = cvec_ini; \ cvec_##tag##_reserve(&x, size); \ return x; \ } \ -- cgit v1.2.3