Merge branch 'upstream-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/mfashe...
[linux-2.6] / security / selinux / ss / hashtab.c
1 /*
2  * Implementation of the hash table type.
3  *
4  * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
5  */
6 #include <linux/kernel.h>
7 #include <linux/slab.h>
8 #include <linux/errno.h>
9 #include "hashtab.h"
10
11 struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key),
12                                int (*keycmp)(struct hashtab *h, const void *key1, const void *key2),
13                                u32 size)
14 {
15         struct hashtab *p;
16         u32 i;
17
18         p = kzalloc(sizeof(*p), GFP_KERNEL);
19         if (p == NULL)
20                 return p;
21
22         p->size = size;
23         p->nel = 0;
24         p->hash_value = hash_value;
25         p->keycmp = keycmp;
26         p->htable = kmalloc(sizeof(*(p->htable)) * size, GFP_KERNEL);
27         if (p->htable == NULL) {
28                 kfree(p);
29                 return NULL;
30         }
31
32         for (i = 0; i < size; i++)
33                 p->htable[i] = NULL;
34
35         return p;
36 }
37
38 int hashtab_insert(struct hashtab *h, void *key, void *datum)
39 {
40         u32 hvalue;
41         struct hashtab_node *prev, *cur, *newnode;
42
43         if (!h || h->nel == HASHTAB_MAX_NODES)
44                 return -EINVAL;
45
46         hvalue = h->hash_value(h, key);
47         prev = NULL;
48         cur = h->htable[hvalue];
49         while (cur && h->keycmp(h, key, cur->key) > 0) {
50                 prev = cur;
51                 cur = cur->next;
52         }
53
54         if (cur && (h->keycmp(h, key, cur->key) == 0))
55                 return -EEXIST;
56
57         newnode = kzalloc(sizeof(*newnode), GFP_KERNEL);
58         if (newnode == NULL)
59                 return -ENOMEM;
60         newnode->key = key;
61         newnode->datum = datum;
62         if (prev) {
63                 newnode->next = prev->next;
64                 prev->next = newnode;
65         } else {
66                 newnode->next = h->htable[hvalue];
67                 h->htable[hvalue] = newnode;
68         }
69
70         h->nel++;
71         return 0;
72 }
73
74 void *hashtab_search(struct hashtab *h, const void *key)
75 {
76         u32 hvalue;
77         struct hashtab_node *cur;
78
79         if (!h)
80                 return NULL;
81
82         hvalue = h->hash_value(h, key);
83         cur = h->htable[hvalue];
84         while (cur != NULL && h->keycmp(h, key, cur->key) > 0)
85                 cur = cur->next;
86
87         if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
88                 return NULL;
89
90         return cur->datum;
91 }
92
93 void hashtab_destroy(struct hashtab *h)
94 {
95         u32 i;
96         struct hashtab_node *cur, *temp;
97
98         if (!h)
99                 return;
100
101         for (i = 0; i < h->size; i++) {
102                 cur = h->htable[i];
103                 while (cur != NULL) {
104                         temp = cur;
105                         cur = cur->next;
106                         kfree(temp);
107                 }
108                 h->htable[i] = NULL;
109         }
110
111         kfree(h->htable);
112         h->htable = NULL;
113
114         kfree(h);
115 }
116
117 int hashtab_map(struct hashtab *h,
118                 int (*apply)(void *k, void *d, void *args),
119                 void *args)
120 {
121         u32 i;
122         int ret;
123         struct hashtab_node *cur;
124
125         if (!h)
126                 return 0;
127
128         for (i = 0; i < h->size; i++) {
129                 cur = h->htable[i];
130                 while (cur != NULL) {
131                         ret = apply(cur->key, cur->datum, args);
132                         if (ret)
133                                 return ret;
134                         cur = cur->next;
135                 }
136         }
137         return 0;
138 }
139
140
141 void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
142 {
143         u32 i, chain_len, slots_used, max_chain_len;
144         struct hashtab_node *cur;
145
146         slots_used = 0;
147         max_chain_len = 0;
148         for (slots_used = max_chain_len = i = 0; i < h->size; i++) {
149                 cur = h->htable[i];
150                 if (cur) {
151                         slots_used++;
152                         chain_len = 0;
153                         while (cur) {
154                                 chain_len++;
155                                 cur = cur->next;
156                         }
157
158                         if (chain_len > max_chain_len)
159                                 max_chain_len = chain_len;
160                 }
161         }
162
163         info->slots_used = slots_used;
164         info->max_chain_len = max_chain_len;
165 }