hashmap.h 10.5 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4 5 6 7

#ifndef V8_HASHMAP_H_
#define V8_HASHMAP_H_

8
#include "src/allocation.h"
9
#include "src/base/bits.h"
10
#include "src/base/logging.h"
11
#include "src/utils.h"
12

13 14
namespace v8 {
namespace internal {
15

16
template<class AllocationPolicy>
17
class TemplateHashMapImpl {
18 19 20
 public:
  typedef bool (*MatchFun) (void* key1, void* key2);

21 22 23 24 25
  // The default capacity.  This is used by the call sites which want
  // to pass in a non-default AllocationPolicy but want to use the
  // default value of capacity specified by the implementation.
  static const uint32_t kDefaultHashMapCapacity = 8;

26 27
  // initial_capacity is the size of the initial hash map;
  // it must be a power of 2 (and thus must not be 0).
28 29 30
  TemplateHashMapImpl(MatchFun match,
                      uint32_t capacity = kDefaultHashMapCapacity,
                      AllocationPolicy allocator = AllocationPolicy());
31

32
  ~TemplateHashMapImpl();
33

34
  // HashMap entries are (key, value, hash) triplets.
35 36 37 38 39
  // Some clients may not need to use the value slot
  // (e.g. implementers of sets, where the key is the value).
  struct Entry {
    void* key;
    void* value;
40 41
    uint32_t hash;  // The full hash value for key
    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.
jkummerow's avatar
jkummerow committed
46
  Entry* Lookup(void* key, uint32_t hash) const;
47 48 49 50 51 52

  // If an entry with matching key is found, returns that entry.
  // If no matching entry is found, a new entry is inserted with
  // corresponding key, key hash, and NULL value.
  Entry* LookupOrInsert(void* key, uint32_t hash,
                        AllocationPolicy allocator = AllocationPolicy());
53

54
  // Removes the entry with matching key.
55 56 57
  // It returns the value of the deleted entry
  // or null if there is no value for such key.
  void* Remove(void* key, uint32_t hash);
58

59 60 61 62
  // Empties the hash map (occupancy() == 0).
  void Clear();

  // The number of (non-empty) entries in the table.
63
  uint32_t occupancy() const { return occupancy_; }
64 65 66 67

  // The capacity of the table. The implementation
  // makes sure that occupancy is at most 80% of
  // the table capacity.
68
  uint32_t capacity() const { return capacity_; }
69 70 71 72 73 74 75 76 77 78 79 80

