chromium/v8/src/base/hashmap.h

// Copyright 2012 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// 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_

#include <stdlib.h>

#include "src/base/bits.h"
#include "src/base/hashmap-entry.h"
#include "src/base/logging.h"
#include "src/base/platform/memory.h"

namespace v8 {
namespace base {

class DefaultAllocationPolicy { … };

template <typename Key, typename Value, class MatchFun, class AllocationPolicy>
class TemplateHashMapImpl { … };
template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::
    TemplateHashMapImpl(uint32_t initial_capacity, MatchFun match,
                        AllocationPolicy allocator)
    : … { … }

template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::
    TemplateHashMapImpl(const TemplateHashMapImpl* original,
                        AllocationPolicy allocator)
    : … { … }

template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
TemplateHashMapImpl<Key, Value, MatchFun,
                    AllocationPolicy>::~TemplateHashMapImpl() { … }

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 { … }

template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert(
    const Key& key, uint32_t hash) { … }

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(
    const Key& key, uint32_t hash, const Func& 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) { … }

template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::InsertNew(
    const Key& key, uint32_t hash) { … }

template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
Value TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Remove(
    const Key& key, uint32_t hash) { … }

template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Clear() { … }

template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Start() const { … }

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 { … }

template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
template <typename LookupKey>
typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Probe(
    const LookupKey& key, uint32_t hash) const { … }

template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::FillEmptyEntry(
    Entry* entry, const Key& key, const Value& value, uint32_t hash) { … }

template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Initialize(
    uint32_t capacity) { … }

template <typename Key, typename Value, typename MatchFun,
          class AllocationPolicy>
void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Resize() { … }

// Match function which compares hashes before executing a (potentially
// expensive) key comparison.
template <typename Key, typename MatchFun>
struct HashEqualityThenKeyMatcher { … };

// Hashmap<void*, void*> which takes a custom key comparison function pointer.
template <typename AllocationPolicy>
class CustomMatcherTemplateHashMapImpl
    : public TemplateHashMapImpl<
          void*, void*,
          HashEqualityThenKeyMatcher<void*, bool (*)(void*, void*)>,
          AllocationPolicy> { … };

CustomMatcherHashMap;

// Match function which compares keys directly by equality.
template <typename Key>
struct KeyEqualityMatcher { … };

// Hashmap<void*, void*> which compares the key pointers directly.
template <typename AllocationPolicy>
class PointerTemplateHashMapImpl
    : public TemplateHashMapImpl<void*, void*, KeyEqualityMatcher<void*>,
                                 AllocationPolicy> { … };

HashMap;

// A hash map for pointer keys and values with an STL-like interface.
template <class Key, class Value, class MatchFun, class AllocationPolicy>
class TemplateHashMap
    : private TemplateHashMapImpl<void*, void*,
                                  HashEqualityThenKeyMatcher<void*, MatchFun>,
                                  AllocationPolicy> { … };

}  // namespace base
}  // namespace v8

#endif  // V8_BASE_HASHMAP_H_