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