libcpp/symtab.c

   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 #include "internal.h"
  27
  28 /* The code below is a specialization of Vladimir Makarov's expandable
  29    hash tables (see libiberty/hashtab.c).  The abstraction penalty was
  30    too high to continue using the generic form.  This code knows
  31    intrinsically how to calculate a hash value, and how to compare an
  32    existing entry with a potential new one.  */
  33
  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 unsigned int
  43 ht_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, ht_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     {
 166       char *chars = (char *) table->alloc_subobject (len + 1);
 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 }
 364
 365
 366 /* Lookaside Identifier Hash Table */
 367
 368 /* This table is implemented as an extensible linear open hash table.
 369    See http://en.wikipedia.org/wiki/Open_addressing.  */
 370
 371
 372 /* Exchange the DESIRED lookaside table with the existing table in the
 373    READER.  This operation is an information-preserving assignment. */
 374
 375 cpp_lookaside *
 376 cpp_lt_exchange (cpp_reader *reader, cpp_lookaside *desired)
 377 {
 378   cpp_lookaside *current = reader->lookaside_table;
 379   reader->lookaside_table = desired;
 380   return current;
 381 }
 382
 383 /* Clear the lookaside TABLE statistics.  */
 384
 385 static void
 386 lt_clear_stats (struct cpp_lookaside *table)
 387 {
 388   table->searches = 0;
 389   table->comparisons = 0;
 390   table->strcmps = 0;
 391   table->collisions = 0;
 392   table->misses = 0;
 393   table->insertions = 0;
 394   table->macrovalue = 0;
 395   table->resizes = 0;
 396   table->bumps = 0;
 397   table->iterations = 0;
 398   table->empties = 0;
 399 }
 400
 401 /* Create a lookaside table of pow(2,ORDER) entries and set the DEBUG
 402    level.  This function is a constructor.  */
 403
 404 cpp_lookaside *
 405 cpp_lt_create (unsigned int order, unsigned int debug)
 406 {
 407   unsigned int slots = 1 << order;
 408   cpp_lookaside *table = XCNEW (cpp_lookaside);
 409   table->entries = XCNEWVEC (struct lae, slots);
 410   table->order = order;
 411   table->sticky_order = order;
 412   table->active = 0;
 413
 414   table->max_ident_len = 0;
 415   table->max_value_len = 0;
 416   table->strings = XCNEW (struct obstack);
 417   /* Strings need no alignment.  */
 418   _obstack_begin (table->strings, 0, 0,
 419                   (void *(*) (long)) xmalloc,
 420                   (void (*) (void *)) free);
 421   obstack_alignment_mask (table->strings) = 0;
 422
 423   table->pth_debug_level = debug;
 424   lt_clear_stats (table);
 425
 426   return table;
 427 }
 428
 429 /* Print the statistics for the lookaside TABLE.  */
 430
 431 static void
 432 lt_statistics (struct cpp_lookaside *table)
 433 {
 434   fprintf (stderr, "lookaside ");
 435   fprintf (stderr, "order=%u, ",        table->order);
 436   fprintf (stderr, "active=%u, ",       table->active);
 437   fprintf (stderr, "search=%llu, ",     table->searches);
 438   fprintf (stderr, "compare=%llu, ",    table->comparisons);
 439   fprintf (stderr, "strcmp=%llu, ",     table->strcmps);
 440   fprintf (stderr, "collide=%llu, ",    table->collisions);
 441   fprintf (stderr, "miss=%llu, ",       table->misses);
 442   fprintf (stderr, "insert=%llu, ",     table->insertions);
 443   fprintf (stderr, "macro=%llu, ",      table->macrovalue);
 444   fprintf (stderr, "resize=%llu, ",     table->resizes);
 445   fprintf (stderr, "bump=%llu, ",       table->bumps);
 446   fprintf (stderr, "iterations=%llu, ", table->iterations);
 447   fprintf (stderr, "empties=%llu\n",    table->empties);
 448 }
 449
 450 /* Destroy (deallocate) a lookaside TABLE.  This function is a destructor.  */
 451
 452 void
 453 cpp_lt_destroy (cpp_lookaside *table)
 454 {
 455   if (table->pth_debug_level >= 2)
 456     lt_statistics (table);
 457   if (table->strings)
 458     {
 459       obstack_free (table->strings, NULL);
 460       free (table->strings);
 461     }
 462   free (table->entries);
 463   free (table);
 464 }
 465
 466 /* Call the GROK function for all the entries in the lookaside TABLE.
 467    The cpp_lt_forall function passes PASSTHRU to each invocation of GROK,
 468    in addition to the STR characters and their LEN
 469    for each IDENT and MACRO value. */
 470 /* FIXME pph: This code is presently unused, but may prove useful later.  */
 471 #if 0
 472 typedef void (*cpp_lookback) (void *passthru,
 473                               const char *ident_str, unsigned int ident_len,
 474                               const char *macro_str, unsigned int macro_len);
 475 void
 476 cpp_lt_forall (cpp_lookaside *table, cpp_lookback grok, void *passthru)
 477 {
 478   unsigned int slots = 1 << table->order;
 479   struct lae *entries = table->entries;
 480   unsigned int index;
 481   for (index = 0; index < slots ; ++index)
 482     {
 483       hashnode node = entries[index].node;
 484       if (node)
 485         grok (passthru, (const char *)node->str, node->len,
 486               entries[index].value, entries[index].length);
 487     }
 488 }
 489 #endif
 490
 491 /* Query a CPP_NODE for its macro value from READER.  */
 492
 493 static const char *
 494 lt_query_macro (cpp_reader *reader, cpp_hashnode *cpp_node)
 495 {
 496   const char *definition = NULL;
 497   if (cpp_node->flags & NODE_BUILTIN)
 498     {
 499       const char *str = (const char *)cpp_node->ident.str;
 500       if (   strcmp(str, "__DATE__") == 0
 501           || strcmp(str, "__TIME__") == 0
 502           || strcmp(str, "__FILE__") == 0
 503           || strcmp(str, "__LINE__") == 0)
 504         definition = str;
 505       else
 506         {
 507           static char *string = 0;
 508           static unsigned int space = 0;
 509           unsigned int back, needed;
 510           const char *value;
 511
 512           value = (const char *)_cpp_builtin_macro_text (reader, cpp_node);
 513           back = strlen (value);
 514           needed = 1 + back + 1;
 515           if (space < needed)
 516             {
 517               if (string != NULL)
 518                 free (string);
 519               string = XCNEWVEC (char, needed);
 520               space = needed;
 521             }
 522           string[0] = ' ';
 523           strcpy (string + 1, value);
 524           definition = string;
 525         }
 526     }
 527   else
 528     {
 529       char c;
 530       definition = (const char *) cpp_macro_definition (reader, cpp_node);
 531       /* Skip over the macro name within the definition.  */
 532       c = *definition;
 533       while (   ('0' <= c && c <= '9')
 534              || ('A' <= c && c <= 'Z')
 535              || ('a' <= c && c <= 'z')
 536              ||             (c == '_'))
 537         {
 538           c = *++definition;
 539         }
 540     }
 541
 542   if (reader->lookaside_table->pth_debug_level >= 3)
 543     fprintf (stderr, "PTH: macro %s is %s\n",
 544                      (const char *)cpp_node->ident.str,
 545                      definition);
 546
 547   return definition;
 548 }
 549
 550 /* Capture the current STRING definition of a macro for the
 551    libcpp CPP_NODE and store it in the look ASIDE table of the READER. */
 552
 553 static unsigned int
 554 lt_macro_value (const char** string, cpp_lookaside *aside,
 555                 cpp_reader *reader, cpp_hashnode *cpp_node)
 556 {
 557   const char *definition = lt_query_macro (reader, cpp_node);
 558   size_t macro_len = strlen (definition);
 559   *string = (const char *) obstack_copy0 (aside->strings, definition, macro_len);
 560   if (macro_len > aside->max_value_len)
 561     aside->max_value_len = macro_len;
 562   ++aside->macrovalue;
 563   return macro_len;
 564 }
 565
 566 /* Capture the identifier state in the lookaside table of READER
 567    and then empty the lookaside table.  */
 568
 569 cpp_idents_used
 570 cpp_lt_capture (cpp_reader *reader)
 571 {
 572   cpp_idents_used used;
 573   cpp_lookaside *aside = reader->lookaside_table;
 574   unsigned int num_entries = aside->active;
 575   unsigned int slots = 1 << aside->order;
 576   unsigned int table_index;
 577   unsigned int summary_index = 0;
 578
 579   used.num_entries = aside->active;
 580   used.entries = XCNEWVEC (cpp_ident_use, num_entries);
 581
 582   /* Copy the entry information into used identifiers table.  */
 583   for (table_index = 0; table_index < slots ; ++table_index)
 584     {
 585       struct lae *table_entry = aside->entries + table_index;
 586       hashnode node = table_entry->node;
 587       if (node)
 588         {
 589           cpp_ident_use *summary_entry = used.entries + summary_index++;
 590           cpp_hashnode *cpp_node = CPP_HASHNODE (node);
 591
 592           summary_entry->used_by_directive = cpp_node->used_by_directive;
 593           summary_entry->expanded_to_text = cpp_node->expanded_to_text;
 594           summary_entry->ident_len = node->len;
 595           summary_entry->ident_str = (const char *)node->str;
 596           summary_entry->before_len = table_entry->length;
 597           summary_entry->before_str = table_entry->value;
 598
 599           /* Capture any macro value.  */
 600           if (cpp_node->type == NT_MACRO)
 601               summary_entry->after_len = lt_macro_value
 602                   (&summary_entry->after_str, aside, reader, cpp_node);
 603           /* else .after_str and .after_len are still zero initialized.  */
 604         }
 605     }
 606
 607   /* Take the strings from the table and give to the summary.  */
 608   used.strings = aside->strings;
 609   aside->strings = NULL;
 610   used.max_ident_len = aside->max_ident_len;
 611   used.max_value_len = aside->max_value_len;
 612
 613   aside->iterations += slots;
 614   ++aside->empties;
 615
 616   /* Do we need to reallocate the table?  */
 617   if (aside->sticky_order < aside->order - 1)
 618     {
 619       /* Allocate a new table.  */
 620       reader->lookaside_table = cpp_lt_create (aside->sticky_order,
 621                                               aside->pth_debug_level);
 622       cpp_lt_destroy (aside);  /* May also dump statistics.  */
 623     }
 624   else
 625     {
 626       /* Reuse the old table.  */
 627
 628       /* Dump out the statistics.  */
 629       if (aside->pth_debug_level >= 2)
 630         {
 631           lt_statistics (aside);
 632           lt_clear_stats (aside);
 633         }
 634
 635       /* Empty out the entries.  */
 636       memset (aside->entries, 0, slots * sizeof (struct lae));
 637       aside->active = 0;
 638
 639       /* Create a new string table.  */
 640       aside->max_ident_len = 0;
 641       aside->max_value_len = 0;
 642       aside->strings = XCNEW (struct obstack);
 643       /* Strings need no alignment.  */
 644       _obstack_begin (aside->strings, 0, 0,
 645                       (void *(*) (long)) xmalloc,
 646                       (void (*) (void *)) free);
 647       obstack_alignment_mask (aside->strings) = 0;
 648
 649     }
 650
 651   return used;
 652 }
 653
 654 /* Verify that the INDENTIFIERS have before states that consistent
 655    with the current identifier definitions in the READER.
 656    If not, set the BAD_USE and CUR_DEF to indicate the first
 657    inconsistency.  A null means 'not a macro'.  */
 658
 659 bool
 660 cpp_lt_verify_1 (cpp_reader *reader, cpp_idents_used* identifiers,
 661                  cpp_ident_use **bad_use, const char **cur_def,
 662                  int permit_postdef)
 663 {
 664   unsigned int i;
 665   unsigned int num_entries = identifiers->num_entries;
 666   cpp_ident_use *entries = identifiers->entries;
 667
 668   *bad_use = NULL;
 669   *cur_def = NULL;
 670
 671   for (i = 0; i < num_entries; ++i)
 672     {
 673       cpp_hashnode *cpp_node;
 674       cpp_ident_use *entry = entries + i;
 675       const char *ident_str = entry->ident_str;
 676       unsigned int ident_len = entry->ident_len;
 677       const char *before_str = entry->before_str;
 678       unsigned int before_len = entry->before_len;
 679       cpp_node = cpp_peek_sym (reader, (const unsigned char *)ident_str,
 680                                ident_len);
 681       if (cpp_node == NULL)
 682         {
 683           /* The symbol used to exist, but it doesn't now.  */
 684           if (before_str != NULL)
 685             {
 686               *bad_use = entry;
 687               *cur_def = NULL;
 688               goto fail;
 689             }
 690         }
 691       else if (before_len == -1U)
 692         {
 693           /* It was not saved as a macro.  */
 694           if (cpp_node->type == NT_MACRO)
 695             {
 696               /* But it is a macro now!  */
 697               const char *definition;
 698               definition = (const char*) lt_query_macro (reader, cpp_node);
 699               if (permit_postdef)
 700                 {
 701                 /* Check to see if the current value is the after value.  */
 702                 unsigned int after_len = entry->after_len;
 703                 /* strlen is required to avoid the prefix problem.  */
 704                 if (definition == NULL
 705                     || after_len != strlen (definition)
 706                     || memcmp (definition, entry->after_str, after_len) != 0)
 707                   {
 708                     /* They do not have the same value.  */
 709                     *bad_use = entry;
 710                     *cur_def = definition;
 711                     goto fail;
 712                   }
 713                 }
 714               else
 715                 {
 716                   *bad_use = entry;
 717                   *cur_def = definition;
 718                   goto fail;
 719                 }
 720             }
 721           /* Otherwise, both agree it is not a macro.  */
 722         }
 723       else
 724         {
 725           /* It was saved as a macro.  */
 726           const char *definition;
 727
 728           if (cpp_node->type != NT_MACRO)
 729             {
 730               /* But it is not a macro now!  */
 731               *bad_use = entry;
 732               *cur_def = NULL;
 733               goto fail;
 734             }
 735           /* Otherwise, both agree it is a macro.  */
 736           definition = lt_query_macro (reader, cpp_node);
 737           /* strlen is required to avoid the prefix problem.  */
 738           if (definition == NULL
 739               || before_len != strlen (definition)
 740               || memcmp (definition, before_str, before_len) != 0)
 741             {
 742               /* They do not have the same value.  */
 743               *bad_use = entry;
 744               *cur_def = definition;
 745               goto fail;
 746             }
 747         }
 748     }
 749 /* pass: */
 750   *bad_use = NULL;
 751   *cur_def = NULL;
 752   return true;
 753
 754 fail:
 755   return false;
 756 }
 757
 758 bool
 759 cpp_lt_verify (cpp_reader *reader, cpp_idents_used* identifiers,
 760                cpp_ident_use **bad_use, const char **cur_def)
 761 {
 762   return cpp_lt_verify_1 (reader, identifiers, bad_use, cur_def, false);
 763 }
 764
 765 /* Produce the macro definition syntax NEEDED by cpp_define from
 766    the syntax GIVEN by cpp_macro_definition.  */
 767
 768 static void
 769 cpp_lt_define_syntax (char *needed, const char *ident, const char *given)
 770 {
 771   char c;
 772
 773   /* Copy over macro identifier.  */
 774   c = *ident++;
 775   while (c != '\0')
 776     {
 777       *needed++ = c;
 778       c = *ident++;
 779     }
 780
 781   /* Copy over macro definition.  */
 782   c = *given++;
 783   if (c == '(')
 784     {
 785       /* Copy over parameter list.  */
 786       while (c != ')')
 787         {
 788           *needed++ = c;
 789           c = *given++;
 790         }
 791
 792       /* Copy over trailing parenthesis.  */
 793       *needed++ = c;
 794       c = *given++;
 795     }
 796
 797   /* Replace definition space by assignment.  */
 798   /* (c == ' ') */
 799   *needed++ = '=';
 800
 801   /* Copy over macro value.  */
 802   c = *given++;
 803   while (c != '\0')
 804     {
 805       *needed++ = c;
 806       c = *given++;
 807     }
 808
 809   *needed++ = '\0';
 810 }
 811
 812 /* Replay the macro definitions captured by the table of IDENTIFIERS
 813    into the READER state.  */
 814
 815 void
 816 cpp_lt_replay (cpp_reader *reader, cpp_idents_used* identifiers)
 817 {
 818   unsigned int i;
 819   unsigned int num_entries = identifiers->num_entries;
 820   cpp_ident_use *entries = identifiers->entries;
 821   char *buffer = XCNEWVEC (char, identifiers->max_ident_len
 822                                  + identifiers->max_value_len + 1);
 823
 824   /* Prevent the lexer from invalidating the tokens we've read so far.  */
 825   reader->keep_tokens++;
 826
 827   for (i = 0; i < num_entries; ++i)
 828     {
 829       cpp_ident_use *entry = entries + i;
 830       const char *ident_str = entry->ident_str;
 831       const char *before_str = entry->before_str;
 832       const char *after_str = entry->after_str;
 833       if (before_str == NULL)
 834         {
 835           if (after_str != NULL)
 836             {
 837               cpp_lt_define_syntax (buffer, ident_str, after_str);
 838               cpp_define (reader, buffer);
 839             }
 840           /* else consistently not macros */
 841         }
 842       else
 843         {
 844           if (after_str == NULL)
 845             {
 846               cpp_undef (reader, ident_str);
 847             }
 848           else if (strcmp (before_str, after_str) != 0)
 849             {
 850               cpp_undef (reader, ident_str);
 851               cpp_lt_define_syntax (buffer, ident_str, after_str);
 852               cpp_define (reader, buffer);
 853             }
 854           /* else macro with the same definition */
 855         }
 856     }
 857
 858   reader->keep_tokens--;
 859
 860   free (buffer);
 861 }
 862
 863 /* Destroy IDENTIFIERS captured.  */
 864
 865 void
 866 cpp_lt_idents_destroy (cpp_idents_used *identifiers)
 867 {
 868   obstack_free (identifiers->strings, NULL);
 869   XDELETEVEC (identifiers->entries);
 870 }
 871
 872 /* Mappings from hash to index.  */
 873 #define LT_MASK(order) (~(~0 << (order)))
 874 #define LT_FIRST(hash, order, mask) (((hash) ^ ((hash) >> (order))) & (mask))
 875 #define LT_NEXT(index, mask) (((index) + 1) & (mask))
 876 /* Linear probing.  */
 877
 878 /* Resize the look ASIDE table from its OLD_ORDER to a NEW_ORDER.
 879    The NEW_ORDER must hold twice the number of active elements.  */
 880
 881 static void
 882 lt_resize (cpp_lookaside *aside, unsigned int old_order, unsigned int new_order)
 883 {
 884   unsigned int old_index;
 885   unsigned int old_slots = 1 << old_order;
 886   unsigned int new_slots = 1 << new_order;
 887   unsigned int new_mask = LT_MASK (new_order);
 888   struct lae *old_entries = aside->entries;
 889   struct lae *new_entries = XCNEWVEC (struct lae, new_slots);
 890   for ( old_index = 0; old_index < old_slots; ++old_index )
 891     {
 892       hashnode node = old_entries[old_index].node;
 893       if (node)
 894         {
 895           unsigned int hash = old_entries[old_index].hash;
 896           unsigned int new_index = LT_FIRST (hash, new_order, new_mask);
 897           hashnode probe = new_entries[new_index].node;
 898           while (probe)
 899             {
 900               new_index = LT_NEXT (new_index, new_mask);
 901               probe = new_entries[new_index].node;
 902               ++aside->bumps;
 903             }
 904           new_entries[new_index].node = node;
 905           new_entries[new_index].hash = hash;
 906           new_entries[new_index].length = old_entries[old_index].length;
 907           new_entries[new_index].value = old_entries[old_index].value;
 908         }
 909     }
 910   free (old_entries);
 911   aside->entries = new_entries;
 912   aside->order = new_order;
 913   ++aside->resizes;
 914 }
 915
 916 /* Lookup the IDENTIFER of the given LENGTH and HASH value
 917    in the READER's lookaside table.
 918    The lookup does not compute a hash.  */
 919
 920 cpp_hashnode *
 921 lt_lookup (cpp_reader *reader,
 922            const unsigned char *identifier,
 923            size_t length,
 924            unsigned int hash)
 925 {
 926   cpp_lookaside *aside = reader->lookaside_table;
 927   /* Compress the hash to an index.
 928      Assume there is sufficient entropy in the lowest 2*order bits.  */
 929   unsigned int order = aside->order;
 930   unsigned int mask = LT_MASK (order);
 931   unsigned int index = LT_FIRST (hash, order, mask);
 932   cpp_hashnode *cpp_node;
 933
 934   /* Search the lookaside table.  */
 935   struct lae *entries = aside->entries;
 936   hashnode node = entries[index].node;
 937   ++aside->searches;
 938
 939   /* Hashes have no sentinel value, so an entry is empty iff there is
 940      a null node value. */
 941   while (node)
 942     {
 943       if (entries[index].hash == hash)
 944         {
 945           ++aside->comparisons;
 946           if (node->len == length)
 947             {
 948               ++aside->strcmps;
 949               if (memcmp (node->str, identifier, length) == 0)
 950                 return CPP_HASHNODE (node);
 951             }
 952         }
 953
 954       ++aside->collisions;
 955       index = LT_NEXT (index, mask);
 956       node = entries[index].node;
 957     }
 958
 959   ++aside->misses;
 960
 961   node = ht_lookup_with_hash
 962         (reader->hash_table, identifier, length, hash, HT_ALLOC);
 963   cpp_node = CPP_HASHNODE(node);
 964
 965   /* Do not save macro parameter names; they don't affect verification.  */
 966   if (cpp_node->flags & NODE_MACRO_ARG)
 967     return cpp_node;
 968
 969   ++aside->insertions;
 970
 971   /* Fill out new entry.  */
 972   ++aside->active;
 973   entries[index].node = node;
 974   entries[index].hash = hash;
 975   if (length > aside->max_ident_len)
 976     aside->max_ident_len = length;
 977
 978   /* Capture any macro value.  */
 979   if (cpp_node->type == NT_MACRO)
 980     entries[index].length = lt_macro_value
 981         (&entries[index].value, aside, reader, cpp_node);
 982   /* else .value and .length are still zero from initialization.  */
 983
 984   /* Check table load factor.  */
 985   if (aside->active >= (unsigned)(1 << (order - 1)))
 986       /* Table is at least half full; double it.  */
 987       lt_resize (aside, order, order + 1);
 988
 989   return cpp_node;
 990 }