-//===- llvm/ADT/MapVector.h - Map with deterministic value order *- C++ -*-===//
+//===- llvm/ADT/MapVector.h - Map w/ deterministic value order --*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
//
//===----------------------------------------------------------------------===//
//
-// This file implements a map that also provides access to all stored values
-// in a deterministic order via the getValues method. Note that the iteration
-// order itself is just the DenseMap order and not deterministic. The interface
-// is purposefully minimal.
+// This file implements a map that provides insertion order iteration. The
+// interface is purposefully minimal. The key is assumed to be cheap to copy
+// and 2 copies are kept, one for indexing in a DenseMap, one for iteration in
+// a std::vector.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ADT_MAPVECTOR_H
#define LLVM_ADT_MAPVECTOR_H
-#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
#include <vector>
namespace llvm {
/// This class implements a map that also provides access to all stored values
/// in a deterministic order. The values are kept in a std::vector and the
/// mapping is done with DenseMap from Keys to indexes in that vector.
-template<typename KeyT, typename ValueT>
+template<typename KeyT, typename ValueT,
+ typename MapType = llvm::DenseMap<KeyT, unsigned>,
+ typename VectorType = std::vector<std::pair<KeyT, ValueT> > >
class MapVector {
- typedef llvm::DenseMap<KeyT, unsigned> MapType;
- typedef std::vector<ValueT> VectorType;
- typedef typename VectorType::size_type SizeType;
+ typedef typename VectorType::size_type size_type;
MapType Map;
VectorType Vector;
public:
- // The keys and values are not stored close to each other, so the iterator
- // operator->() cannot return a pointer to a std::pair like a DenseMap does.
- // Instead it returns a FakePair that contains references to Key and Value.
- // This lets code using this to look the same as if using a regular DenseMap.
- template<bool IsConst>
- struct FakePair {
- typedef typename conditional<IsConst, const ValueT, ValueT>::type VT;
- const KeyT &first;
- VT &second;
- FakePair(const KeyT &K, VT &V) : first(K), second(V) {
- }
- FakePair *operator->() {
- return this;
- }
- };
-
- template<bool IsConst>
- class IteratorTemplate {
- typedef typename MapType::const_iterator WrappedIteratorType;
- WrappedIteratorType WrappedI;
- typedef
- typename conditional<IsConst, const VectorType, VectorType>::type VT;
- VT &VecRef;
- typedef FakePair<IsConst> PairType;
- friend class IteratorTemplate<true>;
-
- public:
- IteratorTemplate(WrappedIteratorType I, VT &V) :
- WrappedI(I), VecRef(V) {
- }
+ typedef typename VectorType::iterator iterator;
+ typedef typename VectorType::const_iterator const_iterator;
+ typedef typename VectorType::reverse_iterator reverse_iterator;
+ typedef typename VectorType::const_reverse_iterator const_reverse_iterator;
- // If IsConst is true this is a converting constructor from iterator to
- // const_iterator and the default copy constructor is used.
- // Otherwise this is a copy constructor for iterator.
- IteratorTemplate(const IteratorTemplate<false>& I) :
- WrappedI(I.WrappedI), VecRef(I.VecRef) {
- }
+ size_type size() const { return Vector.size(); }
- bool operator!=(const IteratorTemplate &RHS) const {
- return WrappedI != RHS.WrappedI;
- }
+ iterator begin() { return Vector.begin(); }
+ const_iterator begin() const { return Vector.begin(); }
+ iterator end() { return Vector.end(); }
+ const_iterator end() const { return Vector.end(); }
- IteratorTemplate &operator++() { // Preincrement
- ++WrappedI;
- return *this;
- }
+ reverse_iterator rbegin() { return Vector.rbegin(); }
+ const_reverse_iterator rbegin() const { return Vector.rbegin(); }
+ reverse_iterator rend() { return Vector.rend(); }
+ const_reverse_iterator rend() const { return Vector.rend(); }
- PairType operator->() {
- unsigned Pos = WrappedI->second;
- PairType Ret(WrappedI->first, VecRef[Pos]);
- return Ret;
- }
- };
+ bool empty() const {
+ return Vector.empty();
+ }
- typedef IteratorTemplate<false> iterator;
- typedef IteratorTemplate<true> const_iterator;
+ std::pair<KeyT, ValueT> &front() { return Vector.front(); }
+ const std::pair<KeyT, ValueT> &front() const { return Vector.front(); }
+ std::pair<KeyT, ValueT> &back() { return Vector.back(); }
+ const std::pair<KeyT, ValueT> &back() const { return Vector.back(); }
- SizeType size() const {
- return Vector.size();
+ void clear() {
+ Map.clear();
+ Vector.clear();
}
- iterator begin() {
- return iterator(Map.begin(), this->Vector);
+ ValueT &operator[](const KeyT &Key) {
+ std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
+ std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
+ unsigned &I = Result.first->second;
+ if (Result.second) {
+ Vector.push_back(std::make_pair(Key, ValueT()));
+ I = Vector.size() - 1;
+ }
+ return Vector[I].second;
}
- const_iterator begin() const {
- return const_iterator(Map.begin(), this->Vector);
+ ValueT lookup(const KeyT &Key) const {
+ typename MapType::const_iterator Pos = Map.find(Key);
+ return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
}
- iterator end() {
- return iterator(Map.end(), this->Vector);
+ std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
+ std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
+ std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
+ unsigned &I = Result.first->second;
+ if (Result.second) {
+ Vector.push_back(std::make_pair(KV.first, KV.second));
+ I = Vector.size() - 1;
+ return std::make_pair(std::prev(end()), true);
+ }
+ return std::make_pair(begin() + I, false);
}
- const_iterator end() const {
- return const_iterator(Map.end(), this->Vector);
+ size_type count(const KeyT &Key) const {
+ typename MapType::const_iterator Pos = Map.find(Key);
+ return Pos == Map.end()? 0 : 1;
}
- bool empty() const {
- return Map.empty();
+ iterator find(const KeyT &Key) {
+ typename MapType::const_iterator Pos = Map.find(Key);
+ return Pos == Map.end()? Vector.end() :
+ (Vector.begin() + Pos->second);
}
- typedef typename VectorType::iterator value_iterator;
- typedef typename VectorType::const_iterator const_value_iterator;
-
- value_iterator value_begin() {
- return Vector.begin();
+ const_iterator find(const KeyT &Key) const {
+ typename MapType::const_iterator Pos = Map.find(Key);
+ return Pos == Map.end()? Vector.end() :
+ (Vector.begin() + Pos->second);
}
- const_value_iterator value_begin() const {
- return Vector.begin();
+ /// \brief Remove the last element from the vector.
+ void pop_back() {
+ typename MapType::iterator Pos = Map.find(Vector.back().first);
+ Map.erase(Pos);
+ Vector.pop_back();
}
- value_iterator value_end() {
- return Vector.end();
+ /// \brief Remove the element given by Iterator.
+ ///
+ /// Returns an iterator to the element following the one which was removed,
+ /// which may be end().
+ ///
+ /// \note This is a deceivingly expensive operation (linear time). It's
+ /// usually better to use \a remove_if() if possible.
+ typename VectorType::iterator erase(typename VectorType::iterator Iterator) {
+ Map.erase(Iterator->first);
+ auto Next = Vector.erase(Iterator);
+ if (Next == Vector.end())
+ return Next;
+
+ // Update indices in the map.
+ size_t Index = Next - Vector.begin();
+ for (auto &I : Map) {
+ assert(I.second != Index && "Index was already erased!");
+ if (I.second > Index)
+ --I.second;
+ }
+ return Next;
}
- const_value_iterator value_end() const {
- return Vector.end();
+ /// \brief Remove all elements with the key value Key.
+ ///
+ /// Returns the number of elements removed.
+ size_type erase(const KeyT &Key) {
+ auto Iterator = find(Key);
+ if (Iterator == end())
+ return 0;
+ erase(Iterator);
+ return 1;
}
- ValueT &operator[](const KeyT &Key) {
- std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
- std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
- unsigned &I = Result.first->second;
- if (Result.second) {
- Vector.push_back(ValueT());
- I = Vector.size() - 1;
+ /// \brief Remove the elements that match the predicate.
+ ///
+ /// Erase all elements that match \c Pred in a single pass. Takes linear
+ /// time.
+ template <class Predicate> void remove_if(Predicate Pred);
+};
+
+template <typename KeyT, typename ValueT, typename MapType, typename VectorType>
+template <class Function>
+void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) {
+ auto O = Vector.begin();
+ for (auto I = O, E = Vector.end(); I != E; ++I) {
+ if (Pred(*I)) {
+ // Erase from the map.
+ Map.erase(I->first);
+ continue;
}
- return Vector[I];
+
+ if (I != O) {
+ // Move the value and update the index in the map.
+ *O = std::move(*I);
+ Map[O->first] = O - Vector.begin();
+ }
+ ++O;
}
+ // Erase trailing entries in the vector.
+ Vector.erase(O, Vector.end());
+}
+
+/// \brief A MapVector that performs no allocations if smaller than a certain
+/// size.
+template <typename KeyT, typename ValueT, unsigned N>
+struct SmallMapVector
+ : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>,
+ SmallVector<std::pair<KeyT, ValueT>, N>> {
};
-}
+} // end namespace llvm
#endif
projects / oota-llvm.git / blobdiff