1 /* SPDX-License-Identifier: GPL-2.0 */ 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 * 9 * Author : Stephen Smalley, <sds@tycho.nsa.gov> 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 */ 26 u32 (*hash_value)(struct hashtab *h, const void *key); 27 /* hash function */ 28 int (*keycmp)(struct hashtab *h, const void *key1, const void *key2); 29 /* key comparison function */ 30 }; 31 32 struct hashtab_info { 33 u32 slots_used; 34 u32 max_chain_len; 35 }; 36 37 /* 38 * Initializes a new hash table with the specified characteristics. 39 * 40 * Returns -ENOMEM if insufficient space is available or 0 otherwise. 41 */ 42 int hashtab_init(struct hashtab *h, 43 u32 (*hash_value)(struct hashtab *h, const void *key), 44 int (*keycmp)(struct hashtab *h, const void *key1, 45 const void *key2), 46 u32 nel_hint); 47 48 /* 49 * Inserts the specified (key, datum) pair into the specified hash table. 50 * 51 * Returns -ENOMEM on memory allocation error, 52 * -EEXIST if there is already an entry with the same key, 53 * -EINVAL for general errors or 54 0 otherwise. 55 */ 56 int hashtab_insert(struct hashtab *h, void *k, void *d); 57 58 /* 59 * Searches for the entry with the specified key in the hash table. 60 * 61 * Returns NULL if no entry has the specified key or 62 * the datum of the entry otherwise. 63 */ 64 void *hashtab_search(struct hashtab *h, const void *k); 65 66 /* 67 * Destroys the specified hash table. 68 */ 69 void hashtab_destroy(struct hashtab *h); 70 71 /* 72 * Applies the specified apply function to (key,datum,args) 73 * for each entry in the specified hash table. 74 * 75 * The order in which the function is applied to the entries 76 * is dependent upon the internal structure of the hash table. 77 * 78 * If apply returns a non-zero status, then hashtab_map will cease 79 * iterating through the hash table and will propagate the error 80 * return to its caller. 81 */ 82 int hashtab_map(struct hashtab *h, 83 int (*apply)(void *k, void *d, void *args), 84 void *args); 85 86 /* Fill info with some hash table statistics */ 87 void hashtab_stat(struct hashtab *h, struct hashtab_info *info); 88 89 #endif /* _SS_HASHTAB_H */ 90