gold/stringpool.h

   1 // stringpool.h -- a string pool for gold    -*- C++ -*-
   2
   3 #include <string>
   4 #include <list>
   5
   6 // Stringpool
   7 //   Manage a pool of unique strings.
   8
   9 #ifndef GOLD_STRINGPOOL_H
  10 #define GOLD_STRINGPOOL_H
  11
  12 namespace gold
  13 {
  14
  15 class Output_file;
  16
  17 template<typename Stringpool_char>
  18 class Stringpool_template
  19 {
  20  public:
  21   // The type of a key into the stringpool.  A key value will always
  22   // be the same during any run of the linker.  The string pointers
  23   // may change when using address space randomization.  We use key
  24   // values in order to get repeatable runs when the value is inserted
  25   // into an unordered hash table.  Zero is never a valid key.
  26   typedef size_t Key;
  27
  28   // Create a Stringpool.  ZERO_NULL is true if we should reserve
  29   // offset 0 to hold the empty string.
  30   Stringpool_template(bool zero_null = true);
  31
  32   ~Stringpool_template();
  33
  34   // Add a string to the pool.  This returns a canonical permanent
  35   // pointer to the string.  If PKEY is not NULL, this sets *PKEY to
  36   // the key for the string.
  37   const Stringpool_char*
  38   add(const Stringpool_char*, Key* pkey);
  39
  40   const Stringpool_char*
  41   add(const std::basic_string<Stringpool_char>& s, Key* pkey)
  42   { return this->add(s.c_str(), pkey); }
  43
  44   // Add the prefix of a string to the pool.
  45   const Stringpool_char*
  46   add(const Stringpool_char*, size_t, Key* pkey);
  47
  48   // If a string is present, return the canonical string.  Otherwise,
  49   // return NULL.  If PKEY is not NULL, set *PKEY to the key.
  50   const Stringpool_char*
  51   find(const Stringpool_char*, Key* pkey) const;
  52
  53   // Turn the stringpool into an ELF strtab: determine the offsets of
  54   // all the strings.
  55   void
  56   set_string_offsets();
  57
  58   // Get the offset of a string in an ELF strtab.  This returns the
  59   // offset in bytes, not characters.
  60   off_t
  61   get_offset(const Stringpool_char*) const;
  62
  63   off_t
  64   get_offset(const std::basic_string<Stringpool_char>& s) const
  65   { return this->get_offset(s.c_str()); }
  66
  67   // Get the size of the ELF strtab.  This returns the number of
  68   // bytes, not characters.
  69   off_t
  70   get_strtab_size() const
  71   {
  72     gold_assert(this->strtab_size_ != 0);
  73     return this->strtab_size_;
  74   }
  75
  76   // Write the strtab into the output file at the specified offset.
  77   void
  78   write(Output_file*, off_t offset);
  79
  80  private:
  81   Stringpool_template(const Stringpool_template&);
  82   Stringpool_template& operator=(const Stringpool_template&);
  83
  84   // Return the length of a string.
  85   static size_t
  86   string_length(const Stringpool_char*);
  87
  88   // We store the actual data in a list of these buffers.
  89   struct Stringdata
  90   {
  91     // Length of data in buffer.
  92     size_t len;
  93     // Allocated size of buffer.
  94     size_t alc;
  95     // Buffer index.
  96     unsigned int index;
  97     // Buffer.
  98     char data[1];
  99   };
 100
 101   // Copy a string into the buffers, returning a canonical string.
 102   const Stringpool_char*
 103   add_string(const Stringpool_char*, Key*);
 104
 105   struct Stringpool_hash
 106   {
 107     size_t
 108     operator()(const Stringpool_char*) const;
 109   };
 110
 111   struct Stringpool_eq
 112   {
 113     bool
 114     operator()(const Stringpool_char* p1, const Stringpool_char* p2) const;
 115   };
 116
 117   // Return whether s1 is a suffix of s2.
 118   static bool
 119   is_suffix(const Stringpool_char* s1, size_t len1,
 120             const Stringpool_char* s2, size_t len2);
 121
 122   // The hash table is a map from string names to a pair of Key and
 123   // ELF strtab offsets.  We only use the offsets if we turn this into
 124   // an ELF strtab section.
 125
 126   typedef std::pair<Key, off_t> Val;
 127
 128 #ifdef HAVE_TR1_UNORDERED_SET
 129   typedef Unordered_map<const Stringpool_char*, Val, Stringpool_hash,
 130                         Stringpool_eq,
 131                         std::allocator<std::pair<const Stringpool_char* const,
 132                                                  Val> >,
 133                         true> String_set_type;
 134 #else
 135   typedef Unordered_map<const Stringpool_char*, Val, Stringpool_hash,
 136                         Stringpool_eq> String_set_type;
 137 #endif
 138
 139   // Comparison routine used when sorting into an ELF strtab.  We
 140   // store string-sizes in the sort-vector so we don't have to
 141   // recompute them log(n) times as we sort.
 142   struct Stringpool_sort_info
 143   {
 144     typename String_set_type::iterator it;
 145     size_t string_length;
 146     Stringpool_sort_info(typename String_set_type::iterator i, size_t s)
 147       : it(i), string_length(s)
 148     { }
 149   };
 150
 151   struct Stringpool_sort_comparison
 152   {
 153     bool
 154     operator()(const Stringpool_sort_info&, const Stringpool_sort_info&) const;
 155   };
 156
 157   // List of Stringdata structures.
 158   typedef std::list<Stringdata*> Stringdata_list;
 159
 160   // Mapping from const char* to namepool entry.
 161   String_set_type string_set_;
 162   // List of buffers.
 163   Stringdata_list strings_;
 164   // Size of ELF strtab.
 165   off_t strtab_size_;
 166   // Next Stringdata index.
 167   unsigned int next_index_;
 168   // Whether to reserve offset 0 to hold the null string.
 169   bool zero_null_;
 170 };
 171
 172 // The most common type of Stringpool.
 173 typedef Stringpool_template<char> Stringpool;
 174
 175 } // End namespace gold.
 176
 177 #endif // !defined(GOLD_STRINGPOOL_H)