src/shared/hashmap.c

	hashmap.c revision de99c9dcbaf6e474551266d8f0b519bf2d8d0522
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba/***
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba  This file is part of systemd.
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba  Copyright 2010 Lennart Poettering
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba  systemd is free software; you can redistribute it and/or modify it
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba  under the terms of the GNU Lesser General Public License as published by
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba  the Free Software Foundation; either version 2.1 of the License, or
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba  (at your option) any later version.
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba  systemd is distributed in the hope that it will be useful, but
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba  WITHOUT ANY WARRANTY; without even the implied warranty of
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba  Lesser General Public License for more details.
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba  You should have received a copy of the GNU Lesser General Public License
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba  along with systemd; If not, see <http://www.gnu.org/licenses/>.
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba***/
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba#include <assert.h>
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba#include <stdlib.h>
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba#include <string.h>
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp#include <errno.h>
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba#include "util.h"
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba#include "hashmap.h"
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba#include "macro.h"
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba#include "siphash24.h"
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac#define INITIAL_N_BUCKETS 31
8b15572442aae50358e392562bd2e1ebfd5b2906matthew
eef6695bc3b88e10d60477095ebddd4b9499481fpgambastruct hashmap_entry {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        const void *key;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        void *value;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        struct hashmap_entry *bucket_next, *bucket_previous;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        struct hashmap_entry *iterate_next, *iterate_previous;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba};
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambastruct Hashmap {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        hash_func_t hash_func;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        compare_func_t compare_func;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        struct hashmap_entry *iterate_list_head, *iterate_list_tail;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
d729d88914866aa41d5d6dc5e7f6a7fb5f601bc3matthew        struct hashmap_entry ** buckets;
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        unsigned n_buckets, n_entries;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        uint8_t hash_key[HASH_KEY_SIZE];
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        bool from_pool:1;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba};
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambastruct pool {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        struct pool *next;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        unsigned n_tiles;
d87eec6ea79502a1c14f1d960527ba986dfeb52cJnRouvignac        unsigned n_used;
d87eec6ea79502a1c14f1d960527ba986dfeb52cJnRouvignac};
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambastatic struct pool *first_hashmap_pool = NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgambastatic void *first_hashmap_tile = NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambastatic struct pool *first_entry_pool = NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgambastatic void *first_entry_tile = NULL;
0d397efc4b781ef5b60108708fa1131467d2c3c8gbellato
0d397efc4b781ef5b60108708fa1131467d2c3c8gbellatostatic void* allocate_tile(struct pool **first_pool, void **first_tile, size_t tile_size, unsigned at_least) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        unsigned i;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        /* When a tile is released we add it to the list and simply
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba         * place the next pointer at its offset 0. */
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        assert(tile_size >= sizeof(void*));
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        assert(at_least > 0);
ea1dd4f3ba4c9d619a6c413f934507938a804f95ludo
ea1dd4f3ba4c9d619a6c413f934507938a804f95ludo        if (*first_tile) {
ea1dd4f3ba4c9d619a6c413f934507938a804f95ludo                void *r;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                r = *first_tile;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                *first_tile = * (void**) (*first_tile);
8b15572442aae50358e392562bd2e1ebfd5b2906matthew                return r;
8b15572442aae50358e392562bd2e1ebfd5b2906matthew        }
af0f03109bd00f4ccb3d6671bbc4e4f1a32ccbf9gbellato
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (_unlikely_(!*first_pool) || _unlikely_((*first_pool)->n_used >= (*first_pool)->n_tiles)) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                unsigned n;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                size_t size;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                struct pool *p;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                n = *first_pool ? (*first_pool)->n_tiles : 0;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                n = MAX(at_least, n * 2);
d87eec6ea79502a1c14f1d960527ba986dfeb52cJnRouvignac                size = PAGE_ALIGN(ALIGN(sizeof(struct pool)) + n*tile_size);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                n = (size - ALIGN(sizeof(struct pool))) / tile_size;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                p = malloc(size);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                if (!p)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                        return NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                p->next = *first_pool;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                p->n_tiles = n;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                p->n_used = 0;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                *first_pool = p;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        }
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        i = (*first_pool)->n_used++;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return ((uint8_t*) (*first_pool)) + ALIGN(sizeof(struct pool)) + i*tile_size;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambastatic void deallocate_tile(void **first_tile, void *p) {
85f6e15f35fa13ce5e3d0ed1716c8986b048745emrossign        * (void**) p = *first_tile;
8b15572442aae50358e392562bd2e1ebfd5b2906matthew        *first_tile = p;
8b15572442aae50358e392562bd2e1ebfd5b2906matthew}
85f6e15f35fa13ce5e3d0ed1716c8986b048745emrossign
8b15572442aae50358e392562bd2e1ebfd5b2906matthew#ifdef VALGRIND
8b15572442aae50358e392562bd2e1ebfd5b2906matthew
85f6e15f35fa13ce5e3d0ed1716c8986b048745emrossignstatic void drop_pool(struct pool *p) {
8b15572442aae50358e392562bd2e1ebfd5b2906matthew        while (p) {
85f6e15f35fa13ce5e3d0ed1716c8986b048745emrossign                struct pool *n;
8b15572442aae50358e392562bd2e1ebfd5b2906matthew                n = p->next;
d87eec6ea79502a1c14f1d960527ba986dfeb52cJnRouvignac                free(p);
8b15572442aae50358e392562bd2e1ebfd5b2906matthew                p = n;
8b15572442aae50358e392562bd2e1ebfd5b2906matthew        }
8b15572442aae50358e392562bd2e1ebfd5b2906matthew}
8b15572442aae50358e392562bd2e1ebfd5b2906matthew
8b15572442aae50358e392562bd2e1ebfd5b2906matthew__attribute__((destructor)) static void cleanup_pool(void) {
85f6e15f35fa13ce5e3d0ed1716c8986b048745emrossign        /* Be nice to valgrind */
85f6e15f35fa13ce5e3d0ed1716c8986b048745emrossign
85f6e15f35fa13ce5e3d0ed1716c8986b048745emrossign        drop_pool(first_hashmap_pool);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        drop_pool(first_entry_pool);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba#endif
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambaunsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        uint64_t u;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        siphash24((uint8_t*) &u, p, strlen(p), hash_key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return (unsigned long) u;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
05dfdaaa15dba2ce14a71f74ec6b233a3c527389ludo
eef6695bc3b88e10d60477095ebddd4b9499481fpgambaint string_compare_func(const void *a, const void *b) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return strcmp(a, b);
0d397efc4b781ef5b60108708fa1131467d2c3c8gbellato}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambaunsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        uint64_t u;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        siphash24((uint8_t*) &u, &p, sizeof(p), hash_key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return (unsigned long) u;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambaint trivial_compare_func(const void *a, const void *b) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return a < b ? -1 : (a > b ? 1 : 0);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
d87eec6ea79502a1c14f1d960527ba986dfeb52cJnRouvignac
eef6695bc3b88e10d60477095ebddd4b9499481fpgambaunsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        uint64_t u;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        siphash24((uint8_t*) &u, p, sizeof(uint64_t), hash_key);
d87eec6ea79502a1c14f1d960527ba986dfeb52cJnRouvignac        return (unsigned long) u;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
6031e9c7eb72435516a6828deb2e97533ed0382dludovicpint uint64_compare_func(const void *_a, const void *_b) {
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp        uint64_t a, b;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        a = *(const uint64_t*) _a;
d87eec6ea79502a1c14f1d960527ba986dfeb52cJnRouvignac        b = *(const uint64_t*) _b;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return a < b ? -1 : (a > b ? 1 : 0);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba#if SIZEOF_DEV_T != 8
eef6695bc3b88e10d60477095ebddd4b9499481fpgambaunsigned long devt_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        uint64_t u;
af0f03109bd00f4ccb3d6671bbc4e4f1a32ccbf9gbellato        siphash24((uint8_t*) &u, p, sizeof(dev_t), hash_key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return (unsigned long) u;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
8b15572442aae50358e392562bd2e1ebfd5b2906matthew
eef6695bc3b88e10d60477095ebddd4b9499481fpgambaint devt_compare_func(const void *_a, const void *_b) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        dev_t a, b;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        a = *(const dev_t*) _a;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        b = *(const dev_t*) _b;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return a < b ? -1 : (a > b ? 1 : 0);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba#endif
d729d88914866aa41d5d6dc5e7f6a7fb5f601bc3matthew
d729d88914866aa41d5d6dc5e7f6a7fb5f601bc3matthewstatic unsigned bucket_hash(Hashmap *h, const void *p) {
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        return (unsigned) (h->hash_func(p, h->hash_key) % h->n_buckets);
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew}
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthewstatic void get_hash_key(uint8_t hash_key[HASH_KEY_SIZE], bool reuse_is_ok) {
d729d88914866aa41d5d6dc5e7f6a7fb5f601bc3matthew        static uint8_t current[HASH_KEY_SIZE];
d729d88914866aa41d5d6dc5e7f6a7fb5f601bc3matthew        static bool current_initialized = false;
d729d88914866aa41d5d6dc5e7f6a7fb5f601bc3matthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        /* Returns a hash function key to use. In order to keep things
d729d88914866aa41d5d6dc5e7f6a7fb5f601bc3matthew         * fast we will not generate a new key each time we allocate a
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew         * new hash table. Instead, we'll just reuse the most recently
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew         * generated one, except if we never generated one or when we
d729d88914866aa41d5d6dc5e7f6a7fb5f601bc3matthew         * are rehashing an entire hash table because we reached a
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba         * fill level */
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
8b15572442aae50358e392562bd2e1ebfd5b2906matthew        if (!current_initialized || !reuse_is_ok) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                random_bytes(current, sizeof(current));
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                current_initialized = true;
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp        }
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp        memcpy(hash_key, current, sizeof(current));
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew}
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp
6031e9c7eb72435516a6828deb2e97533ed0382dludovicpHashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp        bool b;
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp        Hashmap *h;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        size_t size;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        b = is_main_thread();
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        size = ALIGN(sizeof(Hashmap)) + INITIAL_N_BUCKETS * sizeof(struct hashmap_entry*);
5d335b755ccd43707ff8529f93345030d559bc81matthew
5d335b755ccd43707ff8529f93345030d559bc81matthew        if (b) {
5d335b755ccd43707ff8529f93345030d559bc81matthew                h = allocate_tile(&first_hashmap_pool, &first_hashmap_tile, size, 8);
5d335b755ccd43707ff8529f93345030d559bc81matthew                if (!h)
5d335b755ccd43707ff8529f93345030d559bc81matthew                        return NULL;
5d335b755ccd43707ff8529f93345030d559bc81matthew
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                memzero(h, size);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        } else {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                h = malloc0(size);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                if (!h)
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp                        return NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        }
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
8b15572442aae50358e392562bd2e1ebfd5b2906matthew        h->hash_func = hash_func ? hash_func : trivial_hash_func;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        h->compare_func = compare_func ? compare_func : trivial_compare_func;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        h->n_buckets = INITIAL_N_BUCKETS;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        h->n_entries = 0;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        h->iterate_list_head = h->iterate_list_tail = NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        h->buckets = (struct hashmap_entry**) ((uint8_t*) h + ALIGN(sizeof(Hashmap)));
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
8b15572442aae50358e392562bd2e1ebfd5b2906matthew        h->from_pool = b;
8b15572442aae50358e392562bd2e1ebfd5b2906matthew
8b15572442aae50358e392562bd2e1ebfd5b2906matthew        get_hash_key(h->hash_key, true);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return h;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthewint hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) {
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        Hashmap *q;
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        assert(h);
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (*h)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return 0;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
a776a93d0afa206f307e9140a35497ee255840f2mrossign        q = hashmap_new(hash_func, compare_func);
a776a93d0afa206f307e9140a35497ee255840f2mrossign        if (!q)
a776a93d0afa206f307e9140a35497ee255840f2mrossign                return -ENOMEM;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        *h = q;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        return 0;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambastatic void link_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        assert(h);
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        assert(e);
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        /* Insert into hash table */
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        e->bucket_next = h->buckets[hash];
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        e->bucket_previous = NULL;
afd6ce83f9ecfa7b375c1f72eb5f279bbd01568cmatthew        if (h->buckets[hash])
afd6ce83f9ecfa7b375c1f72eb5f279bbd01568cmatthew                h->buckets[hash]->bucket_previous = e;
afd6ce83f9ecfa7b375c1f72eb5f279bbd01568cmatthew        h->buckets[hash] = e;
afd6ce83f9ecfa7b375c1f72eb5f279bbd01568cmatthew
afd6ce83f9ecfa7b375c1f72eb5f279bbd01568cmatthew        /* Insert into iteration list */
afd6ce83f9ecfa7b375c1f72eb5f279bbd01568cmatthew        e->iterate_previous = h->iterate_list_tail;
afd6ce83f9ecfa7b375c1f72eb5f279bbd01568cmatthew        e->iterate_next = NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (h->iterate_list_tail) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                assert(h->iterate_list_head);
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew                h->iterate_list_tail->iterate_next = e;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        } else {
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew                assert(!h->iterate_list_head);
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew                h->iterate_list_head = e;
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        }
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        h->iterate_list_tail = e;
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        h->n_entries++;
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        assert(h->n_entries >= 1);
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthewstatic void unlink_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        assert(h);
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        assert(e);
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        /* Remove from iteration list */
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        if (e->iterate_next)
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew                e->iterate_next->iterate_previous = e->iterate_previous;
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        else
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew                h->iterate_list_tail = e->iterate_previous;
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        if (e->iterate_previous)
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew                e->iterate_previous->iterate_next = e->iterate_next;
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        else
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew                h->iterate_list_head = e->iterate_next;
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        /* Remove from hash table bucket list */
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (e->bucket_next)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                e->bucket_next->bucket_previous = e->bucket_previous;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (e->bucket_previous)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                e->bucket_previous->bucket_next = e->bucket_next;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        else
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                h->buckets[hash] = e->bucket_next;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        assert(h->n_entries >= 1);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        h->n_entries--;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambastatic void remove_entry(Hashmap *h, struct hashmap_entry *e) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        unsigned hash;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        assert(h);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        assert(e);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        hash = bucket_hash(h, e->key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        unlink_entry(h, e, hash);
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp        if (h->from_pool)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                deallocate_tile(&first_entry_tile, e);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        else
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                free(e);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp
6031e9c7eb72435516a6828deb2e97533ed0382dludovicpvoid hashmap_free(Hashmap*h) {
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp        /* Free the hashmap, but nothing in it */
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp        if (!h)
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp                return;
85f6e15f35fa13ce5e3d0ed1716c8986b048745emrossign
8b15572442aae50358e392562bd2e1ebfd5b2906matthew        hashmap_clear(h);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (h->buckets != (struct hashmap_entry**) ((uint8_t*) h + ALIGN(sizeof(Hashmap))))
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                free(h->buckets);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        if (h->from_pool)
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo                deallocate_tile(&first_hashmap_tile, h);
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        else
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo                free(h);
6031e9c7eb72435516a6828deb2e97533ed0382dludovicp}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambavoid hashmap_free_free(Hashmap *h) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
8b15572442aae50358e392562bd2e1ebfd5b2906matthew        /* Free the hashmap and all data objects in it, but not the
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba         * keys */
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        if (!h)
ea1dd4f3ba4c9d619a6c413f934507938a804f95ludo                return;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        hashmap_clear_free(h);
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        hashmap_free(h);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthewvoid hashmap_free_free_free(Hashmap *h) {
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        /* Free the hashmap and all data and key objects in it */
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        if (!h)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
8b15572442aae50358e392562bd2e1ebfd5b2906matthew        hashmap_clear_free_free(h);
8b15572442aae50358e392562bd2e1ebfd5b2906matthew        hashmap_free(h);
8b15572442aae50358e392562bd2e1ebfd5b2906matthew}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambavoid hashmap_clear(Hashmap *h) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!h)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        while (h->iterate_list_head)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                remove_entry(h, h->iterate_list_head);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambavoid hashmap_clear_free(Hashmap *h) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        void *p;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!h)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        while ((p = hashmap_steal_first(h)))
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                free(p);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambavoid hashmap_clear_free_free(Hashmap *h) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!h)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        while (h->iterate_list_head) {
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo                void *a, *b;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo                a = h->iterate_list_head->value;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo                b = (void*) h->iterate_list_head->key;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo                remove_entry(h, h->iterate_list_head);
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo                free(a);
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo                free(b);
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        }
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambastatic struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
a776a93d0afa206f307e9140a35497ee255840f2mrossign        struct hashmap_entry *e;
a776a93d0afa206f307e9140a35497ee255840f2mrossign        assert(h);
a776a93d0afa206f307e9140a35497ee255840f2mrossign        assert(hash < h->n_buckets);
a776a93d0afa206f307e9140a35497ee255840f2mrossign
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        for (e = h->buckets[hash]; e; e = e->bucket_next)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                if (h->compare_func(e->key, key) == 0)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                        return e;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
afd6ce83f9ecfa7b375c1f72eb5f279bbd01568cmatthewstatic bool resize_buckets(Hashmap *h) {
afd6ce83f9ecfa7b375c1f72eb5f279bbd01568cmatthew        struct hashmap_entry **n, *i;
afd6ce83f9ecfa7b375c1f72eb5f279bbd01568cmatthew        unsigned m;
afd6ce83f9ecfa7b375c1f72eb5f279bbd01568cmatthew        uint8_t nkey[HASH_KEY_SIZE];
afd6ce83f9ecfa7b375c1f72eb5f279bbd01568cmatthew
afd6ce83f9ecfa7b375c1f72eb5f279bbd01568cmatthew        assert(h);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (_likely_(h->n_entries*4 < h->n_buckets*3))
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew                return false;
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        /* Increase by four */
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        m = (h->n_entries+1)*4-1;
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        /* If we hit OOM we simply risk packed hashmaps... */
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        n = new0(struct hashmap_entry*, m);
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        if (!n)
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew                return false;
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
85f6e15f35fa13ce5e3d0ed1716c8986b048745emrossign        /* Let's use a different randomized hash key for the
85f6e15f35fa13ce5e3d0ed1716c8986b048745emrossign         * extension, so that people cannot guess what we are using
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew         * here forever */
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        get_hash_key(nkey, false);
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        for (i = h->iterate_list_head; i; i = i->iterate_next) {
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew                unsigned long old_bucket, new_bucket;
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew                old_bucket = h->hash_func(i->key, h->hash_key) % h->n_buckets;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew                /* First, drop from old bucket table */
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                if (i->bucket_next)
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew                        i->bucket_next->bucket_previous = i->bucket_previous;
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew                if (i->bucket_previous)
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew                        i->bucket_previous->bucket_next = i->bucket_next;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                else
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                        h->buckets[old_bucket] = i->bucket_next;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                /* Then, add to new backet table */
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                new_bucket = h->hash_func(i->key, nkey)  % m;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                i->bucket_next = n[new_bucket];
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                i->bucket_previous = NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                if (n[new_bucket])
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                        n[new_bucket]->bucket_previous = i;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                n[new_bucket] = i;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        }
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (h->buckets != (struct hashmap_entry**) ((uint8_t*) h + ALIGN(sizeof(Hashmap))))
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                free(h->buckets);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        h->buckets = n;
0d397efc4b781ef5b60108708fa1131467d2c3c8gbellato        h->n_buckets = m;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        memcpy(h->hash_key, nkey, HASH_KEY_SIZE);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return true;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthewint hashmap_put(Hashmap *h, const void *key, void *value) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        struct hashmap_entry *e;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        unsigned hash;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        assert(h);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        hash = bucket_hash(h, key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        e = hash_scan(h, hash, key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (e) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                if (e->value == value)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                        return 0;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return -EEXIST;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        }
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (resize_buckets(h))
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                hash = bucket_hash(h, key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (h->from_pool)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry), 64U);
d729d88914866aa41d5d6dc5e7f6a7fb5f601bc3matthew        else
d729d88914866aa41d5d6dc5e7f6a7fb5f601bc3matthew                e = new(struct hashmap_entry, 1);
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        if (!e)
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew                return -ENOMEM;
d729d88914866aa41d5d6dc5e7f6a7fb5f601bc3matthew
d729d88914866aa41d5d6dc5e7f6a7fb5f601bc3matthew        e->key = key;
d729d88914866aa41d5d6dc5e7f6a7fb5f601bc3matthew        e->value = value;
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew        link_entry(h, e, hash);
f38f1b1dd4d4521b3ab1160332de4f1767e6ddfamatthew
d729d88914866aa41d5d6dc5e7f6a7fb5f601bc3matthew        return 1;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambaint hashmap_replace(Hashmap *h, const void *key, void *value) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        struct hashmap_entry *e;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        unsigned hash;
ea1dd4f3ba4c9d619a6c413f934507938a804f95ludo
ea1dd4f3ba4c9d619a6c413f934507938a804f95ludo        assert(h);
ea1dd4f3ba4c9d619a6c413f934507938a804f95ludo
8b15572442aae50358e392562bd2e1ebfd5b2906matthew        hash = bucket_hash(h, key);
a776a93d0afa206f307e9140a35497ee255840f2mrossign        e = hash_scan(h, hash, key);
a776a93d0afa206f307e9140a35497ee255840f2mrossign        if (e) {
a776a93d0afa206f307e9140a35497ee255840f2mrossign                e->key = key;
a776a93d0afa206f307e9140a35497ee255840f2mrossign                e->value = value;
a776a93d0afa206f307e9140a35497ee255840f2mrossign                return 0;
8b15572442aae50358e392562bd2e1ebfd5b2906matthew        }
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        return hashmap_put(h, key, value);
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo}
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
eef6695bc3b88e10d60477095ebddd4b9499481fpgambaint hashmap_update(Hashmap *h, const void *key, void *value) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        struct hashmap_entry *e;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        unsigned hash;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        assert(h);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        hash = bucket_hash(h, key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        e = hash_scan(h, hash, key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!e)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return -ENOENT;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        e->value = value;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return 0;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo}
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludovoid* hashmap_get(Hashmap *h, const void *key) {
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        unsigned hash;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        struct hashmap_entry *e;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        if (!h)
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo                return NULL;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        hash = bucket_hash(h, key);
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        e = hash_scan(h, hash, key);
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        if (!e)
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo                return NULL;
ea1dd4f3ba4c9d619a6c413f934507938a804f95ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        return e->value;
ea1dd4f3ba4c9d619a6c413f934507938a804f95ludo}
ea1dd4f3ba4c9d619a6c413f934507938a804f95ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludovoid* hashmap_get2(Hashmap *h, const void *key, void **key2) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        unsigned hash;
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac        struct hashmap_entry *e;
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac        if (!h)
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac                return NULL;
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac        hash = bucket_hash(h, key);
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac        e = hash_scan(h, hash, key);
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac        if (!e)
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac                return NULL;
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac        if (key2)
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac                *key2 = (void*) e->key;
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac        return e->value;
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac}
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignacbool hashmap_contains(Hashmap *h, const void *key) {
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac        unsigned hash;
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac        if (!h)
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac                return false;
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac        hash = bucket_hash(h, key);
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac        return !!hash_scan(h, hash, key);
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac}
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignacvoid* hashmap_remove(Hashmap *h, const void *key) {
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac        struct hashmap_entry *e;
d87eec6ea79502a1c14f1d960527ba986dfeb52cJnRouvignac        unsigned hash;
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac        void *data;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!h)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return NULL;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        hash = bucket_hash(h, key);
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        e = hash_scan(h, hash, key);
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        if (!e)
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo                return NULL;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        data = e->value;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        remove_entry(h, e);
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo        return data;
49ec0e527beda838ac41d558df188d2c7fa7a1c8ludo}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambavoid* hashmap_remove2(Hashmap *h, const void *key, void **rkey) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        struct hashmap_entry *e;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        unsigned hash;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        void *data;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!h) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                if (rkey)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                        *rkey = NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        }
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        hash = bucket_hash(h, key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        e = hash_scan(h, hash, key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!e) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                if (rkey)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                        *rkey = NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        }
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        data = e->value;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (rkey)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                *rkey = (void*) e->key;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        remove_entry(h, e);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return data;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambaint hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        struct hashmap_entry *e;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        unsigned old_hash, new_hash;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac        if (!h)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return -ENOENT;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        old_hash = bucket_hash(h, old_key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        e = hash_scan(h, old_hash, old_key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!e)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return -ENOENT;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        new_hash = bucket_hash(h, new_key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (hash_scan(h, new_hash, new_key))
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return -EEXIST;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        unlink_entry(h, e, old_hash);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        e->key = new_key;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        e->value = value;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        link_entry(h, e, new_hash);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return 0;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
bbbf74f3a03a1063865820855dfafd2dc368ce0cpgambaint hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        struct hashmap_entry *e, *k;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        unsigned old_hash, new_hash;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!h)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return -ENOENT;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        old_hash = bucket_hash(h, old_key);
a776a93d0afa206f307e9140a35497ee255840f2mrossign        e = hash_scan(h, old_hash, old_key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!e)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return -ENOENT;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        new_hash = bucket_hash(h, new_key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        k = hash_scan(h, new_hash, new_key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (k)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                if (e != k)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                        remove_entry(h, k);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        unlink_entry(h, e, old_hash);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        e->key = new_key;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        e->value = value;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        link_entry(h, e, new_hash);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return 0;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
91c1c33da74bf7248cbf46057d5721f53fef2cf4matthewvoid* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
91c1c33da74bf7248cbf46057d5721f53fef2cf4matthew        struct hashmap_entry *e;
91c1c33da74bf7248cbf46057d5721f53fef2cf4matthew        unsigned hash;
91c1c33da74bf7248cbf46057d5721f53fef2cf4matthew
91c1c33da74bf7248cbf46057d5721f53fef2cf4matthew        if (!h)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        hash = bucket_hash(h, key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        e = hash_scan(h, hash, key);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!e)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (e->value != value)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        remove_entry(h, e);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return value;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
0d397efc4b781ef5b60108708fa1131467d2c3c8gbellato
eef6695bc3b88e10d60477095ebddd4b9499481fpgambavoid *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        struct hashmap_entry *e;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        assert(i);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!h)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                goto at_end;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (*i == ITERATOR_LAST)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                goto at_end;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (*i == ITERATOR_FIRST && !h->iterate_list_head)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                goto at_end;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (e->iterate_next)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                *i = (Iterator) e->iterate_next;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        else
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                *i = ITERATOR_LAST;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (key)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                *key = e->key;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return e->value;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambaat_end:
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        *i = ITERATOR_LAST;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (key)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                *key = NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return NULL;
0d397efc4b781ef5b60108708fa1131467d2c3c8gbellato}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambavoid *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        struct hashmap_entry *e;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        assert(i);
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!h)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                goto at_beginning;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (*i == ITERATOR_FIRST)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                goto at_beginning;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (*i == ITERATOR_LAST && !h->iterate_list_tail)
91c1c33da74bf7248cbf46057d5721f53fef2cf4matthew                goto at_beginning;
91c1c33da74bf7248cbf46057d5721f53fef2cf4matthew
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (e->iterate_previous)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                *i = (Iterator) e->iterate_previous;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        else
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                *i = ITERATOR_FIRST;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (key)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                *key = e->key;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return e->value;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambaat_beginning:
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        *i = ITERATOR_FIRST;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (key)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                *key = NULL;
d87eec6ea79502a1c14f1d960527ba986dfeb52cJnRouvignac
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return NULL;
df880e8f097ecf074c379e7137f2672437ac858fmatthew}
df880e8f097ecf074c379e7137f2672437ac858fmatthew
df880e8f097ecf074c379e7137f2672437ac858fmatthewvoid *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
df880e8f097ecf074c379e7137f2672437ac858fmatthew        unsigned hash;
df880e8f097ecf074c379e7137f2672437ac858fmatthew        struct hashmap_entry *e;
df880e8f097ecf074c379e7137f2672437ac858fmatthew
df880e8f097ecf074c379e7137f2672437ac858fmatthew        if (!h)
df880e8f097ecf074c379e7137f2672437ac858fmatthew                return NULL;
df880e8f097ecf074c379e7137f2672437ac858fmatthew
df880e8f097ecf074c379e7137f2672437ac858fmatthew        hash = bucket_hash(h, key);
df880e8f097ecf074c379e7137f2672437ac858fmatthew
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        e = hash_scan(h, hash, key);
df880e8f097ecf074c379e7137f2672437ac858fmatthew        if (!e)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return NULL;
df880e8f097ecf074c379e7137f2672437ac858fmatthew
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        *i = (Iterator) e;
df880e8f097ecf074c379e7137f2672437ac858fmatthew
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return e->value;
df880e8f097ecf074c379e7137f2672437ac858fmatthew}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambavoid* hashmap_first(Hashmap *h) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!h)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!h->iterate_list_head)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return h->iterate_list_head->value;
89d54fea9b0d8b41866907a986b578b57dbc8ac3matthew}
89d54fea9b0d8b41866907a986b578b57dbc8ac3matthew
89d54fea9b0d8b41866907a986b578b57dbc8ac3matthewvoid* hashmap_first_key(Hashmap *h) {
89d54fea9b0d8b41866907a986b578b57dbc8ac3matthew
89d54fea9b0d8b41866907a986b578b57dbc8ac3matthew        if (!h)
89d54fea9b0d8b41866907a986b578b57dbc8ac3matthew                return NULL;
89d54fea9b0d8b41866907a986b578b57dbc8ac3matthew
89d54fea9b0d8b41866907a986b578b57dbc8ac3matthew        if (!h->iterate_list_head)
89d54fea9b0d8b41866907a986b578b57dbc8ac3matthew                return NULL;
89d54fea9b0d8b41866907a986b578b57dbc8ac3matthew
89d54fea9b0d8b41866907a986b578b57dbc8ac3matthew        return (void*) h->iterate_list_head->key;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba}
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac
eef6695bc3b88e10d60477095ebddd4b9499481fpgambavoid* hashmap_last(Hashmap *h) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!h)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return NULL;
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!h->iterate_list_tail)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        return h->iterate_list_tail->value;
0b5792318cb29b979a4811a1aa237d35e3919830JnRouvignac}
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgambavoid* hashmap_steal_first(Hashmap *h) {
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        void *data;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!h)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba        if (!h->iterate_list_head)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return NULL;
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba
c1c0b08b5ce89eacff706ff6785d88f5640e96bepgamba        data = h->iterate_list_head->value;
bbbf74f3a03a1063865820855dfafd2dc368ce0cpgamba        remove_entry(h, h->iterate_list_head);
bbbf74f3a03a1063865820855dfafd2dc368ce0cpgamba
bbbf74f3a03a1063865820855dfafd2dc368ce0cpgamba        return data;
bbbf74f3a03a1063865820855dfafd2dc368ce0cpgamba}
bbbf74f3a03a1063865820855dfafd2dc368ce0cpgamba
bbbf74f3a03a1063865820855dfafd2dc368ce0cpgambavoid* hashmap_steal_first_key(Hashmap *h) {
bbbf74f3a03a1063865820855dfafd2dc368ce0cpgamba        void *key;
bbbf74f3a03a1063865820855dfafd2dc368ce0cpgamba
bbbf74f3a03a1063865820855dfafd2dc368ce0cpgamba        if (!h)
bbbf74f3a03a1063865820855dfafd2dc368ce0cpgamba                return NULL;
bbbf74f3a03a1063865820855dfafd2dc368ce0cpgamba
bbbf74f3a03a1063865820855dfafd2dc368ce0cpgamba        if (!h->iterate_list_head)
eef6695bc3b88e10d60477095ebddd4b9499481fpgamba                return NULL;

        key = (void*) h->iterate_list_head->key;
        remove_entry(h, h->iterate_list_head);

        return key;
}

