← Back to branch summary

~ubuntu-branches/ubuntu/gutsy/checkpolicy/gutsy

« back to all changes in this revision

Viewing changes to hashtab.c

  • Committer: Bazaar Package Importer
  • Author(s): Russell Coker
  • Date: 2004-05-20 04:32:00 UTC
  • Revision ID: james.westby@ubuntu.com-20040520043200-w4lzkx37dmmc3wt9
Tags: upstream-1.10
Import upstream version 1.10

Show diffs side-by-side

added added

removed removed

Lines of Context:
hashtab.c
 
1
 
 
2
/* Author : Stephen Smalley, <sds@epoch.ncsc.mil> */
 
3
 
 
4
/* FLASK */
 
5
 
 
6
/*
 
7
 * Implementation of the hash table type.
 
8
 */
 
9
 
 
10
#include "hashtab.h"
 
11
 
 
12
hashtab_t hashtab_create(unsigned int (*hash_value) (hashtab_t h,
 
13
                                                     hashtab_key_t key),
 
14
                         int (*keycmp) (hashtab_t h,
 
15
                                        hashtab_key_t key1,
 
16
                                        hashtab_key_t key2),
 
17
                         unsigned int size)
 
18
{
 
19
        hashtab_t p;
 
20
        unsigned int i;
 
21
 
 
22
 
 
23
        p = (hashtab_t) kmalloc(sizeof(hashtab_val_t),GFP_KERNEL);
 
24
        if (p == NULL)
 
25
                return p;
 
26
 
 
27
        memset(p, 0, sizeof(hashtab_val_t));
 
28
        p->size = size;
 
29
        p->nel = 0;
 
30
        p->hash_value = hash_value;
 
31
        p->keycmp = keycmp;
 
32
        p->htable = (hashtab_ptr_t *) kmalloc(sizeof(hashtab_ptr_t) * size,GFP_KERNEL);
 
33
        if (p->htable == NULL) {
 
34
                kfree(p);
 
35
                return NULL;
 
36
        }
 
37
        for (i = 0; i < size; i++)
 
38
                p->htable[i] = (hashtab_ptr_t) NULL;
 
39
 
 
40
        return p;
 
41
}
 
42
 
 
43
 
 
44
int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum)
 
45
{
 
46
        int hvalue;
 
47
        hashtab_ptr_t prev, cur, newnode;
 
48
 
 
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) kmalloc(sizeof(hashtab_node_t),GFP_KERNEL);
 
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
 
 
82
 
 
83
int hashtab_remove(hashtab_t h, hashtab_key_t key,
 
84
                   void (*destroy) (hashtab_key_t k,
 
85
                                    hashtab_datum_t d,
 
86
                                    void *args),
 
87
                   void *args)
 
88
{
 
89
        int hvalue;
 
90
        hashtab_ptr_t cur, last;
 
91
 
 
92
 
 
93
        if (!h)
 
94
                return HASHTAB_MISSING;
 
95
 
 
96
        hvalue = h->hash_value(h, key);
 
97
        last = NULL;
 
98
        cur = h->htable[hvalue];
 
99
        while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
 
100
                last = cur;
 
101
                cur = cur->next;
 
102
        }
 
103
 
 
104
        if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
 
105
                return HASHTAB_MISSING;
 
106
 
 
107
        if (last == NULL)
 
108
                h->htable[hvalue] = cur->next;
 
109
        else
 
110
                last->next = cur->next;
 
111
 
 
112
        if (destroy)
 
113
                destroy(cur->key, cur->datum, args);
 
114
        kfree(cur);
 
115
        h->nel--;
 
116
        return HASHTAB_SUCCESS;
 
117
}
 
118
 
 
119
 
 
120
int hashtab_replace(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum,
 
121
                    void (*destroy) (hashtab_key_t k,
 
122
                                     hashtab_datum_t d,
 
123
                                     void *args),
 
124
                    void *args)
 
125
{
 
126
        int hvalue;
 
127
        hashtab_ptr_t prev, cur, newnode;
 
128
 
 
129
 
 
130
        if (!h)
 
131
                return HASHTAB_OVERFLOW;
 
132
 
 
133
        hvalue = h->hash_value(h, key);
 
134
        prev = NULL;
 
135
        cur = h->htable[hvalue];
 
136
        while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
 
137
                prev = cur;
 
138
                cur = cur->next;
 
139
        }
 
140
 
 
141
        if (cur && (h->keycmp(h, key, cur->key) == 0)) {
 
142
                if (destroy)
 
143
                        destroy(cur->key, cur->datum, args);
 
144
                cur->key = key;
 
145
                cur->datum = datum;
 
146
        } else {
 
147
                newnode = (hashtab_ptr_t) kmalloc(sizeof(hashtab_node_t),GFP_KERNEL);
 
148
                if (newnode == NULL)
 
149
                        return HASHTAB_OVERFLOW;
 
150
                memset(newnode, 0, sizeof(struct hashtab_node));
 
151
                newnode->key = key;
 
152
                newnode->datum = datum;
 
153
                if (prev) {
 
154
                        newnode->next = prev->next;
 
155
                        prev->next = newnode;
 
156
                } else {
 
157
                        newnode->next = h->htable[hvalue];
 
158
                        h->htable[hvalue] = newnode;
 
159
                }
 
160
        }
 
