gcc/stringpool.c

   1 /* String pool for GCC.
   2    Copyright (C) 2000, 2001, 2002, 2003, 2004 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   struct ht_identifier * *
 205     GTY((length ("%h.nslots"),
 206          nested_ptr (union tree_node, "%h ? GCC_IDENT_TO_HT_IDENT (%h) : NULL",
 207                      "%h ? HT_IDENT_TO_GCC_IDENT (%h) : NULL")))
 208     entries;
 209   unsigned int nslots;
 210   unsigned int nelements;
 211 };
 212
 213 static GTY(()) struct string_pool_data * spd;
 214
 215 /* Copy HP into the corresponding entry in HT2, and then clear
 216    the cpplib parts of HP.  */
 217
 218 static int
 219 ht_copy_and_clear (cpp_reader *r ATTRIBUTE_UNUSED, hashnode hp, const void *ht2_p)
 220 {
 221   cpp_hashnode *h = CPP_HASHNODE (hp);
 222   struct ht *ht2 = (struct ht *) ht2_p;
 223
 224   if (h->type != NT_VOID
 225       && (h->flags & NODE_BUILTIN) == 0)
 226     {
 227       cpp_hashnode *h2 = CPP_HASHNODE (ht_lookup (ht2,
 228                                                   NODE_NAME (h),
 229                                                   NODE_LEN (h),
 230                                                   HT_ALLOC));
 231       h2->type = h->type;
 232       memcpy (&h2->value, &h->value, sizeof (h->value));
 233
 234       h->type = NT_VOID;
 235       memset (&h->value, 0, sizeof (h->value));
 236     }
 237   return 1;
 238 }
 239
 240 /* The hash table as it was before gt_pch_save_stringpool was called.  */
 241
 242 static struct ht *saved_ident_hash;
 243
 244 /* Prepare the stringpool to be written (by clearing all the cpp parts
 245    of each entry) and place the data to be saved in SPD.  Save the
 246    current state in SAVED_IDENT_HASH so that gt_pch_fixup_stringpool
 247    can restore it.  */
 248
 249 void
 250 gt_pch_save_stringpool (void)
 251 {
 252   spd = ggc_alloc (sizeof (*spd));
 253   spd->nslots = ident_hash->nslots;
 254   spd->nelements = ident_hash->nelements;
 255   spd->entries = ggc_alloc (sizeof (spd->entries[0]) * spd->nslots);
 256   memcpy (spd->entries, ident_hash->entries,
 257           spd->nslots * sizeof (spd->entries[0]));
 258
 259   saved_ident_hash = ht_create (14);
 260   saved_ident_hash->alloc_node = alloc_node;
 261   ht_forall (ident_hash, ht_copy_and_clear, saved_ident_hash);
 262 }
 263
 264 /* Return the stringpool to its state before gt_pch_save_stringpool
 265    was called.  */
 266
 267 void
 268 gt_pch_fixup_stringpool (void)
 269 {
 270   ht_forall (saved_ident_hash, ht_copy_and_clear, ident_hash);
 271   ht_destroy (saved_ident_hash);
 272   saved_ident_hash = 0;
 273 }
 274
 275 /* A PCH file has been restored, which loaded SPD; fill the real hash table
 276    from SPD.  */
 277
 278 void
 279 gt_pch_restore_stringpool (void)
 280 {
 281   ht_load (ident_hash, spd->entries, spd->nslots, spd->nelements, false);
 282   spd = NULL;
 283 }
 284
 285 #include "gt-stringpool.h"