hashmap.h 20.4 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

lpy's avatar
lpy committed
5 6 7 8 9 10
// The reason we write our own hash map instead of using unordered_map in STL,
// is that STL containers use a mutex pool on debug build, which will lead to
// deadlock when we are using async signal handler.

#ifndef V8_BASE_HASHMAP_H_
#define V8_BASE_HASHMAP_H_
11

12 13
#include <stdlib.h>

14
#include "src/base/bits.h"
15
#include "src/base/hashmap-entry.h"
16
#include "src/base/logging.h"
17
#include "src/base/platform/wrappers.h"
18

19
namespace v8 {
lpy's avatar
lpy committed
20 21 22 23
namespace base {

class DefaultAllocationPolicy {
 public:
24 25
  template <typename T, typename TypeTag = T[]>
  V8_INLINE T* NewArray(size_t length) {
26
    return static_cast<T*>(base::Malloc(length * sizeof(T)));
27 28 29
  }
  template <typename T, typename TypeTag = T[]>
  V8_INLINE void DeleteArray(T* p, size_t length) {
30
    base::Free(p);
31
  }
lpy's avatar
lpy committed
32
};
33

34
template <typename Key, typename Value, class MatchFun, class AllocationPolicy>
35
class TemplateHashMapImpl {
36
 public:
37
  using Entry = TemplateHashMapEntry<Key, Value>;
38

39 40 41 42 43
  // 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;

44 45
  // initial_capacity is the size of the initial hash map;
  // it must be a power of 2 (and thus must not be 0).
46 47 48
  explicit TemplateHashMapImpl(uint32_t capacity = kDefaultHashMapCapacity,
                               MatchFun match = MatchFun(),
                               AllocationPolicy allocator = AllocationPolicy());
49

50 51 52
  TemplateHashMapImpl(const TemplateHashMapImpl&) = delete;
  TemplateHashMapImpl& operator=(const TemplateHashMapImpl&) = delete;

53
  // Clones the given hashmap and creates a copy with the same entries.
54 55 56
  explicit TemplateHashMapImpl(const TemplateHashMapImpl* original,
                               AllocationPolicy allocator = AllocationPolicy());

57
  TemplateHashMapImpl(TemplateHashMapImpl&& other) V8_NOEXCEPT = default;
58

59
  ~TemplateHashMapImpl();
60

61 62
  TemplateHashMapImpl& operator=(TemplateHashMapImpl&& other)
      V8_NOEXCEPT = default;
63

64
  // If an entry with matching key is found, returns that entry.
65 66
  // Otherwise, nullptr is returned.
  Entry* Lookup(const Key& key, uint32_t hash) const;
67 68 69

  // If an entry with matching key is found, returns that entry.
  // If no matching entry is found, a new entry is inserted with
70
  // corresponding key, key hash, and default initialized value.
71
  Entry* LookupOrInsert(const Key& key, uint32_t hash);
72

73 74 75 76
  // 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 value created by func.
  template <typename Func>
77
  Entry* LookupOrInsert(const Key& key, uint32_t hash, const Func& value_func);
78

79 80 81 82 83 84 85 86 87 88 89 90 91 92
  // Heterogeneous version of LookupOrInsert, which allows a
  // different lookup key type than the hashmap's key type.
  // The requirement is that MatchFun has an overload:
  //
  //   operator()(const LookupKey& lookup_key, const Key& entry_key)
  //
  // If an entry with matching key is found, returns that entry.
  // If no matching entry is found, a new entry is inserted with
  // a key created by key_func, key hash, and value created by
  // value_func.
  template <typename LookupKey, typename KeyFunc, typename ValueFunc>
  Entry* LookupOrInsert(const LookupKey& lookup_key, uint32_t hash,
                        const KeyFunc& key_func, const ValueFunc& value_func);

93
  Entry* InsertNew(const Key& key, uint32_t hash);
94

95
  // Removes the entry with matching key.
96 97
  // It returns the value of the deleted entry
  // or null if there is no value for such key.
98
  Value Remove(const Key& key, uint32_t hash);
99

100 101 102
  // Empties the hash map (occupancy() == 0).
  void Clear();

103 104
  // Empties the map and makes it unusable for allocation.
  void Invalidate() {
105 106
    DCHECK_NOT_NULL(impl_.map_);
    impl_.allocator().DeleteArray(impl_.map_, capacity());
107
    impl_ = Impl(impl_.match(), AllocationPolicy());
108 109
  }

110
  // The number of (non-empty) entries in the table.
111
  uint32_t occupancy() const { return impl_.occupancy_; }
112 113 114 115

