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