1 //===- llvm/ADT/MultiImplMap.h - 'Normally small' pointer set ----*- C++ -*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
22 // Types that should be defined in nested map class:
26 // value_type; // std::pair<key_type, mapped_type>
27 // // or std::pair<const key_type, mapped_type>
31 // Map implementation should provide the next interface:
34 // (default constructor)
38 // unsigned size() const;
39 // bool empty() const;
43 // const_iterator begin();
45 // const_iterator end();
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);
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);
62 // // Other operations
63 // self& operator=(const self& other);
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);
71 // The list of methods that should be implemented in nested map iterator class:
73 // (conversion constructor from non-constant iterator)
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++();
82 //===----------------------------------------------------------------------===//
84 #ifndef MULTIIMPLEMENTATIONMAP_H_
85 #define MULTIIMPLEMENTATIONMAP_H_
90 #include "llvm/ADT/DenseMap.h"
91 #include "llvm/ADT/FlatArrayMap.h"
92 #include "llvm/Support/type_traits.h"
96 template<class SmallMapTy, class BigMapTy, bool IsConst = false>
97 class MultiImplMapIterator;
99 template<class SmallMapTy, class BigMapTy>
100 struct MultiImplMapIteratorsFactory;
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;
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,
122 MultiImplMapIteratorsFactory<SmallMapTy, BigMapTy> >
129 enum { MaxSmallSize = MaxSmallN };
132 typedef MultiImplMapTypes<SmallMapTy, BigMapTy> Types;
134 typedef typename Types::key_type key_type;
135 typedef typename Types::mapped_type mapped_type;
136 typedef typename Types::value_type value_type;
138 typedef typename ItFactory::iterator iterator;
139 typedef typename ItFactory::const_iterator const_iterator;
141 typedef std::pair<iterator, bool> ins_res;
143 typedef typename std::pair<typename SmallMapTy::iterator, bool>
146 typedef typename std::pair<typename BigMapTy::iterator, bool>
149 typedef MultiImplMap<SmallMapTy, BigMapTy, MaxSmallN> self;
151 MultiImplMap() : UseSmall(true) {}
153 MultiImplMap(const self& other) {
154 if (other.UseSmall) {
155 SmallMap = other.SmallMap;
158 if (other.size() <= MaxSmallN) {
159 SmallMap.insert(other.BigMap.begin(), other.BigMap.end());
162 BigMap = other.BigMap;
170 unsigned size() const {
172 return SmallMap.size();
173 return BigMap.size();
178 return SmallMap.empty();
179 return BigMap.empty();
186 return ItFactory::begin(SmallMap);
187 return ItFactory::begin(BigMap);
189 const_iterator begin() const {
191 return ItFactory::begin(SmallMap);
192 return ItFactory::begin(BigMap);
197 return ItFactory::end(SmallMap);
198 return ItFactory::end(BigMap);
200 const_iterator end() const {
202 return ItFactory::end(SmallMap);
203 return ItFactory::end(BigMap);
215 std::pair<iterator, bool> insert(const value_type& KV) {
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);
222 // Move all to big map.
223 BigMap.insert(SmallMap.begin(), SmallMap.end());
228 big_ins_res Res = BigMap.insert(KV);
229 return std::make_pair(ItFactory::it(BigMap, Res.first), Res.second);
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));
239 template <typename IterT>
240 void insert(IterT I, IterT E) {
245 void erase(key_type K) {
252 void erase(iterator i) {
256 void swap(MultiImplMap& rhs) {
257 SmallMap.swap(rhs.SmallMap);
258 BigMap.swap(rhs.BigMap);
259 std::swap(UseSmall, rhs.UseSmall);
264 iterator find(const key_type& K) {
266 return ItFactory::it(SmallMap, SmallMap.find(K));
267 return ItFactory::it(BigMap, BigMap.find(K));
270 const_iterator find(const key_type& K) const {
272 return ItFactory::const_it(SmallMap, SmallMap.find(K));
273 return ItFactory::const_it(BigMap, BigMap.find(K));
276 bool count(const key_type& K) const {
277 return find(K) != end();
280 mapped_type &operator[](const key_type &Key) {
281 ins_res res = insert(std::make_pair(Key, mapped_type()));
282 return res.first->second;
287 self& operator=(const self& other) {
288 if (other.isSmall()) {
289 SmallMap = other.SmallMap;
300 BigMap = other.BigMap;
306 bool isSmall()const {
310 SmallMapTy& getSmallMap() {
314 const SmallMapTy& getSmallMap() const {
318 BigMapTy& getBigMap() {
322 const BigMapTy& getBigMap() const {
327 template<class SmallMapTy, class BigMapTy, unsigned MaxSmallN>
328 class MultiImplMap<SmallMapTy, BigMapTy, MaxSmallN, true> :
329 public MultiImplMap<SmallMapTy, BigMapTy, MaxSmallN, false>
332 typedef MultiImplMap<SmallMapTy, BigMapTy, MaxSmallN, false> ParentTy;
333 typedef typename ParentTy::Types Types;
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;
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
343 bool isPointerIntoBucketsArray(const void *Ptr) const {
345 return this->SmallMap.isPointerIntoBucketsArray(Ptr);
346 return this->BigMap.isPointerIntoBucketsArray(Ptr);
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 {
354 return this->SmallMap.getPointerIntoBucketsArray();
355 return this->BigMap.getPointerIntoBucketsArray();
358 value_type& FindAndConstruct(const key_type &Key) {
359 std::pair<iterator, bool> Res =
360 this->insert(std::make_pair(Key, mapped_type()));
365 template<class SmallMapTy, class BigMapTy, bool IsConst>
366 class MultiImplMapIterator {
369 typedef MultiImplMapTypes<SmallMapTy, BigMapTy> Types;
371 typedef typename Types::mapped_type mapped_type;
373 typedef typename conditional<IsConst,
374 const typename Types::value_type,
375 typename Types::value_type>::type value_type;
377 typedef typename conditional<IsConst,
378 typename SmallMapTy::const_iterator,
379 typename SmallMapTy::iterator>::type
382 typedef typename conditional<IsConst,
383 typename BigMapTy::const_iterator,
384 typename BigMapTy::iterator>::type
387 typedef typename conditional<IsConst, const void*, void*>::type void_ptr_ty;
389 typedef value_type *pointer;
390 typedef value_type &reference;
392 typedef MultiImplMapIterator<SmallMapTy, BigMapTy, IsConst> self;
394 typedef MultiImplMapIterator<SmallMapTy, BigMapTy, false> non_const_self;
395 typedef MultiImplMapIterator<SmallMapTy, BigMapTy, true> const_self;
397 friend class MultiImplMapIterator<SmallMapTy, BigMapTy, true>;
398 friend class MultiImplMapIterator<SmallMapTy, BigMapTy, false>;
402 template <typename OtherValTy>
403 static value_type* toValueTypePtr(OtherValTy& ValTyRef) {
404 return reinterpret_cast<value_type*>(
405 reinterpret_cast<void_ptr_ty>(&ValTyRef));
408 template <typename OtherValTy>
409 static value_type& toValueTypeRef(OtherValTy& ValTyRef) {
410 return *reinterpret_cast<value_type*>(
411 reinterpret_cast<void_ptr_ty>(&ValTyRef));
414 small_iterator SmallIt;
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) {}
426 bool operator==(const const_self& rhs) const {
427 if (UseSmall != rhs.UseSmall)
430 return SmallIt == rhs.SmallIt;
431 return BigIt == rhs.BigIt;
434 bool operator!=(const const_self& rhs) const {
435 if (UseSmall != rhs.UseSmall)
438 return SmallIt != rhs.SmallIt;
439 return BigIt != rhs.BigIt;
442 reference operator*() const {
443 return UseSmall ? toValueTypeRef(*SmallIt) : toValueTypeRef(*BigIt);;
446 pointer operator->() const {
447 return UseSmall ? toValueTypePtr(*SmallIt) : toValueTypePtr(*BigIt);
451 inline self& operator++() {
452 if (UseSmall) ++SmallIt;
457 self operator++(int) {
458 self tmp = *this; ++*this; return tmp;
462 template<class SmallMapTy, class BigMapTy>
463 struct MultiImplMapIteratorsFactory {
465 typedef MultiImplMapIterator<SmallMapTy, BigMapTy, false> iterator;
466 typedef MultiImplMapIterator<SmallMapTy, BigMapTy, true> const_iterator;
468 template<class MapImpl, class ItTy>
469 static iterator it(MapImpl& impl, ItTy it) {
472 template<class MapImpl, class ConstItTy>
473 static const_iterator const_it(const MapImpl& impl, ConstItTy it) {
474 return const_iterator(it);
476 template<class MapImpl>
477 static iterator begin(MapImpl& impl) {
478 return iterator(impl.begin());
480 template<class MapImpl>
481 static const_iterator begin(const MapImpl& impl) {
482 return const_iterator(impl.begin());
484 template<class MapImpl>
485 static iterator end(MapImpl& impl) {
486 return iterator(impl.end());
488 template<class MapImpl>
489 static const_iterator end(const MapImpl& impl) {
490 return const_iterator(impl.end());
494 template<typename KeyTy, typename MappedTy, unsigned MaxArraySize,
496 struct MultiImplMapIteratorsFactory<
497 FlatArrayMap<KeyTy, MappedTy, MaxArraySize>,
498 DenseMap<KeyTy, MappedTy, KeyInfoT> >
501 typedef FlatArrayMap<KeyTy, MappedTy, MaxArraySize> SmallMapTy;
502 typedef DenseMap<KeyTy, MappedTy, KeyInfoT> BigMapTy;
504 typedef DenseMapIterator<KeyTy, MappedTy, KeyInfoT, false>
506 typedef DenseMapIterator<KeyTy, MappedTy, KeyInfoT, true>
509 static iterator it(SmallMapTy& impl, typename SmallMapTy::iterator it) {
510 return iterator(&(*it), &(*impl.end()));
512 static const_iterator const_it(
513 const SmallMapTy& impl, typename SmallMapTy::const_iterator it) {
514 return const_iterator(&(*it), &(*impl.end()));
516 static iterator it(BigMapTy& impl, typename BigMapTy::iterator it) {
519 static const_iterator const_it(
520 const BigMapTy& impl, typename BigMapTy::const_iterator it) {
523 static iterator begin(SmallMapTy& impl) {
524 return it(impl, impl.begin());
526 static const_iterator begin(const SmallMapTy& impl) {
527 return it(impl, impl.begin());
529 static iterator begin(BigMapTy& impl) {
532 static const_iterator begin(const BigMapTy& impl) {
535 static iterator end(SmallMapTy& impl) {
536 return it(impl, impl.end());
538 static const_iterator end(const SmallMapTy& impl) {
539 return const_it(impl, impl.end());
541 static iterator end(BigMapTy& impl) {
544 static const_iterator end(const BigMapTy& impl) {
550 #endif /* MULTIIMPLEMENTATIONMAP_H_ */