Add casts to avoid warnings.
[external/binutils.git] / gold / stringpool.cc
1 // stringpool.cc -- a string pool for gold
2
3 // Copyright 2006, 2007 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_(), strings_(), strtab_size_(0), next_index_(1),
39     next_uncopied_key_(-1), zero_null_(true)
40 {
41 }
42
43 template<typename Stringpool_char>
44 void
45 Stringpool_template<Stringpool_char>::clear()
46 {
47   for (typename std::list<Stringdata*>::iterator p = this->strings_.begin();
48        p != this->strings_.end();
49        ++p)
50     delete[] reinterpret_cast<char*>(*p);
51   this->strings_.clear();
52   this->string_set_.clear();
53 }
54
55 template<typename Stringpool_char>
56 Stringpool_template<Stringpool_char>::~Stringpool_template()
57 {
58   this->clear();
59 }
60
61 // Return the length of a string of arbitrary character type.
62
63 template<typename Stringpool_char>
64 size_t
65 Stringpool_template<Stringpool_char>::string_length(const Stringpool_char* p)
66 {
67   size_t len = 0;
68   for (; *p != 0; ++p)
69     ++len;
70   return len;
71 }
72
73 // Specialize string_length for char.  Maybe we could just use
74 // std::char_traits<>::length?
75
76 template<>
77 inline size_t
78 Stringpool_template<char>::string_length(const char* p)
79 {
80   return strlen(p);
81 }
82
83 // Equality comparison function.
84
85 template<typename Stringpool_char>
86 bool
87 Stringpool_template<Stringpool_char>::Stringpool_eq::operator()(
88     const Stringpool_char* s1,
89     const Stringpool_char* s2) const
90 {
91   while (*s1 != 0)
92     if (*s1++ != *s2++)
93       return false;
94   return *s2 == 0;
95 }
96
97 // Specialize equality comparison for char.
98
99 template<>
100 bool
101 Stringpool_template<char>::Stringpool_eq::operator()(const char* s1,
102                                                      const char* s2) const
103 {
104   return strcmp(s1, s2) == 0;
105 }
106
107 // Hash function.
108
109 template<typename Stringpool_char>
110 size_t
111 Stringpool_template<Stringpool_char>::Stringpool_hash::operator()(
112     const Stringpool_char* s) const
113 {
114   // Fowler/Noll/Vo (FNV) hash (type FNV-1a).
115   if (sizeof(size_t) > 4)
116     {
117       size_t result = static_cast<size_t>(14695981039346656037ULL);
118       while (*s != 0)
119         {
120           const char* p = reinterpret_cast<const char*>(s);
121           for (size_t i = 0; i < sizeof(Stringpool_char); ++i)
122             {
123               result ^= (size_t) *p++;
124               result *= 1099511628211ULL;
125             }
126           ++s;
127         }
128       return result;
129     }
130   else
131     {
132       size_t result = 2166136261UL;
133       while (*s != 0)
134         {
135           const char* p = reinterpret_cast<const char*>(s);
136           for (size_t i = 0; i < sizeof(Stringpool_char); ++i)
137             {
138               result ^= (size_t) *p++;
139               result *= 16777619UL;
140             }
141           ++s;
142         }
143       return result;
144     }
145 }
146
147 // Add a string to the list of canonical strings.  Return a pointer to
148 // the canonical string.  If PKEY is not NULL, set *PKEY to the key.
149
150 template<typename Stringpool_char>
151 const Stringpool_char*
152 Stringpool_template<Stringpool_char>::add_string(const Stringpool_char* s,
153                                                  Key* pkey)
154 {
155   // We are in trouble if we've already computed the string offsets.
156   gold_assert(this->strtab_size_ == 0);
157
158   // The size we allocate for a new Stringdata.
159   const size_t buffer_size = 1000;
160   // The amount we multiply the Stringdata index when calculating the
161   // key.
162   const size_t key_mult = 1024;
163   gold_assert(key_mult >= buffer_size);
164
165   size_t len = (string_length(s) + 1) * sizeof(Stringpool_char);
166
167   size_t alc;
168   bool front = true;
169   if (len > buffer_size)
170     {
171       alc = sizeof(Stringdata) + len;
172       front = false;
173     }
174   else if (this->strings_.empty())
175     alc = sizeof(Stringdata) + buffer_size;
176   else
177     {
178       Stringdata *psd = this->strings_.front();
179       if (len > psd->alc - psd->len)
180         alc = sizeof(Stringdata) + buffer_size;
181       else
182         {
183           char* ret = psd->data + psd->len;
184           memcpy(ret, s, len);
185
186           if (pkey != NULL)
187             *pkey = psd->index * key_mult + psd->len;
188
189           psd->len += len;
190
191           return reinterpret_cast<const Stringpool_char*>(ret);
192         }
193     }
194
195   Stringdata *psd = reinterpret_cast<Stringdata*>(new char[alc]);
196   psd->alc = alc - sizeof(Stringdata);
197   memcpy(psd->data, s, len);
198   psd->len = len;
199   psd->index = this->next_index_;
200   ++this->next_index_;
201
202   if (pkey != NULL)
203     *pkey = psd->index * key_mult;
204
205   if (front)
206     this->strings_.push_front(psd);
207   else
208     this->strings_.push_back(psd);
209
210   return reinterpret_cast<const Stringpool_char*>(psd->data);
211 }
212
213 // Add a string to a string pool.
214
215 template<typename Stringpool_char>
216 const Stringpool_char*
217 Stringpool_template<Stringpool_char>::add(const Stringpool_char* s, bool copy,
218                                           Key* pkey)
219 {
220   // FIXME: This will look up the entry twice in the hash table.  The
221   // problem is that we can't insert S before we canonicalize it.  I
222   // don't think there is a way to handle this correctly with
223   // unordered_map, so this should be replaced with custom code to do
224   // what we need, which is to return the empty slot.
225
226   typename String_set_type::const_iterator p = this->string_set_.find(s);
227   if (p != this->string_set_.end())
228     {
229       if (pkey != NULL)
230         *pkey = p->second.first;
231       return p->first;
232     }
233
234   Key k;
235   const Stringpool_char* ret;
236   if (copy)
237     ret = this->add_string(s, &k);
238   else
239     {
240       ret = s;
241       k = this->next_uncopied_key_;
242       --this->next_uncopied_key_;
243     }
244
245   const off_t ozero = 0;
246   std::pair<const Stringpool_char*, Val> element(ret,
247                                                  std::make_pair(k, ozero));
248   std::pair<typename String_set_type::iterator, bool> ins =
249     this->string_set_.insert(element);
250   gold_assert(ins.second);
251
252   if (pkey != NULL)
253     *pkey = k;
254
255   return ret;
256 }
257
258 // Add a prefix of a string to a string pool.
259
260 template<typename Stringpool_char>
261 const Stringpool_char*
262 Stringpool_template<Stringpool_char>::add_prefix(const Stringpool_char* s,
263                                                  size_t len,
264                                                  Key* pkey)
265 {
266   // FIXME: This implementation should be rewritten when we rewrite
267   // the hash table to avoid copying.
268   std::basic_string<Stringpool_char> st(s, len);
269   return this->add(st.c_str(), true, pkey);
270 }
271
272 template<typename Stringpool_char>
273 const Stringpool_char*
274 Stringpool_template<Stringpool_char>::find(const Stringpool_char* s,
275                                            Key* pkey) const
276 {
277   typename String_set_type::const_iterator p = this->string_set_.find(s);
278   if (p == this->string_set_.end())
279     return NULL;
280
281   if (pkey != NULL)
282     *pkey = p->second.first;
283
284   return p->first;
285 }
286
287 // Comparison routine used when sorting into an ELF strtab.  We want
288 // to sort this so that when one string is a suffix of another, we
289 // always see the shorter string immediately after the longer string.
290 // For example, we want to see these strings in this order:
291 //   abcd
292 //   cd
293 //   d
294 // When strings are not suffixes, we don't care what order they are
295 // in, but we need to ensure that suffixes wind up next to each other.
296 // So we do a reversed lexicographic sort on the reversed string.
297
298 template<typename Stringpool_char>
299 bool
300 Stringpool_template<Stringpool_char>::Stringpool_sort_comparison::operator()(
301   const Stringpool_sort_info& sort_info1,
302   const Stringpool_sort_info& sort_info2) const
303 {
304   const Stringpool_char* s1 = sort_info1.it->first;
305   const Stringpool_char* s2 = sort_info2.it->first;
306   const size_t len1 = sort_info1.string_length;
307   const size_t len2 = sort_info2.string_length;
308   const size_t minlen = len1 < len2 ? len1 : len2;
309   const Stringpool_char* p1 = s1 + len1 - 1;
310   const Stringpool_char* p2 = s2 + len2 - 1;
311   for (size_t i = minlen; i > 0; --i, --p1, --p2)
312     {
313       if (*p1 != *p2)
314         return *p1 > *p2;
315     }
316   return len1 > len2;
317 }
318
319 // Return whether s1 is a suffix of s2.
320
321 template<typename Stringpool_char>
322 bool
323 Stringpool_template<Stringpool_char>::is_suffix(const Stringpool_char* s1,
324                                                 size_t len1,
325                                                 const Stringpool_char* s2,
326                                                 size_t len2)
327 {
328   if (len1 > len2)
329     return false;
330   return memcmp(s1, s2 + len2 - len1, len1 * sizeof(Stringpool_char)) == 0;
331 }
332
333 // Turn the stringpool into an ELF strtab: determine the offsets of
334 // each string in the table.
335
336 template<typename Stringpool_char>
337 void
338 Stringpool_template<Stringpool_char>::set_string_offsets()
339 {
340   if (this->strtab_size_ != 0)
341     {
342       // We've already computed the offsets.
343       return;
344     }
345
346   const size_t charsize = sizeof(Stringpool_char);
347
348   // Offset 0 may be reserved for the empty string.
349   off_t offset = this->zero_null_ ? charsize : 0;
350
351   // Sorting to find suffixes can take over 25% of the total CPU time
352   // used by the linker.  Since it's merely an optimization to reduce
353   // the strtab size, and gives a relatively small benefit (it's
354   // typically rare for a symbol to be a suffix of another), we only
355   // take the time to sort when the user asks for heavy optimization.
356   if (parameters->optimization_level() < 2)
357     {
358       for (typename String_set_type::iterator curr = this->string_set_.begin();
359            curr != this->string_set_.end();
360            curr++)
361         {
362           if (this->zero_null_ && curr->first[0] == 0)
363             curr->second.second = 0;
364           else
365             {
366               curr->second.second = offset;
367               offset += (string_length(curr->first) + 1) * charsize;
368             }
369         }
370     }
371   else
372     {
373       size_t count = this->string_set_.size();
374
375       std::vector<Stringpool_sort_info> v;
376       v.reserve(count);
377
378       for (typename String_set_type::iterator p = this->string_set_.begin();
379            p != this->string_set_.end();
380            ++p)
381         v.push_back(Stringpool_sort_info(p, string_length(p->first)));
382
383       std::sort(v.begin(), v.end(), Stringpool_sort_comparison());
384
385       for (typename std::vector<Stringpool_sort_info>::iterator last = v.end(),
386              curr = v.begin();
387            curr != v.end();
388            last = curr++)
389         {
390           if (this->zero_null_ && curr->it->first[0] == 0)
391             curr->it->second.second = 0;
392           else if (last != v.end()
393                    && is_suffix(curr->it->first, curr->string_length,
394                                 last->it->first, last->string_length))
395             curr->it->second.second = (last->it->second.second
396                                        + ((last->string_length
397                                            - curr->string_length)
398                                           * charsize));
399           else
400             {
401               curr->it->second.second = offset;
402               offset += (curr->string_length + 1) * charsize;
403             }
404         }
405     }
406
407   this->strtab_size_ = offset;
408 }
409
410 // Get the offset of a string in the ELF strtab.  The string must
411 // exist.
412
413 template<typename Stringpool_char>
414 off_t
415 Stringpool_template<Stringpool_char>::get_offset(const Stringpool_char* s)
416   const
417 {
418   gold_assert(this->strtab_size_ != 0);
419   typename String_set_type::const_iterator p = this->string_set_.find(s);
420   if (p != this->string_set_.end())
421     return p->second.second;
422   gold_unreachable();
423 }
424
425 // Write the ELF strtab into the buffer.
426
427 template<typename Stringpool_char>
428 void
429 Stringpool_template<Stringpool_char>::write_to_buffer(unsigned char* buffer,
430                                                       size_t bufsize)
431 {
432   gold_assert(this->strtab_size_ != 0);
433    // Quiet the compiler in opt mode.
434   if (bufsize < static_cast<size_t>(this->strtab_size_))
435     gold_assert(bufsize >= static_cast<size_t>(this->strtab_size_));
436   if (this->zero_null_)
437     buffer[0] = '\0';
438   for (typename String_set_type::const_iterator p = this->string_set_.begin();
439        p != this->string_set_.end();
440        ++p)
441     {
442       const int len = (string_length(p->first) + 1) * sizeof(Stringpool_char);
443       gold_assert(p->second.second + len <= this->strtab_size_);
444       memcpy(buffer + p->second.second, p->first, len);
445     }
446 }
447
448 // Write the ELF strtab into the output file at the specified offset.
449
450 template<typename Stringpool_char>
451 void
452 Stringpool_template<Stringpool_char>::write(Output_file* of, off_t offset)
453 {
454   gold_assert(this->strtab_size_ != 0);
455   unsigned char* view = of->get_output_view(offset, this->strtab_size_);
456   this->write_to_buffer(view, this->strtab_size_);
457   of->write_output_view(offset, this->strtab_size_, view);
458 }
459
460 // Instantiate the templates we need.
461
462 template
463 class Stringpool_template<char>;
464
465 template
466 class Stringpool_template<uint16_t>;
467
468 template
469 class Stringpool_template<uint32_t>;
470
471 } // End namespace gold.