256 lines
8.3 KiB
C++
256 lines
8.3 KiB
C++
/*
|
|
* Copyright (C) 2015-2017 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/Vector.h>
|
|
|
|
namespace WTF {
|
|
|
|
template<typename KeyTypeArg, typename ValueTypeArg>
|
|
struct KeyValuePair;
|
|
|
|
// IndexSparseSet is an efficient set of integers that can only be valued
|
|
// between zero and size() - 1.
|
|
//
|
|
// The implementation is using Briggs Sparse Set representation. We allocate
|
|
// memory from 0 to size() - 1 to do mapping in O(1), but we never initialize
|
|
// that memory. When adding/removing values to the set, they are added in a list
|
|
// and the corresponding bucket is initialized to the position in the list.
|
|
//
|
|
// The assumption here is that we only need a sparse subset of number live at any
|
|
// time.
|
|
|
|
template<typename T>
|
|
struct DefaultIndexSparseSetTraits {
|
|
typedef T EntryType;
|
|
|
|
static T create(unsigned entry)
|
|
{
|
|
return entry;
|
|
}
|
|
|
|
static unsigned key(const T& entry)
|
|
{
|
|
return entry;
|
|
}
|
|
};
|
|
|
|
template<typename KeyType, typename ValueType>
|
|
struct DefaultIndexSparseSetTraits<KeyValuePair<KeyType, ValueType>> {
|
|
typedef KeyValuePair<KeyType, ValueType> EntryType;
|
|
|
|
template<typename PassedValueType>
|
|
static EntryType create(unsigned key, PassedValueType&& value)
|
|
{
|
|
return EntryType(key, std::forward<PassedValueType>(value));
|
|
}
|
|
|
|
static unsigned key(const EntryType& entry)
|
|
{
|
|
return entry.key;
|
|
}
|
|
};
|
|
|
|
template<typename EntryType = unsigned, typename EntryTypeTraits = DefaultIndexSparseSetTraits<EntryType>, typename OverflowHandler = CrashOnOverflow>
|
|
class IndexSparseSet {
|
|
WTF_MAKE_FAST_ALLOCATED;
|
|
typedef Vector<EntryType, 0, OverflowHandler> ValueList;
|
|
public:
|
|
explicit IndexSparseSet(unsigned size);
|
|
|
|
template<typename... Arguments>
|
|
bool add(unsigned, Arguments&&...);
|
|
template<typename... Arguments>
|
|
bool set(unsigned, Arguments&&...);
|
|
bool remove(unsigned);
|
|
void clear();
|
|
|
|
unsigned size() const;
|
|
bool isEmpty() const;
|
|
bool contains(unsigned) const;
|
|
const EntryType* get(unsigned) const;
|
|
EntryType* get(unsigned);
|
|
|
|
typedef typename ValueList::const_iterator const_iterator;
|
|
const_iterator begin() const;
|
|
const_iterator end() const;
|
|
|
|
void sort();
|
|
|
|
void validate();
|
|
|
|
const ValueList& values() const { return m_values; }
|
|
|
|
private:
|
|
Vector<unsigned, 0, OverflowHandler, 1> m_map;
|
|
ValueList m_values;
|
|
};
|
|
|
|
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
|
|
inline IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::IndexSparseSet(unsigned size)
|
|
{
|
|
m_map.grow(size);
|
|
}
|
|
|
|
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
|
|
template<typename... Arguments>
|
|
inline bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::add(unsigned value, Arguments&&... arguments)
|
|
{
|
|
if (contains(value))
|
|
return false;
|
|
|
|
unsigned newPosition = m_values.size();
|
|
m_values.append(EntryTypeTraits::create(value, std::forward<Arguments>(arguments)...));
|
|
m_map[value] = newPosition;
|
|
return true;
|
|
}
|
|
|
|
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
|
|
template<typename... Arguments>
|
|
inline bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::set(unsigned value, Arguments&&... arguments)
|
|
{
|
|
if (EntryType* entry = get(value)) {
|
|
*entry = EntryTypeTraits::create(value, std::forward<Arguments>(arguments)...);
|
|
return false;
|
|
}
|
|
|
|
unsigned newPosition = m_values.size();
|
|
m_values.append(EntryTypeTraits::create(value, std::forward<Arguments>(arguments)...));
|
|
m_map[value] = newPosition;
|
|
return true;
|
|
}
|
|
|
|
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
|
|
inline bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::remove(unsigned value)
|
|
{
|
|
unsigned position = m_map[value];
|
|
if (position >= m_values.size())
|
|
return false;
|
|
|
|
if (EntryTypeTraits::key(m_values[position]) == value) {
|
|
EntryType lastValue = m_values.last();
|
|
m_values[position] = WTFMove(lastValue);
|
|
m_map[EntryTypeTraits::key(lastValue)] = position;
|
|
m_values.removeLast();
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
|
|
void IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::clear()
|
|
{
|
|
m_values.shrink(0);
|
|
}
|
|
|
|
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
|
|
unsigned IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::size() const
|
|
{
|
|
return m_values.size();
|
|
}
|
|
|
|
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
|
|
bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::isEmpty() const
|
|
{
|
|
return !size();
|
|
}
|
|
|
|
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
|
|
bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::contains(unsigned value) const
|
|
{
|
|
unsigned position = m_map[value];
|
|
if (position >= m_values.size())
|
|
return false;
|
|
|
|
return EntryTypeTraits::key(m_values[position]) == value;
|
|
}
|
|
|
|
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
|
|
auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::get(unsigned value) -> EntryType*
|
|
{
|
|
unsigned position = m_map[value];
|
|
if (position >= m_values.size())
|
|
return nullptr;
|
|
|
|
EntryType& entry = m_values[position];
|
|
if (EntryTypeTraits::key(entry) != value)
|
|
return nullptr;
|
|
|
|
return &entry;
|
|
}
|
|
|
|
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
|
|
auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::get(unsigned value) const -> const EntryType*
|
|
{
|
|
return const_cast<IndexSparseSet*>(this)->get(value);
|
|
}
|
|
|
|
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
|
|
void IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::sort()
|
|
{
|
|
std::sort(
|
|
m_values.begin(), m_values.end(),
|
|
[&] (const EntryType& a, const EntryType& b) {
|
|
return EntryTypeTraits::key(a) < EntryTypeTraits::key(b);
|
|
});
|
|
|
|
// Bring m_map back in sync with m_values
|
|
for (unsigned index = 0; index < m_values.size(); ++index) {
|
|
unsigned key = EntryTypeTraits::key(m_values[index]);
|
|
m_map[key] = index;
|
|
}
|
|
|
|
#if ASSERT_ENABLED
|
|
validate();
|
|
#endif
|
|
}
|
|
|
|
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
|
|
void IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::validate()
|
|
{
|
|
RELEASE_ASSERT(m_values.size() <= m_map.size());
|
|
for (const EntryType& entry : *this)
|
|
RELEASE_ASSERT(contains(EntryTypeTraits::key(entry)));
|
|
}
|
|
|
|
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
|
|
auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::begin() const -> const_iterator
|
|
{
|
|
return m_values.begin();
|
|
}
|
|
|
|
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
|
|
auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::end() const -> const_iterator
|
|
{
|
|
return m_values.end();
|
|
}
|
|
|
|
} // namespace WTF
|
|
|
|
using WTF::DefaultIndexSparseSetTraits;
|
|
using WTF::IndexSparseSet;
|