blob: 57bdb97b63df1c69650bcf0a04764f7b4e6de2c4 [file] [log] [blame] [edit]
// Copyright 2016 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef FBL_INTRUSIVE_HASH_TABLE_H_
#define FBL_INTRUSIVE_HASH_TABLE_H_
#include <zircon/assert.h>
#include <utility>
#include <fbl/intrusive_container_utils.h>
#include <fbl/intrusive_pointer_traits.h>
#include <fbl/intrusive_single_list.h>
#include <fbl/macros.h>
namespace fbl {
// Fwd decl of sanity checker class used by tests.
namespace tests {
namespace intrusive_containers {
class HashTableChecker;
} // namespace intrusive_containers
} // namespace tests
namespace internal {
inline constexpr size_t kDefaultNumBuckets = 37;
} // namespace internal
// DefaultHashTraits defines a default implementation of traits used to
// define the hash function for a hash table.
//
// At a minimum, a class or a struct which is to be used to define the
// hash traits of a hashtable must define...
//
// GetHash : A static method which take a constant reference to an instance of
// the container's KeyType and returns an instance of the container's
// HashType representing the hashed value of the key. The value must
// be on the range from [0, Container::kNumBuckets - 1]
//
// DefaultHashTraits generates a compliant implementation of hash traits taking
// its KeyType, ObjType, HashType and NumBuckets from template parameters.
// Users of DefaultHashTraits only need to implement a static method of ObjType
// named GetHash which takes a const reference to a KeyType and returns a
// HashType. The default implementation will automatically mod by the number of
// buckets given in the template parameters. If the user's hash function
// already automatically guarantees that the returned hash value will be in the
// proper range, he/she should implement their own hash traits to avoid the
// extra div/mod operation.
template <typename KeyType, typename ObjType, typename HashType, HashType kNumBuckets>
struct DefaultHashTraits {
static_assert(std::is_unsigned_v<HashType>, "HashTypes must be unsigned integers");
static HashType GetHash(const KeyType& key) {
return static_cast<HashType>(ObjType::GetHash(key) % kNumBuckets);
}
};
template <typename _KeyType, typename _PtrType, typename _BucketType = SinglyLinkedList<_PtrType>,
typename _HashType = size_t, _HashType _NumBuckets = internal::kDefaultNumBuckets,
typename _KeyTraits = DefaultKeyedObjectTraits<
_KeyType, typename internal::ContainerPtrTraits<_PtrType>::ValueType>,
typename _HashTraits = DefaultHashTraits<
_KeyType, typename internal::ContainerPtrTraits<_PtrType>::ValueType, _HashType,
_NumBuckets>>
class __POINTER(_KeyType) HashTable {
private:
// Private fwd decls of the iterator implementation.
template <typename IterTraits>
class iterator_impl;
struct iterator_traits;
struct const_iterator_traits;
public:
// Pointer types/traits
using PtrType = _PtrType;
using PtrTraits = internal::ContainerPtrTraits<PtrType>;
using ValueType = typename PtrTraits::ValueType;
using RefType = typename PtrTraits::RefType;
// Key types/traits
using KeyType = _KeyType;
using KeyTraits = _KeyTraits;
// Hash types/traits
using HashType = _HashType;
using HashTraits = _HashTraits;
// Bucket types/traits
using BucketType = _BucketType;
using NodeTraits = typename BucketType::NodeTraits;
// Declarations of the standard iterator types.
using iterator = iterator_impl<iterator_traits>;
using const_iterator = iterator_impl<const_iterator_traits>;
// An alias for the type of this specific HashTable<...> and its test sanity checker.
using ContainerType =
HashTable<_KeyType, _PtrType, _BucketType, _HashType, _NumBuckets, _KeyTraits, _HashTraits>;
using CheckerType = ::fbl::tests::intrusive_containers::HashTableChecker;
// The number of buckets should be a nice prime such as 37, 211, 389 unless
// The hash function is really good. Lots of cheap hash functions have
// hidden periods for which the mod with prime above 'mostly' fixes.
static constexpr HashType kNumBuckets = _NumBuckets;
// Hash tables only support constant order erase if their underlying bucket
// type does.
static constexpr bool SupportsConstantOrderErase = BucketType::SupportsConstantOrderErase;
static constexpr bool SupportsConstantOrderSize = true;
static constexpr bool IsAssociative = true;
static constexpr bool IsSequenced = false;
static_assert(kNumBuckets > 0, "Hash tables must have at least one bucket");
static_assert(std::is_unsigned_v<HashType>, "HashTypes must be unsigned integers");
constexpr HashTable() noexcept {
using NodeState = internal::node_state_t<NodeTraits, RefType>;
// Make certain that the type of pointer we are expected to manage matches
// the type of pointer that our Node type expects to manage. In theory, our
// bucket has already performed this check for us, but extra sanity checks
// are always welcome.
static_assert(std::is_same_v<PtrType, typename NodeState::PtrType>,
"SinglyLinkedList's pointer type must match its Node's pointerType");
// HashTable does not currently support direct remove-from-container (but
// could do so if it did not track size)
static_assert(!(NodeState::kNodeOptions & NodeOptions::AllowRemoveFromContainer),
"HashTable does not support nodes which allow RemoveFromContainer.");
}
~HashTable() { ZX_DEBUG_ASSERT(PtrTraits::IsManaged || is_empty()); }
// Standard begin/end, cbegin/cend iterator accessors.
iterator begin() { return iterator(this, iterator::BEGIN); }
const_iterator begin() const { return const_iterator(this, const_iterator::BEGIN); }
const_iterator cbegin() const { return const_iterator(this, const_iterator::BEGIN); }
iterator end() { return iterator(this, iterator::END); }
const_iterator end() const { return const_iterator(this, const_iterator::END); }
const_iterator cend() const { return const_iterator(this, const_iterator::END); }
// make_iterator : construct an iterator out of a reference to an object.
iterator make_iterator(ValueType& obj) {
HashType ndx = GetHash(KeyTraits::GetKey(obj));
return iterator(this, ndx, buckets_[ndx].make_iterator(obj));
}
const_iterator make_iterator(const ValueType& obj) const {
HashType ndx = GetHash(KeyTraits::GetKey(obj));
return const_iterator(this, ndx, buckets_[ndx].make_iterator(obj));
}
void insert(const PtrType& ptr) { insert(PtrType(ptr)); }
void insert(PtrType&& ptr) {
ZX_DEBUG_ASSERT(ptr != nullptr);
KeyType key = KeyTraits::GetKey(*ptr);
BucketType& bucket = GetBucket(key);
// Duplicate keys are disallowed. Debug assert if someone tries to to
// insert an element with a duplicate key. If the user thought that
// there might be a duplicate key in the HashTable already, he/she
// should have used insert_or_find() instead.
ZX_DEBUG_ASSERT(FindInBucket(bucket, key).IsValid() == false);
bucket.push_front(std::move(ptr));
++count_;
}
// insert_or_find
//
// Insert the element pointed to by ptr if it is not already in the
// HashTable, or find the element that the ptr collided with instead.
//
// 'iter' is an optional out parameter pointer to an iterator which
// will reference either the newly inserted item, or the item whose key
// collided with ptr.
//
// insert_or_find returns true if there was no collision and the item was
// successfully inserted, otherwise it returns false.
//
bool insert_or_find(const PtrType& ptr, iterator* iter = nullptr) {
return insert_or_find(PtrType(ptr), iter);
}
bool insert_or_find(PtrType&& ptr, iterator* iter = nullptr) {
ZX_DEBUG_ASSERT(ptr != nullptr);
KeyType key = KeyTraits::GetKey(*ptr);
HashType ndx = GetHash(key);
auto& bucket = buckets_[ndx];
auto bucket_iter = FindInBucket(bucket, key);
if (bucket_iter.IsValid()) {
if (iter)
*iter = iterator(this, ndx, bucket_iter);
return false;
}
bucket.push_front(std::move(ptr));
++count_;
if (iter)
*iter = iterator(this, ndx, bucket.begin());
return true;
}
// insert_or_replace
//
// Find the element in the hashtable with the same key as *ptr and replace
// it with ptr, then return the pointer to the element which was replaced.
// If no element in the hashtable shares a key with *ptr, simply add ptr to
// the hashtable and return nullptr.
//
PtrType insert_or_replace(const PtrType& ptr) { return insert_or_replace(PtrType(ptr)); }
PtrType insert_or_replace(PtrType&& ptr) {
ZX_DEBUG_ASSERT(ptr != nullptr);
KeyType key = KeyTraits::GetKey(*ptr);
HashType ndx = GetHash(key);
auto& bucket = buckets_[ndx];
auto orig = PtrTraits::GetRaw(ptr);
PtrType replaced = bucket.replace_if(
[key](const ValueType& other) -> bool {
return KeyTraits::EqualTo(key, KeyTraits::GetKey(other));
},
std::move(ptr));
if (orig == PtrTraits::GetRaw(replaced)) {
bucket.push_front(std::move(replaced));
count_++;
return nullptr;
}
return replaced;
}
iterator find(const KeyType& key) {
HashType ndx = GetHash(key);
auto& bucket = buckets_[ndx];
auto bucket_iter = FindInBucket(bucket, key);
return bucket_iter.IsValid() ? iterator(this, ndx, bucket_iter) : iterator(this, iterator::END);
}
const_iterator find(const KeyType& key) const {
HashType ndx = GetHash(key);
const auto& bucket = buckets_[ndx];
auto bucket_iter = FindInBucket(bucket, key);
return bucket_iter.IsValid() ? const_iterator(this, ndx, bucket_iter)
: const_iterator(this, const_iterator::END);
}
PtrType erase(const KeyType& key) {
BucketType& bucket = GetBucket(key);
PtrType ret = internal::KeyEraseUtils<BucketType, KeyTraits>::erase(bucket, key);
if (ret != nullptr)
--count_;
return ret;
}
PtrType erase(const iterator& iter) {
if (!iter.IsValid())
return PtrType(nullptr);
return direct_erase(buckets_[iter.bucket_ndx_], *iter);
}
PtrType erase(ValueType& obj) { return direct_erase(GetBucket(obj), obj); }
// clear
//
// Clear out the all of the hashtable buckets. For managed pointer types,
// this will release all references held by the hashtable to the objects
// which were in it.
void clear() {
for (auto& e : buckets_)
e.clear();
count_ = 0;
}
// clear_unsafe
//
// Perform a clear_unsafe on all buckets and reset the internal count to
// zero. See comments in fbl/intrusive_single_list.h
// Think carefully before calling this!
void clear_unsafe() {
static_assert(PtrTraits::IsManaged == false,
"clear_unsafe is not allowed for containers of managed pointers");
static_assert(NodeTraits::NodeState::kNodeOptions & NodeOptions::AllowClearUnsafe,
"Container does not support clear_unsafe. Consider adding "
"NodeOptions::AllowClearUnsafe to your node storage.");
for (auto& e : buckets_)
e.clear_unsafe();
count_ = 0;
}
size_t size() const { return count_; }
bool is_empty() const { return count_ == 0; }
// erase_if
//
// Find the first member of the hash table which satisfies the predicate
// given by 'fn' and erase it from the list, returning a referenced pointer
// to the removed element. Return nullptr if no member satisfies the
// predicate.
template <typename UnaryFn>
PtrType erase_if(UnaryFn fn) {
if (is_empty())
return PtrType(nullptr);
for (HashType i = 0; i < kNumBuckets; ++i) {
auto& bucket = buckets_[i];
if (!bucket.is_empty()) {
PtrType ret = bucket.erase_if(fn);
if (ret != nullptr) {
--count_;
return ret;
}
}
}
return PtrType(nullptr);
}
// find_if
//
// Find the first member of the hash table which satisfies the predicate
// given by 'fn' and return an iterator to it. Return end() if no member
// satisfies the predicate.
template <typename UnaryFn>
const_iterator find_if(UnaryFn fn) const {
for (auto iter = begin(); iter.IsValid(); ++iter)
if (fn(*iter))
return iter;
return end();
}
template <typename UnaryFn>
iterator find_if(UnaryFn fn) {
for (auto iter = begin(); iter.IsValid(); ++iter)
if (fn(*iter))
return iter;
return end();
}
private:
// The traits of a non-const iterator
struct iterator_traits {
using RefType = typename PtrTraits::RefType;
using RawPtrType = typename PtrTraits::RawPtrType;
using IterType = typename BucketType::iterator;
static IterType BucketBegin(BucketType& bucket) { return bucket.begin(); }
static IterType BucketEnd(BucketType& bucket) { return bucket.end(); }
};
// The traits of a const iterator
struct const_iterator_traits {
using RefType = typename PtrTraits::ConstRefType;
using RawPtrType = typename PtrTraits::ConstRawPtrType;
using IterType = typename BucketType::const_iterator;
static IterType BucketBegin(const BucketType& bucket) { return bucket.cbegin(); }
static IterType BucketEnd(const BucketType& bucket) { return bucket.cend(); }
};
// The shared implementation of the iterator
template <class IterTraits>
class iterator_impl {
public:
iterator_impl() {}
iterator_impl(const iterator_impl& other) {
hash_table_ = other.hash_table_;
bucket_ndx_ = other.bucket_ndx_;
iter_ = other.iter_;
}
iterator_impl& operator=(const iterator_impl& other) {
hash_table_ = other.hash_table_;
bucket_ndx_ = other.bucket_ndx_;
iter_ = other.iter_;
return *this;
}
bool IsValid() const { return iter_.IsValid(); }
bool operator==(const iterator_impl& other) const { return iter_ == other.iter_; }
bool operator!=(const iterator_impl& other) const { return iter_ != other.iter_; }
// Prefix
iterator_impl& operator++() {
if (!IsValid())
return *this;
ZX_DEBUG_ASSERT(hash_table_);
// Bump the bucket iterator and go looking for a new bucket if the
// iterator has become invalid.
++iter_;
advance_if_invalid_iter();
return *this;
}
iterator_impl& operator--() {
// If we have never been bound to a HashTable instance, the we had
// better be invalid.
if (!hash_table_) {
ZX_DEBUG_ASSERT(!IsValid());
return *this;
}
// Back up the bucket iterator. If it is still valid, then we are done.
--iter_;
if (iter_.IsValid())
return *this;
// If the iterator is invalid after backing up, check previous
// buckets to see if they contain any nodes.
while (bucket_ndx_) {
--bucket_ndx_;
auto& bucket = GetBucket(bucket_ndx_);
if (!bucket.is_empty()) {
iter_ = --IterTraits::BucketEnd(bucket);
ZX_DEBUG_ASSERT(iter_.IsValid());
return *this;
}
}
// Looks like we have backed up past the beginning. Update the
// bookkeeping to point at the end of the last bucket.
bucket_ndx_ = kNumBuckets - 1;
iter_ = IterTraits::BucketEnd(GetBucket(bucket_ndx_));
return *this;
}
// Postfix
iterator_impl operator++(int) {
iterator_impl ret(*this);
++(*this);
return ret;
}
iterator_impl operator--(int) {
iterator_impl ret(*this);
--(*this);
return ret;
}
typename PtrTraits::PtrType CopyPointer() const { return iter_.CopyPointer(); }
typename IterTraits::RefType operator*() const { return iter_.operator*(); }
typename IterTraits::RawPtrType operator->() const { return iter_.operator->(); }
private:
friend ContainerType;
using IterType = typename IterTraits::IterType;
enum BeginTag { BEGIN };
enum EndTag { END };
iterator_impl(const ContainerType* hash_table, BeginTag)
: hash_table_(hash_table), bucket_ndx_(0), iter_(IterTraits::BucketBegin(GetBucket(0))) {
advance_if_invalid_iter();
}
iterator_impl(const ContainerType* hash_table, EndTag)
: hash_table_(hash_table),
bucket_ndx_(kNumBuckets - 1),
iter_(IterTraits::BucketEnd(GetBucket(kNumBuckets - 1))) {}
iterator_impl(const ContainerType* hash_table, HashType bucket_ndx, const IterType& iter)
: hash_table_(hash_table), bucket_ndx_(bucket_ndx), iter_(iter) {}
BucketType& GetBucket(HashType ndx) {
return const_cast<ContainerType*>(hash_table_)->buckets_[ndx];
}
void advance_if_invalid_iter() {
// If the iterator has run off the end of it's current bucket, then
// check to see if there are nodes in any of the remaining buckets.
if (!iter_.IsValid()) {
while (bucket_ndx_ < (kNumBuckets - 1)) {
++bucket_ndx_;
auto& bucket = GetBucket(bucket_ndx_);
if (!bucket.is_empty()) {
iter_ = IterTraits::BucketBegin(bucket);
ZX_DEBUG_ASSERT(iter_.IsValid());
break;
} else if (bucket_ndx_ == (kNumBuckets - 1)) {
iter_ = IterTraits::BucketEnd(bucket);
}
}
}
}
const ContainerType* hash_table_ = nullptr;
HashType bucket_ndx_ = 0;
IterType iter_;
};
PtrType direct_erase(BucketType& bucket, ValueType& obj) {
PtrType ret = internal::DirectEraseUtils<BucketType>::erase(bucket, obj);
if (ret != nullptr)
--count_;
return ret;
}
static typename BucketType::iterator FindInBucket(BucketType& bucket, const KeyType& key) {
return bucket.find_if([key](const ValueType& other) -> bool {
return KeyTraits::EqualTo(key, KeyTraits::GetKey(other));
});
}
static typename BucketType::const_iterator FindInBucket(const BucketType& bucket,
const KeyType& key) {
return bucket.find_if([key](const ValueType& other) -> bool {
return KeyTraits::EqualTo(key, KeyTraits::GetKey(other));
});
}
// The test framework's 'checker' class is our friend.
friend CheckerType;
// Iterators need to access our bucket array in order to iterate.
friend iterator;
friend const_iterator;
// Hash tables may not currently be copied, assigned or moved.
DISALLOW_COPY_ASSIGN_AND_MOVE(HashTable);
BucketType& GetBucket(const KeyType& key) { return buckets_[GetHash(key)]; }
BucketType& GetBucket(const ValueType& obj) { return GetBucket(KeyTraits::GetKey(obj)); }
static HashType GetHash(const KeyType& obj) {
HashType ret = HashTraits::GetHash(obj);
ZX_DEBUG_ASSERT((ret >= 0) && (ret < kNumBuckets));
return ret;
}
size_t count_ = 0UL;
BucketType buckets_[kNumBuckets];
};
// TaggedHashTable<> is intended for use with ContainableBaseClasses<>.
//
// For an easy way to allow instances of your class to live in multiple
// intrusive containers at once, simply derive from
// ContainableBaseClasses<YourContainables<PtrType, TagType>...> and then use
// this template instead of HashTable<> as the container, passing the same tag
// type you used earlier as the third parameter.
//
// See comments on ContainableBaseClasses<> in fbl/intrusive_container_utils.h
// for more details.
//
template <typename KeyType, typename PtrType, typename TagType,
typename BucketType = TaggedSinglyLinkedList<PtrType, TagType>,
typename HashType = size_t, HashType NumBuckets = internal::kDefaultNumBuckets,
typename KeyTraits = DefaultKeyedObjectTraits<
KeyType, typename internal::ContainerPtrTraits<PtrType>::ValueType>,
typename HashTraits =
DefaultHashTraits<KeyType, typename internal::ContainerPtrTraits<PtrType>::ValueType,
HashType, NumBuckets>>
using TaggedHashTable =
HashTable<KeyType, PtrType, BucketType, HashType, NumBuckets, KeyTraits, HashTraits>;
// Explicit declaration of constexpr storage.
#define HASH_TABLE_PROP(_type, _name) \
template <typename KeyType, typename PtrType, typename BucketType, typename HashType, \
HashType NumBuckets, typename KeyTraits, typename HashTraits> \
constexpr _type \
HashTable<KeyType, PtrType, BucketType, HashType, NumBuckets, KeyTraits, HashTraits>::_name
HASH_TABLE_PROP(HashType, kNumBuckets);
HASH_TABLE_PROP(bool, SupportsConstantOrderErase);
HASH_TABLE_PROP(bool, SupportsConstantOrderSize);
HASH_TABLE_PROP(bool, IsAssociative);
HASH_TABLE_PROP(bool, IsSequenced);
#undef HASH_TABLE_PROP
} // namespace fbl
#endif // FBL_INTRUSIVE_HASH_TABLE_H_