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