summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--README.md6
-rw-r--r--docs/cmap_api.md14
-rw-r--r--docs/cset_api.md10
-rw-r--r--docs/csmap_api.md12
-rw-r--r--docs/csset_api.md8
-rw-r--r--include/stc/cmap.h22
-rw-r--r--include/stc/csmap.h64
-rw-r--r--include/stc/forward.h10
-rw-r--r--include/stc/priv/template.h6
-rw-r--r--misc/benchmarks/external/ankerl/robin_hood.h2
-rw-r--r--misc/benchmarks/external/ankerl/unordered_dense.h87
-rw-r--r--misc/benchmarks/external/emhash/hash_table7.hpp27
-rw-r--r--misc/benchmarks/shootout_hashmaps.cpp1
13 files changed, 172 insertions, 97 deletions
diff --git a/README.md b/README.md
index e67ab453..311763e1 100644
--- a/README.md
+++ b/README.md
@@ -320,8 +320,10 @@ You may also cherry-pick shared linking mode on individual containers by `#defin
`#define i_implement`, or force static symbols by `#define i_static` before container includes.
As a special case, there may be non-templated functions in templated containers that should be implemented only
-once if needed. Currently, for **clist**, define `i_extern` before including `clist.h` for sorting functionality
-(global `STC_EXTERN` may alternatively be defined).
+once and if needed. Currently, define `i_extern` before including **clist** for its sorting function, and before
+**cregex** or **utf8** to implement them (global `STC_EXTERN` can alternatively be defined).
+
+It is possible to generate single headers by executing the python script in src/singleheader.py <header>.
Conveniently, `src\libstc.c` implements non-templated functions as shared symbols for **cstr**, **csview**,
**cbits** and **crandom**. When building in shared mode (-DSTC_HEADER), you may include this file in your project,
diff --git a/docs/cmap_api.md b/docs/cmap_api.md
index 2c6274ae..76fbda92 100644
--- a/docs/cmap_api.md
+++ b/docs/cmap_api.md
@@ -38,7 +38,7 @@ See the c++ class [std::unordered_map](https://en.cppreference.com/w/cpp/contain
#define i_tag // alternative typename: cmap_{i_tag}. i_tag defaults to i_val
#define i_hash_functor // advanced, see examples/functor.c for similar usage.
#define i_eq_functor // advanced, see examples/functor.c for similar usage.
-#define i_size // define cmap_X_sizet. default int32_t. If defined, table expand 2x (else 1.5x)
+#define i_ssize // default int32_t. If defined, table expand 2x (else 1.5x)
#include <stc/cmap.h>
```
`X` should be replaced by the value of `i_tag` in all of the following documentation.
@@ -47,20 +47,20 @@ See the c++ class [std::unordered_map](https://en.cppreference.com/w/cpp/contain
```c
cmap_X cmap_X_init(void);
-cmap_X cmap_X_with_capacity(cmap_X_sizet cap);
+cmap_X cmap_X_with_capacity(i_ssize cap);
cmap_X cmap_X_clone(cmap_x map);
void cmap_X_clear(cmap_X* self);
void cmap_X_copy(cmap_X* self, const cmap_X* other);
float cmap_X_max_load_factor(const cmap_X* self); // default: 0.85f
-bool cmap_X_reserve(cmap_X* self, cmap_X_sizet size);
+bool cmap_X_reserve(cmap_X* self, i_ssize size);
void cmap_X_shrink_to_fit(cmap_X* self);
void cmap_X_drop(cmap_X* self); // destructor
bool cmap_X_empty(const cmap_X* self );
-cmap_X_sizet cmap_X_size(const cmap_X* self);
-cmap_X_sizet cmap_X_capacity(const cmap_X* self); // buckets * max_load_factor
-cmap_X_sizet cmap_X_bucket_count(const cmap_X* self); // num. of allocated buckets
+i_ssize cmap_X_size(const cmap_X* self);
+i_ssize cmap_X_capacity(const cmap_X* self); // buckets * max_load_factor
+i_ssize cmap_X_bucket_count(const cmap_X* self); // num. of allocated buckets
const cmap_X_mapped* cmap_X_at(const cmap_X* self, i_keyraw rkey); // rkey must be in map
cmap_X_mapped* cmap_X_at_mut(cmap_X* self, i_keyraw rkey); // mutable at
@@ -83,7 +83,7 @@ void cmap_X_erase_entry(cmap_X* self, cmap_X_value* entry);
cmap_X_iter cmap_X_begin(const cmap_X* self);
cmap_X_iter cmap_X_end(const cmap_X* self);
void cmap_X_next(cmap_X_iter* it);
-cmap_X_iter cmap_X_advance(cmap_X_iter it, cmap_X_sizet n);
+cmap_X_iter cmap_X_advance(cmap_X_iter it, cmap_X_ssize n);
cmap_X_value cmap_X_value_clone(cmap_X_value val);
cmap_X_raw cmap_X_value_toraw(cmap_X_value* pval);
diff --git a/docs/cset_api.md b/docs/cset_api.md
index 27e633b4..34b6f3eb 100644
--- a/docs/cset_api.md
+++ b/docs/cset_api.md
@@ -21,7 +21,7 @@ A **cset** is an associative container that contains a set of unique objects of
#define i_tag // alternative typename: cmap_{i_tag}. i_tag defaults to i_val
#define i_hash_functor // advanced, see examples/functor.c for similar usage.
#define i_eq_functor // advanced, see examples/functor.c for similar usage.
-#define i_size // defines cset_X_sizet. default int32_t. If defined, table expand 2x (else 1.5x)
+#define i_ssize // default int32_t. If defined, table expand 2x (else 1.5x)
#include <stc/cset.h>
```
`X` should be replaced by the value of `i_tag` in all of the following documentation.
@@ -36,14 +36,14 @@ cset_X cset_X_clone(cset_x set);
void cset_X_clear(cset_X* self);
void cset_X_copy(cset_X* self, const cset_X* other);
float cset_X_max_load_factor(const cset_X* self); // default: 0.85
-bool cset_X_reserve(cset_X* self, cset_X_sizet size);
+bool cset_X_reserve(cset_X* self, i_ssize size);
void cset_X_shrink_to_fit(cset_X* self);
void cset_X_drop(cset_X* self); // destructor
-cset_X_sizet cset_X_size(const cset_X* self); // num. of allocated buckets
-cset_X_sizet cset_X_capacity(const cset_X* self); // buckets * max_load_factor
+i_ssize cset_X_size(const cset_X* self); // num. of allocated buckets
+i_ssize cset_X_capacity(const cset_X* self); // buckets * max_load_factor
bool cset_X_empty(const cset_X* self);
-cset_X_sizet cset_X_bucket_count(const cset_X* self);
+i_ssize cset_X_bucket_count(const cset_X* self);
bool cset_X_contains(const cset_X* self, i_keyraw rkey);
const cset_X_value* cset_X_get(const cset_X* self, i_keyraw rkey); // return NULL if not found
diff --git a/docs/csmap_api.md b/docs/csmap_api.md
index 59185081..19a654d6 100644
--- a/docs/csmap_api.md
+++ b/docs/csmap_api.md
@@ -34,7 +34,7 @@ See the c++ class [std::map](https://en.cppreference.com/w/cpp/container/map) fo
#define i_tag // alternative typename: csmap_{i_tag}. i_tag defaults to i_val
#define i_cmp_functor // advanced, see examples/functor.c for similar usage.
-#define i_size // defines csmap_X_sizet type; defaults to int32_t
+#define i_ssize // defaults to int32_t
#include <stc/csmap.h>
```
`X` should be replaced by the value of `i_tag` in all of the following documentation.
@@ -43,8 +43,8 @@ See the c++ class [std::map](https://en.cppreference.com/w/cpp/container/map) fo
```c
csmap_X csmap_X_init(void);
-csset_X csmap_X_with_capacity(csmap_X_sizet cap);
-bool csmap_X_reserve(csmap_X* self, csmap_X_sizet cap);
+csset_X csmap_X_with_capacity(i_ssize cap);
+bool csmap_X_reserve(csmap_X* self, i_ssize cap);
void csmap_X_shrink_to_fit(csmap_X* self);
csmap_X csmap_X_clone(csmap_x map);
@@ -53,8 +53,8 @@ void csmap_X_copy(csmap_X* self, const csmap_X* other);
void csmap_X_drop(csmap_X* self); // destructor
bool csmap_X_empty(const csmap_X* self);
-csmap_X_sizet csmap_X_size(const csmap_X* self);
-csmap_X_sizet csmap_X_capacity(const csmap_X* self);
+i_ssize csmap_X_size(const csmap_X* self);
+i_ssize csmap_X_capacity(const csmap_X* self);
const csmap_X_mapped* csmap_X_at(const csmap_X* self, i_keyraw rkey); // rkey must be in map
csmap_X_mapped* csmap_X_at_mut(csmap_X* self, i_keyraw rkey); // mutable at
@@ -82,7 +82,7 @@ csmap_X_iter csmap_X_erase_range(csmap_X* self, csmap_X_iter it1, csmap
csmap_X_iter csmap_X_begin(const csmap_X* self);
csmap_X_iter csmap_X_end(const csmap_X* self);
void csmap_X_next(csmap_X_iter* iter);
-csmap_X_iter csmap_X_advance(csmap_X_iter it, csmap_X_sizet n);
+csmap_X_iter csmap_X_advance(csmap_X_iter it, i_ssize n);
csmap_X_value csmap_X_value_clone(csmap_X_value val);
csmap_X_raw csmap_X_value_toraw(csmap_X_value* pval);
diff --git a/docs/csset_api.md b/docs/csset_api.md
index 4618bd18..c696eab5 100644
--- a/docs/csset_api.md
+++ b/docs/csset_api.md
@@ -20,7 +20,7 @@ See the c++ class [std::set](https://en.cppreference.com/w/cpp/container/set) fo
#define i_cmp_functor // advanced, see examples/functor.c for similar usage.
#define i_tag // alternative typename: csset_{i_tag}. i_tag defaults to i_val
-#define i_size // defines csset_X_sizet type; defaults to int32_t
+#define i_ssize // defaults to int32_t
#include <stc/csset.h>
```
`X` should be replaced by the value of `i_tag` in all of the following documentation.
@@ -29,8 +29,8 @@ See the c++ class [std::set](https://en.cppreference.com/w/cpp/container/set) fo
```c
csset_X csset_X_init(void);
-csset_X csset_X_with_capacity(csset_X_sizet cap);
-bool csset_X_reserve(csset_X* self, csset_X_sizet cap);
+csset_X csset_X_with_capacity(i_ssize cap);
+bool csset_X_reserve(csset_X* self, i_ssize cap);
void csset_X_shrink_to_fit(csset_X* self);
csset_X csset_X_clone(csset_x set);
@@ -38,7 +38,7 @@ void csset_X_clear(csset_X* self);
void csset_X_copy(csset_X* self, const csset_X* other);
void csset_X_drop(csset_X* self); // destructor
-csset_X_sizet csset_X_size(const csset_X* self);
+i_ssize csset_X_size(const csset_X* self);
bool csset_X_empty(const csset_X* self);
const csset_X_value* csset_X_get(const csset_X* self, i_keyraw rkey); // const get
diff --git a/include/stc/cmap.h b/include/stc/cmap.h
index 0553823b..799df1ec 100644
--- a/include/stc/cmap.h
+++ b/include/stc/cmap.h
@@ -73,8 +73,8 @@ typedef struct { int64_t idx; uint8_t hx; } chash_bucket_t;
#ifndef i_max_load_factor
#define i_max_load_factor 0.85f
#endif
-#ifndef i_size
- #define i_size int32_t
+#ifndef i_ssize
+ #define i_ssize int32_t
#define _i_expandby 1
#else
#define _i_expandby 2
@@ -87,7 +87,7 @@ typedef struct { int64_t idx; uint8_t hx; } chash_bucket_t;
#define i_eq_functor(self, x, y) i_eq(x, y)
#endif
#if !c_option(c_is_forward)
- _cx_deftypes(_c_chash_types, _cx_self, i_key, i_val, i_size, _i_MAP_ONLY, _i_SET_ONLY);
+ _cx_deftypes(_c_chash_types, _cx_self, i_key, i_val, i_ssize, _i_MAP_ONLY, _i_SET_ONLY);
#endif
_i_MAP_ONLY( struct _cx_value {
@@ -378,7 +378,7 @@ _cx_memb(_bucket_)(const _cx_self* self, const _cx_rawkey* rkeyptr) {
STC_DEF _cx_result
_cx_memb(_insert_entry_)(_cx_self* self, _cx_rawkey rkey) {
_cx_result res = {NULL};
- if (self->size + 2 > (i_size)((float)self->bucket_count * (i_max_load_factor)))
+ if (self->size + 2 > (i_ssize)((float)self->bucket_count * (i_max_load_factor)))
if (!_cx_memb(_reserve)(self, self->size*3/2))
return res;
@@ -412,12 +412,12 @@ _cx_memb(_clone)(_cx_self m) {
STC_DEF bool
_cx_memb(_reserve)(_cx_self* self, const int64_t newcap) {
- const i_size _oldbuckets = self->bucket_count, _newcap = (i_size)newcap;
+ const i_ssize _oldbuckets = self->bucket_count, _newcap = (i_ssize)newcap;
if (_newcap != self->size && _newcap <= _oldbuckets)
return true;
- i_size _nbuckets = (i_size)((float)_newcap / (i_max_load_factor)) + 4;
+ i_ssize _nbuckets = (i_ssize)((float)_newcap / (i_max_load_factor)) + 4;
#if _i_expandby == 2
- _nbuckets = (i_size)next_power_of_2(_nbuckets);
+ _nbuckets = (i_ssize)next_power_of_2(_nbuckets);
#else
_nbuckets |= 1;
#endif
@@ -431,7 +431,7 @@ _cx_memb(_reserve)(_cx_self* self, const int64_t newcap) {
m._hashx[_nbuckets] = 0xff;
const _cx_value* e = self->table;
const uint8_t* h = self->_hashx;
- for (i_size i = 0; i < _oldbuckets; ++i, ++e) if (*h++) {
+ for (i_ssize i = 0; i < _oldbuckets; ++i, ++e) if (*h++) {
_cx_rawkey r = i_keyto(_i_keyref(e));
chash_bucket_t b = _cx_memb(_bucket_)(&m, &r);
m.table[b.idx] = *e;
@@ -446,8 +446,8 @@ _cx_memb(_reserve)(_cx_self* self, const int64_t newcap) {
STC_DEF void
_cx_memb(_erase_entry)(_cx_self* self, _cx_value* _val) {
- i_size i = (i_size)(_val - self->table), j = i, k;
- const i_size _cap = self->bucket_count;
+ i_ssize i = (i_ssize)(_val - self->table), j = i, k;
+ const i_ssize _cap = self->bucket_count;
_cx_value* _slot = self->table;
uint8_t* _hashx = self->_hashx;
_cx_memb(_value_drop)(_val);
@@ -457,7 +457,7 @@ _cx_memb(_erase_entry)(_cx_self* self, _cx_value* _val) {
if (! _hashx[j])
break;
const _cx_rawkey _raw = i_keyto(_i_keyref(_slot + j));
- k = (i_size)c_PASTE(fastrange_,_i_expandby)(i_hash_functor(self, (&_raw)), (uint64_t)_cap);
+ k = (i_ssize)c_PASTE(fastrange_,_i_expandby)(i_hash_functor(self, (&_raw)), (uint64_t)_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/csmap.h b/include/stc/csmap.h
index 6a359fbb..4344ceb9 100644
--- a/include/stc/csmap.h
+++ b/include/stc/csmap.h
@@ -73,15 +73,15 @@ int main(void) {
#define _i_SET_ONLY c_false
#define _i_keyref(vp) (&(vp)->first)
#endif
-#ifndef i_size
- #define i_size int32_t
+#ifndef i_ssize
+ #define i_ssize int32_t
#endif
#include "priv/template.h"
#ifndef i_cmp_functor
#define i_cmp_functor(self, x, y) i_cmp(x, y)
#endif
#if !c_option(c_is_forward)
- _cx_deftypes(_c_aatree_types, _cx_self, i_key, i_val, i_size, _i_MAP_ONLY, _i_SET_ONLY);
+ _cx_deftypes(_c_aatree_types, _cx_self, i_key, i_val, i_ssize, _i_MAP_ONLY, _i_SET_ONLY);
#endif
_i_MAP_ONLY( struct _cx_value {
@@ -89,7 +89,7 @@ _i_MAP_ONLY( struct _cx_value {
_cx_mapped second;
}; )
struct _cx_node {
- i_size link[2];
+ i_ssize link[2];
int8_t level;
_cx_value value;
};
@@ -229,21 +229,21 @@ _cx_memb(_init)(void) {
STC_DEF bool
_cx_memb(_reserve)(_cx_self* self, const int64_t cap) {
- if ((i_size)cap <= self->cap)
+ if ((i_ssize)cap <= self->cap)
return false;
_cx_node* nodes = (_cx_node*)i_realloc(self->nodes, (cap + 1)*c_sizeof(_cx_node));
if (!nodes)
return false;
nodes[0] = c_LITERAL(_cx_node){{0, 0}, 0};
self->nodes = nodes;
- self->cap = (i_size)cap;
+ self->cap = (i_ssize)cap;
return true;
}
STC_DEF _cx_value*
_cx_memb(_front)(const _cx_self* self) {
_cx_node *d = self->nodes;
- i_size tn = self->root;
+ i_ssize tn = self->root;
while (d[tn].link[0])
tn = d[tn].link[0];
return &d[tn].value;
@@ -252,15 +252,15 @@ _cx_memb(_front)(const _cx_self* self) {
STC_DEF _cx_value*
_cx_memb(_back)(const _cx_self* self) {
_cx_node *d = self->nodes;
- i_size tn = self->root;
+ i_ssize tn = self->root;
while (d[tn].link[1])
tn = d[tn].link[1];
return &d[tn].value;
}
-static i_size
+static i_ssize
_cx_memb(_new_node_)(_cx_self* self, int level) {
- i_size tn;
+ i_ssize tn;
if (self->disp) {
tn = self->disp;
self->disp = self->nodes[tn].link[1];
@@ -344,7 +344,7 @@ STC_INLINE _cx_self _cx_memb(_from_n)(const _cx_raw* raw, int64_t n)
STC_DEF _cx_value*
_cx_memb(_find_it)(const _cx_self* self, _cx_rawkey rkey, _cx_iter* out) {
- i_size tn = self->root;
+ i_ssize tn = self->root;
_cx_node *d = out->_d = self->nodes;
out->_top = 0;
while (tn) {
@@ -364,7 +364,7 @@ _cx_memb(_lower_bound)(const _cx_self* self, _cx_rawkey rkey) {
_cx_iter it;
_cx_memb(_find_it)(self, rkey, &it);
if (!it.ref && it._top) {
- i_size tn = it._st[--it._top];
+ i_ssize tn = it._st[--it._top];
it._tn = it._d[tn].link[1];
it.ref = &it._d[tn].value;
}
@@ -373,7 +373,7 @@ _cx_memb(_lower_bound)(const _cx_self* self, _cx_rawkey rkey) {
STC_DEF void
_cx_memb(_next)(_cx_iter *it) {
- i_size tn = it->_tn;
+ i_ssize tn = it->_tn;
if (it->_top || tn) {
while (tn) {
it->_st[it->_top++] = tn;
@@ -386,10 +386,10 @@ _cx_memb(_next)(_cx_iter *it) {
it->ref = NULL;
}
-STC_DEF i_size
-_cx_memb(_skew_)(_cx_node *d, i_size tn) {
+STC_DEF i_ssize
+_cx_memb(_skew_)(_cx_node *d, i_ssize tn) {
if (tn && d[d[tn].link[0]].level == d[tn].level) {
- i_size tmp = d[tn].link[0];
+ i_ssize tmp = d[tn].link[0];
d[tn].link[0] = d[tmp].link[1];
d[tmp].link[1] = tn;
tn = tmp;
@@ -397,10 +397,10 @@ _cx_memb(_skew_)(_cx_node *d, i_size tn) {
return tn;
}
-STC_DEF i_size
-_cx_memb(_split_)(_cx_node *d, i_size tn) {
+STC_DEF i_ssize
+_cx_memb(_split_)(_cx_node *d, i_ssize tn) {
if (d[d[d[tn].link[1]].link[1]].level == d[tn].level) {
- i_size tmp = d[tn].link[1];
+ i_ssize tmp = d[tn].link[1];
d[tn].link[1] = d[tmp].link[0];
d[tmp].link[0] = tn;
tn = tmp;
@@ -409,9 +409,9 @@ _cx_memb(_split_)(_cx_node *d, i_size tn) {
return tn;
}
-static i_size
-_cx_memb(_insert_entry_i_)(_cx_self* self, i_size tn, const _cx_rawkey* rkey, _cx_result* _res) {
- i_size up[64], tx = tn;
+static i_ssize
+_cx_memb(_insert_entry_i_)(_cx_self* self, i_ssize tn, const _cx_rawkey* rkey, _cx_result* _res) {
+ i_ssize up[64], tx = tn;
_cx_node* d = self->nodes;
int c, top = 0, dir = 0;
while (tx) {
@@ -444,19 +444,19 @@ _cx_memb(_insert_entry_i_)(_cx_self* self, i_size tn, const _cx_rawkey* rkey, _c
static _cx_result
_cx_memb(_insert_entry_)(_cx_self* self, _cx_rawkey rkey) {
_cx_result res = {NULL};
- i_size tn = _cx_memb(_insert_entry_i_)(self, self->root, &rkey, &res);
+ i_ssize tn = _cx_memb(_insert_entry_i_)(self, self->root, &rkey, &res);
self->root = tn;
self->size += res.inserted;
return res;
}
-static i_size
-_cx_memb(_erase_r_)(_cx_self *self, i_size tn, const _cx_rawkey* rkey, int *erased) {
+static i_ssize
+_cx_memb(_erase_r_)(_cx_self *self, i_ssize tn, const _cx_rawkey* rkey, int *erased) {
_cx_node *d = self->nodes;
if (tn == 0)
return 0;
_cx_rawkey raw = i_keyto(_i_keyref(&d[tn].value));
- i_size tx; int c = i_cmp_functor(self, (&raw), rkey);
+ i_ssize tx; int c = i_cmp_functor(self, (&raw), rkey);
if (c != 0)
d[tn].link[c < 0] = _cx_memb(_erase_r_)(self, d[tn].link[c < 0], rkey, erased);
else {
@@ -493,7 +493,7 @@ _cx_memb(_erase_r_)(_cx_self *self, i_size tn, const _cx_rawkey* rkey, int *eras
STC_DEF int
_cx_memb(_erase)(_cx_self* self, _cx_rawkey rkey) {
int erased = 0;
- i_size root = _cx_memb(_erase_r_)(self, self->root, &rkey, &erased);
+ i_ssize root = _cx_memb(_erase_r_)(self, self->root, &rkey, &erased);
if (!erased)
return 0;
self->root = root;
@@ -535,11 +535,11 @@ _cx_memb(_erase_range)(_cx_self* self, _cx_iter it1, _cx_iter it2) {
}
#if !defined i_no_clone
-static i_size
-_cx_memb(_clone_r_)(_cx_self* self, _cx_node* src, i_size sn) {
+static i_ssize
+_cx_memb(_clone_r_)(_cx_self* self, _cx_node* src, i_ssize sn) {
if (sn == 0)
return 0;
- i_size tx, tn = _cx_memb(_new_node_)(self, src[sn].level);
+ i_ssize tx, tn = _cx_memb(_new_node_)(self, src[sn].level);
self->nodes[tn].value = _cx_memb(_value_clone)(src[sn].value);
tx = _cx_memb(_clone_r_)(self, src, src[sn].link[0]); self->nodes[tn].link[0] = tx;
tx = _cx_memb(_clone_r_)(self, src, src[sn].link[1]); self->nodes[tn].link[1] = tx;
@@ -549,7 +549,7 @@ _cx_memb(_clone_r_)(_cx_self* self, _cx_node* src, i_size sn) {
STC_DEF _cx_self
_cx_memb(_clone)(_cx_self tree) {
_cx_self clone = _cx_memb(_with_capacity)(tree.size);
- i_size root = _cx_memb(_clone_r_)(&clone, tree.nodes, tree.root);
+ i_ssize root = _cx_memb(_clone_r_)(&clone, tree.nodes, tree.root);
clone.root = root;
clone.size = tree.size;
return clone;
@@ -569,7 +569,7 @@ _cx_memb(_emplace)(_cx_self* self, _cx_rawkey rkey _i_MAP_ONLY(, i_valraw rmappe
#endif // i_no_emplace
static void
-_cx_memb(_drop_r_)(_cx_node* d, i_size tn) {
+_cx_memb(_drop_r_)(_cx_node* d, i_ssize tn) {
if (tn) {
_cx_memb(_drop_r_)(d, d[tn].link[0]);
_cx_memb(_drop_r_)(d, d[tn].link[1]);
diff --git a/include/stc/forward.h b/include/stc/forward.h
index 64d4370a..00c531fe 100644
--- a/include/stc/forward.h
+++ b/include/stc/forward.h
@@ -106,7 +106,7 @@ typedef union {
#define _c_chash_types(SELF, KEY, VAL, SZ, MAP_ONLY, SET_ONLY) \
typedef KEY SELF##_key; \
typedef VAL SELF##_mapped; \
- typedef SZ SELF##_sizet; \
+ typedef SZ SELF##_ssize; \
\
typedef SET_ONLY( SELF##_key ) \
MAP_ONLY( struct SELF##_value ) \
@@ -125,13 +125,13 @@ typedef union {
typedef struct SELF { \
SELF##_value* table; \
uint8_t* _hashx; \
- SELF##_sizet size, bucket_count; \
+ SELF##_ssize size, bucket_count; \
} SELF
#define _c_aatree_types(SELF, KEY, VAL, SZ, MAP_ONLY, SET_ONLY) \
typedef KEY SELF##_key; \
typedef VAL SELF##_mapped; \
- typedef SZ SELF##_sizet; \
+ typedef SZ SELF##_ssize; \
typedef struct SELF##_node SELF##_node; \
\
typedef SET_ONLY( SELF##_key ) \
@@ -147,12 +147,12 @@ typedef union {
SELF##_value *ref; \
SELF##_node *_d; \
int _top; \
- SELF##_sizet _tn, _st[36]; \
+ SELF##_ssize _tn, _st[36]; \
} SELF##_iter; \
\
typedef struct SELF { \
SELF##_node *nodes; \
- SELF##_sizet root, disp, head, size, cap; \
+ SELF##_ssize root, disp, head, size, cap; \
} SELF
#define _c_cstack_fixed(SELF, VAL, CAP) \
diff --git a/include/stc/priv/template.h b/include/stc/priv/template.h
index dd770839..3bef2c9a 100644
--- a/include/stc/priv/template.h
+++ b/include/stc/priv/template.h
@@ -44,8 +44,8 @@
#define _i_prefix
#endif
-#ifndef i_size
- #define i_size intptr_t
+#ifndef i_ssize
+ #define i_ssize intptr_t
#endif
#ifndef i_allocator
@@ -298,7 +298,7 @@
#undef i_hash
#undef i_rawclass
#undef i_capacity
-#undef i_size
+#undef i_ssize
#undef i_val
#undef i_val_str
diff --git a/misc/benchmarks/external/ankerl/robin_hood.h b/misc/benchmarks/external/ankerl/robin_hood.h
index 0af031f5..b4e0fbc5 100644
--- a/misc/benchmarks/external/ankerl/robin_hood.h
+++ b/misc/benchmarks/external/ankerl/robin_hood.h
@@ -206,7 +206,7 @@ static Counts& counts() {
// workaround missing "is_trivially_copyable" in g++ < 5.0
// See https://stackoverflow.com/a/31798726/48181
-#if defined(__GNUC__) && __GNUC__ < 5
+#if defined(__GNUC__) && __GNUC__ < 5 && !defined(__clang__)
# define ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(...) __has_trivial_copy(__VA_ARGS__)
#else
# define ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(...) std::is_trivially_copyable<__VA_ARGS__>::value
diff --git a/misc/benchmarks/external/ankerl/unordered_dense.h b/misc/benchmarks/external/ankerl/unordered_dense.h
index 05c7e928..faad051d 100644
--- a/misc/benchmarks/external/ankerl/unordered_dense.h
+++ b/misc/benchmarks/external/ankerl/unordered_dense.h
@@ -1,12 +1,12 @@
///////////////////////// ankerl::unordered_dense::{map, set} /////////////////////////
// A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion.
-// Version 3.0.0
+// Version 3.1.0
// https://github.com/martinus/unordered_dense
//
// Licensed under the MIT License <http://opensource.org/licenses/MIT>.
// SPDX-License-Identifier: MIT
-// Copyright (c) 2022 Martin Leitner-Ankerl <[email protected]>
+// Copyright (c) 2022-2023 Martin Leitner-Ankerl <[email protected]>
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
@@ -31,7 +31,7 @@
// see https://semver.org/spec/v2.0.0.html
#define ANKERL_UNORDERED_DENSE_VERSION_MAJOR 3 // NOLINT(cppcoreguidelines-macro-usage) incompatible API changes
-#define ANKERL_UNORDERED_DENSE_VERSION_MINOR 0 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible functionality
+#define ANKERL_UNORDERED_DENSE_VERSION_MINOR 1 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible functionality
#define ANKERL_UNORDERED_DENSE_VERSION_PATCH 0 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible bug fixes
// API versioning with inline namespace, see https://www.foonathan.net/2018/11/inline-namespaces/
@@ -55,6 +55,18 @@
# define ANKERL_UNORDERED_DENSE_PACK(decl) __pragma(pack(push, 1)) decl __pragma(pack(pop))
#endif
+// exceptions
+#if defined(__cpp_exceptions) || defined(__EXCEPTIONS) || defined(_CPPUNWIND)
+# define ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() 1
+#else
+# define ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() 0
+#endif
+#ifdef _MSC_VER
+# define ANKERL_UNORDERED_DENSE_NOINLINE __declspec(noinline)
+#else
+# define ANKERL_UNORDERED_DENSE_NOINLINE __attribute__((noinline))
+#endif
+
#if ANKERL_UNORDERED_DENSE_CPP_VERSION < 201703L
# error ankerl::unordered_dense requires C++17 or higher
#else
@@ -73,13 +85,24 @@
# include <type_traits> // for enable_if_t, declval, conditional_t, ena...
# include <utility> // for forward, exchange, pair, as_const, piece...
# include <vector> // for vector
+# if ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() == 0
+# include <cstdlib> // for abort
+# endif
# define ANKERL_UNORDERED_DENSE_PMR 0 // NOLINT(cppcoreguidelines-macro-usage)
# if defined(__has_include)
# if __has_include(<memory_resource>)
# undef ANKERL_UNORDERED_DENSE_PMR
# define ANKERL_UNORDERED_DENSE_PMR 1 // NOLINT(cppcoreguidelines-macro-usage)
-# include <memory_resource> // for polymorphic_allocator
+# define ANKERL_UNORDERED_DENSE_PMR_ALLOCATOR \
+ std::pmr::polymorphic_allocator // NOLINT(cppcoreguidelines-macro-usage)
+# include <memory_resource> // for polymorphic_allocator
+# elif __has_include(<experimental/memory_resource>)
+# undef ANKERL_UNORDERED_DENSE_PMR
+# define ANKERL_UNORDERED_DENSE_PMR 1 // NOLINT(cppcoreguidelines-macro-usage)
+# define ANKERL_UNORDERED_DENSE_PMR_ALLOCATOR \
+ std::experimental::pmr::polymorphic_allocator // NOLINT(cppcoreguidelines-macro-usage)
+# include <experimental/memory_resource> // for polymorphic_allocator
# endif
# endif
@@ -99,6 +122,38 @@
namespace ankerl::unordered_dense {
inline namespace ANKERL_UNORDERED_DENSE_NAMESPACE {
+namespace detail {
+
+# if ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS()
+
+// make sure this is not inlined as it is slow and dramatically enlarges code, thus making other
+// inlinings more difficult. Throws are also generally the slow path.
+[[noreturn]] inline ANKERL_UNORDERED_DENSE_NOINLINE void on_error_key_not_found() {
+ throw std::out_of_range("ankerl::unordered_dense::map::at(): key not found");
+}
+[[noreturn]] inline ANKERL_UNORDERED_DENSE_NOINLINE void on_error_bucket_overflow() {
+ throw std::overflow_error("ankerl::unordered_dense: reached max bucket size, cannot increase size");
+}
+[[noreturn]] inline ANKERL_UNORDERED_DENSE_NOINLINE void on_error_too_many_elements() {
+ throw std::out_of_range("ankerl::unordered_dense::map::replace(): too many elements");
+}
+
+# else
+
+[[noreturn]] inline void on_error_key_not_found() {
+ abort();
+}
+[[noreturn]] inline void on_error_bucket_overflow() {
+ abort();
+}
+[[noreturn]] inline void on_error_too_many_elements() {
+ abort();
+}
+
+# endif
+
+} // namespace detail
+
// hash ///////////////////////////////////////////////////////////////////////
// This is a stripped-down implementation of wyhash: https://github.com/wangyi-fudan/wyhash
@@ -371,8 +426,10 @@ using detect_reserve = decltype(std::declval<T&>().reserve(size_t{}));
template <typename Mapped>
constexpr bool is_map_v = !std::is_void_v<Mapped>;
+// clang-format off
template <typename Hash, typename KeyEqual>
constexpr bool is_transparent_v = is_detected_v<detect_is_transparent, Hash>&& is_detected_v<detect_is_transparent, KeyEqual>;
+// clang-format on
template <typename From, typename To1, typename To2>
constexpr bool is_neither_convertible_v = !std::is_convertible_v<From, To1> && !std::is_convertible_v<From, To2>;
@@ -590,7 +647,7 @@ private:
void increase_size() {
if (ANKERL_UNORDERED_DENSE_UNLIKELY(m_max_bucket_capacity == max_bucket_count())) {
- throw std::overflow_error("ankerl::unordered_dense: reached max bucket size, cannot increase size");
+ on_error_bucket_overflow();
}
--m_shifts;
deallocate_buckets();
@@ -745,10 +802,10 @@ private:
template <typename K, typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
auto do_at(K const& key) -> Q& {
- if (auto it = find(key); end() != it) {
+ if (auto it = find(key); ANKERL_UNORDERED_DENSE_LIKELY(end() != it)) {
return it->second;
}
- throw std::out_of_range("ankerl::unordered_dense::map::at(): key not found");
+ on_error_key_not_found();
}
template <typename K, typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
@@ -842,8 +899,10 @@ public:
: table(init, bucket_count, hash, KeyEqual(), alloc) {}
~table() {
- auto ba = bucket_alloc(m_values.get_allocator());
- bucket_alloc_traits::deallocate(ba, m_buckets, bucket_count());
+ if (nullptr != m_buckets) {
+ auto ba = bucket_alloc(m_values.get_allocator());
+ bucket_alloc_traits::deallocate(ba, m_buckets, bucket_count());
+ }
}
auto operator=(table const& other) -> table& {
@@ -985,10 +1044,9 @@ public:
// nonstandard API:
// Discards the internally held container and replaces it with the one passed. Erases non-unique elements.
auto replace(value_container_type&& container) {
- if (container.size() > max_size()) {
- throw std::out_of_range("ankerl::unordered_dense::map::replace(): too many elements");
+ if (ANKERL_UNORDERED_DENSE_UNLIKELY(container.size() > max_size())) {
+ on_error_too_many_elements();
}
-
auto shifts = calc_shifts_for_size(container.size());
if (0 == m_num_buckets || shifts < m_shifts || container.get_allocator() != m_values.get_allocator()) {
m_shifts = shifts;
@@ -1479,10 +1537,10 @@ template <class Key,
class Hash = hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Bucket = bucket_type::standard>
-using map = detail::table<Key, T, Hash, KeyEqual, std::pmr::polymorphic_allocator<std::pair<Key, T>>, Bucket>;
+using map = detail::table<Key, T, Hash, KeyEqual, ANKERL_UNORDERED_DENSE_PMR_ALLOCATOR<std::pair<Key, T>>, Bucket>;
template <class Key, class Hash = hash<Key>, class KeyEqual = std::equal_to<Key>, class Bucket = bucket_type::standard>
-using set = detail::table<Key, void, Hash, KeyEqual, std::pmr::polymorphic_allocator<Key>, Bucket>;
+using set = detail::table<Key, void, Hash, KeyEqual, ANKERL_UNORDERED_DENSE_PMR_ALLOCATOR<Key>, Bucket>;
} // namespace pmr
@@ -1501,6 +1559,7 @@ using set = detail::table<Key, void, Hash, KeyEqual, std::pmr::polymorphic_alloc
namespace std { // NOLINT(cert-dcl58-cpp)
template <class Key, class T, class Hash, class KeyEqual, class AllocatorOrContainer, class Bucket, class Pred>
+// NOLINTNEXTLINE(cert-dcl58-cpp)
auto erase_if(ankerl::unordered_dense::detail::table<Key, T, Hash, KeyEqual, AllocatorOrContainer, Bucket>& map, Pred pred)
-> size_t {
using map_t = ankerl::unordered_dense::detail::table<Key, T, Hash, KeyEqual, AllocatorOrContainer, Bucket>;
diff --git a/misc/benchmarks/external/emhash/hash_table7.hpp b/misc/benchmarks/external/emhash/hash_table7.hpp
index ced0f1d0..8f8982f9 100644
--- a/misc/benchmarks/external/emhash/hash_table7.hpp
+++ b/misc/benchmarks/external/emhash/hash_table7.hpp
@@ -1,10 +1,10 @@
// emhash7::HashMap for C++11/14/17
-// version 2.2.3
+// version 2.2.4
// https://github.com/ktprime/ktprime/blob/master/hash_table7.hpp
//
// Licensed under the MIT License <http://opensource.org/licenses/MIT>.
// SPDX-License-Identifier: MIT
-// Copyright (c) 2019-2022 Huang Yuanbing & bailuzhou AT 163.com
+// Copyright (c) 2019-2023 Huang Yuanbing & bailuzhou AT 163.com
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
@@ -166,6 +166,11 @@ namespace emhash7 {
static constexpr size_type INACTIVE = 0 - 0x1u;
#endif
+#ifndef EMH_MALIGN
+ static constexpr uint32_t EMH_MALIGN = 16;
+#endif
+static_assert(EMH_MALIGN >= 16 && 0 == (EMH_MALIGN & (EMH_MALIGN - 1)));
+
#ifndef EMH_SIZE_TYPE_16BIT
static_assert((int)INACTIVE < 0, "INACTIVE must negative (to int)");
#endif
@@ -535,15 +540,25 @@ public:
init(bucket, mlf);
}
- size_t AllocSize(uint64_t num_buckets) const
+ static size_t AllocSize(uint64_t num_buckets)
{
return (num_buckets + EPACK_SIZE) * sizeof(PairT) + (num_buckets + 7) / 8 + BIT_PACK;
}
+ static PairT* alloc_bucket(size_type num_buckets)
+ {
+#if _WIN32
+ auto* new_pairs = (PairT*)malloc(AllocSize(num_buckets));
+#else
+ auto* new_pairs = (PairT*)aligned_alloc(EMH_MALIGN, AllocSize(num_buckets));
+#endif
+ return new_pairs;
+ }
+
HashMap(const HashMap& rhs) noexcept
{
if (rhs.load_factor() > EMH_MIN_LOAD_FACTOR) {
- _pairs = (PairT*)malloc(AllocSize(rhs._num_buckets));
+ _pairs = (PairT*)alloc_bucket(rhs._num_buckets);
clone(rhs);
} else {
init(rhs._num_filled + 2, EMH_DEFAULT_LOAD_FACTOR);
@@ -596,7 +611,7 @@ public:
if (_num_buckets != rhs._num_buckets) {
free(_pairs);
- _pairs = (PairT*)malloc(AllocSize(rhs._num_buckets));
+ _pairs = alloc_bucket(rhs._num_buckets);
}
clone(rhs);
@@ -1355,7 +1370,7 @@ public:
_num_buckets = num_buckets;
_mask = num_buckets - 1;
- _pairs = (PairT*)malloc(AllocSize(_num_buckets));
+ _pairs = alloc_bucket(_num_buckets);
memset((char*)(_pairs + _num_buckets), 0, sizeof(PairT) * EPACK_SIZE);
_bitmask = decltype(_bitmask)(_pairs + EPACK_SIZE + num_buckets);
diff --git a/misc/benchmarks/shootout_hashmaps.cpp b/misc/benchmarks/shootout_hashmaps.cpp
index 78d7bce2..da523d71 100644
--- a/misc/benchmarks/shootout_hashmaps.cpp
+++ b/misc/benchmarks/shootout_hashmaps.cpp
@@ -35,7 +35,6 @@ KHASH_MAP_INIT_INT64(ii, IValue)
// cmap template expansion
#define i_key IKey
#define i_val IValue
-#define i_size uint32_t // optional, enables 2x expand
#define i_tag ii
#define i_max_load_factor MAX_LOAD_FACTOR / 100.0f
#include <stc/cmap.h>
generated by cgit v1.2.3 (git 2.39.1) at 2026-04-18 05:14:26 +0000