| //===--- BlotSetVector.h ----------------------------------------*- C++ -*-===// |
| // |
| // This source file is part of the Swift.org 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 https://swift.org/LICENSE.txt for license information |
| // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef SWIFT_BASIC_BLOTSETVECTOR_H |
| #define SWIFT_BASIC_BLOTSETVECTOR_H |
| |
| #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; |
| |
| public: |
| /// \brief 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(); } |
| llvm::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(); } |
| llvm::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]; |
| } |
| |
| /// Insert \p V into the SetVector if it is not in the array and return the |
| /// index of \p V in the Set Vector. If \p V is already in the SetVector, just |
| /// return its index in the array. |
| unsigned insert(const ValueT &V) { |
| auto Iter = Map.find(V); |
| if (Iter != Map.end()) |
| return Iter->second; |
| |
| unsigned Index = Vector.size(); |
| Map[V] = Index; |
| Vector.push_back(V); |
| return Index; |
| } |
| |
| /// Replace \p V1 with \p V2 placing \p V2 into the position in the array |
| /// where V1 used to be. If \p V2 is already in the set, this just erases \p |
| /// V1. |
| void replace(const ValueT &V1, const ValueT &V2) { |
| auto Iter1 = Map.find(V1); |
| assert(Iter1 != Map.end() && "Cannot replace value that is not in set"); |
| unsigned V1Index = Iter1->second; |
| Map.erase(V1); |
| |
| auto Iter2 = Map.find(V2); |
| if (Iter2 != Map.end()) { |
| Vector[V1Index] = None; |
| return; |
| } |
| |
| Map[V2] = V1Index; |
| Vector[V1Index] = V2; |
| } |
| |
| /// Erase the value \p V if it is in the set. Returns true if V was |
| /// successfully erased and false otherwise. |
| bool erase(const ValueT &V) { |
| auto Iter = Map.find(V); |
| if (Iter == Map.end()) |
| return false; |
| unsigned Index = Iter->second; |
| Map.erase(V); |
| Vector[Index] = None; |
| return true; |
| } |
| |
| /// Attempt to lookup the index of \p V. Returns None upon failure and the |
| /// value on success. |
| Optional<unsigned> getIndex(const ValueT &V) { |
| auto Iter = Map.find(V); |
| if (Iter == Map.end()) |
| return None; |
| return Iter->second; |
| } |
| }; |
| |
| template <typename ValueT, unsigned N, |
| typename VectorT = llvm::SmallVector<Optional<ValueT>, N>, |
| typename MapT = llvm::SmallDenseMap<ValueT, unsigned, N>> |
| class SmallBlotSetVector : public BlotSetVector<ValueT, VectorT, MapT> { |
| public: |
| SmallBlotSetVector() {} |
| }; |
| |
| } // end swift namespace |
| |
| #endif // SWIFT_BASIC_BLOTSETVECTOR_H |