Index: gcc/cp/pph.c
===================================================================
*** gcc/cp/pph.c	(revision 167557)
--- gcc/cp/pph.c	(working copy)
*************** pth_lexer_to_image (pth_image *image, cp
*** 1775,1782 ****
    VEC_safe_push (char, gc, image->ih_sequence, 'H');
  
    /* The identifiers that may conflict with macros.  */
-   if (flag_pth_debug >= 2)
-     cpp_lt_statistics (reader);
    hunk->identifiers = cpp_lt_capture (reader);
  
    /* Remember the text offset where this hunk started and its length.  */
--- 1775,1780 ----
*************** pth_include_handler (cpp_reader *reader 
*** 2050,2055 ****
--- 2048,2059 ----
  }
  
  
+ /* The initial order of the size of the lexical lookaside table,
+    which will accomodate as many as half of its slots in use.  */
+ 
+ static const unsigned int cpp_lt_order = /* 2 to the power of */ 9;
+ 
+ 
  /* Initialize PTH support.  LEXER is the main lexer object used for
     pre-processing.  */
  
*************** pth_init (cp_lexer *lexer)
*** 2064,2071 ****
  
    gcc_assert (flag_pth);
  
!   table = cpp_lt_exchange (parse_in, cpp_lt_create (/*2 to the power*/15,
! 			   flag_pth_debug));
    gcc_assert (table == NULL);
  
    memset (&pth_stats, 0, sizeof (pth_stats));
--- 2068,2075 ----
  
    gcc_assert (flag_pth);
  
!   table = cpp_lt_exchange (parse_in,
!                            cpp_lt_create (cpp_lt_order, flag_pth_debug));
    gcc_assert (table == NULL);
  
    memset (&pth_stats, 0, sizeof (pth_stats));
Index: libcpp/symtab.c
===================================================================
*** libcpp/symtab.c	(revision 167557)
--- libcpp/symtab.c	(working copy)
*************** approx_sqrt (double x)
*** 365,378 ****
  
  /* Lookaside Identifier Hash Table */
  
  cpp_lookaside *
! cpp_lt_exchange (cpp_reader *pfile, cpp_lookaside *desired)
  {
!   cpp_lookaside *current = pfile->lookaside_table;
!   pfile->lookaside_table = desired;
    return current;
  }
  
  cpp_lookaside *
  cpp_lt_create (unsigned int order, unsigned int debug)
  {
--- 365,406 ----
  
  /* Lookaside Identifier Hash Table */
  
+ /* This table is implemented as an extensible linear open hash table.
+    See http://en.wikipedia.org/wiki/Open_addressing.  */
+ 
+ 
+ /* Exchange the DESIRED lookaside table with the existing table in the
+    READER.  This operation is an information-preserving assignment. */
+ 
  cpp_lookaside *
! cpp_lt_exchange (cpp_reader *reader, cpp_lookaside *desired)
  {
!   cpp_lookaside *current = reader->lookaside_table;
!   reader->lookaside_table = desired;
    return current;
  }
  
+ /* Clear the lookaside TABLE statistics.  */
+ 
+ static void
+ lt_clear_stats (struct cpp_lookaside *table)
+ {
+   table->searches = 0;
+   table->comparisons = 0;
+   table->strcmps = 0;
+   table->collisions = 0;
+   table->misses = 0;
+   table->insertions = 0;
+   table->macrovalue = 0;
+   table->resizes = 0;
+   table->bumps = 0;
+   table->iterations = 0;
+   table->empties = 0;
+ }
+ 
+ /* Create a lookaside table of pow(2,ORDER) entries and set the DEBUG
+    level.  This function is a constructor.  */
+ 
  cpp_lookaside *
  cpp_lt_create (unsigned int order, unsigned int debug)
  {
*************** cpp_lt_create (unsigned int order, unsig
*** 380,385 ****
--- 408,414 ----
    cpp_lookaside *table = XCNEW (cpp_lookaside);
    table->entries = XCNEWVEC (struct lae, slots);
    table->order = order;
+   table->sticky_order = order;
    table->active = 0;
  
    table->max_length = 0;
*************** cpp_lt_create (unsigned int order, unsig
*** 390,416 ****
  		  (void (*) (void *)) free);
    obstack_alignment_mask (table->strings) = 0;
  
-   table->searches = 0;
-   table->comparisons = 0;
-   table->strcmps = 0;
-   table->collisions = 0;
-   table->misses = 0;
-   table->insertions = 0;
-   table->macrovalue = 0;
-   table->resizes = 0;
-   table->bumps = 0;
-   table->iterations = 0;
-   table->empties = 0;
- 
    table->flag_pth_debug = debug;
  
    return table;
  }
  
! void
! cpp_lt_statistics (cpp_reader *pfile)
  {
-   struct cpp_lookaside *table = pfile->lookaside_table;
    fprintf (stderr, "lookaside ");
    fprintf (stderr, "order=%u, ",	table->order);
    fprintf (stderr, "active=%u, ",	table->active);
--- 419,435 ----
  		  (void (*) (void *)) free);
    obstack_alignment_mask (table->strings) = 0;
  
    table->flag_pth_debug = debug;
+   lt_clear_stats (table);
  
    return table;
  }
  
! /* Print the statistics for the lookaside TABLE.  */
! 
! static void
! lt_statistics (struct cpp_lookaside *table)
  {
    fprintf (stderr, "lookaside ");
    fprintf (stderr, "order=%u, ",	table->order);
    fprintf (stderr, "active=%u, ",	table->active);
*************** cpp_lt_statistics (cpp_reader *pfile)
*** 425,446 ****
    fprintf (stderr, "bump=%llu, ",	table->bumps);
    fprintf (stderr, "iterations=%llu, ",	table->iterations);
    fprintf (stderr, "empties=%llu\n",	table->empties);
-   table->searches = 0;
-   table->comparisons = 0;
-   table->strcmps = 0;
-   table->collisions = 0;
-   table->misses = 0;
-   table->insertions = 0;
-   table->macrovalue = 0;
-   table->resizes = 0;
-   table->bumps = 0;
-   table->iterations = 0;
-   table->empties = 0;
  }
  
  void 
  cpp_lt_destroy (cpp_lookaside *table)
  {
    if (table->strings)
      {
        obstack_free (table->strings, NULL);
--- 444,458 ----
    fprintf (stderr, "bump=%llu, ",	table->bumps);
    fprintf (stderr, "iterations=%llu, ",	table->iterations);
    fprintf (stderr, "empties=%llu\n",	table->empties);
  }
  
+ /* Destroy (deallocate) a lookaside TABLE.  This function is a destructor.  */
+ 
  void 
  cpp_lt_destroy (cpp_lookaside *table)
  {
+   if (table->flag_pth_debug >= 2)
+     lt_statistics (table);
    if (table->strings)
      {
        obstack_free (table->strings, NULL);
*************** cpp_lt_destroy (cpp_lookaside *table)
*** 450,475 ****
    free (table);
  }
  
! unsigned int
! cpp_lt_num_entries (cpp_lookaside *table)
! {
!   return table->active;
! }
! 
! unsigned int
! cpp_lt_max_length (cpp_lookaside *table)
! {
!   return table->max_length;
! }
! 
! struct obstack *
! cpp_lt_take_strings (cpp_lookaside *table)
! {
!   struct obstack *strings = table->strings;
!   table->strings = NULL;
!   return strings;
! }
! 
  void
  cpp_lt_forall (cpp_lookaside *table, cpp_lookback grok, void *passthru)
  {
--- 462,476 ----
    free (table);
  }
  
! /* Call the GROK function for all the entries in the lookaside TABLE.
!    The cpp_lt_forall function passes PASSTHRU to each invocation of GROK,
!    in addition to the STR characters and their LEN
!    for each IDENT and MACRO value. */
! /* FIXME: This code is presently unused, but may prove useful later.  */
! #if 0
! typedef void (*cpp_lookback) (void *passthru,
!                               const char *ident_str, unsigned int ident_len,
!                               const char *macro_str, unsigned int macro_len);
  void
  cpp_lt_forall (cpp_lookaside *table, cpp_lookback grok, void *passthru)
  {
*************** cpp_lt_forall (cpp_lookaside *table, cpp
*** 484,494 ****
                entries[index].value, entries[index].length);
      }
  }
  
! /* Query a CPP_NODE for its macro value from PFILE.  */
  
  static const char *
! lt_query_macro (cpp_reader *pfile, cpp_hashnode *cpp_node)
  {
    const char *definition = NULL;
    if (cpp_node->flags & NODE_BUILTIN)
--- 485,496 ----
                entries[index].value, entries[index].length);
      }
  }
+ #endif
  
! /* Query a CPP_NODE for its macro value from READER.  */
  
  static const char *
! lt_query_macro (cpp_reader *reader, cpp_hashnode *cpp_node)
  {
    const char *definition = NULL;
    if (cpp_node->flags & NODE_BUILTIN)
*************** lt_query_macro (cpp_reader *pfile, cpp_h
*** 506,512 ****
            unsigned int front, back, needed;
            const char *value;
  
!           value = (const char *)_cpp_builtin_macro_text (pfile, cpp_node);
            front = strlen (str);
            back = strlen (value);
            needed = front + 1 + back + 1;
--- 508,514 ----
            unsigned int front, back, needed;
            const char *value;
  
!           value = (const char *)_cpp_builtin_macro_text (reader, cpp_node);
            front = strlen (str);
            back = strlen (value);
            needed = front + 1 + back + 1;
*************** lt_query_macro (cpp_reader *pfile, cpp_h
*** 525,533 ****
          }
      }
    else
!     definition = (const char *) cpp_macro_definition (pfile, cpp_node);
  
!   if (pfile->lookaside_table->flag_pth_debug >= 3)
      fprintf (stderr, "PTH: macro %s is %s\n",
                       (const char *)cpp_node->ident.str,
                       definition);
--- 527,535 ----
          }
      }
    else
