perf/util/hashmap.c

0001 // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
0002
0003 /*
0004  * Generic non-thread safe hash map implementation.
0005  *
0006  * Copyright (c) 2019 Facebook
0007  */
0008 #include <stdint.h>
0009 #include <stdlib.h>
0010 #include <stdio.h>
0011 #include <errno.h>
0012 #include <linux/err.h>
0013 #include "hashmap.h"
0014
0015 /* make sure libbpf doesn't use kernel-only integer typedefs */
0016 #pragma GCC poison u8 u16 u32 u64 s8 s16 s32 s64
0017
0018 /* prevent accidental re-addition of reallocarray() */
0019 #pragma GCC poison reallocarray
0020
0021 /* start with 4 buckets */
0022 #define HASHMAP_MIN_CAP_BITS 2
0023
0024 static void hashmap_add_entry(struct hashmap_entry **pprev,
0025                   struct hashmap_entry *entry)
0026 {
0027     entry->next = *pprev;
0028     *pprev = entry;
0029 }
0030
0031 static void hashmap_del_entry(struct hashmap_entry **pprev,
0032                   struct hashmap_entry *entry)
0033 {
0034     *pprev = entry->next;
0035     entry->next = NULL;
0036 }
0037
0038 void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn,
0039            hashmap_equal_fn equal_fn, void *ctx)
0040 {
0041     map->hash_fn = hash_fn;
0042     map->equal_fn = equal_fn;
0043     map->ctx = ctx;
0044
0045     map->buckets = NULL;
0046     map->cap = 0;
0047     map->cap_bits = 0;
0048     map->sz = 0;
0049 }
0050
0051 struct hashmap *hashmap__new(hashmap_hash_fn hash_fn,
0052                  hashmap_equal_fn equal_fn,
0053                  void *ctx)
0054 {
0055     struct hashmap *map = malloc(sizeof(struct hashmap));
0056
0057     if (!map)
0058         return ERR_PTR(-ENOMEM);
0059     hashmap__init(map, hash_fn, equal_fn, ctx);
0060     return map;
0061 }
0062
0063 void hashmap__clear(struct hashmap *map)
0064 {
0065     struct hashmap_entry *cur, *tmp;
0066     size_t bkt;
0067
0068     hashmap__for_each_entry_safe(map, cur, tmp, bkt) {
0069         free(cur);
0070     }
0071     free(map->buckets);
0072     map->buckets = NULL;
0073     map->cap = map->cap_bits = map->sz = 0;
0074 }
0075
0076 void hashmap__free(struct hashmap *map)
0077 {
0078     if (IS_ERR_OR_NULL(map))
0079         return;
0080
0081     hashmap__clear(map);
0082     free(map);
0083 }
0084
0085 size_t hashmap__size(const struct hashmap *map)
0086 {
0087     return map->sz;
0088 }
0089
0090 size_t hashmap__capacity(const struct hashmap *map)
0091 {
0092     return map->cap;
0093 }
0094
0095 static bool hashmap_needs_to_grow(struct hashmap *map)
0096 {
0097     /* grow if empty or more than 75% filled */
0098     return (map->cap == 0) || ((map->sz + 1) * 4 / 3 > map->cap);
0099 }
0100
0101 static int hashmap_grow(struct hashmap *map)
0102 {
0103     struct hashmap_entry **new_buckets;
0104     struct hashmap_entry *cur, *tmp;
0105     size_t new_cap_bits, new_cap;
0106     size_t h, bkt;
0107
0108     new_cap_bits = map->cap_bits + 1;
0109     if (new_cap_bits < HASHMAP_MIN_CAP_BITS)
0110         new_cap_bits = HASHMAP_MIN_CAP_BITS;
0111
0112     new_cap = 1UL << new_cap_bits;
0113     new_buckets = calloc(new_cap, sizeof(new_buckets[0]));
0114     if (!new_buckets)
0115         return -ENOMEM;
0116
0117     hashmap__for_each_entry_safe(map, cur, tmp, bkt) {
0118         h = hash_bits(map->hash_fn(cur->key, map->ctx), new_cap_bits);
0119         hashmap_add_entry(&new_buckets[h], cur);
0120     }
0121
0122     map->cap = new_cap;
0123     map->cap_bits = new_cap_bits;
0124     free(map->buckets);
0125     map->buckets = new_buckets;
0126
0127     return 0;
0128 }
0129
0130 static bool hashmap_find_entry(const struct hashmap *map,
0131                    const void *key, size_t hash,
0132                    struct hashmap_entry ***pprev,
0133                    struct hashmap_entry **entry)
0134 {
0135     struct hashmap_entry *cur, **prev_ptr;
0136
0137     if (!map->buckets)
0138         return false;
0139
0140     for (prev_ptr = &map->buckets[hash], cur = *prev_ptr;
0141          cur;
0142          prev_ptr = &cur->next, cur = cur->next) {
0143         if (map->equal_fn(cur->key, key, map->ctx)) {
0144             if (pprev)
0145                 *pprev = prev_ptr;
0146             *entry = cur;
0147             return true;
0148         }
0149     }
0150
0151     return false;
0152 }
0153
0154 int hashmap__insert(struct hashmap *map, const void *key, void *value,
0155             enum hashmap_insert_strategy strategy,
0156             const void **old_key, void **old_value)
0157 {
0158     struct hashmap_entry *entry;
0159     size_t h;
0160     int err;
0161
0162     if (old_key)
0163         *old_key = NULL;
0164     if (old_value)
0165         *old_value = NULL;
0166
0167     h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
0168     if (strategy != HASHMAP_APPEND &&
0169         hashmap_find_entry(map, key, h, NULL, &entry)) {
0170         if (old_key)
0171             *old_key = entry->key;
0172         if (old_value)
0173             *old_value = entry->value;
0174
0175         if (strategy == HASHMAP_SET || strategy == HASHMAP_UPDATE) {
0176             entry->key = key;
0177             entry->value = value;
0178             return 0;
0179         } else if (strategy == HASHMAP_ADD) {
0180             return -EEXIST;
0181         }
0182     }
0183
0184     if (strategy == HASHMAP_UPDATE)
0185         return -ENOENT;
0186
0187     if (hashmap_needs_to_grow(map)) {
0188         err = hashmap_grow(map);
0189         if (err)
0190             return err;
0191         h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
0192     }
0193
0194     entry = malloc(sizeof(struct hashmap_entry));
0195     if (!entry)
0196         return -ENOMEM;
0197
0198     entry->key = key;
0199     entry->value = value;
0200     hashmap_add_entry(&map->buckets[h], entry);
0201     map->sz++;
0202
0203     return 0;
0204 }
0205
0206 bool hashmap__find(const struct hashmap *map, const void *key, void **value)
0207 {
0208     struct hashmap_entry *entry;
0209     size_t h;
0210
0211     h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
0212     if (!hashmap_find_entry(map, key, h, NULL, &entry))
0213         return false;
0214
0215     if (value)
0216         *value = entry->value;
0217     return true;
0218 }
0219
0220 bool hashmap__delete(struct hashmap *map, const void *key,
0221              const void **old_key, void **old_value)
0222 {
0223     struct hashmap_entry **pprev, *entry;
0224     size_t h;
0225
0226     h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
0227     if (!hashmap_find_entry(map, key, h, &pprev, &entry))
0228         return false;
0229
0230     if (old_key)
0231         *old_key = entry->key;
0232     if (old_value)
0233         *old_value = entry->value;
0234
0235     hashmap_del_entry(pprev, entry);
0236     free(entry);
0237     map->sz--;
0238
0239     return true;
0240 }