gcc/stringpool.c

   1 /* String pool for GCC.
   2    Copyright (C) 2000-2014 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 3, 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 COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 /* String text, identifier text and identifier node allocator.
  21    Identifiers are uniquely stored in a hash table.
  22
  23    We use cpplib's hash table implementation.  libiberty's
  24    hashtab.c is not used because it requires 100% average space
  25    overhead per string, which is unacceptable.  Also, this algorithm
  26    is faster.  */
  27
  28 #include "config.h"
  29 #include "system.h"
  30 #include "coretypes.h"
  31 #include "ggc.h"
  32 #include "ggc-internal.h"
  33 #include "tree.h"
  34 #include "symtab.h"
  35 #include "cpplib.h"
  36
  37 /* The "" allocated string.  */
  38 const char empty_string[] = "";
  39
  40 /* Character strings, each containing a single decimal digit.
  41    Written this way to save space.  */
  42 static const char digit_vector[] = {
  43   '0', 0, '1', 0, '2', 0, '3', 0, '4', 0,
  44   '5', 0, '6', 0, '7', 0, '8', 0, '9', 0
  45 };
  46
  47 #define digit_string(d) (digit_vector + ((d) * 2))
  48
  49 struct ht *ident_hash;
  50
  51 static hashnode alloc_node (cpp_hash_table *);
  52 static int mark_ident (struct cpp_reader *, hashnode, const void *);
  53
  54 static void *
  55 stringpool_ggc_alloc (size_t x)
  56 {
  57   return ggc_alloc_atomic (x);
  58 }
  59
  60 /* Initialize the string pool.  */
  61 void
  62 init_stringpool (void)
  63 {
  64   /* Clean up if we're called more than once.
  65      (We can't make this idempotent since identifiers contain state) */
  66   if (ident_hash)
  67     ht_destroy (ident_hash);
  68
  69   /* Create with 16K (2^14) entries.  */
  70   ident_hash = ht_create (14);
  71   ident_hash->alloc_node = alloc_node;
  72   ident_hash->alloc_subobject = stringpool_ggc_alloc;
  73 }
  74
  75 /* Allocate a hash node.  */
  76 static hashnode
  77 alloc_node (cpp_hash_table *table ATTRIBUTE_UNUSED)
  78 {
  79   return GCC_IDENT_TO_HT_IDENT (make_node (IDENTIFIER_NODE));
  80 }
  81
  82 /* Allocate and return a string constant of length LENGTH, containing
  83    CONTENTS.  If LENGTH is -1, CONTENTS is assumed to be a
  84    nul-terminated string, and the length is calculated using strlen.  */
  85
  86 const char *
  87 ggc_alloc_string (const char *contents, int length MEM_STAT_DECL)
  88 {
  89   char *result;
  90
  91   if (length == -1)
  92     length = strlen (contents);
  93
  94   if (length == 0)
  95     return empty_string;
  96   if (length == 1 && ISDIGIT (contents[0]))
  97     return digit_string (contents[0] - '0');
  98
  99   result = (char *) ggc_internal_cleared_alloc (length + 1 PASS_MEM_STAT);
 100   memcpy (result, contents, length);
 101   result[length] = '\0';
 102   return (const char *) result;
 103 }
 104
 105 /* Return an IDENTIFIER_NODE whose name is TEXT (a null-terminated string).
 106    If an identifier with that name has previously been referred to,
 107    the same node is returned this time.  */
 108
 109 #undef get_identifier
 110
 111 tree
 112 get_identifier (const char *text)
 113 {
 114   hashnode ht_node = ht_lookup (ident_hash,
 115                                 (const unsigned char *) text,
 116                                 strlen (text), HT_ALLOC);
 117
 118   /* ht_node can't be NULL here.  */
 119   return HT_IDENT_TO_GCC_IDENT (ht_node);
 120 }
 121
 122 /* Identical to get_identifier, except that the length is assumed
 123    known.  */
 124
 125 tree
 126 get_identifier_with_length (const char *text, size_t length)
 127 {
 128   hashnode ht_node = ht_lookup (ident_hash,
 129                                 (const unsigned char *) text,
 130                                 length, HT_ALLOC);
 131
 132   /* ht_node can't be NULL here.  */
 133   return HT_IDENT_TO_GCC_IDENT (ht_node);
 134 }
 135
 136 /* If an identifier with the name TEXT (a null-terminated string) has
 137    previously been referred to, return that node; otherwise return
 138    NULL_TREE.  */
 139
 140 tree
 141 maybe_get_identifier (const char *text)
 142 {
 143   hashnode ht_node;
 144
 145   ht_node = ht_lookup (ident_hash, (const unsigned char *) text,
 146                        strlen (text), HT_NO_INSERT);
 147   if (ht_node)
 148     return HT_IDENT_TO_GCC_IDENT (ht_node);
 149
 150   return NULL_TREE;
 151 }
 152
 153 /* Report some basic statistics about the string pool.  */
 154
 155 void
 156 stringpool_statistics (void)
 157 {
 158   ht_dump_statistics (ident_hash);
 159 }
 160 \f
 161 /* Mark an identifier for GC.  */
 162
 163 static int
 164 mark_ident (struct cpp_reader *pfile ATTRIBUTE_UNUSED, hashnode h,
 165             const void *v ATTRIBUTE_UNUSED)
 166 {
 167   gt_ggc_m_9tree_node (HT_IDENT_TO_GCC_IDENT (h));
 168   return 1;
 169 }
 170
 171 /* Return true if an identifier should be removed from the table.  */
 172
 173 static int
 174 maybe_delete_ident (struct cpp_reader *pfile ATTRIBUTE_UNUSED, hashnode h,
 175                     const void *v ATTRIBUTE_UNUSED)
 176 {
 177   return !ggc_marked_p (HT_IDENT_TO_GCC_IDENT (h));
 178 }
 179
 180 /* Mark the trees hanging off the identifier node for GGC.  These are
 181    handled specially (not using gengtype) because identifiers are only
 182    roots during one part of compilation.  */
 183
 184 void
 185 ggc_mark_stringpool (void)
 186 {
 187   ht_forall (ident_hash, mark_ident, NULL);
 188 }
 189
 190 /* Purge the identifier hash of identifiers which are no longer
 191    referenced.  */
 192
 193 void
 194 ggc_purge_stringpool (void)
 195 {
 196   ht_purge (ident_hash, maybe_delete_ident, NULL);
 197 }
 198
 199 /* Pointer-walking routine for strings (not very interesting, since
 200    strings don't contain pointers).  */
 201
 202 void
 203 gt_pch_p_S (void *obj ATTRIBUTE_UNUSED, void *x ATTRIBUTE_UNUSED,
 204             gt_pointer_operator op ATTRIBUTE_UNUSED,
 205             void *cookie ATTRIBUTE_UNUSED)
 206 {
 207 }
 208
 209 /* PCH pointer-walking routine for strings.  */
 210
 211 void
 212 gt_pch_n_S (const void *x)
 213 {
 214   gt_pch_note_object (CONST_CAST (void *, x), CONST_CAST (void *, x),
 215                       &gt_pch_p_S);
 216 }
 217
 218
 219 /* User-callable entry point for marking string X.  */
 220
 221 void
 222 gt_pch_nx (const char *& x)
 223 {
 224   gt_pch_n_S (x);
 225 }
 226
 227 void
 228 gt_pch_nx (unsigned char *& x)
 229 {
 230   gt_pch_n_S (x);
 231 }
 232
 233 void
 234 gt_pch_nx (unsigned char& x ATTRIBUTE_UNUSED)
 235 {
 236 }
 237
 238 void
 239 gt_pch_nx (unsigned char *x, gt_pointer_operator op, void *cookie)
 240 {
 241   op (x, cookie);
 242 }
 243 \f
 244 /* Handle saving and restoring the string pool for PCH.  */
 245
 246 /* SPD is saved in the PCH file and holds the information needed
 247    to restore the string pool.  */
 248
 249 struct GTY(()) string_pool_data {
 250   ht_identifier_ptr *
 251     GTY((length ("%h.nslots"),
 252          nested_ptr (union tree_node, "%h ? GCC_IDENT_TO_HT_IDENT (%h) : NULL",
 253                      "%h ? HT_IDENT_TO_GCC_IDENT (%h) : NULL")))
 254     entries;
 255   unsigned int nslots;
 256   unsigned int nelements;
 257 };
 258
 259 static GTY(()) struct string_pool_data * spd;
 260
 261 /* Save the stringpool data in SPD.  */
 262
 263 void
 264 gt_pch_save_stringpool (void)
 265 {
 266   spd = ggc_alloc<string_pool_data> ();
 267   spd->nslots = ident_hash->nslots;
 268   spd->nelements = ident_hash->nelements;
 269   spd->entries = ggc_vec_alloc<ht_identifier_ptr> (spd->nslots);
 270   memcpy (spd->entries, ident_hash->entries,
 271           spd->nslots * sizeof (spd->entries[0]));
 272 }
 273
 274 /* Return the stringpool to its state before gt_pch_save_stringpool
 275    was called.  */
 276
 277 void
 278 gt_pch_fixup_stringpool (void)
 279 {
 280 }
 281
 282 /* A PCH file has been restored, which loaded SPD; fill the real hash table
 283    from SPD.  */
 284
 285 void
 286 gt_pch_restore_stringpool (void)
 287 {
 288   ht_load (ident_hash, spd->entries, spd->nslots, spd->nelements, false);
 289   spd = NULL;
 290 }
 291
 292 #include "gt-stringpool.h"