  // The capacity of the table. The implementation
  // makes sure that occupancy is at most 80% of
  // the table capacity.
116
  uint32_t capacity() const { return impl_.capacity_; }
117 118 119

  // Iteration
  //
120
  // for (Entry* p = map.Start(); p != nullptr; p = map.Next(p)) {
121 122 123 124 125 126
  //   ...
  // }
  //
  // If entries are inserted during iteration, the effect of
  // calling Next() is undefined.
  Entry* Start() const;
127
  Entry* Next(Entry* entry) const;
128

129
  AllocationPolicy allocator() const { return impl_.allocator(); }
130 131

 protected:
132
  void Initialize(uint32_t capacity);
133

134
 private:
135
  Entry* map_end() const { return impl_.map_ + impl_.capacity_; }
136 137
  template <typename LookupKey>
  Entry* Probe(const LookupKey& key, uint32_t hash) const;
138
  Entry* FillEmptyEntry(Entry* entry, const Key& key, const Value& value,
139 140
                        uint32_t hash);
  void Resize();
141

142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
  // To support matcher and allocator that may not be possible to
  // default-construct, we have to store their instances. Using this to store
  // all internal state of the hash map and using private inheritance to store
  // matcher and allocator lets us take advantage of an empty base class
  // optimization to avoid extra space in the common case when MatchFun and
  // AllocationPolicy have no state.
  // TODO(ishell): Once we reach C++20, consider removing the Impl struct and
  // adding match and allocator as [[no_unique_address]] fields.
  struct Impl : private MatchFun, private AllocationPolicy {
    Impl(MatchFun match, AllocationPolicy allocator)
        : MatchFun(std::move(match)), AllocationPolicy(std::move(allocator)) {}

    Impl() = default;
    Impl(const Impl&) V8_NOEXCEPT = default;
    Impl(Impl&& other) V8_NOEXCEPT { *this = std::move(other); }

    Impl& operator=(const Impl& other) V8_NOEXCEPT = default;
    Impl& operator=(Impl&& other) V8_NOEXCEPT {
      MatchFun::operator=(std::move(other));
      AllocationPolicy::operator=(std::move(other));
      map_ = other.map_;
      capacity_ = other.capacity_;
      occupancy_ = other.occupancy_;

      other.map_ = nullptr;
      other.capacity_ = 0;
      other.occupancy_ = 0;
      return *this;
    }

    const MatchFun& match() const { return *this; }
    MatchFun& match() { return *this; }

    const AllocationPolicy& allocator() const { return *this; }
    AllocationPolicy& allocator() { return *this; }

