summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--benchmarks/shootout1_cmap.cpp10
-rw-r--r--benchmarks/shootout2_cmap.cpp2
-rw-r--r--docs/cmap_api.md3
-rw-r--r--docs/cset_api.md3
-rw-r--r--stc/cmap.h48
5 files changed, 28 insertions, 38 deletions
diff --git a/benchmarks/shootout1_cmap.cpp b/benchmarks/shootout1_cmap.cpp
index 7f75a242..d368afa8 100644
--- a/benchmarks/shootout1_cmap.cpp
+++ b/benchmarks/shootout1_cmap.cpp
@@ -70,7 +70,7 @@ static void ins_and_erase_i(picobench::state& s)
static void ins_and_erase_cmap_i(picobench::state& s)
{
cmap_i map = cmap_i_init();
- cmap_i_set_load_factors(&map, 0.0, (int)MaxLoadFactor100 / 100.0);
+ cmap_i_max_load_factor(&map, (int)MaxLoadFactor100 / 100.0);
stc64_srandom(seed);
picobench::scope scope(s);
@@ -90,7 +90,7 @@ static void ins_and_erase_cmap_i(picobench::state& s)
static void ins_and_erase_cmap_x(picobench::state& s)
{
cmap_x map = cmap_x_init();
- cmap_x_set_load_factors(&map, 0.0, (int)MaxLoadFactor100 / 100.0);
+ cmap_x_max_load_factor(&map, (int)MaxLoadFactor100 / 100.0);
stc64_srandom(seed);
picobench::scope scope(s);
@@ -140,7 +140,7 @@ static void ins_and_access_cmap_i(picobench::state& s)
uint64_t mask = (1ull << s.arg()) - 1;
size_t result = 0;
cmap_i map = cmap_i_init();
- cmap_i_set_load_factors(&map, 0.0, (int)MaxLoadFactor100 / 100.0);
+ cmap_i_max_load_factor(&map, (int)MaxLoadFactor100 / 100.0);
stc64_srandom(seed);
picobench::scope scope(s);
@@ -193,7 +193,7 @@ static void ins_and_access_cmap_s(picobench::state& s)
cstr str = cstr_with_size(s.arg(), 'x');
size_t result = 0;
cmap_str map = cmap_str_init();
- cmap_str_set_load_factors(&map, 0.0, (int)MaxLoadFactor100 / 100.0);
+ cmap_str_max_load_factor(&map, (int)MaxLoadFactor100 / 100.0);
stc64_srandom(seed);
picobench::scope scope(s);
@@ -254,7 +254,7 @@ static void iterate_x(picobench::state& s)
static void iterate_cmap_x(picobench::state& s)
{
cmap_x map = cmap_x_init();
- cmap_x_set_load_factors(&map, 0.3, (int)MaxLoadFactor100 / 100.0);
+ cmap_x_max_load_factor(&map, (int)MaxLoadFactor100 / 100.0);
uint64_t K = (1ull << s.arg()) - 1;
picobench::scope scope(s);
diff --git a/benchmarks/shootout2_cmap.cpp b/benchmarks/shootout2_cmap.cpp
index cea7b6ec..7c1595f3 100644
--- a/benchmarks/shootout2_cmap.cpp
+++ b/benchmarks/shootout2_cmap.cpp
@@ -31,7 +31,7 @@ stc64_t rng;
#define CMAP_SETUP(X, Key, Value) cmap_##X map = cmap_##X##_init() \
- ; cmap_##X##_set_load_factors(&map, 0.0, max_load_factor)
+ ; cmap_##X##_max_load_factor(&map, max_load_factor)
#define CMAP_PUT(X, key, val) cmap_##X##_emplace_or_assign(&map, key, val).ref->second
#define CMAP_EMPLACE(X, key, val) cmap_##X##_emplace(&map, key, val).ref->second
#define CMAP_ERASE(X, key) cmap_##X##_erase(&map, key)
diff --git a/docs/cmap_api.md b/docs/cmap_api.md
index 5e8d4d26..2f056479 100644
--- a/docs/cmap_api.md
+++ b/docs/cmap_api.md
@@ -51,8 +51,9 @@ cmap_X cmap_X_with_capacity(size_t cap);
cmap_X cmap_X_clone(cmap_x map);
void cmap_X_clear(cmap_X* self);
-void cmap_X_set_load_factors(cmap_X* self, float min_load, float max_load); // default: 0.15, 0.85
+void cmap_X_max_load_factor(cmap_X* self, float max_load); // default: 0.85
void cmap_X_reserve(cmap_X* self, size_t size);
+void cmap_X_shrink_to_fit(cmap_X* self);
void cmap_X_swap(cmap_X* a, cmap_X* b);
void cmap_X_del(cmap_X* self); // destructor
diff --git a/docs/cset_api.md b/docs/cset_api.md
index 848c6c63..f28c4714 100644
--- a/docs/cset_api.md
+++ b/docs/cset_api.md
@@ -28,8 +28,9 @@ cset_X cset_X_with_capacity(size_t cap);
cset_X cset_X_clone(cset_x set);
void cset_X_clear(cset_X* self);
-void cset_X_set_load_factors(cset_X* self, float min_load, float max_load); // default: 0.15, 0.85
+void cset_X_max_load_factor(cset_X* self, float max_load); // default: 0.85
void cset_X_reserve(cset_X* self, size_t size);
+void cset_X_shrink_to_fit(cset_X* self);
void cset_X_swap(cset_X* a, cset_X* b);
void cset_X_del(cset_X* self); // destructor
diff --git a/stc/cmap.h b/stc/cmap.h
index 45d5790e..9baefe83 100644
--- a/stc/cmap.h
+++ b/stc/cmap.h
@@ -134,7 +134,7 @@ int main(void) {
#ifndef CMAP_SIZE_T
#define CMAP_SIZE_T uint32_t
#endif
-#define _cmap_inits {NULL, NULL, 0, 0, 0.15f, 0.85f}
+#define _cmap_inits {NULL, NULL, 0, 0, 0.85f}
typedef struct {size_t idx; uint_fast8_t hx;} chash_bucket_t; \
STC_API uint64_t c_default_hash(const void *data, size_t len);
@@ -172,7 +172,6 @@ STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored)
CX##_value_t* table; \
uint8_t* _hashx; \
CX##_size_t size, bucket_count; \
- float min_load_factor; \
float max_load_factor; \
} CX; \
\
@@ -188,19 +187,20 @@ STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored)
STC_API CX CX##_with_capacity(size_t cap); \
STC_API CX CX##_clone(CX map); \
STC_API void CX##_reserve(CX* self, size_t capacity); \
+ STC_INLINE void CX##_shrink_to_fit(CX* self) {CX##_reserve(self, self->size);} \
+ STC_INLINE void CX##_max_load_factor(CX* self, float ml) {self->max_load_factor = ml;} \
STC_API void CX##_del(CX* self); \
STC_API void CX##_clear(CX* self); \
STC_INLINE bool CX##_empty(CX m) {return m.size == 0;} \
STC_INLINE size_t CX##_size(CX m) {return (size_t) m.size;} \
STC_INLINE size_t CX##_bucket_count(CX map) {return (size_t) map.bucket_count;} \
STC_INLINE size_t CX##_capacity(CX map) \
- {return (size_t) (map.bucket_count*map.max_load_factor);} \
+ {return (size_t) (map.bucket_count * map.max_load_factor);} \
STC_INLINE void CX##_swap(CX *map1, CX *map2) {c_swap(CX, *map1, *map2);} \
STC_API CX##_iter_t CX##_find(const CX* self, RawKey rkey); \
STC_INLINE bool CX##_contains(const CX* self, RawKey rkey) \
{return self->size && self->_hashx[CX##_bucket_(self, &rkey).idx];} \
STC_API void CX##_erase_entry(CX* self, CX##_value_t* val); \
- STC_API CX##_iter_t CX##_erase_it(CX* self, CX##_iter_t it); \
\
STC_INLINE CX##_value_t \
CX##_value_clone(CX##_value_t val) { \
@@ -215,12 +215,6 @@ STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored)
MAP_ONLY_##C( mappedDel(&val->second); ) \
} \
\
- STC_INLINE void \
- CX##_set_load_factors(CX* self, float min_load, float max_load) { \
- self->min_load_factor = min_load; \
- self->max_load_factor = max_load; \
- } \
- \
STC_INLINE CX##_result_t \
CX##_emplace(CX* self, RawKey rkey MAP_ONLY_##C(, RawMapped rmapped)) { \
CX##_result_t res = CX##_insert_entry_(self, rkey); \
@@ -293,6 +287,13 @@ STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored)
return self->_hashx[b.idx] ? CX##_erase_entry(self, self->table + b.idx), 1 : 0; \
} \
\
+ STC_INLINE CX##_iter_t \
+ CX##_erase_it(CX* self, CX##_iter_t it) { \
+ CX##_erase_entry(self, it.ref); \
+ if (*it._hx == 0) CX##_next(&it); \
+ return it; \
+ } \
+\
_c_implement_chash(CX, C, Key, Mapped, keyEqualsRaw, keyHashRaw, \
mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
keyDel, keyFromRaw, keyToRaw, RawKey) \
@@ -364,13 +365,10 @@ STC_INLINE size_t fastrange_uint64_t(uint64_t x, uint64_t n) \
return it; \
} \
\
- STC_INLINE void CX##_reserve_expand_(CX* self) { \
- if (self->size + 1 >= self->bucket_count*self->max_load_factor) \
- CX##_reserve(self, 5 + self->size * 3 / 2); \
- } \
STC_DEF CX##_result_t \
CX##_insert_entry_(CX* self, RawKey rkey) { \
- CX##_reserve_expand_(self); \
+ if (self->size + 1 >= (CX##_size_t) (self->bucket_count * self->max_load_factor)) \
+ CX##_reserve(self, 8 + self->size * 3 / 2); \
chash_bucket_t b = CX##_bucket_(self, &rkey); \
CX##_result_t res = {&self->table[b.idx], !self->_hashx[b.idx]}; \
if (res.inserted) { \
@@ -385,7 +383,7 @@ STC_INLINE size_t fastrange_uint64_t(uint64_t x, uint64_t n) \
CX clone = { \
c_new_2(CX##_value_t, m.bucket_count), \
(uint8_t *) memcpy(c_malloc(m.bucket_count + 1), m._hashx, m.bucket_count + 1), \
- m.size, m.bucket_count, m.min_load_factor, m.max_load_factor \
+ m.size, m.bucket_count, m.max_load_factor \
}; \
CX##_value_t *e = m.table, *end = e + m.bucket_count, *dst = clone.table; \
for (uint8_t *hx = m._hashx; e != end; ++hx, ++e, ++dst) \
@@ -397,12 +395,12 @@ STC_INLINE size_t fastrange_uint64_t(uint64_t x, uint64_t n) \
CX##_reserve(CX* self, size_t newcap) { \
if (newcap < self->size) return; \
size_t oldcap = self->bucket_count; \
- newcap = (size_t) (newcap / self->max_load_factor) | 1; \
+ newcap = (size_t) (2 + newcap / self->max_load_factor) | 1; \
CX tmp = { \
c_new_2 (CX##_value_t, newcap), \
(uint8_t *) c_calloc(newcap + 1, sizeof(uint8_t)), \
self->size, (CX##_size_t) newcap, \
- self->min_load_factor, self->max_load_factor \
+ self->max_load_factor \
}; \
/* Rehash: */ \
tmp._hashx[newcap] = 0xff; c_swap(CX, *self, tmp); \
@@ -434,18 +432,8 @@ STC_INLINE size_t fastrange_uint64_t(uint64_t x, uint64_t n) \
if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ \
slot[i] = slot[j], hashx[i] = hashx[j], i = j; \
} \
- hashx[i] = 0, k = --self->size; \
- if (k < cap*self->min_load_factor && k > 512) \
- CX##_reserve(self, k*1.2); \
- } \
-\
- STC_DEF CX##_iter_t \
- CX##_erase_it(CX* self, CX##_iter_t it) { \
- size_t idx = it.ref - self->table; \
- CX##_erase_entry(self, it.ref); \
- it.ref = self->table + idx, it._hx = self->_hashx + idx; \
- if (*it._hx == 0) CX##_next(&it); \
- return it; \
+ hashx[i] = 0; \
+ --self->size; \
}
generated by cgit v1.2.3 (git 2.39.1) at 2026-04-14 23:19:17 +0000