From a433992d150f22c2fdff2c13801a74b31b726b55 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Sat, 26 Sep 2020 10:54:19 +0200 Subject: Update zix --- src/zix/btree.c | 17 +++++++---- src/zix/common.h | 17 ++++++++--- src/zix/digest.c | 90 ++++++++++++++++++++++++++++++++++++++++++++++++-------- src/zix/digest.h | 26 +++++++++++++++- src/zix/hash.c | 15 ++++++---- src/zix/hash.h | 12 ++++---- 6 files changed, 143 insertions(+), 34 deletions(-) (limited to 'src/zix') diff --git a/src/zix/btree.c b/src/zix/btree.c index bc07f51..0a8010f 100644 --- a/src/zix/btree.c +++ b/src/zix/btree.c @@ -594,8 +594,10 @@ zix_btree_remove(ZixBTree* const t, n->children[1]->n_vals}; n = zix_btree_merge(t, n, 0); - ti->stack[ti->level].node = n; - ti->stack[ti->level].index = counts[i]; + if (ti) { + ti->stack[ti->level].node = n; + ti->stack[ti->level].index = counts[i]; + } } else { // Both child's siblings are minimal, merge them if (i < n->n_vals) { @@ -659,6 +661,9 @@ zix_btree_lower_bound(const ZixBTree* const t, if (!t) { *ti = NULL; return ZIX_STATUS_BAD_ARG; + } else if (!t->root) { + *ti = NULL; + return ZIX_STATUS_SUCCESS; } ZixBTreeNode* n = t->root; @@ -760,7 +765,7 @@ zix_btree_iter_copy(const ZixBTreeIter* const i) ZIX_API bool zix_btree_iter_is_end(const ZixBTreeIter* const i) { - return !i || (i->level == 0 && i->stack[0].node == NULL); + return !i || i->stack[0].node == NULL; } ZIX_API bool @@ -768,14 +773,16 @@ zix_btree_iter_equals(const ZixBTreeIter* const lhs, const ZixBTreeIter* const r { if (zix_btree_iter_is_end(lhs) && zix_btree_iter_is_end(rhs)) { return true; - } else if (!lhs || !rhs || lhs->n_levels != rhs->n_levels) { + } else if (zix_btree_iter_is_end(lhs) || zix_btree_iter_is_end(rhs)) { + return false; + } else if (!lhs || !rhs || lhs->level != rhs->level) { return false; } return !memcmp(lhs, rhs, sizeof(ZixBTreeIter) + - lhs->n_levels * sizeof(ZixBTreeIterFrame)); + (lhs->level + 1) * sizeof(ZixBTreeIterFrame)); } ZIX_API void diff --git a/src/zix/common.h b/src/zix/common.h index a59c033..3271858 100644 --- a/src/zix/common.h +++ b/src/zix/common.h @@ -17,6 +17,8 @@ #ifndef ZIX_COMMON_H #define ZIX_COMMON_H +#include + /** @addtogroup zix @{ @@ -48,14 +50,21 @@ #ifdef __cplusplus extern "C" { -#else -# include #endif #ifdef __GNUC__ -#define ZIX_UNUSED __attribute__((__unused__)) +#define ZIX_LOG_FUNC(fmt, arg1) __attribute__((format(printf, fmt, arg1))) +#else +#define ZIX_LOG_FUNC(fmt, arg1) +#endif + +// Unused parameter macro to suppresses warnings and make it impossible to use +#if defined(__cplusplus) +# define ZIX_UNUSED(name) +#elif defined(__GNUC__) +# define ZIX_UNUSED(name) name##_unused __attribute__((__unused__)) #else -#define ZIX_UNUSED +# define ZIX_UNUSED(name) name #endif typedef enum { diff --git a/src/zix/digest.c b/src/zix/digest.c index 7d9c035..889cfde 100644 --- a/src/zix/digest.c +++ b/src/zix/digest.c @@ -1,5 +1,5 @@ /* - Copyright 2012-2014 David Robillard + Copyright 2012-2020 David Robillard Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above @@ -20,23 +20,29 @@ # include #endif +#include +#include + +#ifdef __SSE4_2__ + +// SSE 4.2 CRC32 + ZIX_API uint32_t zix_digest_start(void) { -#ifdef __SSE4_2__ - return 1; // CRC32 initial value -#else - return 5381; // DJB hash initial value -#endif + return 1; } ZIX_API uint32_t zix_digest_add(uint32_t hash, const void* const buf, const size_t len) { const uint8_t* str = (const uint8_t*)buf; -#ifdef __SSE4_2__ - // SSE 4.2 CRC32 - for (size_t i = 0; i < (len / sizeof(uint32_t)); ++i) { + + for (size_t i = 0; i < (len / sizeof(uint64_t)); ++i) { + hash = (uint32_t)_mm_crc32_u64(hash, *(const uint64_t*)str); + str += sizeof(uint64_t); + } + if (len & sizeof(uint32_t)) { hash = _mm_crc32_u32(hash, *(const uint32_t*)str); str += sizeof(uint32_t); } @@ -47,11 +53,71 @@ zix_digest_add(uint32_t hash, const void* const buf, const size_t len) if (len & sizeof(uint8_t)) { hash = _mm_crc32_u8(hash, *(const uint8_t*)str); } + + return hash; +} + +ZIX_API uint32_t +zix_digest_add_64(uint32_t hash, const void* const buf, const size_t len) +{ + assert((uintptr_t)buf % sizeof(uint64_t) == 0); + assert(len % sizeof(uint64_t) == 0); + + const uint64_t* ptr = (const uint64_t*)buf; + + for (size_t i = 0; i < (len / sizeof(uint64_t)); ++i) { + hash = (uint32_t)_mm_crc32_u64(hash, *ptr); + ++ptr; + } + + return hash; +} + +ZIX_API uint32_t +zix_digest_add_ptr(const uint32_t hash, const void* const ptr) +{ +#if UINTPTR_MAX == UINT64_MAX + return (uint32_t)_mm_crc32_u64(hash, (uintptr_t)ptr); +#else + return _mm_crc32_u32(hash, (uintptr_t)ptr); +#endif +} + #else - // Classic DJB hash + +// Classic DJB hash + +ZIX_API uint32_t +zix_digest_start(void) +{ + return 5381; +} + +ZIX_API uint32_t +zix_digest_add(uint32_t hash, const void* const buf, const size_t len) +{ + const uint8_t* str = (const uint8_t*)buf; + for (size_t i = 0; i < len; ++i) { - hash = (hash << 5) + hash + str[i]; + hash = (hash << 5u) + hash + str[i]; } -#endif + return hash; } + +ZIX_API uint32_t +zix_digest_add_64(uint32_t hash, const void* const buf, const size_t len) +{ + assert((uintptr_t)buf % sizeof(uint64_t) == 0); + assert(len % sizeof(uint64_t) == 0); + + return zix_digest_add(hash, buf, len); +} + +ZIX_API uint32_t +zix_digest_add_ptr(const uint32_t hash, const void* const ptr) +{ + return zix_digest_add(hash, &ptr, sizeof(ptr)); +} + +#endif diff --git a/src/zix/digest.h b/src/zix/digest.h index 264c918..16ba9b9 100644 --- a/src/zix/digest.h +++ b/src/zix/digest.h @@ -1,5 +1,5 @@ /* - Copyright 2012 David Robillard + Copyright 2012-2020 David Robillard Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above @@ -26,12 +26,36 @@ extern "C" { #endif +/** + Return an initial empty digest value. +*/ ZIX_API uint32_t zix_digest_start(void); +/** + Update `hash` to include `buf`, a buffer of `len` bytes. + + This can be used for any size or alignment. +*/ ZIX_API uint32_t zix_digest_add(uint32_t hash, const void* buf, size_t len); +/** + Update `hash` to include `buf`, a 64-bit aligned buffer of `len` bytes. + + Both `buf` and `len` must be evenly divisible by 8 (64 bits). +*/ +ZIX_API uint32_t +zix_digest_add_64(uint32_t hash, const void* buf, size_t len); + +/** + Update `hash` to include `ptr`. + + This hashes the value of the pointer itself, and does not dereference `ptr`. +*/ +ZIX_API uint32_t +zix_digest_add_ptr(uint32_t hash, const void* ptr); + #ifdef __cplusplus } /* extern "C" */ #endif diff --git a/src/zix/hash.c b/src/zix/hash.c index f633e16..c4a2dba 100644 --- a/src/zix/hash.c +++ b/src/zix/hash.c @@ -1,5 +1,5 @@ /* - Copyright 2011-2014 David Robillard + Copyright 2011-2018 David Robillard Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above @@ -14,13 +14,12 @@ OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ +#include "zix/hash.h" + #include -#include #include #include -#include "zix/hash.h" - /** Primes, each slightly less than twice its predecessor, and as far away from powers of two as possible. @@ -76,6 +75,10 @@ zix_hash_new(ZixHashFunc hash_func, ZIX_API void zix_hash_free(ZixHash* hash) { + if (!hash) { + return; + } + for (unsigned b = 0; b < *hash->n_buckets; ++b) { ZixHashEntry* bucket = hash->buckets[b]; for (ZixHashEntry* e = bucket; e;) { @@ -141,7 +144,7 @@ find_entry(const ZixHash* hash, return NULL; } -ZIX_API const void* +ZIX_API void* zix_hash_find(const ZixHash* hash, const void* value) { const unsigned h_nomod = hash->hash_func(value); @@ -151,7 +154,7 @@ zix_hash_find(const ZixHash* hash, const void* value) } ZIX_API ZixStatus -zix_hash_insert(ZixHash* hash, const void* value, const void** inserted) +zix_hash_insert(ZixHash* hash, const void* value, void** inserted) { unsigned h_nomod = hash->hash_func(value); unsigned h = h_nomod % *hash->n_buckets; diff --git a/src/zix/hash.h b/src/zix/hash.h index db24c45..9546a64 100644 --- a/src/zix/hash.h +++ b/src/zix/hash.h @@ -17,11 +17,11 @@ #ifndef ZIX_HASH_H #define ZIX_HASH_H +#include "zix/common.h" + #include #include -#include "zix/common.h" - #ifdef __cplusplus extern "C" { #endif @@ -91,9 +91,9 @@ zix_hash_size(const ZixHash* hash); @return ZIX_STATUS_SUCCESS, ZIX_STATUS_EXISTS, or ZIX_STATUS_NO_MEM. */ ZIX_API ZixStatus -zix_hash_insert(ZixHash* hash, - const void* value, - const void** inserted); +zix_hash_insert(ZixHash* hash, + const void* value, + void** inserted); /** Remove an item from `hash`. @@ -112,7 +112,7 @@ zix_hash_remove(ZixHash* hash, @param hash The hash table. @param value The value to search for. */ -ZIX_API const void* +ZIX_API void* zix_hash_find(const ZixHash* hash, const void* value); -- cgit v1.2.1