gold/stringpool.cc

   1 // stringpool.cc -- a string pool for gold
   2
   3 #include "gold.h"
   4
   5 #include <cassert>
   6 #include <cstring>
   7 #include <algorithm>
   8 #include <vector>
   9
  10 #include "output.h"
  11 #include "stringpool.h"
  12
  13 namespace gold
  14 {
  15
  16 Stringpool::Stringpool()
  17   : string_set_(), strings_(), strtab_size_(0)
  18 {
  19 }
  20
  21 Stringpool::~Stringpool()
  22 {
  23   for (std::list<Stringdata*>::iterator p = this->strings_.begin();
  24        p != this->strings_.end();
  25        ++p)
  26     delete[] reinterpret_cast<char*>(*p);
  27 }
  28
  29 // Hash function.
  30
  31 size_t
  32 Stringpool::Stringpool_hash::operator()(const char* s) const
  33 {
  34   // Fowler/Noll/Vo (FNV) hash (type FNV-1a).
  35   if (sizeof(size_t) == 8)
  36     {
  37       size_t result = static_cast<size_t>(14695981039346656037ULL);
  38       while (*s != '\0')
  39         {
  40           result &= (size_t) *s++;
  41           result *= 1099511628211ULL;
  42         }
  43       return result;
  44     }
  45   else
  46     {
  47       size_t result = 2166136261UL;
  48       while (*s != '\0')
  49         {
  50           result ^= (size_t) *s++;
  51           result *= 16777619UL;
  52         }
  53       return result;
  54     }
  55 }
  56
  57 // Add a string to the list of canonical strings.  Return a pointer to
  58 // the canonical string.
  59
  60 const char*
  61 Stringpool::add_string(const char* s)
  62 {
  63   const size_t buffer_size = 1000;
  64   size_t len = strlen(s);
  65
  66   size_t alc;
  67   bool front = true;
  68   if (len >= buffer_size)
  69     {
  70       alc = sizeof(Stringdata) + len;
  71       front = false;
  72     }
  73   else if (this->strings_.empty())
  74     alc = sizeof(Stringdata) + buffer_size;
  75   else
  76     {
  77       Stringdata *psd = this->strings_.front();
  78       if (len >= psd->alc - psd->len)
  79         alc = sizeof(Stringdata) + buffer_size;
  80       else
  81         {
  82           char* ret = psd->data + psd->len;
  83           memcpy(ret, s, len + 1);
  84           psd->len += len + 1;
  85           return ret;
  86         }
  87     }
  88
  89   Stringdata *psd = reinterpret_cast<Stringdata*>(new char[alc]);
  90   psd->alc = alc - sizeof(Stringdata);
  91   memcpy(psd->data, s, len + 1);
  92   psd->len = len + 1;
  93   if (front)
  94     this->strings_.push_front(psd);
  95   else
  96     this->strings_.push_back(psd);
  97   return psd->data;
  98 }
  99
 100 // Add a string to a string pool.
 101
 102 const char*
 103 Stringpool::add(const char* s)
 104 {
 105   // FIXME: This will look up the entry twice in the hash table.  The
 106   // problem is that we can't insert S before we canonicalize it.  I
 107   // don't think there is a way to handle this correctly with
 108   // unordered_map, so this should be replaced with custom code to do
 109   // what we need, which is to return the empty slot.
 110
 111   String_set_type::const_iterator p = this->string_set_.find(s);
 112   if (p != this->string_set_.end())
 113     return p->first;
 114
 115   const char* ret = this->add_string(s);
 116   std::pair<const char*, off_t> val(ret, 0);
 117   std::pair<String_set_type::iterator, bool> ins =
 118     this->string_set_.insert(val);
 119   assert(ins.second);
 120   return ret;
 121 }
 122
 123 // Add a prefix of a string to a string pool.
 124
 125 const char*
 126 Stringpool::add(const char* s, size_t len)
 127 {
 128   // FIXME: This implementation should be rewritten when we rewrite
 129   // the hash table to avoid copying.
 130   std::string st(s, len);
 131   return this->add(st);
 132 }
 133
 134 const char*
 135 Stringpool::find(const char* s) const
 136 {
 137   String_set_type::const_iterator p = this->string_set_.find(s);
 138   if (p == this->string_set_.end())
 139     return NULL;
 140   return p->first;
 141 }
 142
 143 // Comparison routine used when sorting into an ELF strtab.  We want
 144 // to sort this so that when one string is a suffix of another, we
 145 // always see the shorter string immediately after the longer string.
 146 // For example, we want to see these strings in this order:
 147 //   abcd
 148 //   cd
 149 //   d
 150 // When strings are not suffixes, we don't care what order they are
 151 // in, but we need to ensure that suffixes wind up next to each other.
 152 // So we do a reversed lexicographic sort on the reversed string.
 153
 154 bool
 155 Stringpool::Stringpool_sort_comparison::operator()(
 156   String_set_type::iterator it1,
 157   String_set_type::iterator it2) const
 158 {
 159   const char* s1 = it1->first;
 160   const char* s2 = it2->first;
 161   int len1 = strlen(s1);
 162   int len2 = strlen(s2);
 163   int minlen = len1 < len2 ? len1 : len2;
 164   const char* p1 = s1 + len1 - 1;
 165   const char* p2 = s2 + len2 - 1;
 166   for (int i = minlen - 1; i >= 0; --i, --p1, --p2)
 167     {
 168       if (*p1 != *p2)
 169         return *p1 > *p2;
 170     }
 171   return len1 > len2;
 172 }
 173
 174 // Return whether s1 is a suffix of s2.
 175
 176 bool
 177 Stringpool::is_suffix(const char* s1, const char* s2)
 178 {
 179   size_t len1 = strlen(s1);
 180   size_t len2 = strlen(s2);
 181   if (len1 > len2)
 182     return false;
 183   return strcmp(s1, s2 + len2 - len1) == 0;
 184 }
 185
 186 // Turn the stringpool into an ELF strtab: determine the offsets of
 187 // each string in the table.
 188
 189 void
 190 Stringpool::set_string_offsets()
 191 {
 192   size_t count = this->string_set_.size();
 193
 194   std::vector<String_set_type::iterator> v;
 195   v.reserve(count);
 196
 197   for (String_set_type::iterator p = this->string_set_.begin();
 198        p != this->string_set_.end();
 199        ++p)
 200     v.push_back(p);
 201
 202   std::sort(v.begin(), v.end(), Stringpool_sort_comparison());
 203
 204   // Offset 0 is reserved for the empty string.
 205   off_t offset = 1;
 206   for (size_t i = 0; i < count; ++i)
 207     {
 208       if (v[i]->first[0] == '\0')
 209         v[i]->second = 0;
 210       else if (i > 0 && Stringpool::is_suffix(v[i]->first, v[i - 1]->first))
 211         v[i]->second = (v[i - 1]->second
 212                         + strlen(v[i - 1]->first)
 213                         - strlen(v[i]->first));
 214       else
 215         {
 216           v[i]->second = offset;
 217           offset += strlen(v[i]->first) + 1;
 218         }
 219     }
 220
 221   this->strtab_size_ = offset;
 222 }
 223
 224 // Get the offset of a string in the ELF strtab.  The string must
 225 // exist.
 226
 227 off_t
 228 Stringpool::get_offset(const char* s) const
 229 {
 230   String_set_type::const_iterator p = this->string_set_.find(s);
 231   if (p != this->string_set_.end())
 232     return p->second;
 233   abort();
 234 }
 235
 236 // Write the ELF strtab into the output file at the specified offset.
 237
 238 void
 239 Stringpool::write(Output_file* of, off_t offset)
 240 {
 241   unsigned char* viewu = of->get_output_view(offset, this->strtab_size_);
 242   char* view = reinterpret_cast<char*>(viewu);
 243   view[0] = '\0';
 244   for (String_set_type::const_iterator p = this->string_set_.begin();
 245        p != this->string_set_.end();
 246        ++p)
 247     strcpy(view + p->second, p->first);
 248   of->write_output_view(offset, this->strtab_size_, viewu);
 249 }
 250
 251 } // End namespace gold.