#include <errno.h>

#include <pthread.h>

#include <stdint.h>

#include <stdlib.h>

#include "alloc-util.h"

#include "fileio.h"

#include "hashmap.h"

#include "macro.h"

#include "memory-util.h"

#include "mempool.h"

#include "missing_syscall.h"

#include "process-util.h"

#include "random-util.h"

#include "set.h"

#include "siphash24.h"

#include "string-util.h"

#include "strv.h"

#if ENABLE_DEBUG_HASHMAP

#include "list.h"

#define INV_KEEP_FREE 5U

struct hashmap_base_entry {

const void *key;

};

struct plain_hashmap_entry {

struct hashmap_base_entry b;

void *value;

};

struct ordered_hashmap_entry {

struct plain_hashmap_entry p;

unsigned iterate_next, iterate_previous;

};

struct set_entry {

struct hashmap_base_entry b;

};

#define _IDX_SWAP_BEGIN (UINT_MAX - 3)

#define IDX_PUT (_IDX_SWAP_BEGIN + 0)

#define IDX_TMP (_IDX_SWAP_BEGIN + 1)

#define _IDX_SWAP_END (_IDX_SWAP_BEGIN + 2)

#define IDX_FIRST (UINT_MAX - 1) /* special index for freshly initialized iterators */

#define IDX_NIL UINT_MAX /* special index value meaning "none" or "end" */

assert_cc(IDX_FIRST == _IDX_SWAP_END);

assert_cc(IDX_FIRST == _IDX_ITERATOR_FIRST);

struct swap_entries {

struct ordered_hashmap_entry e[_IDX_SWAP_END - _IDX_SWAP_BEGIN];

};

typedef uint8_t dib_raw_t;

#define DIB_RAW_OVERFLOW ((dib_raw_t)0xfdU) /* indicates DIB value is greater than representable */

#define DIB_RAW_REHASH ((dib_raw_t)0xfeU) /* entry yet to be rehashed during in-place resize */

#define DIB_RAW_FREE ((dib_raw_t)0xffU) /* a free bucket */

#define DIB_RAW_INIT ((char)DIB_RAW_FREE) /* a byte to memset a DIB store with when initializing */

#define DIB_FREE UINT_MAX

#if ENABLE_DEBUG_HASHMAP

struct hashmap_debug_info {

};

static LIST_HEAD(struct hashmap_debug_info, hashmap_debug_list);

static pthread_mutex_t hashmap_debug_list_mutex = PTHREAD_MUTEX_INITIALIZER;

enum HashmapType {

};

struct _packed_ indirect_storage {

void *storage; /* where buckets and DIBs are stored */

uint8_t hash_key[HASH_KEY_SIZE]; /* hash key; changes during resize */

unsigned n_entries; /* number of stored entries */

unsigned n_buckets; /* number of buckets */

unsigned idx_lowest_entry; /* Index below which all buckets are free.

uint8_t _pad[3]; /* padding for the whole HashmapBase */

/* The bitfields in HashmapBase complete the alignment of the whole thing. */

};

struct direct_storage {

};

#define DIRECT_BUCKETS(entry_t) \

(sizeof(struct direct_storage) / (sizeof(entry_t) + sizeof(dib_raw_t)))

assert_cc(DIRECT_BUCKETS(struct ordered_hashmap_entry) >= 1);

assert_cc(DIRECT_BUCKETS(struct set_entry) < (1 << 3));

static uint8_t shared_hash_key[HASH_KEY_SIZE];

struct HashmapBase {

};

struct Hashmap {

struct HashmapBase b;

};

struct OrderedHashmap {

struct HashmapBase b;

unsigned iterate_list_head, iterate_list_tail;

};

struct Set {

struct HashmapBase b;

};

typedef struct CacheMem {

} CacheMem;

struct IteratedCache {

HashmapBase *hashmap;

CacheMem keys, values;

};

DEFINE_MEMPOOL(hashmap_pool, Hashmap, 8);

DEFINE_MEMPOOL(ordered_hashmap_pool, OrderedHashmap, 8);

assert_cc(sizeof(Hashmap) == sizeof(Set));

struct hashmap_type_info {

};

