1 /* SPDX-License-Identifier: GPL-2.0 */
2 /*
3  * A hash table (hashtab) maintains associations between
4  * key values and datum values.  The type of the key values
5  * and the type of the datum values is arbitrary.  The
6  * functions for hash computation and key comparison are
7  * provided by the creator of the table.
8  *
9  * Author : Stephen Smalley, <sds@tycho.nsa.gov>
10  */
11 #ifndef _SS_HASHTAB_H_
12 #define _SS_HASHTAB_H_
13 
14 #include <linux/types.h>
15 #include <linux/errno.h>
16 #include <linux/sched.h>
17 
18 #define HASHTAB_MAX_NODES	U32_MAX
19 
20 struct hashtab_key_params {
21 	u32 (*hash)(const void *key);	/* hash function */
22 	int (*cmp)(const void *key1, const void *key2);
23 					/* key comparison function */
24 };
25 
26 struct hashtab_node {
27 	void *key;
28 	void *datum;
29 	struct hashtab_node *next;
30 };
31 
32 struct hashtab {
33 	struct hashtab_node **htable;	/* hash table */
34 	u32 size;			/* number of slots in hash table */
35 	u32 nel;			/* number of elements in hash table */
36 };
37 
38 struct hashtab_info {
39 	u32 slots_used;
40 	u32 max_chain_len;
41 };
42 
43 /*
44  * Initializes a new hash table with the specified characteristics.
45  *
46  * Returns -ENOMEM if insufficient space is available or 0 otherwise.
47  */
48 int hashtab_init(struct hashtab *h, u32 nel_hint);
49 
50 int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
51 		     void *key, void *datum);
52 
53 /*
54  * Inserts the specified (key, datum) pair into the specified hash table.
55  *
56  * Returns -ENOMEM on memory allocation error,
57  * -EEXIST if there is already an entry with the same key,
58  * -EINVAL for general errors or
59   0 otherwise.
60  */
hashtab_insert(struct hashtab * h,void * key,void * datum,struct hashtab_key_params key_params)61 static inline int hashtab_insert(struct hashtab *h, void *key, void *datum,
62 				 struct hashtab_key_params key_params)
63 {
64 	u32 hvalue;
65 	struct hashtab_node *prev, *cur;
66 
67 	cond_resched();
68 
69 	if (!h->size || h->nel == HASHTAB_MAX_NODES)
70 		return -EINVAL;
71 
72 	hvalue = key_params.hash(key) & (h->size - 1);
73 	prev = NULL;
74 	cur = h->htable[hvalue];
75 	while (cur) {
76 		int cmp = key_params.cmp(key, cur->key);
77 
78 		if (cmp == 0)
79 			return -EEXIST;
80 		if (cmp < 0)
81 			break;
82 		prev = cur;
83 		cur = cur->next;
84 	}
85 
86 	return __hashtab_insert(h, prev ? &prev->next : &h->htable[hvalue],
87 				key, datum);
88 }
89 
90 /*
91  * Searches for the entry with the specified key in the hash table.
92  *
93  * Returns NULL if no entry has the specified key or
94  * the datum of the entry otherwise.
95  */
hashtab_search(struct hashtab * h,const void * key,struct hashtab_key_params key_params)96 static inline void *hashtab_search(struct hashtab *h, const void *key,
97 				   struct hashtab_key_params key_params)
98 {
99 	u32 hvalue;
100 	struct hashtab_node *cur;
101 
102 	if (!h->size)
103 		return NULL;
104 
105 	hvalue = key_params.hash(key) & (h->size - 1);
106 	cur = h->htable[hvalue];
107 	while (cur) {
108 		int cmp = key_params.cmp(key, cur->key);
109 
110 		if (cmp == 0)
111 			return cur->datum;
112 		if (cmp < 0)
113 			break;
114 		cur = cur->next;
115 	}
116 	return NULL;
117 }
118 
119 /*
120  * Destroys the specified hash table.
121  */
122 void hashtab_destroy(struct hashtab *h);
123 
124 /*
125  * Applies the specified apply function to (key,datum,args)
126  * for each entry in the specified hash table.
127  *
128  * The order in which the function is applied to the entries
129  * is dependent upon the internal structure of the hash table.
130  *
131  * If apply returns a non-zero status, then hashtab_map will cease
132  * iterating through the hash table and will propagate the error
133  * return to its caller.
134  */
135 int hashtab_map(struct hashtab *h,
136 		int (*apply)(void *k, void *d, void *args),
137 		void *args);
138 
139 int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
140 		int (*copy)(struct hashtab_node *new,
141 			struct hashtab_node *orig, void *args),
142 		int (*destroy)(void *k, void *d, void *args),
143 		void *args);
144 
145 /* Fill info with some hash table statistics */
146 void hashtab_stat(struct hashtab *h, struct hashtab_info *info);
147 
148 #endif	/* _SS_HASHTAB_H */
149