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