tools/perf/util/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         struct hashmap_entry *cur, *tmp;
  63         size_t bkt;
  64
  65         hashmap__for_each_entry_safe(map, cur, tmp, bkt) {
  66                 free(cur);
  67         }
  68         free(map->buckets);
  69         map->buckets = NULL;
  70         map->cap = map->cap_bits = map->sz = 0;
  71 }
  72
  73 void hashmap__free(struct hashmap *map)
  74 {
  75         if (!map)
  76                 return;
  77
  78         hashmap__clear(map);
  79         free(map);
  80 }
  81
  82 size_t hashmap__size(const struct hashmap *map)
  83 {
  84         return map->sz;
  85 }
  86
  87 size_t hashmap__capacity(const struct hashmap *map)
  88 {
  89         return map->cap;
  90 }
  91
  92 static bool hashmap_needs_to_grow(struct hashmap *map)
  93 {
  94         /* grow if empty or more than 75% filled */
  95         return (map->cap == 0) || ((map->sz + 1) * 4 / 3 > map->cap);
  96 }
  97
  98 static int hashmap_grow(struct hashmap *map)
  99 {
 100         struct hashmap_entry **new_buckets;
 101         struct hashmap_entry *cur, *tmp;
 102         size_t new_cap_bits, new_cap;
 103         size_t h, bkt;
 104
 105         new_cap_bits = map->cap_bits + 1;
 106         if (new_cap_bits < HASHMAP_MIN_CAP_BITS)
 107                 new_cap_bits = HASHMAP_MIN_CAP_BITS;
 108
 109         new_cap = 1UL << new_cap_bits;
 110         new_buckets = calloc(new_cap, sizeof(new_buckets[0]));
 111         if (!new_buckets)
 112                 return -ENOMEM;
 113
 114         hashmap__for_each_entry_safe(map, cur, tmp, bkt) {
 115                 h = hash_bits(map->hash_fn(cur->key, map->ctx), new_cap_bits);
 116                 hashmap_add_entry(&new_buckets[h], cur);
 117         }
 118
 119         map->cap = new_cap;
 120         map->cap_bits = new_cap_bits;
 121         free(map->buckets);
 122         map->buckets = new_buckets;
 123
 124         return 0;
 125 }
 126
 127 static bool hashmap_find_entry(const struct hashmap *map,
 128                                const void *key, size_t hash,
 129                                struct hashmap_entry ***pprev,
 130                                struct hashmap_entry **entry)
 131 {
 132         struct hashmap_entry *cur, **prev_ptr;
 133
 134         if (!map->buckets)
 135                 return false;
 136
 137         for (prev_ptr = &map->buckets[hash], cur = *prev_ptr;
 138              cur;
 139              prev_ptr = &cur->next, cur = cur->next) {
 140                 if (map->equal_fn(cur->key, key, map->ctx)) {
 141                         if (pprev)
 142                                 *pprev = prev_ptr;
 143                         *entry = cur;
 144                         return true;
 145                 }
 146         }
 147
 148         return false;
 149 }
 150
 151 int hashmap__insert(struct hashmap *map, const void *key, void *value,
 152                     enum hashmap_insert_strategy strategy,
 153                     const void **old_key, void **old_value)
 154 {
 155         struct hashmap_entry *entry;
 156         size_t h;
 157         int err;
 158
 159         if (old_key)
 160                 *old_key = NULL;
 161         if (old_value)
 162                 *old_value = NULL;
 163
 164         h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
 165         if (strategy != HASHMAP_APPEND &&
 166             hashmap_find_entry(map, key, h, NULL, &entry)) {
 167                 if (old_key)
 168                         *old_key = entry->key;
 169                 if (old_value)
 170                         *old_value = entry->value;
 171
 172                 if (strategy == HASHMAP_SET || strategy == HASHMAP_UPDATE) {
 173                         entry->key = key;
 174                         entry->value = value;
 175                         return 0;
 176                 } else if (strategy == HASHMAP_ADD) {
 177                         return -EEXIST;
 178                 }
 179         }
 180
 181         if (strategy == HASHMAP_UPDATE)
 182                 return -ENOENT;
 183
 184         if (hashmap_needs_to_grow(map)) {
 185                 err = hashmap_grow(map);
 186                 if (err)
 187                         return err;
 188                 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
 189         }
 190
 191         entry = malloc(sizeof(struct hashmap_entry));
 192         if (!entry)
 193                 return -ENOMEM;
 194
 195         entry->key = key;
 196         entry->value = value;
 197         hashmap_add_entry(&map->buckets[h], entry);
 198         map->sz++;
 199
 200         return 0;
 201 }
 202
 203 bool hashmap__find(const struct hashmap *map, const void *key, void **value)
 204 {
 205         struct hashmap_entry *entry;
 206         size_t h;
 207
 208         h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
 209         if (!hashmap_find_entry(map, key, h, NULL, &entry))
 210                 return false;
 211
 212         if (value)
 213                 *value = entry->value;
 214         return true;
 215 }
 216
 217 bool hashmap__delete(struct hashmap *map, const void *key,
 218                      const void **old_key, void **old_value)
 219 {
 220         struct hashmap_entry **pprev, *entry;
 221         size_t h;
 222
 223         h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
 224         if (!hashmap_find_entry(map, key, h, &pprev, &entry))
 225                 return false;
 226
 227         if (old_key)
 228                 *old_key = entry->key;
 229         if (old_value)
 230                 *old_value = entry->value;
 231
 232         hashmap_del_entry(pprev, entry);
 233         free(entry);
 234         map->sz--;
 235
 236         return true;
 237 }
 238