1 /*
2 * Implementation of the hash table type.
3 *
4 * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
5 */
6
7 /* Ported to Xen 3.0, George Coker, <gscoker@alpha.ncsc.mil> */
8
9 #include <xen/lib.h>
10 #include <xen/xmalloc.h>
11 #include <xen/errno.h>
12 #include "hashtab.h"
13
hashtab_create(u32 (* hash_value)(struct hashtab * h,const void * key),int (* keycmp)(struct hashtab * h,const void * key1,const void * key2),u32 size)14 struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h,
15 const void *key),
16 int (*keycmp)(struct hashtab *h, const void *key1,
17 const void *key2), u32 size)
18 {
19 struct hashtab *p = xzalloc(struct hashtab);
20
21 if ( p == NULL )
22 return p;
23
24 p->size = size;
25 p->hash_value = hash_value;
26 p->keycmp = keycmp;
27 p->htable = xzalloc_array(struct hashtab_node *, size);
28 if ( p->htable == NULL )
29 {
30 xfree(p);
31 return NULL;
32 }
33
34 return p;
35 }
36
hashtab_insert(struct hashtab * h,void * key,void * datum)37 int hashtab_insert(struct hashtab *h, void *key, void *datum)
38 {
39 u32 hvalue;
40 struct hashtab_node *prev, *cur, *newnode;
41
42 if ( !h || h->nel == HASHTAB_MAX_NODES )
43 return -EINVAL;
44
45 hvalue = h->hash_value(h, key);
46 prev = NULL;
47 cur = h->htable[hvalue];
48 while ( cur && h->keycmp(h, key, cur->key) > 0 )
49 {
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 = xzalloc(struct hashtab_node);
58 if ( newnode == NULL )
59 return -ENOMEM;
60 newnode->key = key;
61 newnode->datum = datum;
62 if ( prev )
63 {
64 newnode->next = prev->next;
65 prev->next = newnode;
66 }
67 else
68 {
69 newnode->next = h->htable[hvalue];
70 h->htable[hvalue] = newnode;
71 }
72
73 h->nel++;
74 return 0;
75 }
76
hashtab_search(struct hashtab * h,const void * key)77 void *hashtab_search(struct hashtab *h, const void *key)
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];
87 while ( cur != NULL && h->keycmp(h, key, cur->key) > 0 )
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
hashtab_destroy(struct hashtab * h)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 {
106 cur = h->htable[i];
107 while ( cur != NULL )
108 {
109 temp = cur;
110 cur = cur->next;
111 xfree(temp);
112 }
113 h->htable[i] = NULL;
114 }
115
116 xfree(h->htable);
117 h->htable = NULL;
118
119 xfree(h);
120 }
121
hashtab_map(struct hashtab * h,int (* apply)(void * k,void * d,void * args),void * args)122 int hashtab_map(struct hashtab *h,
123 int (*apply)(void *k, void *d, void *args),
124 void *args)
125 {
126 u32 i;
127 int ret;
128 struct hashtab_node *cur;
129
130 if ( !h )
131 return 0;
132
133 for ( i = 0; i < h->size; i++ )
134 {
135 cur = h->htable[i];
136 while ( cur != NULL )
137 {
138 ret = apply(cur->key, cur->datum, args);
139 if ( ret )
140 return ret;
141 cur = cur->next;
142 }
143 }
144 return 0;
145 }
146
147
hashtab_stat(struct hashtab * h,struct hashtab_info * info)148 void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
149 {
150 u32 i, chain_len, slots_used, max_chain_len;
151 struct hashtab_node *cur;
152
153 slots_used = 0;
154 max_chain_len = 0;
155 for ( slots_used = max_chain_len = i = 0; i < h->size; i++ )
156 {
157 cur = h->htable[i];
158 if ( cur )
159 {
160 slots_used++;
161 chain_len = 0;
162 while ( cur )
163 {
164 chain_len++;
165 cur = cur->next;
166 }
167
168 if ( chain_len > max_chain_len )
169 max_chain_len = chain_len;
170 }
171 }
172
173 info->slots_used = slots_used;
174 info->max_chain_len = max_chain_len;
175 }
176