1/*	$OpenBSD: hashtable.h,v 1.2 2020/06/08 04:48:14 jsg Exp $	*/
2/*
3 * Copyright (c) 2017 Mark Kettenis
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */
17
18#ifndef _LINUX_HASHTABLE_H
19#define _LINUX_HASHTABLE_H
20
21#include <linux/list.h>
22#include <linux/hash.h>
23
24#define DECLARE_HASHTABLE(name, bits) struct hlist_head name[1 << (bits)]
25
26static inline void
27__hash_init(struct hlist_head *table, u_int size)
28{
29	u_int i;
30
31	for (i = 0; i < size; i++)
32		INIT_HLIST_HEAD(&table[i]);
33}
34
35static inline bool
36__hash_empty(struct hlist_head *table, u_int size)
37{
38	u_int i;
39
40	for (i = 0; i < size; i++) {
41		if (!hlist_empty(&table[i]))
42			return false;
43	}
44
45	return true;
46}
47
48#define __hash(table, key)	&table[key % (nitems(table) - 1)]
49
50#define hash_init(table)	__hash_init(table, nitems(table))
51#define hash_add(table, node, key) \
52	hlist_add_head(node, __hash(table, key))
53#define hash_del(node)		hlist_del_init(node)
54#define hash_empty(table)	__hash_empty(table, nitems(table))
55#define hash_for_each_possible(table, obj, member, key) \
56	hlist_for_each_entry(obj, __hash(table, key), member)
57#define hash_for_each_safe(table, i, tmp, obj, member) 	\
58	for (i = 0; i < nitems(table); i++)		\
59	       hlist_for_each_entry_safe(obj, tmp, &table[i], member)
60
61#endif
62