blob: bf57c311c7929ea85dbb01d980825af4e61597fc [file] [log] [blame]
//===--- BlotSetVector.h ----------------------------------------*- C++ -*-===//
// This source file is part of the open source project
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
// See for license information
// See for the list of Swift project authors
#include "swift/Basic/LLVM.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include <vector>
namespace swift {
/// This is a set container with the following properties:
/// 1. Fast insertion-order iteration.
/// 2. Stable index offsets for all values after all operations including
/// erase.
/// This contrasts with SetVector where index offsets are not stable due to
/// usage of std::vector::erase(). In contrast, BlotSetVector uses the `blot
/// operation' (a) which trades memory for runtime and index offset stability.
/// 3. Fast replacement of a value v1 with a second value v2 guaranteeing that
/// v2 is placed into the same array index as v1, just deleting v1 if v2 is
/// already in the array.
/// This is important if one has other data structures referring to v1 via v1's
/// index in the vector that one wishes to now refer to v2.
/// 4. Fast deletion via the 'blot' operation.
/// 5. Fast insertion.
/// (a) The `blot operation' is leaving the value in the set vector, but marking
/// the value as being dead.
template <typename ValueT, typename VectorT = std::vector<Optional<ValueT>>,
typename MapT = llvm::DenseMap<ValueT, unsigned>>
class BlotSetVector {
VectorT vector;
MapT map;
/// Construct an empty BlotSetVector.
BlotSetVector() {}
bool empty() const { return vector.empty(); }
unsigned size() const { return vector.size(); }
using iterator = typename VectorT::iterator;
using const_iterator = typename VectorT::const_iterator;
iterator begin() { return vector.begin(); }
iterator end() { return vector.end(); }
const_iterator begin() const { return vector.begin(); }
const_iterator end() const { return vector.end(); }
ArrayRef<Optional<ValueT>> getArray() const { return vector; }
iterator_range<const_iterator> getRange() const {
return {begin(), end()};
using const_reverse_iterator = typename VectorT::const_reverse_iterator;
const_reverse_iterator rbegin() const { return vector.rbegin(); }
const_reverse_iterator rend() const { return vector.rend(); }
iterator_range<const_reverse_iterator> getReverseRange() const {
return {rbegin(), rend()};
const Optional<ValueT> &operator[](unsigned n) const {
assert(n < vector.size() && "Out of range!");
return vector[n];
/// Grow the set vector so that it can contain at least \p capacity items
/// before resizing again.
/// \param capacity The minimum size that the set vector will be able to grow
/// to before a resize is required to insert additional items.
void reserve(unsigned capacity) {
/// Insert \p value into the SetVector if it is not there already.
/// \param value The item to insert if not already present.
/// \returns Both the index of the item and whether it was inserted in a pair.
/// If the item was already present, its preexisting index along with
/// false will be returned. If the item was newly added, its new
/// index along with true will be returned.
std::pair<unsigned, bool> insert(const ValueT &value) {
auto iterator = map.find(value);
if (iterator != map.end())
return {iterator->second, false};
unsigned index = vector.size();
map[value] = index;
return {index, true};
/// Replace \p value1 with \p value2 placing \p value2 into the position in
/// the array where value1 used to be. If \p value2 is already in the set,
/// this just erases \p value1.
void replace(const ValueT &value1, const ValueT &value2) {
auto iterator1 = map.find(value1);
assert(iterator1 != map.end() && "Cannot replace value that is not in set");
unsigned index1 = iterator1->second;
auto iterator2 = map.find(value2);
if (iterator2 != map.end()) {
vector[index1] = None;
map[value2] = index1;
vector[index1] = value2;
/// Erase the value \p value if it is in the set. Returns true if value was
/// successfully erased and false otherwise.
bool erase(const ValueT &value) {
auto iterator = map.find(value);
if (iterator == map.end())
return false;
unsigned index = iterator->second;
vector[index] = None;
return true;
/// Return the last element of the blot map vector. Will be None if blotted.
Optional<ValueT> pop_back_val() {
auto result = vector.pop_back_val();
if (!result)
return result;
return result;
/// Attempt to lookup the index of \p value. Returns None upon failure and the
/// value on success.
Optional<unsigned> getIndex(const ValueT &value) {
auto iterator = map.find(value);
if (iterator == map.end())
return None;
return iterator->second;
/// Clear the backing vector and map.
void clear() {
template <typename ValueT, unsigned N>
class SmallBlotSetVector
: public BlotSetVector<ValueT, llvm::SmallVector<Optional<ValueT>, N>,
llvm::SmallDenseMap<ValueT, unsigned, N>> {
SmallBlotSetVector() {}
} // namespace swift