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