]>
Commit | Line | Data |
---|---|---|
1da177e4 LT |
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 | ||
bb242497 CS |
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), | |
1da177e4 LT |
13 | u32 size) |
14 | { | |
15 | struct hashtab *p; | |
16 | u32 i; | |
17 | ||
89d155ef | 18 | p = kzalloc(sizeof(*p), GFP_KERNEL); |
1da177e4 LT |
19 | if (p == NULL) |
20 | return p; | |
21 | ||
1da177e4 LT |
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 | ||
89d155ef | 57 | newnode = kzalloc(sizeof(*newnode), GFP_KERNEL); |
1da177e4 LT |
58 | if (newnode == NULL) |
59 | return -ENOMEM; | |
1da177e4 LT |
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 | ||
bb242497 | 74 | void *hashtab_search(struct hashtab *h, const void *key) |
1da177e4 LT |
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 | } |