diff options
Diffstat (limited to 'include')
| -rw-r--r-- | include/conts/map.h | 28 |
1 files changed, 16 insertions, 12 deletions
diff --git a/include/conts/map.h b/include/conts/map.h index 571eda2..f617d10 100644 --- a/include/conts/map.h +++ b/include/conts/map.h @@ -18,6 +18,10 @@ #error "Need map name" #endif +#ifndef MAP_FACTOR +#define MAP_FACTOR 2 +#endif + #ifndef MAP_MALLOC #define MAP_MALLOC malloc #endif @@ -130,16 +134,16 @@ static inline void MAP(destroy)(struct MAP_ROOT *root) static inline MAP_VALUE_TYPE *MAP(find_hash)(struct MAP_ROOT *root, MAP_KEY_TYPE key, uint32_t hash) { - for (size_t s = MAP_SPVEC(len)(&root->buf); s >= conts_spvec_size(0); s /= 2) { + for (size_t s = MAP_SPVEC(len)(&root->buf); + s >= conts_spvec_size(0); + s /= MAP_FACTOR) { bool base = s == conts_spvec_size(0); - size_t range = base ? s : s / 2; - size_t offst = base ? 0 : s / 2; + size_t range = base ? s : (MAP_FACTOR - 1) * s / MAP_FACTOR; + size_t offst = base ? 0 : s / MAP_FACTOR; /* linear probing for now */ for (size_t i = 0; i < range; ++i) { - assert(__builtin_popcountll(range) == 1); - size_t idx = (hash + i) & (range - 1); - + size_t idx = (hash + i) % range; struct MAP_NODE *n = MAP_SPVEC(at)(&root->buf, idx + offst); /* unused node means chain must not exist in this range */ @@ -182,8 +186,8 @@ static inline MAP_VALUE_TYPE *MAP(insert)(struct MAP_ROOT *root, MAP_KEY_TYPE ke /* grow as needed */ size_t s = MAP_SPVEC(len)(&root->buf); - if (2 * root->n >= s) { - s *= 2; + if (MAP_FACTOR * root->n >= s) { + s *= MAP_FACTOR; if (!MAP_SPVEC(reserve)(&root->buf, s)) return NULL; @@ -194,13 +198,12 @@ static inline MAP_VALUE_TYPE *MAP(insert)(struct MAP_ROOT *root, MAP_KEY_TYPE ke /* there must always be at least one free spot */ root->n++; bool base = s == conts_spvec_size(0); - size_t range = base ? s : s / 2; - size_t offst = base ? 0 : s / 2; + size_t range = base ? s : (MAP_FACTOR - 1) * s / MAP_FACTOR; + size_t offst = base ? 0 : s / MAP_FACTOR; /* linear probing for now */ for (size_t i = 0; i < range; ++i) { - assert(__builtin_popcountll(range) == 1); - size_t idx = (hash + i) & (range - 1); + size_t idx = (hash + i) % range; struct MAP_NODE *n = MAP_SPVEC(at)(&root->buf, idx + offst); if (n->used == CONTS_MAP_USED) @@ -291,6 +294,7 @@ static inline size_t MAP(len)(struct MAP_ROOT *root) #undef MAP_ROOT #undef MAP_KEY_TYPE #undef MAP_VALUE_TYPE +#undef MAP_FACTOR #undef MAP_CMP #undef MAP_HASH #undef MAP_NAME |