Mercurial > hg > CbC > CbC_gcc
annotate libcpp/symtab.c @ 120:f93fa5091070
fix conv1.c
| author | mir3636 |
|---|---|
| date | Thu, 08 Mar 2018 14:53:42 +0900 |
| parents | 04ced10e8804 |
| children | 84e7813d76e9 |
| rev | line source |
|---|---|
| 0 | 1 /* Hash tables. |
| 111 | 2 Copyright (C) 2000-2017 Free Software Foundation, Inc. |
| 0 | 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 3, 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; see the file COPYING3. If not see | |
| 16 <http://www.gnu.org/licenses/>. | |
| 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. */ | |
| 31 | |
| 32 static unsigned int calc_hash (const unsigned char *, size_t); | |
| 111 | 33 static void ht_expand (cpp_hash_table *); |
| 0 | 34 static double approx_sqrt (double); |
| 35 | |
| 36 /* A deleted entry. */ | |
| 37 #define DELETED ((hashnode) -1) | |
| 38 | |
| 39 /* Calculate the hash of the string STR of length LEN. */ | |
| 40 | |
| 41 static unsigned int | |
| 42 calc_hash (const unsigned char *str, size_t len) | |
| 43 { | |
| 44 size_t n = len; | |
| 45 unsigned int r = 0; | |
| 46 | |
| 47 while (n--) | |
| 48 r = HT_HASHSTEP (r, *str++); | |
| 49 | |
| 50 return HT_HASHFINISH (r, len); | |
| 51 } | |
| 52 | |
| 53 /* Initialize an identifier hashtable. */ | |
| 54 | |
| 111 | 55 cpp_hash_table * |
| 0 | 56 ht_create (unsigned int order) |
| 57 { | |
| 58 unsigned int nslots = 1 << order; | |
| 111 | 59 cpp_hash_table *table; |
| 0 | 60 |
| 111 | 61 table = XCNEW (cpp_hash_table); |
| 0 | 62 |
| 63 /* Strings need no alignment. */ | |
| 111 | 64 obstack_specify_allocation (&table->stack, 0, 0, xmalloc, free); |
| 0 | 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 | |
| 111 | 77 ht_destroy (cpp_hash_table *table) |
| 0 | 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. If the | |
| 87 identifier hasn't been seen before, and INSERT is CPP_NO_INSERT, | |
| 88 returns NULL. Otherwise insert and returns a new entry. A new | |
| 89 string is allocated. */ | |
| 90 hashnode | |
| 111 | 91 ht_lookup (cpp_hash_table *table, const unsigned char *str, size_t len, |
| 0 | 92 enum ht_lookup_option insert) |
| 93 { | |
| 94 return ht_lookup_with_hash (table, str, len, calc_hash (str, len), | |
| 95 insert); | |
| 96 } | |
| 97 | |
| 98 hashnode | |
| 111 | 99 ht_lookup_with_hash (cpp_hash_table *table, const unsigned char *str, |
| 0 | 100 size_t len, unsigned int hash, |
| 101 enum ht_lookup_option insert) | |
| 102 { | |
| 103 unsigned int hash2; | |
| 104 unsigned int index; | |
| 105 unsigned int deleted_index = table->nslots; | |
| 106 size_t sizemask; | |
| 107 hashnode node; | |
| 108 | |
| 109 sizemask = table->nslots - 1; | |
| 110 index = hash & sizemask; | |
| 111 table->searches++; | |
| 112 | |
| 113 node = table->entries[index]; | |
| 114 | |
| 115 if (node != NULL) | |
| 116 { | |
| 117 if (node == DELETED) | |
| 118 deleted_index = index; | |
| 119 else if (node->hash_value == hash | |
| 120 && HT_LEN (node) == (unsigned int) len | |
| 121 && !memcmp (HT_STR (node), str, len)) | |
| 122 return node; | |
| 123 | |
| 124 /* hash2 must be odd, so we're guaranteed to visit every possible | |
| 125 location in the table during rehashing. */ | |
| 126 hash2 = ((hash * 17) & sizemask) | 1; | |
| 127 | |
| 128 for (;;) | |
| 129 { | |
| 130 table->collisions++; | |
| 131 index = (index + hash2) & sizemask; | |
| 132 node = table->entries[index]; | |
| 133 if (node == NULL) | |
| 134 break; | |
| 135 | |
| 136 if (node == DELETED) | |
| 137 { | |
| 138 if (deleted_index != table->nslots) | |
| 139 deleted_index = index; | |
| 140 } | |
| 141 else if (node->hash_value == hash | |
| 142 && HT_LEN (node) == (unsigned int) len | |
| 143 && !memcmp (HT_STR (node), str, len)) | |
| 144 return node; | |
| 145 } | |
| 146 } | |
| 147 | |
| 148 if (insert == HT_NO_INSERT) | |
| 149 return NULL; | |
| 150 | |
| 151 /* We prefer to overwrite the first deleted slot we saw. */ | |
| 152 if (deleted_index != table->nslots) | |
| 153 index = deleted_index; | |
| 154 | |
| 155 node = (*table->alloc_node) (table); | |
| 156 table->entries[index] = node; | |
| 157 | |
| 158 HT_LEN (node) = (unsigned int) len; | |
| 159 node->hash_value = hash; | |
| 160 | |
| 161 if (table->alloc_subobject) | |
| 162 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
163 char *chars = (char *) table->alloc_subobject (len + 1); |
| 0 | 164 memcpy (chars, str, len); |
| 165 chars[len] = '\0'; | |
| 166 HT_STR (node) = (const unsigned char *) chars; | |
| 167 } | |
| 168 else | |
| 169 HT_STR (node) = (const unsigned char *) obstack_copy0 (&table->stack, | |
| 170 str, len); | |
| 171 | |
| 172 if (++table->nelements * 4 >= table->nslots * 3) | |
| 173 /* Must expand the string table. */ | |
| 174 ht_expand (table); | |
| 175 | |
| 176 return node; | |
| 177 } | |
| 178 | |
| 179 /* Double the size of a hash table, re-hashing existing entries. */ | |
| 180 | |
| 181 static void | |
| 111 | 182 ht_expand (cpp_hash_table *table) |
| 0 | 183 { |
| 184 hashnode *nentries, *p, *limit; | |
| 185 unsigned int size, sizemask; | |
| 186 | |
| 187 size = table->nslots * 2; | |
| 188 nentries = XCNEWVEC (hashnode, size); | |
| 189 sizemask = size - 1; | |
| 190 | |
| 191 p = table->entries; | |
| 192 limit = p + table->nslots; | |
| 193 do | |
| 194 if (*p && *p != DELETED) | |
| 195 { | |
| 196 unsigned int index, hash, hash2; | |
| 197 | |
| 198 hash = (*p)->hash_value; | |
| 199 index = hash & sizemask; | |
| 200 | |
| 201 if (nentries[index]) | |
| 202 { | |
| 203 hash2 = ((hash * 17) & sizemask) | 1; | |
| 204 do | |
| 205 { | |
| 206 index = (index + hash2) & sizemask; | |
| 207 } | |
| 208 while (nentries[index]); | |
| 209 } | |
| 210 nentries[index] = *p; | |
| 211 } | |
| 212 while (++p < limit); | |
| 213 | |
| 214 if (table->entries_owned) | |
| 215 free (table->entries); | |
| 216 table->entries_owned = true; | |
| 217 table->entries = nentries; | |
| 218 table->nslots = size; | |
| 219 } | |
| 220 | |
| 221 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE, | |
| 222 the node, and V. */ | |
| 223 void | |
| 111 | 224 ht_forall (cpp_hash_table *table, ht_cb cb, const void *v) |
| 0 | 225 { |
| 226 hashnode *p, *limit; | |
| 227 | |
| 228 p = table->entries; | |
| 229 limit = p + table->nslots; | |
| 230 do | |
| 231 if (*p && *p != DELETED) | |
| 232 { | |
| 233 if ((*cb) (table->pfile, *p, v) == 0) | |
| 234 break; | |
| 235 } | |
| 236 while (++p < limit); | |
| 237 } | |
| 238 | |
| 239 /* Like ht_forall, but a nonzero return from the callback means that | |
| 240 the entry should be removed from the table. */ | |
| 241 void | |
| 111 | 242 ht_purge (cpp_hash_table *table, ht_cb cb, const void *v) |
| 0 | 243 { |
| 244 hashnode *p, *limit; | |
| 245 | |
| 246 p = table->entries; | |
| 247 limit = p + table->nslots; | |
| 248 do | |
| 249 if (*p && *p != DELETED) | |
| 250 { | |
| 251 if ((*cb) (table->pfile, *p, v)) | |
| 252 *p = DELETED; | |
| 253 } | |
| 254 while (++p < limit); | |
| 255 } | |
| 256 | |
| 257 /* Restore the hash table. */ | |
| 258 void | |
| 111 | 259 ht_load (cpp_hash_table *ht, hashnode *entries, |
| 0 | 260 unsigned int nslots, unsigned int nelements, |
| 261 bool own) | |
| 262 { | |
| 263 if (ht->entries_owned) | |
| 264 free (ht->entries); | |
| 265 ht->entries = entries; | |
| 266 ht->nslots = nslots; | |
| 267 ht->nelements = nelements; | |
| 268 ht->entries_owned = own; | |
| 269 } | |
| 270 | |
| 271 /* Dump allocation statistics to stderr. */ | |
| 272 | |
| 273 void | |
| 111 | 274 ht_dump_statistics (cpp_hash_table *table) |
| 0 | 275 { |
| 276 size_t nelts, nids, overhead, headers; | |
| 277 size_t total_bytes, longest, deleted = 0; | |
| 278 double sum_of_squares, exp_len, exp_len2, exp2_len; | |
| 279 hashnode *p, *limit; | |
| 280 | |
| 281 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \ | |
| 282 ? (x) \ | |
| 283 : ((x) < 1024*1024*10 \ | |
| 284 ? (x) / 1024 \ | |
| 285 : (x) / (1024*1024)))) | |
| 286 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M')) | |
| 287 | |
| 288 total_bytes = longest = sum_of_squares = nids = 0; | |
| 289 p = table->entries; | |
| 290 limit = p + table->nslots; | |
| 291 do | |
| 292 if (*p == DELETED) | |
| 293 ++deleted; | |
| 294 else if (*p) | |
| 295 { | |
| 296 size_t n = HT_LEN (*p); | |
| 297 | |
| 298 total_bytes += n; | |
| 299 sum_of_squares += (double) n * n; | |
| 300 if (n > longest) | |
| 301 longest = n; | |
| 302 nids++; | |
| 303 } | |
| 304 while (++p < limit); | |
| 305 | |
| 306 nelts = table->nelements; | |
| 307 overhead = obstack_memory_used (&table->stack) - total_bytes; | |
| 308 headers = table->nslots * sizeof (hashnode); | |
| 309 | |
| 310 fprintf (stderr, "\nString pool\nentries\t\t%lu\n", | |
| 311 (unsigned long) nelts); | |
| 312 fprintf (stderr, "identifiers\t%lu (%.2f%%)\n", | |
| 313 (unsigned long) nids, nids * 100.0 / nelts); | |
| 314 fprintf (stderr, "slots\t\t%lu\n", | |
| 315 (unsigned long) table->nslots); | |
| 316 fprintf (stderr, "deleted\t\t%lu\n", | |
| 317 (unsigned long) deleted); | |
| 318 fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n", | |
| 319 SCALE (total_bytes), LABEL (total_bytes), | |
| 320 SCALE (overhead), LABEL (overhead)); | |
| 321 fprintf (stderr, "table size\t%lu%c\n", | |
| 322 SCALE (headers), LABEL (headers)); | |
| 323 | |
| 324 exp_len = (double)total_bytes / (double)nelts; | |
| 325 exp2_len = exp_len * exp_len; | |
| 326 exp_len2 = (double) sum_of_squares / (double) nelts; | |
| 327 | |
| 328 fprintf (stderr, "coll/search\t%.4f\n", | |
| 329 (double) table->collisions / (double) table->searches); | |
| 330 fprintf (stderr, "ins/search\t%.4f\n", | |
| 331 (double) nelts / (double) table->searches); | |
| 332 fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n", | |
| 333 exp_len, approx_sqrt (exp_len2 - exp2_len)); | |
| 334 fprintf (stderr, "longest entry\t%lu\n", | |
| 335 (unsigned long) longest); | |
| 336 #undef SCALE | |
| 337 #undef LABEL | |
| 338 } | |
| 339 | |
| 340 /* Return the approximate positive square root of a number N. This is for | |
| 341 statistical reports, not code generation. */ | |
| 342 static double | |
| 343 approx_sqrt (double x) | |
| 344 { | |
| 345 double s, d; | |
| 346 | |
| 347 if (x < 0) | |
| 348 abort (); | |
| 349 if (x == 0) | |
| 350 return 0; | |
| 351 | |
| 352 s = x; | |
| 353 do | |
| 354 { | |
| 355 d = (s * s - x) / (2 * s); | |
| 356 s -= d; | |
| 357 } | |
| 358 while (d > .0001); | |
| 359 return s; | |
| 360 } |