161
 
 
162
        return HASHTAB_SUCCESS;
 
163
}
 
164
 
 
165
 
 
166
hashtab_datum_t
 
167
hashtab_search(hashtab_t h, hashtab_key_t key)
 
168
{
 
169
        int hvalue;
 
170
        hashtab_ptr_t cur;
 
171
 
 
172
 
 
173
        if (!h)
 
174
                return NULL;
 
175
 
 
176
        hvalue = h->hash_value(h, key);
 
177
        cur = h->htable[hvalue];
 
178
        while (cur != NULL && h->keycmp(h, key, cur->key) > 0)
 
179
                cur = cur->next;
 
180
 
 
181
        if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
 
182
                return NULL;
 
183
 
 
184
        return cur->datum;
 
185
}
 
186
 
 
187
 
 
188
void hashtab_destroy(hashtab_t h)
 
189
{
 
190
        unsigned int i;
 
191
        hashtab_ptr_t cur, temp;
 
192
 
 
193
 
 
194
        if (!h)
 
195
                return;
 
196
 
 
197
        for (i = 0; i < h->size; i++) {
 
198
                cur = h->htable[i];
 
199
                while (cur != NULL) {
 
200
                        temp = cur;
 
201
                        cur = cur->next;
 
202
                        kfree(temp);
 
203
                }
 
204
                h->htable[i] = NULL;
 
205
        }
 
206
 
 
207
        kfree(h->htable);
 
208
        h->htable = NULL;
 
209
 
 
210
        kfree(h);
 
211
}
 
212
 
 
213
 
 
214
int hashtab_map(hashtab_t h,
 
215
                int (*apply) (hashtab_key_t k,
 
216
                              hashtab_datum_t d,
 
217
                              void *args),
 
218
                void *args)
 
219
{
 
220
        unsigned int i, ret;
 
221
        hashtab_ptr_t cur;
 
222
 
 
223
 
 
224
        if (!h)
 
225
                return HASHTAB_SUCCESS;
 
226
 
 
227
        for (i = 0; i < h->size; i++) {
 
228
                cur = h->htable[i];
 
229
                while (cur != NULL) {
 
230
                        ret = apply(cur->key, cur->datum, args);
 
231
                        if (ret)
 
232
                                return ret;
 
233
                        cur = cur->next;
 
234
                }
 
235
        }
 
236
        return HASHTAB_SUCCESS;
 
237
}
 
238
 
 
239
 
 
240
void hashtab_map_remove_on_error(hashtab_t h,
 
241
                                 int (*apply) (hashtab_key_t k,
 
242
                                               hashtab_datum_t d,
 
243
                                               void *args),
 
244
                                 void (*destroy) (hashtab_key_t k,
 
245
                                                  hashtab_datum_t d,
 
246
                                                  void *args),
 
247
                                 void *args)
 
248
{
 
249
        unsigned int i;
 
250
        int ret;
 
251
        hashtab_ptr_t last, cur, temp;
 
252
 
 
253
 
 
254
        if (!h)
 
255
                return;
 
256
 
 
257
        for (i = 0; i < h->size; i++) {
 
258
                last = NULL;
 
259
                cur = h->htable[i];
 
260
                while (cur != NULL) {
 
261
                        ret = apply(cur->key, cur->datum, args);
 
262
                        if (ret) {
 
263
                                if (last) {
 
264
                                        last->next = cur->next;
 
265
                                } else {
 
266
                                        h->htable[i] = cur->next;
 
267
                                }
 
268
 
 
269
                                temp = cur;
 
270
                                cur = cur->next;
 
271
                                if (destroy)
 
272
                                        destroy(temp->key, temp->datum, args);
 
273
                                kfree(temp);
 
274
                                h->nel--;
 
275
                        } else {
 
276
                                last = cur;
 
277
                                cur = cur->next;
 
278
                        }
 
279
                }
 
280
        }
 
281
 
 
282
        return;
 
283
}
 
284
 
 
285
void hashtab_hash_eval(hashtab_t h, char *tag)
 
286
{
 
287
        unsigned int i;
 
288
        int chain_len, slots_used, max_chain_len;
 
289
        hashtab_ptr_t cur;
 
290
 
 
291
 
 
292
        slots_used = 0;
 
293
        max_chain_len = 0;
 
294
        for (i = 0; i < h->size; i++) {
 
295
                cur = h->htable[i];
 
296
                if (cur) {
 
297
                        slots_used++;
 
298
                        chain_len = 0;
 
299
                        while (cur) {
 
300
                                chain_len++;
 
301
                                cur = cur->next;
 
302
                        }
 
303
 
 
304
                        if (chain_len > max_chain_len)
 
305
                                max_chain_len = chain_len;
 
306
                }
 
307
        }
 
308
 
 
309
        printk("%s:  %d entries and %d/%d buckets used, longest chain length %d\n",
 
310
               tag, h->nel, slots_used, h->size, max_chain_len);
 
311
}
 
312