    Entry* map_ = nullptr;
    uint32_t capacity_ = 0;
    uint32_t occupancy_ = 0;
  } impl_;
182
};
183 184 185
template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::
186
    TemplateHashMapImpl(uint32_t initial_capacity, MatchFun match,
187
                        AllocationPolicy allocator)
188
    : impl_(std::move(match), std::move(allocator)) {
189
  Initialize(initial_capacity);
190 191
}

192 193 194
template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::
195
    TemplateHashMapImpl(const TemplateHashMapImpl* original,
196
                        AllocationPolicy allocator)
197 198 199
    : impl_(original->impl_.match(), std::move(allocator)) {
  impl_.capacity_ = original->capacity();
  impl_.occupancy_ = original->occupancy();
200
  impl_.map_ = impl_.allocator().template NewArray<Entry>(capacity());
201
  memcpy(impl_.map_, original->impl_.map_, capacity() * sizeof(Entry));
202 203
}

204 205 206 207
template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
TemplateHashMapImpl<Key, Value, MatchFun,
                    AllocationPolicy>::~TemplateHashMapImpl() {
208
  if (impl_.map_) impl_.allocator().DeleteArray(impl_.map_, capacity());
209 210
}

211 212 213 214 215
template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Lookup(
    const Key& key, uint32_t hash) const {
216 217
  Entry* entry = Probe(key, hash);
  return entry->exists() ? entry : nullptr;
218 219
}

220 221 222 223
template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert(
224 225
    const Key& key, uint32_t hash) {
  return LookupOrInsert(key, hash, []() { return Value(); });
226 227 228 229 230 231 232
}

template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
template <typename Func>
typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert(
233
    const Key& key, uint32_t hash, const Func& value_func) {
234 235 236 237 238 239 240 241 242 243 244
  return LookupOrInsert(
      key, hash, [&key]() { return key; }, value_func);
}

template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
template <typename LookupKey, typename KeyFunc, typename ValueFunc>
typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert(
    const LookupKey& lookup_key, uint32_t hash, const KeyFunc& key_func,
    const ValueFunc& value_func) {
245
  // Find a matching entry.
246
  Entry* entry = Probe(lookup_key, hash);
247 248
  if (entry->exists()) {
    return entry;
249 250
  }

251
  return FillEmptyEntry(entry, key_func(), value_func(), hash);
252 253
}

254 255 256 257
template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::InsertNew(
258
    const Key& key, uint32_t hash) {
259
  Entry* entry = Probe(key, hash);
260
  return FillEmptyEntry(entry, key, Value(), hash);
261 262
}

263 264 265 266
template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
Value TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Remove(
    const Key& key, uint32_t hash) {
267 268
  // Lookup the entry for the key to remove.
  Entry* p = Probe(key, hash);
269
  if (!p->exists()) {
270
    // Key not found nothing to remove.
271
    return nullptr;
272 273
  }

274
  Value value = p->value;
275 276 277 278 279 280 281 282 283 284 285 286 287 288
  // 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.
289
  DCHECK(occupancy() < capacity());
290 291 292 293 294 295 296

  // 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()) {
297
      q = impl_.map_;
298 299 300 301 302
    }

    // 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.
303
    if (!q->exists()) {
304 305 306 307
      break;
    }

    // Find the initial position for the entry at position q.
308
    Entry* r = impl_.map_ + (q->hash & (capacity() - 1));
309 310 311 312

    // 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.
lpy's avatar
lpy committed
313
    if ((q > p && (r <= p || r > q)) || (q < p && (r <= p && r > q))) {
314 315 316 317 318 319
      *p = *q;
      p = q;
    }
  }

  // Clear the entry which is allowed to en emptied.
320
  p->clear();
321
  impl_.occupancy_--;
322
  return value;
323 324
}

325 326 327
template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Clear() {
328
  // Mark all entries as empty.
329 330
  for (size_t i = 0; i < capacity(); ++i) {
    impl_.map_[i].clear();
331
  }
332
  impl_.occupancy_ = 0;
333 334
}

335 336 337 338
template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Start() const {
339
  return Next(impl_.map_ - 1);
340 341
}

342 343 344 345 346
template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Next(
    Entry* entry) const {
347
  const Entry* end = map_end();
348
  DCHECK(impl_.map_ - 1 <= entry && entry < end);
349 350 351
  for (entry++; entry < end; entry++) {
    if (entry->exists()) {
      return entry;
352 353
    }
  }
354
  return nullptr;
355 356
}

357 358
template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
359
template <typename LookupKey>
360 361
typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Probe(
362
    const LookupKey& key, uint32_t hash) const {
363 364 365 366 367 368 369 370 371
  DCHECK(base::bits::IsPowerOfTwo(capacity()));
  size_t i = hash & (capacity() - 1);
  DCHECK(i < capacity());

  DCHECK(occupancy() < capacity());  // Guarantees loop termination.
  Entry* map = impl_.map_;
  while (map[i].exists() &&
         !impl_.match()(hash, map[i].hash, key, map[i].key)) {
    i = (i + 1) & (capacity() - 1);
372 373
  }

374
  return &map[i];
375 376
}

