Mercurial > hg > CbC > CbC_gcc
annotate libcpp/symtab.c @ 97:4d6300120c29 cbc-gcc-4.6.0
modify condition of tail call in expand_call method
| author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 20 Jan 2012 04:48:59 +0900 |
| parents | 77e2b8dfacca |
| children | 04ced10e8804 |
| rev | line source |
|---|---|
| 0 | 1 /* Hash tables. |
| 2 Copyright (C) 2000, 2001, 2003, 2004, 2008, 2009 | |
| 3 Free Software Foundation, Inc. | |
| 4 | |
| 5 This program is free software; you can redistribute it and/or modify it | |
| 6 under the terms of the GNU General Public License as published by the | |
| 7 Free Software Foundation; either version 3, or (at your option) any | |
| 8 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 | |
| 16 along with this program; see the file COPYING3. If not see | |
| 17 <http://www.gnu.org/licenses/>. | |
| 18 | |
| 19 In other words, you are welcome to use, share and improve this program. | |
| 20 You are forbidden to forbid anyone else to use, share and improve | |
| 21 what you give them. Help stamp out software-hoarding! */ | |
| 22 | |
| 23 #include "config.h" | |
| 24 #include "system.h" | |
| 25 #include "symtab.h" | |
| 26 | |
| 27 /* The code below is a specialization of Vladimir Makarov's expandable | |
| 28 hash tables (see libiberty/hashtab.c). The abstraction penalty was | |
| 29 too high to continue using the generic form. This code knows | |
| 30 intrinsically how to calculate a hash value, and how to compare an | |
| 31 existing entry with a potential new one. */ | |
| 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 /* A deleted entry. */ | |
| 38 #define DELETED ((hashnode) -1) | |
| 39 | |
| 40 /* Calculate the hash of the string STR of length LEN. */ | |
| 41 | |
| 42 static unsigned int | |
| 43 calc_hash (const unsigned char *str, size_t len) | |
| 44 { | |
| 45 size_t n = len; | |
| 46 unsigned int r = 0; | |
| 47 | |
| 48 while (n--) | |
| 49 r = HT_HASHSTEP (r, *str++); | |
| 50 | |
| 51 return HT_HASHFINISH (r, len); | |
| 52 } | |
| 53 | |
| 54 /* Initialize an identifier hashtable. */ | |
| 55 | |
| 56 hash_table * | |
| 57 ht_create (unsigned int order) | |
| 58 { | |
| 59 unsigned int nslots = 1 << order; | |
| 60 hash_table *table; | |
| 61 | |
| 62 table = XCNEW (hash_table); | |
| 63 | |
| 64 /* Strings need no alignment. */ | |
| 65 _obstack_begin (&table->stack, 0, 0, | |
| 66 (void *(*) (long)) xmalloc, | |
| 67 (void (*) (void *)) free); | |
| 68 | |
| 69 obstack_alignment_mask (&table->stack) = 0; | |
| 70 | |
| 71 table->entries = XCNEWVEC (hashnode, nslots); | |
| 72 table->entries_owned = true; | |
| 73 table->nslots = nslots; | |
| 74 return table; | |
| 75 } | |
| 76 | |
| 77 /* Frees all memory associated with a hash table. */ | |
| 78 | |
| 79 void | |
| 80 ht_destroy (hash_table *table) | |
| 81 { | |
| 82 obstack_free (&table->stack, NULL); | |
| 83 if (table->entries_owned) | |
| 84 free (table->entries); | |
| 85 free (table); | |
| 86 } | |
| 87 | |
| 88 /* Returns the hash entry for the a STR of length LEN. If that string | |
| 89 already exists in the table, returns the existing entry. If the | |
| 90 identifier hasn't been seen before, and INSERT is CPP_NO_INSERT, | |
| 91 returns NULL. Otherwise insert and returns a new entry. A new | |
| 92 string is allocated. */ | |
| 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 unsigned int deleted_index = table->nslots; | |
| 109 size_t sizemask; | |
| 110 hashnode node; | |
| 111 | |
| 112 sizemask = table->nslots - 1; | |
| 113 index = hash & sizemask; | |
| 114 table->searches++; | |
| 115 | |
| 116 node = table->entries[index]; | |
| 117 | |
| 118 if (node != NULL) | |
| 119 { | |
| 120 if (node == DELETED) | |
| 121 deleted_index = index; | |
| 122 else if (node->hash_value == hash | |
| 123 && HT_LEN (node) == (unsigned int) len | |
| 124 && !memcmp (HT_STR (node), str, len)) | |
| 125 return node; | |
| 126 | |
| 127 /* hash2 must be odd, so we're guaranteed to visit every possible | |
| 128 location in the table during rehashing. */ | |
| 129 hash2 = ((hash * 17) & sizemask) | 1; | |
| 130 | |
| 131 for (;;) | |
| 132 { | |
| 133 table->collisions++; | |
| 134 index = (index + hash2) & sizemask; | |
| 135 node = table->entries[index]; | |
| 136 if (node == NULL) | |
| 137 break; | |
| 138 | |
| 139 if (node == DELETED) | |
| 140 { | |
| 141 if (deleted_index != table->nslots) | |
| 142 deleted_index = index; | |
| 143 } | |
| 144 else if (node->hash_value == hash | |
| 145 && HT_LEN (node) == (unsigned int) len | |
| 146 && !memcmp (HT_STR (node), str, len)) | |
| 147 return node; | |
| 148 } | |
| 149 } | |
| 150 | |
| 151 if (insert == HT_NO_INSERT) | |
| 152 return NULL; | |
| 153 | |
| 154 /* We prefer to overwrite the first deleted slot we saw. */ | |
| 155 if (deleted_index != table->nslots) | |
| 156 index = deleted_index; | |
| 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 | |
| 164 if (table->alloc_subobject) | |
| 165 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
166 char *chars = (char *) table->alloc_subobject (len + 1); |
| 0 | 167 memcpy (chars, str, len); |
| 168 chars[len] = '\0'; | |
| 169 HT_STR (node) = (const unsigned char *) chars; | |
| 170 } | |
| 171 else | |
| 172 HT_STR (node) = (const unsigned char *) obstack_copy0 (&table->stack, | |
| 173 str, len); | |
| 174 | |
| 175 if (++table->nelements * 4 >= table->nslots * 3) | |
| 176 /* Must expand the string table. */ | |
| 177 ht_expand (table); | |
| 178 | |
| 179 return node; | |
| 180 } | |
| 181 | |
| 182 /* Double the size of a hash table, re-hashing existing entries. */ | |
| 183 | |
| 184 static void | |
| 185 ht_expand (hash_table *table) | |
| 186 { | |
| 187 hashnode *nentries, *p, *limit; | |
| 188 unsigned int size, sizemask; | |
| 189 | |
| 190 size = table->nslots * 2; | |
| 191 nentries = XCNEWVEC (hashnode, size); | |
| 192 sizemask = size - 1; | |
| 193 | |
| 194 p = table->entries; | |
| 195 limit = p + table->nslots; | |
| 196 do | |
| 197 if (*p && *p != DELETED) | |
| 198 { | |
| 199 unsigned int index, hash, hash2; | |
| 200 | |
| 201 hash = (*p)->hash_value; | |
| 202 index = hash & sizemask; | |
| 203 | |
| 204 if (nentries[index]) | |
| 205 { | |
| 206 hash2 = ((hash * 17) & sizemask) | 1; | |
| 207 do | |
| 208 { | |
| 209 index = (index + hash2) & sizemask; | |
| 210 } | |
| 211 while (nentries[index]); | |
| 212 } | |
| 213 nentries[index] = *p; | |
| 214 } | |
| 215 while (++p < limit); | |
| 216 | |
| 217 if (table->entries_owned) | |
| 218 free (table->entries); | |
| 219 table->entries_owned = true; | |
| 220 table->entries = nentries; | |
| 221 table->nslots = size; | |
| 222 } | |
| 223 | |
| 224 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE, | |
| 225 the node, and V. */ | |
| 226 void | |
| 227 ht_forall (hash_table *table, ht_cb cb, const void *v) | |
| 228 { | |
| 229 hashnode *p, *limit; | |
| 230 | |
| 231 p = table->entries; | |
| 232 limit = p + table->nslots; | |
| 233 do | |
| 234 if (*p && *p != DELETED) | |
| 235 { | |
| 236 if ((*cb) (table->pfile, *p, v) == 0) | |
| 237 break; | |
| 238 } | |
| 239 while (++p < limit); | |
| 240 } | |
| 241 | |
| 242 /* Like ht_forall, but a nonzero return from the callback means that | |
| 243 the entry should be removed from the table. */ | |
| 244 void | |
| 245 ht_purge (hash_table *table, ht_cb cb, const void *v) | |
| 246 { | |
| 247 hashnode *p, *limit; | |
| 248 | |
| 249 p = table->entries; | |
| 250 limit = p + table->nslots; | |
| 251 do | |
| 252 if (*p && *p != DELETED) | |
| 253 { | |
| 254 if ((*cb) (table->pfile, *p, v)) | |
| 255 *p = DELETED; | |
| 256 } | |
| 257 while (++p < limit); | |
| 258 } | |
| 259 | |
| 260 /* Restore the hash table. */ | |
| 261 void | |
| 262 ht_load (hash_table *ht, hashnode *entries, | |
| 263 unsigned int nslots, unsigned int nelements, | |
| 264 bool own) | |
| 265 { | |
| 266 if (ht->entries_owned) | |
| 267 free (ht->entries); | |
| 268 ht->entries = entries; | |
| 269 ht->nslots = nslots; | |
| 270 ht->nelements = nelements; | |
| 271 ht->entries_owned = own; | |
| 272 } | |
| 273 | |
| 274 /* Dump allocation statistics to stderr. */ | |
| 275 | |
| 276 void | |
| 277 ht_dump_statistics (hash_table *table) | |
| 278 { | |
| 279 size_t nelts, nids, overhead, headers; | |
| 280 size_t total_bytes, longest, deleted = 0; | |
| 281 double sum_of_squares, exp_len, exp_len2, exp2_len; | |
| 282 hashnode *p, *limit; | |
| 283 | |
| 284 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \ | |
| 285 ? (x) \ | |
| 286 : ((x) < 1024*1024*10 \ | |
| 287 ? (x) / 1024 \ | |
| 288 : (x) / (1024*1024)))) | |
| 289 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M')) | |
| 290 | |
| 291 total_bytes = longest = sum_of_squares = nids = 0; | |
| 292 p = table->entries; | |
| 293 limit = p + table->nslots; | |
| 294 do | |
| 295 if (*p == DELETED) | |
| 296 ++deleted; | |
| 297 else if (*p) | |
| 298 { | |
| 299 size_t n = HT_LEN (*p); | |
| 300 | |
| 301 total_bytes += n; | |
| 302 sum_of_squares += (double) n * n; | |
| 303 if (n > longest) | |
| 304 longest = n; | |
| 305 nids++; | |
| 306 } | |
| 307 while (++p < limit); | |
| 308 | |
| 309 nelts = table->nelements; | |
| 310 overhead = obstack_memory_used (&table->stack) - total_bytes; | |
| 311 headers = table->nslots * sizeof (hashnode); | |
| 312 | |
| 313 fprintf (stderr, "\nString pool\nentries\t\t%lu\n", | |
| 314 (unsigned long) nelts); | |
| 315 fprintf (stderr, "identifiers\t%lu (%.2f%%)\n", | |
| 316 (unsigned long) nids, nids * 100.0 / nelts); | |
| 317 fprintf (stderr, "slots\t\t%lu\n", | |
| 318 (unsigned long) table->nslots); | |
| 319 fprintf (stderr, "deleted\t\t%lu\n", | |
| 320 (unsigned long) deleted); | |
| 321 fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n", | |
| 322 SCALE (total_bytes), LABEL (total_bytes), | |
| 323 SCALE (overhead), LABEL (overhead)); | |
| 324 fprintf (stderr, "table size\t%lu%c\n", | |
| 325 SCALE (headers), LABEL (headers)); | |
| 326 | |
| 327 exp_len = (double)total_bytes / (double)nelts; | |
| 328 exp2_len = exp_len * exp_len; | |
| 329 exp_len2 = (double) sum_of_squares / (double) nelts; | |
| 330 | |
| 331 fprintf (stderr, "coll/search\t%.4f\n", | |
| 332 (double) table->collisions / (double) table->searches); | |
| 333 fprintf (stderr, "ins/search\t%.4f\n", | |
| 334 (double) nelts / (double) table->searches); | |
| 335 fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n", | |
| 336 exp_len, approx_sqrt (exp_len2 - exp2_len)); | |
| 337 fprintf (stderr, "longest entry\t%lu\n", | |
| 338 (unsigned long) longest); | |
| 339 #undef SCALE | |
| 340 #undef LABEL | |
| 341 } | |
| 342 | |
| 343 /* Return the approximate positive square root of a number N. This is for | |
| 344 statistical reports, not code generation. */ | |
| 345 static double | |
| 346 approx_sqrt (double x) | |
| 347 { | |
| 348 double s, d; | |
| 349 | |
| 350 if (x < 0) | |
| 351 abort (); | |
| 352 if (x == 0) | |
| 353 return 0; | |
| 354 | |
| 355 s = x; | |
| 356 do | |
| 357 { | |
| 358 d = (s * s - x) / (2 * s); | |
| 359 s -= d; | |
| 360 } | |
| 361 while (d > .0001); | |
| 362 return s; | |
| 363 } |