Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame^] | 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, void *key); |
| 26 | /* hash function */ |
| 27 | int (*keycmp)(struct hashtab *h, void *key1, 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, void *key), |
| 43 | int (*keycmp)(struct hashtab *h, void *key1, 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, 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 */ |