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 * 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 */ 43 struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key), 44 int (*keycmp)(struct hashtab *h, const void *key1, const void *key2), 45 u32 size); 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 53 0 otherwise. 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 */ 63 void *hashtab_search(struct hashtab *h, const void *k); 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 /* Use kmem_cache for hashtab_node */ 89 void hashtab_cache_init(void); 90 void hashtab_cache_destroy(void); 91 92 #endif /* _SS_HASHTAB_H */ 93