mirror of
https://github.com/darlinghq/darling-WTF.git
synced 2024-11-23 03:49:41 +00:00
529 lines
14 KiB
C++
529 lines
14 KiB
C++
/*
|
|
* Copyright (C) 2015-2019 Apple Inc. All rights reserved.
|
|
*
|
|
* Redistribution and use in source and binary forms, with or without
|
|
* modification, are permitted provided that the following conditions
|
|
* are met:
|
|
* 1. Redistributions of source code must retain the above copyright
|
|
* notice, this list of conditions and the following disclaimer.
|
|
* 2. Redistributions in binary form must reproduce the above copyright
|
|
* notice, this list of conditions and the following disclaimer in the
|
|
* documentation and/or other materials provided with the distribution.
|
|
*
|
|
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
|
|
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
|
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
|
|
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
|
|
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
|
|
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
|
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
|
|
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
|
|
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
|
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
|
|
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
*/
|
|
|
|
#pragma once
|
|
|
|
#include <wtf/Assertions.h>
|
|
#include <wtf/FastMalloc.h>
|
|
|
|
namespace JSC { namespace DFG {
|
|
class StructureAbstractValue;
|
|
} } // namespace JSC::DFG
|
|
|
|
namespace WTF {
|
|
|
|
// FIXME: This currently only works for types that are pointer-like: they should have the size
|
|
// of a pointer and like a pointer they should not have assignment operators, copy constructors,
|
|
// non-trivial default constructors, and non-trivial destructors. It may be possible to lift all
|
|
// of these restrictions. If we succeeded then this should be renamed to just TinySet.
|
|
// https://bugs.webkit.org/show_bug.cgi?id=145741
|
|
|
|
template<typename T>
|
|
class TinyPtrSet {
|
|
WTF_MAKE_FAST_ALLOCATED;
|
|
static_assert(sizeof(T) == sizeof(void*), "It's in the title of the class.");
|
|
public:
|
|
TinyPtrSet()
|
|
: m_pointer(0)
|
|
{
|
|
setEmpty();
|
|
}
|
|
|
|
TinyPtrSet(T element)
|
|
: m_pointer(0)
|
|
{
|
|
set(element);
|
|
}
|
|
|
|
ALWAYS_INLINE TinyPtrSet(const TinyPtrSet& other)
|
|
: m_pointer(0)
|
|
{
|
|
copyFrom(other);
|
|
}
|
|
|
|
ALWAYS_INLINE TinyPtrSet& operator=(const TinyPtrSet& other)
|
|
{
|
|
if (this == &other)
|
|
return *this;
|
|
deleteListIfNecessary();
|
|
copyFrom(other);
|
|
return *this;
|
|
}
|
|
|
|
~TinyPtrSet()
|
|
{
|
|
deleteListIfNecessary();
|
|
}
|
|
|
|
void clear()
|
|
{
|
|
deleteListIfNecessary();
|
|
setEmpty();
|
|
}
|
|
|
|
// Returns the only entry if the array has exactly one entry.
|
|
T onlyEntry() const
|
|
{
|
|
if (isThin())
|
|
return singleEntry();
|
|
OutOfLineList* list = this->list();
|
|
if (list->m_length != 1)
|
|
return T();
|
|
return list->list()[0];
|
|
}
|
|
|
|
bool isEmpty() const
|
|
{
|
|
bool result = isThin() && !singleEntry();
|
|
if (result)
|
|
ASSERT(m_pointer != reservedValue);
|
|
return result;
|
|
}
|
|
|
|
// Returns true if the value was added, or false if the value was already there.
|
|
ALWAYS_INLINE bool add(T value)
|
|
{
|
|
ASSERT(value);
|
|
if (isThin()) {
|
|
if (singleEntry() == value)
|
|
return false;
|
|
if (!singleEntry()) {
|
|
set(value);
|
|
return true;
|
|
}
|
|
|
|
OutOfLineList* list = OutOfLineList::create(defaultStartingSize);
|
|
list->m_length = 2;
|
|
list->list()[0] = singleEntry();
|
|
list->list()[1] = value;
|
|
set(list);
|
|
return true;
|
|
}
|
|
|
|
return addOutOfLine(value);
|
|
}
|
|
|
|
bool remove(T value)
|
|
{
|
|
if (isThin()) {
|
|
if (singleEntry() == value) {
|
|
setEmpty();
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
OutOfLineList* list = this->list();
|
|
for (unsigned i = 0; i < list->m_length; ++i) {
|
|
if (list->list()[i] != value)
|
|
continue;
|
|
list->list()[i] = list->list()[--list->m_length];
|
|
if (!list->m_length) {
|
|
OutOfLineList::destroy(list);
|
|
setEmpty();
|
|
}
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
bool contains(T value) const
|
|
{
|
|
if (isThin())
|
|
return singleEntry() == value;
|
|
return containsOutOfLine(value);
|
|
}
|
|
|
|
ALWAYS_INLINE bool merge(const TinyPtrSet& other)
|
|
{
|
|
if (other.isThin()) {
|
|
if (other.singleEntry())
|
|
return add(other.singleEntry());
|
|
return false;
|
|
}
|
|
|
|
return mergeOtherOutOfLine(other);
|
|
}
|
|
|
|
template<typename Functor>
|
|
void forEach(const Functor& functor) const
|
|
{
|
|
if (isThin()) {
|
|
if (!singleEntry())
|
|
return;
|
|
functor(singleEntry());
|
|
return;
|
|
}
|
|
|
|
OutOfLineList* list = this->list();
|
|
for (unsigned i = 0; i < list->m_length; ++i)
|
|
functor(list->list()[i]);
|
|
}
|
|
|
|
template<typename Functor>
|
|
void genericFilter(const Functor& functor)
|
|
{
|
|
if (isThin()) {
|
|
if (!singleEntry())
|
|
return;
|
|
if (functor(singleEntry()))
|
|
return;
|
|
clear();
|
|
return;
|
|
}
|
|
|
|
OutOfLineList* list = this->list();
|
|
for (unsigned i = 0; i < list->m_length; ++i) {
|
|
if (functor(list->list()[i]))
|
|
continue;
|
|
list->list()[i--] = list->list()[--list->m_length];
|
|
}
|
|
if (!list->m_length)
|
|
clear();
|
|
}
|
|
|
|
void filter(const TinyPtrSet& other)
|
|
{
|
|
if (other.isThin()) {
|
|
if (!other.singleEntry() || !contains(other.singleEntry()))
|
|
clear();
|
|
else {
|
|
clear();
|
|
set(other.singleEntry());
|
|
}
|
|
return;
|
|
}
|
|
|
|
genericFilter([&] (T value) { return other.containsOutOfLine(value); });
|
|
}
|
|
|
|
void exclude(const TinyPtrSet& other)
|
|
{
|
|
if (other.isThin()) {
|
|
if (other.singleEntry())
|
|
remove(other.singleEntry());
|
|
return;
|
|
}
|
|
|
|
genericFilter([&] (T value) { return !other.containsOutOfLine(value); });
|
|
}
|
|
|
|
bool isSubsetOf(const TinyPtrSet& other) const
|
|
{
|
|
if (isThin()) {
|
|
if (!singleEntry())
|
|
return true;
|
|
return other.contains(singleEntry());
|
|
}
|
|
|
|
if (other.isThin()) {
|
|
if (!other.singleEntry())
|
|
return false;
|
|
OutOfLineList* list = this->list();
|
|
if (list->m_length >= 2)
|
|
return false;
|
|
if (list->list()[0] == other.singleEntry())
|
|
return true;
|
|
return false;
|
|
}
|
|
|
|
OutOfLineList* list = this->list();
|
|
for (unsigned i = 0; i < list->m_length; ++i) {
|
|
if (!other.containsOutOfLine(list->list()[i]))
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
bool isSupersetOf(const TinyPtrSet& other) const
|
|
{
|
|
return other.isSubsetOf(*this);
|
|
}
|
|
|
|
bool overlaps(const TinyPtrSet& other) const
|
|
{
|
|
if (isThin()) {
|
|
if (!singleEntry())
|
|
return false;
|
|
return other.contains(singleEntry());
|
|
}
|
|
|
|
if (other.isThin()) {
|
|
if (!other.singleEntry())
|
|
return false;
|
|
return containsOutOfLine(other.singleEntry());
|
|
}
|
|
|
|
OutOfLineList* list = this->list();
|
|
for (unsigned i = 0; i < list->m_length; ++i) {
|
|
if (other.containsOutOfLine(list->list()[i]))
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
size_t size() const
|
|
{
|
|
if (isThin())
|
|
return !!singleEntry();
|
|
return list()->m_length;
|
|
}
|
|
|
|
T at(size_t i) const
|
|
{
|
|
if (isThin()) {
|
|
ASSERT(!i);
|
|
ASSERT(singleEntry());
|
|
return singleEntry();
|
|
}
|
|
ASSERT(i < list()->m_length);
|
|
return list()->list()[i];
|
|
}
|
|
|
|
T operator[](size_t i) const { return at(i); }
|
|
|
|
T last() const
|
|
{
|
|
if (isThin()) {
|
|
ASSERT(singleEntry());
|
|
return singleEntry();
|
|
}
|
|
return list()->list()[list()->m_length - 1];
|
|
}
|
|
|
|
class iterator {
|
|
public:
|
|
iterator()
|
|
: m_set(nullptr)
|
|
, m_index(0)
|
|
{
|
|
}
|
|
|
|
iterator(const TinyPtrSet* set, size_t index)
|
|
: m_set(set)
|
|
, m_index(index)
|
|
{
|
|
}
|
|
|
|
T operator*() const { return m_set->at(m_index); }
|
|
iterator& operator++()
|
|
{
|
|
m_index++;
|
|
return *this;
|
|
}
|
|
bool operator==(const iterator& other) const { return m_index == other.m_index; }
|
|
bool operator!=(const iterator& other) const { return !(*this == other); }
|
|
|
|
private:
|
|
const TinyPtrSet* m_set;
|
|
size_t m_index;
|
|
};
|
|
|
|
iterator begin() const { return iterator(this, 0); }
|
|
iterator end() const { return iterator(this, size()); }
|
|
|
|
bool operator==(const TinyPtrSet& other) const
|
|
{
|
|
if (size() != other.size())
|
|
return false;
|
|
return isSubsetOf(other);
|
|
}
|
|
|
|
bool operator!=(const TinyPtrSet& other) const
|
|
{
|
|
return !(*this == other);
|
|
}
|
|
|
|
private:
|
|
friend class JSC::DFG::StructureAbstractValue;
|
|
|
|
static constexpr uintptr_t fatFlag = 1;
|
|
static constexpr uintptr_t reservedFlag = 2;
|
|
static constexpr uintptr_t flags = fatFlag | reservedFlag;
|
|
static constexpr uintptr_t reservedValue = 4;
|
|
|
|
static constexpr unsigned defaultStartingSize = 4;
|
|
|
|
NEVER_INLINE bool addOutOfLine(T value)
|
|
{
|
|
OutOfLineList* list = this->list();
|
|
for (unsigned i = 0; i < list->m_length; ++i) {
|
|
if (list->list()[i] == value)
|
|
return false;
|
|
}
|
|
|
|
if (list->m_length < list->m_capacity) {
|
|
list->list()[list->m_length++] = value;
|
|
return true;
|
|
}
|
|
|
|
OutOfLineList* newList = OutOfLineList::create(list->m_capacity * 2);
|
|
newList->m_length = list->m_length + 1;
|
|
for (unsigned i = list->m_length; i--;)
|
|
newList->list()[i] = list->list()[i];
|
|
newList->list()[list->m_length] = value;
|
|
OutOfLineList::destroy(list);
|
|
set(newList);
|
|
return true;
|
|
}
|
|
|
|
NEVER_INLINE bool mergeOtherOutOfLine(const TinyPtrSet& other)
|
|
{
|
|
OutOfLineList* list = other.list();
|
|
if (list->m_length >= 2) {
|
|
if (isThin()) {
|
|
OutOfLineList* myNewList = OutOfLineList::create(
|
|
list->m_length + !!singleEntry());
|
|
if (singleEntry()) {
|
|
myNewList->m_length = 1;
|
|
myNewList->list()[0] = singleEntry();
|
|
}
|
|
set(myNewList);
|
|
}
|
|
bool changed = false;
|
|
for (unsigned i = 0; i < list->m_length; ++i)
|
|
changed |= addOutOfLine(list->list()[i]);
|
|
return changed;
|
|
}
|
|
|
|
ASSERT(list->m_length);
|
|
return add(list->list()[0]);
|
|
}
|
|
|
|
bool containsOutOfLine(T value) const
|
|
{
|
|
OutOfLineList* list = this->list();
|
|
for (unsigned i = 0; i < list->m_length; ++i) {
|
|
if (list->list()[i] == value)
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
ALWAYS_INLINE void copyFrom(const TinyPtrSet& other)
|
|
{
|
|
if (other.isThin() || other.m_pointer == reservedValue) {
|
|
bool value = getReservedFlag();
|
|
m_pointer = other.m_pointer;
|
|
setReservedFlag(value);
|
|
return;
|
|
}
|
|
copyFromOutOfLine(other);
|
|
}
|
|
|
|
NEVER_INLINE void copyFromOutOfLine(const TinyPtrSet& other)
|
|
{
|
|
ASSERT(!other.isThin() && other.m_pointer != reservedValue);
|
|
OutOfLineList* otherList = other.list();
|
|
OutOfLineList* myList = OutOfLineList::create(otherList->m_length);
|
|
myList->m_length = otherList->m_length;
|
|
for (unsigned i = otherList->m_length; i--;)
|
|
myList->list()[i] = otherList->list()[i];
|
|
set(myList);
|
|
}
|
|
|
|
class OutOfLineList {
|
|
public:
|
|
static OutOfLineList* create(unsigned capacity)
|
|
{
|
|
return new (NotNull, fastMalloc(sizeof(OutOfLineList) + capacity * sizeof(T))) OutOfLineList(0, capacity);
|
|
}
|
|
|
|
static void destroy(OutOfLineList* list)
|
|
{
|
|
fastFree(list);
|
|
}
|
|
|
|
T* list() { return bitwise_cast<T*>(this + 1); }
|
|
|
|
OutOfLineList(unsigned length, unsigned capacity)
|
|
: m_length(length)
|
|
, m_capacity(capacity)
|
|
{
|
|
}
|
|
|
|
unsigned m_length;
|
|
unsigned m_capacity;
|
|
};
|
|
|
|
ALWAYS_INLINE void deleteListIfNecessary()
|
|
{
|
|
if (!isThin()) {
|
|
ASSERT(m_pointer != reservedValue);
|
|
OutOfLineList::destroy(list());
|
|
}
|
|
}
|
|
|
|
bool isThin() const { return !(m_pointer & fatFlag); }
|
|
|
|
void* pointer() const
|
|
{
|
|
return bitwise_cast<void*>(m_pointer & ~flags);
|
|
}
|
|
|
|
T singleEntry() const
|
|
{
|
|
ASSERT(isThin());
|
|
return bitwise_cast<T>(pointer());
|
|
}
|
|
|
|
OutOfLineList* list() const
|
|
{
|
|
ASSERT(!isThin());
|
|
return static_cast<OutOfLineList*>(pointer());
|
|
}
|
|
|
|
void set(T value)
|
|
{
|
|
set(bitwise_cast<uintptr_t>(value), true);
|
|
}
|
|
void set(OutOfLineList* list)
|
|
{
|
|
set(bitwise_cast<uintptr_t>(list), false);
|
|
}
|
|
void setEmpty()
|
|
{
|
|
set(0, true);
|
|
}
|
|
void set(uintptr_t pointer, bool singleEntry)
|
|
{
|
|
m_pointer = pointer | (singleEntry ? 0 : fatFlag) | (m_pointer & reservedFlag);
|
|
}
|
|
bool getReservedFlag() const { return m_pointer & reservedFlag; }
|
|
void setReservedFlag(bool value)
|
|
{
|
|
if (value)
|
|
m_pointer |= reservedFlag;
|
|
else
|
|
m_pointer &= ~reservedFlag;
|
|
}
|
|
|
|
uintptr_t m_pointer;
|
|
};
|
|
|
|
} // namespace WTF
|
|
|
|
using WTF::TinyPtrSet;
|