X-Git-Url: http://git.efficios.com/?a=blobdiff_plain;ds=sidebyside;f=gold%2Fstringpool.cc;h=b31029a0f645cf10dca089a052b0395e5f28f03c;hb=bda13cdcf0db4d9cee648bfa0bfc7f1a4415d2a7;hp=3d8bfe6cad9f2971ad490d90104b4b92f372c533;hpb=8383303e0acce6e4332e2a2097b832e2deb880ec;p=deliverable%2Fbinutils-gdb.git diff --git a/gold/stringpool.cc b/gold/stringpool.cc index 3d8bfe6cad..b31029a0f6 100644 --- a/gold/stringpool.cc +++ b/gold/stringpool.cc @@ -1,6 +1,6 @@ // stringpool.cc -- a string pool for gold -// Copyright 2006, 2007 Free Software Foundation, Inc. +// Copyright (C) 2006-2019 Free Software Foundation, Inc. // Written by Ian Lance Taylor . // This file is part of gold. @@ -34,10 +34,15 @@ namespace gold { template -Stringpool_template::Stringpool_template() - : string_set_(), strings_(), strtab_size_(0), next_index_(1), - next_uncopied_key_(-1), zero_null_(true) +Stringpool_template::Stringpool_template(uint64_t addralign) + : string_set_(), key_to_offset_(), strings_(), strtab_size_(0), + zero_null_(true), optimize_(false), offset_(sizeof(Stringpool_char)), + addralign_(addralign) { + if (parameters->options_valid() + && parameters->options().optimize() >= 2 + && addralign <= sizeof(Stringpool_char)) + this->optimize_ = true; } template @@ -49,6 +54,7 @@ Stringpool_template::clear() ++p) delete[] reinterpret_cast(*p); this->strings_.clear(); + this->key_to_offset_.clear(); this->string_set_.clear(); } @@ -67,7 +73,12 @@ template void Stringpool_template::reserve(unsigned int n) { -#if defined(HAVE_TR1_UNORDERED_MAP) + this->key_to_offset_.reserve(n); + +#if defined(HAVE_UNORDERED_MAP) + this->string_set_.rehash(this->string_set_.size() + n); + return; +#elif defined(HAVE_TR1_UNORDERED_MAP) // rehash() implementation is broken in gcc 4.0.3's stl //this->string_set_.rehash(this->string_set_.size() + n); //return; @@ -82,28 +93,6 @@ Stringpool_template::reserve(unsigned int n) this->string_set_.swap(new_string_set); } -// Return the length of a string of arbitrary character type. - -template -size_t -Stringpool_template::string_length(const Stringpool_char* p) -{ - size_t len = 0; - for (; *p != 0; ++p) - ++len; - return len; -} - -// Specialize string_length for char. Maybe we could just use -// std::char_traits<>::length? - -template<> -inline size_t -Stringpool_template::string_length(const char* p) -{ - return strlen(p); -} - // Compare two strings of arbitrary character type for equality. template @@ -136,8 +125,9 @@ Stringpool_template::Stringpool_eq::operator()( { return (h1.hash_code == h2.hash_code && h1.length == h2.length - && memcmp(h1.string, h2.string, - h1.length * sizeof(Stringpool_char)) == 0); + && (h1.string == h2.string + || memcmp(h1.string, h2.string, + h1.length * sizeof(Stringpool_char)) == 0)); } // Hash function. The length is in characters, not bytes. @@ -147,28 +137,7 @@ size_t Stringpool_template::string_hash(const Stringpool_char* s, size_t length) { - // Fowler/Noll/Vo (FNV) hash (type FNV-1a). - const unsigned char* p = reinterpret_cast(s); - if (sizeof(size_t) > 4) - { - size_t result = static_cast(14695981039346656037ULL); - for (size_t i = 0; i < length * sizeof(Stringpool_char); ++i) - { - result ^= static_cast(*p++); - result *= 1099511628211ULL; - } - return result; - } - else - { - size_t result = 2166136261UL; - for (size_t i = 0; i < length * sizeof(Stringpool_char); ++i) - { - result ^= static_cast(*p++); - result *= 16777619UL; - } - return result; - } + return gold::string_hash(s, length); } // Add the string S to the list of canonical strings. Return a @@ -179,8 +148,7 @@ Stringpool_template::string_hash(const Stringpool_char* s, template const Stringpool_char* Stringpool_template::add_string(const Stringpool_char* s, - size_t len, - Key* pkey) + size_t len) { // We are in trouble if we've already computed the string offsets. gold_assert(this->strtab_size_ == 0); @@ -207,7 +175,7 @@ Stringpool_template::add_string(const Stringpool_char* s, alc = sizeof(Stringdata) + buffer_size; else { - Stringdata *psd = this->strings_.front(); + Stringdata* psd = this->strings_.front(); if (len > psd->alc - psd->len) alc = sizeof(Stringdata) + buffer_size; else @@ -217,30 +185,18 @@ Stringpool_template::add_string(const Stringpool_char* s, memset(ret + len - sizeof(Stringpool_char), 0, sizeof(Stringpool_char)); - if (pkey != NULL) - *pkey = psd->index * key_mult + psd->len; - psd->len += len; return reinterpret_cast(ret); } } - Stringdata *psd = reinterpret_cast(new char[alc]); + Stringdata* psd = reinterpret_cast(new char[alc]); psd->alc = alc - sizeof(Stringdata); 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_; - - if (pkey != NULL) - { - *pkey = psd->index * key_mult; - // Ensure there was no overflow. - gold_assert(*pkey / key_mult == psd->index); - } if (front) this->strings_.push_front(psd); @@ -256,18 +212,47 @@ template const Stringpool_char* Stringpool_template::add(const Stringpool_char* s, bool copy, Key* pkey) +{ + return this->add_with_length(s, string_length(s), copy, pkey); +} + +// Add a new key offset entry. + +template +void +Stringpool_template::new_key_offset(size_t length) +{ + section_offset_type offset; + if (this->zero_null_ && length == 0) + offset = 0; + else + { + offset = this->offset_; + // Align strings. + offset = align_address(offset, this->addralign_); + this->offset_ = offset + (length + 1) * sizeof(Stringpool_char); + } + this->key_to_offset_.push_back(offset); +} + +template +const Stringpool_char* +Stringpool_template::add_with_length(const Stringpool_char* s, + size_t length, + bool copy, + Key* pkey) { typedef std::pair Insert_type; + // We add 1 so that 0 is always invalid. + const Key k = this->key_to_offset_.size() + 1; + if (!copy) { // When we don't need to copy the string, we can call insert // directly. - const Key k = this->next_uncopied_key_; - const section_offset_type ozero = 0; - std::pair element(Hashkey(s), - std::make_pair(k, ozero)); + std::pair element(Hashkey(s, length), k); Insert_type ins = this->string_set_.insert(element); @@ -277,53 +262,40 @@ Stringpool_template::add(const Stringpool_char* s, bool copy, { // We just added the string. The key value has now been // used. - --this->next_uncopied_key_; + this->new_key_offset(length); } else { - gold_assert(k != p->second.first); + gold_assert(k != p->second); } if (pkey != NULL) - *pkey = p->second.first; + *pkey = p->second; return p->first.string; } - return this->add_prefix(s, string_length(s), pkey); -} - -// Add a prefix of a string to a string pool. - -template -const Stringpool_char* -Stringpool_template::add_prefix(const Stringpool_char* s, - size_t len, - Key* pkey) -{ - // When adding an entry, this will look it up twice in the hash + // When we have to copy the string, we 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. + // code will only be computed once. - Hashkey hk(s, len); + Hashkey hk(s, length); 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; + *pkey = p->second; return p->first.string; } - Key k; - hk.string = this->add_string(s, len, &k); + this->new_key_offset(length); + + hk.string = this->add_string(s, length); // The contents of the string stay the same, so we don't need to // adjust hk.hash_code or hk.length. - const section_offset_type ozero = 0; - std::pair element(hk, std::make_pair(k, ozero)); + std::pair element(hk, k); - typedef std::pair Insert_type; Insert_type ins = this->string_set_.insert(element); gold_assert(ins.second); @@ -343,7 +315,7 @@ Stringpool_template::find(const Stringpool_char* s, return NULL; if (pkey != NULL) - *pkey = p->second.first; + *pkey = p->second; return p->first.string; } @@ -419,20 +391,10 @@ Stringpool_template::set_string_offsets() // the strtab size, and gives a relatively small benefit (it's // typically rare for a symbol to be a suffix of another), we only // take the time to sort when the user asks for heavy optimization. - if (parameters->optimization_level() < 2) + if (!this->optimize_) { - for (typename String_set_type::iterator curr = this->string_set_.begin(); - curr != this->string_set_.end(); - curr++) - { - if (this->zero_null_ && curr->first.string[0] == 0) - curr->second.second = 0; - else - { - curr->second.second = offset; - offset += (curr->first.length + 1) * charsize; - } - } + // If we are not optimizing, the offsets are already assigned. + offset = this->offset_; } else { @@ -448,27 +410,32 @@ Stringpool_template::set_string_offsets() std::sort(v.begin(), v.end(), Stringpool_sort_comparison()); + section_offset_type last_offset = -1; for (typename std::vector::iterator last = v.end(), curr = v.begin(); curr != v.end(); last = curr++) { + section_offset_type this_offset; if (this->zero_null_ && (*curr)->first.string[0] == 0) - (*curr)->second.second = 0; + this_offset = 0; else if (last != v.end() + && ((((*curr)->first.length - (*last)->first.length) + % this->addralign_) == 0) && 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)); + this_offset = (last_offset + + (((*last)->first.length - (*curr)->first.length) + * charsize)); else { - (*curr)->second.second = offset; - offset += ((*curr)->first.length + 1) * charsize; + this_offset = align_address(offset, this->addralign_); + offset = this_offset + ((*curr)->first.length + 1) * charsize; } + this->key_to_offset_[(*curr)->second - 1] = this_offset; + last_offset = this_offset; } } @@ -482,11 +449,21 @@ template section_offset_type Stringpool_template::get_offset(const Stringpool_char* s) const +{ + return this->get_offset_with_length(s, string_length(s)); +} + +template +section_offset_type +Stringpool_template::get_offset_with_length( + const Stringpool_char* s, + size_t length) const { gold_assert(this->strtab_size_ != 0); - typename String_set_type::const_iterator p = this->string_set_.find(s); + Hashkey hk(s, length); + typename String_set_type::const_iterator p = this->string_set_.find(hk); if (p != this->string_set_.end()) - return p->second.second; + return this->key_to_offset_[p->second - 1]; gold_unreachable(); } @@ -507,9 +484,10 @@ Stringpool_template::write_to_buffer( ++p) { const int len = (p->first.length + 1) * sizeof(Stringpool_char); - gold_assert(static_cast(p->second.second) + len + const section_offset_type offset = this->key_to_offset_[p->second - 1]; + gold_assert(static_cast(offset) + len <= this->strtab_size_); - memcpy(buffer + p->second.second, p->first.string, len); + memcpy(buffer + offset, p->first.string, len); } } @@ -531,7 +509,7 @@ template void Stringpool_template::print_stats(const char* name) const { -#if defined(HAVE_TR1_UNORDERED_MAP) || defined(HAVE_EXT_HASH_MAP) +#if defined(HAVE_UNORDERED_MAP) || defined(HAVE_TR1_UNORDERED_MAP) || defined(HAVE_EXT_HASH_MAP) fprintf(stderr, _("%s: %s entries: %zu; buckets: %zu\n"), program_name, name, this->string_set_.size(), this->string_set_.bucket_count());