!     definition = (const char *) cpp_macro_definition (reader, cpp_node);
  
!   if (reader->lookaside_table->flag_pth_debug >= 3)
      fprintf (stderr, "PTH: macro %s is %s\n",
                       (const char *)cpp_node->ident.str,
                       definition);
*************** lt_query_macro (cpp_reader *pfile, cpp_h
*** 536,548 ****
  }
  
  /* Capture the current STRING definition of a macro for the
!    libcpp NODE and store it in the look ASIDE table of the PFILE. */
  
  static unsigned int
  lt_macro_value (const char** string, cpp_lookaside *aside,
!                 cpp_reader *pfile, cpp_hashnode *cpp_node)
  {
!   const char *definition = lt_query_macro (pfile, cpp_node);
    size_t macro_len = strlen (definition);
    *string = (const char *) obstack_copy0 (aside->strings, definition, macro_len);
    if (macro_len > aside->max_length)
--- 538,550 ----
  }
  
  /* Capture the current STRING definition of a macro for the
!    libcpp CPP_NODE and store it in the look ASIDE table of the READER. */
  
  static unsigned int
  lt_macro_value (const char** string, cpp_lookaside *aside,
!                 cpp_reader *reader, cpp_hashnode *cpp_node)
  {
!   const char *definition = lt_query_macro (reader, cpp_node);
    size_t macro_len = strlen (definition);
    *string = (const char *) obstack_copy0 (aside->strings, definition, macro_len);
    if (macro_len > aside->max_length)
*************** lt_macro_value (const char** string, cpp
*** 551,564 ****
    return macro_len;
  }
  
! /* Capture the identifier state in the lookaside table of PFILE
     and then empty the lookaside table.  */
  
  cpp_idents_used
! cpp_lt_capture (cpp_reader *pfile)
  {
    cpp_idents_used used;
!   cpp_lookaside *aside = pfile->lookaside_table;
    unsigned int num_entries = aside->active;
    unsigned int slots = 1 << aside->order;
    unsigned int table_index;
--- 553,566 ----
    return macro_len;
  }
  
! /* Capture the identifier state in the lookaside table of READER
     and then empty the lookaside table.  */
  
  cpp_idents_used
! cpp_lt_capture (cpp_reader *reader)
  {
    cpp_idents_used used;
!   cpp_lookaside *aside = reader->lookaside_table;
    unsigned int num_entries = aside->active;
    unsigned int slots = 1 << aside->order;
    unsigned int table_index;
*************** cpp_lt_capture (cpp_reader *pfile)
*** 567,572 ****
--- 569,575 ----
    used.num_entries = aside->active;
    used.entries = XCNEWVEC (cpp_ident_use, num_entries);
  
+   /* Copy the entry information into used identifiers table.  */
    for (table_index = 0; table_index < slots ; ++table_index)
      {
        struct lae *table_entry = aside->entries + table_index;
*************** cpp_lt_capture (cpp_reader *pfile)
*** 586,617 ****
            cpp_node = CPP_HASHNODE (node);
            if (cpp_node->type == NT_MACRO)
                summary_entry->after_len = lt_macro_value
!                   (&summary_entry->after_str, aside, pfile, cpp_node);
            /* else .after_str and .after_len are still zero initialized.  */
          }
      }
  
-   /* Now empty out the lookaside table. */
-   memset (aside->entries, 0, slots * sizeof (struct lae));
-   aside->active = 0;
- 
    /* Take the strings from the table and give to the summary.  */
    used.strings = aside->strings;
    aside->strings = NULL;
    used.max_length = aside->max_length;
  
-   /* Create a new string table.  */
-   aside->max_length = 0;
-   aside->strings = XCNEW (struct obstack);
-   /* Strings need no alignment.  */
-   _obstack_begin (aside->strings, 0, 0,
- 		  (void *(*) (long)) xmalloc,
- 		  (void (*) (void *)) free);
-   obstack_alignment_mask (aside->strings) = 0;
- 
    aside->iterations += slots;
    ++aside->empties;
  
    return used;
  }
  
