gold/stringpool.h

   1 // stringpool.h -- a string pool for gold    -*- C++ -*-
   2
   3 #include <string>
   4 #include <list>
   5
   6 #ifndef GOLD_STRINGPOOL_H
   7 #define GOLD_STRINGPOOL_H
   8
   9 namespace gold
  10 {
  11
  12 class Output_file;
  13
  14 // A Stringpool is a pool of unique strings.  It provides the
  15 // following features:
  16
  17 // Every string in the pool is unique.  Thus, if you have two strings
  18 // in the Stringpool, you can compare them for equality by using
  19 // pointer comparison rather than string comparison.
  20
  21 // There is a key associated with every string in the pool.  If you
  22 // add strings to the Stringpool in the same order, then the key for
  23 // each string will always be the same for any run of the linker.
  24 // This is not true of the string pointers themselves, as they may
  25 // change due to address space randomization.  Some parts of the
  26 // linker (e.g., the symbol table) use the key value instead of the
  27 // string pointer so that repeated runs of the linker will generate
  28 // precisely the same output.
  29
  30 // A Stringpool can be turned into a string table, a sequential series
  31 // of null terminated strings.  The first string may optionally be a
  32 // single zero byte, as required for SHT_STRTAB sections.  This
  33 // conversion is only permitted after all strings have been added to
  34 // the Stringpool.  After doing this conversion, you can ask for the
  35 // offset of any string in the stringpool in the string table, and you
  36 // can write the resulting string table to an output file.
  37
  38 // When a Stringpool is turned into a string table, then as an
  39 // optimization it will reuse string suffixes to avoid duplicating
  40 // strings.  That is, given the strings "abc" and "bc", only the
  41 // string "abc" will be stored, and "bc" will be represented by an
  42 // offset into the middle of the string "abc".
  43
  44 // Stringpools are implemented in terms of Stringpool_template, which
  45 // is generalized on the type of character used for the strings.  Most
  46 // uses will want the Stringpool type which uses char.  Other cases
  47 // are used for merging wide string constants.
  48
  49 template<typename Stringpool_char>
  50 class Stringpool_template
  51 {
  52  public:
  53   // The type of a key into the stringpool.  As described above, a key
  54   // value will always be the same during any run of the linker.  Zero
  55   // is never a valid key value.
  56   typedef size_t Key;
  57
  58   // Create a Stringpool.  ZERO_NULL is true if we should reserve
  59   // offset 0 to hold the empty string when converting the stringpool
  60   // to a string table.  ZERO_NULL should be true if you want a proper
  61   // ELF SHT_STRTAB section.
  62   Stringpool_template(bool zero_null = true);
  63
  64   ~Stringpool_template();
  65
  66   // Add the string S to the pool.  This returns a canonical permanent
  67   // pointer to the string in the pool.  If PKEY is not NULL, this
  68   // sets *PKEY to the key for the string.
  69   const Stringpool_char*
  70   add(const Stringpool_char* s, Key* pkey);
  71
  72   // Add the string S to the pool.
  73   const Stringpool_char*
  74   add(const std::basic_string<Stringpool_char>& s, Key* pkey)
  75   { return this->add(s.c_str(), pkey); }
  76
  77   // Add the prefix of length LEN of string S to the pool.
  78   const Stringpool_char*
  79   add(const Stringpool_char* s, size_t len, Key* pkey);
  80
  81   // If the string S is present in the pool, return the canonical
  82   // string pointer.  Otherwise, return NULL.  If PKEY is not NULL,
  83   // set *PKEY to the key.
  84   const Stringpool_char*
  85   find(const Stringpool_char* s, Key* pkey) const;
  86
  87   // Turn the stringpool into a string table: determine the offsets of
  88   // all the strings.  After this is called, no more strings may be
  89   // added to the stringpool.
  90   void
  91   set_string_offsets();
  92
  93   // Get the offset of the string S in the string table.  This returns
  94   // the offset in bytes, not in units of Stringpool_char.  This may
  95   // only be called after set_string_offsets has been called.
  96   off_t
  97   get_offset(const Stringpool_char* s) const;
  98
  99   // Get the offset of the string S in the string table.
 100   off_t
 101   get_offset(const std::basic_string<Stringpool_char>& s) const
 102   { return this->get_offset(s.c_str()); }
 103
 104   // Get the size of the string table.  This returns the number of
 105   // bytes, not in units of Stringpool_char.
 106   off_t
 107   get_strtab_size() const
 108   {
 109     gold_assert(this->strtab_size_ != 0);
 110     return this->strtab_size_;
 111   }
 112
 113   // Write the string table into the output file at the specified
 114   // offset.
 115   void
 116   write(Output_file*, off_t offset);
 117
 118  private:
 119   Stringpool_template(const Stringpool_template&);
 120   Stringpool_template& operator=(const Stringpool_template&);
 121
 122   // Return the length of a string in units of Stringpool_char.
 123   static size_t
 124   string_length(const Stringpool_char*);
 125
 126   // We store the actual data in a list of these buffers.
 127   struct Stringdata
 128   {
 129     // Length of data in buffer.
 130     size_t len;
 131     // Allocated size of buffer.
 132     size_t alc;
 133     // Buffer index.
 134     unsigned int index;
 135     // Buffer.
 136     char data[1];
 137   };
 138
 139   // Copy a string into the buffers, returning a canonical string.
 140   const Stringpool_char*
 141   add_string(const Stringpool_char*, Key*);
 142
 143   // Hash function.
 144   struct Stringpool_hash
 145   {
 146     size_t
 147     operator()(const Stringpool_char*) const;
 148   };
 149
 150   // Equality comparison function for hash table.
 151   struct Stringpool_eq
 152   {
 153     bool
 154     operator()(const Stringpool_char* p1, const Stringpool_char* p2) const;
 155   };
 156
 157   // Return whether s1 is a suffix of s2.
 158   static bool
 159   is_suffix(const Stringpool_char* s1, size_t len1,
 160             const Stringpool_char* s2, size_t len2);
 161
 162   // The hash table is a map from string names to a pair of Key and
 163   // string table offsets.  We only use the offsets if we turn this
 164   // into an string table section.
 165
 166   typedef std::pair<Key, off_t> Val;
 167
 168 #ifdef HAVE_TR1_UNORDERED_SET
 169   typedef Unordered_map<const Stringpool_char*, Val, Stringpool_hash,
 170                         Stringpool_eq,
 171                         std::allocator<std::pair<const Stringpool_char* const,
 172                                                  Val> >,
 173                         true> String_set_type;
 174 #else
 175   typedef Unordered_map<const Stringpool_char*, Val, Stringpool_hash,
 176                         Stringpool_eq> String_set_type;
 177 #endif
 178
 179   // Comparison routine used when sorting into a string table.  We
 180   // store string-sizes in the sort-vector so we don't have to
 181   // recompute them log(n) times as we sort.
 182   struct Stringpool_sort_info
 183   {
 184     typename String_set_type::iterator it;
 185     size_t string_length;
 186     Stringpool_sort_info(typename String_set_type::iterator i, size_t s)
 187       : it(i), string_length(s)
 188     { }
 189   };
 190
 191   struct Stringpool_sort_comparison
 192   {
 193     bool
 194     operator()(const Stringpool_sort_info&, const Stringpool_sort_info&) const;
 195   };
 196
 197   // List of Stringdata structures.
 198   typedef std::list<Stringdata*> Stringdata_list;
 199
 200   // Mapping from const char* to namepool entry.
 201   String_set_type string_set_;
 202   // List of buffers.
 203   Stringdata_list strings_;
 204   // Size of string table.
 205   off_t strtab_size_;
 206   // Next Stringdata index.
 207   unsigned int next_index_;
 208   // Whether to reserve offset 0 to hold the null string.
 209   bool zero_null_;
 210 };
 211
 212 // The most common type of Stringpool.
 213 typedef Stringpool_template<char> Stringpool;
 214
 215 } // End namespace gold.
 216
 217 #endif // !defined(GOLD_STRINGPOOL_H)