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     memcpy(Array, RHS.Array, sizeof(value_type) * (MaxArraySize + 1));
 100     NumElements = RHS.NumElements;
 101   }
 102
 103   void init () {
 104     memset(Array + MaxArraySize, 0, sizeof(value_type));
 105     NumElements = 0;
 106   }
 107
 108   bool insertInternal(KeyTy Ptr, MappedTy Val, value_type*& Item) {
 109     // Check to see if it is already in the set.
 110     value_type *Found;
 111     if (lookupFor(Ptr, Found)) {
 112       Item = Found;
 113       return false;
 114     }
 115     if (NumElements < MaxArraySize) {
 116       unsigned Idx = NumElements++;
 117       Array[Idx] = std::make_pair(Ptr, Val);
 118       Item = Array + Idx;
 119       return true;
 120     }
 121     Item = Array + MaxArraySize; // return end()
 122     return false;
 123   }
 124
 125   public:
 126
 127     // Constructors
 128
 129     FlatArrayMap() : EmptyKey(), EmptyValue() {
 130       init();
 131     }
 132
 133     FlatArrayMap(const self &that) :
 134       EmptyKey(), EmptyValue() {
 135       copyFrom(that);
 136     }
 137
 138     template<typename It>
 139     FlatArrayMap(It I, It E) :
 140       EmptyKey(), EmptyValue() {
 141       init();
 142       insert(I, E);
 143     }
 144
 145     // Size
 146
 147     unsigned size() const {
 148       return NumElements;
 149     }
 150
 151     bool empty() const {
 152       return !NumElements;
 153     }
 154
 155     // Iterators
 156
 157     iterator begin() {
 158       return iterator(Array);
 159     }
 160     const_iterator begin() const {
 161       return const_iterator(Array);
 162     }
 163
 164     iterator end() {
 165       return iterator(Array + NumElements);
 166     }
 167     const_iterator end() const {
 168       return const_iterator(Array + NumElements);
 169     }
 170
 171     // Modifiers
 172
 173     void clear() {
 174       for (unsigned i = 0; i < NumElements; ++i) {
 175         Array[i].first = EmptyKey;
 176         Array[i].second = EmptyValue;
 177       }
 178       NumElements = 0;
 179     }
 180
 181     // The map container is extended by inserting a single new element.
 182     // The behavior is the same as the std::map::insert, except the
 183     // case when maximum number of elements is reached;
 184     // in this case map declines any farther attempts
 185     // to insert new elements ("insert" method returns <end(),false>).
 186     std::pair<iterator, bool> insert(const value_type& KV) {
 187       value_type* Item;
 188       bool Res = insertInternal(KV.first, KV.second, Item);
 189       return std::make_pair(iterator(Item), Res);
 190     }
 191
 192     template <typename IterT>
 193     void insert(IterT I, IterT E) {
 194       for (; I != E; ++I)
 195         insert(*I);
 196     }
 197
 198     void erase(key_type K) {
 199       unsigned Found = findFor(K);
 200       if (Found != BadIndex) {
 201         value_type *APtr = Array + Found;
 202         value_type *E = Array + NumElements;
 203         *APtr = E[-1];
 204         E[-1].first.~key_type();
 205         E[-1].second.~mapped_type();
 206         --NumElements;
 207       }
 208     }
 209
 210     void erase(iterator i) {
 211       erase(i->first);
 212     }
 213
 214     void swap(self& RHS) {
 215       std::swap_ranges(Array, Array+MaxArraySize,  RHS.Array);
 216       std::swap(this->NumElements, RHS.NumElements);
 217     }
 218
 219     // Search operations
 220
 221     iterator find(const key_type& K) {
 222       value_type *Found;
 223       if (lookupFor(K, Found))
 224         return iterator(Found);
 225       return end();
 226     }
 227
 228     const_iterator find(const key_type& K) const {
 229       const value_type *Found;
 230       if (lookupFor(K, Found))
 231         return const_iterator(Found);
 232       return end();
 233     }
 234
 235     bool count(const key_type& K) const {
 236       return find(K) != end();
 237     }
 238
 239     mapped_type &operator[](const key_type &Key) {
 240       std::pair<iterator, bool> res = insert(Key, mapped_type());
 241       return res.first->second;
 242     }
 243
 244     // Other operations
 245
 246     self& operator=(const self& other) {
 247       clear();
 248       copyFrom(other);
 249       return *this;
 250     }
 251
 252     /// isPointerIntoBucketsArray - Return true if the specified pointer points
 253     /// somewhere into the map's array of buckets (i.e. either to a key or
 254     /// value).
 255     bool isPointerIntoBucketsArray(const void *Ptr) const {
 256       return Ptr >= Array && Ptr < Array + NumElements;
 257     }
 258
 259     /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
 260     /// array.
 261     const void *getPointerIntoBucketsArray() const { return Array; }
 262   };
 263
 264   template<typename KeyTy, typename MappedTy, bool IsConst>
 265   class FlatArrayMapIterator {
 266
 267     typedef FlatArrayMapTypes<KeyTy, MappedTy> Types;
 268
 269     typedef typename conditional<IsConst,
 270                                  const typename Types::value_type,
 271                                  typename Types::value_type>::type value_type;
 272     typedef value_type *pointer;
 273     typedef value_type &reference;
 274
 275     typedef FlatArrayMapIterator<KeyTy, MappedTy, IsConst> self;
 276     typedef FlatArrayMapIterator<KeyTy, MappedTy, false> non_const_self;
 277     typedef FlatArrayMapIterator<KeyTy, MappedTy, true> const_self;
 278
 279     friend class FlatArrayMapIterator<KeyTy, MappedTy, false>;
 280     friend class FlatArrayMapIterator<KeyTy, MappedTy, true>;
 281
 282     pointer TheBucket;
 283
 284   public:
 285
 286     FlatArrayMapIterator() : TheBucket(0) {}
 287
 288     explicit FlatArrayMapIterator(pointer BP) :
 289         TheBucket(BP) {}
 290
 291     // If IsConst is true this is a converting constructor from iterator to
 292     // const_iterator and the default copy constructor is used.
 293     // Otherwise this is a copy constructor for iterator.
 294     FlatArrayMapIterator(const non_const_self& I)
 295       : TheBucket(I.TheBucket) {}
 296
 297     bool operator==(const const_self &RHS) const {
 298       return TheBucket->first == RHS.TheBucket->first;
 299     }
 300     bool operator!=(const const_self &RHS) const {
 301       return TheBucket->first != RHS.TheBucket->first;
 302     }
 303
 304     reference operator*() const {
 305       return *TheBucket;
 306     }
 307
 308     pointer operator->() const {
 309       return TheBucket;
 310     }
 311
 312     inline self& operator++() {   // Preincrement
 313       ++TheBucket;
 314       return *this;
 315     }
 316
 317     self operator++(int) {        // Postincrement
 318       FlatArrayMapIterator tmp = *this; ++*this; return tmp;
 319     }
 320   };
 321 }
 322
 323 #endif /* FLATARRAYMAP_H_ */