diff options
| -rw-r--r-- | gold/stringpool.cc | 214 | ||||
| -rw-r--r-- | gold/stringpool.h | 90 |
2 files changed, 184 insertions, 120 deletions
diff --git a/gold/stringpool.cc b/gold/stringpool.cc index 19698e2..0ac1dcb 100644 --- a/gold/stringpool.cc +++ b/gold/stringpool.cc @@ -80,13 +80,12 @@ Stringpool_template<char>::string_length(const char* p) return strlen(p); } -// Equality comparison function. +// Compare two strings of arbitrary character type for equality. template<typename Stringpool_char> bool -Stringpool_template<Stringpool_char>::Stringpool_eq::operator()( - const Stringpool_char* s1, - const Stringpool_char* s2) const +Stringpool_template<Stringpool_char>::string_equal(const Stringpool_char* s1, + const Stringpool_char* s2) { while (*s1 != 0) if (*s1++ != *s2++) @@ -94,62 +93,69 @@ Stringpool_template<Stringpool_char>::Stringpool_eq::operator()( return *s2 == 0; } -// Specialize equality comparison for char. +// Specialize string_equal for char. template<> -bool -Stringpool_template<char>::Stringpool_eq::operator()(const char* s1, - const char* s2) const +inline bool +Stringpool_template<char>::string_equal(const char* s1, const char* s2) { return strcmp(s1, s2) == 0; } -// Hash function. +// Equality comparison function for the hash table. + +template<typename Stringpool_char> +inline bool +Stringpool_template<Stringpool_char>::Stringpool_eq::operator()( + const Hashkey& h1, + const Hashkey& h2) const +{ + return (h1.hash_code == h2.hash_code + && h1.length == h2.length + && memcmp(h1.string, h2.string, + h1.length * sizeof(Stringpool_char)) == 0); +} + +// Hash function. The length is in characters, not bytes. template<typename Stringpool_char> size_t -Stringpool_template<Stringpool_char>::Stringpool_hash::operator()( - const Stringpool_char* s) const +Stringpool_template<Stringpool_char>::string_hash(const Stringpool_char* s, + size_t length) { // Fowler/Noll/Vo (FNV) hash (type FNV-1a). + const unsigned char* p = reinterpret_cast<const unsigned char*>(s); if (sizeof(size_t) > 4) { size_t result = static_cast<size_t>(14695981039346656037ULL); - while (*s != 0) + for (size_t i = 0; i < length * sizeof(Stringpool_char); ++i) { - const char* p = reinterpret_cast<const char*>(s); - for (size_t i = 0; i < sizeof(Stringpool_char); ++i) - { - result ^= (size_t) *p++; - result *= 1099511628211ULL; - } - ++s; + result ^= static_cast<size_t>(*p++); + result *= 1099511628211ULL; } return result; } else { size_t result = 2166136261UL; - while (*s != 0) + for (size_t i = 0; i < length * sizeof(Stringpool_char); ++i) { - const char* p = reinterpret_cast<const char*>(s); - for (size_t i = 0; i < sizeof(Stringpool_char); ++i) - { - result ^= (size_t) *p++; - result *= 16777619UL; - } - ++s; + result ^= static_cast<size_t>(*p++); + result *= 16777619UL; } return result; } } -// Add a string to the list of canonical strings. Return a pointer to -// the canonical string. If PKEY is not NULL, set *PKEY to the key. +// Add the string S to the list of canonical strings. Return a +// pointer to the canonical string. If PKEY is not NULL, set *PKEY to +// the key. LENGTH is the length of S in characters. Note that S may +// not be NUL terminated. template<typename Stringpool_char> const Stringpool_char* Stringpool_template<Stringpool_char>::add_string(const Stringpool_char* s, + size_t len, Key* pkey) { // We are in trouble if we've already computed the string offsets. @@ -162,7 +168,9 @@ Stringpool_template<Stringpool_char>::add_string(const Stringpool_char* s, const size_t key_mult = 1024; gold_assert(key_mult >= buffer_size); - size_t len = (string_length(s) + 1) * sizeof(Stringpool_char); + // Convert len to the number of bytes we need to allocate, including + // the null character. + len = (len + 1) * sizeof(Stringpool_char); size_t alc; bool front = true; @@ -181,7 +189,9 @@ Stringpool_template<Stringpool_char>::add_string(const Stringpool_char* s, else { char* ret = psd->data + psd->len; - memcpy(ret, s, len); + memcpy(ret, s, len - sizeof(Stringpool_char)); + memset(ret + len - sizeof(Stringpool_char), 0, + sizeof(Stringpool_char)); if (pkey != NULL) *pkey = psd->index * key_mult + psd->len; @@ -194,7 +204,9 @@ Stringpool_template<Stringpool_char>::add_string(const Stringpool_char* s, Stringdata *psd = reinterpret_cast<Stringdata*>(new char[alc]); psd->alc = alc - sizeof(Stringdata); - memcpy(psd->data, s, len); + memcpy(psd->data, s, len - sizeof(Stringpool_char)); + memset(psd->data + len - sizeof(Stringpool_char), 0, + sizeof(Stringpool_char)); psd->len = len; psd->index = this->next_index_; ++this->next_index_; @@ -217,42 +229,39 @@ const Stringpool_char* Stringpool_template<Stringpool_char>::add(const Stringpool_char* s, bool copy, Key* pkey) { - // FIXME: This will look up the entry twice in the hash table. The - // problem is that we can't insert S before we canonicalize it. I - // don't think there is a way to handle this correctly with - // unordered_map, so this should be replaced with custom code to do - // what we need, which is to return the empty slot. + typedef std::pair<typename String_set_type::iterator, bool> Insert_type; - typename String_set_type::const_iterator p = this->string_set_.find(s); - if (p != this->string_set_.end()) + if (!copy) { - if (pkey != NULL) - *pkey = p->second.first; - return p->first; - } + // When we don't need to copy the string, we can call insert + // directly. - Key k; - const Stringpool_char* ret; - if (copy) - ret = this->add_string(s, &k); - else - { - ret = s; - k = this->next_uncopied_key_; - --this->next_uncopied_key_; - } + const Key k = this->next_uncopied_key_; + const off_t ozero = 0; + std::pair<Hashkey, Hashval> element(Hashkey(s), + std::make_pair(k, ozero)); - const off_t ozero = 0; - std::pair<const Stringpool_char*, Val> element(ret, - std::make_pair(k, ozero)); - std::pair<typename String_set_type::iterator, bool> ins = - this->string_set_.insert(element); - gold_assert(ins.second); + Insert_type ins = this->string_set_.insert(element); - if (pkey != NULL) - *pkey = k; + typename String_set_type::const_iterator p = ins.first; + + if (ins.second) + { + // We just added the string. The key value has now been + // used. + --this->next_uncopied_key_; + } + else + { + gold_assert(k != p->second.first); + } + + if (pkey != NULL) + *pkey = p->second.first; + return p->first.string; + } - return ret; + return this->add_prefix(s, string_length(s), pkey); } // Add a prefix of a string to a string pool. @@ -263,10 +272,36 @@ Stringpool_template<Stringpool_char>::add_prefix(const Stringpool_char* s, size_t len, Key* pkey) { - // FIXME: This implementation should be rewritten when we rewrite - // the hash table to avoid copying. - std::basic_string<Stringpool_char> st(s, len); - return this->add(st.c_str(), true, pkey); + // When adding an entry, this will look it up twice in the hash + // table. The problem is that we can't insert S before we + // canonicalize it by copying it into the canonical list. The hash + // code will only be computed once, so this isn't all that + // expensive. + + Hashkey hk(s, len); + typename String_set_type::const_iterator p = this->string_set_.find(hk); + if (p != this->string_set_.end()) + { + if (pkey != NULL) + *pkey = p->second.first; + return p->first.string; + } + + Key k; + hk.string = this->add_string(s, len, &k); + // The contents of the string stay the same, so we don't need to + // adjust hk.hash_code or hk.length. + + const off_t ozero = 0; + std::pair<Hashkey, Hashval> element(hk, std::make_pair(k, ozero)); + + typedef std::pair<typename String_set_type::iterator, bool> Insert_type; + Insert_type ins = this->string_set_.insert(element); + gold_assert(ins.second); + + if (pkey != NULL) + *pkey = k; + return hk.string; } template<typename Stringpool_char> @@ -274,14 +309,15 @@ const Stringpool_char* Stringpool_template<Stringpool_char>::find(const Stringpool_char* s, Key* pkey) const { - typename String_set_type::const_iterator p = this->string_set_.find(s); + Hashkey hk(s); + typename String_set_type::const_iterator p = this->string_set_.find(hk); if (p == this->string_set_.end()) return NULL; if (pkey != NULL) *pkey = p->second.first; - return p->first; + return p->first.string; } // Comparison routine used when sorting into an ELF strtab. We want @@ -301,10 +337,12 @@ Stringpool_template<Stringpool_char>::Stringpool_sort_comparison::operator()( const Stringpool_sort_info& sort_info1, const Stringpool_sort_info& sort_info2) const { - const Stringpool_char* s1 = sort_info1.it->first; - const Stringpool_char* s2 = sort_info2.it->first; - const size_t len1 = sort_info1.string_length; - const size_t len2 = sort_info2.string_length; + const Hashkey& h1(sort_info1->first); + const Hashkey& h2(sort_info2->first); + const Stringpool_char* s1 = h1.string; + const Stringpool_char* s2 = h2.string; + const size_t len1 = h1.length; + const size_t len2 = h2.length; const size_t minlen = len1 < len2 ? len1 : len2; const Stringpool_char* p1 = s1 + len1 - 1; const Stringpool_char* p2 = s2 + len2 - 1; @@ -359,12 +397,12 @@ Stringpool_template<Stringpool_char>::set_string_offsets() curr != this->string_set_.end(); curr++) { - if (this->zero_null_ && curr->first[0] == 0) + if (this->zero_null_ && curr->first.string[0] == 0) curr->second.second = 0; else { curr->second.second = offset; - offset += (string_length(curr->first) + 1) * charsize; + offset += (curr->first.length + 1) * charsize; } } } @@ -378,7 +416,7 @@ Stringpool_template<Stringpool_char>::set_string_offsets() for (typename String_set_type::iterator p = this->string_set_.begin(); p != this->string_set_.end(); ++p) - v.push_back(Stringpool_sort_info(p, string_length(p->first))); + v.push_back(Stringpool_sort_info(p)); std::sort(v.begin(), v.end(), Stringpool_sort_comparison()); @@ -387,19 +425,21 @@ Stringpool_template<Stringpool_char>::set_string_offsets() curr != v.end(); last = curr++) { - if (this->zero_null_ && curr->it->first[0] == 0) - curr->it->second.second = 0; + if (this->zero_null_ && (*curr)->first.string[0] == 0) + (*curr)->second.second = 0; else if (last != v.end() - && is_suffix(curr->it->first, curr->string_length, - last->it->first, last->string_length)) - curr->it->second.second = (last->it->second.second - + ((last->string_length - - curr->string_length) - * charsize)); + && is_suffix((*curr)->first.string, + (*curr)->first.length, + (*last)->first.string, + (*last)->first.length)) + (*curr)->second.second = ((*last)->second.second + + (((*last)->first.length + - (*curr)->first.length) + * charsize)); else { - curr->it->second.second = offset; - offset += (curr->string_length + 1) * charsize; + (*curr)->second.second = offset; + offset += ((*curr)->first.length + 1) * charsize; } } } @@ -439,9 +479,9 @@ Stringpool_template<Stringpool_char>::write_to_buffer(unsigned char* buffer, p != this->string_set_.end(); ++p) { - const int len = (string_length(p->first) + 1) * sizeof(Stringpool_char); + const int len = (p->first.length + 1) * sizeof(Stringpool_char); gold_assert(p->second.second + len <= this->strtab_size_); - memcpy(buffer + p->second.second, p->first, len); + memcpy(buffer + p->second.second, p->first.string, len); } } diff --git a/gold/stringpool.h b/gold/stringpool.h index c5a3baf..929b4d1 100644 --- a/gold/stringpool.h +++ b/gold/stringpool.h @@ -161,6 +161,15 @@ class Stringpool_template static size_t string_length(const Stringpool_char*); + // Return whether two strings are equal. + static bool + string_equal(const Stringpool_char*, const Stringpool_char*); + + // Compute a hash code for a string. LENGTH is the length of the + // string in characters. + static size_t + string_hash(const Stringpool_char*, size_t length); + // We store the actual data in a list of these buffers. struct Stringdata { @@ -176,55 +185,70 @@ class Stringpool_template // Copy a string into the buffers, returning a canonical string. const Stringpool_char* - add_string(const Stringpool_char*, Key*); + add_string(const Stringpool_char*, size_t, Key*); + + // Return whether s1 is a suffix of s2. + static bool + is_suffix(const Stringpool_char* s1, size_t len1, + const Stringpool_char* s2, size_t len2); + + // The hash table key includes the string, the length of the string, + // and the hash code for the string. We put the hash code + // explicitly into the key so that we can do a find()/insert() + // sequence without having to recompute the hash. Computing the + // hash code is a significant user of CPU time in the linker. + struct Hashkey + { + const Stringpool_char* string; + // Length is in characters, not bytes. + size_t length; + size_t hash_code; + + // This goes in an STL container, so we need a default + // constructor. + Hashkey() + : string(NULL), length(0), hash_code(0) + { } + + // Note that these constructors are relatively expensive, because + // they compute the hash code. + Hashkey(const Stringpool_char* s) + : string(s), length(string_length(s)), hash_code(string_hash(s, length)) + { } + + Hashkey(const Stringpool_char* s, size_t len) + : string(s), length(len), hash_code(string_hash(s, len)) + { } + }; - // Hash function. + // Hash function. This is trivial, since we have already computed + // the hash. struct Stringpool_hash { size_t - operator()(const Stringpool_char*) const; + operator()(const Hashkey& hk) const + { return hk.hash_code; } }; // Equality comparison function for hash table. struct Stringpool_eq { bool - operator()(const Stringpool_char* p1, const Stringpool_char* p2) const; + operator()(const Hashkey&, const Hashkey&) const; }; - // Return whether s1 is a suffix of s2. - static bool - is_suffix(const Stringpool_char* s1, size_t len1, - const Stringpool_char* s2, size_t len2); - - // The hash table is a map from string names to a pair of Key and - // string table offsets. We only use the offsets if we turn this - // into an string table section. + // The hash table is a map from strings to a pair of Key and string + // table offsets. We only use the offsets if we turn this into an + // string table section. - typedef std::pair<Key, off_t> Val; + typedef std::pair<Key, off_t> Hashval; -#ifdef HAVE_TR1_UNORDERED_SET - typedef Unordered_map<const Stringpool_char*, Val, Stringpool_hash, - Stringpool_eq, - std::allocator<std::pair<const Stringpool_char* const, - Val> >, - true> String_set_type; -#else - typedef Unordered_map<const Stringpool_char*, Val, Stringpool_hash, + typedef Unordered_map<Hashkey, Hashval, Stringpool_hash, Stringpool_eq> String_set_type; -#endif - // Comparison routine used when sorting into a string table. We - // store string-sizes in the sort-vector so we don't have to - // recompute them log(n) times as we sort. - struct Stringpool_sort_info - { - typename String_set_type::iterator it; - size_t string_length; - Stringpool_sort_info(typename String_set_type::iterator i, size_t s) - : it(i), string_length(s) - { } - }; + // Comparison routine used when sorting into a string table. + + typedef typename String_set_type::iterator Stringpool_sort_info; struct Stringpool_sort_comparison { |