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