From c749f6287457662b1474ad7faeee31a193994af3 Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylo-work@users.noreply.github.com> Date: Tue, 3 Mar 2020 22:35:30 +0100 Subject: Initial upload --- cdef.h | 42 ++++++++++++++++ cmap.h | 149 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ cmap_test.c | 119 +++++++++++++++++++++++++++++++++++++++++++++ cstring.h | 158 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ cvector.h | 137 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 605 insertions(+) create mode 100644 cdef.h create mode 100644 cmap.h create mode 100644 cmap_test.c create mode 100644 cstring.h create mode 100644 cvector.h diff --git a/cdef.h b/cdef.h new file mode 100644 index 00000000..8384778e --- /dev/null +++ b/cdef.h @@ -0,0 +1,42 @@ +#ifndef CDEF__H__ +#define CDEF__H__ + + +// Macro overloading feature support: https://rextester.com/ONP80107 +#define cdef_CAT( A, B ) A ## B +#define cdef_EXPAND(...) __VA_ARGS__ +#define cdef_VA_ARG_SIZE(...) cdef_EXPAND(cdef_APPLY_ARG_N((__VA_ARGS__, cdef_RSEQ_N))) +#define cdef_APPLY_ARG_N(ARGS) cdef_EXPAND(cdef_ARG_N ARGS) +#define cdef_ARG_N(_0, _1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, N,...) N +#define cdef_RSEQ_N 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 +#define cdef_OVERLOAD_SELECT(NAME, NUM) cdef_CAT( NAME ## _, NUM) + +#define cdef_MACRO_OVERLOAD(NAME, ...) cdef_OVERLOAD_SELECT(NAME, cdef_VA_ARG_SIZE(__VA_ARGS__))(__VA_ARGS__) +// #define foo(...) cdef_MACRO_OVERLOAD(foo, __VA_ARGS__) +// #define foo_1(X) foo_2(X, 100) +// #define foo_2(X, Y) X + Y + + +#define cdef_initRaw(x) (x) +#define cdef_getRaw(x) (x) +static inline void cdef_destroy(void* value) {} + +#define cforeach(...) cdef_MACRO_OVERLOAD(cforeach, __VA_ARGS__) +#define cforeach_3(it, tagc, con) for (it = tagc##_begin(con); it.item != tagc##_end(con).item; it = tagc##_next(it)) +#define cforeach_5(it, tagc, con, cond, next) for (it = tagc##_begin(con); it.item != tagc##_end(con).item && (cond); it = tagc##_next(it), next) + +static inline uint32_t +cdef_murmurHash(const void *data, size_t len) // One-at-a-time 32bit +{ + const unsigned char *key = (const unsigned char *) data; + uint32_t h = 3323198485ul; + while (len--) { + h ^= *key++; + h *= 0x5bd1e995; + h ^= h >> 15; + } + return h; +} + + +#endif \ No newline at end of file diff --git a/cmap.h b/cmap.h new file mode 100644 index 00000000..78ab6ff9 --- /dev/null +++ b/cmap.h @@ -0,0 +1,149 @@ +#ifndef CMAP_H_ +#define CMAP_H_ + +#include "cvector.h" + +#define CMap(tag) CMap_##tag##_t +#define CMapEntry(tag) CMapEntry_##tag##_t +#define CMapIter(tag) CMapIter_##tag##_t + +#define cmap_INIT {cvector_INIT, 0} +#define cmap_size(cm) ((cvector_size_t) (cm)._size) +#define cmap_capacity(cm) cvector_capacity((cm)._vec) + + +// CMapEntry: +#define declare_CMapEntry_5(tag, Key, Value, keyDestr, valueDestr) \ +typedef struct CMapEntry(tag) { Key key; Value value; short _used; } CMapEntry(tag); \ +typedef struct CMapIter(tag) { CMapEntry(tag) *item, *_end; } CMapIter(tag); \ + \ +static inline void cmapentry_##tag##_destroy(CMapEntry(tag)* p) { \ + keyDestr(&p->key); \ + valueDestr(&p->value); \ + p->_used = 0; \ +} + +// CMap: +#define declare_CMap(...) cdef_MACRO_OVERLOAD(declare_CMap, __VA_ARGS__) + +#define declare_CMap_3(tag, Key, Value) \ + declare_CMap_4(tag, Key, Value, cdef_destroy) + +#define declare_CMap_4(tag, Key, Value, valueDestr) \ + declare_CMap_10(tag, Key, Value, valueDestr, Key, cdef_getRaw, memcmp, cdef_murmurHash, cdef_initRaw, cdef_destroy) + + +// CMap: +#define declare_CMap_STR(...) cdef_MACRO_OVERLOAD(declare_CMap_STR, __VA_ARGS__) + +#define declare_CMap_STR_2(tag, Value) \ + declare_CMap_STR_3(tag, Value, cdef_destroy) + +#define declare_CMap_STR_3(tag, Value, valueDestr) \ + declare_CMap_10(tag, CString, Value, valueDestr, const char*, cstring_getRaw, cstring_compare, cstring_hash, cstring_make, cstring_destroy) + + +// CMap full: +#define declare_CMap_10(tag, Key, Value, valueDestr, KeyRaw, keyGetRaw, keyCompare, keyHasher, keyInit, keyDestr) \ + declare_CMapEntry_5(tag, Key, Value, keyDestr, valueDestr); \ + declare_CVector_3(_map##tag, CMapEntry(tag), cmapentry_##tag##_destroy); \ + \ +typedef struct CMap(tag) { \ + CVector(_map##tag) _vec; \ + cvector_size_t _size; \ +} CMap(tag); \ + \ +static inline CMap(tag) cmap_##tag##_init(void) { \ + CMap(tag) map = cmap_INIT; \ + return map; \ +} \ + \ +static inline void cmap_##tag##_destroy(CMap(tag)* self) { \ + if (self->_size == 0) return; \ + cvector_size_t cap = cvector_capacity(self->_vec); \ + CMapEntry(tag)* p = self->_vec.data, *end = p + cap; \ + for (; p != end; ++p) if (p->_used) cmapentry_##tag##_destroy(p); \ + cvector__map##tag##_destroy(&self->_vec); \ +} \ + \ +static inline void cmap_##tag##_clear(CMap(tag)* self) { \ + CMap(tag) cm = cmap_INIT; \ + cmap_##tag##_destroy(self); \ + *self = cm; \ +} \ + \ + \ +static inline CMapEntry(tag)* cmap_##tag##_get(CMap(tag) cm, KeyRaw rawKey) { \ + if (cm._size == 0) return NULL; \ + cvector_size_t cap = cvector_capacity(cm._vec); \ + cvector_size_t idx = keyHasher(&rawKey, sizeof(Key)) % cap, first = idx; \ + FIBONACCI_DECL; \ + while (cm._vec.data[idx]._used && keyCompare(&cm._vec.data[idx].key, &rawKey, sizeof(Key)) != 0) \ + idx = (first + FIBONACCI_NEXT) % cap; \ + return cm._vec.data[idx]._used ? &cm._vec.data[idx] : NULL; \ +} \ + \ +static inline int cmap_##tag##_erase(CMap(tag)* self, KeyRaw rawKey) { \ + CMapEntry(tag)* entryPtr = cmap_##tag##_get(*self, rawKey); \ + if (entryPtr) { \ + cmapentry_##tag##_destroy(entryPtr); \ + --self->_size; \ + } \ + return entryPtr != NULL; \ +} \ + \ + static inline cvector_size_t cmap_##tag##_rehash(CMap(tag)* self); /* predeclared */ \ + \ +static inline void cmap_##tag##_put(CMap(tag)* self, KeyRaw rawKey, Value val) { \ + CMapEntry(tag) entry = {keyInit(rawKey), val, 1}; \ + cvector_size_t cap = cvector_capacity(self->_vec); \ + if (self->_size >= cap * 8 / 10) \ + cap = cmap_##tag##_rehash(self); \ + cvector_size_t idx = keyHasher(&rawKey, sizeof(Key)) % cap, first = idx; \ + FIBONACCI_DECL; \ + while (self->_vec.data[idx]._used) \ + idx = (first + FIBONACCI_NEXT) % cap; \ + self->_vec.data[idx] = entry; \ + ++self->_size; \ +} \ + \ +static inline cvector_size_t cmap_##tag##_rehash(CMap(tag)* self) { \ + CVector(_map##tag) vec = cvector_INIT; \ + cvector_size_t newcap = 7 + cmap_capacity(*self) * 2; \ + cvector__map##tag##_swap(&self->_vec, &vec); \ + cvector__map##tag##_reserve(&self->_vec, newcap); \ + self->_size = 0; \ + memset(self->_vec.data, 0, sizeof(CMapEntry(tag)) * newcap); \ + CMapEntry(tag)* p = vec.data; \ + cvector_size_t i, oldcap = cvector_capacity(vec); \ + for (i = 0; i < oldcap; ++i, ++p) \ + if (p->_used) cmap_##tag##_put(self, keyGetRaw(p->key), p->value); \ + return newcap; \ +} \ + \ + \ +static inline CMapIter(tag) cmap_##tag##_begin(CMap(tag) map) { \ + CMapIter(tag) null = {NULL, NULL}; \ + if (map._size == 0) return null; \ + CMapEntry(tag)* p = map._vec.data, *end = p + _cvector_capacity(map._vec); \ + while (p != end && !p->_used) ++p; \ + CMapIter(tag) it = {p, end}; return it; \ +} \ + \ +static inline CMapIter(tag) cmap_##tag##_next(CMapIter(tag) iter) { \ + ++iter.item; \ + while (iter.item != iter._end && !iter.item->_used) ++iter.item; \ + return iter; \ +} \ + \ +static inline CMapIter(tag) cmap_##tag##_end(CMap(tag) map) { \ + CMapEntry(tag)* end = (map._size == 0) ? NULL : map._vec.data + _cvector_capacity(map._vec); \ + CMapIter(tag) iter = {end, end}; \ + return iter; \ +} + + +#define FIBONACCI_DECL cvector_size_t fib1 = 1, fib2 = 2, fibx +#define FIBONACCI_NEXT (fibx = fib1 + fib2, fib1 = fib2, fib2 = fibx) + +#endif diff --git a/cmap_test.c b/cmap_test.c new file mode 100644 index 00000000..bd567cfe --- /dev/null +++ b/cmap_test.c @@ -0,0 +1,119 @@ +#include +#include + +#include "cmap.h" +#include "cstring.h" + + +declare_CVector(cs, CString, cstring_destroy); +declare_CMap_STR(ss, CString, cstring_destroy); +declare_CMap_STR(si, int); +declare_CMap(id, uint64_t, double); + + +// like fgets, but removes any newline +char *fgetstr(char *string, int n, FILE *stream) +{ + char *res = fgets(string, n, stream); + if (!res) return res; + int last = strlen(string); + if (last) { + --last; if (string[last] == '\n') string[last] = '\0'; + } + return string; +} + +int read_words(CMap(si)* map) +{ + FILE * fp; +# define bufferLength 1024 + char line[bufferLength]; + size_t len = 0, i = 0; + size_t read; + + fp = fopen("words_dictionary.txt", "r"); + if (fp == NULL) + return -1; + + while (fgetstr(line, bufferLength, fp)) { + ++i; + if (i < 20) printf("%zu: %s\n", i, line); + cmap_si_put(map, line, i); + } + + fclose(fp); + return 0; +} + +int main() +{ + uint32_t i = 11, n = 671523123; + + CMap(si) words = cmap_init(); + printf("read\n"); + read_words(&words); + //for (i=0; i<100; i++) { printf("%d: %d\n", i, graph[i]); graph[i] = 0; } + CMapEntry(si)* num = NULL; + num = cmap_si_get(words, "hello"); + if (num) printf("%s: %d\n", num->key.str, num->value); + + num = cmap_si_get(words, "funny"); + if (num) printf("%s: %d\n", num->key.str, num->value); + + printf("%d, %d\n", cmap_size(words), cmap_capacity(words)); + cmap_si_clear(&words); + +/* + CVector(cs) strv = cvector_INIT; + + CString hello = cstring_make("Hello"); + cstring_assign(&hello, "Awesome"); + + + + cvector_cs_push(&strv, cstring_make("E1")); + cvector_cs_push(&strv, cstring_make("E2")); + cvector_cs_push(&strv, cstring_make("E3")); + {CVectorIter(cs) it; cforeach (it, cvector_cs, strv) { + printf(" %s\n", it.item->str); + }} + + {int i; for (i = 0; i < cvector_size(strv); ++i) { + printf(" %s\n", strv.data[i].str); + }} + cvector_cs_destroy(&strv); + + CMap(ss) smap = cmap_init(); + cmap_ss_put(&smap, "KEY1", cstring_make("VAL1")); + cmap_ss_put(&smap, "KEY2", cstring_make("VAL2")); + cmap_ss_put(&smap, "hello", cstring_makeCopy(hello)); + + cstring_destroy(&hello); + + {CMapIter(ss) it = cmap_ss_begin(smap), end = cmap_ss_end(smap); + for (; it.item != end.item; it = cmap_ss_next(it)) { + printf(" %s: %s\n", it.item->key.str, it.item->value.str); + }} + cmap_ss_destroy(&smap); +*/ + CMap(id) mymap = cmap_init(); + //for (i = 0; i < 600000; ++i) + // cmap_id_put(&mymap, ((uint64_t)i)*i, i * 1.0); + + + + //for (i=0; i<100; i++) { printf("%d: %d\n", i, graph[i]); graph[i] = 0; } + uint64_t tn = 75000; + cmap_id_put(&mymap, tn * tn, tn * 1.0); + printf("look %llu: %f\n", tn*tn, cmap_id_get(mymap, tn*tn) ? cmap_id_get(mymap, tn*tn)->value : -999.9); + + //for (i = 0; i < cmap_size(mymap); ++i) + // printf("look %d: %f\n", i*i, *cmap_id_get(mymap, i*i)); + /* + {CMapIter(id) it; int k = 0; + cforeach (it, cmap_id, mymap, k < 10, ++k) { + printf(" %d: %f\n", it.item->key, it.item->value); + }} + */ + cmap_id_destroy(&mymap); +} diff --git a/cstring.h b/cstring.h new file mode 100644 index 00000000..efedf1b6 --- /dev/null +++ b/cstring.h @@ -0,0 +1,158 @@ +#ifndef CSTRING__H__ +#define CSTRING__H__ + +#include +#include +#include +#include +#include + +#include "cdef.h" + +typedef uint32_t cstring_size_t; +typedef struct CString { + char* str; +} CString; + + +static cstring_size_t _cstring_null_rep[] = {0, 0, 0}; +#define _cstring_rep(cs) (((cstring_size_t *) (cs).str) - 2) + +#define cstring_INIT {(char* ) (_cstring_null_rep + 2)} +#define cstring_size(cs) ((cstring_size_t) _cstring_rep(cs)[0]) +#define cstring_capacity(cs) ((cstring_size_t) _cstring_rep(cs)[1]) + + +static inline void cstring_reserve(CString* self, cstring_size_t cap) { + cstring_size_t len = cstring_size(*self), oldcap = cstring_capacity(*self); + if (cap > oldcap) { + cstring_size_t* rep = (cstring_size_t *) realloc(oldcap ? _cstring_rep(*self) : NULL, sizeof(cstring_size_t) * 2 + cap + 1); + rep[0] = len; + rep[1] = cap; + self->str = (char* ) (rep + 2); + self->str[len] = '\0'; + } +} + +static inline void cstring_destroy(CString* self) { + if (cstring_capacity(*self)) { + free(_cstring_rep(*self)); + } +} + +static inline CString cstring_init(void) { + CString cs = cstring_INIT; + return cs; +} + +static inline CString cstring_makeN(const char* str, cstring_size_t len) { + CString cs = cstring_INIT; + if (len) { + cstring_reserve(&cs, len); + memcpy(cs.str, str, len); + _cstring_rep(cs)[0] = len; + cs.str[len] = '\0'; + } + return cs; +} + +static inline CString cstring_make(const char* str) { + return cstring_makeN(str, strlen(str)); +} + +static inline CString cstring_makeCopy(CString cs) { + return cstring_makeN(cs.str, cstring_size(cs)); +} + +static inline void cstring_clear(CString* self) { + CString cs = cstring_INIT; + cstring_destroy(self); + *self = cs; +} + +static inline CString* cstring_assignN(CString* self, const char* str, cstring_size_t len) { + if (len) { + cstring_reserve(self, len); + memmove(self->str, str, len); + self->str[len] = '\0'; + _cstring_rep(*self)[0] = len; + } + return self; +} + +static inline CString* cstring_assign(CString* self, const char* str) { + return cstring_assignN(self, str, strlen(str)); +} + +static inline CString* cstring_assignCopy(CString* self, CString cs2) { + return cstring_assignN(self, cs2.str, cstring_size(cs2)); +} + + +static inline CString* cstring_appendN(CString* self, const char* str, cstring_size_t len) { + if (len) { + cstring_size_t oldlen = cstring_size(*self), newlen = oldlen + len; + if (newlen > cstring_capacity(*self)) + cstring_reserve(self, (newlen * 5) / 3); + memmove(&self->str[oldlen], str, len); + self->str[newlen] = '\0'; + _cstring_rep(*self)[0] = newlen; + } + return self; +} + +static inline CString* cstring_append(CString* self, const char* str) { + return cstring_appendN(self, str, strlen(str)); +} +static inline CString* cstring_appendCopy(CString* self, CString cs2) { + return cstring_appendN(self, cs2.str, cstring_size(cs2)); +} + + +static inline char cstring_back(CString cs) { + return cs.str[cstring_size(cs) - 1]; +} + +static inline CString* cstring_push(CString* self, char value) { + return cstring_appendN(self, &value, 1); +} + + +static inline void cstring_pop(CString* self) { + --_cstring_rep(*self)[0]; +} + +/* readonly */ + +static inline bool cstring_empty(CString cs) { + return cstring_size(cs) == 0; +} + +static inline bool cstring_equals(CString cs1, const char* str) { + return strcmp(cs1.str, str) == 0; +} +static inline bool cstring_equalsS(CString cs1, CString cs2) { + return strcmp(cs1.str, cs2.str) == 0; +} + +static inline char* cstring_find(CString cs, const char* needle) { + return strstr(cs.str, needle); +} + +static inline char* cstring_splitFirst(const char* delimiters, CString cs) { + return strtok(cs.str, delimiters); +} + +static inline char* cstring_splitNext(const char* delimiters) { + return strtok(NULL, delimiters); +} + + +// CVector / CMap API functions: + +#define cstring_getRaw(x) ((x).str) +static inline uint32_t cstring_hash(const char** str, size_t sz_ignored) { return cdef_murmurHash(*str, strlen(*str)); } +static inline int cstring_compare(CString* self, const char** str, size_t sz_ignored) { return strcmp(self->str, *str); } + + +#endif diff --git a/cvector.h b/cvector.h new file mode 100644 index 00000000..b19ef791 --- /dev/null +++ b/cvector.h @@ -0,0 +1,137 @@ +#ifndef CVECTOR__H__ +#define CVECTOR__H__ + +#include +#include +#include +#include +#include + +#include "cdef.h" + +typedef uint32_t cvector_size_t; + +#define _cvector_size(cv) ((cvector_size_t *)(cv).data)[-2] +#define _cvector_capacity(cv) ((cvector_size_t *)(cv).data)[-1] + +static inline cvector_size_t* _cvector_alloced(void* data) { + return data ? ((cvector_size_t *) data) - 2 : NULL; +} +static inline cvector_size_t _cvector_safe_size(const void* data) { + return data ? ((const cvector_size_t *) data)[-2] : 0; +} +static inline cvector_size_t _cvector_safe_capacity(const void* data) { + return data ? ((const cvector_size_t *) data)[-1] : 0; +} + + +#define CVector(tag) CVector_##tag##_t +#define CVectorIter(tag) CVectorIter_##tag##_t + +#define cvector_INIT {NULL} +#define cvector_size(cv) _cvector_safe_size((cv).data) +#define cvector_capacity(cv) _cvector_safe_capacity((cv).data) +#define cvector_empty(cv) (_cvector_safe_size((cv).data) == 0) + +#define declare_CVector(...) cdef_MACRO_OVERLOAD(declare_CVector, __VA_ARGS__) +#define declare_CVector_2(tag, T) declare_CVector_3(tag, T, cdef_destroy) +#define declare_CVector_STR(tag) declare_CVector_3(tag, CString, cstring_destroy) + +#define declare_CVector_3(tag, T, valueDestr) \ +typedef T cvector_##tag##_value_t; \ +typedef struct CVector(tag) { \ + T* data; \ +} CVector(tag); \ +typedef struct CVectorIter(tag) { \ + T* item; \ +} CVectorIter(tag); \ + \ +static inline CVector(tag) cvector_##tag##_init(void) { \ + CVector(tag) cv = cvector_INIT; \ + return cv; \ +} \ + \ +static inline void cvector_##tag##_swap(CVector(tag)* v1, CVector(tag)* v2) { \ + T* data = v1->data; v1->data = v2->data; v2->data = data; \ +} \ + \ +static inline void cvector_##tag##_destroy(CVector(tag)* self) { \ + T* p = self->data; \ + cvector_size_t i = 0, n = cvector_size(*self); \ + for (; i < n; ++p, ++i) valueDestr(p); \ + free(_cvector_alloced(self->data)); \ +} \ + \ +static inline void cvector_##tag##_reserve(CVector(tag)* self, cvector_size_t cap) { \ + if (cap > cvector_capacity(*self)) { \ + cvector_size_t len = cvector_size(*self); \ + cvector_size_t* rep = (cvector_size_t *) realloc(_cvector_alloced(self->data), 2 * sizeof(cvector_size_t) + cap * sizeof(T)); \ + self->data = (T *) (rep + 2); \ + rep[0] = len; \ + rep[1] = cap; \ + } \ +} \ + \ + \ +static inline CVector(tag) cvector_##tag##_make(const T* data, cvector_size_t len) { \ + CVector(tag) cv = cvector_INIT; \ + if (len) { \ + cvector_##tag##_reserve(&cv, len); \ + memcpy(cv.data, data, len * sizeof(T)); \ + _cvector_size(cv) = len; \ + } \ + return cv; \ +} \ + \ +static inline void cvector_##tag##_clear(CVector(tag)* self) { \ + CVector(tag) cv = cvector_INIT; \ + cvector_##tag##_destroy(self); \ + *self = cv; \ +} \ + \ + \ +static inline void cvector_##tag##_push(CVector(tag)* self, T value) { \ + cvector_size_t newsize = cvector_size(*self) + 1; \ + if (newsize > cvector_capacity(*self)) \ + cvector_##tag##_reserve(self, 7 + newsize * 5 / 3); \ + self->data[cvector_size(*self)] = value; \ + _cvector_size(*self) = newsize; \ +} \ + \ +static inline void cvector_##tag##_insert(CVector(tag)* self, cvector_size_t pos, T value) { \ + cvector_##tag##_push(self, value); \ + cvector_size_t len = cvector_size(*self); \ + memmove(&self->data[pos + 1], &self->data[pos], (len - pos - 1) * sizeof(T)); \ + self->data[pos] = value; \ +} \ + \ + \ +static inline T cvector_##tag##_back(CVector(tag) cv) { \ + return cv.data[_cvector_size(cv) - 1]; \ +} \ + \ + \ +static inline T cvector_##tag##_pop(CVector(tag)* self) { \ + T value = cvector_##tag##_back(*self); \ + --_cvector_size(*self); \ + return value; \ +} \ + \ + \ +static inline CVectorIter(tag) cvector_##tag##_begin(CVector(tag) vec) { \ + CVectorIter(tag) iter = {vec.data}; \ + return iter; \ +} \ + \ +static inline CVectorIter(tag) cvector_##tag##_next(CVectorIter(tag) iter) { \ + ++iter.item; \ + return iter; \ +} \ + \ +static inline CVectorIter(tag) cvector_##tag##_end(CVector(tag) vec) { \ + CVectorIter(tag) iter = {vec.data + cvector_size(vec)}; \ + return iter; \ +} + + +#endif -- cgit v1.2.3