daily update
[binutils.git] / gold / stringpool.cc
blobd53cf7792ffc6c9bea0b681ae86a77d64ebd3513
1 // stringpool.cc -- a string pool for gold
3 #include "gold.h"
5 #include <cstring>
6 #include <algorithm>
7 #include <vector>
9 #include "output.h"
10 #include "stringpool.h"
12 namespace gold
15 Stringpool::Stringpool()
16 : string_set_(), strings_(), strtab_size_(0), next_index_(1)
20 Stringpool::~Stringpool()
22 for (std::list<Stringdata*>::iterator p = this->strings_.begin();
23 p != this->strings_.end();
24 ++p)
25 delete[] reinterpret_cast<char*>(*p);
28 // Hash function.
30 size_t
31 Stringpool::Stringpool_hash::operator()(const char* s) const
33 // Fowler/Noll/Vo (FNV) hash (type FNV-1a).
34 if (sizeof(size_t) == 8)
36 size_t result = static_cast<size_t>(14695981039346656037ULL);
37 while (*s != '\0')
39 result &= (size_t) *s++;
40 result *= 1099511628211ULL;
42 return result;
44 else
46 size_t result = 2166136261UL;
47 while (*s != '\0')
49 result ^= (size_t) *s++;
50 result *= 16777619UL;
52 return result;
56 // Add a string to the list of canonical strings. Return a pointer to
57 // the canonical string. If PKEY is not NULL, set *PKEY to the key.
59 const char*
60 Stringpool::add_string(const char* s, Key* pkey)
62 // We are in trouble if we've already computed the string offsets.
63 gold_assert(this->strtab_size_ == 0);
65 // The size we allocate for a new Stringdata.
66 const size_t buffer_size = 1000;
67 // The amount we multiply the Stringdata index when calculating the
68 // key.
69 const size_t key_mult = 1024;
70 gold_assert(key_mult >= buffer_size);
72 size_t len = strlen(s);
74 size_t alc;
75 bool front = true;
76 if (len >= buffer_size)
78 alc = sizeof(Stringdata) + len;
79 front = false;
81 else if (this->strings_.empty())
82 alc = sizeof(Stringdata) + buffer_size;
83 else
85 Stringdata *psd = this->strings_.front();
86 if (len >= psd->alc - psd->len)
87 alc = sizeof(Stringdata) + buffer_size;
88 else
90 char* ret = psd->data + psd->len;
91 memcpy(ret, s, len + 1);
93 if (pkey != NULL)
94 *pkey = psd->index * key_mult + psd->len;
96 psd->len += len + 1;
98 return ret;
102 Stringdata *psd = reinterpret_cast<Stringdata*>(new char[alc]);
103 psd->alc = alc - sizeof(Stringdata);
104 memcpy(psd->data, s, len + 1);
105 psd->len = len + 1;
106 psd->index = this->next_index_;
107 ++this->next_index_;
109 if (pkey != NULL)
110 *pkey = psd->index * key_mult;
112 if (front)
113 this->strings_.push_front(psd);
114 else
115 this->strings_.push_back(psd);
117 return psd->data;
120 // Add a string to a string pool.
122 const char*
123 Stringpool::add(const char* s, Key* pkey)
125 // FIXME: This will look up the entry twice in the hash table. The
126 // problem is that we can't insert S before we canonicalize it. I
127 // don't think there is a way to handle this correctly with
128 // unordered_map, so this should be replaced with custom code to do
129 // what we need, which is to return the empty slot.
131 String_set_type::const_iterator p = this->string_set_.find(s);
132 if (p != this->string_set_.end())
134 if (pkey != NULL)
135 *pkey = p->second.first;
136 return p->first;
139 Key k;
140 const char* ret = this->add_string(s, &k);
142 const off_t ozero = 0;
143 std::pair<const char*, Val> element(ret, std::make_pair(k, ozero));
144 std::pair<String_set_type::iterator, bool> ins =
145 this->string_set_.insert(element);
146 gold_assert(ins.second);
148 if (pkey != NULL)
149 *pkey = k;
151 return ret;
154 // Add a prefix of a string to a string pool.
156 const char*
157 Stringpool::add(const char* s, size_t len, Key* pkey)
159 // FIXME: This implementation should be rewritten when we rewrite
160 // the hash table to avoid copying.
161 std::string st(s, len);
162 return this->add(st, pkey);
165 const char*
166 Stringpool::find(const char* s, Key* pkey) const
168 String_set_type::const_iterator p = this->string_set_.find(s);
169 if (p == this->string_set_.end())
170 return NULL;
172 if (pkey != NULL)
173 *pkey = p->second.first;
175 return p->first;
178 // Comparison routine used when sorting into an ELF strtab. We want
179 // to sort this so that when one string is a suffix of another, we
180 // always see the shorter string immediately after the longer string.
181 // For example, we want to see these strings in this order:
182 // abcd
183 // cd
184 // d
185 // When strings are not suffixes, we don't care what order they are
186 // in, but we need to ensure that suffixes wind up next to each other.
187 // So we do a reversed lexicographic sort on the reversed string.
189 bool
190 Stringpool::Stringpool_sort_comparison::operator()(
191 String_set_type::iterator it1,
192 String_set_type::iterator it2) const
194 const char* s1 = it1->first;
195 const char* s2 = it2->first;
196 int len1 = strlen(s1);
197 int len2 = strlen(s2);
198 int minlen = len1 < len2 ? len1 : len2;
199 const char* p1 = s1 + len1 - 1;
200 const char* p2 = s2 + len2 - 1;
201 for (int i = minlen - 1; i >= 0; --i, --p1, --p2)
203 if (*p1 != *p2)
204 return *p1 > *p2;
206 return len1 > len2;
209 // Return whether s1 is a suffix of s2.
211 bool
212 Stringpool::is_suffix(const char* s1, const char* s2)
214 size_t len1 = strlen(s1);
215 size_t len2 = strlen(s2);
216 if (len1 > len2)
217 return false;
218 return strcmp(s1, s2 + len2 - len1) == 0;
221 // Turn the stringpool into an ELF strtab: determine the offsets of
222 // each string in the table.
224 void
225 Stringpool::set_string_offsets()
227 if (this->strtab_size_ != 0)
229 // We've already computed the offsets.
230 return;
233 size_t count = this->string_set_.size();
235 std::vector<String_set_type::iterator> v;
236 v.reserve(count);
238 for (String_set_type::iterator p = this->string_set_.begin();
239 p != this->string_set_.end();
240 ++p)
241 v.push_back(p);
243 std::sort(v.begin(), v.end(), Stringpool_sort_comparison());
245 // Offset 0 is reserved for the empty string.
246 off_t offset = 1;
247 for (size_t i = 0; i < count; ++i)
249 if (v[i]->first[0] == '\0')
250 v[i]->second.second = 0;
251 else if (i > 0 && Stringpool::is_suffix(v[i]->first, v[i - 1]->first))
252 v[i]->second.second = (v[i - 1]->second.second
253 + strlen(v[i - 1]->first)
254 - strlen(v[i]->first));
255 else
257 v[i]->second.second = offset;
258 offset += strlen(v[i]->first) + 1;
262 this->strtab_size_ = offset;
265 // Get the offset of a string in the ELF strtab. The string must
266 // exist.
268 off_t
269 Stringpool::get_offset(const char* s) const
271 gold_assert(this->strtab_size_ != 0);
272 String_set_type::const_iterator p = this->string_set_.find(s);
273 if (p != this->string_set_.end())
274 return p->second.second;
275 gold_unreachable();
278 // Write the ELF strtab into the output file at the specified offset.
280 void
281 Stringpool::write(Output_file* of, off_t offset)
283 gold_assert(this->strtab_size_ != 0);
284 unsigned char* viewu = of->get_output_view(offset, this->strtab_size_);
285 char* view = reinterpret_cast<char*>(viewu);
286 view[0] = '\0';
287 for (String_set_type::const_iterator p = this->string_set_.begin();
288 p != this->string_set_.end();
289 ++p)
290 strcpy(view + p->second.second, p->first);
291 of->write_output_view(offset, this->strtab_size_, viewu);
294 } // End namespace gold.