// Copyright 2015, ARM Limited
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// * Redistributions of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
// * 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.
// * Neither the name of ARM Limited nor the names of its contributors may be
// used to endorse or promote products derived from this software without
// specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS CONTRIBUTORS "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 THE COPYRIGHT OWNER 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 VIXL_INVALSET_H_
#define VIXL_INVALSET_H_
#include <string.h>
#include <algorithm>
#include <vector>
#include "vixl/globals.h"
namespace vixl {
// We define a custom data structure template and its iterator as `std`
// containers do not fit the performance requirements for some of our use cases.
//
// The structure behaves like an iterable unordered set with special properties
// and restrictions. "InvalSet" stands for "Invalidatable Set".
//
// Restrictions and requirements:
// - Adding an element already present in the set is illegal. In debug mode,
// this is checked at insertion time.
// - The templated class `ElementType` must provide comparison operators so that
// `std::sort()` can be used.
// - A key must be available to represent invalid elements.
// - Elements with an invalid key must compare higher or equal to any other
// element.
//
// Use cases and performance considerations:
// Our use cases present two specificities that allow us to design this
// structure to provide fast insertion *and* fast search and deletion
// operations:
// - Elements are (generally) inserted in order (sorted according to their key).
// - A key is available to mark elements as invalid (deleted).
// The backing `std::vector` allows for fast insertions. When
// searching for an element we ensure the elements are sorted (this is generally
// the case) and perform a binary search. When deleting an element we do not
// free the associated memory immediately. Instead, an element to be deleted is
// marked with the 'invalid' key. Other methods of the container take care of
// ignoring entries marked as invalid.
// To avoid the overhead of the `std::vector` container when only few entries
// are used, a number of elements are preallocated.
// 'ElementType' and 'KeyType' are respectively the types of the elements and
// their key. The structure only reclaims memory when safe to do so, if the
// number of elements that can be reclaimed is greater than `RECLAIM_FROM` and
// greater than `<total number of elements> / RECLAIM_FACTOR.
#define TEMPLATE_INVALSET_P_DECL \
class ElementType, \
unsigned N_PREALLOCATED_ELEMENTS, \
class KeyType, \
KeyType INVALID_KEY, \
size_t RECLAIM_FROM, \
unsigned RECLAIM_FACTOR
#define TEMPLATE_INVALSET_P_DEF \
ElementType, N_PREALLOCATED_ELEMENTS, \
KeyType, INVALID_KEY, RECLAIM_FROM, RECLAIM_FACTOR
template<class S> class InvalSetIterator; // Forward declaration.
template<TEMPLATE_INVALSET_P_DECL> class InvalSet {
public:
InvalSet();
~InvalSet();
static const size_t kNPreallocatedElements = N_PREALLOCATED_ELEMENTS;
static const KeyType kInvalidKey = INVALID_KEY;
// It is illegal to insert an element already present in the set.
void insert(const ElementType& element);
// Looks for the specified element in the set and - if found - deletes it.
void erase(const ElementType& element);
// This indicates the number of (valid) elements stored in this set.
size_t size() const;
// Returns true if no elements are stored in the set.
// Note that this does not mean the the backing storage is empty: it can still
// contain invalid elements.
bool empty() const;
void clear();
const ElementType min_element();
// This returns the key of the minimum element in the set.
KeyType min_element_key();
static bool IsValid(const ElementType& element);
static KeyType Key(const ElementType& element);
static void SetKey(ElementType* element, KeyType key);
protected:
// Returns a pointer to the element in vector_ if it was found, or NULL
// otherwise.
ElementType* Search(const ElementType& element);
// The argument *must* point to an element stored in *this* set.
// This function is not allowed to move elements in the backing vector
// storage.
void EraseInternal(ElementType* element);
// The elements in the range searched must be sorted.
ElementType* BinarySearch(const ElementType& element,
ElementType* start,
ElementType* end) const;
// Sort the elements.
enum SortType {
// The 'hard' version guarantees that invalid elements are moved to the end
// of the container.
kHardSort,
// The 'soft' version only guarantees that the elements will be sorted.
// Invalid elements may still be present anywhere in the set.
kSoftSort
};
void Sort(SortType sort_type);
// Delete the elements that have an invalid key. The complexity is linear
// with the size of the vector.
void Clean();
const ElementType Front() const;
const ElementType Back() const;
// Delete invalid trailing elements and return the last valid element in the
// set.
const ElementType CleanBack();
// Returns a pointer to the start or end of the backing storage.
const ElementType* StorageBegin() const;
const ElementType* StorageEnd() const;
ElementType* StorageBegin();
ElementType* StorageEnd();
// Returns the index of the element within the backing storage. The element
// must belong to the backing storage.
size_t ElementIndex(const ElementType* element) const;
// Returns the element at the specified index in the backing storage.
const ElementType* ElementAt(size_t index) const;
ElementType* ElementAt(size_t index);
static const ElementType* FirstValidElement(const ElementType* from,
const ElementType* end);
void CacheMinElement();
const ElementType CachedMinElement() const;
bool ShouldReclaimMemory() const;
void ReclaimMemory();
bool IsUsingVector() const { return vector_ != NULL; }
void set_sorted(bool sorted) { sorted_ = sorted; }
// We cache some data commonly required by users to improve performance.
// We cannot cache pointers to elements as we do not control the backing
// storage.
bool valid_cached_min_;
size_t cached_min_index_; // Valid iff `valid_cached_min_` is true.
KeyType cached_min_key_; // Valid iff `valid_cached_min_` is true.
// Indicates whether the elements are sorted.
bool sorted_;
// This represents the number of (valid) elements in this set.
size_t size_;
// The backing storage is either the array of preallocated elements or the
// vector. The structure starts by using the preallocated elements, and
// transitions (permanently) to using the vector once more than
// kNPreallocatedElements are used.
// Elements are only invalidated when using the vector. The preallocated
// storage always only contains valid elements.
ElementType preallocated_[kNPreallocatedElements];
std::vector<ElementType>* vector_;
#ifdef VIXL_DEBUG
// Iterators acquire and release this monitor. While a set is acquired,
// certain operations are illegal to ensure that the iterator will
// correctly iterate over the elements in the set.
int monitor_;
int monitor() const { return monitor_; }
void Acquire() { monitor_++; }
void Release() {
monitor_--;
VIXL_ASSERT(monitor_ >= 0);
}
#endif
friend class InvalSetIterator<InvalSet<TEMPLATE_INVALSET_P_DEF> >;
typedef ElementType _ElementType;
typedef KeyType _KeyType;
};
template<class S> class InvalSetIterator {
private:
// Redefine types to mirror the associated set types.
typedef typename S::_ElementType ElementType;
typedef typename S::_KeyType KeyType;
public:
explicit InvalSetIterator(S* inval_set);
~InvalSetIterator();
ElementType* Current() const;
void Advance();
bool Done() const;
// Mark this iterator as 'done'.
void Finish();
// Delete the current element and advance the iterator to point to the next
// element.
void DeleteCurrentAndAdvance();
static bool IsValid(const ElementType& element);
static KeyType Key(const ElementType& element);
protected:
void MoveToValidElement();
// Indicates if the iterator is looking at the vector or at the preallocated
// elements.
const bool using_vector_;
// Used when looking at the preallocated elements, or in debug mode when using
// the vector to track how many times the iterator has advanced.
size_t index_;
typename std::vector<ElementType>::iterator iterator_;
S* inval_set_;
};
template<TEMPLATE_INVALSET_P_DECL>
InvalSet<TEMPLATE_INVALSET_P_DEF>::InvalSet()
: valid_cached_min_(false),
sorted_(true), size_(0), vector_(NULL) {
#ifdef VIXL_DEBUG
monitor_ = 0;
#endif
}
template<TEMPLATE_INVALSET_P_DECL>
InvalSet<TEMPLATE_INVALSET_P_DEF>::~InvalSet() {
VIXL_ASSERT(monitor_ == 0);
delete vector_;
}
template<TEMPLATE_INVALSET_P_DECL>
void InvalSet<TEMPLATE_INVALSET_P_DEF>::insert(const ElementType& element) {
VIXL_ASSERT(monitor() == 0);
VIXL_ASSERT(IsValid(element));
VIXL_ASSERT(Search(element) == NULL);
set_sorted(empty() || (sorted_ && (element > CleanBack())));
if (IsUsingVector()) {
vector_->push_back(element);
} else {
if (size_ < kNPreallocatedElements) {
preallocated_[size_] = element;
} else {
// Transition to using the vector.
vector_ = new std::vector<ElementType>(preallocated_,
preallocated_ + size_);
vector_->push_back(element);
}
}
size_++;
if (valid_cached_min_ && (element < min_element())) {
cached_min_index_ = IsUsingVector() ? vector_->size() - 1 : size_ - 1;
cached_min_key_ = Key(element);
valid_cached_min_ = true;
}
if (ShouldReclaimMemory()) {
ReclaimMemory();
}
}
template<TEMPLATE_INVALSET_P_DECL>
void InvalSet<TEMPLATE_INVALSET_P_DEF>::erase(const ElementType& element) {
VIXL_ASSERT(monitor() == 0);
VIXL_ASSERT(IsValid(element));
ElementType* local_element = Search(element);
if (local_element != NULL) {
EraseInternal(local_element);
}
}
template<TEMPLATE_INVALSET_P_DECL>
ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::Search(
const ElementType& element) {
VIXL_ASSERT(monitor() == 0);
if (empty()) {
return NULL;
}
if (ShouldReclaimMemory()) {
ReclaimMemory();
}
if (!sorted_) {
Sort(kHardSort);
}
if (!valid_cached_min_) {
CacheMinElement();
}
return BinarySearch(element, ElementAt(cached_min_index_), StorageEnd());
}
template<TEMPLATE_INVALSET_P_DECL>
size_t InvalSet<TEMPLATE_INVALSET_P_DEF>::size() const {
return size_;
}
template<TEMPLATE_INVALSET_P_DECL>
bool InvalSet<TEMPLATE_INVALSET_P_DEF>::empty() const {
return size_ == 0;
}
template<TEMPLATE_INVALSET_P_DECL>
void InvalSet<TEMPLATE_INVALSET_P_DEF>::clear() {
VIXL_ASSERT(monitor() == 0);
size_ = 0;
if (IsUsingVector()) {
vector_->clear();
}
set_sorted(true);
valid_cached_min_ = false;
}
template<TEMPLATE_INVALSET_P_DECL>
const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::min_element() {
VIXL_ASSERT(monitor() == 0);
VIXL_ASSERT(!empty());
CacheMinElement();
return *ElementAt(cached_min_index_);
}
template<TEMPLATE_INVALSET_P_DECL>
KeyType InvalSet<TEMPLATE_INVALSET_P_DEF>::min_element_key() {
VIXL_ASSERT(monitor() == 0);
if (valid_cached_min_) {
return cached_min_key_;
} else {
return Key(min_element());
}
}
template<TEMPLATE_INVALSET_P_DECL>
bool InvalSet<TEMPLATE_INVALSET_P_DEF>::IsValid(const ElementType& element) {
return Key(element) != kInvalidKey;
}
template<TEMPLATE_INVALSET_P_DECL>
void InvalSet<TEMPLATE_INVALSET_P_DEF>::EraseInternal(ElementType* element) {
// Note that this function must be safe even while an iterator has acquired
// this set.
VIXL_ASSERT(element != NULL);
size_t deleted_index = ElementIndex(element);
if (IsUsingVector()) {
VIXL_ASSERT((&(vector_->front()) <= element) &&
(element <= &(vector_->back())));
SetKey(element, kInvalidKey);
} else {
VIXL_ASSERT((preallocated_ <= element) &&
(element < (preallocated_ + kNPreallocatedElements)));
ElementType* end = preallocated_ + kNPreallocatedElements;
size_t copy_size = sizeof(*element) * (end - element - 1);
memmove(element, element + 1, copy_size);
}
size_--;
if (valid_cached_min_ &&
(deleted_index == cached_min_index_)) {
if (sorted_ && !empty()) {
const ElementType* min = FirstValidElement(element, StorageEnd());
cached_min_index_ = ElementIndex(min);
cached_min_key_ = Key(*min);
valid_cached_min_ = true;
} else {
valid_cached_min_ = false;
}
}
}
template<TEMPLATE_INVALSET_P_DECL>
ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::BinarySearch(
const ElementType& element, ElementType* start, ElementType* end) const {
if (start == end) {
return NULL;
}
VIXL_ASSERT(sorted_);
VIXL_ASSERT(start < end);
VIXL_ASSERT(!empty());
// Perform a binary search through the elements while ignoring invalid
// elements.
ElementType* elements = start;
size_t low = 0;
size_t high = (end - start) - 1;
while (low < high) {
// Find valid bounds.
while (!IsValid(elements[low]) && (low < high)) ++low;
while (!IsValid(elements[high]) && (low < high)) --high;
VIXL_ASSERT(low <= high);
// Avoid overflow when computing the middle index.
size_t middle = low / 2 + high / 2 + (low & high & 1);
if ((middle == low) || (middle == high)) {
break;
}
while (!IsValid(elements[middle]) && (middle < high - 1)) ++middle;
while (!IsValid(elements[middle]) && (low + 1 < middle)) --middle;
if (!IsValid(elements[middle])) {
break;
}
if (elements[middle] < element) {
low = middle;
} else {
high = middle;
}
}
if (elements[low] == element) return &elements[low];
if (elements[high] == element) return &elements[high];
return NULL;
}
template<TEMPLATE_INVALSET_P_DECL>
void InvalSet<TEMPLATE_INVALSET_P_DEF>::Sort(SortType sort_type) {
VIXL_ASSERT(monitor() == 0);
if (sort_type == kSoftSort) {
if (sorted_) {
return;
}
}
if (empty()) {
return;
}
Clean();
std::sort(StorageBegin(), StorageEnd());
set_sorted(true);
cached_min_index_ = 0;
cached_min_key_ = Key(Front());
valid_cached_min_ = true;
}
template<TEMPLATE_INVALSET_P_DECL>
void InvalSet<TEMPLATE_INVALSET_P_DEF>::Clean() {
VIXL_ASSERT(monitor() == 0);
if (empty() || !IsUsingVector()) {
return;
}
// Manually iterate through the vector storage to discard invalid elements.
ElementType* start = &(vector_->front());
ElementType* end = start + vector_->size();
ElementType* c = start;
ElementType* first_invalid;
ElementType* first_valid;
ElementType* next_invalid;
while (c < end && IsValid(*c)) { c++; }
first_invalid = c;
while (c < end) {
while (c < end && !IsValid(*c)) { c++; }
first_valid = c;
while (c < end && IsValid(*c)) { c++; }
next_invalid = c;
ptrdiff_t n_moved_elements = (next_invalid - first_valid);
memmove(first_invalid, first_valid, n_moved_elements * sizeof(*c));
first_invalid = first_invalid + n_moved_elements;
c = next_invalid;
}
// Delete the trailing invalid elements.
vector_->erase(vector_->begin() + (first_invalid - start), vector_->end());
VIXL_ASSERT(vector_->size() == size_);
if (sorted_) {
valid_cached_min_ = true;
cached_min_index_ = 0;
cached_min_key_ = Key(*ElementAt(0));
} else {
valid_cached_min_ = false;
}
}
template<TEMPLATE_INVALSET_P_DECL>
const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::Front() const {
VIXL_ASSERT(!empty());
return IsUsingVector() ? vector_->front() : preallocated_[0];
}
template<TEMPLATE_INVALSET_P_DECL>
const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::Back() const {
VIXL_ASSERT(!empty());
return IsUsingVector() ? vector_->back() : preallocated_[size_ - 1];
}
template<TEMPLATE_INVALSET_P_DECL>
const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::CleanBack() {
VIXL_ASSERT(monitor() == 0);
if (IsUsingVector()) {
// Delete the invalid trailing elements.
typename std::vector<ElementType>::reverse_iterator it = vector_->rbegin();
while (!IsValid(*it)) {
it++;
}
vector_->erase(it.base(), vector_->end());
}
return Back();
}
template<TEMPLATE_INVALSET_P_DECL>
const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageBegin() const {
return IsUsingVector() ? &(vector_->front()) : preallocated_;
}
template<TEMPLATE_INVALSET_P_DECL>
const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageEnd() const {
return IsUsingVector() ? &(vector_->back()) + 1 : preallocated_ + size_;
}
template<TEMPLATE_INVALSET_P_DECL>
ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageBegin() {
return IsUsingVector() ? &(vector_->front()) : preallocated_;
}
template<TEMPLATE_INVALSET_P_DECL>
ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageEnd() {
return IsUsingVector() ? &(vector_->back()) + 1 : preallocated_ + size_;
}
template<TEMPLATE_INVALSET_P_DECL>
size_t InvalSet<TEMPLATE_INVALSET_P_DEF>::ElementIndex(
const ElementType* element) const {
VIXL_ASSERT((StorageBegin() <= element) && (element < StorageEnd()));
return element - StorageBegin();
}
template<TEMPLATE_INVALSET_P_DECL>
const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::ElementAt(
size_t index) const {
VIXL_ASSERT(
(IsUsingVector() && (index < vector_->size())) || (index < size_));
return StorageBegin() + index;
}
template<TEMPLATE_INVALSET_P_DECL>
ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::ElementAt(size_t index) {
VIXL_ASSERT(
(IsUsingVector() && (index < vector_->size())) || (index < size_));
return StorageBegin() + index;
}
template<TEMPLATE_INVALSET_P_DECL>
const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::FirstValidElement(
const ElementType* from, const ElementType* end) {
while ((from < end) && !IsValid(*from)) {
from++;
}
return from;
}
template<TEMPLATE_INVALSET_P_DECL>
void InvalSet<TEMPLATE_INVALSET_P_DEF>::CacheMinElement() {
VIXL_ASSERT(monitor() == 0);
VIXL_ASSERT(!empty());
if (valid_cached_min_) {
return;
}
if (sorted_) {
const ElementType* min = FirstValidElement(StorageBegin(), StorageEnd());
cached_min_index_ = ElementIndex(min);
cached_min_key_ = Key(*min);
valid_cached_min_ = true;
} else {
Sort(kHardSort);
}
VIXL_ASSERT(valid_cached_min_);
}
template<TEMPLATE_INVALSET_P_DECL>
bool InvalSet<TEMPLATE_INVALSET_P_DEF>::ShouldReclaimMemory() const {
if (!IsUsingVector()) {
return false;
}
size_t n_invalid_elements = vector_->size() - size_;
return (n_invalid_elements > RECLAIM_FROM) &&
(n_invalid_elements > vector_->size() / RECLAIM_FACTOR);
}
template<TEMPLATE_INVALSET_P_DECL>
void InvalSet<TEMPLATE_INVALSET_P_DEF>::ReclaimMemory() {
VIXL_ASSERT(monitor() == 0);
Clean();
}
template<class S>
InvalSetIterator<S>::InvalSetIterator(S* inval_set)
: using_vector_((inval_set != NULL) && inval_set->IsUsingVector()),
index_(0),
inval_set_(inval_set) {
if (inval_set != NULL) {
inval_set->Sort(S::kSoftSort);
#ifdef VIXL_DEBUG
inval_set->Acquire();
#endif
if (using_vector_) {
iterator_ = typename std::vector<ElementType>::iterator(
inval_set_->vector_->begin());
}
MoveToValidElement();
}
}
template<class S>
InvalSetIterator<S>::~InvalSetIterator() {
#ifdef VIXL_DEBUG
if (inval_set_ != NULL) {
inval_set_->Release();
}
#endif
}
template<class S>
typename S::_ElementType* InvalSetIterator<S>::Current() const {
VIXL_ASSERT(!Done());
if (using_vector_) {
return &(*iterator_);
} else {
return &(inval_set_->preallocated_[index_]);
}
}
template<class S>
void InvalSetIterator<S>::Advance() {
VIXL_ASSERT(!Done());
if (using_vector_) {
iterator_++;
#ifdef VIXL_DEBUG
index_++;
#endif
MoveToValidElement();
} else {
index_++;
}
}
template<class S>
bool InvalSetIterator<S>::Done() const {
if (using_vector_) {
bool done = (iterator_ == inval_set_->vector_->end());
VIXL_ASSERT(done == (index_ == inval_set_->size()));
return done;
} else {
return index_ == inval_set_->size();
}
}
template<class S>
void InvalSetIterator<S>::Finish() {
VIXL_ASSERT(inval_set_->sorted_);
if (using_vector_) {
iterator_ = inval_set_->vector_->end();
}
index_ = inval_set_->size();
}
template<class S>
void InvalSetIterator<S>::DeleteCurrentAndAdvance() {
if (using_vector_) {
inval_set_->EraseInternal(&(*iterator_));
MoveToValidElement();
} else {
inval_set_->EraseInternal(inval_set_->preallocated_ + index_);
}
}
template<class S>
bool InvalSetIterator<S>::IsValid(const ElementType& element) {
return S::IsValid(element);
}
template<class S>
typename S::_KeyType InvalSetIterator<S>::Key(const ElementType& element) {
return S::Key(element);
}
template<class S>
void InvalSetIterator<S>::MoveToValidElement() {
if (using_vector_) {
while ((iterator_ != inval_set_->vector_->end()) && !IsValid(*iterator_)) {
iterator_++;
}
} else {
VIXL_ASSERT(inval_set_->empty() || IsValid(inval_set_->preallocated_[0]));
// Nothing to do.
}
}
#undef TEMPLATE_INVALSET_P_DECL
#undef TEMPLATE_INVALSET_P_DEF
} // namespace vixl
#endif // VIXL_INVALSET_H_
