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