libvtv/vtv_map.h

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