1
2 /* Author : Stephen Smalley, <[email protected]> */
3
4 /* FLASK */
5
6 /*
7 * Implementation of the hash table type.
8 */
9
10 #include <stdlib.h>
11 #include <string.h>
12 #include "hashtab.h"
13
selinux_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)14 hashtab_t selinux_hashtab_create(unsigned int (*hash_value) (hashtab_t h,
15 const_hashtab_key_t key),
16 int (*keycmp) (hashtab_t h,
17 const_hashtab_key_t key1,
18 const_hashtab_key_t key2),
19 unsigned int size)
20 {
21
22 hashtab_t p;
23 unsigned int i;
24
25 p = (hashtab_t) malloc(sizeof(hashtab_val_t));
26 if (p == NULL)
27 return p;
28
29 memset(p, 0, sizeof(hashtab_val_t));
30 p->size = size;
31 p->nel = 0;
32 p->hash_value = hash_value;
33 p->keycmp = keycmp;
34 p->htable = (hashtab_ptr_t *) malloc(sizeof(hashtab_ptr_t) * size);
35 if (p->htable == NULL) {
36 free(p);
37 return NULL;
38 }
39 for (i = 0; i < size; i++)
40 p->htable[i] = (hashtab_ptr_t) NULL;
41
42 return p;
43 }
44
selinux_hashtab_insert(hashtab_t h,hashtab_key_t key,hashtab_datum_t datum)45 int selinux_hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum)
46 {
47 unsigned int hvalue;
48 hashtab_ptr_t prev, cur, newnode;
49
50 if (!h)
51 return HASHTAB_OVERFLOW;
52
53 hvalue = h->hash_value(h, key);
54 prev = NULL;
55 cur = h->htable[hvalue];
56 while (cur && h->keycmp(h, key, cur->key) > 0) {
57 prev = cur;
58 cur = cur->next;
59 }
60
61 if (cur && (h->keycmp(h, key, cur->key) == 0))
62 return HASHTAB_PRESENT;
63
64 newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t));
65 if (newnode == NULL)
66 return HASHTAB_OVERFLOW;
67 memset(newnode, 0, sizeof(struct hashtab_node));
68 newnode->key = key;
69 newnode->datum = datum;
70 if (prev) {
71 newnode->next = prev->next;
72 prev->next = newnode;
73 } else {
74 newnode->next = h->htable[hvalue];
75 h->htable[hvalue] = newnode;
76 }
77
78 h->nel++;
79 return HASHTAB_SUCCESS;
80 }
81
selinux_hashtab_remove(hashtab_t h,hashtab_key_t key,void (* destroy)(hashtab_key_t k,hashtab_datum_t d,void * args),void * args)82 int selinux_hashtab_remove(hashtab_t h, hashtab_key_t key,
83 void (*destroy) (hashtab_key_t k,
84 hashtab_datum_t d, void *args), void *args)
85 {
86 unsigned int hvalue;
87 hashtab_ptr_t cur, last;
88
89 if (!h)
90 return HASHTAB_MISSING;
91
92 hvalue = h->hash_value(h, key);
93 last = NULL;
94 cur = h->htable[hvalue];
95 while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
96 last = cur;
97 cur = cur->next;
98 }
99
100 if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
101 return HASHTAB_MISSING;
102
103 if (last == NULL)
104 h->htable[hvalue] = cur->next;
105 else
106 last->next = cur->next;
107
108 if (destroy)
109 destroy(cur->key, cur->datum, args);
110 free(cur);
111 h->nel--;
112 return HASHTAB_SUCCESS;
113 }
114
selinux_hashtab_search(hashtab_t h,const_hashtab_key_t key)115 hashtab_datum_t selinux_hashtab_search(hashtab_t h, const_hashtab_key_t key)
116 {
117
118 unsigned int hvalue;
119 hashtab_ptr_t cur;
120
121 if (!h)
122 return NULL;
123
124 hvalue = h->hash_value(h, key);
125 cur = h->htable[hvalue];
126 while (cur != NULL && h->keycmp(h, key, cur->key) > 0)
127 cur = cur->next;
128
129 if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
130 return NULL;
131
132 return cur->datum;
133 }
134
selinux_hashtab_destroy(hashtab_t h)135 void selinux_hashtab_destroy(hashtab_t h)
136 {
137 unsigned int i;
138 hashtab_ptr_t cur, temp;
139
140 if (!h)
141 return;
142
143 for (i = 0; i < h->size; i++) {
144 cur = h->htable[i];
145 while (cur != NULL) {
146 temp = cur;
147 cur = cur->next;
148 free(temp);
149 }
150 h->htable[i] = NULL;
151 }
152
153 free(h->htable);
154 h->htable = NULL;
155
156 free(h);
157 }
158
selinux_hashtab_destroy_key(hashtab_t h,int (* destroy_key)(hashtab_key_t k))159 void selinux_hashtab_destroy_key(hashtab_t h,
160 int (*destroy_key) (hashtab_key_t k))
161 {
162 unsigned int i;
163 hashtab_ptr_t cur, temp;
164
165 if (!h)
166 return;
167
168 for (i = 0; i < h->size; i++) {
169 cur = h->htable[i];
170 while (cur != NULL) {
171 temp = cur;
172 cur = cur->next;
173 destroy_key(temp->key);
174 free(temp);
175 }
176 h->htable[i] = NULL;
177 }
178
179 free(h->htable);
180 h->htable = NULL;
181
182 free(h);
183 }
184
selinux_hashtab_map(hashtab_t h,int (* apply)(hashtab_key_t k,hashtab_datum_t d,void * args),void * args)185 int selinux_hashtab_map(hashtab_t h,
186 int (*apply) (hashtab_key_t k,
187 hashtab_datum_t d, void *args), void *args)
188 {
189 unsigned int i;
190 hashtab_ptr_t cur;
191 int ret;
192
193 if (!h)
194 return HASHTAB_SUCCESS;
195
196 for (i = 0; i < h->size; i++) {
197 cur = h->htable[i];
198 while (cur != NULL) {
199 ret = apply(cur->key, cur->datum, args);
200 if (ret)
201 return ret;
202 cur = cur->next;
203 }
204 }
205 return HASHTAB_SUCCESS;
206 }
207
selinux_hashtab_hash_eval(hashtab_t h,char * tag)208 void selinux_hashtab_hash_eval(hashtab_t h, char *tag)
209 {
210 unsigned int i;
211 int chain_len, slots_used, max_chain_len;
212 hashtab_ptr_t cur;
213
214 slots_used = 0;
215 max_chain_len = 0;
216 for (i = 0; i < h->size; i++) {
217 cur = h->htable[i];
218 if (cur) {
219 slots_used++;
220 chain_len = 0;
221 while (cur) {
222 chain_len++;
223 cur = cur->next;
224 }
225
226 if (chain_len > max_chain_len)
227 max_chain_len = chain_len;
228 }
229 }
230
231 printf
232 ("%s: %d entries and %d/%d buckets used, longest chain length %d\n",
233 tag, h->nel, slots_used, h->size, max_chain_len);
234 }
235