blob: bce4588c15cf3dffe244058381579a99e1d03e81 [file] [log] [blame]
/*
* 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.
*/
#ifndef IndexSparseSet_h
#define IndexSparseSet_h
#include <wtf/HashTraits.h>
#include <wtf/Vector.h>
namespace WTF {
// 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 {
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();
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 (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);
});
}
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;
#endif // IndexSparseSet_h