#ifndef SmallPtrSet_h
#define SmallPtrSet_h
#include <wtf/Assertions.h>
#include <wtf/FastMalloc.h>
#include <wtf/HashFunctions.h>
#include <wtf/Noncopyable.h>
namespace WTF {
template<typename PtrType, unsigned SmallArraySize = 8>
class SmallPtrSet {
WTF_MAKE_NONCOPYABLE(SmallPtrSet);
static_assert(std::is_trivially_destructible<PtrType>::value, "We currently don't support non-trivially destructible pointer types.");
static_assert(sizeof(PtrType) == sizeof(void*), "Only support pointer sized things.");
static_assert(!(SmallArraySize & (SmallArraySize - 1)), "Inline size must be a power of two.");
public:
SmallPtrSet()
{
initialize();
}
SmallPtrSet(SmallPtrSet&& other)
{
memcpy(this, &other, sizeof(SmallPtrSet));
other.initialize();
}
SmallPtrSet& operator=(SmallPtrSet&& other)
{
this->~SmallPtrSet();
new (this) SmallPtrSet(WTFMove(other));
return *this;
}
~SmallPtrSet()
{
if (!isSmall())
fastFree(m_buffer);
}
inline void add(PtrType ptr)
{
ASSERT(isValidEntry(ptr));
if (isSmall()) {
for (unsigned i = 0; i < m_size; i++) {
if (m_smallStorage[i] == ptr)
return;
}
if (m_size < SmallArraySize) {
m_smallStorage[m_size] = ptr;
++m_size;
return;
}
grow(std::max(64u, SmallArraySize * 2));
}
if (UNLIKELY(m_size * 4 >= m_capacity * 3)) {
grow(m_capacity * 2);
ASSERT(!(m_capacity & (m_capacity - 1)));
}
void** bucket = this->bucket(ptr);
if (*bucket != ptr) {
*bucket = ptr;
++m_size;
}
}
inline bool contains(PtrType ptr) const
{
ASSERT(isValidEntry(ptr));
if (isSmall()) {
for (unsigned i = 0; i < m_size; i++) { if (m_smallStorage[i] == ptr)
return true;
}
return false;
}
void** bucket = this->bucket(ptr);
return *bucket == ptr;
}
class iterator {
public:
iterator& operator++()
{
m_index++;
ASSERT(m_index <= m_capacity);
while (m_index < m_capacity && m_buffer[m_index] == emptyValue())
m_index++;
return *this;
}
PtrType operator*() const { ASSERT(m_index < m_capacity); return static_cast<PtrType>(m_buffer[m_index]); }
bool operator==(const iterator& other) const { ASSERT(m_buffer == other.m_buffer); return m_index == other.m_index; }
bool operator!=(const iterator& other) const { ASSERT(m_buffer == other.m_buffer); return !(*this == other); }
private:
template<typename U, unsigned S> friend class WTF::SmallPtrSet;
unsigned m_index;
unsigned m_capacity;
void** m_buffer;
};
iterator begin() const
{
iterator it;
it.m_index = std::numeric_limits<unsigned>::max();
it.m_capacity = m_capacity;
if (isSmall())
it.m_buffer = const_cast<void**>(m_smallStorage);
else
it.m_buffer = m_buffer;
++it;
return it;
}
iterator end() const
{
iterator it;
it.m_index = m_capacity;
it.m_capacity = m_capacity;
if (isSmall())
it.m_buffer = const_cast<void**>(m_smallStorage);
else
it.m_buffer = m_buffer;
return it;
}
inline unsigned size() const { return m_size; }
private:
constexpr static void* emptyValue()
{
return bitwise_cast<void*>(std::numeric_limits<uintptr_t>::max());
}
bool isValidEntry(const PtrType ptr) const
{
return ptr != emptyValue();
}
inline bool isSmall() const
{
return m_capacity == SmallArraySize;
}
inline void initialize()
{
m_size = 0;
m_buffer = nullptr;
m_capacity = SmallArraySize;
memset(m_smallStorage, -1, sizeof(void*) * SmallArraySize);
ASSERT(isSmall());
}
inline void grow(unsigned size)
{
ASSERT(static_cast<int32_t>(bitwise_cast<intptr_t>(emptyValue())) == -1);
size_t allocationSize = sizeof(void*) * size;
bool wasSmall = isSmall();
void** oldBuffer = wasSmall ? m_smallStorage : m_buffer;
unsigned oldCapacity = m_capacity;
m_buffer = static_cast<void**>(fastMalloc(allocationSize));
memset(m_buffer, -1, allocationSize);
m_capacity = size;
for (unsigned i = 0; i < oldCapacity; i++) {
if (oldBuffer[i] != emptyValue()) {
void** ptr = this->bucket(static_cast<PtrType>(oldBuffer[i]));
*ptr = oldBuffer[i];
}
}
if (!wasSmall)
fastFree(oldBuffer);
}
inline void** bucket(PtrType target) const
{
ASSERT(!(m_capacity & (m_capacity - 1)));
unsigned bucket = PtrHashBase<PtrType, false >::hash(target) & (m_capacity - 1);
unsigned index = 0;
while (true) {
void** ptr = m_buffer + bucket;
if (*ptr == emptyValue())
return ptr;
if (*ptr == target)
return ptr;
index++;
bucket = (bucket + index) & (m_capacity - 1);
}
}
unsigned m_size;
unsigned m_capacity;
void** m_buffer;
void* m_smallStorage[SmallArraySize];
};
}
using WTF::SmallPtrSet;
#endif // SmallPtrSet_h