src/hashmap.h

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef V8_HASHMAP_H_
   6 #define V8_HASHMAP_H_
   7
   8 #include "src/allocation.h"
   9 #include "src/base/bits.h"
  10 #include "src/base/logging.h"
  11 #include "src/utils.h"
  12
  13 namespace v8 {
  14 namespace internal {
  15
  16 template<class AllocationPolicy>
  17 class TemplateHashMapImpl {
  18  public:
  19   typedef bool (*MatchFun) (void* key1, void* key2);
  20
  21   // The default capacity.  This is used by the call sites which want
  22   // to pass in a non-default AllocationPolicy but want to use the
  23   // default value of capacity specified by the implementation.
  24   static const uint32_t kDefaultHashMapCapacity = 8;
  25
  26   // initial_capacity is the size of the initial hash map;
  27   // it must be a power of 2 (and thus must not be 0).
  28   TemplateHashMapImpl(MatchFun match,
  29                       uint32_t capacity = kDefaultHashMapCapacity,
  30                       AllocationPolicy allocator = AllocationPolicy());
  31
  32   ~TemplateHashMapImpl();
  33
  34   // HashMap entries are (key, value, hash) triplets.
  35   // Some clients may not need to use the value slot
  36   // (e.g. implementers of sets, where the key is the value).
  37   struct Entry {
  38     void* key;
  39     void* value;
  40     uint32_t hash;  // The full hash value for key
  41     int order;  // If you never remove entries this is the insertion order.
  42   };
  43
  44   // If an entry with matching key is found, returns that entry.
  45   // Otherwise, NULL is returned.
  46   Entry* Lookup(void* key, uint32_t hash) const;
  47
  48   // If an entry with matching key is found, returns that entry.
  49   // If no matching entry is found, a new entry is inserted with
  50   // corresponding key, key hash, and NULL value.
  51   Entry* LookupOrInsert(void* key, uint32_t hash,
  52                         AllocationPolicy allocator = AllocationPolicy());
  53
  54   // Removes the entry with matching key.
  55   // It returns the value of the deleted entry
  56   // or null if there is no value for such key.
  57   void* Remove(void* key, uint32_t hash);
  58
  59   // Empties the hash map (occupancy() == 0).
  60   void Clear();
  61
  62   // The number of (non-empty) entries in the table.
  63   uint32_t occupancy() const { return occupancy_; }
  64
  65   // The capacity of the table. The implementation
  66   // makes sure that occupancy is at most 80% of
  67   // the table capacity.
  68   uint32_t capacity() const { return capacity_; }
  69
  70   // Iteration
  71   //
  72   // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) {
  73   //   ...
  74   // }
  75   //
  76   // If entries are inserted during iteration, the effect of
  77   // calling Next() is undefined.
  78   Entry* Start() const;
  79   Entry* Next(Entry* p) const;
  80
  81   // Some match functions defined for convenience.
  82   static bool PointersMatch(void* key1, void* key2) {
  83     return key1 == key2;
  84   }
  85
  86  private:
  87   MatchFun match_;
  88   Entry* map_;
  89   uint32_t capacity_;
  90   uint32_t occupancy_;
  91
  92   Entry* map_end() const { return map_ + capacity_; }
  93   Entry* Probe(void* key, uint32_t hash) const;
  94   void Initialize(uint32_t capacity, AllocationPolicy allocator);
  95   void Resize(AllocationPolicy allocator);
  96 };
  97
  98 typedef TemplateHashMapImpl<FreeStoreAllocationPolicy> HashMap;
  99
 100 template<class AllocationPolicy>
 101 TemplateHashMapImpl<AllocationPolicy>::TemplateHashMapImpl(
 102     MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator) {
 103   match_ = match;
 104   Initialize(initial_capacity, allocator);
 105 }
 106
 107
 108 template<class AllocationPolicy>
 109 TemplateHashMapImpl<AllocationPolicy>::~TemplateHashMapImpl() {
 110   AllocationPolicy::Delete(map_);
 111 }
 112
 113
 114 template <class AllocationPolicy>
 115 typename TemplateHashMapImpl<AllocationPolicy>::Entry*
 116 TemplateHashMapImpl<AllocationPolicy>::Lookup(void* key, uint32_t hash) const {
 117   Entry* p = Probe(key, hash);
 118   return p->key != NULL ? p : NULL;
 119 }
 120
 121
 122 template <class AllocationPolicy>
 123 typename TemplateHashMapImpl<AllocationPolicy>::Entry*
 124 TemplateHashMapImpl<AllocationPolicy>::LookupOrInsert(
 125     void* key, uint32_t hash, AllocationPolicy allocator) {
 126   // Find a matching entry.
 127   Entry* p = Probe(key, hash);
 128   if (p->key != NULL) {
 129     return p;
 130   }
 131
 132   // No entry found; insert one.
 133   p->key = key;
 134   p->value = NULL;
 135   p->hash = hash;
 136   p->order = occupancy_;
 137   occupancy_++;
 138
 139   // Grow the map if we reached >= 80% occupancy.
 140   if (occupancy_ + occupancy_ / 4 >= capacity_) {
 141     Resize(allocator);
 142     p = Probe(key, hash);
 143   }
 144
 145   return p;
 146 }
 147
 148
 149 template<class AllocationPolicy>
 150 void* TemplateHashMapImpl<AllocationPolicy>::Remove(void* key, uint32_t hash) {
 151   // Lookup the entry for the key to remove.
 152   Entry* p = Probe(key, hash);
 153   if (p->key == NULL) {
 154     // Key not found nothing to remove.
 155     return NULL;
 156   }
 157
 158   void* value = p->value;
 159   // To remove an entry we need to ensure that it does not create an empty
 160   // entry that will cause the search for another entry to stop too soon. If all
 161   // the entries between the entry to remove and the next empty slot have their
 162   // initial position inside this interval, clearing the entry to remove will
 163   // not break the search. If, while searching for the next empty entry, an
 164   // entry is encountered which does not have its initial position between the
 165   // entry to remove and the position looked at, then this entry can be moved to
 166   // the place of the entry to remove without breaking the search for it. The
 167   // entry made vacant by this move is now the entry to remove and the process
 168   // starts over.
 169   // Algorithm from http://en.wikipedia.org/wiki/Open_addressing.
 170
 171   // This guarantees loop termination as there is at least one empty entry so
 172   // eventually the removed entry will have an empty entry after it.
 173   DCHECK(occupancy_ < capacity_);
 174
 175   // p is the candidate entry to clear. q is used to scan forwards.
 176   Entry* q = p;  // Start at the entry to remove.
 177   while (true) {
 178     // Move q to the next entry.
 179     q = q + 1;
 180     if (q == map_end()) {
 181       q = map_;
 182     }
 183
 184     // All entries between p and q have their initial position between p and q
 185     // and the entry p can be cleared without breaking the search for these
 186     // entries.
 187     if (q->key == NULL) {
 188       break;
 189     }
 190
 191     // Find the initial position for the entry at position q.
 192     Entry* r = map_ + (q->hash & (capacity_ - 1));
 193
 194     // If the entry at position q has its initial position outside the range
 195     // between p and q it can be moved forward to position p and will still be
 196     // found. There is now a new candidate entry for clearing.
 197     if ((q > p && (r <= p || r > q)) ||
 198         (q < p && (r <= p && r > q))) {
 199       *p = *q;
 200       p = q;
 201     }
 202   }
 203
 204   // Clear the entry which is allowed to en emptied.
 205   p->key = NULL;
 206   occupancy_--;
 207   return value;
 208 }
 209
 210
 211 template<class AllocationPolicy>
 212 void TemplateHashMapImpl<AllocationPolicy>::Clear() {
 213   // Mark all entries as empty.
 214   const Entry* end = map_end();
 215   for (Entry* p = map_; p < end; p++) {
 216     p->key = NULL;
 217   }
 218   occupancy_ = 0;
 219 }
 220
 221
 222 template<class AllocationPolicy>
 223 typename TemplateHashMapImpl<AllocationPolicy>::Entry*
 224     TemplateHashMapImpl<AllocationPolicy>::Start() const {
 225   return Next(map_ - 1);
 226 }
 227
 228
 229 template<class AllocationPolicy>
 230 typename TemplateHashMapImpl<AllocationPolicy>::Entry*
 231     TemplateHashMapImpl<AllocationPolicy>::Next(Entry* p) const {
 232   const Entry* end = map_end();
 233   DCHECK(map_ - 1 <= p && p < end);
 234   for (p++; p < end; p++) {
 235     if (p->key != NULL) {
 236       return p;
 237     }
 238   }
 239   return NULL;
 240 }
 241
 242
 243 template <class AllocationPolicy>
 244 typename TemplateHashMapImpl<AllocationPolicy>::Entry*
 245 TemplateHashMapImpl<AllocationPolicy>::Probe(void* key, uint32_t hash) const {
 246   DCHECK(key != NULL);
 247
 248   DCHECK(base::bits::IsPowerOfTwo32(capacity_));
 249   Entry* p = map_ + (hash & (capacity_ - 1));
 250   const Entry* end = map_end();
 251   DCHECK(map_ <= p && p < end);
 252
 253   DCHECK(occupancy_ < capacity_);  // Guarantees loop termination.
 254   while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) {
 255     p++;
 256     if (p >= end) {
 257       p = map_;
 258     }
 259   }
 260
 261   return p;
 262 }
 263
 264
 265 template<class AllocationPolicy>
 266 void TemplateHashMapImpl<AllocationPolicy>::Initialize(
 267     uint32_t capacity, AllocationPolicy allocator) {
 268   DCHECK(base::bits::IsPowerOfTwo32(capacity));
 269   map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry)));
 270   if (map_ == NULL) {
 271     v8::internal::FatalProcessOutOfMemory("HashMap::Initialize");
 272     return;
 273   }
 274   capacity_ = capacity;
 275   Clear();
 276 }
 277
 278
 279 template<class AllocationPolicy>
 280 void TemplateHashMapImpl<AllocationPolicy>::Resize(AllocationPolicy allocator) {
 281   Entry* map = map_;
 282   uint32_t n = occupancy_;
 283
 284   // Allocate larger map.
 285   Initialize(capacity_ * 2, allocator);
 286
 287   // Rehash all current entries.
 288   for (Entry* p = map; n > 0; p++) {
 289     if (p->key != NULL) {
 290       Entry* entry = LookupOrInsert(p->key, p->hash, allocator);
 291       entry->value = p->value;
 292       entry->order = p->order;
 293       n--;
 294     }
 295   }
 296
 297   // Delete old map.
 298   AllocationPolicy::Delete(map);
 299 }
 300
 301
 302 // A hash map for pointer keys and values with an STL-like interface.
 303 template<class Key, class Value, class AllocationPolicy>
 304 class TemplateHashMap: private TemplateHashMapImpl<AllocationPolicy> {
 305  public:
 306   STATIC_ASSERT(sizeof(Key*) == sizeof(void*));  // NOLINT
 307   STATIC_ASSERT(sizeof(Value*) == sizeof(void*));  // NOLINT
 308   struct value_type {
 309     Key* first;
 310     Value* second;
 311   };
 312
 313   class Iterator {
 314    public:
 315     Iterator& operator++() {
 316       entry_ = map_->Next(entry_);
 317       return *this;
 318     }
 319
 320     value_type* operator->() { return reinterpret_cast<value_type*>(entry_); }
 321     bool operator!=(const Iterator& other) { return  entry_ != other.entry_; }
 322
 323    private:
 324     Iterator(const TemplateHashMapImpl<AllocationPolicy>* map,
 325              typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) :
 326         map_(map), entry_(entry) { }
 327
 328     const TemplateHashMapImpl<AllocationPolicy>* map_;
 329     typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_;
 330
 331     friend class TemplateHashMap;
 332   };
 333
 334   TemplateHashMap(
 335       typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match,
 336       AllocationPolicy allocator = AllocationPolicy())
 337         : TemplateHashMapImpl<AllocationPolicy>(
 338             match,
 339             TemplateHashMapImpl<AllocationPolicy>::kDefaultHashMapCapacity,
 340             allocator) { }
 341
 342   Iterator begin() const { return Iterator(this, this->Start()); }
 343   Iterator end() const { return Iterator(this, NULL); }
 344   Iterator find(Key* key, bool insert = false,
 345                 AllocationPolicy allocator = AllocationPolicy()) {
 346     if (insert) {
 347       return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator));
 348     }
 349     return Iterator(this, this->Lookup(key, key->Hash()));
 350   }
 351 };
 352
 353 } }  // namespace v8::internal
 354
 355 #endif  // V8_HASHMAP_H_