gold/stringpool.cc

   1 // stringpool.cc -- a string pool for gold
   2
   3 #include "gold.h"
   4
   5 #include <cstring>
   6 #include <algorithm>
   7 #include <vector>
   8
   9 #include "output.h"
  10 #include "stringpool.h"
  11
  12 namespace gold
  13 {
  14
  15 template<typename Stringpool_char>
  16 Stringpool_template<Stringpool_char>::Stringpool_template()
  17   : string_set_(), strings_(), strtab_size_(0), next_index_(1),
  18     zero_null_(true)
  19 {
  20 }
  21
  22 template<typename Stringpool_char>
  23 Stringpool_template<Stringpool_char>::~Stringpool_template()
  24 {
  25   for (typename std::list<Stringdata*>::iterator p = this->strings_.begin();
  26        p != this->strings_.end();
  27        ++p)
  28     delete[] reinterpret_cast<char*>(*p);
  29 }
  30
  31 // Return the length of a string of arbitrary character type.
  32
  33 template<typename Stringpool_char>
  34 size_t
  35 Stringpool_template<Stringpool_char>::string_length(const Stringpool_char* p)
  36 {
  37   size_t len = 0;
  38   for (; *p != 0; ++p)
  39     ++len;
  40   return len;
  41 }
  42
  43 // Specialize string_length for char.  Maybe we could just use
  44 // std::char_traits<>::length?
  45
  46 template<>
  47 inline size_t
  48 Stringpool_template<char>::string_length(const char* p)
  49 {
  50   return strlen(p);
  51 }
  52
  53 // Equality comparison function.
  54
  55 template<typename Stringpool_char>
  56 bool
  57 Stringpool_template<Stringpool_char>::Stringpool_eq::operator()(
  58     const Stringpool_char* s1,
  59     const Stringpool_char* s2) const
  60 {
  61   while (*s1 != 0)
  62     if (*s1++ != *s2++)
  63       return false;
  64   return *s2 == 0;
  65 }
  66
  67 // Specialize equality comparison for char.
  68
  69 template<>
  70 bool
  71 Stringpool_template<char>::Stringpool_eq::operator()(const char* s1,
  72                                                      const char* s2) const
  73 {
  74   return strcmp(s1, s2) == 0;
  75 }
  76
  77 // Hash function.
  78
  79 template<typename Stringpool_char>
  80 size_t
  81 Stringpool_template<Stringpool_char>::Stringpool_hash::operator()(
  82     const Stringpool_char* s) const
  83 {
  84   // Fowler/Noll/Vo (FNV) hash (type FNV-1a).
  85   if (sizeof(size_t) == 8)
  86     {
  87       size_t result = static_cast<size_t>(14695981039346656037ULL);
  88       while (*s != 0)
  89         {
  90           const char* p = reinterpret_cast<const char*>(s);
  91           for (size_t i = 0; i < sizeof(Stringpool_char); ++i)
  92             {
  93               result &= (size_t) *p++;
  94               result *= 1099511628211ULL;
  95             }
  96           ++s;
  97         }
  98       return result;
  99     }
 100   else
 101     {
 102       size_t result = 2166136261UL;
 103       while (*s != 0)
 104         {
 105           const char* p = reinterpret_cast<const char*>(s);
 106           for (size_t i = 0; i < sizeof(Stringpool_char); ++i)
 107             {
 108               result ^= (size_t) *p++;
 109               result *= 16777619UL;
 110             }
 111           ++s;
 112         }
 113       return result;
 114     }
 115 }
 116
 117 // Add a string to the list of canonical strings.  Return a pointer to
 118 // the canonical string.  If PKEY is not NULL, set *PKEY to the key.
 119
 120 template<typename Stringpool_char>
 121 const Stringpool_char*
 122 Stringpool_template<Stringpool_char>::add_string(const Stringpool_char* s,
 123                                                  Key* pkey)
 124 {
 125   // We are in trouble if we've already computed the string offsets.
 126   gold_assert(this->strtab_size_ == 0);
 127
 128   // The size we allocate for a new Stringdata.
 129   const size_t buffer_size = 1000;
 130   // The amount we multiply the Stringdata index when calculating the
 131   // key.
 132   const size_t key_mult = 1024;
 133   gold_assert(key_mult >= buffer_size);
 134
 135   size_t len = (string_length(s) + 1) * sizeof(Stringpool_char);
 136
 137   size_t alc;
 138   bool front = true;
 139   if (len > buffer_size)
 140     {
 141       alc = sizeof(Stringdata) + len;
 142       front = false;
 143     }
 144   else if (this->strings_.empty())
 145     alc = sizeof(Stringdata) + buffer_size;
 146   else
 147     {
 148       Stringdata *psd = this->strings_.front();
 149       if (len > psd->alc - psd->len)
 150         alc = sizeof(Stringdata) + buffer_size;
 151       else
 152         {
 153           char* ret = psd->data + psd->len;
 154           memcpy(ret, s, len);
 155
 156           if (pkey != NULL)
 157             *pkey = psd->index * key_mult + psd->len;
 158
 159           psd->len += len;
 160
 161           return reinterpret_cast<const Stringpool_char*>(ret);
 162         }
 163     }
 164
 165   Stringdata *psd = reinterpret_cast<Stringdata*>(new char[alc]);
 166   psd->alc = alc - sizeof(Stringdata);
 167   memcpy(psd->data, s, len);
 168   psd->len = len;
 169   psd->index = this->next_index_;
 170   ++this->next_index_;
 171
 172   if (pkey != NULL)
 173     *pkey = psd->index * key_mult;
 174
 175   if (front)
 176     this->strings_.push_front(psd);
 177   else
 178     this->strings_.push_back(psd);
 179
 180   return reinterpret_cast<const Stringpool_char*>(psd->data);
 181 }
 182
 183 // Add a string to a string pool.
 184
 185 template<typename Stringpool_char>
 186 const Stringpool_char*
 187 Stringpool_template<Stringpool_char>::add(const Stringpool_char* s, Key* pkey)
 188 {
 189   // FIXME: This will look up the entry twice in the hash table.  The
 190   // problem is that we can't insert S before we canonicalize it.  I
 191   // don't think there is a way to handle this correctly with
 192   // unordered_map, so this should be replaced with custom code to do
 193   // what we need, which is to return the empty slot.
 194
 195   typename String_set_type::const_iterator p = this->string_set_.find(s);
 196   if (p != this->string_set_.end())
 197     {
 198       if (pkey != NULL)
 199         *pkey = p->second.first;
 200       return p->first;
 201     }
 202
 203   Key k;
 204   const Stringpool_char* ret = this->add_string(s, &k);
 205
 206   const off_t ozero = 0;
 207   std::pair<const Stringpool_char*, Val> element(ret,
 208                                                  std::make_pair(k, ozero));
 209   std::pair<typename String_set_type::iterator, bool> ins =
 210     this->string_set_.insert(element);
 211   gold_assert(ins.second);
 212
 213   if (pkey != NULL)
 214     *pkey = k;
 215
 216   return ret;
 217 }
 218
 219 // Add a prefix of a string to a string pool.
 220
 221 template<typename Stringpool_char>
 222 const Stringpool_char*
 223 Stringpool_template<Stringpool_char>::add(const Stringpool_char* s, size_t len,
 224                                  Key* pkey)
 225 {
 226   // FIXME: This implementation should be rewritten when we rewrite
 227   // the hash table to avoid copying.
 228   std::basic_string<Stringpool_char> st(s, len);
 229   return this->add(st, pkey);
 230 }
 231
 232 template<typename Stringpool_char>
 233 const Stringpool_char*
 234 Stringpool_template<Stringpool_char>::find(const Stringpool_char* s,
 235                                            Key* pkey) const
 236 {
 237   typename String_set_type::const_iterator p = this->string_set_.find(s);
 238   if (p == this->string_set_.end())
 239     return NULL;
 240
 241   if (pkey != NULL)
 242     *pkey = p->second.first;
 243
 244   return p->first;
 245 }
 246
 247 // Comparison routine used when sorting into an ELF strtab.  We want
 248 // to sort this so that when one string is a suffix of another, we
 249 // always see the shorter string immediately after the longer string.
 250 // For example, we want to see these strings in this order:
 251 //   abcd
 252 //   cd
 253 //   d
 254 // When strings are not suffixes, we don't care what order they are
 255 // in, but we need to ensure that suffixes wind up next to each other.
 256 // So we do a reversed lexicographic sort on the reversed string.
 257
 258 template<typename Stringpool_char>
 259 bool
 260 Stringpool_template<Stringpool_char>::Stringpool_sort_comparison::operator()(
 261   const Stringpool_sort_info& sort_info1,
 262   const Stringpool_sort_info& sort_info2) const
 263 {
 264   const Stringpool_char* s1 = sort_info1.it->first;
 265   const Stringpool_char* s2 = sort_info2.it->first;
 266   const size_t len1 = sort_info1.string_length;
 267   const size_t len2 = sort_info2.string_length;
 268   const size_t minlen = len1 < len2 ? len1 : len2;
 269   const Stringpool_char* p1 = s1 + len1 - 1;
 270   const Stringpool_char* p2 = s2 + len2 - 1;
 271   for (size_t i = minlen; i > 0; --i, --p1, --p2)
 272     {
 273       if (*p1 != *p2)
 274         return *p1 > *p2;
 275     }
 276   return len1 > len2;
 277 }
 278
 279 // Return whether s1 is a suffix of s2.
 280
 281 template<typename Stringpool_char>
 282 bool
 283 Stringpool_template<Stringpool_char>::is_suffix(const Stringpool_char* s1,
 284                                                 size_t len1,
 285                                                 const Stringpool_char* s2,
 286                                                 size_t len2)
 287 {
 288   if (len1 > len2)
 289     return false;
 290   return memcmp(s1, s2 + len2 - len1, len1 * sizeof(Stringpool_char)) == 0;
 291 }
 292
 293 // Turn the stringpool into an ELF strtab: determine the offsets of
 294 // each string in the table.
 295
 296 template<typename Stringpool_char>
 297 void
 298 Stringpool_template<Stringpool_char>::set_string_offsets()
 299 {
 300   if (this->strtab_size_ != 0)
 301     {
 302       // We've already computed the offsets.
 303       return;
 304     }
 305
 306   size_t count = this->string_set_.size();
 307
 308   std::vector<Stringpool_sort_info> v;
 309   v.reserve(count);
 310
 311   for (typename String_set_type::iterator p = this->string_set_.begin();
 312        p != this->string_set_.end();
 313        ++p)
 314     v.push_back(Stringpool_sort_info(p, string_length(p->first)));
 315
 316   std::sort(v.begin(), v.end(), Stringpool_sort_comparison());
 317
 318   const size_t charsize = sizeof(Stringpool_char);
 319
 320   // Offset 0 may be reserved for the empty string.
 321   off_t offset = this->zero_null_ ? charsize : 0;
 322
 323   for (typename std::vector<Stringpool_sort_info>::iterator last = v.end(),
 324          curr = v.begin();
 325        curr != v.end();
 326        last = curr++)
 327     {
 328       if (this->zero_null_ && curr->it->first[0] == 0)
 329         curr->it->second.second = 0;
 330       else if (last != v.end()
 331                && is_suffix(curr->it->first, curr->string_length,
 332                             last->it->first, last->string_length))
 333         curr->it->second.second = (last->it->second.second
 334                                    + ((last->string_length
 335                                        - curr->string_length)
 336                                       * charsize));
 337       else
 338         {
 339           curr->it->second.second = offset;
 340           offset += (curr->string_length + 1) * charsize;
 341         }
 342     }
 343
 344   this->strtab_size_ = offset;
 345 }
 346
 347 // Get the offset of a string in the ELF strtab.  The string must
 348 // exist.
 349
 350 template<typename Stringpool_char>
 351 off_t
 352 Stringpool_template<Stringpool_char>::get_offset(const Stringpool_char* s)
 353   const
 354 {
 355   gold_assert(this->strtab_size_ != 0);
 356   typename String_set_type::const_iterator p = this->string_set_.find(s);
 357   if (p != this->string_set_.end())
 358     return p->second.second;
 359   gold_unreachable();
 360 }
 361
 362 // Write the ELF strtab into the output file at the specified offset.
 363
 364 template<typename Stringpool_char>
 365 void
 366 Stringpool_template<Stringpool_char>::write(Output_file* of, off_t offset)
 367 {
 368   gold_assert(this->strtab_size_ != 0);
 369   unsigned char* viewu = of->get_output_view(offset, this->strtab_size_);
 370   char* view = reinterpret_cast<char*>(viewu);
 371   if (this->zero_null_)
 372     view[0] = '\0';
 373   for (typename String_set_type::const_iterator p = this->string_set_.begin();
 374        p != this->string_set_.end();
 375        ++p)
 376     memcpy(view + p->second.second, p->first,
 377            (string_length(p->first) + 1) * sizeof(Stringpool_char));
 378   of->write_output_view(offset, this->strtab_size_, viewu);
 379 }
 380
 381 // Instantiate the templates we need.
 382
 383 template
 384 class Stringpool_template<char>;
 385
 386 template
 387 class Stringpool_template<uint16_t>;
 388
 389 template
 390 class Stringpool_template<uint32_t>;
 391
 392 } // End namespace gold.