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