1 /* Hash tables. 2 Copyright (C) 2000, 2001, 2003, 2004 Free Software Foundation, Inc. 3 4 This program is free software; you can redistribute it and/or modify it 5 under the terms of the GNU General Public License as published by the 6 Free Software Foundation; either version 2, or (at your option) any 7 later version. 8 9 This program is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 GNU General Public License for more details. 13 14 You should have received a copy of the GNU General Public License 15 along with this program; if not, write to the Free Software 16 Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 17 18 In other words, you are welcome to use, share and improve this program. 19 You are forbidden to forbid anyone else to use, share and improve 20 what you give them. Help stamp out software-hoarding! */ 21 22 #include "config.h" 23 #include "system.h" 24 #include "symtab.h" 25 26 /* The code below is a specialization of Vladimir Makarov's expandable 27 hash tables (see libiberty/hashtab.c). The abstraction penalty was 28 too high to continue using the generic form. This code knows 29 intrinsically how to calculate a hash value, and how to compare an 30 existing entry with a potential new one. Also, the ability to 31 delete members from the table has been removed. */ 32 33 static unsigned int calc_hash (const unsigned char *, size_t); 34 static void ht_expand (hash_table *); 35 static double approx_sqrt (double); 36 37 /* Calculate the hash of the string STR of length LEN. */ 38 39 static unsigned int 40 calc_hash (const unsigned char *str, size_t len) 41 { 42 size_t n = len; 43 unsigned int r = 0; 44 45 while (n--) 46 r = HT_HASHSTEP (r, *str++); 47 48 return HT_HASHFINISH (r, len); 49 } 50 51 /* Initialize an identifier hashtable. */ 52 53 hash_table * 54 ht_create (unsigned int order) 55 { 56 unsigned int nslots = 1 << order; 57 hash_table *table; 58 59 table = XCNEW (hash_table); 60 61 /* Strings need no alignment. */ 62 _obstack_begin (&table->stack, 0, 0, 63 (void *(*) (long)) xmalloc, 64 (void (*) (void *)) free); 65 66 obstack_alignment_mask (&table->stack) = 0; 67 68 table->entries = XCNEWVEC (hashnode, nslots); 69 table->entries_owned = true; 70 table->nslots = nslots; 71 return table; 72 } 73 74 /* Frees all memory associated with a hash table. */ 75 76 void 77 ht_destroy (hash_table *table) 78 { 79 obstack_free (&table->stack, NULL); 80 if (table->entries_owned) 81 free (table->entries); 82 free (table); 83 } 84 85 /* Returns the hash entry for the a STR of length LEN. If that string 86 already exists in the table, returns the existing entry, and, if 87 INSERT is CPP_ALLOCED, frees the last obstack object. If the 88 identifier hasn't been seen before, and INSERT is CPP_NO_INSERT, 89 returns NULL. Otherwise insert and returns a new entry. A new 90 string is alloced if INSERT is CPP_ALLOC, otherwise INSERT is 91 CPP_ALLOCED and the item is assumed to be at the top of the 92 obstack. */ 93 hashnode 94 ht_lookup (hash_table *table, const unsigned char *str, size_t len, 95 enum ht_lookup_option insert) 96 { 97 return ht_lookup_with_hash (table, str, len, calc_hash (str, len), 98 insert); 99 } 100 101 hashnode 102 ht_lookup_with_hash (hash_table *table, const unsigned char *str, 103 size_t len, unsigned int hash, 104 enum ht_lookup_option insert) 105 { 106 unsigned int hash2; 107 unsigned int index; 108 size_t sizemask; 109 hashnode node; 110 111 sizemask = table->nslots - 1; 112 index = hash & sizemask; 113 table->searches++; 114 115 node = table->entries[index]; 116 117 if (node != NULL) 118 { 119 if (node->hash_value == hash 120 && HT_LEN (node) == (unsigned int) len 121 && !memcmp (HT_STR (node), str, len)) 122 { 123 if (insert == HT_ALLOCED) 124 /* The string we search for was placed at the end of the 125 obstack. Release it. */ 126 obstack_free (&table->stack, (void *) str); 127 return node; 128 } 129 130 /* hash2 must be odd, so we're guaranteed to visit every possible 131 location in the table during rehashing. */ 132 hash2 = ((hash * 17) & sizemask) | 1; 133 134 for (;;) 135 { 136 table->collisions++; 137 index = (index + hash2) & sizemask; 138 node = table->entries[index]; 139 if (node == NULL) 140 break; 141 142 if (node->hash_value == hash 143 && HT_LEN (node) == (unsigned int) len 144 && !memcmp (HT_STR (node), str, len)) 145 { 146 if (insert == HT_ALLOCED) 147 /* The string we search for was placed at the end of the 148 obstack. Release it. */ 149 obstack_free (&table->stack, (void *) str); 150 return node; 151 } 152 } 153 } 154 155 if (insert == HT_NO_INSERT) 156 return NULL; 157 158 node = (*table->alloc_node) (table); 159 table->entries[index] = node; 160 161 HT_LEN (node) = (unsigned int) len; 162 node->hash_value = hash; 163 if (insert == HT_ALLOC) 164 HT_STR (node) = (const unsigned char *) obstack_copy0 (&table->stack, 165 str, len); 166 else 167 HT_STR (node) = str; 168 169 if (++table->nelements * 4 >= table->nslots * 3) 170 /* Must expand the string table. */ 171 ht_expand (table); 172 173 return node; 174 } 175 176 /* Double the size of a hash table, re-hashing existing entries. */ 177 178 static void 179 ht_expand (hash_table *table) 180 { 181 hashnode *nentries, *p, *limit; 182 unsigned int size, sizemask; 183 184 size = table->nslots * 2; 185 nentries = XCNEWVEC (hashnode, size); 186 sizemask = size - 1; 187 188 p = table->entries; 189 limit = p + table->nslots; 190 do 191 if (*p) 192 { 193 unsigned int index, hash, hash2; 194 195 hash = (*p)->hash_value; 196 index = hash & sizemask; 197 198 if (nentries[index]) 199 { 200 hash2 = ((hash * 17) & sizemask) | 1; 201 do 202 { 203 index = (index + hash2) & sizemask; 204 } 205 while (nentries[index]); 206 } 207 nentries[index] = *p; 208 } 209 while (++p < limit); 210 211 if (table->entries_owned) 212 free (table->entries); 213 table->entries_owned = true; 214 table->entries = nentries; 215 table->nslots = size; 216 } 217 218 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE, 219 the node, and V. */ 220 void 221 ht_forall (hash_table *table, ht_cb cb, const void *v) 222 { 223 hashnode *p, *limit; 224 225 p = table->entries; 226 limit = p + table->nslots; 227 do 228 if (*p) 229 { 230 if ((*cb) (table->pfile, *p, v) == 0) 231 break; 232 } 233 while (++p < limit); 234 } 235 236 /* Restore the hash table. */ 237 void 238 ht_load (hash_table *ht, hashnode *entries, 239 unsigned int nslots, unsigned int nelements, 240 bool own) 241 { 242 if (ht->entries_owned) 243 free (ht->entries); 244 ht->entries = entries; 245 ht->nslots = nslots; 246 ht->nelements = nelements; 247 ht->entries_owned = own; 248 } 249 250 /* Dump allocation statistics to stderr. */ 251 252 void 253 ht_dump_statistics (hash_table *table) 254 { 255 size_t nelts, nids, overhead, headers; 256 size_t total_bytes, longest; 257 double sum_of_squares, exp_len, exp_len2, exp2_len; 258 hashnode *p, *limit; 259 260 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \ 261 ? (x) \ 262 : ((x) < 1024*1024*10 \ 263 ? (x) / 1024 \ 264 : (x) / (1024*1024)))) 265 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M')) 266 267 total_bytes = longest = sum_of_squares = nids = 0; 268 p = table->entries; 269 limit = p + table->nslots; 270 do 271 if (*p) 272 { 273 size_t n = HT_LEN (*p); 274 275 total_bytes += n; 276 sum_of_squares += (double) n * n; 277 if (n > longest) 278 longest = n; 279 nids++; 280 } 281 while (++p < limit); 282 283 nelts = table->nelements; 284 overhead = obstack_memory_used (&table->stack) - total_bytes; 285 headers = table->nslots * sizeof (hashnode); 286 287 fprintf (stderr, "\nString pool\nentries\t\t%lu\n", 288 (unsigned long) nelts); 289 fprintf (stderr, "identifiers\t%lu (%.2f%%)\n", 290 (unsigned long) nids, nids * 100.0 / nelts); 291 fprintf (stderr, "slots\t\t%lu\n", 292 (unsigned long) table->nslots); 293 fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n", 294 SCALE (total_bytes), LABEL (total_bytes), 295 SCALE (overhead), LABEL (overhead)); 296 fprintf (stderr, "table size\t%lu%c\n", 297 SCALE (headers), LABEL (headers)); 298 299 exp_len = (double)total_bytes / (double)nelts; 300 exp2_len = exp_len * exp_len; 301 exp_len2 = (double) sum_of_squares / (double) nelts; 302 303 fprintf (stderr, "coll/search\t%.4f\n", 304 (double) table->collisions / (double) table->searches); 305 fprintf (stderr, "ins/search\t%.4f\n", 306 (double) nelts / (double) table->searches); 307 fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n", 308 exp_len, approx_sqrt (exp_len2 - exp2_len)); 309 fprintf (stderr, "longest entry\t%lu\n", 310 (unsigned long) longest); 311 #undef SCALE 312 #undef LABEL 313 } 314 315 /* Return the approximate positive square root of a number N. This is for 316 statistical reports, not code generation. */ 317 static double 318 approx_sqrt (double x) 319 { 320 double s, d; 321 322 if (x < 0) 323 abort (); 324 if (x == 0) 325 return 0; 326 327 s = x; 328 do 329 { 330 d = (s * s - x) / (2 * s); 331 s -= d; 332 } 333 while (d > .0001); 334 return s; 335 } 336