--- 589,641 ----
            cpp_node = CPP_HASHNODE (node);
            if (cpp_node->type == NT_MACRO)
                summary_entry->after_len = lt_macro_value
!                   (&summary_entry->after_str, aside, reader, cpp_node);
            /* else .after_str and .after_len are still zero initialized.  */
          }
      }
  
    /* Take the strings from the table and give to the summary.  */
    used.strings = aside->strings;
    aside->strings = NULL;
    used.max_length = aside->max_length;
  
    aside->iterations += slots;
    ++aside->empties;
  
+   /* Do we need to reallocate the table?  */
+   if (aside->sticky_order < aside->order - 1)
+     {
+       /* Allocate a new table.  */
+       reader->lookaside_table = cpp_lt_create (aside->sticky_order,
+                                               aside->flag_pth_debug);
+       cpp_lt_destroy (aside);  /* May also dump statistics.  */
+     }
+   else
+     {
+       /* Reuse the old table.  */
+ 
+       /* Dump out the statistics.  */
+       if (aside->flag_pth_debug >= 2)
+         {
+           lt_statistics (aside);
+           lt_clear_stats (aside);
+         }
+ 
+       /* Empty out the entries.  */
+       memset (aside->entries, 0, slots * sizeof (struct lae));
+       aside->active = 0;
+ 
+       /* Create a new string table.  */
+       aside->max_length = 0;
+       aside->strings = XCNEW (struct obstack);
+       /* Strings need no alignment.  */
+       _obstack_begin (aside->strings, 0, 0,
+ 		      (void *(*) (long)) xmalloc,
+ 		      (void (*) (void *)) free);
+       obstack_alignment_mask (aside->strings) = 0;
+ 
+     }
+ 
    return used;
  }
  
