1 /* hash.c -- hash table maintenance 2 Copyright (C) 1995, 1999, 2002 Free Software Foundation, Inc. 3 Written by Greg McGary <gkm (at) gnu.org> <greg (at) mcgary.org> 4 5 This program is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation; either version 2, or (at your option) 8 any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License along with 16 this program; see the file COPYING. If not, write to the Free Software 17 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. */ 18 19 #include "make.h" 20 #include "hash.h" 21 22 #define CALLOC(t, n) ((t *) calloc (sizeof (t), (n))) 23 #define MALLOC(t, n) ((t *) xmalloc (sizeof (t) * (n))) 24 #define REALLOC(o, t, n) ((t *) xrealloc ((o), sizeof (t) * (n))) 25 #define CLONE(o, t, n) ((t *) memcpy (MALLOC (t, (n)), (o), sizeof (t) * (n))) 26 27 static void hash_rehash __P((struct hash_table* ht)); 28 static unsigned long round_up_2 __P((unsigned long rough)); 29 30 /* Implement double hashing with open addressing. The table size is 31 always a power of two. The secondary (`increment') hash function 32 is forced to return an odd-value, in order to be relatively prime 33 to the table size. This guarantees that the increment can 34 potentially hit every slot in the table during collision 35 resolution. */ 36 37 void *hash_deleted_item = &hash_deleted_item; 38 39 /* Force the table size to be a power of two, possibly rounding up the 40 given size. */ 41 42 void 43 hash_init (struct hash_table *ht, unsigned long size, 44 hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp) 45 { 46 ht->ht_size = round_up_2 (size); 47 ht->ht_empty_slots = ht->ht_size; 48 ht->ht_vec = (void**) CALLOC (struct token *, ht->ht_size); 49 if (ht->ht_vec == 0) 50 { 51 fprintf (stderr, _("can't allocate %ld bytes for hash table: memory exhausted"), 52 ht->ht_size * sizeof(struct token *)); 53 exit (1); 54 } 55 56 ht->ht_capacity = ht->ht_size - (ht->ht_size / 16); /* 93.75% loading factor */ 57 ht->ht_fill = 0; 58 ht->ht_collisions = 0; 59 ht->ht_lookups = 0; 60 ht->ht_rehashes = 0; 61 ht->ht_hash_1 = hash_1; 62 ht->ht_hash_2 = hash_2; 63 ht->ht_compare = hash_cmp; 64 } 65 66 /* Load an array of items into `ht'. */ 67 68 void 69 hash_load (struct hash_table *ht, void *item_table, 70 unsigned long cardinality, unsigned long size) 71 { 72 char *items = (char *) item_table; 73 while (cardinality--) 74 { 75 hash_insert (ht, items); 76 items += size; 77 } 78 } 79 80 /* Returns the address of the table slot matching `key'. If `key' is 81 not found, return the address of an empty slot suitable for 82 inserting `key'. The caller is responsible for incrementing 83 ht_fill on insertion. */ 84 85 void ** 86 hash_find_slot (struct hash_table *ht, const void *key) 87 { 88 void **slot; 89 void **deleted_slot = 0; 90 unsigned int hash_2 = 0; 91 unsigned int hash_1 = (*ht->ht_hash_1) (key); 92 93 ht->ht_lookups++; 94 for (;;) 95 { 96 hash_1 &= (ht->ht_size - 1); 97 slot = &ht->ht_vec[hash_1]; 98 99 if (*slot == 0) 100 return (deleted_slot ? deleted_slot : slot); 101 if (*slot == hash_deleted_item) 102 { 103 if (deleted_slot == 0) 104 deleted_slot = slot; 105 } 106 else 107 { 108 if (key == *slot) 109 return slot; 110 if ((*ht->ht_compare) (key, *slot) == 0) 111 return slot; 112 ht->ht_collisions++; 113 } 114 if (!hash_2) 115 hash_2 = (*ht->ht_hash_2) (key) | 1; 116 hash_1 += hash_2; 117 } 118 } 119 120 void * 121 hash_find_item (struct hash_table *ht, const void *key) 122 { 123 void **slot = hash_find_slot (ht, key); 124 return ((HASH_VACANT (*slot)) ? 0 : *slot); 125 } 126 127 void * 128 hash_insert (struct hash_table *ht, const void *item) 129 { 130 void **slot = hash_find_slot (ht, item); 131 const void *old_item = slot ? *slot : 0; 132 hash_insert_at (ht, item, slot); 133 return (void *)((HASH_VACANT (old_item)) ? 0 : old_item); 134 } 135 136 void * 137 hash_insert_at (struct hash_table *ht, const void *item, const void *slot) 138 { 139 const void *old_item = *(void **) slot; 140 if (HASH_VACANT (old_item)) 141 { 142 ht->ht_fill++; 143 if (old_item == 0) 144 ht->ht_empty_slots--; 145 old_item = item; 146 } 147 *(void const **) slot = item; 148 if (ht->ht_empty_slots < ht->ht_size - ht->ht_capacity) 149 { 150 hash_rehash (ht); 151 return (void *) hash_find_slot (ht, item); 152 } 153 else 154 return (void *) slot; 155 } 156 157 void * 158 hash_delete (struct hash_table *ht, const void *item) 159 { 160 void **slot = hash_find_slot (ht, item); 161 return hash_delete_at (ht, slot); 162 } 163 164 void * 165 hash_delete_at (struct hash_table *ht, const void *slot) 166 { 167 void *item = *(void **) slot; 168 if (!HASH_VACANT (item)) 169 { 170 *(void const **) slot = hash_deleted_item; 171 ht->ht_fill--; 172 return item; 173 } 174 else 175 return 0; 176 } 177 178 void 179 hash_free_items (struct hash_table *ht) 180 { 181 void **vec = ht->ht_vec; 182 void **end = &vec[ht->ht_size]; 183 for (; vec < end; vec++) 184 { 185 void *item = *vec; 186 if (!HASH_VACANT (item)) 187 free (item); 188 *vec = 0; 189 } 190 ht->ht_fill = 0; 191 ht->ht_empty_slots = ht->ht_size; 192 } 193 194 void 195 hash_delete_items (struct hash_table *ht) 196 { 197 void **vec = ht->ht_vec; 198 void **end = &vec[ht->ht_size]; 199 for (; vec < end; vec++) 200 *vec = 0; 201 ht->ht_fill = 0; 202 ht->ht_collisions = 0; 203 ht->ht_lookups = 0; 204 ht->ht_rehashes = 0; 205 ht->ht_empty_slots = ht->ht_size; 206 } 207 208 void 209 hash_free (struct hash_table *ht, int free_items) 210 { 211 if (free_items) 212 hash_free_items (ht); 213 else 214 { 215 ht->ht_fill = 0; 216 ht->ht_empty_slots = ht->ht_size; 217 } 218 free (ht->ht_vec); 219 ht->ht_vec = 0; 220 ht->ht_capacity = 0; 221 } 222 223 void 224 hash_map (struct hash_table *ht, hash_map_func_t map) 225 { 226 void **slot; 227 void **end = &ht->ht_vec[ht->ht_size]; 228 229 for (slot = ht->ht_vec; slot < end; slot++) 230 { 231 if (!HASH_VACANT (*slot)) 232 (*map) (*slot); 233 } 234 } 235 236 void 237 hash_map_arg (struct hash_table *ht, hash_map_arg_func_t map, void *arg) 238 { 239 void **slot; 240 void **end = &ht->ht_vec[ht->ht_size]; 241 242 for (slot = ht->ht_vec; slot < end; slot++) 243 { 244 if (!HASH_VACANT (*slot)) 245 (*map) (*slot, arg); 246 } 247 } 248 249 /* Double the size of the hash table in the event of overflow... */ 250 251 static void 252 hash_rehash (struct hash_table *ht) 253 { 254 unsigned long old_ht_size = ht->ht_size; 255 void **old_vec = ht->ht_vec; 256 void **ovp; 257 258 if (ht->ht_fill >= ht->ht_capacity) 259 { 260 ht->ht_size *= 2; 261 ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4); 262 } 263 ht->ht_rehashes++; 264 ht->ht_vec = (void **) CALLOC (struct token *, ht->ht_size); 265 266 for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++) 267 { 268 if (! HASH_VACANT (*ovp)) 269 { 270 void **slot = hash_find_slot (ht, *ovp); 271 *slot = *ovp; 272 } 273 } 274 ht->ht_empty_slots = ht->ht_size - ht->ht_fill; 275 free (old_vec); 276 } 277 278 void 279 hash_print_stats (struct hash_table *ht, FILE *out_FILE) 280 { 281 /* GKM FIXME: honor NO_FLOAT */ 282 fprintf (out_FILE, _("Load=%ld/%ld=%.0f%%, "), ht->ht_fill, ht->ht_size, 283 100.0 * (double) ht->ht_fill / (double) ht->ht_size); 284 fprintf (out_FILE, _("Rehash=%d, "), ht->ht_rehashes); 285 fprintf (out_FILE, _("Collisions=%ld/%ld=%.0f%%"), ht->ht_collisions, ht->ht_lookups, 286 (ht->ht_lookups 287 ? (100.0 * (double) ht->ht_collisions / (double) ht->ht_lookups) 288 : 0)); 289 } 290 291 /* Dump all items into a NULL-terminated vector. Use the 292 user-supplied vector, or malloc one. */ 293 294 void ** 295 hash_dump (struct hash_table *ht, void **vector_0, qsort_cmp_t compare) 296 { 297 void **vector; 298 void **slot; 299 void **end = &ht->ht_vec[ht->ht_size]; 300 301 if (vector_0 == 0) 302 vector_0 = MALLOC (void *, ht->ht_fill + 1); 303 vector = vector_0; 304 305 for (slot = ht->ht_vec; slot < end; slot++) 306 if (!HASH_VACANT (*slot)) 307 *vector++ = *slot; 308 *vector = 0; 309 310 if (compare) 311 qsort (vector_0, ht->ht_fill, sizeof (void *), compare); 312 return vector_0; 313 } 314 315 /* Round a given number up to the nearest power of 2. */ 316 317 static unsigned long 318 round_up_2 (unsigned long n) 319 { 320 n |= (n >> 1); 321 n |= (n >> 2); 322 n |= (n >> 4); 323 n |= (n >> 8); 324 n |= (n >> 16); 325 326 #if !defined(HAVE_LIMITS_H) || ULONG_MAX > 4294967295 327 /* We only need this on systems where unsigned long is >32 bits. */ 328 n |= (n >> 32); 329 #endif 330 331 return n + 1; 332 } 333
