LLVM  6.0.0svn
IndexedMap.h
Go to the documentation of this file.
1 //===- llvm/ADT/IndexedMap.h - An index map implementation ------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements an indexed map. The index map template takes two
11 // types. The first is the mapped type and the second is a functor
12 // that maps its argument to a size_t. On instantiation a "null" value
13 // can be provided to be used as a "does not exist" indicator in the
14 // map. A member function grow() is provided that given the value of
15 // the maximally indexed key (the argument of the functor) makes sure
16 // the map has enough space for it.
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #ifndef LLVM_ADT_INDEXEDMAP_H
21 #define LLVM_ADT_INDEXEDMAP_H
22 
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/STLExtras.h"
25 #include <cassert>
26 
27 namespace llvm {
28 
29 template <typename T, typename ToIndexT = identity<unsigned>>
30  class IndexedMap {
31  using IndexT = typename ToIndexT::argument_type;
32  // Prefer SmallVector with zero inline storage over std::vector. IndexedMaps
33  // can grow very large and SmallVector grows more efficiently as long as T
34  // is trivially copyable.
36 
37  StorageT storage_;
38  T nullVal_;
39  ToIndexT toIndex_;
40 
41  public:
42  IndexedMap() : nullVal_(T()) {}
43 
44  explicit IndexedMap(const T& val) : nullVal_(val) {}
45 
46  typename StorageT::reference operator[](IndexT n) {
47  assert(toIndex_(n) < storage_.size() && "index out of bounds!");
48  return storage_[toIndex_(n)];
49  }
50 
51  typename StorageT::const_reference operator[](IndexT n) const {
52  assert(toIndex_(n) < storage_.size() && "index out of bounds!");
53  return storage_[toIndex_(n)];
54  }
55 
56  void reserve(typename StorageT::size_type s) {
57  storage_.reserve(s);
58  }
59 
60  void resize(typename StorageT::size_type s) {
61  storage_.resize(s, nullVal_);
62  }
63 
64  void clear() {
65  storage_.clear();
66  }
67 
68  void grow(IndexT n) {
69  unsigned NewSize = toIndex_(n) + 1;
70  if (NewSize > storage_.size())
71  resize(NewSize);
72  }
73 
74  bool inBounds(IndexT n) const {
75  return toIndex_(n) < storage_.size();
76  }
77 
78  typename StorageT::size_type size() const {
79  return storage_.size();
80  }
81  };
82 
83 } // end namespace llvm
84 
85 #endif // LLVM_ADT_INDEXEDMAP_H
StorageT::size_type size() const
Definition: IndexedMap.h:78
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
StorageT::reference operator[](IndexT n)
Definition: IndexedMap.h:46
void reserve(size_type N)
Definition: SmallVector.h:380
IndexedMap(const T &val)
Definition: IndexedMap.h:44
typename SuperClass::size_type size_type
Definition: SmallVector.h:330
bool inBounds(IndexT n) const
Definition: IndexedMap.h:74
void resize(typename StorageT::size_type s)
Definition: IndexedMap.h:60
void reserve(typename StorageT::size_type s)
Definition: IndexedMap.h:56
void grow(IndexT n)
Definition: IndexedMap.h:68
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StorageT::const_reference operator[](IndexT n) const
Definition: IndexedMap.h:51
void resize(size_type N)
Definition: SmallVector.h:355