  // Iteration
  //
  // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) {
  //   ...
  // }
  //
  // If entries are inserted during iteration, the effect of
  // calling Next() is undefined.
  Entry* Start() const;
  Entry* Next(Entry* p) const;

81 82 83 84 85
  // Some match functions defined for convenience.
  static bool PointersMatch(void* key1, void* key2) {
    return key1 == key2;
  }

86 87 88 89 90 91
 private:
  MatchFun match_;
  Entry* map_;
  uint32_t capacity_;
  uint32_t occupancy_;

92
  Entry* map_end() const { return map_ + capacity_; }
jkummerow's avatar
jkummerow committed
93
  Entry* Probe(void* key, uint32_t hash) const;
94 95
  void Initialize(uint32_t capacity, AllocationPolicy allocator);
  void Resize(AllocationPolicy allocator);
96 97
};

98
typedef TemplateHashMapImpl<FreeStoreAllocationPolicy> HashMap;
99

100 101 102
template<class AllocationPolicy>
TemplateHashMapImpl<AllocationPolicy>::TemplateHashMapImpl(
    MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator) {
103
  match_ = match;
104
  Initialize(initial_capacity, allocator);
105 106 107
}


108 109 110
template<class AllocationPolicy>
TemplateHashMapImpl<AllocationPolicy>::~TemplateHashMapImpl() {
  AllocationPolicy::Delete(map_);
111 112 113
}


114 115
template <class AllocationPolicy>
typename TemplateHashMapImpl<AllocationPolicy>::Entry*
jkummerow's avatar
jkummerow committed
116
TemplateHashMapImpl<AllocationPolicy>::Lookup(void* key, uint32_t hash) const {
117 118 119 120 121 122
  Entry* p = Probe(key, hash);
  return p->key != NULL ? p : NULL;
}


template <class AllocationPolicy>
123
typename TemplateHashMapImpl<AllocationPolicy>::Entry*
124 125
TemplateHashMapImpl<AllocationPolicy>::LookupOrInsert(
    void* key, uint32_t hash, AllocationPolicy allocator) {
126 127 128 129 130 131
  // Find a matching entry.
  Entry* p = Probe(key, hash);
  if (p->key != NULL) {
    return p;
  }

132 133 134 135 136 137 138 139 140 141 142
  // No entry found; insert one.
  p->key = key;
  p->value = NULL;
  p->hash = hash;
  p->order = occupancy_;
  occupancy_++;

  // Grow the map if we reached >= 80% occupancy.
  if (occupancy_ + occupancy_ / 4 >= capacity_) {
    Resize(allocator);
    p = Probe(key, hash);
143 144
  }

145
  return p;
146 147 148
}


149 150
template<class AllocationPolicy>
void* TemplateHashMapImpl<AllocationPolicy>::Remove(void* key, uint32_t hash) {
151 152 153 154
  // Lookup the entry for the key to remove.
  Entry* p = Probe(key, hash);
  if (p->key == NULL) {
    // Key not found nothing to remove.
155
    return NULL;
156 157
  }

158
  void* value = p->value;
159 160 161 162 163 164 165 166 167 168 169 170 171 172
  // To remove an entry we need to ensure that it does not create an empty
  // entry that will cause the search for another entry to stop too soon. If all
  // the entries between the entry to remove and the next empty slot have their
  // initial position inside this interval, clearing the entry to remove will
  // not break the search. If, while searching for the next empty entry, an
  // entry is encountered which does not have its initial position between the
  // entry to remove and the position looked at, then this entry can be moved to
  // the place of the entry to remove without breaking the search for it. The
  // entry made vacant by this move is now the entry to remove and the process
  // starts over.
  // Algorithm from http://en.wikipedia.org/wiki/Open_addressing.

  // This guarantees loop termination as there is at least one empty entry so
  // eventually the removed entry will have an empty entry after it.
173
  DCHECK(occupancy_ < capacity_);
174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206

  // p is the candidate entry to clear. q is used to scan forwards.
  Entry* q = p;  // Start at the entry to remove.
  while (true) {
    // Move q to the next entry.
    q = q + 1;
    if (q == map_end()) {
      q = map_;
    }

    // All entries between p and q have their initial position between p and q
    // and the entry p can be cleared without breaking the search for these
    // entries.
    if (q->key == NULL) {
      break;
    }

    // Find the initial position for the entry at position q.
    Entry* r = map_ + (q->hash & (capacity_ - 1));

    // If the entry at position q has its initial position outside the range
    // between p and q it can be moved forward to position p and will still be
    // found. There is now a new candidate entry for clearing.
    if ((q > p && (r <= p || r > q)) ||
        (q < p && (r <= p && r > q))) {
      *p = *q;
      p = q;
    }
  }

  // Clear the entry which is allowed to en emptied.
  p->key = NULL;
  occupancy_--;
207
  return value;
208 209 210
}


211 212
template<class AllocationPolicy>
void TemplateHashMapImpl<AllocationPolicy>::Clear() {
213 214 215 216 217 218 219 220 221
  // Mark all entries as empty.
  const Entry* end = map_end();
  for (Entry* p = map_; p < end; p++) {
    p->key = NULL;
  }
  occupancy_ = 0;
}


222 223 224
template<class AllocationPolicy>
typename TemplateHashMapImpl<AllocationPolicy>::Entry*
    TemplateHashMapImpl<AllocationPolicy>::Start() const {
225 226 227 228
  return Next(map_ - 1);
}


229 230 231
template<class AllocationPolicy>
typename TemplateHashMapImpl<AllocationPolicy>::Entry*
    TemplateHashMapImpl<AllocationPolicy>::Next(Entry* p) const {
232
  const Entry* end = map_end();
233
  DCHECK(map_ - 1 <= p && p < end);
234 235 236 237 238 239 240 241 242
  for (p++; p < end; p++) {
    if (p->key != NULL) {
      return p;
    }
  }
  return NULL;
}


243
template <class AllocationPolicy>
244
typename TemplateHashMapImpl<AllocationPolicy>::Entry*
jkummerow's avatar
jkummerow committed
245
TemplateHashMapImpl<AllocationPolicy>::Probe(void* key, uint32_t hash) const {
246
  DCHECK(key != NULL);
247

248
  DCHECK(base::bits::IsPowerOfTwo32(capacity_));
249 250
  Entry* p = map_ + (hash & (capacity_ - 1));
  const Entry* end = map_end();
251
  DCHECK(map_ <= p && p < end);
252

253
  DCHECK(occupancy_ < capacity_);  // Guarantees loop termination.
254 255 256 257 258 259 260 261 262 263 264
  while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) {
    p++;
    if (p >= end) {
      p = map_;
    }
  }

