+// Return the length of a string in units of Char_type.
+
+template<typename Char_type>
+inline size_t
+string_length(const Char_type* 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
+string_length(const char* p)
+{
+ return strlen(p);
+}
+
+// A Stringpool is a pool of unique strings. It provides the
+// following features:
+
+// Every string in the pool is unique. Thus, if you have two strings
+// in the Stringpool, you can compare them for equality by using
+// pointer comparison rather than string comparison.
+
+// There is a key associated with every string in the pool. If you
+// add strings to the Stringpool in the same order, then the key for
+// each string will always be the same for any run of the linker.
+// This is not true of the string pointers themselves, as they may
+// change due to address space randomization. Some parts of the
+// linker (e.g., the symbol table) use the key value instead of the
+// string pointer so that repeated runs of the linker will generate
+// precisely the same output.
+
+// When you add a string to a Stringpool, Stringpool will optionally
+// make a copy of it. Thus there is no requirement to keep a copy
+// elsewhere.
+
+// A Stringpool can be turned into a string table, a sequential series
+// of null terminated strings. The first string may optionally be a
+// single zero byte, as required for SHT_STRTAB sections. This
+// conversion is only permitted after all strings have been added to
+// the Stringpool. After doing this conversion, you can ask for the
+// offset of any string (or any key) in the stringpool in the string
+// table, and you can write the resulting string table to an output
+// file.
+
+// When a Stringpool is turned into a string table, then as an
+// optimization it will reuse string suffixes to avoid duplicating
+// strings. That is, given the strings "abc" and "bc", only the
+// string "abc" will be stored, and "bc" will be represented by an
+// offset into the middle of the string "abc".
+
+
+// A simple chunked vector class--this is a subset of std::vector
+// which stores memory in chunks. We don't provide iterators, because
+// we don't need them.
+
+template<typename Element>
+class Chunked_vector
+{
+ public:
+ Chunked_vector()
+ : chunks_(), size_(0)
+ { }
+
+ // Clear the elements.
+ void
+ clear()
+ {
+ this->chunks_.clear();
+ this->size_ = 0;
+ }
+
+ // Reserve elements.
+ void
+ reserve(unsigned int n)
+ {
+ if (n > this->chunks_.size() * chunk_size)
+ {
+ this->chunks_.resize((n + chunk_size - 1) / chunk_size);
+ // We need to call reserve() of all chunks since changing
+ // this->chunks_ casues Element_vectors to be copied. The
+ // reserved capacity of an Element_vector may be lost in copying.
+ for (size_t i = 0; i < this->chunks_.size(); ++i)
+ this->chunks_[i].reserve(chunk_size);
+ }
+ }
+
+ // Get the number of elements.
+ size_t
+ size() const
+ { return this->size_; }
+
+ // Push a new element on the back of the vector.
+ void
+ push_back(const Element& element)
+ {
+ size_t chunk_index = this->size_ / chunk_size;
+ if (chunk_index >= this->chunks_.size())
+ {
+ this->chunks_.push_back(Element_vector());
+ this->chunks_.back().reserve(chunk_size);
+ gold_assert(chunk_index < this->chunks_.size());
+ }
+ this->chunks_[chunk_index].push_back(element);
+ this->size_++;
+ }
+
+ // Return a reference to an entry in the vector.
+ Element&
+ operator[](size_t i)
+ { return this->chunks_[i / chunk_size][i % chunk_size]; }
+
+ const Element&
+ operator[](size_t i) const
+ { return this->chunks_[i / chunk_size][i % chunk_size]; }
+
+ private:
+ static const unsigned int chunk_size = 8192;
+
+ typedef std::vector<Element> Element_vector;
+ typedef std::vector<Element_vector> Chunk_vector;
+
+ Chunk_vector chunks_;
+ size_t size_;
+};
+
+
+// Stringpools are implemented in terms of Stringpool_template, which
+// is generalized on the type of character used for the strings. Most
+// uses will want the Stringpool type which uses char. Other cases
+// are used for merging wide string constants.
+