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
hashtab_create(unsigned int (* hash_value)(hashtab_t h,const_hashtab_key_t key),int (* keycmp)(hashtab_t h,const_hashtab_key_t key1,const_hashtab_key_t key2),unsigned int size)37 hashtab_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
hashtab_check_resize(hashtab_t h)65 static 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
hashtab_insert(hashtab_t h,hashtab_key_t key,hashtab_datum_t datum)104 int 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
hashtab_remove(hashtab_t h,hashtab_key_t key,void (* destroy)(hashtab_key_t k,hashtab_datum_t d,void * args),void * args)143 int 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
hashtab_search(hashtab_t h,const_hashtab_key_t key)176 hashtab_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
hashtab_destroy(hashtab_t h)196 void 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
hashtab_map(hashtab_t h,int (* apply)(hashtab_key_t k,hashtab_datum_t d,void * args),void * args)220 int 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
hashtab_hash_eval(hashtab_t h,char * tag)243 void 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