From 7c326f3effd9977cb34e23d9cc9e9eb42ae3c789 Mon Sep 17 00:00:00 2001 From: tylo Date: Wed, 11 Mar 2020 10:47:54 +0100 Subject: Renamed cdef.h to cdefs.h including symbols inside. --- benchmark.cpp | 20 +++++-------------- cdef.h | 61 -------------------------------------------------------- cdefs.h | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ cmap.h | 22 ++++++++++---------- cstring.h | 13 ++++++------ cvector.h | 10 +++------- 6 files changed, 89 insertions(+), 101 deletions(-) delete mode 100644 cdef.h create mode 100644 cdefs.h diff --git a/benchmark.cpp b/benchmark.cpp index ca65ce5a..30bf9d2c 100644 --- a/benchmark.cpp +++ b/benchmark.cpp @@ -1,10 +1,8 @@ #include #include #include -#include "cmap.h" -#include "cvector.h" #include "cstring.h" -#include "hash_set.hpp" +#include "cmap.h" #include @@ -21,31 +19,23 @@ int main() const size_t N = 10000000; printf("Starting\n"); - //cmap_ii_reserve(&map, N * 1.7); + //cmap_ii_reserve(&map, N * 1.25); before = clock(); fib1 = 0, fib2 = 1; for (size_t i = 0; i < N; ++i) { checksum += ++cmap_ii_put(&map, FIBONACCI_NEXT, i)->value; } difference = clock() - before; - printf("%llu Check: %f\n", checksum, 1.0 * difference / CLOCKS_PER_SEC); + printf("Check: %llu, size: %llu, time: %f\n", checksum, cmap_size(map), 1.0 * difference / CLOCKS_PER_SEC); cmap_ii_destroy(&map); std::unordered_map map2; + //map2.reserve(N); before = clock(); fib1 = 0, fib2 = 1; checksum = 0; for (size_t i = 0; i < N; ++i) checksum += ++(map2[FIBONACCI_NEXT] = i); difference = clock() - before; - printf("%llu Check: %f\n", checksum, 1.0 * difference / CLOCKS_PER_SEC); + printf("Check: %llu, size: %llu, time: %f\n", checksum, map2.size(), 1.0 * difference / CLOCKS_PER_SEC); map2.clear(); - - emhash7::HashMap map3; - //map3.reserve(N); - before = clock(); - fib1 = 0, fib2 = 1; checksum = 0; - for (size_t i = 0; i < N; ++i) - checksum += ++(*map3.insert(FIBONACCI_NEXT, i).first).second; - difference = clock() - before; - printf("%llu Check: %f\n", checksum, 1.0 * difference / CLOCKS_PER_SEC); } \ No newline at end of file diff --git a/cdef.h b/cdef.h deleted file mode 100644 index 865436a0..00000000 --- a/cdef.h +++ /dev/null @@ -1,61 +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 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_max_alloca (1000) -#define cdef_swap(T, x, y) { T __t = x; x = y; y = __t; } - -#define cdef_initRaw(x) (x) -#define cdef_getRaw(x) (x) -static inline void cdef_destroy(void* value) {} - -#define cforeach(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 cdef_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/cdefs.h b/cdefs.h new file mode 100644 index 00000000..6fb10410 --- /dev/null +++ b/cdefs.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 CDEFS__H__ +#define CDEFS__H__ + +#include +#include + +// Macro overloading feature support: https://rextester.com/ONP80107 +#define cdefs_CAT( A, B ) A ## B +#define cdefs_EXPAND(...) __VA_ARGS__ +#define cdefs_VA_ARG_SIZE(...) cdefs_EXPAND(cdefs_APPLY_ARG_N((__VA_ARGS__, cdefs_RSEQ_N))) +#define cdefs_APPLY_ARG_N(ARGS) cdefs_EXPAND(cdefs_ARG_N ARGS) +#define cdefs_ARG_N(_0, _1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, N,...) N +#define cdefs_RSEQ_N 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 +#define cdefs_OVERLOAD_SELECT(NAME, NUM) cdefs_CAT( NAME ## _, NUM) + +#define cdefs_MACRO_OVERLOAD(NAME, ...) cdefs_OVERLOAD_SELECT(NAME, cdefs_VA_ARG_SIZE(__VA_ARGS__))(__VA_ARGS__) +// #define foo(...) cdefs_MACRO_OVERLOAD(foo, __VA_ARGS__) +// #define foo_1(X) foo_2(X, 100) +// #define foo_2(X, Y) X + Y + +#define cdefs_max_alloca (1000) +#define cdefs_swap(T, x, y) { T __t = x; x = y; y = __t; } + +#define cdefs_initRaw(x) (x) +#define cdefs_getRaw(x) (x) +static inline void cdefs_destroy(void* value) {} + +#define cforeach(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 cdefs_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 index 9e5bcb88..542f7c87 100644 --- a/cmap.h +++ b/cmap.h @@ -51,27 +51,27 @@ typedef struct CMapEntry_##tag CMapEntry_##tag // CMap: -#define declare_CMap(...) cdef_MACRO_OVERLOAD(declare_CMap, __VA_ARGS__) +#define declare_CMap(...) cdefs_MACRO_OVERLOAD(declare_CMap, __VA_ARGS__) #define declare_CMap_3(tag, Key, Value) \ - declare_CMap_4(tag, Key, Value, cdef_destroy) + declare_CMap_4(tag, Key, Value, cdefs_destroy) #define declare_CMap_4(tag, Key, Value, valueDestroy) \ - declare_CMap_10(tag, Key, Value, valueDestroy, Key, cdef_initRaw, cdef_getRaw, memcmp, cdef_murmurHash, cdef_destroy) + declare_CMap_10(tag, Key, Value, valueDestroy, Key, memcmp, cdefs_murmurHash, cdefs_initRaw, cdefs_getRaw, cdefs_destroy) // CMap: -#define declare_CMap_StringKey(...) cdef_MACRO_OVERLOAD(declare_CMap_StringKey, __VA_ARGS__) +#define declare_CMap_StringKey(...) cdefs_MACRO_OVERLOAD(declare_CMap_StringKey, __VA_ARGS__) #define declare_CMap_StringKey_2(tag, Value) \ - declare_CMap_StringKey_3(tag, Value, cdef_destroy) + declare_CMap_StringKey_3(tag, Value, cdefs_destroy) #define declare_CMap_StringKey_3(tag, Value, valueDestroy) \ - declare_CMap_10(tag, CString, Value, valueDestroy, const char*, cstring_make, cstring_getRaw, cstring_compareRaw, cstring_hashRaw, cstring_destroy) + declare_CMap_10(tag, CString, Value, valueDestroy, const char*, cstring_compareRaw, cstring_hashRaw, cstring_make, cstring_getRaw, cstring_destroy) // CMap full: -#define declare_CMap_10(tag, Key, Value, valueDestroy, KeyRaw, keyInitRaw, keyGetRaw, keyCompare, keyHasher, keyDestroy) \ +#define declare_CMap_10(tag, Key, Value, valueDestroy, KeyRaw, keyCompareRaw, keyHashRaw, keyInitRaw, keyGetRaw, keyDestroy) \ declare_CMapEntry(tag, Key, Value, keyDestroy, valueDestroy); \ declare_CVector_3(map_##tag, CMapEntry_##tag, cmapentry_##tag##_destroy); \ \ @@ -109,7 +109,7 @@ static inline void cmap_##tag##_clear(CMap_##tag* self) { \ \ static inline void cmap_##tag##_swap(CMap_##tag* a, CMap_##tag* b) { \ cvector_map_##tag##_swap(&a->_vec, &b->_vec); \ - cdef_swap(size_t, a->_size, b->_size); \ + cdefs_swap(size_t, a->_size, b->_size); \ } \ \ static inline void cmap_##tag##_setMaxLoadFactor(CMap_##tag* self, float fac) { \ @@ -120,7 +120,7 @@ static inline void cmap_##tag##_setMaxLoadFactor(CMap_##tag* self, float fac) { \ static inline size_t cmap_##tag##_bucket(CMap_##tag cm, KeyRaw rawKey) { \ size_t cap = cvector_capacity(cm._vec); \ - size_t idx = cmap_reduce(keyHasher(&rawKey, sizeof(Key)), cap); \ + size_t idx = cmap_reduce(keyHashRaw(&rawKey, sizeof(Key)), cap); \ size_t first = idx, erased_idx = cap; \ FIBONACCI_DECL; \ do { \ @@ -128,10 +128,10 @@ static inline size_t cmap_##tag##_bucket(CMap_##tag cm, KeyRaw rawKey) { \ case CMapEntry_VACANT: \ return erased_idx != cap ? erased_idx : idx; \ case CMapEntry_INUSE: \ - if (keyCompare(&cm._vec.data[idx].key, &rawKey, sizeof(Key)) != 0) \ + if (keyCompareRaw(&cm._vec.data[idx].key, &rawKey, sizeof(Key)) != 0) \ break; \ if (erased_idx != cap) { \ - cdef_swap(CMapEntry_##tag, cm._vec.data[erased_idx], cm._vec.data[idx]); \ + cdefs_swap(CMapEntry_##tag, cm._vec.data[erased_idx], cm._vec.data[idx]); \ return erased_idx; \ } \ return idx; \ diff --git a/cstring.h b/cstring.h index f877847c..bfffe2e3 100644 --- a/cstring.h +++ b/cstring.h @@ -25,11 +25,10 @@ #include #include -#include #include #include -#include "cdef.h" +#include "cdefs.h" typedef struct CString { char* str; @@ -138,10 +137,10 @@ static inline void _cstring_internalMove(CString* self, size_t pos1, size_t pos2 } static inline void cstring_insertN(CString* self, size_t pos, const char* str, size_t n) { - char* xstr = (char *) memcpy(n > cdef_max_alloca ? malloc(n) : alloca(n), str, n); + char* xstr = (char *) memcpy(n > cdefs_max_alloca ? malloc(n) : alloca(n), str, n); _cstring_internalMove(self, pos, pos + n); memcpy(&self->str[pos], xstr, n); - if (n > cdef_max_alloca) free(xstr); + if (n > cdefs_max_alloca) free(xstr); } static inline void cstring_insert(CString* self, size_t pos, const char* str) { @@ -161,10 +160,10 @@ static inline size_t cstring_findN(CString cs, size_t pos, const char* needle, s static inline size_t cstring_replaceN(CString* self, size_t pos, const char* s1, size_t n1, const char* s2, size_t n2) { size_t pos2 = cstring_findN(*self, pos, s1, n1); if (pos2 == cstring_npos) return cstring_npos; - char* xs2 = (char *) memcpy(n2 > cdef_max_alloca ? malloc(n2) : alloca(n2), s2, n2); + char* xs2 = (char *) memcpy(n2 > cdefs_max_alloca ? malloc(n2) : alloca(n2), s2, n2); _cstring_internalMove(self, pos2 + n1, pos2 + n2); memcpy(&self->str[pos2], xs2, n2); - if (n2 > cdef_max_alloca) free(xs2); + if (n2 > cdefs_max_alloca) free(xs2); return pos2; } @@ -238,7 +237,7 @@ static inline char* cstring_splitNext(const char* delimiters) { // CVector / CMap API functions: #define cstring_getRaw(x) ((x).str) -static inline uint32_t cstring_hashRaw(const char** str, size_t sz_ignored) { return cdef_murmurHash(*str, strlen(*str)); } +static inline uint32_t cstring_hashRaw(const char** str, size_t sz_ignored) { return cdefs_murmurHash(*str, strlen(*str)); } static inline int cstring_compareRaw(CString* self, const char** str, size_t sz_ignored) { return strcmp(self->str, *str); } diff --git a/cvector.h b/cvector.h index 58085eb4..02a351ed 100644 --- a/cvector.h +++ b/cvector.h @@ -24,12 +24,8 @@ #define CVECTOR__H__ #include -#include -#include #include -#include - -#include "cdef.h" +#include "cdefs.h" #define cvector_initializer {NULL} @@ -37,8 +33,8 @@ #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, Value) declare_CVector_3(tag, Value, cdef_destroy) +#define declare_CVector(...) cdefs_MACRO_OVERLOAD(declare_CVector, __VA_ARGS__) +#define declare_CVector_2(tag, Value) declare_CVector_3(tag, Value, cdefs_destroy) #define declare_CStringVector(tag) declare_CVector_3(tag, CString, cstring_destroy) -- cgit v1.2.3