unsigned hashmap_size(Hashmap *h) {

        if (!h)
                return 0;

        return h->n_entries;
}

unsigned hashmap_buckets(Hashmap *h) {

        if (!h)
                return 0;

        return h->n_buckets;
}

bool hashmap_isempty(Hashmap *h) {

        if (!h)
                return true;

        return h->n_entries == 0;
}

int hashmap_merge(Hashmap *h, Hashmap *other) {
        struct hashmap_entry *e;

        assert(h);

        if (!other)
                return 0;

        for (e = other->iterate_list_head; e; e = e->iterate_next) {
                int r;

                r = hashmap_put(h, e->key, e->value);
                if (r < 0 && r != -EEXIST)
                        return r;
        }

        return 0;
}

void hashmap_move(Hashmap *h, Hashmap *other) {
        struct hashmap_entry *e, *n;

        assert(h);

        /* The same as hashmap_merge(), but every new item from other
         * is moved to h. This function is guaranteed to succeed. */

        if (!other)
                return;

        for (e = other->iterate_list_head; e; e = n) {
                unsigned h_hash, other_hash;

                n = e->iterate_next;

                h_hash = bucket_hash(h, e->key);
                if (hash_scan(h, h_hash, e->key))
                        continue;

                other_hash = bucket_hash(other, e->key);
                unlink_entry(other, e, other_hash);
                link_entry(h, e, h_hash);
        }
}

