2
/* Author : Stephen Smalley, <sds@epoch.ncsc.mil> */
7
* Implementation of the hash table type.
12
hashtab_t hashtab_create(unsigned int (*hash_value) (hashtab_t h,
14
int (*keycmp) (hashtab_t h,
23
p = (hashtab_t) kmalloc(sizeof(hashtab_val_t),GFP_KERNEL);
27
memset(p, 0, sizeof(hashtab_val_t));
30
p->hash_value = hash_value;
32
p->htable = (hashtab_ptr_t *) kmalloc(sizeof(hashtab_ptr_t) * size,GFP_KERNEL);
33
if (p->htable == NULL) {
37
for (i = 0; i < size; i++)
38
p->htable[i] = (hashtab_ptr_t) NULL;
44
int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum)
47
hashtab_ptr_t prev, cur, newnode;
51
return HASHTAB_OVERFLOW;
53
hvalue = h->hash_value(h, key);
55
cur = h->htable[hvalue];
56
while (cur && h->keycmp(h, key, cur->key) > 0) {
61
if (cur && (h->keycmp(h, key, cur->key) == 0))
62
return HASHTAB_PRESENT;
64
newnode = (hashtab_ptr_t) kmalloc(sizeof(hashtab_node_t),GFP_KERNEL);
66
return HASHTAB_OVERFLOW;
67
memset(newnode, 0, sizeof(struct hashtab_node));
69
newnode->datum = datum;
71
newnode->next = prev->next;
74
newnode->next = h->htable[hvalue];
75
h->htable[hvalue] = newnode;
79
return HASHTAB_SUCCESS;
83
int hashtab_remove(hashtab_t h, hashtab_key_t key,
84
void (*destroy) (hashtab_key_t k,
90
hashtab_ptr_t cur, last;
94
return HASHTAB_MISSING;
96
hvalue = h->hash_value(h, key);
98
cur = h->htable[hvalue];
99
while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
104
if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
105
return HASHTAB_MISSING;
108
h->htable[hvalue] = cur->next;
110
last->next = cur->next;
113
destroy(cur->key, cur->datum, args);
116
return HASHTAB_SUCCESS;
120
int hashtab_replace(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum,
121
void (*destroy) (hashtab_key_t k,
127
hashtab_ptr_t prev, cur, newnode;
131
return HASHTAB_OVERFLOW;
133
hvalue = h->hash_value(h, key);
135
cur = h->htable[hvalue];
136
while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
141
if (cur && (h->keycmp(h, key, cur->key) == 0)) {
143
destroy(cur->key, cur->datum, args);
147
newnode = (hashtab_ptr_t) kmalloc(sizeof(hashtab_node_t),GFP_KERNEL);
149
return HASHTAB_OVERFLOW;
150
memset(newnode, 0, sizeof(struct hashtab_node));
152
newnode->datum = datum;
154
newnode->next = prev->next;
155
prev->next = newnode;
157
newnode->next = h->htable[hvalue];
158
h->htable[hvalue] = newnode;
162
return HASHTAB_SUCCESS;
167
hashtab_search(hashtab_t h, hashtab_key_t key)
176
hvalue = h->hash_value(h, key);
177
cur = h->htable[hvalue];
178
while (cur != NULL && h->keycmp(h, key, cur->key) > 0)
181
if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
188
void hashtab_destroy(hashtab_t h)
191
hashtab_ptr_t cur, temp;
197
for (i = 0; i < h->size; i++) {
199
while (cur != NULL) {
214
int hashtab_map(hashtab_t h,
215
int (*apply) (hashtab_key_t k,
225
return HASHTAB_SUCCESS;
227
for (i = 0; i < h->size; i++) {
229
while (cur != NULL) {
230
ret = apply(cur->key, cur->datum, args);
236
return HASHTAB_SUCCESS;
240
void hashtab_map_remove_on_error(hashtab_t h,
241
int (*apply) (hashtab_key_t k,
244
void (*destroy) (hashtab_key_t k,
251
hashtab_ptr_t last, cur, temp;
257
for (i = 0; i < h->size; i++) {
260
while (cur != NULL) {
261
ret = apply(cur->key, cur->datum, args);
264
last->next = cur->next;
266
h->htable[i] = cur->next;
272
destroy(temp->key, temp->datum, args);
285
void hashtab_hash_eval(hashtab_t h, char *tag)
288
int chain_len, slots_used, max_chain_len;
294
for (i = 0; i < h->size; i++) {
304
if (chain_len > max_chain_len)
305
max_chain_len = chain_len;
309
printk("%s: %d entries and %d/%d buckets used, longest chain length %d\n",
310
tag, h->nel, slots_used, h->size, max_chain_len);