static _used_ const struct hashmap_type_info hashmap_type_info[_HASHMAP_TYPE_MAX] = {

[HASHMAP_TYPE_PLAIN] = {

.head_size = sizeof(Hashmap),

.entry_size = sizeof(struct plain_hashmap_entry),

.mempool = &hashmap_pool,

.n_direct_buckets = DIRECT_BUCKETS(struct plain_hashmap_entry),

},

[HASHMAP_TYPE_ORDERED] = {

.head_size = sizeof(OrderedHashmap),

.entry_size = sizeof(struct ordered_hashmap_entry),

.mempool = &ordered_hashmap_pool,

.n_direct_buckets = DIRECT_BUCKETS(struct ordered_hashmap_entry),

},

[HASHMAP_TYPE_SET] = {

.head_size = sizeof(Set),

.entry_size = sizeof(struct set_entry),

.mempool = &hashmap_pool,

.n_direct_buckets = DIRECT_BUCKETS(struct set_entry),

},

};

#if VALGRIND

_destructor_ static void cleanup_pools(void) {

_cleanup_free_ char *t = NULL;

int r;

/* Be nice to valgrind */

/* The pool is only allocated by the main thread, but the memory can

/* We build our own is_main_thread() here, which doesn't use C11

if (getpid() != gettid())

return;

r = get_proc_field("/proc/self/status", "Threads", WHITESPACE, &t);

if (r < 0 || !streq(t, "1"))

return;

mempool_drop(&hashmap_pool);

mempool_drop(&ordered_hashmap_pool);

}

static unsigned n_buckets(HashmapBase *h) {

return h->has_indirect ? h->indirect.n_buckets

: hashmap_type_info[h->type].n_direct_buckets;

}

static unsigned n_entries(HashmapBase *h) {

return h->has_indirect ? h->indirect.n_entries

: h->n_direct_entries;

}

static void n_entries_inc(HashmapBase *h) {

if (h->has_indirect)

h->indirect.n_entries++;

else

h->n_direct_entries++;

}

static void n_entries_dec(HashmapBase *h) {

if (h->has_indirect)

h->indirect.n_entries--;

else

h->n_direct_entries--;

}

static void* storage_ptr(HashmapBase *h) {

return h->has_indirect ? h->indirect.storage

: h->direct.storage;

}

static uint8_t* hash_key(HashmapBase *h) {

return h->has_indirect ? h->indirect.hash_key

: shared_hash_key;

}

static unsigned base_bucket_hash(HashmapBase *h, const void *p) {

struct siphash state;

uint64_t hash;

siphash24_init(&state, hash_key(h));

h->hash_ops->hash(p, &state);

hash = siphash24_finalize(&state);

return (unsigned) (hash % n_buckets(h));

}

#define bucket_hash(h, p) base_bucket_hash(HASHMAP_BASE(h), p)

static void base_set_dirty(HashmapBase *h) {

h->dirty = true;

}

#define hashmap_set_dirty(h) base_set_dirty(HASHMAP_BASE(h))

static void get_hash_key(uint8_t hash_key[HASH_KEY_SIZE], bool reuse_is_ok) {

static uint8_t current[HASH_KEY_SIZE];

static bool current_initialized = false;

/* Returns a hash function key to use. In order to keep things

if (!current_initialized || !reuse_is_ok) {

random_bytes(current, sizeof(current));

current_initialized = true;

}

memcpy(hash_key, current, sizeof(current));

}

static struct hashmap_base_entry* bucket_at(HashmapBase *h, unsigned idx) {

return (struct hashmap_base_entry*)

((uint8_t*) storage_ptr(h) + idx * hashmap_type_info[h->type].entry_size);

}

static struct plain_hashmap_entry* plain_bucket_at(Hashmap *h, unsigned idx) {

return (struct plain_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx);

}

static struct ordered_hashmap_entry* ordered_bucket_at(OrderedHashmap *h, unsigned idx) {

return (struct ordered_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx);

}

static struct set_entry *set_bucket_at(Set *h, unsigned idx) {

return (struct set_entry*) bucket_at(HASHMAP_BASE(h), idx);

}

static struct ordered_hashmap_entry* bucket_at_swap(struct swap_entries *swap, unsigned idx) {

return &swap->e[idx - _IDX_SWAP_BEGIN];

}

static struct hashmap_base_entry* bucket_at_virtual(HashmapBase *h, struct swap_entries *swap,

unsigned idx) {

if (idx < _IDX_SWAP_BEGIN)

return bucket_at(h, idx);

if (idx < _IDX_SWAP_END)

return &bucket_at_swap(swap, idx)->p.b;

assert_not_reached("Invalid index");

}

static dib_raw_t* dib_raw_ptr(HashmapBase *h) {

return (dib_raw_t*)

((uint8_t*) storage_ptr(h) + hashmap_type_info[h->type].entry_size * n_buckets(h));

}

static unsigned bucket_distance(HashmapBase *h, unsigned idx, unsigned from) {

return idx >= from ? idx - from

: n_buckets(h) + idx - from;

}

static unsigned bucket_calculate_dib(HashmapBase *h, unsigned idx, dib_raw_t raw_dib) {

unsigned initial_bucket;

if (raw_dib == DIB_RAW_FREE)

return DIB_FREE;

if (_likely_(raw_dib < DIB_RAW_OVERFLOW))

return raw_dib;

/*

initial_bucket = bucket_hash(h, bucket_at(h, idx)->key);

return bucket_distance(h, idx, initial_bucket);

}

static void bucket_set_dib(HashmapBase *h, unsigned idx, unsigned dib) {

dib_raw_ptr(h)[idx] = dib != DIB_FREE ? MIN(dib, DIB_RAW_OVERFLOW) : DIB_RAW_FREE;

}

static unsigned skip_free_buckets(HashmapBase *h, unsigned idx) {

dib_raw_t *dibs;

dibs = dib_raw_ptr(h);

for ( ; idx < n_buckets(h); idx++)

if (dibs[idx] != DIB_RAW_FREE)

return idx;

return IDX_NIL;

}

static void bucket_mark_free(HashmapBase *h, unsigned idx) {

memzero(bucket_at(h, idx), hashmap_type_info[h->type].entry_size);

bucket_set_dib(h, idx, DIB_FREE);

}

static void bucket_move_entry(HashmapBase *h, struct swap_entries *swap,

unsigned from, unsigned to) {

struct hashmap_base_entry *e_from, *e_to;

assert(from != to);

e_from = bucket_at_virtual(h, swap, from);

e_to = bucket_at_virtual(h, swap, to);

memcpy(e_to, e_from, hashmap_type_info[h->type].entry_size);

if (h->type == HASHMAP_TYPE_ORDERED) {

OrderedHashmap *lh = (OrderedHashmap*) h;

struct ordered_hashmap_entry *le, *le_to;

le_to = (struct ordered_hashmap_entry*) e_to;

if (le_to->iterate_next != IDX_NIL) {

le = (struct ordered_hashmap_entry*)

bucket_at_virtual(h, swap, le_to->iterate_next);

le->iterate_previous = to;

}

if (le_to->iterate_previous != IDX_NIL) {

le = (struct ordered_hashmap_entry*)

bucket_at_virtual(h, swap, le_to->iterate_previous);

le->iterate_next = to;

}

if (lh->iterate_list_head == from)

lh->iterate_list_head = to;

if (lh->iterate_list_tail == from)

lh->iterate_list_tail = to;

}

}

static unsigned next_idx(HashmapBase *h, unsigned idx) {

return (idx + 1U) % n_buckets(h);

}

static unsigned prev_idx(HashmapBase *h, unsigned idx) {

return (n_buckets(h) + idx - 1U) % n_buckets(h);

}

static void* entry_value(HashmapBase *h, struct hashmap_base_entry *e) {

switch (h->type) {

case HASHMAP_TYPE_PLAIN:

case HASHMAP_TYPE_ORDERED:

return ((struct plain_hashmap_entry*)e)->value;

case HASHMAP_TYPE_SET:

return (void*) e->key;

default:

assert_not_reached("Unknown hashmap type");

}

}

static void base_remove_entry(HashmapBase *h, unsigned idx) {

unsigned left, right, prev, dib;

dib_raw_t raw_dib, *dibs;

dibs = dib_raw_ptr(h);

assert(dibs[idx] != DIB_RAW_FREE);

#if ENABLE_DEBUG_HASHMAP

h->debug.rem_count++;

h->debug.last_rem_idx = idx;

left = idx;

/* Find the stop bucket ("right"). It is either free or has DIB == 0. */

for (right = next_idx(h, left); ; right = next_idx(h, right)) {

raw_dib = dibs[right];

if (IN_SET(raw_dib, 0, DIB_RAW_FREE))

break;

/* The buckets are not supposed to be all occupied and with DIB > 0.

assert(left != right);

}

if (h->type == HASHMAP_TYPE_ORDERED) {

OrderedHashmap *lh = (OrderedHashmap*) h;

struct ordered_hashmap_entry *le = ordered_bucket_at(lh, idx);

if (le->iterate_next != IDX_NIL)

ordered_bucket_at(lh, le->iterate_next)->iterate_previous = le->iterate_previous;

else

lh->iterate_list_tail = le->iterate_previous;

if (le->iterate_previous != IDX_NIL)

ordered_bucket_at(lh, le->iterate_previous)->iterate_next = le->iterate_next;

else

lh->iterate_list_head = le->iterate_next;

}

/* Now shift all buckets in the interval (left, right) one step backwards */

for (prev = left, left = next_idx(h, left); left != right;

prev = left, left = next_idx(h, left)) {

dib = bucket_calculate_dib(h, left, dibs[left]);

assert(dib != 0);

bucket_move_entry(h, NULL, left, prev);

bucket_set_dib(h, prev, dib - 1);

}

bucket_mark_free(h, prev);

n_entries_dec(h);

base_set_dirty(h);

}

#define remove_entry(h, idx) base_remove_entry(HASHMAP_BASE(h), idx)

static unsigned hashmap_iterate_in_insertion_order(OrderedHashmap *h, Iterator *i) {

struct ordered_hashmap_entry *e;

unsigned idx;

assert(h);

assert(i);

if (i->idx == IDX_NIL)

goto at_end;

if (i->idx == IDX_FIRST && h->iterate_list_head == IDX_NIL)

goto at_end;

if (i->idx == IDX_FIRST) {

idx = h->iterate_list_head;

e = ordered_bucket_at(h, idx);

} else {

idx = i->idx;

e = ordered_bucket_at(h, idx);

/*

if (e->p.b.key != i->next_key) {

idx = prev_idx(HASHMAP_BASE(h), idx);

e = ordered_bucket_at(h, idx);

}

assert(e->p.b.key == i->next_key);

}

#if ENABLE_DEBUG_HASHMAP

i->prev_idx = idx;

if (e->iterate_next != IDX_NIL) {

struct ordered_hashmap_entry *n;

i->idx = e->iterate_next;

n = ordered_bucket_at(h, i->idx);

i->next_key = n->p.b.key;

} else

i->idx = IDX_NIL;

return idx;

at_end:

i->idx = IDX_NIL;

return IDX_NIL;

}

static unsigned hashmap_iterate_in_internal_order(HashmapBase *h, Iterator *i) {

unsigned idx;

assert(h);

assert(i);

if (i->idx == IDX_NIL)

goto at_end;

if (i->idx == IDX_FIRST) {

/* fast forward to the first occupied bucket */

if (h->has_indirect) {

i->idx = skip_free_buckets(h, h->indirect.idx_lowest_entry);

h->indirect.idx_lowest_entry = i->idx;

} else

i->idx = skip_free_buckets(h, 0);

if (i->idx == IDX_NIL)

goto at_end;

} else {

struct hashmap_base_entry *e;

assert(i->idx > 0);

e = bucket_at(h, i->idx);

/*

if (e->key != i->next_key)

e = bucket_at(h, --i->idx);

assert(e->key == i->next_key);

}

idx = i->idx;

#if ENABLE_DEBUG_HASHMAP

i->prev_idx = idx;

i->idx = skip_free_buckets(h, i->idx + 1);

if (i->idx != IDX_NIL)

i->next_key = bucket_at(h, i->idx)->key;

else

i->idx = IDX_NIL;

return idx;

at_end:

i->idx = IDX_NIL;

return IDX_NIL;

}

static unsigned hashmap_iterate_entry(HashmapBase *h, Iterator *i) {

if (!h) {

i->idx = IDX_NIL;

return IDX_NIL;

}

#if ENABLE_DEBUG_HASHMAP

if (i->idx == IDX_FIRST) {

i->put_count = h->debug.put_count;

i->rem_count = h->debug.rem_count;

} else {

/* While iterating, must not add any new entries */

assert(i->put_count == h->debug.put_count);

/* ... or remove entries other than the current one */

assert(i->rem_count == h->debug.rem_count ||

(i->rem_count == h->debug.rem_count - 1 &&

i->prev_idx == h->debug.last_rem_idx));

/* Reset our removals counter */

i->rem_count = h->debug.rem_count;

}

return h->type == HASHMAP_TYPE_ORDERED ? hashmap_iterate_in_insertion_order((OrderedHashmap*) h, i)

: hashmap_iterate_in_internal_order(h, i);

}

bool _hashmap_iterate(HashmapBase *h, Iterator *i, void **value, const void **key) {

struct hashmap_base_entry *e;

void *data;

unsigned idx;

idx = hashmap_iterate_entry(h, i);

if (idx == IDX_NIL) {

if (value)

*value = NULL;

if (key)

*key = NULL;

return false;

}

e = bucket_at(h, idx);

data = entry_value(h, e);

if (value)

*value = data;

if (key)

*key = e->key;

return true;

}

#define HASHMAP_FOREACH_IDX(idx, h, i) \

for ((i) = ITERATOR_FIRST, (idx) = hashmap_iterate_entry((h), &(i)); \

(idx != IDX_NIL); \

(idx) = hashmap_iterate_entry((h), &(i)))

IteratedCache* _hashmap_iterated_cache_new(HashmapBase *h) {

IteratedCache *cache;

assert(h);

assert(!h->cached);

if (h->cached)

return NULL;

cache = new0(IteratedCache, 1);

if (!cache)

return NULL;

cache->hashmap = h;

h->cached = true;

return cache;

}

static void reset_direct_storage(HashmapBase *h) {

const struct hashmap_type_info *hi = &hashmap_type_info[h->type];

void *p;

assert(!h->has_indirect);

p = mempset(h->direct.storage, 0, hi->entry_size * hi->n_direct_buckets);

memset(p, DIB_RAW_INIT, sizeof(dib_raw_t) * hi->n_direct_buckets);

}

static void shared_hash_key_initialize(void) {

random_bytes(shared_hash_key, sizeof(shared_hash_key));

}

static struct HashmapBase* hashmap_base_new(const struct hash_ops *hash_ops, enum HashmapType type HASHMAP_DEBUG_PARAMS) {

HashmapBase *h;

const struct hashmap_type_info *hi = &hashmap_type_info[type];

bool up;

up = mempool_enabled();

h = up ? mempool_alloc0_tile(hi->mempool) : malloc0(hi->head_size);

if (!h)

return NULL;

h->type = type;

h->from_pool = up;

h->hash_ops = hash_ops ?: &trivial_hash_ops;

if (type == HASHMAP_TYPE_ORDERED) {

OrderedHashmap *lh = (OrderedHashmap*)h;

lh->iterate_list_head = lh->iterate_list_tail = IDX_NIL;

}

reset_direct_storage(h);

static pthread_once_t once = PTHREAD_ONCE_INIT;

assert_se(pthread_once(&once, shared_hash_key_initialize) == 0);

#if ENABLE_DEBUG_HASHMAP

h->debug.func = func;

h->debug.file = file;

h->debug.line = line;

assert_se(pthread_mutex_lock(&hashmap_debug_list_mutex) == 0);

LIST_PREPEND(debug_list, hashmap_debug_list, &h->debug);

assert_se(pthread_mutex_unlock(&hashmap_debug_list_mutex) == 0);

return h;

}

Hashmap *_hashmap_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {

return (Hashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS);

}

OrderedHashmap *_ordered_hashmap_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {

return (OrderedHashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS);

}

Set *_set_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {

return (Set*) hashmap_base_new(hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS);

}

static int hashmap_base_ensure_allocated(HashmapBase **h, const struct hash_ops *hash_ops,

enum HashmapType type HASHMAP_DEBUG_PARAMS) {

HashmapBase *q;

assert(h);

if (*h)

return 0;

q = hashmap_base_new(hash_ops, type HASHMAP_DEBUG_PASS_ARGS);

if (!q)

return -ENOMEM;

*h = q;

return 1;

}

int _hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {

return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS);

}

