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