← Back to branch summary

~ubuntu-branches/ubuntu/precise/policycoreutils/precise

« back to all changes in this revision

Viewing changes to newrole/hashtab.c

  • Committer: Bazaar Package Importer
  • Author(s): Caleb Case, Caleb Case, Joseph Jackson IV
  • Date: 2008-02-09 21:36:48 UTC
  • mfrom: (1.2.9 upstream)
  • Revision ID: james.westby@ubuntu.com-20080209213648-lgax8nm8jer4ld25
Tags: 2.0.43-0ubuntu1
[ Caleb Case ]
* New upstream SVN HEAD
 + Merged support for non-interactive newrole command invocation from
   Tim Reed.
 + Update Makefile to not build restorecond if
   /usr/include/sys/inotify.h is not present
 + Drop verbose output on fixfiles -C from Dan Walsh.
 + Fix argument handling in fixfiles from Dan Walsh.
 + Enhance boolean support in semanage, including using the .xml
   description when available, from Dan Walsh.
 + load_policy initial load option from Chad Sellers.
 + Fix semodule option handling from Dan Walsh.
 + Add deleteall support for ports and fcontexts in semanage from Dan
   Walsh.
 + Add genhomedircon script to invoke semodule -Bn from Dan Walsh.
 + Update semodule man page for -D from Dan Walsh.
 + Add boolean, locallist, deleteall, and store support to semanage
   from Dan Walsh.
 + Improve semodule reporting of system errors from Stephen Smalley.
 + Fix setfiles selabel option flag setting for 64-bit from Stephen
   Smalley.
 + Remove genhomedircon script (functionality is now provided
   within libsemanage) from Todd Miller.
 + Fix genhomedircon searching for USER from Todd Miller
 + Install run_init with mode 0755 from Dan Walsh.
 + Fix chcat from Dan Walsh.
 + Fix fixfiles pattern expansion and error reporting from Dan Walsh.   
 + Optimize genhomedircon to compile regexes once from Dan Walsh.
 + Fix semanage gettext call from Dan Walsh.
 + Disable dontaudits via semodule -D
 + Rebase setfiles to use new labeling interface.
 + Fixed setsebool (falling through to error path on success).
 + Merged genhomedircon fixes from Dan Walsh.
 + Merged setfiles -c usage fix from Dan Walsh.
 + Merged restorecon fix from Yuichi Nakamura.
 + Dropped -lsepol where no longer needed.
 + Merge newrole support for alternate pam configs from Ted X Toth.
 + Merged merging of restorecon into setfiles from Stephen Smalley.
 + Merged genhomedircon fix to find conflicting directories correctly
   from Dan Walsh.
* debian/policycoreutils.restorecon.init
  * Removing improper '$' 

[ Joseph Jackson IV ]
* debian/control
  - Update Debian Maintainer field

Show diffs side-by-side

added added

removed removed

Lines of Context:
newrole/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 <stdlib.h>
 
11
#include <string.h>
 
12
#include "hashtab.h"
 
13
 
 
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
 
 
45
int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum)
 
46
{
 
47
        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
 
 
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
        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
 
 
115
int hashtab_replace(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum,
 
116
                    void (*destroy) (hashtab_key_t k,
 
117
                                     hashtab_datum_t d, void *args), void *args)
 
118
{
 
119
        int hvalue;
 
120
        hashtab_ptr_t prev, cur, newnode;
 
121
 
 
122
        if (!h)
 
123
                return HASHTAB_OVERFLOW;
 
124
 
 
125
        hvalue = h->hash_value(h, key);
 
126
        prev = NULL;
 
127
        cur = h->htable[hvalue];
 
128
        while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
 
129
                prev = cur;
 
130
                cur = cur->next;
 
131
        }
 
132
 
 
133
        if (cur && (h->keycmp(h, key, cur->key) == 0)) {
 
134
                if (destroy)
 
135
                        destroy(cur->key, cur->datum, args);
 
136
                cur->key = key;
 
137
                cur->datum = datum;
 
138
        } else {
 
139
                newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t));
 
140
                if (newnode == NULL)
 
141
                        return HASHTAB_OVERFLOW;
 
142
                memset(newnode, 0, sizeof(struct hashtab_node));
 
143
                newnode->key = key;
 
144
                newnode->datum = datum;
 
145
                if (prev) {
 
146
                        newnode->next = prev->next;
 
147
                        prev->next = newnode;
 
148
                } else {
 
149
                        newnode->next = h->htable[hvalue];
 
150
                        h->htable[hvalue] = newnode;
 
151
                }
 
152
        }
 
153
 
 
154
        return HASHTAB_SUCCESS;
 
155
}
 
