LLVM  16.0.0git
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 /// \file
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
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::SmallVector< T, 0 >
llvm::IndexedMap::clear
void clear()
Definition: IndexedMap.h:64
T
#define T
Definition: Mips16ISelLowering.cpp:341
STLExtras.h
llvm::IndexedMap::operator[]
StorageT::reference operator[](IndexT n)
Definition: IndexedMap.h:46
llvm::IndexedMap::size
StorageT::size_type size() const
Definition: IndexedMap.h:78
llvm::IndexedMap
Definition: IndexedMap.h:30
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:624
llvm::IndexedMap::reserve
void reserve(typename StorageT::size_type s)
Definition: IndexedMap.h:56
val
The initial backend is deliberately restricted to z10 We should add support for later architectures at some point If an asm ties an i32 r result to an i64 the input will be treated as an leaving the upper bits uninitialised For i64 store i32 val
Definition: README.txt:15
s
multiplies can be turned into SHL s
Definition: README.txt:370
llvm::IndexedMap::IndexedMap
IndexedMap(const T &val)
Definition: IndexedMap.h:44
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::IndexedMap::IndexedMap
IndexedMap()
Definition: IndexedMap.h:42
llvm::IndexedMap::operator[]
StorageT::const_reference operator[](IndexT n) const
Definition: IndexedMap.h:51
llvm::IndexedMap::grow
void grow(IndexT n)
Definition: IndexedMap.h:68
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:596
SmallVector.h
llvm::IndexedMap::inBounds
bool inBounds(IndexT n) const
Definition: IndexedMap.h:74
llvm::SmallVectorImpl< unsigned >::size_type
typename SuperClass::size_type size_type
Definition: SmallVector.h:566
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:649
llvm::IndexedMap::resize
void resize(typename StorageT::size_type s)
Definition: IndexedMap.h:60
llvm::SmallVectorImpl< unsigned >::reference
typename SuperClass::reference reference
Definition: SmallVector.h:565