1 2 /* Author : Stephen Smalley, <sds@epoch.ncsc.mil> */ 3 4 /* FLASK */ 5 6 /* 7 * A hash table (hashtab) maintains associations between 8 * key values and datum values. The type of the key values 9 * and the type of the datum values is arbitrary. The 10 * functions for hash computation and key comparison are 11 * provided by the creator of the table. 12 */ 13 14 #ifndef _NEWROLE_HASHTAB_H_ 15 #define _NEWROLE_HASHTAB_H_ 16 17 #include <stdint.h> 18 #include <errno.h> 19 #include <stdio.h> 20 21 typedef char *hashtab_key_t; /* generic key type */ 22 typedef void *hashtab_datum_t; /* generic datum type */ 23 24 typedef struct hashtab_node *hashtab_ptr_t; 25 26 typedef struct hashtab_node { 27 hashtab_key_t key; 28 hashtab_datum_t datum; 29 hashtab_ptr_t next; 30 } hashtab_node_t; 31 32 typedef struct hashtab_val { 33 hashtab_ptr_t *htable; /* hash table */ 34 unsigned int size; /* number of slots in hash table */ 35 uint32_t nel; /* number of elements in hash table */ 36 unsigned int (*hash_value) (struct hashtab_val * h, hashtab_key_t key); /* hash function */ 37 int (*keycmp) (struct hashtab_val * h, hashtab_key_t key1, hashtab_key_t key2); /* key comparison function */ 38 } hashtab_val_t; 39 40 typedef hashtab_val_t *hashtab_t; 41 42 /* Define status codes for hash table functions */ 43 #define HASHTAB_SUCCESS 0 44 #define HASHTAB_OVERFLOW -ENOMEM 45 #define HASHTAB_PRESENT -EEXIST 46 #define HASHTAB_MISSING -ENOENT 47 48 /* 49 Creates a new hash table with the specified characteristics. 50 51 Returns NULL if insufficent space is available or 52 the new hash table otherwise. 53 */ 54 extern hashtab_t hashtab_create(unsigned int (*hash_value) (hashtab_t h, 55 const hashtab_key_t 56 key), 57 int (*keycmp) (hashtab_t h, 58 const hashtab_key_t key1, 59 const hashtab_key_t key2), 60 unsigned int size); 61 /* 62 Inserts the specified (key, datum) pair into the specified hash table. 63 64 Returns HASHTAB_OVERFLOW if insufficient space is available or 65 HASHTAB_PRESENT if there is already an entry with the same key or 66 HASHTAB_SUCCESS otherwise. 67 */ 68 extern int hashtab_insert(hashtab_t h, hashtab_key_t k, hashtab_datum_t d); 69 70 /* 71 Removes the entry with the specified key from the hash table. 72 Applies the specified destroy function to (key,datum,args) for 73 the entry. 74 75 Returns HASHTAB_MISSING if no entry has the specified key or 76 HASHTAB_SUCCESS otherwise. 77 */ 78 extern int hashtab_remove(hashtab_t h, hashtab_key_t k, 79 void (*destroy) (hashtab_key_t k, 80 hashtab_datum_t d, 81 void *args), void *args); 82 83 /* 84 Insert or replace the specified (key, datum) pair in the specified 85 hash table. If an entry for the specified key already exists, 86 then the specified destroy function is applied to (key,datum,args) 87 for the entry prior to replacing the entry's contents. 88 89 Returns HASHTAB_OVERFLOW if insufficient space is available or 90 HASHTAB_SUCCESS otherwise. 91 */ 92 extern int hashtab_replace(hashtab_t h, hashtab_key_t k, hashtab_datum_t d, 93 void (*destroy) (hashtab_key_t k, 94 hashtab_datum_t d, 95 void *args), void *args); 96 97 /* 98 Searches for the entry with the specified key in the hash table. 99 100 Returns NULL if no entry has the specified key or 101 the datum of the entry otherwise. 102 */ 103 extern hashtab_datum_t hashtab_search(hashtab_t h, const hashtab_key_t k); 104 105 /* 106 Destroys the specified hash table. 107 */ 108 extern void hashtab_destroy(hashtab_t h); 109 110 /* 111 Applies the specified apply function to (key,datum,args) 112 for each entry in the specified hash table. 113 114 The order in which the function is applied to the entries 115 is dependent upon the internal structure of the hash table. 116 117 If apply returns a non-zero status, then hashtab_map will cease 118 iterating through the hash table and will propagate the error 119 return to its caller. 120 */ 121 extern int hashtab_map(hashtab_t h, 122 int (*apply) (hashtab_key_t k, 123 hashtab_datum_t d, 124 void *args), void *args); 125 126 /* 127 Same as hashtab_map, except that if apply returns a non-zero status, 128 then the (key,datum) pair will be removed from the hashtab and the 129 destroy function will be applied to (key,datum,args). 130 */ 131 extern void hashtab_map_remove_on_error(hashtab_t h, 132 int (*apply) (hashtab_key_t k, 133 hashtab_datum_t d, 134 void *args), 135 void (*destroy) (hashtab_key_t k, 136 hashtab_datum_t d, 137 void *args), 138 void *args); 139 140 extern void hashtab_hash_eval(hashtab_t h, char *tag); 141 142 #endif 143