include/llvm/ADT/FlatArrayMap.h

   1 //===- llvm/ADT/FlatArrayMap.h - 'Normally small' pointer set ----*- C++ -*-==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the FlatArrayMap class.
  11 // See FlatArrayMap doxygen comments for more details.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef FLATARRAYMAP_H_
  16 #define FLATARRAYMAP_H_
  17
  18 #include <algorithm>
  19 #include <utility>
  20 #include "llvm/Support/type_traits.h"
  21
  22 namespace llvm {
  23
  24   template <typename KeyTy, typename MappedTy>
  25   struct FlatArrayMapTypes {
  26     typedef KeyTy key_type;
  27     typedef MappedTy mapped_type;
  28     typedef typename std::pair<key_type, mapped_type> value_type;
  29   };
  30
  31   template<typename KeyTy, typename MappedTy, bool IsConst = false>
  32   class FlatArrayMapIterator;
  33
  34   //===--------------------------------------------------------------------===//
  35   /// FlatArrayMap presents map container interface.
  36   /// It uses flat array implementation inside:
  37   /// [ <key0, value0>, <key1, value1>, ... <keyN, valueN> ]
  38   /// It works fast for small amount of elements.
  39   /// User should pass key type, mapped type (type of value), and maximum
  40   /// number of elements.
  41   /// After maximum number of elements is reached, map declines any farther
  42   /// attempts to insert new elements ("insert" method returns <end(),false>).
  43   ///
  44   template <typename KeyTy, typename MappedTy, unsigned MaxArraySize>
  45   class FlatArrayMap {
  46   public:
  47     typedef FlatArrayMapTypes<KeyTy, MappedTy> Types;
  48
  49     typedef typename Types::key_type key_type;
  50     typedef typename Types::mapped_type mapped_type;
  51     typedef typename Types::value_type value_type;
  52
  53     typedef FlatArrayMapIterator<KeyTy, MappedTy> iterator;
  54     typedef FlatArrayMapIterator<KeyTy, MappedTy, true> const_iterator;
  55
  56     typedef FlatArrayMap<KeyTy, MappedTy, MaxArraySize> self;
  57
  58   private:
  59
  60     enum { BadIndex = -1U };
  61
  62     key_type EmptyKey;
  63     mapped_type EmptyValue;
  64
  65     value_type Array[MaxArraySize + 1];
  66     unsigned NumElements;
  67
  68   unsigned findFor(const KeyTy Ptr) const {
  69     // Linear search for the item.
  70     for (const value_type *APtr = Array, *E = Array + NumElements;
  71                APtr != E; ++APtr) {
  72       if (APtr->first == Ptr) {
  73         return APtr - Array;
  74       }
  75     }
  76     return BadIndex;
  77   }
  78
  79   bool lookupFor(const KeyTy &Ptr, const value_type*& Found) const {
  80     unsigned FoundIdx = findFor(Ptr);
  81     if (FoundIdx != BadIndex) {
  82       Found = Array + FoundIdx;
  83       return true;
  84     }
  85     return false;
  86   }
  87
  88   bool lookupFor(const KeyTy &Ptr, value_type*& Found) {
  89     unsigned FoundIdx = findFor(Ptr);
  90     if (FoundIdx != BadIndex) {
  91       Found = Array + FoundIdx;
  92       return true;
  93     }
  94     return false;
  95   }
  96
  97
  98   void copyFrom(const self &RHS) {
  99     std::copy(RHS.Array, RHS.Array + MaxArraySize + 1, Array);
 100     NumElements = RHS.NumElements;
 101   }
 102
 103   void init () {
 104     // Even if Array contains non POD, use memset for last element,
 105     // since it is used as end() iterator only.
 106     memset(Array + MaxArraySize, 0, sizeof(value_type));
 107     NumElements = 0;
 108   }
 109
 110   bool insertInternal(KeyTy Ptr, MappedTy Val, value_type*& Item) {
 111     // Check to see if it is already in the set.
 112     value_type *Found;
 113     if (lookupFor(Ptr, Found)) {
 114       Item = Found;
 115       return false;
 116     }
 117     if (NumElements < MaxArraySize) {
 118       unsigned Idx = NumElements++;
 119       Array[Idx] = std::make_pair(Ptr, Val);
 120       Item = Array + Idx;
 121       return true;
 122     }
 123     Item = Array + MaxArraySize; // return end()
 124     return false;
 125   }
 126
 127   public:
 128
 129     // Constructors
 130
 131     FlatArrayMap() : EmptyKey(), EmptyValue() {
 132       init();
 133     }
 134
 135     FlatArrayMap(const self &that) :
 136       EmptyKey(), EmptyValue() {
 137       copyFrom(that);
 138     }
 139
 140     template<typename It>
 141     FlatArrayMap(It I, It E) :
 142       EmptyKey(), EmptyValue() {
 143       init();
 144       insert(I, E);
 145     }
 146
 147     // Size
 148
 149     unsigned size() const {
 150       return NumElements;
 151     }
 152
 153     bool empty() const {
 154       return !NumElements;
 155     }
 156
 157     // Iterators
 158
 159     iterator begin() {
 160       return iterator(Array);
 161     }
 162     const_iterator begin() const {
 163       return const_iterator(Array);
 164     }
 165
 166     iterator end() {
 167       return iterator(Array + NumElements);
 168     }
 169     const_iterator end() const {
 170       return const_iterator(Array + NumElements);
 171     }
 172
 173     // Modifiers
 174
 175     void clear() {
 176       for (unsigned i = 0; i < NumElements; ++i) {
 177         Array[i].first = EmptyKey;
 178         Array[i].second = EmptyValue;
 179       }
 180       NumElements = 0;
 181     }
 182
 183     // The map container is extended by inserting a single new element.
 184     // The behavior is the same as the std::map::insert, except the
 185     // case when maximum number of elements is reached;
 186     // in this case map declines any farther attempts
 187     // to insert new elements ("insert" method returns <end(),false>).
 188     std::pair<iterator, bool> insert(const value_type& KV) {
 189       value_type* Item;
 190       bool Res = insertInternal(KV.first, KV.second, Item);
 191       return std::make_pair(iterator(Item), Res);
 192     }
 193
 194     template <typename IterT>
 195     void insert(IterT I, IterT E) {
 196       for (; I != E; ++I)
 197         insert(*I);
 198     }
 199
 200     void erase(key_type K) {
 201       unsigned Found = findFor(K);
 202       if (Found != BadIndex) {
 203         value_type *APtr = Array + Found;
 204         value_type *E = Array + NumElements;
 205         *APtr = E[-1];
 206         E[-1].first.~key_type();
 207         E[-1].second.~mapped_type();
 208         --NumElements;
 209       }
 210     }
 211
 212     void erase(iterator i) {
 213       erase(i->first);
 214     }
 215
 216     void swap(self& RHS) {
 217       std::swap_ranges(Array, Array+MaxArraySize,  RHS.Array);
 218       std::swap(this->NumElements, RHS.NumElements);
 219     }
 220
 221     // Search operations
 222
 223     iterator find(const key_type& K) {
 224       value_type *Found;
 225       if (lookupFor(K, Found))
 226         return iterator(Found);
 227       return end();
 228     }
 229
 230     const_iterator find(const key_type& K) const {
 231       const value_type *Found;
 232       if (lookupFor(K, Found))
 233         return const_iterator(Found);
 234       return end();
 235     }
 236
 237     bool count(const key_type& K) const {
 238       return find(K) != end();
 239     }
 240
 241     mapped_type &operator[](const key_type &Key) {
 242       std::pair<iterator, bool> res = insert(Key, mapped_type());
 243       return res.first->second;
 244     }
 245
 246     // Other operations
 247
 248     self& operator=(const self& other) {
 249       clear();
 250       copyFrom(other);
 251       return *this;
 252     }
 253
 254     /// isPointerIntoBucketsArray - Return true if the specified pointer points
 255     /// somewhere into the map's array of buckets (i.e. either to a key or
 256     /// value).
 257     bool isPointerIntoBucketsArray(const void *Ptr) const {
 258       return Ptr >= Array && Ptr < Array + NumElements;
 259     }
 260
 261     /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
 262     /// array.
 263     const void *getPointerIntoBucketsArray() const { return Array; }
 264   };
 265
 266   template<typename KeyTy, typename MappedTy, bool IsConst>
 267   class FlatArrayMapIterator {
 268
 269     typedef FlatArrayMapTypes<KeyTy, MappedTy> Types;
 270
 271     typedef typename conditional<IsConst,
 272                                  const typename Types::value_type,
 273                                  typename Types::value_type>::type value_type;
 274     typedef value_type *pointer;
 275     typedef value_type &reference;
 276
 277     typedef FlatArrayMapIterator<KeyTy, MappedTy, IsConst> self;
 278     typedef FlatArrayMapIterator<KeyTy, MappedTy, false> non_const_self;
 279     typedef FlatArrayMapIterator<KeyTy, MappedTy, true> const_self;
 280
 281     friend class FlatArrayMapIterator<KeyTy, MappedTy, false>;
 282     friend class FlatArrayMapIterator<KeyTy, MappedTy, true>;
 283
 284     pointer TheBucket;
 285
 286   public:
 287
 288     FlatArrayMapIterator() : TheBucket(0) {}
 289
 290     explicit FlatArrayMapIterator(pointer BP) :
 291         TheBucket(BP) {}
 292
 293     // If IsConst is true this is a converting constructor from iterator to
 294     // const_iterator and the default copy constructor is used.
 295     // Otherwise this is a copy constructor for iterator.
 296     FlatArrayMapIterator(const non_const_self& I)
 297       : TheBucket(I.TheBucket) {}
 298
 299     bool operator==(const const_self &RHS) const {
 300       return TheBucket->first == RHS.TheBucket->first;
 301     }
 302     bool operator!=(const const_self &RHS) const {
 303       return TheBucket->first != RHS.TheBucket->first;
 304     }
 305
 306     reference operator*() const {
 307       return *TheBucket;
 308     }
 309
 310     pointer operator->() const {
 311       return TheBucket;
 312     }
 313
 314     inline self& operator++() {   // Preincrement
 315       ++TheBucket;
 316       return *this;
 317     }
 318
 319     self operator++(int) {        // Postincrement
 320       FlatArrayMapIterator tmp = *this; ++*this; return tmp;
 321     }
 322   };
 323 }
 324
 325 #endif /* FLATARRAYMAP_H_ */