blob: b690ace86aa13fbdba8ad72fc1b5b4dcc4408d34 [file] [log] [blame]
// Copyright 2021 The Chromium 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 SRC_GN_POINTER_SET_H_
#define SRC_GN_POINTER_SET_H_
#include <functional>
#include "gn/hash_table_base.h"
// PointerSet<T> is a fast implemention of a set of non-owning and non-null
// typed pointer values (of type T*).
//
// Note that this intentionally does not support a find() method
// for performance reasons, instead callers must use contains(), add()
// or erase() directly to perform lookups or conditional insertion/removal.
//
// Only constant iterators are provided. Moreover, the slightly faster
// iteration form can be used for performance as in:
//
// for (auto it = my_set.begin(); it.valid(); ++it) {
// T* ptr = *it;
// ...
// }
//
// Instead of:
//
// for (T* ptr : my_set) {
// ...
// }
//
// The PointerSetNode type implements the methods required by HashTableBase<>
// to store and hash a pointer directly in the buckets array. The special
// address 1 is used as the tombstone value to support removal.
//
// Null nodes are marked with an empty pointer, which means that nullptr
// itself cannot be stored in the set.
struct PointerSetNode {
const void* ptr_;
bool is_null() const { return !ptr_; }
bool is_tombstone() const { return ptr_ == MakeTombstone(); }
bool is_valid() const { return !is_null() && !is_tombstone(); }
size_t hash_value() const { return MakeHash(ptr_); }
// Return the tomebstone value. This could be a static constexpr value
// if C++ didn't complain about reinterpret_cast<> here.
static const void* MakeTombstone() {
return reinterpret_cast<const void*>(1u);
}
// Return the hash corresponding to a given pointer.
static size_t MakeHash(const void* ptr) {
return std::hash<const void*>()(ptr);
}
};
template <typename T>
class PointerSet : public HashTableBase<PointerSetNode> {
public:
using NodeType = PointerSetNode;
using BaseType = HashTableBase<NodeType>;
PointerSet() = default;
// Allow copying pointer sets.
PointerSet(const PointerSet& other) { insert(other); }
PointerSet& operator=(const PointerSet& other) {
if (this != &other) {
this->~PointerSet();
new (this) PointerSet(other);
}
return *this;
}
// Redefine move operators since the copy constructor above
// masks the base ones by default.
PointerSet(PointerSet&& other) noexcept : BaseType(std::move(other)) {}
PointerSet& operator=(PointerSet&& other) noexcept {
if (this != &other) {
this->~PointerSet();
new (this) PointerSet(std::move(other));
}
return *this;
}
// Range constructor.
template <typename InputIter>
PointerSet(InputIter first, InputIter last) {
for (; first != last; ++first)
add(*first);
}
// Clear the set.
void clear() { NodeClear(); }
// Add one pointer to the set. Return true if the pointer was
// added, or false if its was already in the set.
bool add(T* ptr) {
NodeType* node = Lookup(ptr);
if (node->is_valid())
return false;
node->ptr_ = ptr;
UpdateAfterInsert();
return true;
}
// Return true if a given pointer is already in the set.
bool contains(T* ptr) const { return Lookup(ptr)->is_valid(); }
// Try to remove a pointer from the set. Return true in case of
// removal, or false if the pointer was not in the set.
bool erase(T* ptr) {
NodeType* node = Lookup(ptr);
if (!node->is_valid())
return false;
node->ptr_ = node->MakeTombstone();
UpdateAfterRemoval();
return true;
}
// Same as add() but does not return a boolean.
// This minimizes code changes when PointerSet<> replaces
// other standard set types in the code.
void insert(T* ptr) { add(ptr); }
// Range insertion.
template <typename InputIter>
void insert(InputIter first, InputIter last) {
for (; first != last; ++first)
add(*first);
}
// Insert of aitems of |other| into the current set. This
// is slightly more efficient than using range insertion
// with insert(other.begin(), other.end()).
void insert(const PointerSet& other) {
for (const_iterator iter = other.begin(); iter.valid(); ++iter)
add(*iter);
}
// Return a new set that is the intersection of the current one
// and |other|.
PointerSet intersection_with(const PointerSet& other) const {
PointerSet result;
for (const_iterator iter = other.begin(); iter.valid(); ++iter) {
if (contains(*iter))
result.add(*iter);
}
return result;
}
// Only provide const interators for pointer sets.
struct const_iterator : public NodeIterator {
T* const* operator->() const {
return &const_cast<T*>(static_cast<const T*>(node_->ptr_));
}
T* operator*() const {
return const_cast<T*>(static_cast<const T*>(node_->ptr_));
}
// The following allows:
// std::vector<T*> vector(set.begin(), set.end());
using iterator_category = std::forward_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = T*;
using pointer = T**;
using reference = T*&;
};
const_iterator begin() const { return {NodeBegin()}; }
const_iterator end() const { return {NodeEnd()}; }
// Only used for unit-tests so performance is not critical.
bool operator==(const PointerSet& other) const {
if (size() != other.size())
return false;
for (const_iterator iter = begin(); iter.valid(); ++iter)
if (!other.contains(*iter))
return false;
for (const_iterator iter = other.begin(); iter.valid(); ++iter)
if (!contains(*iter))
return false;
return true;
}
private:
// Lookup node matching a given pointer. If result->valid() is true
// then the pointer was found, otherwise, this is the location of
// the best place to insert it.
NodeType* Lookup(T* ptr) const {
size_t hash = NodeType::MakeHash(ptr);
return NodeLookup(hash, [&](NodeType* node) { return node->ptr_ == ptr; });
}
};
#endif // SRC_GN_POINTER_SET_H_