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
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)35 hashtab_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
hashtab_insert(hashtab_t h,hashtab_key_t key,hashtab_datum_t datum)66 int 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
hashtab_remove(hashtab_t h,hashtab_key_t key,void (* destroy)(hashtab_key_t k,hashtab_datum_t d,void * args),void * args)103 int 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
hashtab_replace(hashtab_t h,hashtab_key_t key,hashtab_datum_t datum,void (* destroy)(hashtab_key_t k,hashtab_datum_t d,void * args),void * args)136 int 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
hashtab_search(hashtab_t h,const_hashtab_key_t key)178 hashtab_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
hashtab_destroy(hashtab_t h)198 void 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
hashtab_map(hashtab_t h,int (* apply)(hashtab_key_t k,hashtab_datum_t d,void * args),void * args)222 int 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
hashtab_map_remove_on_error(hashtab_t h,int (* apply)(hashtab_key_t k,hashtab_datum_t d,void * args),void (* destroy)(hashtab_key_t k,hashtab_datum_t d,void * args),void * args)244 void 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
hashtab_hash_eval(hashtab_t h,char * tag)287 void 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