  return p;
}


265 266 267
template<class AllocationPolicy>
void TemplateHashMapImpl<AllocationPolicy>::Initialize(
    uint32_t capacity, AllocationPolicy allocator) {
268
  DCHECK(base::bits::IsPowerOfTwo32(capacity));
269
  map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry)));
270 271 272 273 274 275 276 277 278
  if (map_ == NULL) {
    v8::internal::FatalProcessOutOfMemory("HashMap::Initialize");
    return;
  }
  capacity_ = capacity;
  Clear();
}


279 280
template<class AllocationPolicy>
void TemplateHashMapImpl<AllocationPolicy>::Resize(AllocationPolicy allocator) {
281 282 283 284
  Entry* map = map_;
  uint32_t n = occupancy_;

  // Allocate larger map.
285
  Initialize(capacity_ * 2, allocator);
286 287 288 289

  // Rehash all current entries.
  for (Entry* p = map; n > 0; p++) {
    if (p->key != NULL) {
290
      Entry* entry = LookupOrInsert(p->key, p->hash, allocator);
291 292
      entry->value = p->value;
      entry->order = p->order;
293 294 295 296 297
      n--;
    }
  }

  // Delete old map.
298
  AllocationPolicy::Delete(map);
299
}
300

301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334

// A hash map for pointer keys and values with an STL-like interface.
template<class Key, class Value, class AllocationPolicy>
class TemplateHashMap: private TemplateHashMapImpl<AllocationPolicy> {
 public:
  STATIC_ASSERT(sizeof(Key*) == sizeof(void*));  // NOLINT
  STATIC_ASSERT(sizeof(Value*) == sizeof(void*));  // NOLINT
  struct value_type {
    Key* first;
    Value* second;
  };

  class Iterator {
   public:
    Iterator& operator++() {
      entry_ = map_->Next(entry_);
      return *this;
    }

    value_type* operator->() { return reinterpret_cast<value_type*>(entry_); }
    bool operator!=(const Iterator& other) { return  entry_ != other.entry_; }

   private:
    Iterator(const TemplateHashMapImpl<AllocationPolicy>* map,
             typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) :
        map_(map), entry_(entry) { }

    const TemplateHashMapImpl<AllocationPolicy>* map_;
    typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_;

    friend class TemplateHashMap;
  };

  TemplateHashMap(
335 336 337 338 339 340
      typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match,
      AllocationPolicy allocator = AllocationPolicy())
        : TemplateHashMapImpl<AllocationPolicy>(
            match,
            TemplateHashMapImpl<AllocationPolicy>::kDefaultHashMapCapacity,
            allocator) { }
341 342 343

  Iterator begin() const { return Iterator(this, this->Start()); }
  Iterator end() const { return Iterator(this, NULL); }
344 345
  Iterator find(Key* key, bool insert = false,
                AllocationPolicy allocator = AllocationPolicy()) {
346 347 348 349
    if (insert) {
      return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator));
    }
    return Iterator(this, this->Lookup(key, key->Hash()));
350 351 352
  }
};

353 354
}  // namespace internal
}  // namespace v8
355 356

#endif  // V8_HASHMAP_H_