156
 
 
157
hashtab_datum_t hashtab_search(hashtab_t h, const hashtab_key_t key)
 
158
{
 
159
 
 
160
        int hvalue;
 
161
        hashtab_ptr_t cur;
 
162
 
 
163
        if (!h)
 
164
                return NULL;
 
165
 
 
166
        hvalue = h->hash_value(h, key);
 
167
        cur = h->htable[hvalue];
 
168
        while (cur != NULL && h->keycmp(h, key, cur->key) > 0)
 
169
                cur = cur->next;
 
170
 
 
171
        if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
 
172
                return NULL;
 
173
 
 
174
        return cur->datum;
 
175
}
 
176
 
 
177
void hashtab_destroy(hashtab_t h)
 
178
{
 
179
        unsigned int i;
 
180
        hashtab_ptr_t cur, temp;
 
181
 
 
182
        if (!h)
 
183
                return;
 
184
 
 
185
        for (i = 0; i < h->size; i++) {
 
186
                cur = h->htable[i];
 
187
                while (cur != NULL) {
 
188
                        temp = cur;
 
189
                        cur = cur->next;
 
190
                        free(temp);
 
191
                }
 
192
                h->htable[i] = NULL;
 
193
        }
 
194
 
 
195
        free(h->htable);
 
196
        h->htable = NULL;
 
197
 
 
198
        free(h);
 
199
}
 
200
 
 
201
int hashtab_map(hashtab_t h,
 
202
                int (*apply) (hashtab_key_t k,
 
203
                              hashtab_datum_t d, void *args), void *args)
 
204
{
 
205
        unsigned int i, ret;
 
206
        hashtab_ptr_t cur;
 
207
 
 
208
        if (!h)
 
209
                return HASHTAB_SUCCESS;
 
210
 
 
211
        for (i = 0; i < h->size; i++) {
 
212
                cur = h->htable[i];
 
213
                while (cur != NULL) {
 
214
                        ret = apply(cur->key, cur->datum, args);
 
215
                        if (ret)
 
216
                                return ret;
 
217
                        cur = cur->next;
 
218
                }
 
219
        }
 
220
        return HASHTAB_SUCCESS;
 
221
}
 
222
 
 
223
void hashtab_map_remove_on_error(hashtab_t h,
 
224
                                 int (*apply) (hashtab_key_t k,
 
225
                                               hashtab_datum_t d,
 
226
                                               void *args),
 
227
                                 void (*destroy) (hashtab_key_t k,
 
228
                                                  hashtab_datum_t d,
 
229
                                                  void *args), void *args)
 
230
{
 
231
        unsigned int i;
 
232
        int ret;
 
233
        hashtab_ptr_t last, cur, temp;
 
234
 
 
235
        if (!h)
 
236
                return;
 
237
 
 
238
        for (i = 0; i < h->size; i++) {
 
239
                last = NULL;
 
240
                cur = h->htable[i];
 
241
                while (cur != NULL) {
 
242
                        ret = apply(cur->key, cur->datum, args);
 
243
                        if (ret) {
 
244
                                if (last) {
 
245
                                        last->next = cur->next;
 
246
                                } else {
 
247
                                        h->htable[i] = cur->next;
 
248
                                }
 
249
 
 
250
                                temp = cur;
 
251
                                cur = cur->next;
 
252
                                if (destroy)
 
253
                                        destroy(temp->key, temp->datum, args);
 
254
                                free(temp);
 
255
                                h->nel--;
 
256
                        } else {
 
257
                                last = cur;
 
258
                                cur = cur->next;
 
259
                        }
 
260
                }
 
261
        }
 
262
 
 
263
        return;
 
264
}
 
265
 
 
266
void hashtab_hash_eval(hashtab_t h, char *tag)
 
267
{
 
268
        unsigned int i;
 
269
        int chain_len, slots_used, max_chain_len;
 
270
        hashtab_ptr_t cur;
 
271
 
 
272
        slots_used = 0;
 
273
        max_chain_len = 0;
 
274
        for (i = 0; i < h->size; i++) {
 
275
                cur = h->htable[i];
 
276
                if (cur) {
 
277
                        slots_used++;
 
278
                        chain_len = 0;
 
279
                        while (cur) {
 
280
                                chain_len++;
 
281
                                cur = cur->next;
 
282
                        }
 
283
 
 
284
                        if (chain_len > max_chain_len)
 
285
                                max_chain_len = chain_len;
 
286
                }
 
287
        }
 
288
 
 
289
        printf
 
290
            ("%s:  %d entries and %d/%d buckets used, longest chain length %d\n",
 
291
             tag, h->nel, slots_used, h->size, max_chain_len);
 
292
}