1e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao//===-- llvm/ADT/UniqueVector.h ---------------------------------*- C++ -*-===// 2e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// 3e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// The LLVM Compiler Infrastructure 4e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// 5e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// This file is distributed under the University of Illinois Open Source 6e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// License. See LICENSE.TXT for details. 7e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// 8e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao//===----------------------------------------------------------------------===// 9e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 10e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao#ifndef LLVM_ADT_UNIQUEVECTOR_H 11e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao#define LLVM_ADT_UNIQUEVECTOR_H 12e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 13e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao#include <cassert> 14e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao#include <map> 15e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao#include <vector> 16e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 17e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liaonamespace llvm { 18e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 19e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao//===----------------------------------------------------------------------===// 20e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// UniqueVector - This class produces a sequential ID number (base 1) for each 21e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// unique entry that is added. T is the type of entries in the vector. This 22e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// class should have an implementation of operator== and of operator<. 23e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// Entries can be fetched using operator[] with the entry ID. 24e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liaotemplate<class T> class UniqueVector { 25cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinespublic: 26cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines typedef typename std::vector<T> VectorType; 27cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines typedef typename VectorType::iterator iterator; 28cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines typedef typename VectorType::const_iterator const_iterator; 29cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 30e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liaoprivate: 31e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Map - Used to handle the correspondence of entry to ID. 32e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao std::map<T, unsigned> Map; 33e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 34e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Vector - ID ordered vector of entries. Entries can be indexed by ID - 1. 35e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // 36cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines VectorType Vector; 37e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 38e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liaopublic: 39e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// insert - Append entry to the vector if it doesn't already exist. Returns 40e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// the entry's index + 1 to be used as a unique ID. 41e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao unsigned insert(const T &Entry) { 42e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Check if the entry is already in the map. 43e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao unsigned &Val = Map[Entry]; 44e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 45e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // See if entry exists, if so return prior ID. 46e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao if (Val) return Val; 47e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 48e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Compute ID for entry. 49e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao Val = static_cast<unsigned>(Vector.size()) + 1; 50e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 51e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Insert in vector. 52e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao Vector.push_back(Entry); 53e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return Val; 54e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 55e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 56e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// idFor - return the ID for an existing entry. Returns 0 if the entry is 57e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// not found. 58e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao unsigned idFor(const T &Entry) const { 59e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Search for entry in the map. 60e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao typename std::map<T, unsigned>::const_iterator MI = Map.find(Entry); 61e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 62e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // See if entry exists, if so return ID. 63e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao if (MI != Map.end()) return MI->second; 64e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 65e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // No luck. 66e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return 0; 67e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 68e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 69e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// operator[] - Returns a reference to the entry with the specified ID. 70e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// 71e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao const T &operator[](unsigned ID) const { 72e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao assert(ID-1 < size() && "ID is 0 or out of range!"); 73e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return Vector[ID - 1]; 74e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 75e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 76cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// \brief Return an iterator to the start of the vector. 77cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines iterator begin() { return Vector.begin(); } 78cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 79cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// \brief Return an iterator to the start of the vector. 80cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const_iterator begin() const { return Vector.begin(); } 81cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 82cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// \brief Return an iterator to the end of the vector. 83cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines iterator end() { return Vector.end(); } 84cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 85cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// \brief Return an iterator to the end of the vector. 86cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const_iterator end() const { return Vector.end(); } 87cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 88e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// size - Returns the number of entries in the vector. 89e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// 90e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao size_t size() const { return Vector.size(); } 91e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 92e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// empty - Returns true if the vector is empty. 93e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// 94e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao bool empty() const { return Vector.empty(); } 95e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 96e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// reset - Clears all the entries. 97e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// 98e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao void reset() { 99e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao Map.clear(); 100e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao Vector.resize(0, 0); 101e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 102e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao}; 103e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 104e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao} // End of namespace llvm 105e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 106e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao#endif // LLVM_ADT_UNIQUEVECTOR_H 107