src/3rdparty/v8/src/hashmap.h

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28 #ifndef V8_HASHMAP_H_
  29 #define V8_HASHMAP_H_
  30
  31 #include "allocation.h"
  32 #include "checks.h"
  33 #include "utils.h"
  34
  35 namespace v8 {
  36 namespace internal {
  37
  38 template<class AllocationPolicy>
  39 class TemplateHashMapImpl {
  40  public:
  41   typedef bool (*MatchFun) (void* key1, void* key2);
  42
  43   // initial_capacity is the size of the initial hash map;
  44   // it must be a power of 2 (and thus must not be 0).
  45   TemplateHashMapImpl(MatchFun match, uint32_t initial_capacity = 8);
  46
  47   ~TemplateHashMapImpl();
  48
  49   // HashMap entries are (key, value, hash) triplets.
  50   // Some clients may not need to use the value slot
  51   // (e.g. implementers of sets, where the key is the value).
  52   struct Entry {
  53     void* key;
  54     void* value;
  55     uint32_t hash;  // the full hash value for key
  56   };
  57
  58   // If an entry with matching key is found, Lookup()
  59   // returns that entry. If no matching entry is found,
  60   // but insert is set, a new entry is inserted with
  61   // corresponding key, key hash, and NULL value.
  62   // Otherwise, NULL is returned.
  63   Entry* Lookup(void* key, uint32_t hash, bool insert);
  64
  65   // Removes the entry with matching key.
  66   // It returns the value of the deleted entry
  67   // or null if there is no value for such key.
  68   void* Remove(void* key, uint32_t hash);
  69
  70   // Empties the hash map (occupancy() == 0).
  71   void Clear();
  72
  73   // The number of (non-empty) entries in the table.
  74   uint32_t occupancy() const { return occupancy_; }
  75
  76   // The capacity of the table. The implementation
  77   // makes sure that occupancy is at most 80% of
  78   // the table capacity.
  79   uint32_t capacity() const { return capacity_; }
  80
  81   // Iteration
  82   //
  83   // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) {
  84   //   ...
  85   // }
  86   //
  87   // If entries are inserted during iteration, the effect of
  88   // calling Next() is undefined.
  89   Entry* Start() const;
  90   Entry* Next(Entry* p) const;
  91
  92  private:
  93   MatchFun match_;
  94   Entry* map_;
  95   uint32_t capacity_;
  96   uint32_t occupancy_;
  97
  98   Entry* map_end() const { return map_ + capacity_; }
  99   Entry* Probe(void* key, uint32_t hash);
 100   void Initialize(uint32_t capacity);
 101   void Resize();
 102 };
 103
 104 typedef TemplateHashMapImpl<FreeStoreAllocationPolicy> HashMap;
 105
 106 template<class P>
 107 TemplateHashMapImpl<P>::TemplateHashMapImpl(MatchFun match,
 108                     uint32_t initial_capacity) {
 109   match_ = match;
 110   Initialize(initial_capacity);
 111 }
 112
 113
 114 template<class P>
 115 TemplateHashMapImpl<P>::~TemplateHashMapImpl() {
 116   P::Delete(map_);
 117 }
 118
 119
 120 template<class P>
 121 typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Lookup(
 122     void* key, uint32_t hash, bool insert) {
 123   // Find a matching entry.
 124   Entry* p = Probe(key, hash);
 125   if (p->key != NULL) {
 126     return p;
 127   }
 128
 129   // No entry found; insert one if necessary.
 130   if (insert) {
 131     p->key = key;
 132     p->value = NULL;
 133     p->hash = hash;
 134     occupancy_++;
 135
 136     // Grow the map if we reached >= 80% occupancy.
 137     if (occupancy_ + occupancy_/4 >= capacity_) {
 138       Resize();
 139       p = Probe(key, hash);
 140     }
 141
 142     return p;
 143   }
 144
 145   // No entry found and none inserted.
 146   return NULL;
 147 }
 148
 149
 150 template<class P>
 151 void* TemplateHashMapImpl<P>::Remove(void* key, uint32_t hash) {
 152   // Lookup the entry for the key to remove.
 153   Entry* p = Probe(key, hash);
 154   if (p->key == NULL) {
 155     // Key not found nothing to remove.
 156     return NULL;
 157   }
 158
 159   void* value = p->value;
 160   // To remove an entry we need to ensure that it does not create an empty
 161   // entry that will cause the search for another entry to stop too soon. If all
 162   // the entries between the entry to remove and the next empty slot have their
 163   // initial position inside this interval, clearing the entry to remove will
 164   // not break the search. If, while searching for the next empty entry, an
 165   // entry is encountered which does not have its initial position between the
 166   // entry to remove and the position looked at, then this entry can be moved to
 167   // the place of the entry to remove without breaking the search for it. The
 168   // entry made vacant by this move is now the entry to remove and the process
 169   // starts over.
 170   // Algorithm from http://en.wikipedia.org/wiki/Open_addressing.
 171
 172   // This guarantees loop termination as there is at least one empty entry so
 173   // eventually the removed entry will have an empty entry after it.
 174   ASSERT(occupancy_ < capacity_);
 175
 176   // p is the candidate entry to clear. q is used to scan forwards.
 177   Entry* q = p;  // Start at the entry to remove.
 178   while (true) {
 179     // Move q to the next entry.
 180     q = q + 1;
 181     if (q == map_end()) {
 182       q = map_;
 183     }
 184
 185     // All entries between p and q have their initial position between p and q
 186     // and the entry p can be cleared without breaking the search for these
 187     // entries.
 188     if (q->key == NULL) {
 189       break;
 190     }
 191
 192     // Find the initial position for the entry at position q.
 193     Entry* r = map_ + (q->hash & (capacity_ - 1));
 194
 195     // If the entry at position q has its initial position outside the range
 196     // between p and q it can be moved forward to position p and will still be
 197     // found. There is now a new candidate entry for clearing.
 198     if ((q > p && (r <= p || r > q)) ||
 199         (q < p && (r <= p && r > q))) {
 200       *p = *q;
 201       p = q;
 202     }
 203   }
 204
 205   // Clear the entry which is allowed to en emptied.
 206   p->key = NULL;
 207   occupancy_--;
 208   return value;
 209 }
 210
 211
 212 template<class P>
 213 void TemplateHashMapImpl<P>::Clear() {
 214   // Mark all entries as empty.
 215   const Entry* end = map_end();
 216   for (Entry* p = map_; p < end; p++) {
 217     p->key = NULL;
 218   }
 219   occupancy_ = 0;
 220 }
 221
 222
 223 template<class P>
 224 typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Start() const {
 225   return Next(map_ - 1);
 226 }
 227
 228
 229 template<class P>
 230 typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Next(Entry* p)
 231     const {
 232   const Entry* end = map_end();
 233   ASSERT(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 P>
 244 typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Probe(void* key,
 245                                                             uint32_t hash) {
 246   ASSERT(key != NULL);
 247
 248   ASSERT(IsPowerOf2(capacity_));
 249   Entry* p = map_ + (hash & (capacity_ - 1));
 250   const Entry* end = map_end();
 251   ASSERT(map_ <= p && p < end);
 252
 253   ASSERT(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 P>
 266 void TemplateHashMapImpl<P>::Initialize(uint32_t capacity) {
 267   ASSERT(IsPowerOf2(capacity));
 268   map_ = reinterpret_cast<Entry*>(P::New(capacity * sizeof(Entry)));
 269   if (map_ == NULL) {
 270     v8::internal::FatalProcessOutOfMemory("HashMap::Initialize");
 271     return;
 272   }
 273   capacity_ = capacity;
 274   Clear();
 275 }
 276
 277
 278 template<class P>
 279 void TemplateHashMapImpl<P>::Resize() {
 280   Entry* map = map_;
 281   uint32_t n = occupancy_;
 282
 283   // Allocate larger map.
 284   Initialize(capacity_ * 2);
 285
 286   // Rehash all current entries.
 287   for (Entry* p = map; n > 0; p++) {
 288     if (p->key != NULL) {
 289       Lookup(p->key, p->hash, true)->value = p->value;
 290       n--;
 291     }
 292   }
 293
 294   // Delete old map.
 295   P::Delete(map);
 296 }
 297
 298
 299 // A hash map for pointer keys and values with an STL-like interface.
 300 template<class Key, class Value, class AllocationPolicy>
 301 class TemplateHashMap: private TemplateHashMapImpl<AllocationPolicy> {
 302  public:
 303   STATIC_ASSERT(sizeof(Key*) == sizeof(void*));  // NOLINT
 304   STATIC_ASSERT(sizeof(Value*) == sizeof(void*));  // NOLINT
 305   struct value_type {
 306     Key* first;
 307     Value* second;
 308   };
 309
 310   class Iterator {
 311    public:
 312     Iterator& operator++() {
 313       entry_ = map_->Next(entry_);
 314       return *this;
 315     }
 316
 317     value_type* operator->() { return reinterpret_cast<value_type*>(entry_); }
 318     bool operator!=(const Iterator& other) { return  entry_ != other.entry_; }
 319
 320    private:
 321     Iterator(const TemplateHashMapImpl<AllocationPolicy>* map,
 322              typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) :
 323         map_(map), entry_(entry) { }
 324
 325     const TemplateHashMapImpl<AllocationPolicy>* map_;
 326     typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_;
 327
 328     friend class TemplateHashMap;
 329   };
 330
 331   TemplateHashMap(
 332       typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match)
 333     : TemplateHashMapImpl<AllocationPolicy>(match) { }
 334
 335   Iterator begin() const { return Iterator(this, this->Start()); }
 336   Iterator end() const { return Iterator(this, NULL); }
 337   Iterator find(Key* key, bool insert = false) {
 338     return Iterator(this, this->Lookup(key, key->Hash(), insert));
 339   }
 340 };
 341
 342 } }  // namespace v8::internal
 343
 344 #endif  // V8_HASHMAP_H_