hashtab.h

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