gold/stringpool.cc

   1 // stringpool.cc -- a string pool for gold
   2
   3 #include "gold.h"
   4
   5 #include <cassert>
   6 #include <cstring>
   7
   8 #include "stringpool.h"
   9
  10 namespace gold
  11 {
  12
  13 Stringpool::Stringpool()
  14   : string_set_(), strings_()
  15 {
  16 }
  17
  18 Stringpool::~Stringpool()
  19 {
  20   for (std::list<stringdata*>::iterator p = this->strings_.begin();
  21        p != this->strings_.end();
  22        ++p)
  23     delete[] reinterpret_cast<char*>(*p);
  24 }
  25
  26 // Hash function.
  27
  28 size_t
  29 Stringpool::Stringpool_hash::operator()(const char* s) const
  30 {
  31   // Fowler/Noll/Vo (FNV) hash (type FNV-1a).
  32   if (sizeof(size_t) == 8)
  33     {
  34       size_t result = 14695981039346656037ULL;
  35       while (*s != '\0')
  36         {
  37           result &= (size_t) *s++;
  38           result *= 1099511628211ULL;
  39         }
  40       return result;
  41     }
  42   else
  43     {
  44       size_t result = 2166136261UL;
  45       while (*s != '\0')
  46         {
  47           result ^= (size_t) *s++;
  48           result *= 16777619UL;
  49         }
  50       return result;
  51     }
  52 }
  53
  54 // Add a string to the list of canonical strings.  Return a pointer to
  55 // the canonical string.
  56
  57 const char*
  58 Stringpool::add_string(const char* s)
  59 {
  60   const size_t buffer_size = 1000;
  61   size_t len = strlen(s);
  62
  63   size_t alc;
  64   bool front = true;
  65   if (len >= buffer_size)
  66     {
  67       alc = sizeof(stringdata) + len;
  68       front = false;
  69     }
  70   else if (this->strings_.empty())
  71     alc = sizeof(stringdata) + buffer_size;
  72   else
  73     {
  74       stringdata *psd = this->strings_.front();
  75       if (len >= psd->alc - psd->len)
  76         alc = sizeof(stringdata) + buffer_size;
  77       else
  78         {
  79           char* ret = psd->data + psd->len;
  80           memcpy(ret, s, len + 1);
  81           psd->len += len + 1;
  82           return ret;
  83         }
  84     }
  85
  86   stringdata *psd = reinterpret_cast<stringdata*>(new char[alc]);
  87   psd->alc = alc;
  88   memcpy(psd->data, s, len + 1);
  89   psd->len = len + 1;
  90   if (front)
  91     this->strings_.push_front(psd);
  92   else
  93     this->strings_.push_back(psd);
  94   return psd->data;
  95 }
  96
  97 // Add a string to a string pool.
  98
  99 const char*
 100 Stringpool::add(const char* s)
 101 {
 102   // FIXME: This will look up the entry twice in the hash table.  The
 103   // problem is that we can't insert S before we canonicalize it.  I
 104   // don't think there is a way to handle this correctly with
 105   // unordered_set, so this should be replaced with custom code to do
 106   // what we need, which is to return the empty slot.
 107
 108   String_set_type::const_iterator p = this->string_set_.find(s);
 109   if (p != this->string_set_.end())
 110     return *p;
 111
 112   const char* ret = this->add_string(s);
 113   std::pair<String_set_type::iterator, bool> ins =
 114     this->string_set_.insert(ret);
 115   assert(ins.second);
 116   return ret;
 117 }
 118
 119 // Add a prefix of a string to a string pool.
 120
 121 const char*
 122 Stringpool::add(const char* s, size_t len)
 123 {
 124   // FIXME: This implementation should be rewritten when we rewrite
 125   // the hash table to avoid copying.
 126   std::string st(s, len);
 127   return this->add(st);
 128 }
 129
 130 } // End namespace gold.