1/*
2 * Implementation of the hash table type.
3 *
4 * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
5 */
6#include <linux/kernel.h>
7#include <linux/slab.h>
8#include <linux/errno.h>
9#include <linux/sched.h>
10#include "hashtab.h"
11
12struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key),
13			       int (*keycmp)(struct hashtab *h, const void *key1, const void *key2),
14			       u32 size)
15{
16	struct hashtab *p;
17	u32 i;
18
19	p = kzalloc(sizeof(*p), GFP_KERNEL);
20	if (p == NULL)
21		return p;
22
23	p->size = size;
24	p->nel = 0;
25	p->hash_value = hash_value;
26	p->keycmp = keycmp;
27	p->htable = kmalloc(sizeof(*(p->htable)) * size, GFP_KERNEL);
28	if (p->htable == NULL) {
29		kfree(p);
30		return NULL;
31	}
32
33	for (i = 0; i < size; i++)
34		p->htable[i] = NULL;
35
36	return p;
37}
38
39int hashtab_insert(struct hashtab *h, void *key, void *datum)
40{
41	u32 hvalue;
42	struct hashtab_node *prev, *cur, *newnode;
43
44	cond_resched();
45
46	if (!h || h->nel == HASHTAB_MAX_NODES)
47		return -EINVAL;
48
49	hvalue = h->hash_value(h, key);
50	prev = NULL;
51	cur = h->htable[hvalue];
52	while (cur && h->keycmp(h, key, cur->key) > 0) {
53		prev = cur;
54		cur = cur->next;
55	}
56
57	if (cur && (h->keycmp(h, key, cur->key) == 0))
58		return -EEXIST;
59
60	newnode = kzalloc(sizeof(*newnode), GFP_KERNEL);
61	if (newnode == NULL)
62		return -ENOMEM;
63	newnode->key = key;
64	newnode->datum = datum;
65	if (prev) {
66		newnode->next = prev->next;
67		prev->next = newnode;
68	} else {
69		newnode->next = h->htable[hvalue];
70		h->htable[hvalue] = newnode;
71	}
72
73	h->nel++;
74	return 0;
75}
76
77void *hashtab_search(struct hashtab *h, const void *key)
78{
79	u32 hvalue;
80	struct hashtab_node *cur;
81
82	if (!h)
83		return NULL;
84
85	hvalue = h->hash_value(h, key);
86	cur = h->htable[hvalue];
87	while (cur && h->keycmp(h, key, cur->key) > 0)
88		cur = cur->next;
89
90	if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
91		return NULL;
92
93	return cur->datum;
94}
95
96void hashtab_destroy(struct hashtab *h)
97{
98	u32 i;
99	struct hashtab_node *cur, *temp;
100
101	if (!h)
102		return;
103
104	for (i = 0; i < h->size; i++) {
105		cur = h->htable[i];
106		while (cur) {
107			temp = cur;
108			cur = cur->next;
109			kfree(temp);
110		}
111		h->htable[i] = NULL;
112	}
113
114	kfree(h->htable);
115	h->htable = NULL;
116
117	kfree(h);
118}
119
120int hashtab_map(struct hashtab *h,
121		int (*apply)(void *k, void *d, void *args),
122		void *args)
123{
124	u32 i;
125	int ret;
126	struct hashtab_node *cur;
127
128	if (!h)
129		return 0;
130
131	for (i = 0; i < h->size; i++) {
132		cur = h->htable[i];
133		while (cur) {
134			ret = apply(cur->key, cur->datum, args);
135			if (ret)
136				return ret;
137			cur = cur->next;
138		}
139	}
140	return 0;
141}
142
143
144void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
145{
146	u32 i, chain_len, slots_used, max_chain_len;
147	struct hashtab_node *cur;
148
149	slots_used = 0;
150	max_chain_len = 0;
151	for (slots_used = max_chain_len = i = 0; i < h->size; i++) {
152		cur = h->htable[i];
153		if (cur) {
154			slots_used++;
155			chain_len = 0;
156			while (cur) {
157				chain_len++;
158				cur = cur->next;
159			}
160
161			if (chain_len > max_chain_len)
162				max_chain_len = chain_len;
163		}
164	}
165
166	info->slots_used = slots_used;
167	info->max_chain_len = max_chain_len;
168}
169