From a084c423f73018aec5c49d8bcbaa38080c277cfb Mon Sep 17 00:00:00 2001 From: tylo Date: Wed, 11 Mar 2020 12:17:12 +0100 Subject: NEW API --- benchmark.cpp | 4 +- c_defs.h | 64 +++++++++++++++ c_hashmap.h | 225 +++++++++++++++++++++++++++++++++++++++++++++++++++++ c_string.h | 244 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ c_vector.h | 147 +++++++++++++++++++++++++++++++++++ cdefs.h | 64 --------------- cmap.h | 225 ----------------------------------------------------- cmap_test.c | 4 +- cstring.h | 244 ---------------------------------------------------------- cvector.h | 147 ----------------------------------- 10 files changed, 684 insertions(+), 684 deletions(-) create mode 100644 c_defs.h create mode 100644 c_hashmap.h create mode 100644 c_string.h create mode 100644 c_vector.h delete mode 100644 cdefs.h delete mode 100644 cmap.h delete mode 100644 cstring.h delete mode 100644 cvector.h diff --git a/benchmark.cpp b/benchmark.cpp index b6a2f472..d88a38fa 100644 --- a/benchmark.cpp +++ b/benchmark.cpp @@ -2,12 +2,12 @@ #include #include #include "c_string.h" -#include "c_hashmap_.h" +#include "c_hashmap.h" #include c_declare_Hashmap(ii, int, int); -declare_c_StringVector(s); +c_declare_Vector_string(s); int main() { diff --git a/c_defs.h b/c_defs.h new file mode 100644 index 00000000..e2914ddf --- /dev/null +++ b/c_defs.h @@ -0,0 +1,64 @@ +// 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. + +#ifndef C_DEFS__H__ +#define C_DEFS__H__ + +#include +#include + +// Macro overloading feature support: https://rextester.com/ONP80107 +#define c_defs_CAT( A, B ) A ## B +#define c_defs_EXPAND(...) __VA_ARGS__ +#define c_defs_VA_ARG_SIZE(...) c_defs_EXPAND(c_defs_APPLY_ARG_N((__VA_ARGS__, c_defs_RSEQ_N))) +#define c_defs_APPLY_ARG_N(ARGS) c_defs_EXPAND(c_defs_ARG_N ARGS) +#define c_defs_ARG_N(_0, _1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, N,...) N +#define c_defs_RSEQ_N 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 +#define c_defs_OVERLOAD_SELECT(NAME, NUM) c_defs_CAT( NAME ## _, NUM) + +#define c_defs_MACRO_OVERLOAD(NAME, ...) c_defs_OVERLOAD_SELECT(NAME, c_defs_VA_ARG_SIZE(__VA_ARGS__))(__VA_ARGS__) +// #define foo(...) c_defs_MACRO_OVERLOAD(foo, __VA_ARGS__) +// #define foo_1(X) foo_2(X, 100) +// #define foo_2(X, Y) X + Y + +#define c_defs_max_alloca (1000) +#define c_defs_swap(T, x, y) { T __t = x; x = y; y = __t; } + +#define c_defs_initRaw(x) (x) +#define c_defs_getRaw(x) (x) +static inline void c_defs_destroy(void* value) {} + +#define c_foreach(it, ctag, con) \ + for (ctag##_iter_t it = ctag##_begin(con); it.item != ctag##_end(con).item; it = ctag##_next(it)) + +static inline uint32_t c_defs_murmurHash(const void *data, size_t len) { // One-at-a-time 32bit + const unsigned char *key = (const unsigned char *) data; + uint32_t h = 0xC613FC15; // ‭0x749E3E6989DF617‬; 64bit + while (len--) { + h ^= *key++; + h *= 0x5bd1e995; // 0x5bd1e9955bd1e995; 64bit + h ^= h >> 15; // 47; 64bit + } + return h; +} + +#endif \ No newline at end of file diff --git a/c_hashmap.h b/c_hashmap.h new file mode 100644 index 00000000..a0f85def --- /dev/null +++ b/c_hashmap.h @@ -0,0 +1,225 @@ +// 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. + +#ifndef C_HASHMAP_H_ +#define C_HASHMAP_H_ + +#include "c_vector.h" + +#define c_hashmap_initializer {c_vector_initializer, 0, 0.8f} +#define c_hashmap_size(cm) ((size_t) (cm)._size) +#define c_hashmap_buckets(cm) c_vector_capacity((cm)._vec) + + +// c_HashmapEntry: +enum { c_HashmapEntry_VACANT = 0, + c_HashmapEntry_INUSE = 1, + c_HashmapEntry_ERASED = 2 +}; +#define c_declare_HashmapEntry(tag, Key, Value, keyDestroy, valueDestroy) \ +struct c_HashmapEntry_##tag { \ + Key key; \ + Value value; \ + uint8_t state, changed; \ +}; \ + \ +static inline void c_hashmapentry_##tag##_destroy(struct c_HashmapEntry_##tag* e) { \ + keyDestroy(&e->key); \ + valueDestroy(&e->value); \ + e->state = c_HashmapEntry_VACANT; \ +} \ +typedef struct c_HashmapEntry_##tag c_HashmapEntry_##tag + + +// c_Hashmap: +#define c_declare_Hashmap(...) c_defs_MACRO_OVERLOAD(c_declare_Hashmap, __VA_ARGS__) + +#define c_declare_Hashmap_3(tag, Key, Value) \ + c_declare_Hashmap_4(tag, Key, Value, c_defs_destroy) + +#define c_declare_Hashmap_4(tag, Key, Value, valueDestroy) \ + c_declare_Hashmap_10(tag, Key, Value, valueDestroy, Key, memcmp, c_defs_murmurHash, c_defs_initRaw, c_defs_getRaw, c_defs_destroy) + + +// c_Hashmap: +#define c_declare_Hashmap_stringkey(...) c_defs_MACRO_OVERLOAD(c_declare_Hashmap_stringkey, __VA_ARGS__) + +#define c_declare_Hashmap_stringkey_2(tag, Value) \ + c_declare_Hashmap_stringkey_3(tag, Value, c_defs_destroy) + +#define c_declare_Hashmap_stringkey_3(tag, Value, valueDestroy) \ + c_declare_Hashmap_10(tag, c_String, Value, valueDestroy, const char*, c_string_compareRaw, c_string_hashRaw, c_string_make, c_string_getRaw, c_string_destroy) + + +// c_Hashmap full: +#define c_declare_Hashmap_10(tag, Key, Value, valueDestroy, KeyRaw, keyCompareRaw, keyHashRaw, keyInitRaw, keyGetRaw, keyDestroy) \ + c_declare_HashmapEntry(tag, Key, Value, keyDestroy, valueDestroy); \ + c_declare_Vector_3(map_##tag, c_HashmapEntry_##tag, c_hashmapentry_##tag##_destroy); \ + \ +typedef struct c_Hashmap_##tag { \ + c_Vector_map_##tag _vec; \ + size_t _size; \ + float maxLoadFactor; \ +} c_Hashmap_##tag; \ + \ +typedef struct c_hashmap_##tag##_iter_t { \ + c_HashmapEntry_##tag *item, *_end; \ +} c_hashmap_##tag##_iter_t; \ + \ +static inline c_Hashmap_##tag c_hashmap_##tag##_init(void) { \ + c_Hashmap_##tag map = c_hashmap_initializer; \ + return map; \ +} \ + \ +static inline void c_hashmap_##tag##_destroy(c_Hashmap_##tag* self) { \ + if (c_hashmap_size(*self)) { \ + size_t cap = _c_vector_capacity(self->_vec); \ + c_HashmapEntry_##tag* e = self->_vec.data, *end = e + cap; \ + for (; e != end; ++e) if (e->state == c_HashmapEntry_INUSE) c_hashmapentry_##tag##_destroy(e); \ + } \ + c_vector_map_##tag##_destroy(&self->_vec); \ +} \ + \ +static inline size_t c_hashmap_##tag##_reserve(c_Hashmap_##tag* self, size_t size); /* predeclared */ \ + \ +static inline void c_hashmap_##tag##_clear(c_Hashmap_##tag* self) { \ + c_Hashmap_##tag cm = c_hashmap_initializer; \ + c_hashmap_##tag##_destroy(self); \ + *self = cm; \ +} \ + \ +static inline void c_hashmap_##tag##_swap(c_Hashmap_##tag* a, c_Hashmap_##tag* b) { \ + c_vector_map_##tag##_swap(&a->_vec, &b->_vec); \ + c_defs_swap(size_t, a->_size, b->_size); \ +} \ + \ +static inline void c_hashmap_##tag##_setMaxLoadFactor(c_Hashmap_##tag* self, float fac) { \ + self->maxLoadFactor = fac; \ + if (c_hashmap_size(*self) > c_hashmap_buckets(*self) * fac) \ + c_hashmap_##tag##_reserve(self, 1 + (size_t) (c_hashmap_size(*self) / fac)); \ +} \ + \ +static inline size_t c_hashmap_##tag##_bucket(c_Hashmap_##tag cm, KeyRaw rawKey) { \ + size_t cap = c_vector_capacity(cm._vec); \ + size_t idx = c_hashmap_reduce(keyHashRaw(&rawKey, sizeof(Key)), cap); \ + size_t first = idx, erased_idx = cap; \ + FIBONACCI_DECL; \ + do { \ + switch (cm._vec.data[idx].state) { \ + case c_HashmapEntry_VACANT: \ + return erased_idx != cap ? erased_idx : idx; \ + case c_HashmapEntry_INUSE: \ + if (keyCompareRaw(&cm._vec.data[idx].key, &rawKey, sizeof(Key)) != 0) \ + break; \ + if (erased_idx != cap) { \ + c_defs_swap(c_HashmapEntry_##tag, cm._vec.data[erased_idx], cm._vec.data[idx]); \ + return erased_idx; \ + } \ + return idx; \ + case c_HashmapEntry_ERASED: \ + if (erased_idx == cap) erased_idx = idx; \ + break; \ + } \ + idx = first + FIBONACCI_NEXT; \ + if (idx >= cap) idx %= cap; \ + } while (1); \ +} \ + \ +static inline c_HashmapEntry_##tag* c_hashmap_##tag##_get(c_Hashmap_##tag cm, KeyRaw rawKey) { \ + if (c_hashmap_size(cm) == 0) return NULL; \ + size_t idx = c_hashmap_##tag##_bucket(cm, rawKey); \ + return cm._vec.data[idx].state == c_HashmapEntry_INUSE ? &cm._vec.data[idx] : NULL; \ +} \ + \ +static inline c_HashmapEntry_##tag* c_hashmap_##tag##_put(c_Hashmap_##tag* self, KeyRaw rawKey, Value value) { \ + size_t cap = c_vector_capacity(self->_vec); \ + if (c_hashmap_size(*self) >= cap * self->maxLoadFactor) \ + cap = c_hashmap_##tag##_reserve(self, (size_t) (cap * 1.8)); \ + size_t idx = c_hashmap_##tag##_bucket(*self, rawKey); \ + c_HashmapEntry_##tag* e = &self->_vec.data[idx]; \ + e->value = value; \ + e->changed = (e->state == c_HashmapEntry_INUSE); \ + if (e->state != c_HashmapEntry_INUSE) { \ + e->key = keyInitRaw(rawKey); \ + e->state = c_HashmapEntry_INUSE; \ + ++self->_size; \ + } \ + return e; \ +} \ + \ +static inline size_t c_hashmap_##tag##_reserve(c_Hashmap_##tag* self, size_t size) { \ + size_t oldcap = c_vector_capacity(self->_vec), newcap = (oldcap ? 1 : 7) + (size / 2) * 2; \ + if (oldcap >= newcap) return oldcap; \ + c_Vector_map_##tag vec = c_vector_initializer; \ + c_vector_map_##tag##_swap(&self->_vec, &vec); \ + c_vector_map_##tag##_reserve(&self->_vec, newcap); \ + self->_size = 0; \ + memset(self->_vec.data, 0, sizeof(c_HashmapEntry_##tag) * newcap); \ + c_HashmapEntry_##tag* e = vec.data; \ + for (size_t i = 0; i < oldcap; ++i, ++e) \ + if (e->state == c_HashmapEntry_INUSE) c_hashmap_##tag##_put(self, keyGetRaw(e->key), e->value); \ + return newcap; \ +} \ + \ +static inline bool c_hashmap_##tag##_erase(c_Hashmap_##tag* self, KeyRaw rawKey) { \ + c_HashmapEntry_##tag* e = c_hashmap_##tag##_get(*self, rawKey); \ + if (e) { \ + c_hashmapentry_##tag##_destroy(e); \ + e->state = c_HashmapEntry_ERASED; \ + --self->_size; \ + return true; \ + } \ + return false; \ +} \ + \ +static inline c_hashmap_##tag##_iter_t c_hashmap_##tag##_begin(c_Hashmap_##tag map) { \ + c_hashmap_##tag##_iter_t null = {NULL, NULL}; \ + if (c_hashmap_size(map) == 0) return null; \ + c_HashmapEntry_##tag* e = map._vec.data, *end = e + _c_vector_capacity(map._vec); \ + while (e != end && e->state != c_HashmapEntry_INUSE) ++e; \ + c_hashmap_##tag##_iter_t it = {e, end}; return it; \ +} \ + \ +static inline c_hashmap_##tag##_iter_t c_hashmap_##tag##_next(c_hashmap_##tag##_iter_t it) { \ + do { ++it.item; } while (it.item != it._end && it.item->state != c_HashmapEntry_INUSE); \ + return it; \ +} \ + \ +static inline c_hashmap_##tag##_iter_t c_hashmap_##tag##_end(c_Hashmap_##tag map) { \ + c_HashmapEntry_##tag* end = (c_hashmap_size(map) == 0) ? NULL : map._vec.data + _c_vector_capacity(map._vec); \ + c_hashmap_##tag##_iter_t it = {end, end}; \ + return it; \ +} \ +typedef Key c_hashmap_##tag##_key_t; \ +typedef Value c_hashmap_##tag##_value_t + + +#define FIBONACCI_DECL size_t fib1 = 0, fib2 = 1, fibx +#define FIBONACCI_NEXT (fibx = fib1 + fib2, fib1 = fib2, fib2 = fibx) + +// https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ +static inline uint32_t c_hashmap_reduce(uint32_t x, uint32_t N) { + return ((uint64_t) x * (uint64_t) N) >> 32 ; +} + + +#endif diff --git a/c_string.h b/c_string.h new file mode 100644 index 00000000..23d9e60a --- /dev/null +++ b/c_string.h @@ -0,0 +1,244 @@ +// 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. + +#ifndef C_STRING__H__ +#define C_STRING__H__ + +#include +#include +#include +#include + +#include "c_defs.h" + +typedef struct c_String { + char* str; +} c_String; + + +static size_t _c_string_null_rep[] = {0, 0, 0}; +#define _c_string_rep(cs) (((size_t *) (cs).str) - 2) + +#define c_string_initializer {(char* ) (_c_string_null_rep + 2)} +#define c_string_size(cs) ((size_t) _c_string_rep(cs)[0]) +#define c_string_capacity(cs) ((size_t) _c_string_rep(cs)[1]) +#define c_string_npos ((size_t) -1) + + +static inline void c_string_reserve(c_String* self, size_t cap) { + size_t len = c_string_size(*self), oldcap = c_string_capacity(*self); + if (cap > oldcap) { + size_t* rep = (size_t *) realloc(oldcap ? _c_string_rep(*self) : NULL, sizeof(size_t) * 2 + cap + 1); + self->str = (char* ) (rep + 2); + self->str[ rep[0] = len ] = '\0'; + rep[1] = cap; + } +} + +static inline void c_string_destroy(c_String* self) { + if (c_string_capacity(*self)) { + free(_c_string_rep(*self)); + } +} + +static inline c_String c_string_init(void) { + c_String cs = c_string_initializer; + return cs; +} + +static inline c_String c_string_makeN(const char* str, size_t len) { + c_String cs = c_string_initializer; + if (len) { + c_string_reserve(&cs, len); + memcpy(cs.str, str, len); + cs.str[ _c_string_rep(cs)[0] = len ] = '\0'; + } + return cs; +} + +static inline c_String c_string_make(const char* str) { + return c_string_makeN(str, strlen(str)); +} + +static inline c_String c_string_makeCopy(c_String cs) { + return c_string_makeN(cs.str, c_string_size(cs)); +} + +static inline void c_string_clear(c_String* self) { + c_String cs = c_string_initializer; + c_string_destroy(self); + *self = cs; +} + +static inline c_String* c_string_assignN(c_String* self, const char* str, size_t len) { + if (len) { + c_string_reserve(self, len); + memmove(self->str, str, len); + self->str[_c_string_rep(*self)[0] = len] = '\0'; + } + return self; +} + +static inline c_String* c_string_assign(c_String* self, const char* str) { + return c_string_assignN(self, str, strlen(str)); +} + +static inline c_String* c_string_copy(c_String* self, c_String cs2) { + return c_string_assignN(self, cs2.str, c_string_size(cs2)); +} + + +static inline c_String* c_string_appendN(c_String* self, const char* str, size_t len) { + if (len) { + size_t oldlen = c_string_size(*self), newlen = oldlen + len; + if (newlen > c_string_capacity(*self)) + c_string_reserve(self, newlen * 5 / 3); + memmove(&self->str[oldlen], str, len); + self->str[_c_string_rep(*self)[0] = newlen] = '\0'; + } + return self; +} + +static inline c_String* c_string_append(c_String* self, const char* str) { + return c_string_appendN(self, str, strlen(str)); +} +static inline c_String* c_string_appendS(c_String* self, c_String cs2) { + return c_string_appendN(self, cs2.str, c_string_size(cs2)); +} + + +static inline void _c_string_internalMove(c_String* self, size_t pos1, size_t pos2) { + if (pos1 == pos2) + return; + size_t len = c_string_size(*self), newlen = len + pos2 - pos1; + if (newlen > c_string_capacity(*self)) + c_string_reserve(self, newlen * 5 / 3); + memmove(&self->str[pos2], &self->str[pos1], len - pos1); + self->str[_c_string_rep(*self)[0] = newlen] = '\0'; +} + +static inline void c_string_insertN(c_String* self, size_t pos, const char* str, size_t n) { + char* xstr = (char *) memcpy(n > c_defs_max_alloca ? malloc(n) : alloca(n), str, n); + _c_string_internalMove(self, pos, pos + n); + memcpy(&self->str[pos], xstr, n); + if (n > c_defs_max_alloca) free(xstr); +} + +static inline void c_string_insert(c_String* self, size_t pos, const char* str) { + c_string_insertN(self, pos, str, strlen(str)); +} + +static inline void c_string_erase(c_String* self, size_t pos, size_t n) { + size_t len = c_string_size(*self); + if (len) { + memmove(&self->str[pos], &self->str[pos + n], len - (pos + n)); + self->str[_c_string_rep(*self)[0] -= n] = '\0'; + } +} + +static inline size_t c_string_findN(c_String cs, size_t pos, const char* needle, size_t n); + +static inline size_t c_string_replaceN(c_String* self, size_t pos, const char* s1, size_t n1, const char* s2, size_t n2) { + size_t pos2 = c_string_findN(*self, pos, s1, n1); + if (pos2 == c_string_npos) return c_string_npos; + char* xs2 = (char *) memcpy(n2 > c_defs_max_alloca ? malloc(n2) : alloca(n2), s2, n2); + _c_string_internalMove(self, pos2 + n1, pos2 + n2); + memcpy(&self->str[pos2], xs2, n2); + if (n2 > c_defs_max_alloca) free(xs2); + return pos2; +} + +static inline size_t c_string_replace(c_String* self, size_t pos, const char* s1, const char* s2) { + return c_string_replaceN(self, pos, s1, strlen(s1), s2, strlen(s2)); +} + + +static inline char c_string_back(c_String cs) { + return cs.str[c_string_size(cs) - 1]; +} + +static inline c_String* c_string_push(c_String* self, char value) { + return c_string_appendN(self, &value, 1); +} + + +static inline void c_string_pop(c_String* self) { + --_c_string_rep(*self)[0]; +} + +/* readonly */ + +static inline bool c_string_empty(c_String cs) { + return c_string_size(cs) == 0; +} + +static inline bool c_string_equals(c_String cs1, const char* str) { + return strcmp(cs1.str, str) == 0; +} +static inline bool c_string_equalsS(c_String cs1, c_String cs2) { + return strcmp(cs1.str, cs2.str) == 0; +} + +static inline char* c_string_strnstr(c_String cs, size_t pos, const char* needle, size_t n) { + char *x = cs.str + pos, // haystack + *z = cs.str + c_string_size(cs) - n + 1; + if (x >= z) + return NULL; + ptrdiff_t sum = 0; + const char *y = x, *p = needle, *q = needle + n; + while (p != q) + sum += *y++ - *p++; + while (x != z) { + if (sum == 0 && memcmp(x, needle, n) == 0) + return x; + sum += *y++ - *x++; + } + return NULL; +} + +static inline size_t c_string_findN(c_String cs, size_t pos, const char* needle, size_t n) { + char* res = c_string_strnstr(cs, pos, needle, n); + return res ? res - cs.str : c_string_npos; +} + +static inline size_t c_string_find(c_String cs, size_t pos, const char* needle) { + char* res = strstr(cs.str + pos, needle); + return res ? res - cs.str : c_string_npos; +} + +static inline char* c_string_splitFirst(const char* delimiters, c_String cs) { + return strtok(cs.str, delimiters); +} + +static inline char* c_string_splitNext(const char* delimiters) { + return strtok(NULL, delimiters); +} + + +// c_Vector / c_Hashmap API functions: + +#define c_string_getRaw(x) ((x).str) +static inline uint32_t c_string_hashRaw(const char** str, size_t sz_ignored) { return c_defs_murmurHash(*str, strlen(*str)); } +static inline int c_string_compareRaw(c_String* self, const char** str, size_t sz_ignored) { return strcmp(self->str, *str); } + + +#endif diff --git a/c_vector.h b/c_vector.h new file mode 100644 index 00000000..58c10edc --- /dev/null +++ b/c_vector.h @@ -0,0 +1,147 @@ +// 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. + +#ifndef C_VECTOR__H__ +#define C_VECTOR__H__ + +#include +#include +#include "c_defs.h" + + +#define c_vector_initializer {NULL} +#define c_vector_size(cv) _c_vector_safe_size((cv).data) +#define c_vector_capacity(cv) _c_vector_safe_capacity((cv).data) +#define c_vector_empty(cv) (_c_vector_safe_size((cv).data) == 0) + +#define c_declare_Vector(...) c_defs_MACRO_OVERLOAD(c_declare_Vector, __VA_ARGS__) +#define c_declare_Vector_2(tag, Value) c_declare_Vector_3(tag, Value, c_defs_destroy) +#define c_declare_Vector_string(tag) c_declare_Vector_3(tag, c_String, c_string_destroy) + + +#define c_declare_Vector_3(tag, Value, valueDestroy) \ +typedef struct c_Vector_##tag { \ + Value* data; \ +} c_Vector_##tag; \ +typedef struct c_vector_##tag##_iter_t { \ + Value* item; \ +} c_vector_##tag##_iter_t; \ + \ +static inline c_Vector_##tag c_vector_##tag##_init(void) { \ + c_Vector_##tag cv = c_vector_initializer; \ + return cv; \ +} \ + \ +static inline void c_vector_##tag##_swap(c_Vector_##tag* a, c_Vector_##tag* b) { \ + Value* data = a->data; a->data = b->data; b->data = data; \ +} \ + \ +static inline void c_vector_##tag##_destroy(c_Vector_##tag* self) { \ + Value* p = self->data; \ + size_t i = 0, n = c_vector_size(*self); \ + for (; i < n; ++p, ++i) valueDestroy(p); \ + free(_c_vector_alloced(self->data)); \ +} \ + \ +static inline void c_vector_##tag##_reserve(c_Vector_##tag* self, size_t cap) { \ + if (cap > c_vector_capacity(*self)) { \ + size_t len = c_vector_size(*self); \ + size_t* rep = (size_t *) realloc(_c_vector_alloced(self->data), 2 * sizeof(size_t) + cap * sizeof(Value)); \ + self->data = (Value *) (rep + 2); \ + rep[0] = len; \ + rep[1] = cap; \ + } \ +} \ + \ +static inline void c_vector_##tag##_clear(c_Vector_##tag* self) { \ + c_Vector_##tag cv = c_vector_initializer; \ + c_vector_##tag##_destroy(self); \ + *self = cv; \ +} \ + \ + \ +static inline void c_vector_##tag##_push(c_Vector_##tag* self, Value value) { \ + size_t newsize = c_vector_size(*self) + 1; \ + if (newsize > c_vector_capacity(*self)) \ + c_vector_##tag##_reserve(self, 7 + newsize * 5 / 3); \ + self->data[c_vector_size(*self)] = value; \ + _c_vector_size(*self) = newsize; \ +} \ + \ +static inline void c_vector_##tag##_insert(c_Vector_##tag* self, size_t pos, Value value) { \ + c_vector_##tag##_push(self, value); \ + size_t len = c_vector_size(*self); \ + memmove(&self->data[pos + 1], &self->data[pos], (len - pos - 1) * sizeof(Value)); \ + self->data[pos] = value; \ +} \ + \ +static inline void c_vector_##tag##_erase(c_Vector_##tag* self, size_t pos, size_t size) { \ + size_t len = c_vector_size(*self); \ + if (len) { \ + Value* p = &self->data[pos], *start = p, *end = p + size; \ + while (p != end) valueDestroy(p++); \ + memmove(start, end, (len - pos - size) * sizeof(Value)); \ + _c_vector_size(*self) -= size; \ + } \ +} \ + \ + \ +static inline Value c_vector_##tag##_back(c_Vector_##tag cv) { \ + return cv.data[_c_vector_size(cv) - 1]; \ +} \ + \ +static inline void c_vector_##tag##_pop(c_Vector_##tag* self) { \ + valueDestroy(&self->data[_c_vector_size(*self) - 1]); \ + --_c_vector_size(*self); \ +} \ + \ +static inline c_vector_##tag##_iter_t c_vector_##tag##_begin(c_Vector_##tag vec) { \ + c_vector_##tag##_iter_t it = {vec.data}; \ + return it; \ +} \ + \ +static inline c_vector_##tag##_iter_t c_vector_##tag##_next(c_vector_##tag##_iter_t it) { \ + ++it.item; \ + return it; \ +} \ + \ +static inline c_vector_##tag##_iter_t c_vector_##tag##_end(c_Vector_##tag vec) { \ + c_vector_##tag##_iter_t it = {vec.data + c_vector_size(vec)}; \ + return it; \ +} \ +typedef Value c_vector_##tag##_value_t + + +#define _c_vector_size(cv) ((size_t *)(cv).data)[-2] +#define _c_vector_capacity(cv) ((size_t *)(cv).data)[-1] + +static inline size_t* _c_vector_alloced(void* data) { + return data ? ((size_t *) data) - 2 : NULL; +} +static inline size_t _c_vector_safe_size(const void* data) { + return data ? ((const size_t *) data)[-2] : 0; +} +static inline size_t _c_vector_safe_capacity(const void* data) { + return data ? ((const size_t *) data)[-1] : 0; +} + +#endif diff --git a/cdefs.h b/cdefs.h deleted file mode 100644 index 3769c358..00000000 --- a/cdefs.h +++ /dev/null @@ -1,64 +0,0 @@ -// 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. - -#ifndef C_DEFS__H__ -#define C_DEFS__H__ - -#include -#include - -// Macro overloading feature support: https://rextester.com/ONP80107 -#define c_defs_CAT( A, B ) A ## B -#define c_defs_EXPAND(...) __VA_ARGS__ -#define c_defs_VA_ARG_SIZE(...) c_defs_EXPAND(c_defs_APPLY_ARG_N((__VA_ARGS__, c_defs_RSEQ_N))) -#define c_defs_APPLY_ARG_N(ARGS) c_defs_EXPAND(c_defs_ARG_N ARGS) -#define c_defs_ARG_N(_0, _1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, N,...) N -#define c_defs_RSEQ_N 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 -#define c_defs_OVERLOAD_SELECT(NAME, NUM) c_defs_CAT( NAME ## _, NUM) - -#define c_defs_MACRO_OVERLOAD(NAME, ...) c_defs_OVERLOAD_SELECT(NAME, c_defs_VA_ARG_SIZE(__VA_ARGS__))(__VA_ARGS__) -// #define foo(...) c_defs_MACRO_OVERLOAD(foo, __VA_ARGS__) -// #define foo_1(X) foo_2(X, 100) -// #define foo_2(X, Y) X + Y - -#define c_defs_max_alloca (1000) -#define c_defs_swap(T, x, y) { T __t = x; x = y; y = __t; } - -#define c_defs_initRaw(x) (x) -#define c_defs_getRaw(x) (x) -static inline void c_defs_destroy(void* value) {} - -#define c_foreach(it, ctag, con) \ - for (ctag##_iter_t it = ctag##_begin(con); it.item != ctag##_end(con).item; it = ctag##_next(it)) - -static inline uint32_t c_defs_murmurHash(const void *data, size_t len) { // One-at-a-time 32bit - const unsigned char *key = (const unsigned char *) data; - uint32_t h = 0xC613FC15; // ‭0x749E3E6989DF617‬; 64bit - while (len--) { - h ^= *key++; - h *= 0x5bd1e995; // 0x5bd1e9955bd1e995; 64bit - h ^= h >> 15; // 47; 64bit - } - return h; -} - -#endif \ No newline at end of file diff --git a/cmap.h b/cmap.h deleted file mode 100644 index 20804882..00000000 --- a/cmap.h +++ /dev/null @@ -1,225 +0,0 @@ -// 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. - -#ifndef C_HASHMAP_H_ -#define C_HASHMAP_H_ - -#include "c_vector.h" - -#define c_hashmap_initializer {c_vector_initializer, 0, 0.8f} -#define c_hashmap_size(cm) ((size_t) (cm)._size) -#define c_hashmap_buckets(cm) c_vector_capacity((cm)._vec) - - -// c_HashmapEntry: -enum { c_HashmapEntry_VACANT = 0, - c_HashmapEntry_INUSE = 1, - c_HashmapEntry_ERASED = 2 -}; -#define c_declare_HashmapEntry(tag, Key, Value, keyDestroy, valueDestroy) \ -struct c_HashmapEntry_##tag { \ - Key key; \ - Value value; \ - uint8_t state, changed; \ -}; \ - \ -static inline void cmapentry_##tag##_destroy(struct c_HashmapEntry_##tag* e) { \ - keyDestroy(&e->key); \ - valueDestroy(&e->value); \ - e->state = c_HashmapEntry_VACANT; \ -} \ -typedef struct c_HashmapEntry_##tag c_HashmapEntry_##tag - - -// c_Hashmap: -#define c_declare_Hashmap(...) c_defs_MACRO_OVERLOAD(c_declare_Hashmap, __VA_ARGS__) - -#define c_declare_Hashmap_3(tag, Key, Value) \ - c_declare_Hashmap_4(tag, Key, Value, c_defs_destroy) - -#define c_declare_Hashmap_4(tag, Key, Value, valueDestroy) \ - c_declare_Hashmap_10(tag, Key, Value, valueDestroy, Key, memcmp, c_defs_murmurHash, c_defs_initRaw, c_defs_getRaw, c_defs_destroy) - - -// c_Hashmap: -#define c_declare_Hashmap_stringkey(...) c_defs_MACRO_OVERLOAD(c_declare_Hashmap_stringkey, __VA_ARGS__) - -#define c_declare_Hashmap_stringkey_2(tag, Value) \ - c_declare_Hashmap_stringkey_3(tag, Value, c_defs_destroy) - -#define c_declare_Hashmap_stringkey_3(tag, Value, valueDestroy) \ - c_declare_Hashmap_10(tag, CString, Value, valueDestroy, const char*, cstring_compareRaw, cstring_hashRaw, cstring_make, cstring_getRaw, cstring_destroy) - - -// c_Hashmap full: -#define c_declare_Hashmap_10(tag, Key, Value, valueDestroy, KeyRaw, keyCompareRaw, keyHashRaw, keyInitRaw, keyGetRaw, keyDestroy) \ - c_declare_HashmapEntry(tag, Key, Value, keyDestroy, valueDestroy); \ - c_declare_Vector_3(map_##tag, c_HashmapEntry_##tag, cmapentry_##tag##_destroy); \ - \ -typedef struct c_Hashmap_##tag { \ - c_Vector_map_##tag _vec; \ - size_t _size; \ - float maxLoadFactor; \ -} c_Hashmap_##tag; \ - \ -typedef struct c_hashmap_##tag##_iter_t { \ - c_HashmapEntry_##tag *item, *_end; \ -} c_hashmap_##tag##_iter_t; \ - \ -static inline c_Hashmap_##tag c_hashmap_##tag##_init(void) { \ - c_Hashmap_##tag map = c_hashmap_initializer; \ - return map; \ -} \ - \ -static inline void c_hashmap_##tag##_destroy(c_Hashmap_##tag* self) { \ - if (c_hashmap_size(*self)) { \ - size_t cap = _c_vector_capacity(self->_vec); \ - c_HashmapEntry_##tag* e = self->_vec.data, *end = e + cap; \ - for (; e != end; ++e) if (e->state == c_HashmapEntry_INUSE) cmapentry_##tag##_destroy(e); \ - } \ - c_vector_map_##tag##_destroy(&self->_vec); \ -} \ - \ -static inline size_t c_hashmap_##tag##_reserve(c_Hashmap_##tag* self, size_t size); /* predeclared */ \ - \ -static inline void c_hashmap_##tag##_clear(c_Hashmap_##tag* self) { \ - c_Hashmap_##tag cm = c_hashmap_initializer; \ - c_hashmap_##tag##_destroy(self); \ - *self = cm; \ -} \ - \ -static inline void c_hashmap_##tag##_swap(c_Hashmap_##tag* a, c_Hashmap_##tag* b) { \ - c_vector_map_##tag##_swap(&a->_vec, &b->_vec); \ - c_defs_swap(size_t, a->_size, b->_size); \ -} \ - \ -static inline void c_hashmap_##tag##_setMaxLoadFactor(c_Hashmap_##tag* self, float fac) { \ - self->maxLoadFactor = fac; \ - if (c_hashmap_size(*self) > c_hashmap_buckets(*self) * fac) \ - c_hashmap_##tag##_reserve(self, 1 + (size_t) (c_hashmap_size(*self) / fac)); \ -} \ - \ -static inline size_t c_hashmap_##tag##_bucket(c_Hashmap_##tag cm, KeyRaw rawKey) { \ - size_t cap = c_vector_capacity(cm._vec); \ - size_t idx = c_hashmap_reduce(keyHashRaw(&rawKey, sizeof(Key)), cap); \ - size_t first = idx, erased_idx = cap; \ - FIBONACCI_DECL; \ - do { \ - switch (cm._vec.data[idx].state) { \ - case c_HashmapEntry_VACANT: \ - return erased_idx != cap ? erased_idx : idx; \ - case c_HashmapEntry_INUSE: \ - if (keyCompareRaw(&cm._vec.data[idx].key, &rawKey, sizeof(Key)) != 0) \ - break; \ - if (erased_idx != cap) { \ - c_defs_swap(c_HashmapEntry_##tag, cm._vec.data[erased_idx], cm._vec.data[idx]); \ - return erased_idx; \ - } \ - return idx; \ - case c_HashmapEntry_ERASED: \ - if (erased_idx == cap) erased_idx = idx; \ - break; \ - } \ - idx = first + FIBONACCI_NEXT; \ - if (idx >= cap) idx %= cap; \ - } while (1); \ -} \ - \ -static inline c_HashmapEntry_##tag* c_hashmap_##tag##_get(c_Hashmap_##tag cm, KeyRaw rawKey) { \ - if (c_hashmap_size(cm) == 0) return NULL; \ - size_t idx = c_hashmap_##tag##_bucket(cm, rawKey); \ - return cm._vec.data[idx].state == c_HashmapEntry_INUSE ? &cm._vec.data[idx] : NULL; \ -} \ - \ -static inline c_HashmapEntry_##tag* c_hashmap_##tag##_put(c_Hashmap_##tag* self, KeyRaw rawKey, Value value) { \ - size_t cap = c_vector_capacity(self->_vec); \ - if (c_hashmap_size(*self) >= cap * self->maxLoadFactor) \ - cap = c_hashmap_##tag##_reserve(self, (size_t) (cap * 1.8)); \ - size_t idx = c_hashmap_##tag##_bucket(*self, rawKey); \ - c_HashmapEntry_##tag* e = &self->_vec.data[idx]; \ - e->value = value; \ - e->changed = (e->state == c_HashmapEntry_INUSE); \ - if (e->state != c_HashmapEntry_INUSE) { \ - e->key = keyInitRaw(rawKey); \ - e->state = c_HashmapEntry_INUSE; \ - ++self->_size; \ - } \ - return e; \ -} \ - \ -static inline size_t c_hashmap_##tag##_reserve(c_Hashmap_##tag* self, size_t size) { \ - size_t oldcap = c_vector_capacity(self->_vec), newcap = (oldcap ? 1 : 7) + (size / 2) * 2; \ - if (oldcap >= newcap) return oldcap; \ - c_Vector_map_##tag vec = c_vector_initializer; \ - c_vector_map_##tag##_swap(&self->_vec, &vec); \ - c_vector_map_##tag##_reserve(&self->_vec, newcap); \ - self->_size = 0; \ - memset(self->_vec.data, 0, sizeof(c_HashmapEntry_##tag) * newcap); \ - c_HashmapEntry_##tag* e = vec.data; \ - for (size_t i = 0; i < oldcap; ++i, ++e) \ - if (e->state == c_HashmapEntry_INUSE) c_hashmap_##tag##_put(self, keyGetRaw(e->key), e->value); \ - return newcap; \ -} \ - \ -static inline bool c_hashmap_##tag##_erase(c_Hashmap_##tag* self, KeyRaw rawKey) { \ - c_HashmapEntry_##tag* e = c_hashmap_##tag##_get(*self, rawKey); \ - if (e) { \ - cmapentry_##tag##_destroy(e); \ - e->state = c_HashmapEntry_ERASED; \ - --self->_size; \ - return true; \ - } \ - return false; \ -} \ - \ -static inline c_hashmap_##tag##_iter_t c_hashmap_##tag##_begin(c_Hashmap_##tag map) { \ - c_hashmap_##tag##_iter_t null = {NULL, NULL}; \ - if (c_hashmap_size(map) == 0) return null; \ - c_HashmapEntry_##tag* e = map._vec.data, *end = e + _c_vector_capacity(map._vec); \ - while (e != end && e->state != c_HashmapEntry_INUSE) ++e; \ - c_hashmap_##tag##_iter_t it = {e, end}; return it; \ -} \ - \ -static inline c_hashmap_##tag##_iter_t c_hashmap_##tag##_next(c_hashmap_##tag##_iter_t it) { \ - do { ++it.item; } while (it.item != it._end && it.item->state != c_HashmapEntry_INUSE); \ - return it; \ -} \ - \ -static inline c_hashmap_##tag##_iter_t c_hashmap_##tag##_end(c_Hashmap_##tag map) { \ - c_HashmapEntry_##tag* end = (c_hashmap_size(map) == 0) ? NULL : map._vec.data + _c_vector_capacity(map._vec); \ - c_hashmap_##tag##_iter_t it = {end, end}; \ - return it; \ -} \ -typedef Key c_hashmap_##tag##_key_t; \ -typedef Value c_hashmap_##tag##_value_t - - -#define FIBONACCI_DECL size_t fib1 = 0, fib2 = 1, fibx -#define FIBONACCI_NEXT (fibx = fib1 + fib2, fib1 = fib2, fib2 = fibx) - -// https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ -static inline uint32_t c_hashmap_reduce(uint32_t x, uint32_t N) { - return ((uint64_t) x * (uint64_t) N) >> 32 ; -} - - -#endif diff --git a/cmap_test.c b/cmap_test.c index 39715b3d..563c27c7 100644 --- a/cmap_test.c +++ b/cmap_test.c @@ -28,7 +28,7 @@ #include "c_string.h" -declare_c_StringVector(s); +c_declare_Vector_string(s); c_declare_Hashmap_stringkey(ss, c_String, c_string_destroy); c_declare_Hashmap_stringkey(si, int); c_declare_Hashmap(id, uint64_t, double); @@ -82,7 +82,7 @@ void stringSpeed(int limit) { if (p != c_string_npos) x += p; } clock_t diff = clock() - before; - printf("cstring length = %llu / %llu, sum %llu speed: %f\n", c_string_size(s), c_string_capacity(s), x, 1.0 * diff / CLOCKS_PER_SEC); + printf("string length = %llu / %llu, sum %llu speed: %f\n", c_string_size(s), c_string_capacity(s), x, 1.0 * diff / CLOCKS_PER_SEC); } int main() diff --git a/cstring.h b/cstring.h deleted file mode 100644 index e0fcd7e5..00000000 --- a/cstring.h +++ /dev/null @@ -1,244 +0,0 @@ -// 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. - -#ifndef C_STRING__H__ -#define C_STRING__H__ - -#include -#include -#include -#include - -#include "c_defs.h" - -typedef struct c_String { - char* str; -} c_String; - - -static size_t _c_string_null_rep[] = {0, 0, 0}; -#define _c_string_rep(cs) (((size_t *) (cs).str) - 2) - -#define c_string_initializer {(char* ) (_c_string_null_rep + 2)} -#define c_string_size(cs) ((size_t) _c_string_rep(cs)[0]) -#define c_string_capacity(cs) ((size_t) _c_string_rep(cs)[1]) -#define c_string_npos ((size_t) -1) - - -static inline void c_string_reserve(c_String* self, size_t cap) { - size_t len = c_string_size(*self), oldcap = c_string_capacity(*self); - if (cap > oldcap) { - size_t* rep = (size_t *) realloc(oldcap ? _c_string_rep(*self) : NULL, sizeof(size_t) * 2 + cap + 1); - self->str = (char* ) (rep + 2); - self->str[ rep[0] = len ] = '\0'; - rep[1] = cap; - } -} - -static inline void c_string_destroy(c_String* self) { - if (c_string_capacity(*self)) { - free(_c_string_rep(*self)); - } -} - -static inline c_String c_string_init(void) { - c_String cs = c_string_initializer; - return cs; -} - -static inline c_String c_string_makeN(const char* str, size_t len) { - c_String cs = c_string_initializer; - if (len) { - c_string_reserve(&cs, len); - memcpy(cs.str, str, len); - cs.str[ _c_string_rep(cs)[0] = len ] = '\0'; - } - return cs; -} - -static inline c_String c_string_make(const char* str) { - return c_string_makeN(str, strlen(str)); -} - -static inline c_String c_string_makeCopy(c_String cs) { - return c_string_makeN(cs.str, c_string_size(cs)); -} - -static inline void c_string_clear(c_String* self) { - c_String cs = c_string_initializer; - c_string_destroy(self); - *self = cs; -} - -static inline c_String* c_string_assignN(c_String* self, const char* str, size_t len) { - if (len) { - c_string_reserve(self, len); - memmove(self->str, str, len); - self->str[_c_string_rep(*self)[0] = len] = '\0'; - } - return self; -} - -static inline c_String* c_string_assign(c_String* self, const char* str) { - return c_string_assignN(self, str, strlen(str)); -} - -static inline c_String* c_string_copy(c_String* self, c_String cs2) { - return c_string_assignN(self, cs2.str, c_string_size(cs2)); -} - - -static inline c_String* c_string_appendN(c_String* self, const char* str, size_t len) { - if (len) { - size_t oldlen = c_string_size(*self), newlen = oldlen + len; - if (newlen > c_string_capacity(*self)) - c_string_reserve(self, newlen * 5 / 3); - memmove(&self->str[oldlen], str, len); - self->str[_c_string_rep(*self)[0] = newlen] = '\0'; - } - return self; -} - -static inline c_String* c_string_append(c_String* self, const char* str) { - return c_string_appendN(self, str, strlen(str)); -} -static inline c_String* c_string_appendS(c_String* self, c_String cs2) { - return c_string_appendN(self, cs2.str, c_string_size(cs2)); -} - - -static inline void _c_string_internalMove(c_String* self, size_t pos1, size_t pos2) { - if (pos1 == pos2) - return; - size_t len = c_string_size(*self), newlen = len + pos2 - pos1; - if (newlen > c_string_capacity(*self)) - c_string_reserve(self, newlen * 5 / 3); - memmove(&self->str[pos2], &self->str[pos1], len - pos1); - self->str[_c_string_rep(*self)[0] = newlen] = '\0'; -} - -static inline void c_string_insertN(c_String* self, size_t pos, const char* str, size_t n) { - char* xstr = (char *) memcpy(n > c_defs_max_alloca ? malloc(n) : alloca(n), str, n); - _c_string_internalMove(self, pos, pos + n); - memcpy(&self->str[pos], xstr, n); - if (n > c_defs_max_alloca) free(xstr); -} - -static inline void c_string_insert(c_String* self, size_t pos, const char* str) { - c_string_insertN(self, pos, str, strlen(str)); -} - -static inline void c_string_erase(c_String* self, size_t pos, size_t n) { - size_t len = c_string_size(*self); - if (len) { - memmove(&self->str[pos], &self->str[pos + n], len - (pos + n)); - self->str[_c_string_rep(*self)[0] -= n] = '\0'; - } -} - -static inline size_t c_string_findN(c_String cs, size_t pos, const char* needle, size_t n); - -static inline size_t c_string_replaceN(c_String* self, size_t pos, const char* s1, size_t n1, const char* s2, size_t n2) { - size_t pos2 = c_string_findN(*self, pos, s1, n1); - if (pos2 == c_string_npos) return c_string_npos; - char* xs2 = (char *) memcpy(n2 > c_defs_max_alloca ? malloc(n2) : alloca(n2), s2, n2); - _c_string_internalMove(self, pos2 + n1, pos2 + n2); - memcpy(&self->str[pos2], xs2, n2); - if (n2 > c_defs_max_alloca) free(xs2); - return pos2; -} - -static inline size_t c_string_replace(c_String* self, size_t pos, const char* s1, const char* s2) { - return c_string_replaceN(self, pos, s1, strlen(s1), s2, strlen(s2)); -} - - -static inline char c_string_back(c_String cs) { - return cs.str[c_string_size(cs) - 1]; -} - -static inline c_String* c_string_push(c_String* self, char value) { - return c_string_appendN(self, &value, 1); -} - - -static inline void c_string_pop(c_String* self) { - --_c_string_rep(*self)[0]; -} - -/* readonly */ - -static inline bool c_string_empty(c_String cs) { - return c_string_size(cs) == 0; -} - -static inline bool c_string_equals(c_String cs1, const char* str) { - return strcmp(cs1.str, str) == 0; -} -static inline bool c_string_equalsS(c_String cs1, c_String cs2) { - return strcmp(cs1.str, cs2.str) == 0; -} - -static inline char* c_string_strnstr(c_String cs, size_t pos, const char* needle, size_t n) { - char *x = cs.str + pos, // haystack - *z = cs.str + c_string_size(cs) - n + 1; - if (x >= z) - return NULL; - ptrdiff_t sum = 0; - const char *y = x, *p = needle, *q = needle + n; - while (p != q) - sum += *y++ - *p++; - while (x != z) { - if (sum == 0 && memcmp(x, needle, n) == 0) - return x; - sum += *y++ - *x++; - } - return NULL; -} - -static inline size_t c_string_findN(c_String cs, size_t pos, const char* needle, size_t n) { - char* res = c_string_strnstr(cs, pos, needle, n); - return res ? res - cs.str : c_string_npos; -} - -static inline size_t c_string_find(c_String cs, size_t pos, const char* needle) { - char* res = strstr(cs.str + pos, needle); - return res ? res - cs.str : c_string_npos; -} - -static inline char* c_string_splitFirst(const char* delimiters, c_String cs) { - return strtok(cs.str, delimiters); -} - -static inline char* c_string_splitNext(const char* delimiters) { - return strtok(NULL, delimiters); -} - - -// c_Vector / c_Hashmap API functions: - -#define c_string_getRaw(x) ((x).str) -static inline uint32_t c_string_hashRaw(const char** str, size_t sz_ignored) { return c_defs_murmurHash(*str, strlen(*str)); } -static inline int c_string_compareRaw(c_String* self, const char** str, size_t sz_ignored) { return strcmp(self->str, *str); } - - -#endif diff --git a/cvector.h b/cvector.h deleted file mode 100644 index 67ce9918..00000000 --- a/cvector.h +++ /dev/null @@ -1,147 +0,0 @@ -// 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. - -#ifndef C_VECTOR__H__ -#define C_VECTOR__H__ - -#include -#include -#include "c_defs.h" - - -#define c_vector_initializer {NULL} -#define c_vector_size(cv) _c_vector_safe_size((cv).data) -#define c_vector_capacity(cv) _c_vector_safe_capacity((cv).data) -#define c_vector_empty(cv) (_c_vector_safe_size((cv).data) == 0) - -#define c_declare_Vector(...) c_defs_MACRO_OVERLOAD(c_declare_Vector, __VA_ARGS__) -#define c_declare_Vector_2(tag, Value) c_declare_Vector_3(tag, Value, c_defs_destroy) -#define declare_CStringVector(tag) c_declare_Vector_3(tag, CString, cstring_destroy) - - -#define c_declare_Vector_3(tag, Value, valueDestroy) \ -typedef struct c_Vector_##tag { \ - Value* data; \ -} c_Vector_##tag; \ -typedef struct c_vector_##tag##_iter_t { \ - Value* item; \ -} c_vector_##tag##_iter_t; \ - \ -static inline c_Vector_##tag c_vector_##tag##_init(void) { \ - c_Vector_##tag cv = c_vector_initializer; \ - return cv; \ -} \ - \ -static inline void c_vector_##tag##_swap(c_Vector_##tag* a, c_Vector_##tag* b) { \ - Value* data = a->data; a->data = b->data; b->data = data; \ -} \ - \ -static inline void c_vector_##tag##_destroy(c_Vector_##tag* self) { \ - Value* p = self->data; \ - size_t i = 0, n = c_vector_size(*self); \ - for (; i < n; ++p, ++i) valueDestroy(p); \ - free(_c_vector_alloced(self->data)); \ -} \ - \ -static inline void c_vector_##tag##_reserve(c_Vector_##tag* self, size_t cap) { \ - if (cap > c_vector_capacity(*self)) { \ - size_t len = c_vector_size(*self); \ - size_t* rep = (size_t *) realloc(_c_vector_alloced(self->data), 2 * sizeof(size_t) + cap * sizeof(Value)); \ - self->data = (Value *) (rep + 2); \ - rep[0] = len; \ - rep[1] = cap; \ - } \ -} \ - \ -static inline void c_vector_##tag##_clear(c_Vector_##tag* self) { \ - c_Vector_##tag cv = c_vector_initializer; \ - c_vector_##tag##_destroy(self); \ - *self = cv; \ -} \ - \ - \ -static inline void c_vector_##tag##_push(c_Vector_##tag* self, Value value) { \ - size_t newsize = c_vector_size(*self) + 1; \ - if (newsize > c_vector_capacity(*self)) \ - c_vector_##tag##_reserve(self, 7 + newsize * 5 / 3); \ - self->data[c_vector_size(*self)] = value; \ - _c_vector_size(*self) = newsize; \ -} \ - \ -static inline void c_vector_##tag##_insert(c_Vector_##tag* self, size_t pos, Value value) { \ - c_vector_##tag##_push(self, value); \ - size_t len = c_vector_size(*self); \ - memmove(&self->data[pos + 1], &self->data[pos], (len - pos - 1) * sizeof(Value)); \ - self->data[pos] = value; \ -} \ - \ -static inline void c_vector_##tag##_erase(c_Vector_##tag* self, size_t pos, size_t size) { \ - size_t len = c_vector_size(*self); \ - if (len) { \ - Value* p = &self->data[pos], *start = p, *end = p + size; \ - while (p != end) valueDestroy(p++); \ - memmove(start, end, (len - pos - size) * sizeof(Value)); \ - _c_vector_size(*self) -= size; \ - } \ -} \ - \ - \ -static inline Value c_vector_##tag##_back(c_Vector_##tag cv) { \ - return cv.data[_c_vector_size(cv) - 1]; \ -} \ - \ -static inline void c_vector_##tag##_pop(c_Vector_##tag* self) { \ - valueDestroy(&self->data[_c_vector_size(*self) - 1]); \ - --_c_vector_size(*self); \ -} \ - \ -static inline c_vector_##tag##_iter_t c_vector_##tag##_begin(c_Vector_##tag vec) { \ - c_vector_##tag##_iter_t it = {vec.data}; \ - return it; \ -} \ - \ -static inline c_vector_##tag##_iter_t c_vector_##tag##_next(c_vector_##tag##_iter_t it) { \ - ++it.item; \ - return it; \ -} \ - \ -static inline c_vector_##tag##_iter_t c_vector_##tag##_end(c_Vector_##tag vec) { \ - c_vector_##tag##_iter_t it = {vec.data + c_vector_size(vec)}; \ - return it; \ -} \ -typedef Value c_vector_##tag##_value_t - - -#define _c_vector_size(cv) ((size_t *)(cv).data)[-2] -#define _c_vector_capacity(cv) ((size_t *)(cv).data)[-1] - -static inline size_t* _c_vector_alloced(void* data) { - return data ? ((size_t *) data) - 2 : NULL; -} -static inline size_t _c_vector_safe_size(const void* data) { - return data ? ((const size_t *) data)[-2] : 0; -} -static inline size_t _c_vector_safe_capacity(const void* data) { - return data ? ((const size_t *) data)[-1] : 0; -} - -#endif -- cgit v1.2.3