*************** cpp_lt_replay (cpp_reader *reader, cpp_i
*** 797,808 ****
--- 821,844 ----
    free (buffer);
  }
  
+ /* Destroy IDENTIFIERS captured.  */
+ 
+ void
+ cpp_lt_idents_destroy (cpp_idents_used *identifiers)
+ {
+   obstack_free (identifiers->strings, NULL);
+   XDELETEVEC (identifiers);
+ }
+ 
  /* Mappings from hash to index.  */
  #define LT_MASK(order) (~(~0 << (order)))
  #define LT_FIRST(hash, order, mask) (((hash) ^ ((hash) >> (order))) & (mask))
  #define LT_NEXT(index, mask) (((index) + 1) & (mask))
  /* Linear probing.  */
  
+ /* Resize the look ASIDE table from its OLD_ORDER to a NEW_ORDER.
+    The NEW_ORDER must hold twice the number of active elements.  */
+ 
  static void
  lt_resize (cpp_lookaside *aside, unsigned int old_order, unsigned int new_order)
  {
*************** lt_resize (cpp_lookaside *aside, unsigne
*** 838,850 ****
    ++aside->resizes;
  }
  
  cpp_hashnode *
! lt_lookup (cpp_reader *pfile,
             const unsigned char *identifier,
             size_t length,
             unsigned int hash)
  {
!   cpp_lookaside *aside = pfile->lookaside_table;
    /* Compress the hash to an index.
       Assume there is sufficient entropy in the lowest 2*order bits.  */
    unsigned int order = aside->order;
--- 874,890 ----
    ++aside->resizes;
  }
  
+ /* Lookup the IDENTIFER of the given LENGTH and HASH value
+    in the READER's lookaside table.
+    The lookup does not compute a hash.  */
+ 
  cpp_hashnode *
! lt_lookup (cpp_reader *reader,
             const unsigned char *identifier,
             size_t length,
             unsigned int hash)
  {
!   cpp_lookaside *aside = reader->lookaside_table;
    /* Compress the hash to an index.
       Assume there is sufficient entropy in the lowest 2*order bits.  */
    unsigned int order = aside->order;
*************** lt_lookup (cpp_reader *pfile,
*** 880,886 ****
    ++aside->misses;
  
    node = ht_lookup_with_hash
! 	(pfile->hash_table, identifier, length, hash, HT_ALLOC);
    cpp_node = CPP_HASHNODE(node);
  
    /* Do not save macro parameter names; they don't affect verification.  */
--- 920,926 ----
    ++aside->misses;
  
    node = ht_lookup_with_hash
! 	(reader->hash_table, identifier, length, hash, HT_ALLOC);
    cpp_node = CPP_HASHNODE(node);
  
    /* Do not save macro parameter names; they don't affect verification.  */
*************** lt_lookup (cpp_reader *pfile,
*** 899,905 ****
    /* Capture any macro value.  */
    if (cpp_node->type == NT_MACRO)
      entries[index].length = lt_macro_value
!             (&entries[index].value, aside, pfile, cpp_node);
    /* else .value and .length are still zero from initialization.  */
  
    /* Check table load factor.  */
--- 939,945 ----
    /* Capture any macro value.  */
    if (cpp_node->type == NT_MACRO)
      entries[index].length = lt_macro_value
!             (&entries[index].value, aside, reader, cpp_node);
    /* else .value and .length are still zero from initialization.  */
  
    /* Check table load factor.  */
Index: libcpp/include/symtab.h
===================================================================
*** libcpp/include/symtab.h	(revision 167557)
--- libcpp/include/symtab.h	(working copy)
*************** typedef struct GTY(()) cpp_idents_used
*** 126,187 ****
    struct obstack * GTY((skip)) strings;
  } cpp_idents_used;
  
! /* Exchange the reader's current lookaside table with a new table.
     To deactivate the lookaside table, set it to NULL.
     The current table is the return value.
     Clients are responsible for creating and destroying the tables.  */
  cpp_lookaside *
! cpp_lt_exchange (struct cpp_reader *pfile, cpp_lookaside *desired);
  
! /* Create the lookaside table.  */
  cpp_lookaside *
  cpp_lt_create (unsigned int order, unsigned int debug);
  
! /* Frees all memory associated with a lookaside table.  */
  void
  cpp_lt_destroy (cpp_lookaside *table);
  
! /* Captures the current state of the lookaside table,
     together with macro definition state before and after the table,
     and then empties the table.  */
  cpp_idents_used
! cpp_lt_capture (struct cpp_reader *pfile);
  
! /* Verifies that the previously captured identifiers
!    are consistent with the current state of the reader.
!    If not, set the bad_use and cur_def to indicate the first  
     inconsistency.  A null means 'not a macro'.  */
  bool
  cpp_lt_verify (struct cpp_reader *reader, cpp_idents_used* identifiers,
                 cpp_ident_use **bad_use, const char **cur_def);
  
! /* Replay the macro definitions captured by the table of identifiers used
!    into the reader state.  */
  void
  cpp_lt_replay (struct cpp_reader *reader, cpp_idents_used* identifiers);
  
! /* Query the number of entries in the lookaside table.  */
! unsigned int
! cpp_lt_num_entries (cpp_lookaside *table);
! 
! /* Query the string length in the lookaside table.  */
! unsigned int
! cpp_lt_max_length (cpp_lookaside *table);
! 
! /* Take ownership of the obstack holding strings in the lookaside table.  */
! struct obstack *
! cpp_lt_take_strings (cpp_lookaside *table);
! 
! /* Visit all the entries in the lookaside table.  */
! typedef void (*cpp_lookback) (void *passthru,
!                               const char *ident_str, unsigned int ident_len,
!                               const char *macro_str, unsigned int macro_len);
  void
! cpp_lt_forall (cpp_lookaside *table, cpp_lookback grok, void *passthru);
! 
! /* Dump the lookaside table statistics to stderr.  */
! void
! cpp_lt_statistics (struct cpp_reader *pfile);
  
  
  #endif /* LIBCPP_SYMTAB_H */
--- 126,169 ----
    struct obstack * GTY((skip)) strings;
  } cpp_idents_used;
  
! /* Exchange the READER's current lookaside table with a new table.
     To deactivate the lookaside table, set it to NULL.
     The current table is the return value.
     Clients are responsible for creating and destroying the tables.  */
  cpp_lookaside *
! cpp_lt_exchange (struct cpp_reader *reader, cpp_lookaside *desired);
  
! /* Create the lookaside table of pow(2,ORDER) entries
!    and set the DEBUG level.  */
  cpp_lookaside *
  cpp_lt_create (unsigned int order, unsigned int debug);
  
! /* Frees all memory associated with a lookaside TABLE.  */
  void
  cpp_lt_destroy (cpp_lookaside *table);
  
! /* Captures the current state of the READER lookaside table,
     together with macro definition state before and after the table,
     and then empties the table.  */
  cpp_idents_used
! cpp_lt_capture (struct cpp_reader *reader);
  
! /* Verifies that the previously captured IDENTIFIERS
!    are consistent with the current state of the READER.
!    If not, set BAD_USE and CUR_DEF to indicate the first  
     inconsistency.  A null means 'not a macro'.  */
  bool
  cpp_lt_verify (struct cpp_reader *reader, cpp_idents_used* identifiers,
                 cpp_ident_use **bad_use, const char **cur_def);
  
! /* Replay the macro definitions captured by the table of IDENTIFIERS
!    into the READER state.  */
  void
  cpp_lt_replay (struct cpp_reader *reader, cpp_idents_used* identifiers);
  
! /* Destroy IDENTIFIERS captured.  */
  void
! cpp_lt_idents_destroy (cpp_idents_used *identifiers);
  
  
  #endif /* LIBCPP_SYMTAB_H */
Index: libcpp/init.c
===================================================================
*** libcpp/init.c	(revision 167557)
--- libcpp/init.c	(working copy)
*************** cpp_destroy (cpp_reader *pfile)
*** 322,327 ****
--- 322,330 ----
        while (pfile->pushed_macros);
      }
  
+   if (pfile->lookaside_table)
+     cpp_lt_destroy (pfile->lookaside_table);
+ 
    free (pfile);
  }
  
Index: libcpp/internal.h
===================================================================
*** libcpp/internal.h	(revision 167557)
--- libcpp/internal.h	(working copy)
*************** struct lae {
*** 338,343 ****
--- 338,344 ----
  struct cpp_lookaside {
    struct lae *entries;		/* The entry storage.  */
    unsigned int order;		/* 2^order slots in the entries array.  */
+   unsigned int sticky_order;	/* For resizing when capturing the entries.  */
    unsigned int active;		/* Number of active entries.  */
    struct obstack *strings;	/* For macro value storage.  */
    unsigned int max_length;	/* Largest string encountered.  */
