1 // stringpool.cc -- a string pool for gold
11 #include "stringpool.h"
16 Stringpool::Stringpool()
17 : string_set_(), strings_(), strtab_size_(0), next_index_(1)
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. If PKEY is not NULL, set *PKEY to the key.
61 Stringpool::add_string(const char* s
, Key
* pkey
)
63 // The size we allocate for a new Stringdata.
64 const size_t buffer_size
= 1000;
65 // The amount we multiply the Stringdata index when calculating the
67 const size_t key_mult
= 1024;
68 assert(key_mult
>= buffer_size
);
70 size_t len
= strlen(s
);
74 if (len
>= buffer_size
)
76 alc
= sizeof(Stringdata
) + len
;
79 else if (this->strings_
.empty())
80 alc
= sizeof(Stringdata
) + buffer_size
;
83 Stringdata
*psd
= this->strings_
.front();
84 if (len
>= psd
->alc
- psd
->len
)
85 alc
= sizeof(Stringdata
) + buffer_size
;
88 char* ret
= psd
->data
+ psd
->len
;
89 memcpy(ret
, s
, len
+ 1);
92 *pkey
= psd
->index
* key_mult
+ psd
->len
;
100 Stringdata
*psd
= reinterpret_cast<Stringdata
*>(new char[alc
]);
101 psd
->alc
= alc
- sizeof(Stringdata
);
102 memcpy(psd
->data
, s
, len
+ 1);
104 psd
->index
= this->next_index_
;
108 *pkey
= psd
->index
* key_mult
;
111 this->strings_
.push_front(psd
);
113 this->strings_
.push_back(psd
);
118 // Add a string to a string pool.
121 Stringpool::add(const char* s
, Key
* pkey
)
123 // FIXME: This will look up the entry twice in the hash table. The
124 // problem is that we can't insert S before we canonicalize it. I
125 // don't think there is a way to handle this correctly with
126 // unordered_map, so this should be replaced with custom code to do
127 // what we need, which is to return the empty slot.
129 String_set_type::const_iterator p
= this->string_set_
.find(s
);
130 if (p
!= this->string_set_
.end())
133 *pkey
= p
->second
.first
;
138 const char* ret
= this->add_string(s
, &k
);
140 const off_t ozero
= 0;
141 std::pair
<const char*, Val
> element(ret
, std::make_pair(k
, ozero
));
142 std::pair
<String_set_type::iterator
, bool> ins
=
143 this->string_set_
.insert(element
);
152 // Add a prefix of a string to a string pool.
155 Stringpool::add(const char* s
, size_t len
, Key
* pkey
)
157 // FIXME: This implementation should be rewritten when we rewrite
158 // the hash table to avoid copying.
159 std::string
st(s
, len
);
160 return this->add(st
, pkey
);
164 Stringpool::find(const char* s
, Key
* pkey
) const
166 String_set_type::const_iterator p
= this->string_set_
.find(s
);
167 if (p
== this->string_set_
.end())
171 *pkey
= p
->second
.first
;
176 // Comparison routine used when sorting into an ELF strtab. We want
177 // to sort this so that when one string is a suffix of another, we
178 // always see the shorter string immediately after the longer string.
179 // For example, we want to see these strings in this order:
183 // When strings are not suffixes, we don't care what order they are
184 // in, but we need to ensure that suffixes wind up next to each other.
185 // So we do a reversed lexicographic sort on the reversed string.
188 Stringpool::Stringpool_sort_comparison::operator()(
189 String_set_type::iterator it1
,
190 String_set_type::iterator it2
) const
192 const char* s1
= it1
->first
;
193 const char* s2
= it2
->first
;
194 int len1
= strlen(s1
);
195 int len2
= strlen(s2
);
196 int minlen
= len1
< len2
? len1
: len2
;
197 const char* p1
= s1
+ len1
- 1;
198 const char* p2
= s2
+ len2
- 1;
199 for (int i
= minlen
- 1; i
>= 0; --i
, --p1
, --p2
)
207 // Return whether s1 is a suffix of s2.
210 Stringpool::is_suffix(const char* s1
, const char* s2
)
212 size_t len1
= strlen(s1
);
213 size_t len2
= strlen(s2
);
216 return strcmp(s1
, s2
+ len2
- len1
) == 0;
219 // Turn the stringpool into an ELF strtab: determine the offsets of
220 // each string in the table.
223 Stringpool::set_string_offsets()
225 size_t count
= this->string_set_
.size();
227 std::vector
<String_set_type::iterator
> v
;
230 for (String_set_type::iterator p
= this->string_set_
.begin();
231 p
!= this->string_set_
.end();
235 std::sort(v
.begin(), v
.end(), Stringpool_sort_comparison());
237 // Offset 0 is reserved for the empty string.
239 for (size_t i
= 0; i
< count
; ++i
)
241 if (v
[i
]->first
[0] == '\0')
242 v
[i
]->second
.second
= 0;
243 else if (i
> 0 && Stringpool::is_suffix(v
[i
]->first
, v
[i
- 1]->first
))
244 v
[i
]->second
.second
= (v
[i
- 1]->second
.second
245 + strlen(v
[i
- 1]->first
)
246 - strlen(v
[i
]->first
));
249 v
[i
]->second
.second
= offset
;
250 offset
+= strlen(v
[i
]->first
) + 1;
254 this->strtab_size_
= offset
;
257 // Get the offset of a string in the ELF strtab. The string must
261 Stringpool::get_offset(const char* s
) const
263 String_set_type::const_iterator p
= this->string_set_
.find(s
);
264 if (p
!= this->string_set_
.end())
265 return p
->second
.second
;
269 // Write the ELF strtab into the output file at the specified offset.
272 Stringpool::write(Output_file
* of
, off_t offset
)
274 unsigned char* viewu
= of
->get_output_view(offset
, this->strtab_size_
);
275 char* view
= reinterpret_cast<char*>(viewu
);
277 for (String_set_type::const_iterator p
= this->string_set_
.begin();
278 p
!= this->string_set_
.end();
280 strcpy(view
+ p
->second
.second
, p
->first
);
281 of
->write_output_view(offset
, this->strtab_size_
, viewu
);
284 } // End namespace gold.
This page took 0.0421010000000001 seconds and 5 git commands to generate.