+ // 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.
+
+ 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;
+ return p->first.string;
+ }
+
+ 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.
+
+ std::pair<Hashkey, Hashval> element(hk, k);
+
+ Insert_type ins = this->string_set_.insert(element);
+ gold_assert(ins.second);
+
+ if (pkey != NULL)
+ *pkey = k;
+ return hk.string;
+}
+
+template<typename Stringpool_char>
+const Stringpool_char*
+Stringpool_template<Stringpool_char>::find(const Stringpool_char* s,
+ Key* pkey) const
+{
+ 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;
+
+ return p->first.string;
+}
+
+// Comparison routine used when sorting into an ELF strtab. We want
+// to sort this so that when one string is a suffix of another, we
+// always see the shorter string immediately after the longer string.
+// For example, we want to see these strings in this order:
+// abcd
+// cd
+// d
+// When strings are not suffixes, we don't care what order they are
+// in, but we need to ensure that suffixes wind up next to each other.
+// So we do a reversed lexicographic sort on the reversed string.
+
+template<typename Stringpool_char>
+bool
+Stringpool_template<Stringpool_char>::Stringpool_sort_comparison::operator()(
+ const Stringpool_sort_info& sort_info1,
+ const Stringpool_sort_info& sort_info2) const
+{
+ 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;
+ for (size_t i = minlen; i > 0; --i, --p1, --p2)
+ {
+ if (*p1 != *p2)
+ return *p1 > *p2;
+ }
+ return len1 > len2;
+}
+
+// Return whether s1 is a suffix of s2.
+
+template<typename Stringpool_char>
+bool
+Stringpool_template<Stringpool_char>::is_suffix(const Stringpool_char* s1,
+ size_t len1,
+ const Stringpool_char* s2,
+ size_t len2)
+{
+ if (len1 > len2)
+ return false;
+ return memcmp(s1, s2 + len2 - len1, len1 * sizeof(Stringpool_char)) == 0;
+}
+
+// Turn the stringpool into an ELF strtab: determine the offsets of
+// each string in the table.
+
+template<typename Stringpool_char>
+void
+Stringpool_template<Stringpool_char>::set_string_offsets()
+{
+ if (this->strtab_size_ != 0)
+ {
+ // We've already computed the offsets.
+ return;
+ }
+
+ const size_t charsize = sizeof(Stringpool_char);
+
+ // Offset 0 may be reserved for the empty string.
+ section_offset_type offset = this->zero_null_ ? charsize : 0;
+
+ // Sorting to find suffixes can take over 25% of the total CPU time
+ // used by the linker. Since it's merely an optimization to reduce
+ // 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 (!this->optimize_)
+ {
+ // If we are not optimizing, the offsets are already assigned.
+ offset = this->offset_;
+ }
+ else
+ {
+ size_t count = this->string_set_.size();
+
+ std::vector<Stringpool_sort_info> v;
+ v.reserve(count);
+
+ for (typename String_set_type::iterator p = this->string_set_.begin();
+ p != this->string_set_.end();
+ ++p)
+ v.push_back(Stringpool_sort_info(p));
+
+ std::sort(v.begin(), v.end(), Stringpool_sort_comparison());
+
+ section_offset_type last_offset = -1;
+ for (typename std::vector<Stringpool_sort_info>::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)
+ 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))
+ this_offset = (last_offset
+ + (((*last)->first.length - (*curr)->first.length)
+ * charsize));
+ else
+ {
+ 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;
+ }
+ }
+
+ this->strtab_size_ = offset;
+}
+
+// Get the offset of a string in the ELF strtab. The string must
+// exist.
+
+template<typename Stringpool_char>
+section_offset_type
+Stringpool_template<Stringpool_char>::get_offset(const Stringpool_char* s)
+ const
+{
+ return this->get_offset_with_length(s, string_length(s));
+}
+
+template<typename Stringpool_char>
+section_offset_type
+Stringpool_template<Stringpool_char>::get_offset_with_length(
+ const Stringpool_char* s,
+ size_t length) const
+{
+ gold_assert(this->strtab_size_ != 0);
+ Hashkey hk(s, length);
+ typename String_set_type::const_iterator p = this->string_set_.find(hk);