X-Git-Url: http://drtracing.org/?a=blobdiff_plain;f=gold%2Fstringpool.h;h=9217b17910fc8f4e9bc45be0bfaabfe8f2ede880;hb=fe7d6a8db01f2a71520578267df7cd2d780ececb;hp=0da7921234b42ff84553d2bde415f261598aab14;hpb=8383303e0acce6e4332e2a2097b832e2deb880ec;p=deliverable%2Fbinutils-gdb.git diff --git a/gold/stringpool.h b/gold/stringpool.h index 0da7921234..9217b17910 100644 --- a/gold/stringpool.h +++ b/gold/stringpool.h @@ -1,6 +1,6 @@ // stringpool.h -- a string pool for gold -*- C++ -*- -// Copyright 2006, 2007 Free Software Foundation, Inc. +// Copyright (C) 2006-2020 Free Software Foundation, Inc. // Written by Ian Lance Taylor . // This file is part of gold. @@ -22,6 +22,7 @@ #include #include +#include #ifndef GOLD_STRINGPOOL_H #define GOLD_STRINGPOOL_H @@ -31,6 +32,28 @@ namespace gold class Output_file; +// Return the length of a string in units of Char_type. + +template +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: @@ -56,8 +79,9 @@ class Output_file; // 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 in the stringpool in the string table, and you -// can write the resulting string table to an output file. +// 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 @@ -65,6 +89,82 @@ class Output_file; // 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 +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_ causes 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_vector; + typedef std::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 @@ -80,7 +180,7 @@ class Stringpool_template typedef size_t Key; // Create a Stringpool. - Stringpool_template(); + Stringpool_template(uint64_t addralign = 1); ~Stringpool_template(); @@ -99,7 +199,18 @@ class Stringpool_template // should not be called for a proper ELF SHT_STRTAB section. void set_no_zero_null() - { this->zero_null_ = false; } + { + gold_assert(this->string_set_.empty() + && this->offset_ == sizeof(Stringpool_char)); + this->zero_null_ = false; + this->offset_ = 0; + } + + // Indicate that this string pool should be optimized, even if not + // running with -O2. + void + set_optimize() + { this->optimize_ = true; } // Add the string S to the pool. This returns a canonical permanent // pointer to the string in the pool. If COPY is true, the string @@ -108,9 +219,15 @@ class Stringpool_template const Stringpool_char* add(const Stringpool_char* s, bool copy, Key* pkey); - // Add the prefix of length LEN of string S to the pool. + // Add the string S to the pool. + const Stringpool_char* + add(const std::basic_string& s, bool copy, Key* pkey) + { return this->add_with_length(s.data(), s.size(), copy, pkey); } + + // Add string S of length LEN characters to the pool. If COPY is + // true, S need not be null terminated. const Stringpool_char* - add_prefix(const Stringpool_char* s, size_t len, Key* pkey); + add_with_length(const Stringpool_char* s, size_t len, bool copy, Key* pkey); // If the string S is present in the pool, return the canonical // string pointer. Otherwise, return NULL. If PKEY is not NULL, @@ -133,7 +250,20 @@ class Stringpool_template // Get the offset of the string S in the string table. section_offset_type get_offset(const std::basic_string& s) const - { return this->get_offset(s.c_str()); } + { return this->get_offset_with_length(s.c_str(), s.size()); } + + // Get the offset of string S, with length LENGTH characters, in the + // string table. + section_offset_type + get_offset_with_length(const Stringpool_char* s, size_t length) const; + + // Get the offset of the string with key K. + section_offset_type + get_offset_from_key(Key k) const + { + gold_assert(k <= this->key_to_offset_.size()); + return this->key_to_offset_[k - 1]; + } // Get the size of the string table. This returns the number of // bytes, not in units of Stringpool_char. @@ -163,10 +293,6 @@ class Stringpool_template Stringpool_template(const Stringpool_template&); Stringpool_template& operator=(const Stringpool_template&); - // Return the length of a string in units of Stringpool_char. - static size_t - string_length(const Stringpool_char*); - // Return whether two strings are equal. static bool string_equal(const Stringpool_char*, const Stringpool_char*); @@ -183,15 +309,17 @@ class Stringpool_template size_t len; // Allocated size of buffer. size_t alc; - // Buffer index. - unsigned int index; // Buffer. char data[1]; }; + // Add a new key offset entry. + void + new_key_offset(size_t); + // Copy a string into the buffers, returning a canonical string. const Stringpool_char* - add_string(const Stringpool_char*, size_t, Key*); + add_string(const Stringpool_char*, size_t); // Return whether s1 is a suffix of s2. static bool @@ -218,7 +346,7 @@ class Stringpool_template // Note that these constructors are relatively expensive, because // they compute the hash code. - Hashkey(const Stringpool_char* s) + explicit Hashkey(const Stringpool_char* s) : string(s), length(string_length(s)), hash_code(string_hash(s, length)) { } @@ -243,11 +371,9 @@ class Stringpool_template operator()(const Hashkey&, const Hashkey&) const; }; - // 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. + // The hash table is a map from strings to Keys. - typedef std::pair Hashval; + typedef Key Hashval; typedef Unordered_map String_set_type; @@ -262,21 +388,29 @@ class Stringpool_template operator()(const Stringpool_sort_info&, const Stringpool_sort_info&) const; }; + // Keys map to offsets via a Chunked_vector. We only use the + // offsets if we turn this into an string table section. + typedef Chunked_vector Key_to_offset; + // List of Stringdata structures. typedef std::list Stringdata_list; // Mapping from const char* to namepool entry. String_set_type string_set_; + // Mapping from Key to string table offset. + Key_to_offset key_to_offset_; // List of buffers. Stringdata_list strings_; // Size of string table. section_size_type strtab_size_; - // Next Stringdata index. - unsigned int next_index_; - // Next key value for a string we don't copy. - int next_uncopied_key_; // Whether to reserve offset 0 to hold the null string. bool zero_null_; + // Whether to optimize the string table. + bool optimize_; + // offset of the next string. + section_offset_type offset_; + // The alignment of strings in the stringpool. + uint64_t addralign_; }; // The most common type of Stringpool.