int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
        unsigned h_hash, other_hash;
        struct hashmap_entry *e;

        if (!other)
                return 0;

        assert(h);

        h_hash = bucket_hash(h, key);
        if (hash_scan(h, h_hash, key))
                return -EEXIST;

        other_hash = bucket_hash(other, key);
        e = hash_scan(other, other_hash, key);
        if (!e)
                return -ENOENT;

        unlink_entry(other, e, other_hash);
        link_entry(h, e, h_hash);

        return 0;
}

Hashmap *hashmap_copy(Hashmap *h) {
        Hashmap *copy;

        assert(h);

        copy = hashmap_new(h->hash_func, h->compare_func);
        if (!copy)
                return NULL;

        if (hashmap_merge(copy, h) < 0) {
                hashmap_free(copy);
                return NULL;
        }

        return copy;
}

char **hashmap_get_strv(Hashmap *h) {
        char **sv;
        Iterator it;
        char *item;
        int n;

        sv = new(char*, h->n_entries+1);
        if (!sv)
                return NULL;

        n = 0;
        HASHMAP_FOREACH(item, h, it)
                sv[n++] = item;
        sv[n] = NULL;

        return sv;
}

void *hashmap_next(Hashmap *h, const void *key) {
        unsigned hash;
        struct hashmap_entry *e;

        assert(h);
        assert(key);

        if (!h)
                return NULL;

        hash = bucket_hash(h, key);
        e = hash_scan(h, hash, key);
        if (!e)
                return NULL;

        e = e->iterate_next;
        if (!e)
                return NULL;

        return e->value;
}