1 2 /* Author : Stephen Smalley, <sds (at) tycho.nsa.gov> */ 3 4 /* FLASK */ 5 6 /* 7 * Implementation of the hash table type. 8 */ 9 10 #include <stdlib.h> 11 #include <string.h> 12 #include "hashtab.h" 13 14 hashtab_t hashtab_create(unsigned int (*hash_value) (hashtab_t h, 15 const_hashtab_key_t key), 16 int (*keycmp) (hashtab_t h, 17 const_hashtab_key_t key1, 18 const_hashtab_key_t key2), 19 unsigned int size) 20 { 21 22 hashtab_t p; 23 unsigned int i; 24 25 p = (hashtab_t) malloc(sizeof(hashtab_val_t)); 26 if (p == NULL) 27 return p; 28 29 memset(p, 0, sizeof(hashtab_val_t)); 30 p->size = size; 31 p->nel = 0; 32 p->hash_value = hash_value; 33 p->keycmp = keycmp; 34 p->htable = (hashtab_ptr_t *) malloc(sizeof(hashtab_ptr_t) * size); 35 if (p->htable == NULL) { 36 free(p); 37 return NULL; 38 } 39 for (i = 0; i < size; i++) 40 p->htable[i] = (hashtab_ptr_t) NULL; 41 42 return p; 43 } 44 45 int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum) 46 { 47 int hvalue; 48 hashtab_ptr_t prev, cur, newnode; 49 50 if (!h) 51 return HASHTAB_OVERFLOW; 52 53 hvalue = h->hash_value(h, key); 54 prev = NULL; 55 cur = h->htable[hvalue]; 56 while (cur && h->keycmp(h, key, cur->key) > 0) { 57 prev = cur; 58 cur = cur->next; 59 } 60 61 if (cur && (h->keycmp(h, key, cur->key) == 0)) 62 return HASHTAB_PRESENT; 63 64 newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t)); 65 if (newnode == NULL) 66 return HASHTAB_OVERFLOW; 67 memset(newnode, 0, sizeof(struct hashtab_node)); 68 newnode->key = key; 69 newnode->datum = datum; 70 if (prev) { 71 newnode->next = prev->next; 72 prev->next = newnode; 73 } else { 74 newnode->next = h->htable[hvalue]; 75 h->htable[hvalue] = newnode; 76 } 77 78 h->nel++; 79 return HASHTAB_SUCCESS; 80 } 81 82 int hashtab_remove(hashtab_t h, hashtab_key_t key, 83 void (*destroy) (hashtab_key_t k, 84 hashtab_datum_t d, void *args), void *args) 85 { 86 int hvalue; 87 hashtab_ptr_t cur, last; 88 89 if (!h) 90 return HASHTAB_MISSING; 91 92 hvalue = h->hash_value(h, key); 93 last = NULL; 94 cur = h->htable[hvalue]; 95 while (cur != NULL && h->keycmp(h, key, cur->key) > 0) { 96 last = cur; 97 cur = cur->next; 98 } 99 100 if (cur == NULL || (h->keycmp(h, key, cur->key) != 0)) 101 return HASHTAB_MISSING; 102 103 if (last == NULL) 104 h->htable[hvalue] = cur->next; 105 else 106 last->next = cur->next; 107 108 if (destroy) 109 destroy(cur->key, cur->datum, args); 110 free(cur); 111 h->nel--; 112 return HASHTAB_SUCCESS; 113 } 114 115 int hashtab_replace(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum, 116 void (*destroy) (hashtab_key_t k, 117 hashtab_datum_t d, void *args), void *args) 118 { 119 int hvalue; 120 hashtab_ptr_t prev, cur, newnode; 121 122 if (!h) 123 return HASHTAB_OVERFLOW; 124 125 hvalue = h->hash_value(h, key); 126 prev = NULL; 127 cur = h->htable[hvalue]; 128 while (cur != NULL && h->keycmp(h, key, cur->key) > 0) { 129 prev = cur; 130 cur = cur->next; 131 } 132 133 if (cur && (h->keycmp(h, key, cur->key) == 0)) { 134 if (destroy) 135 destroy(cur->key, cur->datum, args); 136 cur->key = key; 137 cur->datum = datum; 138 } else { 139 newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t)); 140 if (newnode == NULL) 141 return HASHTAB_OVERFLOW; 142 memset(newnode, 0, sizeof(struct hashtab_node)); 143 newnode->key = key; 144 newnode->datum = datum; 145 if (prev) { 146 newnode->next = prev->next; 147 prev->next = newnode; 148 } else { 149 newnode->next = h->htable[hvalue]; 150 h->htable[hvalue] = newnode; 151 } 152 } 153 154 return HASHTAB_SUCCESS; 155 } 156 157 hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t key) 158 { 159 160 int hvalue; 161 hashtab_ptr_t cur; 162 163 if (!h) 164 return NULL; 165 166 hvalue = h->hash_value(h, key); 167 cur = h->htable[hvalue]; 168 while (cur != NULL && h->keycmp(h, key, cur->key) > 0) 169 cur = cur->next; 170 171 if (cur == NULL || (h->keycmp(h, key, cur->key) != 0)) 172 return NULL; 173 174 return cur->datum; 175 } 176 177 void hashtab_destroy(hashtab_t h) 178 { 179 unsigned int i; 180 hashtab_ptr_t cur, temp; 181 182 if (!h) 183 return; 184 185 for (i = 0; i < h->size; i++) { 186 cur = h->htable[i]; 187 while (cur != NULL) { 188 temp = cur; 189 cur = cur->next; 190 free(temp); 191 } 192 h->htable[i] = NULL; 193 } 194 195 free(h->htable); 196 h->htable = NULL; 197 198 free(h); 199 } 200 201 int hashtab_map(hashtab_t h, 202 int (*apply) (hashtab_key_t k, 203 hashtab_datum_t d, void *args), void *args) 204 { 205 unsigned int i, ret; 206 hashtab_ptr_t cur; 207 208 if (!h) 209 return HASHTAB_SUCCESS; 210 211 for (i = 0; i < h->size; i++) { 212 cur = h->htable[i]; 213 while (cur != NULL) { 214 ret = apply(cur->key, cur->datum, args); 215 if (ret) 216 return ret; 217 cur = cur->next; 218 } 219 } 220 return HASHTAB_SUCCESS; 221 } 222 223 void hashtab_map_remove_on_error(hashtab_t h, 224 int (*apply) (hashtab_key_t k, 225 hashtab_datum_t d, 226 void *args), 227 void (*destroy) (hashtab_key_t k, 228 hashtab_datum_t d, 229 void *args), void *args) 230 { 231 unsigned int i; 232 int ret; 233 hashtab_ptr_t last, cur, temp; 234 235 if (!h) 236 return; 237 238 for (i = 0; i < h->size; i++) { 239 last = NULL; 240 cur = h->htable[i]; 241 while (cur != NULL) { 242 ret = apply(cur->key, cur->datum, args); 243 if (ret) { 244 if (last) { 245 last->next = cur->next; 246 } else { 247 h->htable[i] = cur->next; 248 } 249 250 temp = cur; 251 cur = cur->next; 252 if (destroy) 253 destroy(temp->key, temp->datum, args); 254 free(temp); 255 h->nel--; 256 } else { 257 last = cur; 258 cur = cur->next; 259 } 260 } 261 } 262 263 return; 264 } 265 266 void hashtab_hash_eval(hashtab_t h, char *tag) 267 { 268 unsigned int i; 269 int chain_len, slots_used, max_chain_len; 270 hashtab_ptr_t cur; 271 272 slots_used = 0; 273 max_chain_len = 0; 274 for (i = 0; i < h->size; i++) { 275 cur = h->htable[i]; 276 if (cur) { 277 slots_used++; 278 chain_len = 0; 279 while (cur) { 280 chain_len++; 281 cur = cur->next; 282 } 283 284 if (chain_len > max_chain_len) 285 max_chain_len = chain_len; 286 } 287 } 288 289 printf 290 ("%s: %d entries and %d/%d buckets used, longest chain length %d\n", 291 tag, h->nel, slots_used, h->size, max_chain_len); 292 } 293
