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

Subversion Repositories open8_urisc

[/] [open8_urisc/] [trunk/] [gnu/] [binutils/] [gold/] [stringpool.h] - Blame information for rev 41

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

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