xref: /third_party/selinux/libsepol/src/hashtab.c (revision 6cd6a6ac) 
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
35#include "private.h"
36
37hashtab_t hashtab_create(unsigned int (*hash_value) (hashtab_t h,
38						     const_hashtab_key_t key),
39			 int (*keycmp) (hashtab_t h,
40					const_hashtab_key_t key1,
41					const_hashtab_key_t key2),
42			 unsigned int size)
43{
44
45	hashtab_t p;
46
47	p = (hashtab_t) malloc(sizeof(hashtab_val_t));
48	if (p == NULL)
49		return p;
50
51	memset(p, 0, sizeof(hashtab_val_t));
52	p->size = size;
53	p->nel = 0;
54	p->hash_value = hash_value;
55	p->keycmp = keycmp;
56	p->htable = (hashtab_ptr_t *) calloc(size, sizeof(hashtab_ptr_t));
57	if (p->htable == NULL) {
58		free(p);
59		return NULL;
60	}
61
62	return p;
63}
64
65static void hashtab_check_resize(hashtab_t h)
66{
67	unsigned int hvalue, i, old_size, new_size = h->size;
68	hashtab_ptr_t *new_htable, *dst, cur, next;
69
70	while (new_size <= h->nel && new_size * 2 != 0)
71		new_size *= 2;
72
73	if (h->size == new_size)
74		return;
75
76	new_htable = calloc(new_size, sizeof(*new_htable));
77	if (!new_htable)
78		return;
79
80	old_size = h->size;
81	h->size = new_size;
82
83	/* Move all elements to the new htable */
84	for (i = 0; i < old_size; i++) {
85		cur = h->htable[i];
86		while (cur != NULL) {
87			hvalue = h->hash_value(h, cur->key);
88			dst = &new_htable[hvalue];
89			while (*dst && h->keycmp(h, cur->key, (*dst)->key) > 0)
90				dst = &(*dst)->next;
91
92			next = cur->next;
93
94			cur->next = *dst;
95			*dst = cur;
96
97			cur = next;
98		}
99	}
100	free(h->htable);
101	h->htable = new_htable;
102}
103
104int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum)
105{
106	int hvalue;
107	hashtab_ptr_t prev, cur, newnode;
108
109	if (!h)
110		return SEPOL_ENOMEM;
111
112	hashtab_check_resize(h);
113
114	hvalue = h->hash_value(h, key);
115	prev = NULL;
116	cur = h->htable[hvalue];
117	while (cur && h->keycmp(h, key, cur->key) > 0) {
118		prev = cur;
119		cur = cur->next;
120	}
121
122	if (cur && (h->keycmp(h, key, cur->key) == 0))
123		return SEPOL_EEXIST;
124
125	newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t));
126	if (newnode == NULL)
127		return SEPOL_ENOMEM;
128	memset(newnode, 0, sizeof(struct hashtab_node));
129	newnode->key = key;
130	newnode->datum = datum;
131	if (prev) {
132		newnode->next = prev->next;
133		prev->next = newnode;
134	} else {
135		newnode->next = h->htable[hvalue];
136		h->htable[hvalue] = newnode;
137	}
138
139	h->nel++;
140	return SEPOL_OK;
141}
142
143int hashtab_remove(hashtab_t h, hashtab_key_t key,
144		   void (*destroy) (hashtab_key_t k,
145				    hashtab_datum_t d, void *args), void *args)
146{
147	int hvalue;
148	hashtab_ptr_t cur, last;
149
150	if (!h)
151		return SEPOL_ENOENT;
152
153	hvalue = h->hash_value(h, key);
154	last = NULL;
155	cur = h->htable[hvalue];
156	while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
157		last = cur;
158		cur = cur->next;
159	}
160
161	if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
162		return SEPOL_ENOENT;
163
164	if (last == NULL)
165		h->htable[hvalue] = cur->next;
166	else
167		last->next = cur->next;
168
169	if (destroy)
170		destroy(cur->key, cur->datum, args);
171	free(cur);
172	h->nel--;
173	return SEPOL_OK;
174}
175
176hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t key)
177{
178
179	int hvalue;
180	hashtab_ptr_t cur;
181
182	if (!h)
183		return NULL;
184
185	hvalue = h->hash_value(h, key);
186	cur = h->htable[hvalue];
187	while (cur != NULL && h->keycmp(h, key, cur->key) > 0)
188		cur = cur->next;
189
190	if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
191		return NULL;
192
193	return cur->datum;
194}
195
196void hashtab_destroy(hashtab_t h)
197{
198	unsigned int i;
199	hashtab_ptr_t cur, temp;
200
201	if (!h)
202		return;
203
204	for (i = 0; i < h->size; i++) {
205		cur = h->htable[i];
206		while (cur != NULL) {
207			temp = cur;
208			cur = cur->next;
209			free(temp);
210		}
211		h->htable[i] = NULL;
212	}
213
214	free(h->htable);
215	h->htable = NULL;
216
217	free(h);
218}
219
220int hashtab_map(hashtab_t h,
221		int (*apply) (hashtab_key_t k,
222			      hashtab_datum_t d, void *args), void *args)
223{
224	unsigned int i;
225	hashtab_ptr_t cur;
226	int ret;
227
228	if (!h)
229		return SEPOL_OK;
230
231	for (i = 0; i < h->size; i++) {
232		cur = h->htable[i];
233		while (cur != NULL) {
234			ret = apply(cur->key, cur->datum, args);
235			if (ret)
236				return ret;
237			cur = cur->next;
238		}
239	}
240	return SEPOL_OK;
241}
242
243void hashtab_hash_eval(hashtab_t h, char *tag)
244{
245	unsigned int i;
246	int chain_len, slots_used, max_chain_len;
247	hashtab_ptr_t cur;
248
249	slots_used = 0;
250	max_chain_len = 0;
251	for (i = 0; i < h->size; i++) {
252		cur = h->htable[i];
253		if (cur) {
254			slots_used++;
255			chain_len = 0;
256			while (cur) {
257				chain_len++;
258				cur = cur->next;
259			}
260
261			if (chain_len > max_chain_len)
262				max_chain_len = chain_len;
263		}
264	}
265
266	printf
267	    ("%s:  %d entries and %d/%d buckets used, longest chain length %d\n",
268	     tag, h->nel, slots_used, h->size, max_chain_len);
269}
270