1193323Sed//===- llvm/ADT/IndexedMap.h - An index map implementation ------*- C++ -*-===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This file implements an indexed map. The index map template takes two 10193323Sed// types. The first is the mapped type and the second is a functor 11193323Sed// that maps its argument to a size_t. On instantiation a "null" value 12193323Sed// can be provided to be used as a "does not exist" indicator in the 13193323Sed// map. A member function grow() is provided that given the value of 14193323Sed// the maximally indexed key (the argument of the functor) makes sure 15193323Sed// the map has enough space for it. 16193323Sed// 17193323Sed//===----------------------------------------------------------------------===// 18193323Sed 19193323Sed#ifndef LLVM_ADT_INDEXEDMAP_H 20193323Sed#define LLVM_ADT_INDEXEDMAP_H 21193323Sed 22321369Sdim#include "llvm/ADT/SmallVector.h" 23239462Sdim#include "llvm/ADT/STLExtras.h" 24193323Sed#include <cassert> 25193323Sed 26193323Sednamespace llvm { 27193323Sed 28321369Sdimtemplate <typename T, typename ToIndexT = identity<unsigned>> 29193323Sed class IndexedMap { 30321369Sdim using IndexT = typename ToIndexT::argument_type; 31288943Sdim // Prefer SmallVector with zero inline storage over std::vector. IndexedMaps 32288943Sdim // can grow very large and SmallVector grows more efficiently as long as T 33288943Sdim // is trivially copyable. 34321369Sdim using StorageT = SmallVector<T, 0>; 35321369Sdim 36193323Sed StorageT storage_; 37193323Sed T nullVal_; 38193323Sed ToIndexT toIndex_; 39193323Sed 40193323Sed public: 41321369Sdim IndexedMap() : nullVal_(T()) {} 42193323Sed 43321369Sdim explicit IndexedMap(const T& val) : nullVal_(val) {} 44193323Sed 45193323Sed typename StorageT::reference operator[](IndexT n) { 46193323Sed assert(toIndex_(n) < storage_.size() && "index out of bounds!"); 47193323Sed return storage_[toIndex_(n)]; 48193323Sed } 49193323Sed 50193323Sed typename StorageT::const_reference operator[](IndexT n) const { 51193323Sed assert(toIndex_(n) < storage_.size() && "index out of bounds!"); 52193323Sed return storage_[toIndex_(n)]; 53193323Sed } 54193323Sed 55218893Sdim void reserve(typename StorageT::size_type s) { 56218893Sdim storage_.reserve(s); 57218893Sdim } 58218893Sdim 59218893Sdim void resize(typename StorageT::size_type s) { 60218893Sdim storage_.resize(s, nullVal_); 61218893Sdim } 62218893Sdim 63193323Sed void clear() { 64193323Sed storage_.clear(); 65193323Sed } 66193323Sed 67193323Sed void grow(IndexT n) { 68193323Sed unsigned NewSize = toIndex_(n) + 1; 69193323Sed if (NewSize > storage_.size()) 70218893Sdim resize(NewSize); 71193323Sed } 72193323Sed 73218893Sdim bool inBounds(IndexT n) const { 74218893Sdim return toIndex_(n) < storage_.size(); 75218893Sdim } 76218893Sdim 77193323Sed typename StorageT::size_type size() const { 78193323Sed return storage_.size(); 79193323Sed } 80193323Sed }; 81193323Sed 82321369Sdim} // end namespace llvm 83193323Sed 84321369Sdim#endif // LLVM_ADT_INDEXEDMAP_H 85