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