]>
Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * A hash table (hashtab) maintains associations between | |
3 | * key values and datum values. The type of the key values | |
4 | * and the type of the datum values is arbitrary. The | |
5 | * functions for hash computation and key comparison are | |
6 | * provided by the creator of the table. | |
7 | * | |
7efbb60b | 8 | * Author : Stephen Smalley, <sds@tycho.nsa.gov> |
1da177e4 LT |
9 | */ |
10 | #ifndef _SS_HASHTAB_H_ | |
11 | #define _SS_HASHTAB_H_ | |
12 | ||
13 | #define HASHTAB_MAX_NODES 0xffffffff | |
14 | ||
15 | struct hashtab_node { | |
16 | void *key; | |
17 | void *datum; | |
18 | struct hashtab_node *next; | |
19 | }; | |
20 | ||
21 | struct hashtab { | |
22 | struct hashtab_node **htable; /* hash table */ | |
23 | u32 size; /* number of slots in hash table */ | |
24 | u32 nel; /* number of elements in hash table */ | |
bb242497 | 25 | u32 (*hash_value)(struct hashtab *h, const void *key); |
1da177e4 | 26 | /* hash function */ |
bb242497 | 27 | int (*keycmp)(struct hashtab *h, const void *key1, const void *key2); |
1da177e4 LT |
28 | /* key comparison function */ |
29 | }; | |
30 | ||
31 | struct hashtab_info { | |
32 | u32 slots_used; | |
33 | u32 max_chain_len; | |
34 | }; | |
35 | ||
36 | /* | |
37 | * Creates a new hash table with the specified characteristics. | |
38 | * | |
39 | * Returns NULL if insufficent space is available or | |
40 | * the new hash table otherwise. | |
41 | */ | |
bb242497 | 42 | struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key), |
faff786c EP |
43 | int (*keycmp)(struct hashtab *h, const void *key1, const void *key2), |
44 | u32 size); | |
1da177e4 LT |
45 | |
46 | /* | |
47 | * Inserts the specified (key, datum) pair into the specified hash table. | |
48 | * | |
49 | * Returns -ENOMEM on memory allocation error, | |
50 | * -EEXIST if there is already an entry with the same key, | |
51 | * -EINVAL for general errors or | |
faff786c | 52 | 0 otherwise. |
1da177e4 LT |
53 | */ |
54 | int hashtab_insert(struct hashtab *h, void *k, void *d); | |
55 | ||
56 | /* | |
57 | * Searches for the entry with the specified key in the hash table. | |
58 | * | |
59 | * Returns NULL if no entry has the specified key or | |
60 | * the datum of the entry otherwise. | |
61 | */ | |
bb242497 | 62 | void *hashtab_search(struct hashtab *h, const void *k); |
1da177e4 LT |
63 | |
64 | /* | |
65 | * Destroys the specified hash table. | |
66 | */ | |
67 | void hashtab_destroy(struct hashtab *h); | |
68 | ||
69 | /* | |
70 | * Applies the specified apply function to (key,datum,args) | |
71 | * for each entry in the specified hash table. | |
72 | * | |
73 | * The order in which the function is applied to the entries | |
74 | * is dependent upon the internal structure of the hash table. | |
75 | * | |
76 | * If apply returns a non-zero status, then hashtab_map will cease | |
77 | * iterating through the hash table and will propagate the error | |
78 | * return to its caller. | |
79 | */ | |
80 | int hashtab_map(struct hashtab *h, | |
81 | int (*apply)(void *k, void *d, void *args), | |
82 | void *args); | |
83 | ||
84 | /* Fill info with some hash table statistics */ | |
85 | void hashtab_stat(struct hashtab *h, struct hashtab_info *info); | |
86 | ||
87 | #endif /* _SS_HASHTAB_H */ |