Something went wrong. Try again.
Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
/* * Generic non-thread safe hash map implementation. * * Copyright (c) 2019 Facebook */#include <stdint.h>#include <stdlib.h>#include <stdio.h>#include <errno.h>#include <linux/err.h>#include "hashmap.h"
/* make sure libbpf doesn't use kernel-only integer typedefs */#pragma GCC poison u8 u16 u32 u64 s8 s16 s32 s64
/* prevent accidental re-addition of reallocarray() */#pragma GCC poison reallocarray
/* start with 4 buckets */#define HASHMAP_MIN_CAP_BITS 2
static void hashmap_add_entry(struct hashmap_entry **pprev, struct hashmap_entry *entry){ entry->next = *pprev; *pprev = entry;}
static void hashmap_del_entry(struct hashmap_entry **pprev, struct hashmap_entry *entry){ *pprev = entry->next; entry->next = NULL;}
void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn, hashmap_equal_fn equal_fn, void *ctx){ map->hash_fn = hash_fn; map->equal_fn = equal_fn; map->ctx = ctx;
map->buckets = NULL; map->cap = 0; map->cap_bits = 0; map->sz = 0;}
struct hashmap *hashmap__new(hashmap_hash_fn hash_fn, hashmap_equal_fn equal_fn, void *ctx){ struct hashmap *map = malloc(sizeof(struct hashmap));
if (!map) return ERR_PTR(-ENOMEM); hashmap__init(map, hash_fn, equal_fn, ctx); return map;}
void hashmap__clear(struct hashmap *map){ struct hashmap_entry *cur, *tmp; size_t bkt;
hashmap__for_each_entry_safe(map, cur, tmp, bkt) { free(cur); } free(map->buckets); map->buckets = NULL; map->cap = map->cap_bits = map->sz = 0;}
void hashmap__free(struct hashmap *map){ if (IS_ERR_OR_NULL(map)) return;
hashmap__clear(map); free(map);}
size_t hashmap__size(const struct hashmap *map){ return map->sz;}
size_t hashmap__capacity(const struct hashmap *map){ return map->cap;}
static bool hashmap_needs_to_grow(struct hashmap *map){ /* grow if empty or more than 75% filled */ return (map->cap == 0) || ((map->sz + 1) * 4 / 3 > map->cap);}
static int hashmap_grow(struct hashmap *map){ struct hashmap_entry **new_buckets; struct hashmap_entry *cur, *tmp; size_t new_cap_bits, new_cap; size_t h, bkt;
new_cap_bits = map->cap_bits + 1; if (new_cap_bits < HASHMAP_MIN_CAP_BITS) new_cap_bits = HASHMAP_MIN_CAP_BITS;
new_cap = 1UL << new_cap_bits; new_buckets = calloc(new_cap, sizeof(new_buckets[0])); if (!new_buckets) return -ENOMEM;
hashmap__for_each_entry_safe(map, cur, tmp, bkt) { h = hash_bits(map->hash_fn(cur->key, map->ctx), new_cap_bits); hashmap_add_entry(&new_buckets[h], cur); }
map->cap = new_cap; map->cap_bits = new_cap_bits; free(map->buckets); map->buckets = new_buckets;
return 0;}
static bool hashmap_find_entry(const struct hashmap *map, const long key, size_t hash, struct hashmap_entry ***pprev, struct hashmap_entry **entry){ struct hashmap_entry *cur, **prev_ptr;
if (!map->buckets) return false;
for (prev_ptr = &map->buckets[hash], cur = *prev_ptr; cur; prev_ptr = &cur->next, cur = cur->next) { if (map->equal_fn(cur->key, key, map->ctx)) { if (pprev) *pprev = prev_ptr; *entry = cur; return true; } }
return false;}
int hashmap_insert(struct hashmap *map, long key, long value, enum hashmap_insert_strategy strategy, long *old_key, long *old_value){ struct hashmap_entry *entry; size_t h; int err;
if (old_key) *old_key = 0; if (old_value) *old_value = 0;
h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits); if (strategy != HASHMAP_APPEND && hashmap_find_entry(map, key, h, NULL, &entry)) { if (old_key) *old_key = entry->key; if (old_value) *old_value = entry->value;
if (strategy == HASHMAP_SET || strategy == HASHMAP_UPDATE) { entry->key = key; entry->value = value; return 0; } else if (strategy == HASHMAP_ADD) { return -EEXIST; } }
if (strategy == HASHMAP_UPDATE) return -ENOENT;
if (hashmap_needs_to_grow(map)) { err = hashmap_grow(map); if (err) return err; h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits); }
entry = malloc(sizeof(struct hashmap_entry)); if (!entry) return -ENOMEM;
entry->key = key; entry->value = value; hashmap_add_entry(&map->buckets[h], entry); map->sz++;
return 0;}
bool hashmap_find(const struct hashmap *map, long key, long *value){ struct hashmap_entry *entry; size_t h;
h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits); if (!hashmap_find_entry(map, key, h, NULL, &entry)) return false;
if (value) *value = entry->value; return true;}
bool hashmap_delete(struct hashmap *map, long key, long *old_key, long *old_value){ struct hashmap_entry **pprev, *entry; size_t h;
h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits); if (!hashmap_find_entry(map, key, h, &pprev, &entry)) return false;
if (old_key) *old_key = entry->key; if (old_value) *old_value = entry->value;
hashmap_del_entry(pprev, entry); free(entry); map->sz--;
return true;}