2 * Implementation of the hash table type.
4 * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
6 #include <linux/kernel.h>
7 #include <linux/slab.h>
8 #include <linux/errno.h>
11 struct hashtab
*hashtab_create(u32 (*hash_value
)(struct hashtab
*h
, void *key
),
12 int (*keycmp
)(struct hashtab
*h
, void *key1
, void *key2
),
18 p
= kmalloc(sizeof(*p
), GFP_KERNEL
);
22 memset(p
, 0, sizeof(*p
));
25 p
->hash_value
= hash_value
;
27 p
->htable
= kmalloc(sizeof(*(p
->htable
)) * size
, GFP_KERNEL
);
28 if (p
->htable
== NULL
) {
33 for (i
= 0; i
< size
; i
++)
39 int hashtab_insert(struct hashtab
*h
, void *key
, void *datum
)
42 struct hashtab_node
*prev
, *cur
, *newnode
;
44 if (!h
|| h
->nel
== HASHTAB_MAX_NODES
)
47 hvalue
= h
->hash_value(h
, key
);
49 cur
= h
->htable
[hvalue
];
50 while (cur
&& h
->keycmp(h
, key
, cur
->key
) > 0) {
55 if (cur
&& (h
->keycmp(h
, key
, cur
->key
) == 0))
58 newnode
= kmalloc(sizeof(*newnode
), GFP_KERNEL
);
61 memset(newnode
, 0, sizeof(*newnode
));
63 newnode
->datum
= datum
;
65 newnode
->next
= prev
->next
;
68 newnode
->next
= h
->htable
[hvalue
];
69 h
->htable
[hvalue
] = newnode
;
76 void *hashtab_search(struct hashtab
*h
, void *key
)
79 struct hashtab_node
*cur
;
84 hvalue
= h
->hash_value(h
, key
);
85 cur
= h
->htable
[hvalue
];
86 while (cur
!= NULL
&& h
->keycmp(h
, key
, cur
->key
) > 0)
89 if (cur
== NULL
|| (h
->keycmp(h
, key
, cur
->key
) != 0))
95 void hashtab_destroy(struct hashtab
*h
)
98 struct hashtab_node
*cur
, *temp
;
103 for (i
= 0; i
< h
->size
; i
++) {
105 while (cur
!= NULL
) {
119 int hashtab_map(struct hashtab
*h
,
120 int (*apply
)(void *k
, void *d
, void *args
),
125 struct hashtab_node
*cur
;
130 for (i
= 0; i
< h
->size
; i
++) {
132 while (cur
!= NULL
) {
133 ret
= apply(cur
->key
, cur
->datum
, args
);
143 void hashtab_stat(struct hashtab
*h
, struct hashtab_info
*info
)
145 u32 i
, chain_len
, slots_used
, max_chain_len
;
146 struct hashtab_node
*cur
;
150 for (slots_used
= max_chain_len
= i
= 0; i
< h
->size
; i
++) {
160 if (chain_len
> max_chain_len
)
161 max_chain_len
= chain_len
;
165 info
->slots_used
= slots_used
;
166 info
->max_chain_len
= max_chain_len
;