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 * 8 * Author : Stephen Smalley, <sds@epoch.ncsc.mil> 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 */ 25 u32 (*hash_value)(struct hashtab *h, const void *key); 26 /* hash function */ 27 int (*keycmp)(struct hashtab *h, const void *key1, const void *key2); 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 */ 42 struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key), 43 int (*keycmp)(struct hashtab *h, const void *key1, const void *key2), 44 u32 size); 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 52 0 otherwise. 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 */ 62 void *hashtab_search(struct hashtab *h, const void *k); 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 */ 88