1e3b92422SAndrii Nakryiko // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) 2e3b92422SAndrii Nakryiko 3e3b92422SAndrii Nakryiko /* 4e3b92422SAndrii Nakryiko * Generic non-thread safe hash map implementation. 5e3b92422SAndrii Nakryiko * 6e3b92422SAndrii Nakryiko * Copyright (c) 2019 Facebook 7e3b92422SAndrii Nakryiko */ 8e3b92422SAndrii Nakryiko #include <stdint.h> 9e3b92422SAndrii Nakryiko #include <stdlib.h> 10e3b92422SAndrii Nakryiko #include <stdio.h> 11e3b92422SAndrii Nakryiko #include <errno.h> 12e3b92422SAndrii Nakryiko #include <linux/err.h> 13e3b92422SAndrii Nakryiko #include "hashmap.h" 14e3b92422SAndrii Nakryiko 151d1a3bcfSAndrii Nakryiko /* make sure libbpf doesn't use kernel-only integer typedefs */ 161d1a3bcfSAndrii Nakryiko #pragma GCC poison u8 u16 u32 u64 s8 s16 s32 s64 171d1a3bcfSAndrii Nakryiko 18e3b92422SAndrii Nakryiko /* start with 4 buckets */ 19e3b92422SAndrii Nakryiko #define HASHMAP_MIN_CAP_BITS 2 20e3b92422SAndrii Nakryiko 21e3b92422SAndrii Nakryiko static void hashmap_add_entry(struct hashmap_entry **pprev, 22e3b92422SAndrii Nakryiko struct hashmap_entry *entry) 23e3b92422SAndrii Nakryiko { 24e3b92422SAndrii Nakryiko entry->next = *pprev; 25e3b92422SAndrii Nakryiko *pprev = entry; 26e3b92422SAndrii Nakryiko } 27e3b92422SAndrii Nakryiko 28e3b92422SAndrii Nakryiko static void hashmap_del_entry(struct hashmap_entry **pprev, 29e3b92422SAndrii Nakryiko struct hashmap_entry *entry) 30e3b92422SAndrii Nakryiko { 31e3b92422SAndrii Nakryiko *pprev = entry->next; 32e3b92422SAndrii Nakryiko entry->next = NULL; 33e3b92422SAndrii Nakryiko } 34e3b92422SAndrii Nakryiko 35e3b92422SAndrii Nakryiko void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn, 36e3b92422SAndrii Nakryiko hashmap_equal_fn equal_fn, void *ctx) 37e3b92422SAndrii Nakryiko { 38e3b92422SAndrii Nakryiko map->hash_fn = hash_fn; 39e3b92422SAndrii Nakryiko map->equal_fn = equal_fn; 40e3b92422SAndrii Nakryiko map->ctx = ctx; 41e3b92422SAndrii Nakryiko 42e3b92422SAndrii Nakryiko map->buckets = NULL; 43e3b92422SAndrii Nakryiko map->cap = 0; 44e3b92422SAndrii Nakryiko map->cap_bits = 0; 45e3b92422SAndrii Nakryiko map->sz = 0; 46e3b92422SAndrii Nakryiko } 47e3b92422SAndrii Nakryiko 48e3b92422SAndrii Nakryiko struct hashmap *hashmap__new(hashmap_hash_fn hash_fn, 49e3b92422SAndrii Nakryiko hashmap_equal_fn equal_fn, 50e3b92422SAndrii Nakryiko void *ctx) 51e3b92422SAndrii Nakryiko { 52e3b92422SAndrii Nakryiko struct hashmap *map = malloc(sizeof(struct hashmap)); 53e3b92422SAndrii Nakryiko 54e3b92422SAndrii Nakryiko if (!map) 55e3b92422SAndrii Nakryiko return ERR_PTR(-ENOMEM); 56e3b92422SAndrii Nakryiko hashmap__init(map, hash_fn, equal_fn, ctx); 57e3b92422SAndrii Nakryiko return map; 58e3b92422SAndrii Nakryiko } 59e3b92422SAndrii Nakryiko 60e3b92422SAndrii Nakryiko void hashmap__clear(struct hashmap *map) 61e3b92422SAndrii Nakryiko { 62229bf8bfSAndrii Nakryiko struct hashmap_entry *cur, *tmp; 63229bf8bfSAndrii Nakryiko int bkt; 64229bf8bfSAndrii Nakryiko 65229bf8bfSAndrii Nakryiko hashmap__for_each_entry_safe(map, cur, tmp, bkt) { 66229bf8bfSAndrii Nakryiko free(cur); 67229bf8bfSAndrii Nakryiko } 68e3b92422SAndrii Nakryiko free(map->buckets); 69229bf8bfSAndrii Nakryiko map->buckets = NULL; 70e3b92422SAndrii Nakryiko map->cap = map->cap_bits = map->sz = 0; 71e3b92422SAndrii Nakryiko } 72e3b92422SAndrii Nakryiko 73e3b92422SAndrii Nakryiko void hashmap__free(struct hashmap *map) 74e3b92422SAndrii Nakryiko { 75e3b92422SAndrii Nakryiko if (!map) 76e3b92422SAndrii Nakryiko return; 77e3b92422SAndrii Nakryiko 78e3b92422SAndrii Nakryiko hashmap__clear(map); 79e3b92422SAndrii Nakryiko free(map); 80e3b92422SAndrii Nakryiko } 81e3b92422SAndrii Nakryiko 82e3b92422SAndrii Nakryiko size_t hashmap__size(const struct hashmap *map) 83e3b92422SAndrii Nakryiko { 84e3b92422SAndrii Nakryiko return map->sz; 85e3b92422SAndrii Nakryiko } 86e3b92422SAndrii Nakryiko 87e3b92422SAndrii Nakryiko size_t hashmap__capacity(const struct hashmap *map) 88e3b92422SAndrii Nakryiko { 89e3b92422SAndrii Nakryiko return map->cap; 90e3b92422SAndrii Nakryiko } 91e3b92422SAndrii Nakryiko 92e3b92422SAndrii Nakryiko static bool hashmap_needs_to_grow(struct hashmap *map) 93e3b92422SAndrii Nakryiko { 94e3b92422SAndrii Nakryiko /* grow if empty or more than 75% filled */ 95e3b92422SAndrii Nakryiko return (map->cap == 0) || ((map->sz + 1) * 4 / 3 > map->cap); 96e3b92422SAndrii Nakryiko } 97e3b92422SAndrii Nakryiko 98e3b92422SAndrii Nakryiko static int hashmap_grow(struct hashmap *map) 99e3b92422SAndrii Nakryiko { 100e3b92422SAndrii Nakryiko struct hashmap_entry **new_buckets; 101e3b92422SAndrii Nakryiko struct hashmap_entry *cur, *tmp; 102e3b92422SAndrii Nakryiko size_t new_cap_bits, new_cap; 103e3b92422SAndrii Nakryiko size_t h; 104e3b92422SAndrii Nakryiko int bkt; 105e3b92422SAndrii Nakryiko 106e3b92422SAndrii Nakryiko new_cap_bits = map->cap_bits + 1; 107e3b92422SAndrii Nakryiko if (new_cap_bits < HASHMAP_MIN_CAP_BITS) 108e3b92422SAndrii Nakryiko new_cap_bits = HASHMAP_MIN_CAP_BITS; 109e3b92422SAndrii Nakryiko 110e3b92422SAndrii Nakryiko new_cap = 1UL << new_cap_bits; 111e3b92422SAndrii Nakryiko new_buckets = calloc(new_cap, sizeof(new_buckets[0])); 112e3b92422SAndrii Nakryiko if (!new_buckets) 113e3b92422SAndrii Nakryiko return -ENOMEM; 114e3b92422SAndrii Nakryiko 115e3b92422SAndrii Nakryiko hashmap__for_each_entry_safe(map, cur, tmp, bkt) { 116e3b92422SAndrii Nakryiko h = hash_bits(map->hash_fn(cur->key, map->ctx), new_cap_bits); 117e3b92422SAndrii Nakryiko hashmap_add_entry(&new_buckets[h], cur); 118e3b92422SAndrii Nakryiko } 119e3b92422SAndrii Nakryiko 120e3b92422SAndrii Nakryiko map->cap = new_cap; 121e3b92422SAndrii Nakryiko map->cap_bits = new_cap_bits; 122e3b92422SAndrii Nakryiko free(map->buckets); 123e3b92422SAndrii Nakryiko map->buckets = new_buckets; 124e3b92422SAndrii Nakryiko 125e3b92422SAndrii Nakryiko return 0; 126e3b92422SAndrii Nakryiko } 127e3b92422SAndrii Nakryiko 128e3b92422SAndrii Nakryiko static bool hashmap_find_entry(const struct hashmap *map, 129e3b92422SAndrii Nakryiko const void *key, size_t hash, 130e3b92422SAndrii Nakryiko struct hashmap_entry ***pprev, 131e3b92422SAndrii Nakryiko struct hashmap_entry **entry) 132e3b92422SAndrii Nakryiko { 133e3b92422SAndrii Nakryiko struct hashmap_entry *cur, **prev_ptr; 134e3b92422SAndrii Nakryiko 135e3b92422SAndrii Nakryiko if (!map->buckets) 136e3b92422SAndrii Nakryiko return false; 137e3b92422SAndrii Nakryiko 138e3b92422SAndrii Nakryiko for (prev_ptr = &map->buckets[hash], cur = *prev_ptr; 139e3b92422SAndrii Nakryiko cur; 140e3b92422SAndrii Nakryiko prev_ptr = &cur->next, cur = cur->next) { 141e3b92422SAndrii Nakryiko if (map->equal_fn(cur->key, key, map->ctx)) { 142e3b92422SAndrii Nakryiko if (pprev) 143e3b92422SAndrii Nakryiko *pprev = prev_ptr; 144e3b92422SAndrii Nakryiko *entry = cur; 145e3b92422SAndrii Nakryiko return true; 146e3b92422SAndrii Nakryiko } 147e3b92422SAndrii Nakryiko } 148e3b92422SAndrii Nakryiko 149e3b92422SAndrii Nakryiko return false; 150e3b92422SAndrii Nakryiko } 151e3b92422SAndrii Nakryiko 152e3b92422SAndrii Nakryiko int hashmap__insert(struct hashmap *map, const void *key, void *value, 153e3b92422SAndrii Nakryiko enum hashmap_insert_strategy strategy, 154e3b92422SAndrii Nakryiko const void **old_key, void **old_value) 155e3b92422SAndrii Nakryiko { 156e3b92422SAndrii Nakryiko struct hashmap_entry *entry; 157e3b92422SAndrii Nakryiko size_t h; 158e3b92422SAndrii Nakryiko int err; 159e3b92422SAndrii Nakryiko 160e3b92422SAndrii Nakryiko if (old_key) 161e3b92422SAndrii Nakryiko *old_key = NULL; 162e3b92422SAndrii Nakryiko if (old_value) 163e3b92422SAndrii Nakryiko *old_value = NULL; 164e3b92422SAndrii Nakryiko 165e3b92422SAndrii Nakryiko h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits); 166e3b92422SAndrii Nakryiko if (strategy != HASHMAP_APPEND && 167e3b92422SAndrii Nakryiko hashmap_find_entry(map, key, h, NULL, &entry)) { 168e3b92422SAndrii Nakryiko if (old_key) 169e3b92422SAndrii Nakryiko *old_key = entry->key; 170e3b92422SAndrii Nakryiko if (old_value) 171e3b92422SAndrii Nakryiko *old_value = entry->value; 172e3b92422SAndrii Nakryiko 173e3b92422SAndrii Nakryiko if (strategy == HASHMAP_SET || strategy == HASHMAP_UPDATE) { 174e3b92422SAndrii Nakryiko entry->key = key; 175e3b92422SAndrii Nakryiko entry->value = value; 176e3b92422SAndrii Nakryiko return 0; 177e3b92422SAndrii Nakryiko } else if (strategy == HASHMAP_ADD) { 178e3b92422SAndrii Nakryiko return -EEXIST; 179e3b92422SAndrii Nakryiko } 180e3b92422SAndrii Nakryiko } 181e3b92422SAndrii Nakryiko 182e3b92422SAndrii Nakryiko if (strategy == HASHMAP_UPDATE) 183e3b92422SAndrii Nakryiko return -ENOENT; 184e3b92422SAndrii Nakryiko 185e3b92422SAndrii Nakryiko if (hashmap_needs_to_grow(map)) { 186e3b92422SAndrii Nakryiko err = hashmap_grow(map); 187e3b92422SAndrii Nakryiko if (err) 188e3b92422SAndrii Nakryiko return err; 189e3b92422SAndrii Nakryiko h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits); 190e3b92422SAndrii Nakryiko } 191e3b92422SAndrii Nakryiko 192e3b92422SAndrii Nakryiko entry = malloc(sizeof(struct hashmap_entry)); 193e3b92422SAndrii Nakryiko if (!entry) 194e3b92422SAndrii Nakryiko return -ENOMEM; 195e3b92422SAndrii Nakryiko 196e3b92422SAndrii Nakryiko entry->key = key; 197e3b92422SAndrii Nakryiko entry->value = value; 198e3b92422SAndrii Nakryiko hashmap_add_entry(&map->buckets[h], entry); 199e3b92422SAndrii Nakryiko map->sz++; 200e3b92422SAndrii Nakryiko 201e3b92422SAndrii Nakryiko return 0; 202e3b92422SAndrii Nakryiko } 203e3b92422SAndrii Nakryiko 204e3b92422SAndrii Nakryiko bool hashmap__find(const struct hashmap *map, const void *key, void **value) 205e3b92422SAndrii Nakryiko { 206e3b92422SAndrii Nakryiko struct hashmap_entry *entry; 207e3b92422SAndrii Nakryiko size_t h; 208e3b92422SAndrii Nakryiko 209e3b92422SAndrii Nakryiko h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits); 210e3b92422SAndrii Nakryiko if (!hashmap_find_entry(map, key, h, NULL, &entry)) 211e3b92422SAndrii Nakryiko return false; 212e3b92422SAndrii Nakryiko 213e3b92422SAndrii Nakryiko if (value) 214e3b92422SAndrii Nakryiko *value = entry->value; 215e3b92422SAndrii Nakryiko return true; 216e3b92422SAndrii Nakryiko } 217e3b92422SAndrii Nakryiko 218e3b92422SAndrii Nakryiko bool hashmap__delete(struct hashmap *map, const void *key, 219e3b92422SAndrii Nakryiko const void **old_key, void **old_value) 220e3b92422SAndrii Nakryiko { 221e3b92422SAndrii Nakryiko struct hashmap_entry **pprev, *entry; 222e3b92422SAndrii Nakryiko size_t h; 223e3b92422SAndrii Nakryiko 224e3b92422SAndrii Nakryiko h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits); 225e3b92422SAndrii Nakryiko if (!hashmap_find_entry(map, key, h, &pprev, &entry)) 226e3b92422SAndrii Nakryiko return false; 227e3b92422SAndrii Nakryiko 228e3b92422SAndrii Nakryiko if (old_key) 229e3b92422SAndrii Nakryiko *old_key = entry->key; 230e3b92422SAndrii Nakryiko if (old_value) 231e3b92422SAndrii Nakryiko *old_value = entry->value; 232e3b92422SAndrii Nakryiko 233e3b92422SAndrii Nakryiko hashmap_del_entry(pprev, entry); 234e3b92422SAndrii Nakryiko free(entry); 235e3b92422SAndrii Nakryiko map->sz--; 236e3b92422SAndrii Nakryiko 237e3b92422SAndrii Nakryiko return true; 238e3b92422SAndrii Nakryiko } 239e3b92422SAndrii Nakryiko 240