OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [binutils-2.20.1/] [gold/] [stringpool.h] - Blame information for rev 438

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 205 julius
// stringpool.h -- a string pool for gold    -*- C++ -*-
2
 
3
// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
4
// Written by Ian Lance Taylor <iant@google.com>.
5
 
6
// This file is part of gold.
7
 
8
// This program is free software; you can redistribute it and/or modify
9
// it under the terms of the GNU General Public License as published by
10
// the Free Software Foundation; either version 3 of the License, or
11
// (at your option) any later version.
12
 
13
// This program is distributed in the hope that it will be useful,
14
// but WITHOUT ANY WARRANTY; without even the implied warranty of
15
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16
// GNU General Public License for more details.
17
 
18
// You should have received a copy of the GNU General Public License
19
// along with this program; if not, write to the Free Software
20
// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
21
// MA 02110-1301, USA.
22
 
23
#include <string>
24
#include <list>
25
#include <vector>
26
 
27
#ifndef GOLD_STRINGPOOL_H
28
#define GOLD_STRINGPOOL_H
29
 
30
namespace gold
31
{
32
 
33
class Output_file;
34
 
35
// A Stringpool is a pool of unique strings.  It provides the
36
// following features:
37
 
38
// Every string in the pool is unique.  Thus, if you have two strings
39
// in the Stringpool, you can compare them for equality by using
40
// pointer comparison rather than string comparison.
41
 
42
// There is a key associated with every string in the pool.  If you
43
// add strings to the Stringpool in the same order, then the key for
44
// each string will always be the same for any run of the linker.
45
// This is not true of the string pointers themselves, as they may
46
// change due to address space randomization.  Some parts of the
47
// linker (e.g., the symbol table) use the key value instead of the
48
// string pointer so that repeated runs of the linker will generate
49
// precisely the same output.
50
 
51
// When you add a string to a Stringpool, Stringpool will optionally
52
// make a copy of it.  Thus there is no requirement to keep a copy
53
// elsewhere.
54
 
55
// A Stringpool can be turned into a string table, a sequential series
56
// of null terminated strings.  The first string may optionally be a
57
// single zero byte, as required for SHT_STRTAB sections.  This
58
// conversion is only permitted after all strings have been added to
59
// the Stringpool.  After doing this conversion, you can ask for the
60
// offset of any string (or any key) in the stringpool in the string
61
// table, and you can write the resulting string table to an output
62
// file.
63
 
64
// When a Stringpool is turned into a string table, then as an
65
// optimization it will reuse string suffixes to avoid duplicating
66
// strings.  That is, given the strings "abc" and "bc", only the
67
// string "abc" will be stored, and "bc" will be represented by an
68
// offset into the middle of the string "abc".
69
 
70
 
71
// A simple chunked vector class--this is a subset of std::vector
72
// which stores memory in chunks.  We don't provide iterators, because
73
// we don't need them.
74
 
75
template<typename Element>
76
class Chunked_vector
77
{
78
 public:
79
  Chunked_vector()
80
    : chunks_()
81
  { }
82
 
83
  // Clear the elements.
84
  void
85
  clear()
86
  { this->chunks_.clear(); }
87
 
88
  // Reserve elements.
89
  void
90
  reserve(unsigned int n)
91
  {
92
    n += chunk_size - 1;
93
    while (n >= chunk_size)
94
      {
95
        this->chunks_.push_back(Element_vector());
96
        this->chunks_.back().reserve(chunk_size);
97
        n -= chunk_size;
98
      }
99
  }
100
 
101
  // Get the number of elements.
102
  size_t
103
  size() const
104
  {
105
    if (this->chunks_.empty())
106
      return 0;
107
    else
108
      return ((this->chunks_.size() - 1) * chunk_size
109
              + this->chunks_.back().size());
110
  }
111
 
112
  // Push a new element on the back of the vector.
113
  void
114
  push_back(const Element& element)
115
  {
116
    if (this->chunks_.empty() || this->chunks_.back().size() == chunk_size)
117
      {
118
        this->chunks_.push_back(Element_vector());
119
        this->chunks_.back().reserve(chunk_size);
120
      }
121
    this->chunks_.back().push_back(element);
122
  }
123
 
124
  // Return a reference to an entry in the vector.
125
  Element&
126
  operator[](size_t i)
127
  { return this->chunks_[i / chunk_size][i % chunk_size]; }
128
 
129
  const Element&
130
  operator[](size_t i) const
131
  { return this->chunks_[i / chunk_size][i % chunk_size]; }
132
 
133
 private:
134
  static const unsigned int chunk_size = 8192;
135
 
136
  typedef std::vector<Element> Element_vector;
137
  typedef std::vector<Element_vector> Chunk_vector;
138
 
139
  Chunk_vector chunks_;
140
};
141
 
142
 
143
// Stringpools are implemented in terms of Stringpool_template, which
144
// is generalized on the type of character used for the strings.  Most
145
// uses will want the Stringpool type which uses char.  Other cases
146
// are used for merging wide string constants.
147
 
148
template<typename Stringpool_char>
149
class Stringpool_template
150
{
151
 public:
152
  // The type of a key into the stringpool.  As described above, a key
153
  // value will always be the same during any run of the linker.  Zero
154
  // is never a valid key value.
155
  typedef size_t Key;
156
 
157
  // Create a Stringpool.
158
  Stringpool_template();
159
 
160
  ~Stringpool_template();
161
 
162
  // Clear all the data from the stringpool.
163
  void
164
  clear();
165
 
166
  // Hint to the stringpool class that you intend to insert n additional
167
  // elements.  The stringpool class can use this info however it likes;
168
  // in practice it will resize its internal hashtables to make room.
169
  void
170
  reserve(unsigned int n);
171
 
172
  // Indicate that we should not reserve offset 0 to hold the empty
173
  // string when converting the stringpool to a string table.  This
174
  // should not be called for a proper ELF SHT_STRTAB section.
175
  void
176
  set_no_zero_null()
177
  { this->zero_null_ = false; }
178
 
179
  // Indicate that this string pool should be optimized, even if not
180
  // running with -O2.
181
  void
182
  set_optimize()
183
  { this->optimize_ = true; }
184
 
185
  // Add the string S to the pool.  This returns a canonical permanent
186
  // pointer to the string in the pool.  If COPY is true, the string
187
  // is copied into permanent storage.  If PKEY is not NULL, this sets
188
  // *PKEY to the key for the string.
189
  const Stringpool_char*
190
  add(const Stringpool_char* s, bool copy, Key* pkey);
191
 
192
  // Add string S of length LEN characters to the pool.  If COPY is
193
  // true, S need not be null terminated.
194
  const Stringpool_char*
195
  add_with_length(const Stringpool_char* s, size_t len, bool copy, Key* pkey);
196
 
197
  // If the string S is present in the pool, return the canonical
198
  // string pointer.  Otherwise, return NULL.  If PKEY is not NULL,
199
  // set *PKEY to the key.
200
  const Stringpool_char*
201
  find(const Stringpool_char* s, Key* pkey) const;
202
 
203
  // Turn the stringpool into a string table: determine the offsets of
204
  // all the strings.  After this is called, no more strings may be
205
  // added to the stringpool.
206
  void
207
  set_string_offsets();
208
 
209
  // Get the offset of the string S in the string table.  This returns
210
  // the offset in bytes, not in units of Stringpool_char.  This may
211
  // only be called after set_string_offsets has been called.
212
  section_offset_type
213
  get_offset(const Stringpool_char* s) const;
214
 
215
  // Get the offset of the string S in the string table.
216
  section_offset_type
217
  get_offset(const std::basic_string<Stringpool_char>& s) const
218
  { return this->get_offset_with_length(s.c_str(), s.size()); }
219
 
220
  // Get the offset of string S, with length LENGTH characters, in the
221
  // string table.
222
  section_offset_type
223
  get_offset_with_length(const Stringpool_char* s, size_t length) const;
224
 
225
  // Get the offset of the string with key K.
226
  section_offset_type
227
  get_offset_from_key(Key k) const
228
  {
229
    gold_assert(k <= this->key_to_offset_.size());
230
    return this->key_to_offset_[k - 1];
231
  }
232
 
233
  // Get the size of the string table.  This returns the number of
234
  // bytes, not in units of Stringpool_char.
235
  section_size_type
236
  get_strtab_size() const
237
  {
238
    gold_assert(this->strtab_size_ != 0);
239
    return this->strtab_size_;
240
  }
241
 
242
  // Write the string table into the output file at the specified
243
  // offset.
244
  void
245
  write(Output_file*, off_t offset);
246
 
247
  // Write the string table into the specified buffer, of the
248
  // specified size.  buffer_size should be at least
249
  // get_strtab_size().
250
  void
251
  write_to_buffer(unsigned char* buffer, section_size_type buffer_size);
252
 
253
  // Dump statistical information to stderr.
254
  void
255
  print_stats(const char*) const;
256
 
257
 private:
258
  Stringpool_template(const Stringpool_template&);
259
  Stringpool_template& operator=(const Stringpool_template&);
260
 
261
  // Return the length of a string in units of Stringpool_char.
262
  static size_t
263
  string_length(const Stringpool_char*);
264
 
265
  // Return whether two strings are equal.
266
  static bool
267
  string_equal(const Stringpool_char*, const Stringpool_char*);
268
 
269
  // Compute a hash code for a string.  LENGTH is the length of the
270
  // string in characters.
271
  static size_t
272
  string_hash(const Stringpool_char*, size_t length);
273
 
274
  // We store the actual data in a list of these buffers.
275
  struct Stringdata
276
  {
277
    // Length of data in buffer.
278
    size_t len;
279
    // Allocated size of buffer.
280
    size_t alc;
281
    // Buffer.
282
    char data[1];
283
  };
284
 
285
  // Copy a string into the buffers, returning a canonical string.
286
  const Stringpool_char*
287
  add_string(const Stringpool_char*, size_t);
288
 
289
  // Return whether s1 is a suffix of s2.
290
  static bool
291
  is_suffix(const Stringpool_char* s1, size_t len1,
292
            const Stringpool_char* s2, size_t len2);
293
 
294
  // The hash table key includes the string, the length of the string,
295
  // and the hash code for the string.  We put the hash code
296
  // explicitly into the key so that we can do a find()/insert()
297
  // sequence without having to recompute the hash.  Computing the
298
  // hash code is a significant user of CPU time in the linker.
299
  struct Hashkey
300
  {
301
    const Stringpool_char* string;
302
    // Length is in characters, not bytes.
303
    size_t length;
304
    size_t hash_code;
305
 
306
    // This goes in an STL container, so we need a default
307
    // constructor.
308
    Hashkey()
309
      : string(NULL), length(0), hash_code(0)
310
    { }
311
 
312
    // Note that these constructors are relatively expensive, because
313
    // they compute the hash code.
314
    explicit Hashkey(const Stringpool_char* s)
315
      : string(s), length(string_length(s)), hash_code(string_hash(s, length))
316
    { }
317
 
318
    Hashkey(const Stringpool_char* s, size_t len)
319
      : string(s), length(len), hash_code(string_hash(s, len))
320
    { }
321
  };
322
 
323
  // Hash function.  This is trivial, since we have already computed
324
  // the hash.
325
  struct Stringpool_hash
326
  {
327
    size_t
328
    operator()(const Hashkey& hk) const
329
    { return hk.hash_code; }
330
  };
331
 
332
  // Equality comparison function for hash table.
333
  struct Stringpool_eq
334
  {
335
    bool
336
    operator()(const Hashkey&, const Hashkey&) const;
337
  };
338
 
339
  // The hash table is a map from strings to Keys.
340
 
341
  typedef Key Hashval;
342
 
343
  typedef Unordered_map<Hashkey, Hashval, Stringpool_hash,
344
                        Stringpool_eq> String_set_type;
345
 
346
  // Comparison routine used when sorting into a string table.
347
 
348
  typedef typename String_set_type::iterator Stringpool_sort_info;
349
 
350
  struct Stringpool_sort_comparison
351
  {
352
    bool
353
    operator()(const Stringpool_sort_info&, const Stringpool_sort_info&) const;
354
  };
355
 
356
  // Keys map to offsets via a Chunked_vector.  We only use the
357
  // offsets if we turn this into an string table section.
358
  typedef Chunked_vector<section_offset_type> Key_to_offset;
359
 
360
  // List of Stringdata structures.
361
  typedef std::list<Stringdata*> Stringdata_list;
362
 
363
  // Mapping from const char* to namepool entry.
364
  String_set_type string_set_;
365
  // Mapping from Key to string table offset.
366
  Key_to_offset key_to_offset_;
367
  // List of buffers.
368
  Stringdata_list strings_;
369
  // Size of string table.
370
  section_size_type strtab_size_;
371
  // Whether to reserve offset 0 to hold the null string.
372
  bool zero_null_;
373
  // Whether to optimize the string table.
374
  bool optimize_;
375
};
376
 
377
// The most common type of Stringpool.
378
typedef Stringpool_template<char> Stringpool;
379
 
380
} // End namespace gold.
381
 
382
#endif // !defined(GOLD_STRINGPOOL_H)

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.