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#ifndef __LIBBPF_HASHMAP_H
  9#define __LIBBPF_HASHMAP_H
 10
 11#include <stdbool.h>
 12#include <stddef.h>
 13#include <limits.h>
 14
 15static inline size_t hash_bits(size_t h, int bits)
 16{
 17	/* shuffle bits and return requested number of upper bits */
 18#if (__SIZEOF_SIZE_T__ == __SIZEOF_LONG_LONG__)
 19	/* LP64 case */
 20	return (h * 11400714819323198485llu) >> (__SIZEOF_LONG_LONG__ * 8 - bits);
 21#elif (__SIZEOF_SIZE_T__ <= __SIZEOF_LONG__)
 22	return (h * 2654435769lu) >> (__SIZEOF_LONG__ * 8 - bits);
 23#else
 24#	error "Unsupported size_t size"
 25#endif
 26}
 27
 28typedef size_t (*hashmap_hash_fn)(const void *key, void *ctx);
 29typedef bool (*hashmap_equal_fn)(const void *key1, const void *key2, void *ctx);
 30
 31struct hashmap_entry {
 32	const void *key;
 33	void *value;
 34	struct hashmap_entry *next;
 35};
 36
 37struct hashmap {
 38	hashmap_hash_fn hash_fn;
 39	hashmap_equal_fn equal_fn;
 40	void *ctx;
 41
 42	struct hashmap_entry **buckets;
 43	size_t cap;
 44	size_t cap_bits;
 45	size_t sz;
 46};
 47
 48#define HASHMAP_INIT(hash_fn, equal_fn, ctx) {	\
 49	.hash_fn = (hash_fn),			\
 50	.equal_fn = (equal_fn),			\
 51	.ctx = (ctx),				\
 52	.buckets = NULL,			\
 53	.cap = 0,				\
 54	.cap_bits = 0,				\
 55	.sz = 0,				\
 56}
 57
 58void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn,
 59		   hashmap_equal_fn equal_fn, void *ctx);
 60struct hashmap *hashmap__new(hashmap_hash_fn hash_fn,
 61			     hashmap_equal_fn equal_fn,
 62			     void *ctx);
 63void hashmap__clear(struct hashmap *map);
 64void hashmap__free(struct hashmap *map);
 65
 66size_t hashmap__size(const struct hashmap *map);
 67size_t hashmap__capacity(const struct hashmap *map);
 68
 69/*
 70 * Hashmap insertion strategy:
 71 * - HASHMAP_ADD - only add key/value if key doesn't exist yet;
 72 * - HASHMAP_SET - add key/value pair if key doesn't exist yet; otherwise,
 73 *   update value;
 74 * - HASHMAP_UPDATE - update value, if key already exists; otherwise, do
 75 *   nothing and return -ENOENT;
 76 * - HASHMAP_APPEND - always add key/value pair, even if key already exists.
 77 *   This turns hashmap into a multimap by allowing multiple values to be
 78 *   associated with the same key. Most useful read API for such hashmap is
 79 *   hashmap__for_each_key_entry() iteration. If hashmap__find() is still
 80 *   used, it will return last inserted key/value entry (first in a bucket
 81 *   chain).
 82 */
 83enum hashmap_insert_strategy {
 84	HASHMAP_ADD,
 85	HASHMAP_SET,
 86	HASHMAP_UPDATE,
 87	HASHMAP_APPEND,
 88};
 89
 90/*
 91 * hashmap__insert() adds key/value entry w/ various semantics, depending on
 92 * provided strategy value. If a given key/value pair replaced already
 93 * existing key/value pair, both old key and old value will be returned
 94 * through old_key and old_value to allow calling code do proper memory
 95 * management.
 96 */
 97int hashmap__insert(struct hashmap *map, const void *key, void *value,
 98		    enum hashmap_insert_strategy strategy,
 99		    const void **old_key, void **old_value);
100
101static inline int hashmap__add(struct hashmap *map,
102			       const void *key, void *value)
103{
104	return hashmap__insert(map, key, value, HASHMAP_ADD, NULL, NULL);
105}
106
107static inline int hashmap__set(struct hashmap *map,
108			       const void *key, void *value,
109			       const void **old_key, void **old_value)
110{
111	return hashmap__insert(map, key, value, HASHMAP_SET,
112			       old_key, old_value);
113}
114
115static inline int hashmap__update(struct hashmap *map,
116				  const void *key, void *value,
117				  const void **old_key, void **old_value)
118{
119	return hashmap__insert(map, key, value, HASHMAP_UPDATE,
120			       old_key, old_value);
121}
122
123static inline int hashmap__append(struct hashmap *map,
124				  const void *key, void *value)
125{
126	return hashmap__insert(map, key, value, HASHMAP_APPEND, NULL, NULL);
127}
128
129bool hashmap__delete(struct hashmap *map, const void *key,
130		     const void **old_key, void **old_value);
131
132bool hashmap__find(const struct hashmap *map, const void *key, void **value);
133
134/*
135 * hashmap__for_each_entry - iterate over all entries in hashmap
136 * @map: hashmap to iterate
137 * @cur: struct hashmap_entry * used as a loop cursor
138 * @bkt: integer used as a bucket loop cursor
139 */
140#define hashmap__for_each_entry(map, cur, bkt)				    \
141	for (bkt = 0; bkt < map->cap; bkt++)				    \
142		for (cur = map->buckets[bkt]; cur; cur = cur->next)
143
144/*
145 * hashmap__for_each_entry_safe - iterate over all entries in hashmap, safe
146 * against removals
147 * @map: hashmap to iterate
148 * @cur: struct hashmap_entry * used as a loop cursor
149 * @tmp: struct hashmap_entry * used as a temporary next cursor storage
150 * @bkt: integer used as a bucket loop cursor
151 */
152#define hashmap__for_each_entry_safe(map, cur, tmp, bkt)		    \
153	for (bkt = 0; bkt < map->cap; bkt++)				    \
154		for (cur = map->buckets[bkt];				    \
155		     cur && ({tmp = cur->next; true; });		    \
156		     cur = tmp)
157
158/*
159 * hashmap__for_each_key_entry - iterate over entries associated with given key
160 * @map: hashmap to iterate
161 * @cur: struct hashmap_entry * used as a loop cursor
162 * @key: key to iterate entries for
163 */
164#define hashmap__for_each_key_entry(map, cur, _key)			    \
165	for (cur = ({ size_t bkt = hash_bits(map->hash_fn((_key), map->ctx),\
166					     map->cap_bits);		    \
167		     map->buckets ? map->buckets[bkt] : NULL; });	    \
168	     cur;							    \
169	     cur = cur->next)						    \
170		if (map->equal_fn(cur->key, (_key), map->ctx))
171
172#define hashmap__for_each_key_entry_safe(map, cur, tmp, _key)		    \
173	for (cur = ({ size_t bkt = hash_bits(map->hash_fn((_key), map->ctx),\
174					     map->cap_bits);		    \
175		     cur = map->buckets ? map->buckets[bkt] : NULL; });	    \
176	     cur && ({ tmp = cur->next; true; });			    \
177	     cur = tmp)							    \
178		if (map->equal_fn(cur->key, (_key), map->ctx))
179
180#endif /* __LIBBPF_HASHMAP_H */