377 378 379 380
template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::FillEmptyEntry(
381
    Entry* entry, const Key& key, const Value& value, uint32_t hash) {
382 383 384
  DCHECK(!entry->exists());

  new (entry) Entry(key, value, hash);
385
  impl_.occupancy_++;
386 387

  // Grow the map if we reached >= 80% occupancy.
388
  if (occupancy() + occupancy() / 4 >= capacity()) {
389
    Resize();
390 391 392 393
    entry = Probe(key, hash);
  }

  return entry;
394 395
}

396 397 398
template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Initialize(
399
    uint32_t capacity) {
400
  DCHECK(base::bits::IsPowerOfTwo(capacity));
401
  impl_.map_ = impl_.allocator().template NewArray<Entry>(capacity);
402
  if (impl_.map_ == nullptr) {
lpy's avatar
lpy committed
403
    FATAL("Out of memory: HashMap::Initialize");
404 405
    return;
  }
406
  impl_.capacity_ = capacity;
407 408 409
  Clear();
}

410 411
template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
412
void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Resize() {
413 414
  Entry* old_map = impl_.map_;
  uint32_t old_capacity = capacity();
415
  uint32_t n = occupancy();
416 417

  // Allocate larger map.
418
  Initialize(capacity() * 2);
419 420

  // Rehash all current entries.
421
  for (Entry* entry = old_map; n > 0; entry++) {
422 423
    if (entry->exists()) {
      Entry* new_entry = Probe(entry->key, entry->hash);
424 425
      new_entry =
          FillEmptyEntry(new_entry, entry->key, entry->value, entry->hash);
426 427 428 429 430
      n--;
    }
  }

  // Delete old map.
431
  impl_.allocator().DeleteArray(old_map, old_capacity);
432
}
433

434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449
// Match function which compares hashes before executing a (potentially
// expensive) key comparison.
template <typename Key, typename MatchFun>
struct HashEqualityThenKeyMatcher {
  explicit HashEqualityThenKeyMatcher(MatchFun match) : match_(match) {}

  bool operator()(uint32_t hash1, uint32_t hash2, const Key& key1,
                  const Key& key2) const {
    return hash1 == hash2 && match_(key1, key2);
  }

 private:
  MatchFun match_;
};

// Hashmap<void*, void*> which takes a custom key comparison function pointer.
450
template <typename AllocationPolicy>
451
class CustomMatcherTemplateHashMapImpl
452 453 454 455
    : public TemplateHashMapImpl<
          void*, void*,
          HashEqualityThenKeyMatcher<void*, bool (*)(void*, void*)>,
          AllocationPolicy> {
456
  using Base = TemplateHashMapImpl<
457
      void*, void*, HashEqualityThenKeyMatcher<void*, bool (*)(void*, void*)>,
458
      AllocationPolicy>;
459 460

 public:
461
  using MatchFun = bool (*)(void*, void*);
462

463
  explicit CustomMatcherTemplateHashMapImpl(
464 465
      MatchFun match, uint32_t capacity = Base::kDefaultHashMapCapacity,
      AllocationPolicy allocator = AllocationPolicy())
466 467
      : Base(capacity, HashEqualityThenKeyMatcher<void*, MatchFun>(match),
             allocator) {}
468

469
  explicit CustomMatcherTemplateHashMapImpl(
470
      const CustomMatcherTemplateHashMapImpl* original,
471 472 473
      AllocationPolicy allocator = AllocationPolicy())
      : Base(original, allocator) {}

474 475 476 477
  CustomMatcherTemplateHashMapImpl(const CustomMatcherTemplateHashMapImpl&) =
      delete;
  CustomMatcherTemplateHashMapImpl& operator=(
      const CustomMatcherTemplateHashMapImpl&) = delete;
478 479
};

