From adc8cc5f6e6ae66864c0266656d284bd6de2dfec Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Mon, 15 Feb 2021 20:16:34 +0100 Subject: Added fast posix memccpy() - c_memccpy(). --- benchmarks/cmap_benchmark2.cpp | 1 + stc/cbits.h | 6 +++--- stc/cstr.h | 20 +++++++++++++++++++- 3 files changed, 23 insertions(+), 4 deletions(-) diff --git a/benchmarks/cmap_benchmark2.cpp b/benchmarks/cmap_benchmark2.cpp index f5c7aada..baa929a2 100644 --- a/benchmarks/cmap_benchmark2.cpp +++ b/benchmarks/cmap_benchmark2.cpp @@ -4,6 +4,7 @@ #include #include #include +#include #include "others/bytell_hash_map.hpp" #include "others/robin_hood.hpp" #include "others/hopscotch_map.h" diff --git a/stc/cbits.h b/stc/cbits.h index 0ac0f4ad..2eab9075 100644 --- a/stc/cbits.h +++ b/stc/cbits.h @@ -104,13 +104,13 @@ STC_INLINE void cbits_reset(cbits_t *self, size_t i) { self->_arr[i >> 6] &= ~(1ull << (i & 63)); } STC_INLINE void cbits_set_value(cbits_t *self, size_t i, bool value) { - value ? cbits_set(self, i) : cbits_reset(self, i); + self->_arr[i >> 6] ^= (-(uint64_t)value ^ self->_arr[i >> 6]) & 1ull << (i & 63); } STC_INLINE void cbits_flip(cbits_t *self, size_t i) { self->_arr[i >> 6] ^= 1ull << (i & 63); } STC_INLINE void cbits_set_all(cbits_t *self, bool value) { - memset(self->_arr, value ? 0xff : 0x0, ((self->size + 63) >> 6) * 8); + memset(self->_arr, -value, ((self->size + 63) >> 6) * 8); } STC_INLINE void cbits_set_all64(cbits_t *self, uint64_t pattern) { size_t n = (self->size + 63) >> 6; @@ -198,7 +198,7 @@ STC_DEF void cbits_resize(cbits_t* self, size_t size, bool value) { self->_arr = (uint64_t *) c_realloc(self->_arr, new_n * 8); self->size = size; if (new_n >= old_n) { - memset(self->_arr + old_n, value ? 0xff : 0x0, (new_n - old_n) * 8); + memset(self->_arr + old_n, -value, (new_n - old_n) * 8); if (old_n > 0) { uint64_t m = (1ull << (osize & 63)) - 1; /* mask */ value ? (self->_arr[old_n - 1] |= ~m) : (self->_arr[old_n - 1] &= m); diff --git a/stc/cstr.h b/stc/cstr.h index 02176664..5408548e 100644 --- a/stc/cstr.h +++ b/stc/cstr.h @@ -49,9 +49,10 @@ STC_API size_t cstr_find(cstr_t s, const char* needle); STC_API size_t cstr_find_n(cstr_t s, const char* needle, size_t pos, size_t nlen); STC_API size_t cstr_ifind_n(cstr_t s, const char* needle, size_t pos, size_t nlen); +STC_API void* c_memccpy(void* restrict dst, const void* restrict src, int c, size_t n); STC_API int c_strncasecmp(const char* s1, const char* s2, size_t n); STC_API char* c_strnfind(const char* s, const char* needle, size_t nmax); -STC_DEF char* c_istrnfind(const char* s, const char* needle, size_t nmax); +STC_API char* c_istrnfind(const char* s, const char* needle, size_t nmax); struct cstr_rep { size_t size, cap; char str[sizeof(size_t)]; }; #define _cstr_rep(self) c_container_of((self)->str, struct cstr_rep, str) @@ -392,6 +393,23 @@ cstr_ifind_n(cstr_t s, const char* needle, size_t pos, size_t nlen) { return res ? res - s.str : cstr_npos; } +/* http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord */ +STC_DEF void* +c_memccpy(void* restrict dst, const void* restrict src, int c, size_t n) { + enum {w = sizeof(uintptr_t)}; + #define __z (~(uintptr_t)0/255) + const uint8_t* s = (const uint8_t *) src; uint8_t *d = (uint8_t *) dst, *e = d + n; + const uint8_t *align = (const uint8_t *)(((uintptr_t)s + w-1) & ~(w-1)); + while (s != align) if ((*d++ = *s++) == (uint8_t) c) return d; + for (; d + w <= e; s += w, d += w) { + const uintptr_t x = *(uintptr_t *) s; + if (((x - __z) & ~x & __z*128) ^ (__z * (uint8_t) c)) break; /* hasvalue */ + memcpy(d, &x, w); + } + while (d < e) if ((*d++ = *s++) == (uint8_t) c) return d; + return NULL; +} + STC_DEF int c_strncasecmp(const char* s1, const char* s2, size_t n) { int ret = 0; -- cgit v1.2.3