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), next_index_(1)
  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.  If PKEY is not NULL, set *PKEY to the key.
  59
  60 const char*
  61 Stringpool::add_string(const char* s, Key* pkey)
  62 {
  63   // The size we allocate for a new Stringdata.
  64   const size_t buffer_size = 1000;
  65   // The amount we multiply the Stringdata index when calculating the
  66   // key.
  67   const size_t key_mult = 1024;
  68   assert(key_mult >= buffer_size);
  69
  70   size_t len = strlen(s);
  71
  72   size_t alc;
  73   bool front = true;
  74   if (len >= buffer_size)
  75     {
  76       alc = sizeof(Stringdata) + len;
  77       front = false;
  78     }
  79   else if (this->strings_.empty())
  80     alc = sizeof(Stringdata) + buffer_size;
  81   else
  82     {
  83       Stringdata *psd = this->strings_.front();
  84       if (len >= psd->alc - psd->len)
  85         alc = sizeof(Stringdata) + buffer_size;
  86       else
  87         {
  88           char* ret = psd->data + psd->len;
  89           memcpy(ret, s, len + 1);
  90
  91           if (pkey != NULL)
  92             *pkey = psd->index * key_mult + psd->len;
  93
  94           psd->len += len + 1;
  95
  96           return ret;
  97         }
  98     }
  99
 100   Stringdata *psd = reinterpret_cast<Stringdata*>(new char[alc]);
 101   psd->alc = alc - sizeof(Stringdata);
 102   memcpy(psd->data, s, len + 1);
 103   psd->len = len + 1;
 104   psd->index = this->next_index_;
 105   ++this->next_index_;
 106
 107   if (pkey != NULL)
 108     *pkey = psd->index * key_mult;
 109
 110   if (front)
 111     this->strings_.push_front(psd);
 112   else
 113     this->strings_.push_back(psd);
 114
 115   return psd->data;
 116 }
 117
 118 // Add a string to a string pool.
 119
 120 const char*
 121 Stringpool::add(const char* s, Key* pkey)
 122 {
 123   // FIXME: This will look up the entry twice in the hash table.  The
 124   // problem is that we can't insert S before we canonicalize it.  I
 125   // don't think there is a way to handle this correctly with
 126   // unordered_map, so this should be replaced with custom code to do
 127   // what we need, which is to return the empty slot.
 128
 129   String_set_type::const_iterator p = this->string_set_.find(s);
 130   if (p != this->string_set_.end())
 131     {
 132       if (pkey != NULL)
 133         *pkey = p->second.first;
 134       return p->first;
 135     }
 136
 137   Key k;
 138   const char* ret = this->add_string(s, &k);
 139
 140   const off_t ozero = 0;
 141   std::pair<const char*, Val> element(ret, std::make_pair(k, ozero));
 142   std::pair<String_set_type::iterator, bool> ins =
 143     this->string_set_.insert(element);
 144   assert(ins.second);
 145
 146   if (pkey != NULL)
 147     *pkey = k;
 148
 149   return ret;
 150 }
 151
 152 // Add a prefix of a string to a string pool.
 153
 154 const char*
 155 Stringpool::add(const char* s, size_t len, Key* pkey)
 156 {
 157   // FIXME: This implementation should be rewritten when we rewrite
 158   // the hash table to avoid copying.
 159   std::string st(s, len);
 160   return this->add(st, pkey);
 161 }
 162
 163 const char*
 164 Stringpool::find(const char* s, Key* pkey) const
 165 {
 166   String_set_type::const_iterator p = this->string_set_.find(s);
 167   if (p == this->string_set_.end())
 168     return NULL;
 169
 170   if (pkey != NULL)
 171     *pkey = p->second.first;
 172
 173   return p->first;
 174 }
 175
 176 // Comparison routine used when sorting into an ELF strtab.  We want
 177 // to sort this so that when one string is a suffix of another, we
 178 // always see the shorter string immediately after the longer string.
 179 // For example, we want to see these strings in this order:
 180 //   abcd
 181 //   cd
 182 //   d
 183 // When strings are not suffixes, we don't care what order they are
 184 // in, but we need to ensure that suffixes wind up next to each other.
 185 // So we do a reversed lexicographic sort on the reversed string.
 186
 187 bool
 188 Stringpool::Stringpool_sort_comparison::operator()(
 189   String_set_type::iterator it1,
 190   String_set_type::iterator it2) const
 191 {
 192   const char* s1 = it1->first;
 193   const char* s2 = it2->first;
 194   int len1 = strlen(s1);
 195   int len2 = strlen(s2);
 196   int minlen = len1 < len2 ? len1 : len2;
 197   const char* p1 = s1 + len1 - 1;
 198   const char* p2 = s2 + len2 - 1;
 199   for (int i = minlen - 1; i >= 0; --i, --p1, --p2)
 200     {
 201       if (*p1 != *p2)
 202         return *p1 > *p2;
 203     }
 204   return len1 > len2;
 205 }
 206
 207 // Return whether s1 is a suffix of s2.
 208
 209 bool
 210 Stringpool::is_suffix(const char* s1, const char* s2)
 211 {
 212   size_t len1 = strlen(s1);
 213   size_t len2 = strlen(s2);
 214   if (len1 > len2)
 215     return false;
 216   return strcmp(s1, s2 + len2 - len1) == 0;
 217 }
 218
 219 // Turn the stringpool into an ELF strtab: determine the offsets of
 220 // each string in the table.
 221
 222 void
 223 Stringpool::set_string_offsets()
 224 {
 225   size_t count = this->string_set_.size();
 226
 227   std::vector<String_set_type::iterator> v;
 228   v.reserve(count);
 229
 230   for (String_set_type::iterator p = this->string_set_.begin();
 231        p != this->string_set_.end();
 232        ++p)
 233     v.push_back(p);
 234
 235   std::sort(v.begin(), v.end(), Stringpool_sort_comparison());
 236
 237   // Offset 0 is reserved for the empty string.
 238   off_t offset = 1;
 239   for (size_t i = 0; i < count; ++i)
 240     {
 241       if (v[i]->first[0] == '\0')
 242         v[i]->second.second = 0;
 243       else if (i > 0 && Stringpool::is_suffix(v[i]->first, v[i - 1]->first))
 244         v[i]->second.second = (v[i - 1]->second.second
 245                                + strlen(v[i - 1]->first)
 246                                - strlen(v[i]->first));
 247       else
 248         {
 249           v[i]->second.second = offset;
 250           offset += strlen(v[i]->first) + 1;
 251         }
 252     }
 253
 254   this->strtab_size_ = offset;
 255 }
 256
 257 // Get the offset of a string in the ELF strtab.  The string must
 258 // exist.
 259
 260 off_t
 261 Stringpool::get_offset(const char* s) const
 262 {
 263   String_set_type::const_iterator p = this->string_set_.find(s);
 264   if (p != this->string_set_.end())
 265     return p->second.second;
 266   abort();
 267 }
 268
 269 // Write the ELF strtab into the output file at the specified offset.
 270
 271 void
 272 Stringpool::write(Output_file* of, off_t offset)
 273 {
 274   unsigned char* viewu = of->get_output_view(offset, this->strtab_size_);
 275   char* view = reinterpret_cast<char*>(viewu);
 276   view[0] = '\0';
 277   for (String_set_type::const_iterator p = this->string_set_.begin();
 278        p != this->string_set_.end();
 279        ++p)
 280     strcpy(view + p->second.second, p->first);
 281   of->write_output_view(offset, this->strtab_size_, viewu);
 282 }
 283
 284 } // End namespace gold.