gcc/stringpool.c

   1 /* String pool for GCC.
   2    Copyright (C) 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 /* String text, identifier text and identifier node allocator.  Strings
  22    allocated by ggc_alloc_string are stored in an obstack which is
  23    never shrunk.  Identifiers are uniquely stored in a hash table.
  24
  25    We use cpplib's hash table implementation.  libiberty's
  26    hashtab.c is not used because it requires 100% average space
  27    overhead per string, which is unacceptable.  Also, this algorithm
  28    is faster.  */
  29
  30 #include "config.h"
  31 #include "system.h"
  32 #include "coretypes.h"
  33 #include "tm.h"
  34 #include "ggc.h"
  35 #include "tree.h"
  36 #include "symtab.h"
  37 #include "cpplib.h"
  38
  39 /* The "" allocated string.  */
  40 const char empty_string[] = "";
  41
  42 /* Character strings, each containing a single decimal digit.
  43    Written this way to save space.  */
  44 const char digit_vector[] = {
  45   '0', 0, '1', 0, '2', 0, '3', 0, '4', 0,
  46   '5', 0, '6', 0, '7', 0, '8', 0, '9', 0
  47 };
  48
  49 struct ht *ident_hash;
  50 static struct obstack string_stack;
  51
  52 static hashnode alloc_node (hash_table *);
  53 static int mark_ident (struct cpp_reader *, hashnode, const void *);
  54 static int ht_copy_and_clear (struct cpp_reader *, hashnode, const void *);
  55
  56 /* Initialize the string pool.  */
  57 void
  58 init_stringpool (void)
  59 {
  60   /* Create with 16K (2^14) entries.  */
  61   ident_hash = ht_create (14);
  62   ident_hash->alloc_node = alloc_node;
  63   gcc_obstack_init (&string_stack);
  64 }
  65
  66 /* Allocate a hash node.  */
  67 static hashnode
  68 alloc_node (hash_table *table ATTRIBUTE_UNUSED)
  69 {
  70   return GCC_IDENT_TO_HT_IDENT (make_node (IDENTIFIER_NODE));
  71 }
  72
  73 /* Allocate and return a string constant of length LENGTH, containing
  74    CONTENTS.  If LENGTH is -1, CONTENTS is assumed to be a
  75    nul-terminated string, and the length is calculated using strlen.
  76    If the same string constant has been allocated before, that copy is
  77    returned this time too.  */
  78
  79 const char *
  80 ggc_alloc_string (const char *contents, int length)
  81 {
  82   if (length == -1)
  83     length = strlen (contents);
  84
  85   if (length == 0)
  86     return empty_string;
  87   if (length == 1 && ISDIGIT (contents[0]))
  88     return digit_string (contents[0] - '0');
  89
  90   obstack_grow0 (&string_stack, contents, length);
  91   return obstack_finish (&string_stack);
  92 }
  93
  94 /* Return an IDENTIFIER_NODE whose name is TEXT (a null-terminated string).
  95    If an identifier with that name has previously been referred to,
  96    the same node is returned this time.  */
  97
  98 #undef get_identifier
  99
 100 tree
 101 get_identifier (const char *text)
 102 {
 103   hashnode ht_node = ht_lookup (ident_hash,
 104                                 (const unsigned char *) text,
 105                                 strlen (text), HT_ALLOC);
 106
 107   /* ht_node can't be NULL here.  */
 108   return HT_IDENT_TO_GCC_IDENT (ht_node);
 109 }
 110
 111 /* Identical to get_identifier, except that the length is assumed
 112    known.  */
 113
 114 tree
 115 get_identifier_with_length (const char *text, size_t length)
 116 {
 117   hashnode ht_node = ht_lookup (ident_hash,
 118                                 (const unsigned char *) text,
 119                                 length, HT_ALLOC);
 120
 121   /* ht_node can't be NULL here.  */
 122   return HT_IDENT_TO_GCC_IDENT (ht_node);
 123 }
 124
 125 /* If an identifier with the name TEXT (a null-terminated string) has
 126    previously been referred to, return that node; otherwise return
 127    NULL_TREE.  */
 128
 129 tree
 130 maybe_get_identifier (const char *text)
 131 {
 132   hashnode ht_node;
 133
 134   ht_node = ht_lookup (ident_hash, (const unsigned char *) text,
 135                        strlen (text), HT_NO_INSERT);
 136   if (ht_node)
 137     return HT_IDENT_TO_GCC_IDENT (ht_node);
 138
 139   return NULL_TREE;
 140 }
 141
 142 /* Report some basic statistics about the string pool.  */
 143
 144 void
 145 stringpool_statistics (void)
 146 {
 147   ht_dump_statistics (ident_hash);
 148 }
 149 \f
 150 /* Mark an identifier for GC.  */
 151
 152 static int
 153 mark_ident (struct cpp_reader *pfile ATTRIBUTE_UNUSED, hashnode h,
 154             const void *v ATTRIBUTE_UNUSED)
 155 {
 156   gt_ggc_m_9tree_node (HT_IDENT_TO_GCC_IDENT (h));
 157   return 1;
 158 }
 159
 160 /* Mark the trees hanging off the identifier node for GGC.  These are
 161    handled specially (not using gengtype) because of the special
 162    treatment for strings.  */
 163
 164 void
 165 ggc_mark_stringpool (void)
 166 {
 167   ht_forall (ident_hash, mark_ident, NULL);
 168 }
 169
 170 /* Strings are _not_ GCed, but this routine exists so that a separate
 171    roots table isn't needed for the few global variables that refer
 172    to strings.  */
 173
 174 void
 175 gt_ggc_m_S (void *x ATTRIBUTE_UNUSED)
 176 {
 177 }
 178
 179 /* Pointer-walking routine for strings (not very interesting, since
 180    strings don't contain pointers).  */
 181
 182 void
 183 gt_pch_p_S (void *obj ATTRIBUTE_UNUSED, void *x ATTRIBUTE_UNUSED,
 184             gt_pointer_operator op ATTRIBUTE_UNUSED,
 185             void *cookie ATTRIBUTE_UNUSED)
 186 {
 187 }
 188
 189 /* PCH pointer-walking routine for strings.  */
 190
 191 void
 192 gt_pch_n_S (const void *x)
 193 {
 194   gt_pch_note_object ((void *)x, (void *)x, &gt_pch_p_S);
 195 }
 196 \f
 197 /* Handle saving and restoring the string pool for PCH.  */
 198
 199 /* SPD is saved in the PCH file and holds the information needed
 200    to restore the string pool.  */
 201
 202 struct string_pool_data GTY(())
 203 {
 204   tree * GTY((length ("%h.nslots"))) entries;
 205   unsigned int nslots;
 206   unsigned int nelements;
 207 };
 208
 209 static GTY(()) struct string_pool_data * spd;
 210
 211 /* Copy HP into the corresponding entry in HT2, and then clear
 212    the cpplib parts of HP.  */
 213
 214 static int
 215 ht_copy_and_clear (cpp_reader *r ATTRIBUTE_UNUSED, hashnode hp, const void *ht2_p)
 216 {
 217   cpp_hashnode *h = CPP_HASHNODE (hp);
 218   struct ht *ht2 = (struct ht *) ht2_p;
 219
 220   if (h->type != NT_VOID
 221       && (h->flags & NODE_BUILTIN) == 0)
 222     {
 223       cpp_hashnode *h2 = CPP_HASHNODE (ht_lookup (ht2,
 224                                                   NODE_NAME (h),
 225                                                   NODE_LEN (h),
 226                                                   HT_ALLOC));
 227       h2->type = h->type;
 228       memcpy (&h2->value, &h->value, sizeof (h->value));
 229
 230       h->type = NT_VOID;
 231       memset (&h->value, 0, sizeof (h->value));
 232     }
 233   return 1;
 234 }
 235
 236 /* The hash table as it was before gt_pch_save_stringpool was called.  */
 237
 238 static struct ht *saved_ident_hash;
 239
 240 /* The hash table contains pointers to the cpp_hashnode inside the
 241    lang_identifier.  The PCH machinery can't handle pointers that refer
 242    to the inside of an object, so to save the hash table for PCH the
 243    pointers are adjusted and stored in the variable SPD.  */
 244
 245 void
 246 gt_pch_save_stringpool (void)
 247 {
 248   unsigned int i;
 249
 250   spd = ggc_alloc (sizeof (*spd));
 251   spd->nslots = ident_hash->nslots;
 252   spd->nelements = ident_hash->nelements;
 253   spd->entries = ggc_alloc (sizeof (tree *) * spd->nslots);
 254   for (i = 0; i < spd->nslots; i++)
 255     if (ident_hash->entries[i] != NULL)
 256       spd->entries[i] = HT_IDENT_TO_GCC_IDENT (ident_hash->entries[i]);
 257     else
 258       spd->entries[i] = NULL;
 259
 260   saved_ident_hash = ht_create (14);
 261   saved_ident_hash->alloc_node = alloc_node;
 262   ht_forall (ident_hash, ht_copy_and_clear, saved_ident_hash);
 263 }
 264
 265 /* Return the stringpool to its state before gt_pch_save_stringpool
 266    was called.  */
 267
 268 void
 269 gt_pch_fixup_stringpool (void)
 270 {
 271   ht_forall (saved_ident_hash, ht_copy_and_clear, ident_hash);
 272   ht_destroy (saved_ident_hash);
 273   saved_ident_hash = 0;
 274 }
 275
 276 /* A PCH file has been restored, which loaded SPD; fill the real hash table
 277    with adjusted pointers from SPD.  */
 278
 279 void
 280 gt_pch_restore_stringpool (void)
 281 {
 282   unsigned int i;
 283
 284   ident_hash->nslots = spd->nslots;
 285   ident_hash->nelements = spd->nelements;
 286   ident_hash->entries = xrealloc (ident_hash->entries,
 287                                   sizeof (hashnode) * spd->nslots);
 288   for (i = 0; i < spd->nslots; i++)
 289     if (spd->entries[i] != NULL)
 290       ident_hash->entries[i] = GCC_IDENT_TO_HT_IDENT (spd->entries[i]);
 291     else
 292       ident_hash->entries[i] = NULL;
 293
 294   spd = NULL;
 295 }
 296
 297 #include "gt-stringpool.h"