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