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.cc] - Blame information for rev 205

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 205 julius
// stringpool.cc -- a string pool for gold
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 "gold.h"
24
 
25
#include <cstring>
26
#include <algorithm>
27
#include <vector>
28
 
29
#include "output.h"
30
#include "parameters.h"
31
#include "stringpool.h"
32
 
33
namespace gold
34
{
35
 
36
template<typename Stringpool_char>
37
Stringpool_template<Stringpool_char>::Stringpool_template()
38
  : string_set_(), key_to_offset_(), strings_(), strtab_size_(0),
39
    zero_null_(true), optimize_(false)
40
{
41
  if (parameters->options_valid() && parameters->options().optimize() >= 2)
42
    this->optimize_ = true;
43
}
44
 
45
template<typename Stringpool_char>
46
void
47
Stringpool_template<Stringpool_char>::clear()
48
{
49
  for (typename std::list<Stringdata*>::iterator p = this->strings_.begin();
50
       p != this->strings_.end();
51
       ++p)
52
    delete[] reinterpret_cast<char*>(*p);
53
  this->strings_.clear();
54
  this->key_to_offset_.clear();
55
  this->string_set_.clear();
56
}
57
 
58
template<typename Stringpool_char>
59
Stringpool_template<Stringpool_char>::~Stringpool_template()
60
{
61
  this->clear();
62
}
63
 
64
// Resize the internal hashtable with the expectation we'll get n new
65
// elements.  Note that the hashtable constructor takes a "number of
66
// buckets you'd like," rather than "number of elements you'd like,"
67
// but that's the best we can do.
68
 
69
template<typename Stringpool_char>
70
void
71
Stringpool_template<Stringpool_char>::reserve(unsigned int n)
72
{
73
  this->key_to_offset_.reserve(n);
74
 
75
#if defined(HAVE_TR1_UNORDERED_MAP)
76
  // rehash() implementation is broken in gcc 4.0.3's stl
77
  //this->string_set_.rehash(this->string_set_.size() + n);
78
  //return;
79
#elif defined(HAVE_EXT_HASH_MAP)
80
  this->string_set_.resize(this->string_set_.size() + n);
81
  return;
82
#endif
83
 
84
  // This is the generic "reserve" code, if no #ifdef above triggers.
85
  String_set_type new_string_set(this->string_set_.size() + n);
86
  new_string_set.insert(this->string_set_.begin(), this->string_set_.end());
87
  this->string_set_.swap(new_string_set);
88
}
89
 
90
// Return the length of a string of arbitrary character type.
91
 
92
template<typename Stringpool_char>
93
size_t
94
Stringpool_template<Stringpool_char>::string_length(const Stringpool_char* p)
95
{
96
  size_t len = 0;
97
  for (; *p != 0; ++p)
98
    ++len;
99
  return len;
100
}
101
 
102
// Specialize string_length for char.  Maybe we could just use
103
// std::char_traits<>::length?
104
 
105
template<>
106
inline size_t
107
Stringpool_template<char>::string_length(const char* p)
108
{
109
  return strlen(p);
110
}
111
 
112
// Compare two strings of arbitrary character type for equality.
113
 
114
template<typename Stringpool_char>
115
bool
116
Stringpool_template<Stringpool_char>::string_equal(const Stringpool_char* s1,
117
                                                   const Stringpool_char* s2)
118
{
119
  while (*s1 != 0)
120
    if (*s1++ != *s2++)
121
      return false;
122
  return *s2 == 0;
123
}
124
 
125
// Specialize string_equal for char.
126
 
127
template<>
128
inline bool
129
Stringpool_template<char>::string_equal(const char* s1, const char* s2)
130
{
131
  return strcmp(s1, s2) == 0;
132
}
133
 
134
// Equality comparison function for the hash table.
135
 
136
template<typename Stringpool_char>
137
inline bool
138
Stringpool_template<Stringpool_char>::Stringpool_eq::operator()(
139
    const Hashkey& h1,
140
    const Hashkey& h2) const
141
{
142
  return (h1.hash_code == h2.hash_code
143
          && h1.length == h2.length
144
          && (h1.string == h2.string
145
              || memcmp(h1.string, h2.string,
146
                        h1.length * sizeof(Stringpool_char)) == 0));
147
}
148
 
149
// Hash function.  The length is in characters, not bytes.
150
 
151
template<typename Stringpool_char>
152
size_t
153
Stringpool_template<Stringpool_char>::string_hash(const Stringpool_char* s,
154
                                                  size_t length)
155
{
156
  // This is the hash function used by the dynamic linker for
157
  // DT_GNU_HASH entries.  I compared this to a Fowler/Noll/Vo hash
158
  // for a C++ program with 385,775 global symbols.  This hash
159
  // function was very slightly worse.  However, it is much faster to
160
  // compute.  Overall wall clock time was a win.
161
  const unsigned char* p = reinterpret_cast<const unsigned char*>(s);
162
  size_t h = 5381;
163
  for (size_t i = 0; i < length * sizeof(Stringpool_char); ++i)
164
    h = h * 33 + *p++;
165
  return h;
166
}
167
 
168
// Add the string S to the list of canonical strings.  Return a
169
// pointer to the canonical string.  If PKEY is not NULL, set *PKEY to
170
// the key.  LENGTH is the length of S in characters.  Note that S may
171
// not be NUL terminated.
172
 
173
template<typename Stringpool_char>
174
const Stringpool_char*
175
Stringpool_template<Stringpool_char>::add_string(const Stringpool_char* s,
176
                                                 size_t len)
177
{
178
  // We are in trouble if we've already computed the string offsets.
179
  gold_assert(this->strtab_size_ == 0);
180
 
181
  // The size we allocate for a new Stringdata.
182
  const size_t buffer_size = 1000;
183
  // The amount we multiply the Stringdata index when calculating the
184
  // key.
185
  const size_t key_mult = 1024;
186
  gold_assert(key_mult >= buffer_size);
187
 
188
  // Convert len to the number of bytes we need to allocate, including
189
  // the null character.
190
  len = (len + 1) * sizeof(Stringpool_char);
191
 
192
  size_t alc;
193
  bool front = true;
194
  if (len > buffer_size)
195
    {
196
      alc = sizeof(Stringdata) + len;
197
      front = false;
198
    }
199
  else if (this->strings_.empty())
200
    alc = sizeof(Stringdata) + buffer_size;
201
  else
202
    {
203
      Stringdata *psd = this->strings_.front();
204
      if (len > psd->alc - psd->len)
205
        alc = sizeof(Stringdata) + buffer_size;
206
      else
207
        {
208
          char* ret = psd->data + psd->len;
209
          memcpy(ret, s, len - sizeof(Stringpool_char));
210
          memset(ret + len - sizeof(Stringpool_char), 0,
211
                 sizeof(Stringpool_char));
212
 
213
          psd->len += len;
214
 
215
          return reinterpret_cast<const Stringpool_char*>(ret);
216
        }
217
    }
218
 
219
  Stringdata *psd = reinterpret_cast<Stringdata*>(new char[alc]);
220
  psd->alc = alc - sizeof(Stringdata);
221
  memcpy(psd->data, s, len - sizeof(Stringpool_char));
222
  memset(psd->data + len - sizeof(Stringpool_char), 0,
223
         sizeof(Stringpool_char));
224
  psd->len = len;
225
 
226
  if (front)
227
    this->strings_.push_front(psd);
228
  else
229
    this->strings_.push_back(psd);
230
 
231
  return reinterpret_cast<const Stringpool_char*>(psd->data);
232
}
233
 
234
// Add a string to a string pool.
235
 
236
template<typename Stringpool_char>
237
const Stringpool_char*
238
Stringpool_template<Stringpool_char>::add(const Stringpool_char* s, bool copy,
239
                                          Key* pkey)
240
{
241
  return this->add_with_length(s, string_length(s), copy, pkey);
242
}
243
 
244
template<typename Stringpool_char>
245
const Stringpool_char*
246
Stringpool_template<Stringpool_char>::add_with_length(const Stringpool_char* s,
247
                                                      size_t length,
248
                                                      bool copy,
249
                                                      Key* pkey)
250
{
251
  typedef std::pair<typename String_set_type::iterator, bool> Insert_type;
252
 
253
  // We add 1 so that 0 is always invalid.
254
  const Key k = this->key_to_offset_.size() + 1;
255
 
256
  if (!copy)
257
    {
258
      // When we don't need to copy the string, we can call insert
259
      // directly.
260
 
261
      std::pair<Hashkey, Hashval> element(Hashkey(s, length), k);
262
 
263
      Insert_type ins = this->string_set_.insert(element);
264
 
265
      typename String_set_type::const_iterator p = ins.first;
266
 
267
      if (ins.second)
268
        {
269
          // We just added the string.  The key value has now been
270
          // used.
271
          this->key_to_offset_.push_back(0);
272
        }
273
      else
274
        {
275
          gold_assert(k != p->second);
276
        }
277
 
278
      if (pkey != NULL)
279
        *pkey = p->second;
280
      return p->first.string;
281
    }
282
 
283
  // When we have to copy the string, we look it up twice in the hash
284
  // table.  The problem is that we can't insert S before we
285
  // canonicalize it by copying it into the canonical list. The hash
286
  // code will only be computed once.
287
 
288
  Hashkey hk(s, length);
289
  typename String_set_type::const_iterator p = this->string_set_.find(hk);
290
  if (p != this->string_set_.end())
291
    {
292
      if (pkey != NULL)
293
        *pkey = p->second;
294
      return p->first.string;
295
    }
296
 
297
  this->key_to_offset_.push_back(0);
298
 
299
  hk.string = this->add_string(s, length);
300
  // The contents of the string stay the same, so we don't need to
301
  // adjust hk.hash_code or hk.length.
302
 
303
  std::pair<Hashkey, Hashval> element(hk, k);
304
 
305
  Insert_type ins = this->string_set_.insert(element);
306
  gold_assert(ins.second);
307
 
308
  if (pkey != NULL)
309
    *pkey = k;
310
  return hk.string;
311
}
312
 
313
template<typename Stringpool_char>
314
const Stringpool_char*
315
Stringpool_template<Stringpool_char>::find(const Stringpool_char* s,
316
                                           Key* pkey) const
317
{
318
  Hashkey hk(s);
319
  typename String_set_type::const_iterator p = this->string_set_.find(hk);
320
  if (p == this->string_set_.end())
321
    return NULL;
322
 
323
  if (pkey != NULL)
324
    *pkey = p->second;
325
 
326
  return p->first.string;
327
}
328
 
329
// Comparison routine used when sorting into an ELF strtab.  We want
330
// to sort this so that when one string is a suffix of another, we
331
// always see the shorter string immediately after the longer string.
332
// For example, we want to see these strings in this order:
333
//   abcd
334
//   cd
335
//   d
336
// When strings are not suffixes, we don't care what order they are
337
// in, but we need to ensure that suffixes wind up next to each other.
338
// So we do a reversed lexicographic sort on the reversed string.
339
 
340
template<typename Stringpool_char>
341
bool
342
Stringpool_template<Stringpool_char>::Stringpool_sort_comparison::operator()(
343
  const Stringpool_sort_info& sort_info1,
344
  const Stringpool_sort_info& sort_info2) const
345
{
346
  const Hashkey& h1(sort_info1->first);
347
  const Hashkey& h2(sort_info2->first);
348
  const Stringpool_char* s1 = h1.string;
349
  const Stringpool_char* s2 = h2.string;
350
  const size_t len1 = h1.length;
351
  const size_t len2 = h2.length;
352
  const size_t minlen = len1 < len2 ? len1 : len2;
353
  const Stringpool_char* p1 = s1 + len1 - 1;
354
  const Stringpool_char* p2 = s2 + len2 - 1;
355
  for (size_t i = minlen; i > 0; --i, --p1, --p2)
356
    {
357
      if (*p1 != *p2)
358
        return *p1 > *p2;
359
    }
360
  return len1 > len2;
361
}
362
 
363
// Return whether s1 is a suffix of s2.
364
 
365
template<typename Stringpool_char>
366
bool
367
Stringpool_template<Stringpool_char>::is_suffix(const Stringpool_char* s1,
368
                                                size_t len1,
369
                                                const Stringpool_char* s2,
370
                                                size_t len2)
371
{
372
  if (len1 > len2)
373
    return false;
374
  return memcmp(s1, s2 + len2 - len1, len1 * sizeof(Stringpool_char)) == 0;
375
}
376
 
377
// Turn the stringpool into an ELF strtab: determine the offsets of
378
// each string in the table.
379
 
380
template<typename Stringpool_char>
381
void
382
Stringpool_template<Stringpool_char>::set_string_offsets()
383
{
384
  if (this->strtab_size_ != 0)
385
    {
386
      // We've already computed the offsets.
387
      return;
388
    }
389
 
390
  const size_t charsize = sizeof(Stringpool_char);
391
 
392
  // Offset 0 may be reserved for the empty string.
393
  section_offset_type offset = this->zero_null_ ? charsize : 0;
394
 
395
  // Sorting to find suffixes can take over 25% of the total CPU time
396
  // used by the linker.  Since it's merely an optimization to reduce
397
  // the strtab size, and gives a relatively small benefit (it's
398
  // typically rare for a symbol to be a suffix of another), we only
399
  // take the time to sort when the user asks for heavy optimization.
400
  if (!this->optimize_)
401
    {
402
      for (typename String_set_type::iterator curr = this->string_set_.begin();
403
           curr != this->string_set_.end();
404
           curr++)
405
        {
406
          section_offset_type* poff = &this->key_to_offset_[curr->second - 1];
407
          if (this->zero_null_ && curr->first.string[0] == 0)
408
            *poff = 0;
409
          else
410
            {
411
              *poff = offset;
412
              offset += (curr->first.length + 1) * charsize;
413
            }
414
        }
415
    }
416
  else
417
    {
418
      size_t count = this->string_set_.size();
419
 
420
      std::vector<Stringpool_sort_info> v;
421
      v.reserve(count);
422
 
423
      for (typename String_set_type::iterator p = this->string_set_.begin();
424
           p != this->string_set_.end();
425
           ++p)
426
        v.push_back(Stringpool_sort_info(p));
427
 
428
      std::sort(v.begin(), v.end(), Stringpool_sort_comparison());
429
 
430
      section_offset_type last_offset = -1;
431
      for (typename std::vector<Stringpool_sort_info>::iterator last = v.end(),
432
             curr = v.begin();
433
           curr != v.end();
434
           last = curr++)
435
        {
436
          section_offset_type this_offset;
437
          if (this->zero_null_ && (*curr)->first.string[0] == 0)
438
            this_offset = 0;
439
          else if (last != v.end()
440
                   && is_suffix((*curr)->first.string,
441
                                (*curr)->first.length,
442
                                (*last)->first.string,
443
                                (*last)->first.length))
444
            this_offset = (last_offset
445
                           + (((*last)->first.length - (*curr)->first.length)
446
                              * charsize));
447
          else
448
            {
449
              this_offset = offset;
450
              offset += ((*curr)->first.length + 1) * charsize;
451
            }
452
          this->key_to_offset_[(*curr)->second - 1] = this_offset;
453
          last_offset = this_offset;
454
        }
455
    }
456
 
457
  this->strtab_size_ = offset;
458
}
459
 
460
// Get the offset of a string in the ELF strtab.  The string must
461
// exist.
462
 
463
template<typename Stringpool_char>
464
section_offset_type
465
Stringpool_template<Stringpool_char>::get_offset(const Stringpool_char* s)
466
  const
467
{
468
  return this->get_offset_with_length(s, string_length(s));
469
}
470
 
471
template<typename Stringpool_char>
472
section_offset_type
473
Stringpool_template<Stringpool_char>::get_offset_with_length(
474
    const Stringpool_char* s,
475
    size_t length) const
476
{
477
  gold_assert(this->strtab_size_ != 0);
478
  Hashkey hk(s, length);
479
  typename String_set_type::const_iterator p = this->string_set_.find(hk);
480
  if (p != this->string_set_.end())
481
    return this->key_to_offset_[p->second - 1];
482
  gold_unreachable();
483
}
484
 
485
// Write the ELF strtab into the buffer.
486
 
487
template<typename Stringpool_char>
488
void
489
Stringpool_template<Stringpool_char>::write_to_buffer(
490
    unsigned char* buffer,
491
    section_size_type bufsize)
492
{
493
  gold_assert(this->strtab_size_ != 0);
494
  gold_assert(bufsize >= this->strtab_size_);
495
  if (this->zero_null_)
496
    buffer[0] = '\0';
497
  for (typename String_set_type::const_iterator p = this->string_set_.begin();
498
       p != this->string_set_.end();
499
       ++p)
500
    {
501
      const int len = (p->first.length + 1) * sizeof(Stringpool_char);
502
      const section_offset_type offset = this->key_to_offset_[p->second - 1];
503
      gold_assert(static_cast<section_size_type>(offset) + len
504
                  <= this->strtab_size_);
505
      memcpy(buffer + offset, p->first.string, len);
506
    }
507
}
508
 
509
// Write the ELF strtab into the output file at the specified offset.
510
 
511
template<typename Stringpool_char>
512
void
513
Stringpool_template<Stringpool_char>::write(Output_file* of, off_t offset)
514
{
515
  gold_assert(this->strtab_size_ != 0);
516
  unsigned char* view = of->get_output_view(offset, this->strtab_size_);
517
  this->write_to_buffer(view, this->strtab_size_);
518
  of->write_output_view(offset, this->strtab_size_, view);
519
}
520
 
521
// Print statistical information to stderr.  This is used for --stats.
522
 
523
template<typename Stringpool_char>
524
void
525
Stringpool_template<Stringpool_char>::print_stats(const char* name) const
526
{
527
#if defined(HAVE_TR1_UNORDERED_MAP) || defined(HAVE_EXT_HASH_MAP)
528
  fprintf(stderr, _("%s: %s entries: %zu; buckets: %zu\n"),
529
          program_name, name, this->string_set_.size(),
530
          this->string_set_.bucket_count());
531
#else
532
  fprintf(stderr, _("%s: %s entries: %zu\n"),
533
          program_name, name, this->table_.size());
534
#endif
535
  fprintf(stderr, _("%s: %s Stringdata structures: %zu\n"),
536
          program_name, name, this->strings_.size());
537
}
538
 
539
// Instantiate the templates we need.
540
 
541
template
542
class Stringpool_template<char>;
543
 
544
template
545
class Stringpool_template<uint16_t>;
546
 
547
template
548
class Stringpool_template<uint32_t>;
549
 
550
} // End namespace gold.

powered by: WebSVN 2.1.0

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