tools/lib/bpf/hashmap.c

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