Branch data Line data Source code
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 : 0 : 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 [ # # ]: 0 : if (p == NULL)
20 : : return p;
21 : :
22 : 0 : p->size = size;
23 : 0 : p->nel = 0;
24 : 0 : p->hash_value = hash_value;
25 : 0 : p->keycmp = keycmp;
26 : 0 : p->htable = kmalloc(sizeof(*(p->htable)) * size, GFP_KERNEL);
27 [ # # ]: 0 : if (p->htable == NULL) {
28 : 0 : kfree(p);
29 : 0 : return NULL;
30 : : }
31 : :
32 [ # # ]: 0 : for (i = 0; i < size; i++)
33 : 0 : p->htable[i] = NULL;
34 : :
35 : : return p;
36 : : }
37 : :
38 : 0 : int hashtab_insert(struct hashtab *h, void *key, void *datum)
39 : : {
40 : : u32 hvalue;
41 : : struct hashtab_node *prev, *cur, *newnode;
42 : :
43 [ # # ][ # # ]: 0 : if (!h || h->nel == HASHTAB_MAX_NODES)
44 : : return -EINVAL;
45 : :
46 : 0 : hvalue = h->hash_value(h, key);
47 : : prev = NULL;
48 : 0 : cur = h->htable[hvalue];
49 [ # # ][ # # ]: 0 : while (cur && h->keycmp(h, key, cur->key) > 0) {
50 : : prev = cur;
51 : 0 : cur = cur->next;
52 : : }
53 : :
54 [ # # ][ # # ]: 0 : if (cur && (h->keycmp(h, key, cur->key) == 0))
55 : : return -EEXIST;
56 : :
57 : : newnode = kzalloc(sizeof(*newnode), GFP_KERNEL);
58 [ # # ]: 0 : if (newnode == NULL)
59 : : return -ENOMEM;
60 : 0 : newnode->key = key;
61 : 0 : newnode->datum = datum;
62 [ # # ]: 0 : if (prev) {
63 : 0 : newnode->next = prev->next;
64 : 0 : prev->next = newnode;
65 : : } else {
66 : 0 : newnode->next = h->htable[hvalue];
67 : 0 : h->htable[hvalue] = newnode;
68 : : }
69 : :
70 : 0 : h->nel++;
71 : 0 : return 0;
72 : : }
73 : :
74 : 0 : void *hashtab_search(struct hashtab *h, const void *key)
75 : : {
76 : : u32 hvalue;
77 : : struct hashtab_node *cur;
78 : :
79 [ # # ]: 0 : if (!h)
80 : : return NULL;
81 : :
82 : 0 : hvalue = h->hash_value(h, key);
83 : 0 : cur = h->htable[hvalue];
84 [ # # ][ # # ]: 0 : while (cur && h->keycmp(h, key, cur->key) > 0)
85 : 0 : cur = cur->next;
86 : :
87 [ # # ][ # # ]: 0 : if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
88 : : return NULL;
89 : :
90 : 0 : return cur->datum;
91 : : }
92 : :
93 : 0 : void hashtab_destroy(struct hashtab *h)
94 : : {
95 : : u32 i;
96 : : struct hashtab_node *cur, *temp;
97 : :
98 [ # # ]: 0 : if (!h)
99 : 0 : return;
100 : :
101 [ # # ]: 0 : for (i = 0; i < h->size; i++) {
102 : 0 : cur = h->htable[i];
103 [ # # ]: 0 : while (cur) {
104 : : temp = cur;
105 : 0 : cur = cur->next;
106 : 0 : kfree(temp);
107 : : }
108 : 0 : h->htable[i] = NULL;
109 : : }
110 : :
111 : 0 : kfree(h->htable);
112 : 0 : h->htable = NULL;
113 : :
114 : 0 : kfree(h);
115 : : }
116 : :
117 : 0 : 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 [ # # ]: 0 : if (!h)
126 : : return 0;
127 : :
128 [ # # ]: 0 : for (i = 0; i < h->size; i++) {
129 : 0 : cur = h->htable[i];
130 [ # # ]: 0 : while (cur) {
131 : 0 : ret = apply(cur->key, cur->datum, args);
132 [ # # ]: 0 : if (ret)
133 : : return ret;
134 : 0 : cur = cur->next;
135 : : }
136 : : }
137 : : return 0;
138 : : }
139 : :
140 : :
141 : 0 : 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 [ # # ]: 0 : for (slots_used = max_chain_len = i = 0; i < h->size; i++) {
149 : 0 : cur = h->htable[i];
150 [ # # ]: 0 : if (cur) {
151 : 0 : slots_used++;
152 : : chain_len = 0;
153 [ # # ]: 0 : while (cur) {
154 : 0 : chain_len++;
155 : 0 : cur = cur->next;
156 : : }
157 : :
158 [ # # ]: 0 : if (chain_len > max_chain_len)
159 : : max_chain_len = chain_len;
160 : : }
161 : : }
162 : :
163 : 0 : info->slots_used = slots_used;
164 : 0 : info->max_chain_len = max_chain_len;
165 : 0 : }
|