int _ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {

return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS);

}

int _set_ensure_allocated(Set **s, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {

return hashmap_base_ensure_allocated((HashmapBase**)s, hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS);

}

int _hashmap_ensure_put(Hashmap **h, const struct hash_ops *hash_ops, const void *key, void *value HASHMAP_DEBUG_PARAMS) {

int r;

r = _hashmap_ensure_allocated(h, hash_ops HASHMAP_DEBUG_PASS_ARGS);

if (r < 0)

return r;

return hashmap_put(*h, key, value);

}

int _ordered_hashmap_ensure_put(OrderedHashmap **h, const struct hash_ops *hash_ops, const void *key, void *value HASHMAP_DEBUG_PARAMS) {

int r;

r = _ordered_hashmap_ensure_allocated(h, hash_ops HASHMAP_DEBUG_PASS_ARGS);

if (r < 0)

return r;

return ordered_hashmap_put(*h, key, value);

}

static void hashmap_free_no_clear(HashmapBase *h) {

assert(!h->has_indirect);

assert(h->n_direct_entries == 0);

#if ENABLE_DEBUG_HASHMAP

assert_se(pthread_mutex_lock(&hashmap_debug_list_mutex) == 0);

LIST_REMOVE(debug_list, hashmap_debug_list, &h->debug);

assert_se(pthread_mutex_unlock(&hashmap_debug_list_mutex) == 0);

if (h->from_pool) {

/* Ensure that the object didn't get migrated between threads. */

assert_se(is_main_thread());

mempool_free_tile(hashmap_type_info[h->type].mempool, h);

} else

free(h);

}

HashmapBase* _hashmap_free(HashmapBase *h, free_func_t default_free_key, free_func_t default_free_value) {

if (h) {

_hashmap_clear(h, default_free_key, default_free_value);

hashmap_free_no_clear(h);

}

return NULL;

}

void _hashmap_clear(HashmapBase *h, free_func_t default_free_key, free_func_t default_free_value) {

free_func_t free_key, free_value;

if (!h)

return;

free_key = h->hash_ops->free_key ?: default_free_key;

free_value = h->hash_ops->free_value ?: default_free_value;

if (free_key || free_value) {

/* If destructor calls are defined, let's destroy things defensively: let's take the item out of the

while (_hashmap_size(h) > 0) {

void *k = NULL;

void *v;

v = _hashmap_first_key_and_value(h, true, &k);

if (free_key)

free_key(k);

if (free_value)

free_value(v);

}

}

if (h->has_indirect) {

free(h->indirect.storage);

h->has_indirect = false;

}

h->n_direct_entries = 0;

reset_direct_storage(h);

if (h->type == HASHMAP_TYPE_ORDERED) {

OrderedHashmap *lh = (OrderedHashmap*) h;

lh->iterate_list_head = lh->iterate_list_tail = IDX_NIL;

}

base_set_dirty(h);

}

static int resize_buckets(HashmapBase *h, unsigned entries_add);

static bool hashmap_put_robin_hood(HashmapBase *h, unsigned idx,

struct swap_entries *swap) {

dib_raw_t raw_dib, *dibs;

unsigned dib, distance;

#if ENABLE_DEBUG_HASHMAP

h->debug.put_count++;

dibs = dib_raw_ptr(h);

for (distance = 0; ; distance++) {

raw_dib = dibs[idx];

if (IN_SET(raw_dib, DIB_RAW_FREE, DIB_RAW_REHASH)) {

if (raw_dib == DIB_RAW_REHASH)

bucket_move_entry(h, swap, idx, IDX_TMP);

if (h->has_indirect && h->indirect.idx_lowest_entry > idx)

h->indirect.idx_lowest_entry = idx;

bucket_set_dib(h, idx, distance);

bucket_move_entry(h, swap, IDX_PUT, idx);

if (raw_dib == DIB_RAW_REHASH) {

bucket_move_entry(h, swap, IDX_TMP, IDX_PUT);

return true;

}

return false;

}

dib = bucket_calculate_dib(h, idx, raw_dib);

if (dib < distance) {

/* Found a wealthier entry. Go Robin Hood! */

bucket_set_dib(h, idx, distance);

/* swap the entries */

bucket_move_entry(h, swap, idx, IDX_TMP);

bucket_move_entry(h, swap, IDX_PUT, idx);

bucket_move_entry(h, swap, IDX_TMP, IDX_PUT);

distance = dib;

}

idx = next_idx(h, idx);

}

}