1
2 /* Author : Stephen Smalley, <[email protected]> */
3
4 /*
5 * Updated : Karl MacMillan <[email protected]>
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 unsigned int hvalue;
107 hashtab_ptr_t prev, cur, newnode;
108
109 if (!h || h->nel == UINT32_MAX)
110 return SEPOL_ENOMEM;
111
112 hashtab_check_resize(h);
113
114 hvalue = h->hash_value(h, key);
115
116 for (prev = NULL, cur = h->htable[hvalue]; cur; prev = cur, cur = cur->next) {
117 int cmp;
118
119 cmp = h->keycmp(h, key, cur->key);
120 if (cmp > 0)
121 continue;
122 if (cmp == 0)
123 return SEPOL_EEXIST;
124 break;
125 }
126
127 newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t));
128 if (newnode == NULL)
129 return SEPOL_ENOMEM;
130 memset(newnode, 0, sizeof(struct hashtab_node));
131 newnode->key = key;
132 newnode->datum = datum;
133 if (prev) {
134 newnode->next = prev->next;
135 prev->next = newnode;
136 } else {
137 newnode->next = h->htable[hvalue];
138 h->htable[hvalue] = newnode;
139 }
140
141 h->nel++;
142 return SEPOL_OK;
143 }
144
hashtab_remove(hashtab_t h,hashtab_key_t key,void (* destroy)(hashtab_key_t k,hashtab_datum_t d,void * args),void * args)145 int hashtab_remove(hashtab_t h, hashtab_key_t key,
146 void (*destroy) (hashtab_key_t k,
147 hashtab_datum_t d, void *args), void *args)
148 {
149 unsigned int hvalue;
150 hashtab_ptr_t cur, last;
151
152 if (!h)
153 return SEPOL_ENOENT;
154
155 hvalue = h->hash_value(h, key);
156
157 for (last = NULL, cur = h->htable[hvalue]; cur; last = cur, cur = cur->next) {
158 int cmp;
159
160 cmp = h->keycmp(h, key, cur->key);
161 if (cmp > 0)
162 continue;
163 if (cmp == 0)
164 break;
165 return SEPOL_ENOENT;
166 }
167
168 if (cur == NULL)
169 return SEPOL_ENOENT;
170
171 if (last == NULL)
172 h->htable[hvalue] = cur->next;
173 else
174 last->next = cur->next;
175
176 if (destroy)
177 destroy(cur->key, cur->datum, args);
178 free(cur);
179 h->nel--;
180 return SEPOL_OK;
181 }
182
hashtab_search(hashtab_t h,const_hashtab_key_t key)183 hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t key)
184 {
185
186 unsigned int hvalue;
187 hashtab_ptr_t cur;
188
189 if (!h)
190 return NULL;
191
192 hvalue = h->hash_value(h, key);
193 for (cur = h->htable[hvalue]; cur; cur = cur->next) {
194 int cmp;
195
196 cmp = h->keycmp(h, key, cur->key);
197 if (cmp > 0)
198 continue;
199 if (cmp == 0)
200 return cur->datum;
201 break;
202 }
203
204 return NULL;
205 }
206
hashtab_destroy(hashtab_t h)207 void hashtab_destroy(hashtab_t h)
208 {
209 unsigned int i;
210 hashtab_ptr_t cur, temp;
211
212 if (!h)
213 return;
214
215 for (i = 0; i < h->size; i++) {
216 cur = h->htable[i];
217 while (cur != NULL) {
218 temp = cur;
219 cur = cur->next;
220 free(temp);
221 }
222 h->htable[i] = NULL;
223 }
224
225 free(h->htable);
226 h->htable = NULL;
227
228 free(h);
229 }
230
hashtab_map(hashtab_t h,int (* apply)(hashtab_key_t k,hashtab_datum_t d,void * args),void * args)231 int hashtab_map(hashtab_t h,
232 int (*apply) (hashtab_key_t k,
233 hashtab_datum_t d, void *args), void *args)
234 {
235 unsigned int i;
236 hashtab_ptr_t cur;
237 int ret;
238
239 if (!h)
240 return SEPOL_OK;
241
242 for (i = 0; i < h->size; i++) {
243 cur = h->htable[i];
244 while (cur != NULL) {
245 ret = apply(cur->key, cur->datum, args);
246 if (ret)
247 return ret;
248 cur = cur->next;
249 }
250 }
251 return SEPOL_OK;
252 }
253
hashtab_hash_eval(hashtab_t h,const char * tag)254 void hashtab_hash_eval(hashtab_t h, const char *tag)
255 {
256 unsigned int i;
257 size_t chain_len, slots_used, max_chain_len, chain2_len_sum;
258 hashtab_ptr_t cur;
259
260 slots_used = 0;
261 max_chain_len = 0;
262 chain2_len_sum = 0;
263 for (i = 0; i < h->size; i++) {
264 cur = h->htable[i];
265 if (cur) {
266 slots_used++;
267 chain_len = 0;
268 while (cur) {
269 chain_len++;
270 cur = cur->next;
271 }
272
273 if (chain_len > max_chain_len)
274 max_chain_len = chain_len;
275 chain2_len_sum += chain_len * chain_len;
276 }
277 }
278
279 printf
280 ("%s: %d entries and %zu/%d buckets used, longest chain length %zu, chain length^2 %zu, normalized chain length^2 %.2f\n",
281 tag, h->nel, slots_used, h->size, max_chain_len, chain2_len_sum,
282 chain2_len_sum ? (float)chain2_len_sum / slots_used : 0);
283 }
284