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