From 29b1fb689c71837616023b3adc78eda3d32026b2 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Mon, 25 Apr 2022 20:03:04 +0200 Subject: Removed size argument to `i_hash` template parameter and `c_default_hash`. This was a "design error", and is not worth keeping for backward compability. Please update your code where you use i_hash template parameter (simply remove second argument). --- README.md | 5 +++-- benchmarks/misc/rust_cmap.c | 1 - docs/carc_api.md | 2 +- docs/cbox_api.md | 2 +- docs/ccommon_api.md | 2 +- docs/cmap_api.md | 11 +++++------ docs/cstr_api.md | 2 +- docs/csview_api.md | 2 +- examples/box.c | 4 ++-- examples/city.c | 4 ++-- examples/person_arc.c | 4 ++-- examples/rawptr_elements.c | 2 +- examples/vikings.c | 2 +- include/stc/alt/cstr.h | 13 ++++++++++--- include/stc/carc.h | 6 +++--- include/stc/cbox.h | 6 +++--- include/stc/ccommon.h | 18 +++++++++--------- include/stc/cmap.h | 4 ++-- include/stc/cstr.h | 4 ++-- include/stc/csview.h | 4 ++-- 20 files changed, 52 insertions(+), 46 deletions(-) diff --git a/README.md b/README.md index d87f29ba..4c1f9e02 100644 --- a/README.md +++ b/README.md @@ -3,9 +3,10 @@ STC - Smart Template Containers for C ===================================== -News: Version 3.5 released (Mar 2022) +News: Version 3.6 released (Mar 2022) ------------------------------------- - Swapped to new **cstr** (*short string optimized*, aka SSO). Note that `cstr_str(&s)` must be used, `s.str` is no longer usable. +- Removed size argument to `i_hash` template parameter and `c_default_hash`. This was a "design error". Please update your code. - Added general `i_clone` template parameter: containers with smart pointers (**carc**, **cbox**) can now be correctly cloned. - Allows for `i_key*` template parameters instead of `i_val*` for all containers, not only for **cset** and **csset**. - Optimized *c_default_hash()*. Therefore *c_hash32()* and *c_hash64()* are removed (same speed). @@ -272,7 +273,7 @@ The list of template parameters: - `i_key` - Element key type for map/set only. **[required]**. - `i_val` - Element value type. **[required]**. For cmap/csmap, it is the mapped value type. - `i_cmp` - Three-way comparison of two `i_keyraw or i_valraw` pointers - **[required]** for non-integral valraw types unless `i_opt c_no_cmp` is defined. -- `i_hash` - Hash function taking `i_keyraw *` and a size - defaults to `!i_cmp`. **[required]** for non-POD valraw type. +- `i_hash` - Hash function taking `i_keyraw *` - defaults to `c_default_hash`. **[required]** for non-POD valraw type. - `i_eq` - Equality comparison of two `i_keyraw *` - defaults to `!i_cmp`. Companion with `i_hash`. Properties: diff --git a/benchmarks/misc/rust_cmap.c b/benchmarks/misc/rust_cmap.c index 7df8fa59..5a052915 100644 --- a/benchmarks/misc/rust_cmap.c +++ b/benchmarks/misc/rust_cmap.c @@ -2,7 +2,6 @@ #include #define i_key uint64_t #define i_val uint64_t -#define i_hash c_hash64 #define i_tag u64 #include diff --git a/docs/carc_api.md b/docs/carc_api.md index 3f5675f0..301c25b1 100644 --- a/docs/carc_api.md +++ b/docs/carc_api.md @@ -47,7 +47,7 @@ long carc_X_use_count(carc_X ptr); void carc_X_reset(carc_X* self); void carc_X_reset_from(carc_X* self, i_val val); // assign new carc with value. Takes ownership of val. -uint64_t carc_X_value_hash(const i_val* x, size_t n); // hash value +uint64_t carc_X_value_hash(const i_val* x); // hash value int carc_X_value_cmp(const i_val* x, const i_val* y); // compares pointer addresses if 'i_opt c_no_cmp' // is defined. Otherwise uses 'i_cmp' or default compare. bool carc_X_value_eq(const i_val* x, const i_val* y); // cbox_X_value_cmp == 0 diff --git a/docs/cbox_api.md b/docs/cbox_api.md index a4e88801..2e16815b 100644 --- a/docs/cbox_api.md +++ b/docs/cbox_api.md @@ -44,7 +44,7 @@ void cbox_X_drop(cbox_X* self); // destruct the c void cbox_X_reset(cbox_X* self); void cbox_X_reset_from(cbox_X* self, i_val val); // assign new cbox with value. Takes ownership of val. -uint64_t cbox_X_value_hash(const i_val* x, size_t n); // hash value +uint64_t cbox_X_value_hash(const i_val* x); // hash value int cbox_X_value_cmp(const i_val* x, const i_val* y); // compares pointer addresses if 'i_opt c_no_cmp' // is defined. Otherwise uses 'i_cmp' or default compare. bool cbox_X_value_eq(const i_val* x, const i_val* y); // cbox_X_value_cmp == 0 diff --git a/docs/ccommon_api.md b/docs/ccommon_api.md index 64c1f5fe..41a88065 100644 --- a/docs/ccommon_api.md +++ b/docs/ccommon_api.md @@ -214,7 +214,7 @@ void c_default_drop(Type* val); // does nothing typedef const char* crawstr; int crawstr_cmp(const crawstr* x, const crawstr* y); bool crawstr_eq(const crawstr* x, const crawstr* y); -uint64_t crawstr_hash(const crawstr* x, size_t dummy); +uint64_t crawstr_hash(const crawstr* x); ``` ### c_malloc, c_calloc, c_realloc, c_free diff --git a/docs/cmap_api.md b/docs/cmap_api.md index d51df6b2..a730bee0 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -85,10 +85,9 @@ cmap_X_raw cmap_X_value_toraw(cmap_X_value* pval); ``` Helpers: ```c -uint64_t c_strhash(const char *str); // utility function - -// hash template parameter functions: -uint64_t c_default_hash(const void *data, size_t len); // key is any integral type +uint64_t c_default_hash(const X *obj); // macro, calls c_fasthash(obj, sizeof *obj) +uint64_t c_strhash(const char *str); // string hash funcion, uses strlen() +uint64_t c_fasthash(const void *data, size_t len); // base hash function // equalto template parameter functions: bool c_default_eq(const i_keyraw* a, const i_keyraw* b); // *a == *b @@ -278,7 +277,7 @@ static inline int Viking_cmp(const Viking* a, const Viking* b) { return c ? c : cstr_cmp(&a->country, &b->country); } -static inline uint32_t Viking_hash(const Viking* a, int ignored) { +static inline uint32_t Viking_hash(const Viking* a) { return c_strhash(cstr_str(&a->name)) ^ (c_strhash(cstr_str(&a->country)) >> 15); } @@ -355,7 +354,7 @@ typedef struct RViking { const char* country; } RViking; -static inline uint64_t RViking_hash(const RViking* raw, size_t ignore) { +static inline uint64_t RViking_hash(const RViking* raw) { uint64_t hash = c_strhash(raw->name) ^ (c_strhash(raw->country) >> 15); return hash; } diff --git a/docs/cstr_api.md b/docs/cstr_api.md index 5005c6f7..a7c45152 100644 --- a/docs/cstr_api.md +++ b/docs/cstr_api.md @@ -84,7 +84,7 @@ Note that all methods with arguments `(..., const char* str, size_t n)`, `n` mus ```c int cstr_cmp(const cstr *s1, const cstr *s2); bool cstr_eq(const cstr *s1, const cstr *s2); -bool cstr_hash(const cstr *s, ...); +bool cstr_hash(const cstr *s); char* c_strnstrn(const char* str, const char* needle, size_t slen, size_t nlen); int c_strncasecmp(const char* str1, const char* str2, size_t n); diff --git a/docs/csview_api.md b/docs/csview_api.md index 57aa0d55..b4319c85 100644 --- a/docs/csview_api.md +++ b/docs/csview_api.md @@ -98,7 +98,7 @@ bool cstr_ends_with_sv(cstr s, csview sub); ```c int csview_cmp(const csview* x, const csview* y); bool csview_eq(const csview* x, const csview* y); -uint64_t csview_hash(const csview* x, size_t dummy); +uint64_t csview_hash(const csview* x); ``` ## Types diff --git a/examples/box.c b/examples/box.c index 4a43b149..c50ced1e 100644 --- a/examples/box.c +++ b/examples/box.c @@ -7,8 +7,8 @@ Person Person_new(const char* name, const char* last) { return (Person){.name = cstr_from(name), .last = cstr_from(last)}; } -uint64_t Person_hash(const Person* a, size_t n) { - return cstr_hash(&a->name, 0) ^ cstr_hash(&a->last, 0); +uint64_t Person_hash(const Person* a) { + return cstr_hash(&a->name) ^ cstr_hash(&a->last); } int Person_cmp(const Person* a, const Person* b) { diff --git a/examples/city.c b/examples/city.c index 0e1cbe96..d1bee4b7 100644 --- a/examples/city.c +++ b/examples/city.c @@ -12,8 +12,8 @@ static inline int City_cmp(const City* a, const City* b) { return c ? c : cstr_cmp(&a->country, &b->country); } -static inline uint64_t City_hash(const City* a, size_t n) { - return cstr_hash(&a->name, 0) ^ cstr_hash(&a->country, 0); +static inline uint64_t City_hash(const City* a) { + return cstr_hash(&a->name) ^ cstr_hash(&a->country); } static inline City City_clone(City c) { diff --git a/examples/person_arc.c b/examples/person_arc.c index 9d245340..3e3f662f 100644 --- a/examples/person_arc.c +++ b/examples/person_arc.c @@ -12,8 +12,8 @@ int Person_cmp(const Person* a, const Person* b) { return c ? c : cstr_cmp(&a->last, &b->last); } -uint64_t Person_hash(const Person* a, size_t n) { - return cstr_hash(&a->name, 0) ^ cstr_hash(&a->last, 0); +uint64_t Person_hash(const Person* a) { + return cstr_hash(&a->name) ^ cstr_hash(&a->last); } Person Person_clone(Person p) { diff --git a/examples/rawptr_elements.c b/examples/rawptr_elements.c index 20231528..a1344ea7 100644 --- a/examples/rawptr_elements.c +++ b/examples/rawptr_elements.c @@ -8,7 +8,7 @@ struct { double x, y; } typedef Point; #define i_key Point* #define i_keydrop(x) c_free(*(x)) #define i_keyfrom(x) c_new(Point, *(x)) -#define i_hash(x, n) c_default_hash(*(x), sizeof **(x)) +#define i_hash(x) c_default_hash(*(x)) #define i_cmp(x, y) memcmp(*(x), *(y), sizeof **(x)) // not good! #define i_tag pnt #include diff --git a/examples/vikings.c b/examples/vikings.c index ff2fe8ab..51ab92f8 100644 --- a/examples/vikings.c +++ b/examples/vikings.c @@ -18,7 +18,7 @@ typedef struct RViking { const char* country; } RViking; -uint64_t RViking_hash(const RViking* raw, size_t ignore) { +uint64_t RViking_hash(const RViking* raw) { uint64_t hash = c_strhash(raw->name) ^ (c_strhash(raw->country) >> 15); return hash; } diff --git a/include/stc/alt/cstr.h b/include/stc/alt/cstr.h index 06f8eae1..f81736dc 100644 --- a/include/stc/alt/cstr.h +++ b/include/stc/alt/cstr.h @@ -168,9 +168,16 @@ STC_INLINE int c_strncasecmp(const char* s1, const char* s2, size_t nmax) { } /* container adaptor functions: */ -#define cstr_cmp(xp, yp) strcmp((xp)->str, (yp)->str) -#define cstr_eq(xp, yp) (!cstr_cmp(xp, yp)) -#define cstr_hash(xp, dummy) c_strhash((xp)->str) +#define cstr_cmp(xp, yp) strcmp((xp)->str, (yp)->str) + +STC_INLINE bool cstr_eq(const cstr* x, const cstr* y) { + size_t xs = _cstr_p(x)->size, ys = _cstr_p(y)->size; + return xs == ys && !memcmp(x->str, y->str, xs); +} +STC_INLINE uint64_t cstr_hash(const cstr *self) { + return c_fasthash(self->str, _cstr_p(self)->size); +} + /* -------------------------- IMPLEMENTATION ------------------------- */ #if defined(_i_implement) diff --git a/include/stc/carc.h b/include/stc/carc.h index 1cdca419..80b9a879 100644 --- a/include/stc/carc.h +++ b/include/stc/carc.h @@ -169,12 +169,12 @@ _cx_memb(_take)(_cx_self* self, _cx_self ptr) { } STC_INLINE uint64_t -_cx_memb(_value_hash)(const _cx_value* x, size_t n) { +_cx_memb(_value_hash)(const _cx_value* x) { #if c_option(c_no_cmp) - return c_default_hash(&x, sizeof x); + return c_default_hash(&x); #else _cx_raw rx = i_keyto(x); - return i_hash((&rx), (sizeof rx)); + return i_hash((&rx)); #endif } diff --git a/include/stc/cbox.h b/include/stc/cbox.h index fa6ef2a9..14459640 100644 --- a/include/stc/cbox.h +++ b/include/stc/cbox.h @@ -146,12 +146,12 @@ _cx_memb(_take)(_cx_self* self, _cx_self other) { } STC_INLINE uint64_t -_cx_memb(_value_hash)(const _cx_value* x, size_t n) { +_cx_memb(_value_hash)(const _cx_value* x) { #if c_option(c_no_cmp) - return c_default_hash(&x, sizeof x); + return c_default_hash(&x); #else _cx_raw rx = i_keyto(x); - return i_hash((&rx), (sizeof rx)); + return i_hash((&rx)); #endif } diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index 1c19bde7..dd048c43 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -92,27 +92,27 @@ #define c_default_toraw(ptr) (*(ptr)) #define c_default_drop(ptr) ((void) (ptr)) +#define c_default_hash(p) c_fasthash(p, sizeof *(p)) + #define c_option(flag) ((i_opt) & (flag)) #define c_is_fwd (1<<0) #define c_no_atomic (1<<1) #define c_no_clone (1<<2) #define c_no_cmp (1<<3) -#define c_hash (1<<4) -#define c_eq (1<<5) -#define c_static (1<<6) -#define c_header (1<<7) -#define c_implement (1<<8) +#define c_static (1<<4) +#define c_header (1<<5) +#define c_implement (1<<6) /* Generic algorithms */ typedef const char* crawstr; #define crawstr_cmp(xp, yp) strcmp(*(xp), *(yp)) #define crawstr_eq(xp, yp) (!strcmp(*(xp), *(yp))) -#define crawstr_hash(p, dummy) c_strhash(*(p)) +#define crawstr_hash(p) c_strhash(*(p)) #define _c_ROTL(x, k) (x << (k) | x >> (8*sizeof(x) - (k))) -STC_INLINE uint64_t c_default_hash(const void* key, size_t len) { +STC_INLINE uint64_t c_fasthash(const void* key, size_t len) { uint64_t u8, h = 1; size_t n = len >> 3; uint32_t u4; const uint8_t *x = (const uint8_t*) key; @@ -127,8 +127,8 @@ STC_INLINE uint64_t c_default_hash(const void* key, size_t len) { return _c_ROTL(h, 26) ^ h; } -STC_INLINE uint64_t c_strhash(const char *s) - { return c_default_hash(s, strlen(s)); } +STC_INLINE uint64_t c_strhash(const char *str) + { return c_fasthash(str, strlen(str)); } STC_INLINE char* c_strnstrn(const char *s, const char *needle, size_t slen, const size_t nlen) { if (!nlen) return (char *)s; diff --git a/include/stc/cmap.h b/include/stc/cmap.h index 978d624a..25356e16 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -294,7 +294,7 @@ STC_DEF void _cx_memb(_clear)(_cx_self* self) { STC_DEF chash_bucket_t _cx_memb(_bucket_)(const _cx_self* self, const _cx_rawkey* rkeyptr) { - const uint64_t _hash = i_hash(rkeyptr, (sizeof *rkeyptr)); + const uint64_t _hash = i_hash(rkeyptr); uint8_t _hx; _cx_size _cap = self->bucket_count; chash_bucket_t b = {c_paste(fastrange_,i_size)(_hash, _cap), (uint8_t)(_hash | 0x80)}; const uint8_t* _hashx = self->_hashx; @@ -380,7 +380,7 @@ _cx_memb(_erase_entry)(_cx_self* self, _cx_value* _val) { if (! _hashx[j]) break; _cx_rawkey _raw = i_keyto(_i_keyref(_slot + j)); - k = c_paste(fastrange_,i_size)(i_hash((&_raw), (sizeof _raw)), _cap); + k = c_paste(fastrange_,i_size)(i_hash((&_raw)), _cap); if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ _slot[i] = _slot[j], _hashx[i] = _hashx[j], i = j; } diff --git a/include/stc/cstr.h b/include/stc/cstr.h index b669b6d5..b48a9151 100644 --- a/include/stc/cstr.h +++ b/include/stc/cstr.h @@ -262,9 +262,9 @@ STC_INLINE void cstr_insert_s(cstr* self, size_t pos, cstr s) { STC_INLINE bool cstr_getline(cstr *self, FILE *fp) { return cstr_getdelim(self, '\n', fp); } -STC_INLINE uint64_t cstr_hash(const cstr *self, size_t dummylen) { +STC_INLINE uint64_t cstr_hash(const cstr *self) { csview sv = cstr_sv(self); - return c_default_hash(sv.str, sv.size); + return c_fasthash(sv.str, sv.size); } /* -------------------------- IMPLEMENTATION ------------------------- */ diff --git a/include/stc/csview.h b/include/stc/csview.h index be430a79..dd8559b5 100644 --- a/include/stc/csview.h +++ b/include/stc/csview.h @@ -128,8 +128,8 @@ STC_INLINE int csview_cmp(const csview* x, const csview* y) STC_INLINE bool csview_eq(const csview* x, const csview* y) { return x->size == y->size && !memcmp(x->str, y->str, x->size); } -STC_INLINE uint64_t csview_hash(const csview *self, size_t sz) - { return c_default_hash(self->str, self->size); } +STC_INLINE uint64_t csview_hash(const csview *self) + { return c_fasthash(self->str, self->size); } /* -------------------------- IMPLEMENTATION ------------------------- */ #if defined(_i_implement) -- cgit v1.2.3