480 481
using CustomMatcherHashMap =
    CustomMatcherTemplateHashMapImpl<DefaultAllocationPolicy>;
482

483 484 485 486 487 488 489 490 491 492
// Match function which compares keys directly by equality.
template <typename Key>
struct KeyEqualityMatcher {
  bool operator()(uint32_t hash1, uint32_t hash2, const Key& key1,
                  const Key& key2) const {
    return key1 == key2;
  }
};

// Hashmap<void*, void*> which compares the key pointers directly.
493 494
template <typename AllocationPolicy>
class PointerTemplateHashMapImpl
495
    : public TemplateHashMapImpl<void*, void*, KeyEqualityMatcher<void*>,
496
                                 AllocationPolicy> {
497 498
  using Base = TemplateHashMapImpl<void*, void*, KeyEqualityMatcher<void*>,
                                   AllocationPolicy>;
499

500
 public:
501 502 503
  explicit PointerTemplateHashMapImpl(
      uint32_t capacity = Base::kDefaultHashMapCapacity,
      AllocationPolicy allocator = AllocationPolicy())
504
      : Base(capacity, KeyEqualityMatcher<void*>(), allocator) {}
505 506 507 508 509 510 511 512 513 514 515 516 517

  PointerTemplateHashMapImpl(const PointerTemplateHashMapImpl& other,
                             AllocationPolicy allocator = AllocationPolicy())
      : Base(&other, allocator) {}

  PointerTemplateHashMapImpl(PointerTemplateHashMapImpl&& other) V8_NOEXCEPT
      : Base(std::move(other)) {}

  PointerTemplateHashMapImpl& operator=(PointerTemplateHashMapImpl&& other)
      V8_NOEXCEPT {
    static_cast<Base&>(*this) = std::move(other);
    return *this;
  }
518 519
};

520
using HashMap = PointerTemplateHashMapImpl<DefaultAllocationPolicy>;
521

522
// A hash map for pointer keys and values with an STL-like interface.
523 524
template <class Key, class Value, class MatchFun, class AllocationPolicy>
class TemplateHashMap
525 526 527
    : private TemplateHashMapImpl<void*, void*,
                                  HashEqualityThenKeyMatcher<void*, MatchFun>,
                                  AllocationPolicy> {
528 529 530
  using Base = TemplateHashMapImpl<void*, void*,
                                   HashEqualityThenKeyMatcher<void*, MatchFun>,
                                   AllocationPolicy>;
531

532
 public:
533 534
  STATIC_ASSERT(sizeof(Key*) == sizeof(void*));
  STATIC_ASSERT(sizeof(Value*) == sizeof(void*));
535 536 537 538 539 540 541 542 543 544 545 546 547
  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_); }
lpy's avatar
lpy committed
548
    bool operator!=(const Iterator& other) { return entry_ != other.entry_; }
549 550

   private:
551
    Iterator(const Base* map, typename Base::Entry* entry)
lpy's avatar
lpy committed
552
        : map_(map), entry_(entry) {}
553

554 555
    const Base* map_;
    typename Base::Entry* entry_;
556 557 558 559

    friend class TemplateHashMap;
  };

560 561
  explicit TemplateHashMap(MatchFun match,
                           AllocationPolicy allocator = AllocationPolicy())
562 563
      : Base(Base::kDefaultHashMapCapacity,
             HashEqualityThenKeyMatcher<void*, MatchFun>(match), allocator) {}
564 565

  Iterator begin() const { return Iterator(this, this->Start()); }
566
  Iterator end() const { return Iterator(this, nullptr); }
567
  Iterator find(Key* key, bool insert = false) {
568
    if (insert) {
569
      return Iterator(this, this->LookupOrInsert(key, key->Hash()));
570 571
    }
    return Iterator(this, this->Lookup(key, key->Hash()));
572 573 574
  }
};

lpy's avatar
lpy committed
575
}  // namespace base
576
}  // namespace v8
577

lpy's avatar
lpy committed
578
#endif  // V8_BASE_HASHMAP_H_