-//===- 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 <vector>
/// 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;
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) {
- }
-
- // 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) {
- }
-
- bool operator!=(const IteratorTemplate &RHS) const {
- return WrappedI != RHS.WrappedI;
- }
-
- IteratorTemplate &operator++() { // Preincrement
- ++WrappedI;
- return *this;
- }
-
- PairType operator->() {
- unsigned Pos = WrappedI->second;
- PairType Ret(WrappedI->first, VecRef[Pos]);
- return Ret;
- }
- };
-
- typedef IteratorTemplate<false> iterator;
- typedef IteratorTemplate<true> const_iterator;
+ typedef typename VectorType::iterator iterator;
+ typedef typename VectorType::const_iterator const_iterator;
SizeType size() const {
return Vector.size();
}
iterator begin() {
- return iterator(Map.begin(), this->Vector);
+ return Vector.begin();
}
const_iterator begin() const {
- return const_iterator(Map.begin(), this->Vector);
+ return Vector.begin();
}
iterator end() {
- return iterator(Map.end(), this->Vector);
+ return Vector.end();
}
const_iterator end() const {
- return const_iterator(Map.end(), this->Vector);
+ return Vector.end();
}
bool empty() const {
- return Map.empty();
+ return Vector.empty();
}
- typedef typename VectorType::iterator value_iterator;
- typedef typename VectorType::const_iterator const_value_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(); }
- value_iterator value_begin() {
- return Vector.begin();
- }
-
- const_value_iterator value_begin() const {
- return Vector.begin();
+ void clear() {
+ Map.clear();
+ Vector.clear();
}
- value_iterator value_end() {
- return Vector.end();
+ 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_value_iterator value_end() const {
- return Vector.end();
+ ValueT lookup(const KeyT &Key) const {
+ typename MapType::const_iterator Pos = Map.find(Key);
+ return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
}
- ValueT &operator[](const KeyT &Key) {
- std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
+ 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(ValueT());
+ Vector.push_back(std::make_pair(KV.first, KV.second));
I = Vector.size() - 1;
+ return std::make_pair(std::prev(end()), true);
}
- return Vector[I];
+ return std::make_pair(begin() + I, false);
+ }
+
+ unsigned count(const KeyT &Key) const {
+ typename MapType::const_iterator Pos = Map.find(Key);
+ return Pos == Map.end()? 0 : 1;
+ }
+
+ iterator find(const KeyT &Key) {
+ typename MapType::const_iterator Pos = Map.find(Key);
+ return Pos == Map.end()? Vector.end() :
+ (Vector.begin() + Pos->second);
+ }
+
+ 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);
+ }
+
+ /// \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();
}
};
projects / oota-llvm.git / blobdiff