1
2/* Author : Stephen Smalley, <sds@tycho.nsa.gov> */
3
4/*
5 * Updated : Karl MacMillan <kmacmillan@mentalrootkit.com>
6 *
7 * Copyright (C) 2007 Red Hat, Inc.
8 *
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Lesser General Public
11 * License as published by the Free Software Foundation; either
12 * version 2.1 of the License, or (at your option) any later version.
13 *
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17 * Lesser General Public License for more details.
18 *
19 * You should have received a copy of the GNU Lesser General Public
20 * License along with this library; if not, write to the Free Software
21 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
22 */
23
24
25/* FLASK */
26
27/*
28 * Implementation of the hash table type.
29 */
30
31#include <stdlib.h>
32#include <string.h>
33#include <sepol/policydb/hashtab.h>
34
35hashtab_t hashtab_create(unsigned int (*hash_value) (hashtab_t h,
36						     const_hashtab_key_t key),
37			 int (*keycmp) (hashtab_t h,
38					const_hashtab_key_t key1,
39					const_hashtab_key_t key2),
40			 unsigned int size)
41{
42
43	hashtab_t p;
44	unsigned int i;
45
46	p = (hashtab_t) malloc(sizeof(hashtab_val_t));
47	if (p == NULL)
48		return p;
49
50	memset(p, 0, sizeof(hashtab_val_t));
51	p->size = size;
52	p->nel = 0;
53	p->hash_value = hash_value;
54	p->keycmp = keycmp;
55	p->htable = (hashtab_ptr_t *) malloc(sizeof(hashtab_ptr_t) * size);
56	if (p->htable == NULL) {
57		free(p);
58		return NULL;
59	}
60	for (i = 0; i < size; i++)
61		p->htable[i] = (hashtab_ptr_t) NULL;
62
63	return p;
64}
65
66int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum)
67{
68	int hvalue;
69	hashtab_ptr_t prev, cur, newnode;
70
71	if (!h)
72		return SEPOL_ENOMEM;
73
74	hvalue = h->hash_value(h, key);
75	prev = NULL;
76	cur = h->htable[hvalue];
77	while (cur && h->keycmp(h, key, cur->key) > 0) {
78		prev = cur;
79		cur = cur->next;
80	}
81
82	if (cur && (h->keycmp(h, key, cur->key) == 0))
83		return SEPOL_EEXIST;
84
85	newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t));
86	if (newnode == NULL)
87		return SEPOL_ENOMEM;
88	memset(newnode, 0, sizeof(struct hashtab_node));
89	newnode->key = key;
90	newnode->datum = datum;
91	if (prev) {
92		newnode->next = prev->next;
93		prev->next = newnode;
94	} else {
95		newnode->next = h->htable[hvalue];
96		h->htable[hvalue] = newnode;
97	}
98
99	h->nel++;
100	return SEPOL_OK;
101}
102
103int hashtab_remove(hashtab_t h, hashtab_key_t key,
104		   void (*destroy) (hashtab_key_t k,
105				    hashtab_datum_t d, void *args), void *args)
106{
107	int hvalue;
108	hashtab_ptr_t cur, last;
109
110	if (!h)
111		return SEPOL_ENOENT;
112
113	hvalue = h->hash_value(h, key);
114	last = NULL;
115	cur = h->htable[hvalue];
116	while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
117		last = cur;
118		cur = cur->next;
119	}
120
121	if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
122		return SEPOL_ENOENT;
123
124	if (last == NULL)
125		h->htable[hvalue] = cur->next;
126	else
127		last->next = cur->next;
128
129	if (destroy)
130		destroy(cur->key, cur->datum, args);
131	free(cur);
132	h->nel--;
133	return SEPOL_OK;
134}
135
136int hashtab_replace(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum,
137		    void (*destroy) (hashtab_key_t k,
138				     hashtab_datum_t d, void *args), void *args)
139{
140	int hvalue;
141	hashtab_ptr_t prev, cur, newnode;
142
143	if (!h)
144		return SEPOL_ENOMEM;
145
146	hvalue = h->hash_value(h, key);
147	prev = NULL;
148	cur = h->htable[hvalue];
149	while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
150		prev = cur;
151		cur = cur->next;
152	}
153
154	if (cur && (h->keycmp(h, key, cur->key) == 0)) {
155		if (destroy)
156			destroy(cur->key, cur->datum, args);
157		cur->key = key;
158		cur->datum = datum;
159	} else {
160		newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t));
161		if (newnode == NULL)
162			return SEPOL_ENOMEM;
163		memset(newnode, 0, sizeof(struct hashtab_node));
164		newnode->key = key;
165		newnode->datum = datum;
166		if (prev) {
167			newnode->next = prev->next;
168			prev->next = newnode;
169		} else {
170			newnode->next = h->htable[hvalue];
171			h->htable[hvalue] = newnode;
172		}
173	}
174
175	return SEPOL_OK;
176}
177
178hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t key)
179{
180
181	int hvalue;
182	hashtab_ptr_t cur;
183
184	if (!h)
185		return NULL;
186
187	hvalue = h->hash_value(h, key);
188	cur = h->htable[hvalue];
189	while (cur != NULL && h->keycmp(h, key, cur->key) > 0)
190		cur = cur->next;
191
192	if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
193		return NULL;
194
195	return cur->datum;
196}
197
198void hashtab_destroy(hashtab_t h)
199{
200	unsigned int i;
201	hashtab_ptr_t cur, temp;
202
203	if (!h)
204		return;
205
206	for (i = 0; i < h->size; i++) {
207		cur = h->htable[i];
208		while (cur != NULL) {
209			temp = cur;
210			cur = cur->next;
211			free(temp);
212		}
213		h->htable[i] = NULL;
214	}
215
216	free(h->htable);
217	h->htable = NULL;
218
219	free(h);
220}
221
222int hashtab_map(hashtab_t h,
223		int (*apply) (hashtab_key_t k,
224			      hashtab_datum_t d, void *args), void *args)
225{
226	unsigned int i, ret;
227	hashtab_ptr_t cur;
228
229	if (!h)
230		return SEPOL_OK;
231
232	for (i = 0; i < h->size; i++) {
233		cur = h->htable[i];
234		while (cur != NULL) {
235			ret = apply(cur->key, cur->datum, args);
236			if (ret)
237				return ret;
238			cur = cur->next;
239		}
240	}
241	return SEPOL_OK;
242}
243
244void hashtab_map_remove_on_error(hashtab_t h,
245				 int (*apply) (hashtab_key_t k,
246					       hashtab_datum_t d,
247					       void *args),
248				 void (*destroy) (hashtab_key_t k,
249						  hashtab_datum_t d,
250						  void *args), void *args)
251{
252	unsigned int i;
253	int ret;
254	hashtab_ptr_t last, cur, temp;
255
256	if (!h)
257		return;
258
259	for (i = 0; i < h->size; i++) {
260		last = NULL;
261		cur = h->htable[i];
262		while (cur != NULL) {
263			ret = apply(cur->key, cur->datum, args);
264			if (ret) {
265				if (last) {
266					last->next = cur->next;
267				} else {
268					h->htable[i] = cur->next;
269				}
270
271				temp = cur;
272				cur = cur->next;
273				if (destroy)
274					destroy(temp->key, temp->datum, args);
275				free(temp);
276				h->nel--;
277			} else {
278				last = cur;
279				cur = cur->next;
280			}
281		}
282	}
283
284	return;
285}
286
287void hashtab_hash_eval(hashtab_t h, char *tag)
288{
289	unsigned int i;
290	int chain_len, slots_used, max_chain_len;
291	hashtab_ptr_t cur;
292
293	slots_used = 0;
294	max_chain_len = 0;
295	for (i = 0; i < h->size; i++) {
296		cur = h->htable[i];
297		if (cur) {
298			slots_used++;
299			chain_len = 0;
300			while (cur) {
301				chain_len++;
302				cur = cur->next;
303			}
304
305			if (chain_len > max_chain_len)
306				max_chain_len = chain_len;
307		}
308	}
309
310	printf
311	    ("%s:  %d entries and %d/%d buckets used, longest chain length %d\n",
312	     tag, h->nel, slots_used, h->size, max_chain_len);
313}
314