1 // stringpool.cc -- a string pool for gold
11 #include "stringpool.h"
16 Stringpool::Stringpool()
17 : string_set_(), strings_(), strtab_size_(0)
21 Stringpool::~Stringpool()
23 for (std::list<Stringdata*>::iterator p = this->strings_.begin();
24 p != this->strings_.end();
26 delete[] reinterpret_cast<char*>(*p);
32 Stringpool::Stringpool_hash::operator()(const char* s) const
34 // Fowler/Noll/Vo (FNV) hash (type FNV-1a).
35 if (sizeof(size_t) == 8)
37 size_t result = static_cast<size_t>(14695981039346656037ULL);
40 result &= (size_t) *s++;
41 result *= 1099511628211ULL;
47 size_t result = 2166136261UL;
50 result ^= (size_t) *s++;
57 // Add a string to the list of canonical strings. Return a pointer to
58 // the canonical string.
61 Stringpool::add_string(const char* s)
63 const size_t buffer_size = 1000;
64 size_t len = strlen(s);
68 if (len >= buffer_size)
70 alc = sizeof(Stringdata) + len;
73 else if (this->strings_.empty())
74 alc = sizeof(Stringdata) + buffer_size;
77 Stringdata *psd = this->strings_.front();
78 if (len >= psd->alc - psd->len)
79 alc = sizeof(Stringdata) + buffer_size;
82 char* ret = psd->data + psd->len;
83 memcpy(ret, s, len + 1);
89 Stringdata *psd = reinterpret_cast<Stringdata*>(new char[alc]);
90 psd->alc = alc - sizeof(Stringdata);
91 memcpy(psd->data, s, len + 1);
94 this->strings_.push_front(psd);
96 this->strings_.push_back(psd);
100 // Add a string to a string pool.
103 Stringpool::add(const char* s)
105 // FIXME: This will look up the entry twice in the hash table. The
106 // problem is that we can't insert S before we canonicalize it. I
107 // don't think there is a way to handle this correctly with
108 // unordered_map, so this should be replaced with custom code to do
109 // what we need, which is to return the empty slot.
111 String_set_type::const_iterator p = this->string_set_.find(s);
112 if (p != this->string_set_.end())
115 const char* ret = this->add_string(s);
116 std::pair<const char*, off_t> val(ret, 0);
117 std::pair<String_set_type::iterator, bool> ins =
118 this->string_set_.insert(val);
123 // Add a prefix of a string to a string pool.
126 Stringpool::add(const char* s, size_t len)
128 // FIXME: This implementation should be rewritten when we rewrite
129 // the hash table to avoid copying.
130 std::string st(s, len);
131 return this->add(st);
135 Stringpool::find(const char* s) const
137 String_set_type::const_iterator p = this->string_set_.find(s);
138 if (p == this->string_set_.end())
143 // Comparison routine used when sorting into an ELF strtab. We want
144 // to sort this so that when one string is a suffix of another, we
145 // always see the shorter string immediately after the longer string.
146 // For example, we want to see these strings in this order:
150 // When strings are not suffixes, we don't care what order they are
151 // in, but we need to ensure that suffixes wind up next to each other.
152 // So we do a reversed lexicographic sort on the reversed string.
155 Stringpool::Stringpool_sort_comparison::operator()(
156 String_set_type::iterator it1,
157 String_set_type::iterator it2) const
159 const char* s1 = it1->first;
160 const char* s2 = it2->first;
161 int len1 = strlen(s1);
162 int len2 = strlen(s2);
163 int minlen = len1 < len2 ? len1 : len2;
164 const char* p1 = s1 + len1 - 1;
165 const char* p2 = s2 + len2 - 1;
166 for (int i = minlen - 1; i >= 0; --i, --p1, --p2)
174 // Return whether s1 is a suffix of s2.
177 Stringpool::is_suffix(const char* s1, const char* s2)
179 size_t len1 = strlen(s1);
180 size_t len2 = strlen(s2);
183 return strcmp(s1, s2 + len2 - len1) == 0;
186 // Turn the stringpool into an ELF strtab: determine the offsets of
187 // each string in the table.
190 Stringpool::set_string_offsets()
192 size_t count = this->string_set_.size();
194 std::vector<String_set_type::iterator> v;
197 for (String_set_type::iterator p = this->string_set_.begin();
198 p != this->string_set_.end();
202 std::sort(v.begin(), v.end(), Stringpool_sort_comparison());
204 // Offset 0 is reserved for the empty string.
206 for (size_t i = 0; i < count; ++i)
208 if (v[i]->first[0] == '\0')
210 else if (i > 0 && Stringpool::is_suffix(v[i]->first, v[i - 1]->first))
211 v[i]->second = (v[i - 1]->second
212 + strlen(v[i - 1]->first)
213 - strlen(v[i]->first));
216 v[i]->second = offset;
217 offset += strlen(v[i]->first) + 1;
221 this->strtab_size_ = offset;
224 // Get the offset of a string in the ELF strtab. The string must
228 Stringpool::get_offset(const char* s) const
230 String_set_type::const_iterator p = this->string_set_.find(s);
231 if (p != this->string_set_.end())
236 // Write the ELF strtab into the output file at the specified offset.
239 Stringpool::write(Output_file* of, off_t offset)
241 unsigned char* viewu = of->get_output_view(offset, this->strtab_size_);
242 char* view = reinterpret_cast<char*>(viewu);
244 for (String_set_type::const_iterator p = this->string_set_.begin();
245 p != this->string_set_.end();
247 strcpy(view + p->second, p->first);
248 of->write_output_view(offset, this->strtab_size_, viewu);
251 } // End namespace gold.