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