libvtv/vtv_map.h

   1 /* Copyright (C) 2012-2013
   2    Free Software Foundation
   3
   4    This file is part of GCC.
   5
   6    GCC is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3, or (at your option)
   9    any later version.
  10
  11    GCC is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    Under Section 7 of GPL version 3, you are granted additional
  17    permissions described in the GCC Runtime Library Exception, version
  18    3.1, as published by the Free Software Foundation.
  19
  20    You should have received a copy of the GNU General Public License and
  21    a copy of the GCC Runtime Library Exception along with this program;
  22    see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23    <http://www.gnu.org/licenses/>.  */
  24
  25 #ifndef _VTV_MAP_H
  26 #define _VTV_MAP_H 1
  27
  28 #include <string.h>
  29 #include <vtv_utils.h>
  30
  31 inline uint64_t
  32 load8bytes (const void *p)
  33 {
  34   uint64_t result;
  35   memcpy (&result, p, 8);
  36   return result;
  37 }
  38
  39 /* Insert_only_hash_map maps keys to values.  The implementation is a
  40    basic hash table with open addressing.  The keys are not "owned" by
  41    the table; it only stores pointers to keys.  The key type is
  42    specified below (see insert_only_hash_map::key_type) and is,
  43    roughly speaking, a string of any length with the string length and
  44    a hash code stored at the front.  The code here does not compute
  45    any hash codes, but rather uses what's given.  */
  46
  47 template<typename T, typename Alloc>
  48 class insert_only_hash_map
  49   {
  50     public:
  51       typedef size_t size_type;
  52       typedef T value_type;
  53       typedef Alloc alloc_type;
  54       enum { min_capacity = 4 };
  55 #if HASHMAP_STATS
  56   enum { stats = true };
  57 #else
  58   enum { stats = false };
  59 #endif
  60
  61   /* Keys are a byte string (up to 2^32 - 1 long) plus a uint32_t
  62      that's used as a hash code.  The latter can encode arbitrary
  63      information at the client's discretion, so, e.g., multiple keys
  64      that are the same string still "differ" if the hash codes differ.
  65      Keys are equal if the first 8 bytes are equal and the next n
  66      bytes are equal.  */
  67   struct key_type
  68   {
  69     uint32_t n;
  70     uint32_t hash;
  71     char bytes[0];
  72
  73     bool
  74     equals (const key_type *k) const;
  75   };
  76
  77   /* Create an empty map with a reasonable number of buckets for the
  78      expected size.  Returns NULL if the allocator fails.  */
  79
  80   static insert_only_hash_map *
  81   create (size_type expected_size);
  82
  83   /* The opposite of create().  Free the memory for the given map.  */
  84
  85   static void
  86   destroy (insert_only_hash_map *m)
  87   { Alloc().dealloc (m, m->size_in_bytes_); }
  88
  89   /* Return a map identical to this except that *k is mapped to v.
  90      Typcially it's done by modifying this in place, but if a resize
  91      is necessary then this is deallocated and a new map is returned.
  92      Requires k to be non-NULL.  Does nothing and returns NULL if the
  93      allocator fails.  */
  94
  95   insert_only_hash_map*
  96   put (const key_type *k, const value_type &v)
  97   { return this->put_internal (k, v, false); }
  98
  99   /* If *k is a key in this then set *v to point to the corresponding
 100      value.  Otherwise, do the equivalent of insert(k, value_type())
 101      and, if that succeeds, set *v to point to the inserted value.
 102      Requires k to be non-NULL.  Does nothing and returns NULL if the
 103      allocator fails.  Typically returns this, but will return a new
 104      insert_only_hash_map if a resize occurs.  If the return value is
 105      non-NULL, *v is set and it's valid until a resize of the map that
 106      is the return value.  */
 107
 108   insert_only_hash_map *
 109   find_or_add_key (const key_type *k, value_type **v);
 110
 111   /* Get the value corresponding to *k.  Returns NULL if there is
 112      none.  Requires k to be non-NULL.  The return value is valid
 113      until any resize.  */
 114   const value_type *get (const key_type *k) const;
 115
 116   size_type
 117   size () const
 118   { return num_entries_; }
 119
 120   bool
 121   empty () const
 122   { return this->size () == 0; }
 123
 124   size_type
 125   bucket_count () const
 126   { return num_buckets_; }
 127
 128  private:
 129   typedef std::pair <const key_type *, value_type> bucket_type;
 130
 131   insert_only_hash_map *put_internal (const key_type *, const value_type &,
 132                                       bool);
 133
 134   /* This function determines when to resize the table.  */
 135   bool
 136   is_too_full (size_type entries) const
 137   { return entries > (this->bucket_count () * 0.7); }
 138
 139   /* Return a copy with double the number of buckets.  Returns NULL if
 140      the allocator fails.  Otherwise, calls destroy (this).  */
 141   insert_only_hash_map *destructive_copy ();
 142
 143  /* Must be a power of 2 not less than min_capacity. */
 144   size_type num_buckets_;
 145   size_type num_entries_;
 146   size_type size_in_bytes_;
 147   bucket_type buckets[0];  /* Actual array size is num_buckets.  */
 148 };
 149
 150 template <typename T, typename Alloc>
 151 insert_only_hash_map <T, Alloc> *
 152 insert_only_hash_map <T, Alloc>::create (size_type expected_size)
 153 {
 154   size_t cap = min_capacity;
 155   while (expected_size >= cap)
 156     {
 157       cap *= 2;
 158     }
 159   size_t size_in_bytes = sizeof (insert_only_hash_map <T, Alloc>)
 160                                                   + cap * sizeof (bucket_type);
 161   insert_only_hash_map <T, Alloc>* result =
 162       static_cast <insert_only_hash_map <T, Alloc>*> (Alloc ()
 163                                                        .alloc (size_in_bytes));
 164   if (result != NULL)
 165     {
 166       result->size_in_bytes_ = size_in_bytes;
 167       result->num_buckets_ = cap;
 168       result->num_entries_ = 0;
 169       memset (result->buckets, 0, cap * sizeof (bucket_type));
 170     }
 171   return result;
 172 }
 173
 174 template <typename T, typename Alloc>
 175 insert_only_hash_map <T, Alloc>*
 176 insert_only_hash_map <T, Alloc>::destructive_copy ()
 177 {
 178   insert_only_hash_map* copy = create (this->bucket_count ());
 179   if (copy == NULL)
 180     return NULL;
 181   VTV_DEBUG_ASSERT (copy->bucket_count () == 2 * this->bucket_count ());
 182   for (size_type i = 0; i < this->bucket_count (); i++)
 183     if (this->buckets[i].first != NULL)
 184       copy->put_internal (this->buckets[i].first, this->buckets[i].second,
 185                           true);
 186   VTV_DEBUG_ASSERT (copy->size () == this->size ());
 187   destroy (this);
 188   return copy;
 189 }
 190
 191 template <typename T, typename Alloc>
 192 insert_only_hash_map <T, Alloc>*
 193 insert_only_hash_map <T, Alloc>::find_or_add_key (const key_type *k,
 194                                                   value_type **v)
 195 {
 196   /* Table size is always a power of 2.  */
 197   const size_type mask = this->bucket_count () - 1;
 198   size_type bucket_index = k->hash & mask;
 199   size_type step = 1;
 200   for (;;)
 201     {
 202       bucket_type &bucket = this->buckets[bucket_index];
 203       if (bucket.first == NULL)
 204         {
 205           /* Key was not present. */
 206           if (this->is_too_full (this->size () + 1))
 207             {
 208               insert_only_hash_map <T, Alloc>* result =
 209                                                      this->destructive_copy ();
 210               return result == NULL
 211                   ? NULL
 212                   : result->find_or_add_key (k, v);
 213             }
 214           else
 215             {
 216               bucket.first = k;
 217               bucket.second = T ();
 218               this->num_entries_++;
 219               *v = &bucket.second;
 220               return this;
 221             }
 222         }
 223       else if (bucket.first->equals (k))
 224         {
 225           /* Key was present. */
 226           *v = &bucket.second;
 227           return this;
 228         }
 229       else
 230         bucket_index = (bucket_index + step++) & mask;
 231     }
 232 }
 233
 234 template <typename T, typename Alloc>
 235 insert_only_hash_map <T, Alloc>*
 236 insert_only_hash_map <T, Alloc>::put_internal (
 237                                      const insert_only_hash_map::key_type *k,
 238                                      const insert_only_hash_map::value_type &v,
 239                                      bool unique_key_and_resize_not_needed)
 240 {
 241   /* Table size is always a power of 2.  */
 242   const size_type mask = this->bucket_count () - 1;
 243   size_type bucket_index = k->hash & mask;
 244   size_type step = 1;
 245   for (;;)
 246     {
 247       bucket_type &bucket = this->buckets[bucket_index];
 248       if (bucket.first == NULL)
 249         {
 250           /* Key was not present.  */
 251           if (!unique_key_and_resize_not_needed
 252               && this->is_too_full (this->size () + 1))
 253             {
 254               insert_only_hash_map <T, Alloc>* result =
 255                                                      this->destructive_copy ();
 256               return result == NULL
 257                   ? NULL
 258                   : result->put_internal (k, v, true);
 259             }
 260           else
 261             {
 262               bucket.first = k;
 263               bucket.second = v;
 264               this->num_entries_++;
 265               return this;
 266             }
 267         }
 268       else if (!unique_key_and_resize_not_needed && bucket.first->equals (k))
 269         {
 270           /* Key was present.  Just change the value.  */
 271           bucket.second = v;
 272           return this;
 273         }
 274       else
 275         bucket_index = (bucket_index + step++) & mask;
 276     }
 277 }
 278
 279 template <typename T, typename Alloc>
 280 inline const typename insert_only_hash_map <T, Alloc>::value_type*
 281 insert_only_hash_map <T, Alloc>::get (const insert_only_hash_map::key_type *k)
 282                                                                           const
 283 {
 284   /* Table size is always a power of 2.  */
 285   const size_type mask = this->bucket_count () - 1;
 286   size_type bucket_index = k->hash & mask;
 287   size_type step = 1;
 288   for (;;)
 289     {
 290       const bucket_type &bucket = this->buckets[bucket_index];
 291       if (bucket.first == NULL)
 292         return NULL;
 293       else if (bucket.first->equals (k))
 294         return &bucket.second;
 295       else
 296         bucket_index = (bucket_index + step++) & mask;
 297     }
 298 }
 299
 300 template <typename T, typename Alloc>
 301 inline bool
 302 insert_only_hash_map <T, Alloc>::key_type::equals (
 303              const typename insert_only_hash_map <T, Alloc>::key_type *k) const
 304 {
 305   const char* x = reinterpret_cast <const char *> (k);
 306   const char* y = reinterpret_cast <const char *> (this);
 307   return (load8bytes (x) == load8bytes (y)
 308           && memcmp (x + 8, y + 8, this->n) == 0);
 309 }
 310
 311 #endif  /* _VTV_MAP_H  */