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
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 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
hashtab_insert(hashtab_t h,hashtab_key_t key,hashtab_datum_t datum)45 int 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
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 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
hashtab_search(hashtab_t h,const_hashtab_key_t key)115 hashtab_datum_t 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
hashtab_destroy(hashtab_t h)135 void 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
hashtab_map(hashtab_t h,int (* apply)(hashtab_key_t k,hashtab_datum_t d,void * args),void * args)159 int hashtab_map(hashtab_t h,
160 int (*apply) (hashtab_key_t k,
161 hashtab_datum_t d, void *args), void *args)
162 {
163 unsigned int i;
164 hashtab_ptr_t cur;
165 int ret;
166
167 if (!h)
168 return HASHTAB_SUCCESS;
169
170 for (i = 0; i < h->size; i++) {
171 cur = h->htable[i];
172 while (cur != NULL) {
173 ret = apply(cur->key, cur->datum, args);
174 if (ret)
175 return ret;
176 cur = cur->next;
177 }
178 }
179 return HASHTAB_SUCCESS;
180 }
181
hashtab_hash_eval(hashtab_t h,char * tag)182 void hashtab_hash_eval(hashtab_t h, char *tag)
183 {
184 unsigned int i;
185 int chain_len, slots_used, max_chain_len;
186 hashtab_ptr_t cur;
187
188 slots_used = 0;
189 max_chain_len = 0;
190 for (i = 0; i < h->size; i++) {
191 cur = h->htable[i];
192 if (cur) {
193 slots_used++;
194 chain_len = 0;
195 while (cur) {
196 chain_len++;
197 cur = cur->next;
198 }
199
200 if (chain_len > max_chain_len)
201 max_chain_len = chain_len;
202 }
203 }
204
205 printf
206 ("%s: %d entries and %d/%d buckets used, longest chain length %d\n",
207 tag, h->nel, slots_used, h->size, max_chain_len);
208 }
209