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 "llvm/ADT/identity.h" |
26 | #include <cassert> |
27 | |
28 | namespace llvm { |
29 | |
30 | template <typename T, typename ToIndexT = identity<unsigned>> |
31 | class IndexedMap { |
32 | using IndexT = typename ToIndexT::argument_type; |
33 | // Prefer SmallVector with zero inline storage over std::vector. IndexedMaps |
34 | // can grow very large and SmallVector grows more efficiently as long as T |
35 | // is trivially copyable. |
36 | using StorageT = SmallVector<T, 0>; |
37 | |
38 | StorageT storage_; |
39 | T nullVal_; |
40 | ToIndexT toIndex_; |
41 | |
42 | public: |
43 | IndexedMap() : nullVal_(T()) {} |
44 | |
45 | explicit IndexedMap(const T& val) : nullVal_(val) {} |
46 | |
47 | typename StorageT::reference operator[](IndexT n) { |
48 | assert(toIndex_(n) < storage_.size() && "index out of bounds!" ); |
49 | return storage_[toIndex_(n)]; |
50 | } |
51 | |
52 | typename StorageT::const_reference operator[](IndexT n) const { |
53 | assert(toIndex_(n) < storage_.size() && "index out of bounds!" ); |
54 | return storage_[toIndex_(n)]; |
55 | } |
56 | |
57 | void reserve(typename StorageT::size_type s) { |
58 | storage_.reserve(s); |
59 | } |
60 | |
61 | void resize(typename StorageT::size_type s) { |
62 | storage_.resize(s, nullVal_); |
63 | } |
64 | |
65 | void clear() { |
66 | storage_.clear(); |
67 | } |
68 | |
69 | void grow(IndexT n) { |
70 | unsigned NewSize = toIndex_(n) + 1; |
71 | if (NewSize > storage_.size()) |
72 | resize(s: NewSize); |
73 | } |
74 | |
75 | bool inBounds(IndexT n) const { |
76 | return toIndex_(n) < storage_.size(); |
77 | } |
78 | |
79 | typename StorageT::size_type size() const { |
80 | return storage_.size(); |
81 | } |
82 | }; |
83 | |
84 | } // end namespace llvm |
85 | |
86 | #endif // LLVM_ADT_INDEXEDMAP_H |
87 | |