llvm/ADT/IndexedMap.h

0001 //===- llvm/ADT/IndexedMap.h - An index map implementation ------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file implements an indexed map. The index map template takes two
0011 /// types. The first is the mapped type and the second is a functor
0012 /// that maps its argument to a size_t. On instantiation a "null" value
0013 /// can be provided to be used as a "does not exist" indicator in the
0014 /// map. A member function grow() is provided that given the value of
0015 /// the maximally indexed key (the argument of the functor) makes sure
0016 /// the map has enough space for it.
0017 ///
0018 //===----------------------------------------------------------------------===//
0019
0020 #ifndef LLVM_ADT_INDEXEDMAP_H
0021 #define LLVM_ADT_INDEXEDMAP_H
0022
0023 #include "llvm/ADT/SmallVector.h"
0024 #include "llvm/ADT/STLExtras.h"
0025 #include "llvm/ADT/identity.h"
0026 #include <cassert>
0027
0028 namespace llvm {
0029
0030 template <typename T, typename ToIndexT = identity<unsigned>>
0031   class IndexedMap {
0032     using IndexT = typename ToIndexT::argument_type;
0033     // Prefer SmallVector with zero inline storage over std::vector. IndexedMaps
0034     // can grow very large and SmallVector grows more efficiently as long as T
0035     // is trivially copyable.
0036     using StorageT = SmallVector<T, 0>;
0037
0038     StorageT storage_;
0039     T nullVal_;
0040     ToIndexT toIndex_;
0041
0042   public:
0043     IndexedMap() : nullVal_(T()) {}
0044
0045     explicit IndexedMap(const T& val) : nullVal_(val) {}
0046
0047     typename StorageT::reference operator[](IndexT n) {
0048       assert(toIndex_(n) < storage_.size() && "index out of bounds!");
0049       return storage_[toIndex_(n)];
0050     }
0051
0052     typename StorageT::const_reference operator[](IndexT n) const {
0053       assert(toIndex_(n) < storage_.size() && "index out of bounds!");
0054       return storage_[toIndex_(n)];
0055     }
0056
0057     void reserve(typename StorageT::size_type s) {
0058       storage_.reserve(s);
0059     }
0060
0061     void resize(typename StorageT::size_type s) {
0062       storage_.resize(s, nullVal_);
0063     }
0064
0065     void clear() {
0066       storage_.clear();
0067     }
0068
0069     void grow(IndexT n) {
0070       unsigned NewSize = toIndex_(n) + 1;
0071       if (NewSize > storage_.size())
0072         resize(NewSize);
0073     }
0074
0075     bool inBounds(IndexT n) const {
0076       return toIndex_(n) < storage_.size();
0077     }
0078
0079     typename StorageT::size_type size() const {
0080       return storage_.size();
0081     }
0082   };
0083
0084 } // end namespace llvm
0085
0086 #endif // LLVM_ADT_INDEXEDMAP_H