include/llvm/ADT/MultiImplMap.h

   1 //===- llvm/ADT/MultiImplMap.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 MultiImplMap class.
  11 // MultiImplMap presents map container interface.
  12 // It has two modes, one for small amount of elements and one for big amount.
  13 // User should set map implementation for both of them. User also should
  14 // set the maximum possible number of elements for small mode.
  15 // If user want to use MultiImplMap instead of DenseMap, he should pass
  16 // DenseMapCompatible = true. Note that in this case map implementations should
  17 // present additional DenseMap specific methods (see below).
  18 // Initially MultiImplMap uses small mode and small map implementation.
  19 // It triggered to the big mode when number of contained elements exceeds
  20 // maximum possible elements for small mode.
  21 //
  22 // Types that should be defined in nested map class:
  23 //
  24 //    key_type;
  25 //    mapped_type;
  26 //    value_type; // std::pair<key_type, mapped_type>
  27 //                // or std::pair<const key_type, mapped_type>
  28 //    iterator;
  29 //    const_iterator;
  30 //
  31 // Map implementation should provide the next interface:
  32 //
  33 //    // Constructors
  34 //    (default constructor)
  35 //    (copy constructor)
  36 //
  37 //    // Size
  38 //    unsigned size() const;
  39 //    bool empty() const;
  40 //
  41 //    // Iterators
  42 //    iterator begin();
  43 //    const_iterator begin();
  44 //    iterator end();
  45 //    const_iterator end();
  46 //
  47 //    // Modifiers
  48 //    void clear();
  49 //    std::pair<iterator, bool> insert(const value_type& KV);
  50 //    template <typename IterT>
  51 //      void insert(IterT I, IterT E);
  52 //    void erase(key_type K);
  53 //    void erase(iterator i);
  54 //    void swap(MultiImplMap& rhs);
  55 //
  56 //    // Search operations
  57 //    iterator find(const key_type& K);
  58 //    const_iterator find(const key_type& K) const;
  59 //    bool count(const key_type& K) const;
  60 //    mapped_type &operator[](const key_type &Key);
  61 //
  62 //    // Other operations
  63 //    self& operator=(const self& other);
  64 //
  65 //    // If DenseMapCompatible == true, you also should present next methods.
  66 //    // See DenseMap comments for more details about its behavior.
  67 //    bool isPointerIntoBucketsArray(const void *Ptr) const;
  68 //    const void *getPointerIntoBucketsArray() const;
  69 //    value_type& FindAndConstruct(const key_type &Key);
  70 //
  71 // The list of methods that should be implemented in nested map iterator class:
  72 //
  73 //    (conversion constructor from non-constant iterator)
  74 //
  75 //    bool operator==(const const_iterator& rhs) const;
  76 //    bool operator!=(const const_iterator& rhs) const;
  77 //    reference operator*() const;
  78 //    pointer operator->() const;
  79 //    inline self& operator++();
  80 //
  81 //
  82 //===----------------------------------------------------------------------===//
  83
  84 #ifndef MULTIIMPLEMENTATIONMAP_H_
  85 #define MULTIIMPLEMENTATIONMAP_H_
  86
  87
  88 #include <algorithm>
  89 #include <utility>
  90 #include "llvm/ADT/DenseMap.h"
  91 #include "llvm/ADT/FlatArrayMap.h"
  92 #include "llvm/Support/type_traits.h"
  93
  94 namespace llvm {
  95
  96   template<class SmallMapTy, class BigMapTy, bool IsConst = false>
  97   class MultiImplMapIterator;
  98
  99   template<class SmallMapTy, class BigMapTy>
 100     struct MultiImplMapIteratorsFactory;
 101
 102   template<class SmallMapTy, class BigMapTy>
 103   struct MultiImplMapTypes {
 104     typedef typename SmallMapTy::key_type key_type;
 105     typedef typename SmallMapTy::mapped_type mapped_type;
 106     typedef typename std::pair<key_type, mapped_type> value_type;
 107   };
 108
 109   //===--------------------------------------------------------------------===//
 110   /// MultiImplMap is map that has two modes, one for small amount of
 111   /// elements and one for big amount.
 112   /// User should set map implementation for both of them. User also should
 113   /// set the maximum possible number of elements for small mode.
 114   /// If user want to use MultiImplMap instead of DenseMap, he should pass
 115   /// DenseMapCompatible = true.
 116   /// Initially MultiImplMap uses small mode and small map implementation.
 117   /// It triggered to the big mode when number of contained elements exceeds
 118   /// maximum possible elements for small mode.
 119   template<class SmallMapTy, class BigMapTy, unsigned MaxSmallN,
 120            bool DenseMapCompatible = false,
 121            class ItFactory =
 122                MultiImplMapIteratorsFactory<SmallMapTy, BigMapTy> >
 123   class MultiImplMap {
 124
 125   protected:
 126     SmallMapTy SmallMap;
 127     BigMapTy BigMap;
 128     bool UseSmall;
 129     enum { MaxSmallSize = MaxSmallN };
 130
 131   public:
 132     typedef MultiImplMapTypes<SmallMapTy, BigMapTy> Types;
 133
 134     typedef typename Types::key_type key_type;
 135     typedef typename Types::mapped_type mapped_type;
 136     typedef typename Types::value_type value_type;
 137
 138     typedef typename ItFactory::iterator iterator;
 139     typedef typename ItFactory::const_iterator const_iterator;
 140
 141     typedef std::pair<iterator, bool> ins_res;
 142
 143     typedef typename std::pair<typename SmallMapTy::iterator, bool>
 144       small_ins_res;
 145
 146     typedef typename std::pair<typename BigMapTy::iterator, bool>
 147       big_ins_res;
 148
 149     typedef MultiImplMap<SmallMapTy, BigMapTy, MaxSmallN> self;
 150
 151     MultiImplMap() : UseSmall(true) {}
 152
 153     MultiImplMap(const self& other) {
 154       if (other.UseSmall) {
 155         SmallMap = other.SmallMap;
 156         UseSmall = true;
 157       } else {
 158         if (other.size() <= MaxSmallN) {
 159           SmallMap.insert(other.BigMap.begin(), other.BigMap.end());
 160           UseSmall = true;
 161         } else {
 162           BigMap = other.BigMap;
 163           UseSmall = false;
 164         }
 165       }
 166     }
 167
 168     // Size
 169
 170     unsigned size() const {
 171       if (UseSmall)
 172         return SmallMap.size();
 173       return BigMap.size();
 174     }
 175
 176     bool empty() const {
 177       if (UseSmall)
 178         return SmallMap.empty();
 179       return BigMap.empty();
 180     }
 181
 182     // Iterators
 183
 184     iterator begin() {
 185       if (UseSmall)
 186         return ItFactory::begin(SmallMap);
 187       return ItFactory::begin(BigMap);
 188     }
 189     const_iterator begin() const {
 190       if (UseSmall)
 191         return ItFactory::begin(SmallMap);
 192       return ItFactory::begin(BigMap);
 193     }
 194
 195     iterator end() {
 196       if (UseSmall)
 197         return ItFactory::end(SmallMap);
 198       return ItFactory::end(BigMap);
 199     }
 200     const_iterator end() const {
 201       if (UseSmall)
 202         return ItFactory::end(SmallMap);
 203       return ItFactory::end(BigMap);
 204     }
 205
 206     // Modifiers
 207
 208     void clear() {
 209       if (UseSmall)
 210         SmallMap.clear();
 211       else
 212         BigMap.clear();
 213     }
 214
 215     std::pair<iterator, bool> insert(const value_type& KV) {
 216       if (UseSmall) {
 217         if (SmallMap.size() < MaxSmallSize) {
 218           small_ins_res Res = SmallMap.insert(KV);
 219           return std::make_pair(ItFactory::it(SmallMap, Res.first), Res.second);
 220         }
 221
 222         // Move all to big map.
 223         BigMap.insert(SmallMap.begin(), SmallMap.end());
 224         SmallMap.clear();
 225
 226         UseSmall = false;
 227       }
 228       big_ins_res Res = BigMap.insert(KV);
 229       return std::make_pair(ItFactory::it(BigMap, Res.first), Res.second);
 230     }
 231
 232     template <typename OtherValTy>
 233     std::pair<iterator, bool> insert(const OtherValTy& OtherKV) {
 234       const value_type* KV = reinterpret_cast<const value_type*>(
 235           reinterpret_cast<const void*>(OtherKV));
 236       return insert(*KV);
 237     }
 238
 239     template <typename IterT>
 240     void insert(IterT I, IterT E) {
 241       for (; I != E; ++I)
 242         insert(*I);
 243     }
 244
 245     void erase(key_type K) {
 246       if (UseSmall)
 247         SmallMap.erase(K);
 248       else
 249         BigMap.erase(K);
 250     }
 251
 252     void erase(iterator i) {
 253       erase(i->first);
 254     }
 255
 256     void swap(MultiImplMap& rhs) {
 257       SmallMap.swap(rhs.SmallMap);
 258       BigMap.swap(rhs.BigMap);
 259       std::swap(UseSmall, rhs.UseSmall);
 260     }
 261
 262     // Search operations
 263
 264     iterator find(const key_type& K) {
 265       if (UseSmall)
 266         return ItFactory::it(SmallMap, SmallMap.find(K));
 267       return ItFactory::it(BigMap, BigMap.find(K));
 268     }
 269
 270     const_iterator find(const key_type& K) const {
 271       if (UseSmall)
 272         return ItFactory::const_it(SmallMap, SmallMap.find(K));
 273       return ItFactory::const_it(BigMap, BigMap.find(K));
 274     }
 275
 276     bool count(const key_type& K) const {
 277       return find(K) != end();
 278     }
 279
 280     mapped_type &operator[](const key_type &Key) {
 281       ins_res res = insert(std::make_pair(Key, mapped_type()));
 282       return res.first->second;
 283     }
 284
 285     // Other operations
 286
 287     self& operator=(const self& other) {
 288       if (other.isSmall()) {
 289         SmallMap = other.SmallMap;
 290         if (!UseSmall) {
 291           BigMap.clear();
 292           UseSmall = true;
 293         }
 294         return *this;
 295       }
 296       if (UseSmall) {
 297         SmallMap.clear();
 298         UseSmall = false;
 299       }
 300       BigMap = other.BigMap;
 301       return *this;
 302     }
 303
 304     // Utilities
 305
 306     bool isSmall()const {
 307       return UseSmall;
 308     }
 309
 310     SmallMapTy& getSmallMap() {
 311       return SmallMap;
 312     }
 313
 314     const SmallMapTy& getSmallMap() const {
 315       return SmallMap;
 316     }
 317
 318     BigMapTy& getBigMap() {
 319       return BigMap;
 320     }
 321
 322     const BigMapTy& getBigMap() const {
 323       return BigMap;
 324     }
 325   };
 326
 327   template<class SmallMapTy, class BigMapTy, unsigned MaxSmallN>
 328   class MultiImplMap<SmallMapTy, BigMapTy, MaxSmallN, true> :
 329         public MultiImplMap<SmallMapTy, BigMapTy, MaxSmallN, false>
 330   {
 331   public:
 332     typedef MultiImplMap<SmallMapTy, BigMapTy, MaxSmallN, false> ParentTy;
 333     typedef typename ParentTy::Types Types;
 334
 335     typedef typename Types::key_type key_type;
 336     typedef typename Types::mapped_type mapped_type;
 337     typedef typename Types::value_type value_type;
 338     typedef typename ParentTy::iterator iterator;
 339
 340     /// isPointerIntoBucketsArray - Return true if the specified pointer points
 341     /// somewhere into the DenseMap's array of buckets (i.e. either to a key or
 342     /// value).
 343     bool isPointerIntoBucketsArray(const void *Ptr) const {
 344       if (this->UseSmall)
 345         return this->SmallMap.isPointerIntoBucketsArray(Ptr);
 346       return this->BigMap.isPointerIntoBucketsArray(Ptr);
 347     }
 348
 349     /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
 350     /// array.  In conjunction with the previous method, this can be used to
 351     /// determine whether an insertion caused the map to reallocate data.
 352     const void *getPointerIntoBucketsArray() const {
 353       if (this->UseSmall)
 354         return this->SmallMap.getPointerIntoBucketsArray();
 355       return this->BigMap.getPointerIntoBucketsArray();
 356     }
 357
 358     value_type& FindAndConstruct(const key_type &Key) {
 359       std::pair<iterator, bool> Res =
 360           this->insert(std::make_pair(Key, mapped_type()));
 361       return *Res.first;
 362     }
 363   };
 364
 365   template<class SmallMapTy, class BigMapTy, bool IsConst>
 366   class MultiImplMapIterator {
 367   public:
 368
 369     typedef MultiImplMapTypes<SmallMapTy, BigMapTy> Types;
 370
 371     typedef typename Types::mapped_type mapped_type;
 372
 373     typedef typename conditional<IsConst,
 374                                  const typename Types::value_type,
 375                                  typename Types::value_type>::type value_type;
 376
 377     typedef typename conditional<IsConst,
 378                                  typename SmallMapTy::const_iterator,
 379                                  typename SmallMapTy::iterator>::type
 380                                  small_iterator;
 381
 382     typedef typename conditional<IsConst,
 383                                  typename BigMapTy::const_iterator,
 384                                  typename BigMapTy::iterator>::type
 385                                  big_iterator;
 386
 387     typedef typename conditional<IsConst, const void*, void*>::type void_ptr_ty;
 388
 389     typedef value_type *pointer;
 390     typedef value_type &reference;
 391
 392     typedef MultiImplMapIterator<SmallMapTy, BigMapTy, IsConst> self;
 393
 394     typedef MultiImplMapIterator<SmallMapTy, BigMapTy, false> non_const_self;
 395     typedef MultiImplMapIterator<SmallMapTy, BigMapTy, true> const_self;
 396
 397     friend class MultiImplMapIterator<SmallMapTy, BigMapTy, true>;
 398     friend class MultiImplMapIterator<SmallMapTy, BigMapTy, false>;
 399
 400   protected:
 401
 402     template <typename OtherValTy>
 403     static value_type* toValueTypePtr(OtherValTy& ValTyRef) {
 404       return reinterpret_cast<value_type*>(
 405                reinterpret_cast<void_ptr_ty>(&ValTyRef));
 406     }
 407
 408     template <typename OtherValTy>
 409     static value_type& toValueTypeRef(OtherValTy& ValTyRef) {
 410       return *reinterpret_cast<value_type*>(
 411                 reinterpret_cast<void_ptr_ty>(&ValTyRef));
 412     }
 413
 414     small_iterator SmallIt;
 415     big_iterator BigIt;
 416     bool UseSmall;
 417
 418   public:
 419
 420     MultiImplMapIterator() : UseSmall(true) {}
 421     MultiImplMapIterator(small_iterator It) : SmallIt(It), UseSmall(true) {}
 422     MultiImplMapIterator(big_iterator It) : BigIt(It), UseSmall(false) {}
 423     MultiImplMapIterator(const non_const_self& src) :
 424       SmallIt(src.SmallIt), BigIt(src.BigIt), UseSmall(src.UseSmall) {}
 425
 426     bool operator==(const const_self& rhs) const {
 427       if (UseSmall != rhs.UseSmall)
 428         return false;
 429       if (UseSmall)
 430         return SmallIt == rhs.SmallIt;
 431       return BigIt == rhs.BigIt;
 432     }
 433
 434     bool operator!=(const const_self& rhs) const {
 435       if (UseSmall != rhs.UseSmall)
 436         return true;
 437       if (UseSmall)
 438         return SmallIt != rhs.SmallIt;
 439       return BigIt != rhs.BigIt;
 440     }
 441
 442     reference operator*() const {
 443       return UseSmall ? toValueTypeRef(*SmallIt) : toValueTypeRef(*BigIt);;
 444     }
 445
 446     pointer operator->() const {
 447       return UseSmall ? toValueTypePtr(*SmallIt) : toValueTypePtr(*BigIt);
 448     }
 449
 450     // Preincrement
 451     inline self& operator++() {
 452       if (UseSmall) ++SmallIt;
 453       return *this;
 454     }
 455
 456     // Postincrement
 457     self operator++(int) {
 458       self tmp = *this; ++*this; return tmp;
 459     }
 460   };
 461
 462   template<class SmallMapTy, class BigMapTy>
 463   struct MultiImplMapIteratorsFactory {
 464
 465     typedef MultiImplMapIterator<SmallMapTy, BigMapTy, false> iterator;
 466     typedef MultiImplMapIterator<SmallMapTy, BigMapTy, true> const_iterator;
 467
 468     template<class MapImpl, class ItTy>
 469     static iterator it(MapImpl& impl, ItTy it) {
 470       return iterator(it);
 471     }
 472     template<class MapImpl, class ConstItTy>
 473     static const_iterator const_it(const MapImpl& impl, ConstItTy it) {
 474       return const_iterator(it);
 475     }
 476     template<class MapImpl>
 477     static iterator begin(MapImpl& impl) {
 478       return iterator(impl.begin());
 479     }
 480     template<class MapImpl>
 481     static const_iterator begin(const MapImpl& impl) {
 482       return const_iterator(impl.begin());
 483     }
 484     template<class MapImpl>
 485     static iterator end(MapImpl& impl) {
 486       return iterator(impl.end());
 487     }
 488     template<class MapImpl>
 489     static const_iterator end(const MapImpl& impl) {
 490       return const_iterator(impl.end());
 491     }
 492   };
 493
 494   template<typename KeyTy, typename MappedTy, unsigned MaxArraySize,
 495             typename KeyInfoT>
 496   struct MultiImplMapIteratorsFactory<
 497           FlatArrayMap<KeyTy, MappedTy, MaxArraySize>,
 498           DenseMap<KeyTy, MappedTy, KeyInfoT> >
 499   {
 500
 501     typedef FlatArrayMap<KeyTy, MappedTy, MaxArraySize> SmallMapTy;
 502     typedef DenseMap<KeyTy, MappedTy, KeyInfoT> BigMapTy;
 503
 504     typedef DenseMapIterator<KeyTy, MappedTy, KeyInfoT, false>
 505       iterator;
 506     typedef DenseMapIterator<KeyTy, MappedTy, KeyInfoT, true>
 507       const_iterator;
 508
 509     static iterator it(SmallMapTy& impl, typename SmallMapTy::iterator it) {
 510       return iterator(&(*it), &(*impl.end()));
 511     }
 512     static const_iterator const_it(
 513         const SmallMapTy& impl, typename SmallMapTy::const_iterator it) {
 514       return const_iterator(&(*it), &(*impl.end()));
 515     }
 516     static iterator it(BigMapTy& impl, typename BigMapTy::iterator it) {
 517       return it;
 518     }
 519     static const_iterator const_it(
 520         const BigMapTy& impl, typename BigMapTy::const_iterator it) {
 521       return it;
 522     }
 523     static iterator begin(SmallMapTy& impl) {
 524       return it(impl, impl.begin());
 525     }
 526     static const_iterator begin(const SmallMapTy& impl) {
 527       return it(impl, impl.begin());
 528     }
 529     static iterator begin(BigMapTy& impl) {
 530       return impl.begin();
 531     }
 532     static const_iterator begin(const BigMapTy& impl) {
 533       return impl.begin();
 534     }
 535     static iterator end(SmallMapTy& impl) {
 536       return it(impl, impl.end());
 537     }
 538     static const_iterator end(const SmallMapTy& impl) {
 539       return const_it(impl, impl.end());
 540     }
 541     static iterator end(BigMapTy& impl) {
 542       return impl.end();
 543     }
 544     static const_iterator end(const BigMapTy& impl) {
 545       return impl.end();
 546     }
 547   };
 548 }
 549
 550 #endif /* MULTIIMPLEMENTATIONMAP_H_ */