diff options
| -rw-r--r-- | docs/ProgrammersManual.html | 81 | ||||
| -rw-r--r-- | include/llvm/ADT/FlatArrayMap.h | 323 | ||||
| -rw-r--r-- | include/llvm/ADT/MultiImplMap.h | 550 | ||||
| -rw-r--r-- | include/llvm/ADT/SmallMap.h | 37 | ||||
| -rw-r--r-- | unittests/ADT/SmallMapTest.cpp | 133 |
5 files changed, 1124 insertions, 0 deletions
diff --git a/docs/ProgrammersManual.html b/docs/ProgrammersManual.html index 854f90e28b..e00dd4a66d 100644 --- a/docs/ProgrammersManual.html +++ b/docs/ProgrammersManual.html @@ -95,6 +95,9 @@ option</a></li> <li><a href="#dss_stringmap">"llvm/ADT/StringMap.h"</a></li> <li><a href="#dss_indexedmap">"llvm/ADT/IndexedMap.h"</a></li> <li><a href="#dss_densemap">"llvm/ADT/DenseMap.h"</a></li> + <li><a href="#dss_multiimplmap">"llvm/ADT/MultiImplMap.h"</a></li> + <li><a href="#dss_flatarraymap">"llvm/ADT/FlatArrayMap.h"</a></li> + <li><a href="#dss_smallmap">"llvm/ADT/SmallMap.h"</a></li> <li><a href="#dss_valuemap">"llvm/ADT/ValueMap.h"</a></li> <li><a href="#dss_intervalmap">"llvm/ADT/IntervalMap.h"</a></li> <li><a href="#dss_map"><map></a></li> @@ -1812,6 +1815,84 @@ a <code>Config</code> parameter to the ValueMap template.</p> <!-- _______________________________________________________________________ --> <h4> + <a name="dss_multiimplmap">"llvm/ADT/MultiImplMap.h"</a> +</h4> + +<div> + +<p> +MultiImplMap is map that has two modes, one for small amount of elements and +one for big amount. User should set map implementation for both of them. +User also should set the maximum possible number of elements for small mode. +</p> + +<p> +If user want to use MultiImplMap instead of +<a href="#dss_densemap">DenseMap</a>, he should pass template parameter +DenseMapCompatible = true. Note, that in this case map implementations +should present additional DenseMap specific methods (see below): +<code>isPointerIntoBucketsArray</code>, <code>getPointerIntoBucketsArray</code> +and <code>FindAndConstruct</code>. +</p> + +<p> +Initially MultiImplMap uses small mode and small map implementation. It +triggered to the big mode when the number of contained elements exceeds +maximum possible elements for small mode. +</p> + +</div> + +<!-- _______________________________________________________________________ --> +<h4> + <a name="dss_flatarraymap">"llvm/ADT/FlatArrayMap.h"</a> +</h4> + +<div> + +<p> +FlatArrayMap optimized for small amount of elements. It uses flat array +implementation inside: +</p> +<pre>[ key0, value0, key1, value1, ... keyN, valueN ]</pre> + + +<p> +User should pass key type, mapped type (type of value), and maximum +number of elements. +</p> + +<p> +After maximum number of elements is reached, map declines any further +attempts to insert new elements ("insert" method returns <end(), +false>). +</p> + +<p> +FlatArrayMap has interface that is compatible with +<a href="#dss_densemap">DenseMap</a>, so user can replace it with DenseMap +without any code changing and vice versa. +</p> + +</div> + +<!-- _______________________________________________________________________ --> +<h4> + <a name="dss_smallmap">"llvm/ADT/SmallMap.h"</a> +</h4> + +<div> + +<p> +SmallMap is wrapper around <a href="#dss_multiimplmap">MultiImplMap</a>. +It uses <a href="#dss_flatarraymap">FlatArrayMap</a> for small mode, and +<a href="#dss_densemap">DenseMap</a> for big mode. +</p> + +</div> + +<!-- _______________________________________________________________________ --> +<h4> <a name="dss_intervalmap">"llvm/ADT/IntervalMap.h"</a> </h4> diff --git a/include/llvm/ADT/FlatArrayMap.h b/include/llvm/ADT/FlatArrayMap.h new file mode 100644 index 0000000000..f794c9c22f --- /dev/null +++ b/include/llvm/ADT/FlatArrayMap.h @@ -0,0 +1,323 @@ +//===- llvm/ADT/FlatArrayMap.h - 'Normally small' pointer set ----*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the FlatArrayMap class. +// See FlatArrayMap doxygen comments for more details. +// +//===----------------------------------------------------------------------===// + +#ifndef FLATARRAYMAP_H_ +#define FLATARRAYMAP_H_ + +#include <algorithm> +#include <utility> +#include "llvm/Support/type_traits.h" + +namespace llvm { + + template <typename KeyTy, typename MappedTy> + struct FlatArrayMapTypes { + typedef KeyTy key_type; + typedef MappedTy mapped_type; + typedef typename std::pair<key_type, mapped_type> value_type; + }; + + template<typename KeyTy, typename MappedTy, bool IsConst = false> + class FlatArrayMapIterator; + + //===--------------------------------------------------------------------===// + /// FlatArrayMap presents map container interface. + /// It uses flat array implementation inside: + /// [ <key0, value0>, <key1, value1>, ... <keyN, valueN> ] + /// It works fast for small amount of elements. + /// User should pass key type, mapped type (type of value), and maximum + /// number of elements. + /// After maximum number of elements is reached, map declines any farther + /// attempts to insert new elements ("insert" method returns <end(),false>). + /// + template <typename KeyTy, typename MappedTy, unsigned MaxArraySize> + class FlatArrayMap { + public: + typedef FlatArrayMapTypes<KeyTy, MappedTy> Types; + + typedef typename Types::key_type key_type; + typedef typename Types::mapped_type mapped_type; + typedef typename Types::value_type value_type; + + typedef FlatArrayMapIterator<KeyTy, MappedTy> iterator; + typedef FlatArrayMapIterator<KeyTy, MappedTy, true> const_iterator; + + typedef FlatArrayMap<KeyTy, MappedTy, MaxArraySize> self; + + private: + + enum { BadIndex = -1U }; + + key_type EmptyKey; + mapped_type EmptyValue; + + value_type Array[MaxArraySize + 1]; + unsigned NumElements; + + unsigned findFor(const KeyTy Ptr) const { + // Linear search for the item. + for (const value_type *APtr = Array, *E = Array + NumElements; + APtr != E; ++APtr) { + if (APtr->first == Ptr) { + return APtr - Array; + } + } + return BadIndex; + } + + bool lookupFor(const KeyTy &Ptr, const value_type*& Found) const { + unsigned FoundIdx = findFor(Ptr); + if (FoundIdx != BadIndex) { + Found = Array + FoundIdx; + return true; + } + return false; + } + + bool lookupFor(const KeyTy &Ptr, value_type*& Found) { + unsigned FoundIdx = findFor(Ptr); + if (FoundIdx != BadIndex) { + Found = Array + FoundIdx; + return true; + } + return false; + } + + + void copyFrom(const self &RHS) { + memcpy(Array, RHS.Array, sizeof(value_type) * (MaxArraySize + 1)); + NumElements = RHS.NumElements; + } + + void init () { + memset(Array + MaxArraySize, 0, sizeof(value_type)); + NumElements = 0; + } + + bool insertInternal(KeyTy Ptr, MappedTy Val, value_type*& Item) { + // Check to see if it is already in the set. + value_type *Found; + if (lookupFor(Ptr, Found)) { + Item = Found; + return false; + } + if (NumElements < MaxArraySize) { + unsigned Idx = NumElements++; + Array[Idx] = std::make_pair(Ptr, Val); + Item = Array + Idx; + return true; + } + Item = Array + MaxArraySize; // return end() + return false; + } + + public: + + // Constructors + + FlatArrayMap() : EmptyKey(), EmptyValue() { + init(); + } + + FlatArrayMap(const self &that) : + EmptyKey(), EmptyValue() { + copyFrom(that); + } + + template<typename It> + FlatArrayMap(It I, It E) : + EmptyKey(), EmptyValue() { + init(); + insert(I, E); + } + + // Size + + unsigned size() const { + return NumElements; + } + + bool empty() const { + return !NumElements; + } + + // Iterators + + iterator begin() { + return iterator(Array); + } + const_iterator begin() const { + return const_iterator(Array); + } + + iterator end() { + return iterator(Array + MaxArraySize); + } + const_iterator end() const { + return const_iterator(Array + MaxArraySize); + } + + // Modifiers + + void clear() { + for (unsigned i = 0; i < NumElements; ++i) { + Array[i].first = EmptyKey; + Array[i].second = EmptyValue; + } + NumElements = 0; + } + + // The map container is extended by inserting a single new element. + // The behavior is the same as the std::map::insert, except the + // case when maximum number of elements is reached; + // in this case map declines any farther attempts + // to insert new elements ("insert" method returns <end(),false>). + std::pair<iterator, bool> insert(const value_type& KV) { + value_type* Item; + bool Res = insertInternal(KV.first, KV.second, Item); + return std::make_pair(iterator(Item), Res); + } + + template <typename IterT> + void insert(IterT I, IterT E) { + for (; I != E; ++I) + insert(*I); + } + + void erase(key_type K) { + unsigned Found = findFor(K); + if (Found != BadIndex) { + value_type *APtr = Array + Found; + value_type *E = Array + NumElements; + *APtr = E[-1]; + E[-1].first.~key_type(); + E[-1].second.~mapped_type(); + --NumElements; + } + } + + void erase(iterator i) { + erase(i->first); + } + + void swap(self& RHS) { + std::swap_ranges(Array, Array+MaxArraySize, RHS.Array); + std::swap(this->NumElements, RHS.NumElements); + } + + // Search operations + + iterator find(const key_type& K) { + value_type *Found; + if (lookupFor(K, Found)) + return iterator(Found); + return end(); + } + + const_iterator find(const key_type& K) const { + const value_type *Found; + if (lookupFor(K, Found)) + return const_iterator(Found); + return end(); + } + + bool count(const key_type& K) const { + return find(K) != end(); + } + + mapped_type &operator[](const key_type &Key) { + std::pair<iterator, bool> res = insert(Key, mapped_type()); + return res.first->second; + } + + // Other operations + + self& operator=(const self& other) { + clear(); + copyFrom(other); + return *this; + } + + /// isPointerIntoBucketsArray - Return true if the specified pointer points + /// somewhere into the map's array of buckets (i.e. either to a key or + /// value). + bool isPointerIntoBucketsArray(const void *Ptr) const { + return Ptr >= Array && Ptr < Array + NumElements; + } + + /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets + /// array. + const void *getPointerIntoBucketsArray() const { return Array; } + }; + + template<typename KeyTy, typename MappedTy, bool IsConst> + class FlatArrayMapIterator { + + typedef FlatArrayMapTypes<KeyTy, MappedTy> Types; + + typedef typename conditional<IsConst, + const typename Types::value_type, + typename Types::value_type>::type value_type; + typedef value_type *pointer; + typedef value_type &reference; + + typedef FlatArrayMapIterator<KeyTy, MappedTy, IsConst> self; + typedef FlatArrayMapIterator<KeyTy, MappedTy, false> non_const_self; + typedef FlatArrayMapIterator<KeyTy, MappedTy, true> const_self; + + friend class FlatArrayMapIterator<KeyTy, MappedTy, false>; + friend class FlatArrayMapIterator<KeyTy, MappedTy, true>; + + pointer TheBucket; + + public: + + FlatArrayMapIterator() : TheBucket(0) {} + + explicit FlatArrayMapIterator(pointer BP) : + TheBucket(BP) {} + + // If IsConst is true this is a converting constructor from iterator to + // const_iterator and the default copy constructor is used. + // Otherwise this is a copy constructor for iterator. + FlatArrayMapIterator(const non_const_self& I) + : TheBucket(I.TheBucket) {} + + bool operator==(const const_self &RHS) const { + return TheBucket->first == RHS.TheBucket->first; + } + bool operator!=(const const_self &RHS) const { + return TheBucket->first != RHS.TheBucket->first; + } + + reference operator*() const { + return *TheBucket; + } + + pointer operator->() const { + return TheBucket; + } + + inline self& operator++() { // Preincrement + ++TheBucket; + return *this; + } + + self operator++(int) { // Postincrement + FlatArrayMapIterator tmp = *this; ++*this; return tmp; + } + }; +} + +#endif /* FLATARRAYMAP_H_ */ diff --git a/include/llvm/ADT/MultiImplMap.h b/include/llvm/ADT/MultiImplMap.h new file mode 100644 index 0000000000..da453aa3c4 --- /dev/null +++ b/include/llvm/ADT/MultiImplMap.h @@ -0,0 +1,550 @@ +//===- llvm/ADT/MultiImplMap.h - 'Normally small' pointer set ----*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the MultiImplMap class. +// MultiImplMap presents map container interface. +// It has two modes, one for small amount of elements and one for big amount. +// User should set map implementation for both of them. User also should +// set the maximum possible number of elements for small mode. +// If user want to use MultiImplMap instead of DenseMap, he should pass +// DenseMapCompatible = true. Note that in this case map implementations should +// present additional DenseMap specific methods (see below). +// Initially MultiImplMap uses small mode and small map implementation. +// It triggered to the big mode when number of contained elements exceeds +// maximum possible elements for small mode. +// +// Types that should be defined in nested map class: +// +// key_type; +// mapped_type; +// value_type; // std::pair<key_type, mapped_type> +// // or std::pair<const key_type, mapped_type> +// iterator; +// const_iterator; +// +// Map implementation should provide the next interface: +// +// // Constructors +// (default constructor) +// (copy constructor) +// +// // Size +// unsigned size() const; +// bool empty() const; +// +// // Iterators +// iterator begin(); +// const_iterator begin(); +// iterator end(); +// const_iterator end(); +// +// // Modifiers +// void clear(); +// std::pair<iterator, bool> insert(const value_type& KV); +// template <typename IterT> +// void insert(IterT I, IterT E); +// void erase(key_type K); +// void erase(iterator i); +// void swap(MultiImplMap& rhs); +// +// // Search operations +// iterator find(const key_type& K); +// const_iterator find(const key_type& K) const; +// bool count(const key_type& K) const; +// mapped_type &operator[](const key_type &Key); +// +// // Other operations +// self& operator=(const self& other); +// +// // If DenseMapCompatible == true, you also should present next methods. +// // See DenseMap comments for more details about its behavior. +// bool isPointerIntoBucketsArray(const void *Ptr) const; +// const void *getPointerIntoBucketsArray() const; +// value_type& FindAndConstruct(const key_type &Key); +// +// The list of methods that should be implemented in nested map iterator class: +// +// (conversion constructor from non-constant iterator) +// +// bool operator==(const const_iterator& rhs) const; +// bool operator!=(const const_iterator& rhs) const; +// reference operator*() const; +// pointer operator->() const; +// inline self& operator++(); +// +// +//===----------------------------------------------------------------------===// + +#ifndef MULTIIMPLEMENTATIONMAP_H_ +#define MULTIIMPLEMENTATIONMAP_H_ + + +#include <algorithm> +#include <utility> +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/FlatArrayMap.h" +#include "llvm/Support/type_traits.h" + +namespace llvm { + + template<class SmallMapTy, class BigMapTy, bool IsConst = false> + class MultiImplMapIterator; + + template<class SmallMapTy, class BigMapTy> + struct MultiImplMapIteratorsFactory; + + template<class SmallMapTy, class BigMapTy> + struct MultiImplMapTypes { + typedef typename SmallMapTy::key_type key_type; + typedef typename SmallMapTy::mapped_type mapped_type; + typedef typename std::pair<key_type, mapped_type> value_type; + }; + + //===--------------------------------------------------------------------===// + /// MultiImplMap is map that has two modes, one for small amount of + /// elements and one for big amount. + /// User should set map implementation for both of them. User also should + /// set the maximum possible number of elements for small mode. + /// If user want to use MultiImplMap instead of DenseMap, he should pass + /// DenseMapCompatible = true. + /// Initially MultiImplMap uses small mode and small map implementation. + /// It triggered to the big mode when number of contained elements exceeds + /// maximum possible elements for small mode. + template<class SmallMapTy, class BigMapTy, unsigned MaxSmallN, + bool DenseMapCompatible = false, + class ItFactory = + MultiImplMapIteratorsFactory<SmallMapTy, BigMapTy> > + class MultiImplMap { + + protected: + SmallMapTy SmallMap; + BigMapTy BigMap; + bool UseSmall; + enum { MaxSmallSize = MaxSmallN }; + + public: + typedef MultiImplMapTypes<SmallMapTy, BigMapTy> Types; + + typedef typename Types::key_type key_type; + typedef typename Types::mapped_type mapped_type; + typedef typename Types::value_type value_type; + + typedef typename ItFactory::iterator iterator; + typedef typename ItFactory::const_iterator const_iterator; + + typedef std::pair<iterator, bool> ins_res; + + typedef typename std::pair<typename SmallMapTy::iterator, bool> + small_ins_res; + + typedef typename std::pair<typename BigMapTy::iterator, bool> + big_ins_res; + + typedef MultiImplMap<SmallMapTy, BigMapTy, MaxSmallN> self; + + MultiImplMap() : UseSmall(true) {} + + MultiImplMap(const self& other) { + if (other.UseSmall) { + SmallMap = other.SmallMap; + UseSmall = true; + } else { + if (other.size() <= MaxSmallN) { + SmallMap.insert(other.BigMap.begin(), other.BigMap.end()); + UseSmall = true; + } else { + BigMap = other.BigMap; + UseSmall = false; + } + } + } + + // Size + + unsigned size() const { + if (UseSmall) + return SmallMap.size(); + return BigMap.size(); + } + + bool empty() const { + if (UseSmall) + return SmallMap.empty(); + return BigMap.empty(); + } + + // Iterators + + iterator begin() { + if (UseSmall) + return ItFactory::begin(SmallMap); + return ItFactory::begin(BigMap); + } + const_iterator begin() const { + if (UseSmall) + return ItFactory::begin(SmallMap); + return ItFactory::begin(BigMap); + } + + iterator end() { + if (UseSmall) + return ItFactory::end(SmallMap); + return ItFactory::end(BigMap); + } + const_iterator end() const { + if (UseSmall) + return ItFactory::end(SmallMap); + return ItFactory::end(BigMap); + } + + // Modifiers + + void clear() { + if (UseSmall) + SmallMap.clear(); + else + BigMap.clear(); + } + + std::pair<iterator, bool> insert(const value_type& KV) { + if (UseSmall) { + if (SmallMap.size() < MaxSmallSize) { + small_ins_res Res = SmallMap.insert(KV); + return std::make_pair(ItFactory::it(SmallMap, Res.first), Res.second); + } + + // Move all to big map. + BigMap.insert(SmallMap.begin(), SmallMap.end()); + SmallMap.clear(); + + UseSmall = false; + } + big_ins_res Res = BigMap.insert(KV); + return std::make_pair(ItFactory::it(BigMap, Res.first), Res.second); + } + + template <typename OtherValTy> + std::pair<iterator, bool> insert(const OtherValTy& OtherKV) { + const value_type* KV = reinterpret_cast<const value_type*>( + reinterpret_cast<const void*>(OtherKV)); + return insert(*KV); + } + + template <typename IterT> + void insert(IterT I, IterT E) { + for (; I != E; ++I) + insert(*I); + } + + void erase(key_type K) { + if (UseSmall) + SmallMap.erase(K); + else + BigMap.erase(K); + } + + void erase(iterator i) { + erase(i->first); + } + + void swap(MultiImplMap& rhs) { + SmallMap.swap(rhs.SmallMap); + BigMap.swap(rhs.BigMap); + std::swap(UseSmall, rhs.UseSmall); + } + + // Search operations + + iterator find(const key_type& K) { + if (UseSmall) + return ItFactory::it(SmallMap, SmallMap.find(K)); + return ItFactory::it(BigMap, BigMap.find(K)); + } + + const_iterator find(const key_type& K) const { + if (UseSmall) + return ItFactory::const_it(SmallMap, SmallMap.find(K)); + return ItFactory::const_it(BigMap, BigMap.find(K)); + } + + bool count(const key_type& K) const { + return find(K) != end(); + } + + mapped_type &operator[](const key_type &Key) { + ins_res res = insert(std::make_pair(Key, mapped_type())); + return res.first->second; + } + + // Other operations + + self& operator=(const self& other) { + if (other.isSmall()) { + SmallMap = other.SmallMap; + if (!UseSmall) { + BigMap.clear(); + UseSmall = true; + } + return *this; + } + if (UseSmall) { + SmallMap.clear(); + UseSmall = false; + } + BigMap = other.BigMap; + return *this; + } + + // Utilities + + bool isSmall()const { + return UseSmall; + } + + SmallMapTy& getSmallMap() { + return SmallMap; + } + + const SmallMapTy& getSmallMap() const { + return SmallMap; + } + + BigMapTy& getBigMap() { + return BigMap; + } + + const BigMapTy& getBigMap() const { + return BigMap; + } + }; + + template<class SmallMapTy, class BigMapTy, unsigned MaxSmallN> + class MultiImplMap<SmallMapTy, BigMapTy, MaxSmallN, true> : + public MultiImplMap<SmallMapTy, BigMapTy, MaxSmallN, false> + { + public: + typedef MultiImplMap<SmallMapTy, BigMapTy, MaxSmallN, false> ParentTy; + typedef typename ParentTy::Types Types; + + typedef typename Types::key_type key_type; + typedef typename Types::mapped_type mapped_type; + typedef typename Types::value_type value_type; + typedef typename ParentTy::iterator iterator; + + /// isPointerIntoBucketsArray - Return true if the specified pointer points + /// somewhere into the DenseMap's array of buckets (i.e. either to a key or + /// value). + bool isPointerIntoBucketsArray(const void *Ptr) const { + if (this->UseSmall) + return this->SmallMap.isPointerIntoBucketsArray(Ptr); + return this->BigMap.isPointerIntoBucketsArray(Ptr); + } + + /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets + /// array. In conjunction with the previous method, this can be used to + /// determine whether an insertion caused the map to reallocate data. + const void *getPointerIntoBucketsArray() const { + if (this->UseSmall) + return this->SmallMap.getPointerIntoBucketsArray(); + return this->BigMap.getPointerIntoBucketsArray(); + } + + value_type& FindAndConstruct(const key_type &Key) { + std::pair<iterator, bool> Res = + this->insert(std::make_pair(Key, mapped_type())); + return *Res.first; + } + }; + + template<class SmallMapTy, class BigMapTy, bool IsConst> + class MultiImplMapIterator { + public: + + typedef MultiImplMapTypes<SmallMapTy, BigMapTy> Types; + + typedef typename Types::mapped_type mapped_type; + + typedef typename conditional<IsConst, + const typename Types::value_type, + typename Types::value_type>::type value_type; + + typedef typename conditional<IsConst, + typename SmallMapTy::const_iterator, + typename SmallMapTy::iterator>::type + small_iterator; + + typedef typename conditional<IsConst, + typename BigMapTy::const_iterator, + typename BigMapTy::iterator>::type + big_iterator; + + typedef typename conditional<IsConst, const void*, void*>::type void_ptr_ty; + + typedef value_type *pointer; + typedef value_type &reference; + + typedef MultiImplMapIterator<SmallMapTy, BigMapTy, IsConst> self; + + typedef MultiImplMapIterator<SmallMapTy, BigMapTy, false> non_const_self; + typedef MultiImplMapIterator<SmallMapTy, BigMapTy, true> const_self; + + friend class MultiImplMapIterator<SmallMapTy, BigMapTy, true>; + friend class MultiImplMapIterator<SmallMapTy, BigMapTy, false>; + + protected: + + template <typename OtherValTy> + static value_type* toValueTypePtr(OtherValTy& ValTyRef) { + return reinterpret_cast<value_type*>( + reinterpret_cast<void_ptr_ty>(&ValTyRef)); + } + + template <typename OtherValTy> + static value_type& toValueTypeRef(OtherValTy& ValTyRef) { + return *reinterpret_cast<value_type*>( + reinterpret_cast<void_ptr_ty>(&ValTyRef)); + } + + small_iterator SmallIt; + big_iterator BigIt; + bool UseSmall; + + public: + + MultiImplMapIterator() : UseSmall(true) {} + MultiImplMapIterator(small_iterator It) : SmallIt(It), UseSmall(true) {} + MultiImplMapIterator(big_iterator It) : BigIt(It), UseSmall(false) {} + MultiImplMapIterator(const non_const_self& src) : + SmallIt(src.SmallIt), BigIt(src.BigIt), UseSmall(src.UseSmall) {} + + bool operator==(const const_self& rhs) const { + if (UseSmall != rhs.UseSmall) + return false; + if (UseSmall) + return SmallIt == rhs.SmallIt; + return BigIt == rhs.BigIt; + } + + bool operator!=(const const_self& rhs) const { + if (UseSmall != rhs.UseSmall) + return true; + if (UseSmall) + return SmallIt != rhs.SmallIt; + return BigIt != rhs.BigIt; + } + + reference operator*() const { + return UseSmall ? toValueTypeRef(*SmallIt) : toValueTypeRef(*BigIt);; + } + + pointer operator->() const { + return UseSmall ? toValueTypePtr(*SmallIt) : toValueTypePtr(*BigIt); + } + + // Preincrement + inline self& operator++() { + if (UseSmall) ++SmallIt; + return *this; + } + + // Postincrement + self operator++(int) { + self tmp = *this; ++*this; return tmp; + } + }; + + template<class SmallMapTy, class BigMapTy> + struct MultiImplMapIteratorsFactory { + + typedef MultiImplMapIterator<SmallMapTy, BigMapTy, false> iterator; + typedef MultiImplMapIterator<SmallMapTy, BigMapTy, true> const_iterator; + + template<class MapImpl, class ItTy> + static iterator it(MapImpl& impl, ItTy it) { + return iterator(it); + } + template<class MapImpl, class ConstItTy> + static const_iterator const_it(const MapImpl& impl, ConstItTy it) { + return const_iterator(it); + } + template<class MapImpl> + static iterator begin(MapImpl& impl) { + return iterator(impl.begin()); + } + template<class MapImpl> + static const_iterator begin(const MapImpl& impl) { + return const_iterator(impl.begin()); + } + template<class MapImpl> + static iterator end(MapImpl& impl) { + return iterator(impl.end()); + } + template<class MapImpl> + static const_iterator end(const MapImpl& impl) { + return const_iterator(impl.end()); + } + }; + + template<typename KeyTy, typename MappedTy, unsigned MaxArraySize, + typename KeyInfoT> + struct MultiImplMapIteratorsFactory< + FlatArrayMap<KeyTy, MappedTy, MaxArraySize>, + DenseMap<KeyTy, MappedTy, KeyInfoT> > + { + + typedef FlatArrayMap<KeyTy, MappedTy, MaxArraySize> SmallMapTy; + typedef DenseMap<KeyTy, MappedTy, KeyInfoT> BigMapTy; + + typedef DenseMapIterator<KeyTy, MappedTy, KeyInfoT, false> + iterator; + typedef DenseMapIterator<KeyTy, MappedTy, KeyInfoT, true> + const_iterator; + + static iterator it(SmallMapTy& impl, typename SmallMapTy::iterator it) { + return iterator(&(*it), &(*impl.end())); + } + static const_iterator const_it( + const SmallMapTy& impl, typename SmallMapTy::const_iterator it) { + return const_iterator(&(*it), &(*impl.end())); + } + static iterator it(BigMapTy& impl, typename BigMapTy::iterator it) { + return it; + } + static const_iterator const_it( + const BigMapTy& impl, typename BigMapTy::const_iterator it) { + return it; + } + static iterator begin(SmallMapTy& impl) { + return it(impl, impl.begin()); + } + static const_iterator begin(const SmallMapTy& impl) { + return it(impl, impl.begin()); + } + static iterator begin(BigMapTy& impl) { + return impl.begin(); + } + static const_iterator begin(const BigMapTy& impl) { + return impl.begin(); + } + static iterator end(SmallMapTy& impl) { + return it(impl, impl.end()); + } + static const_iterator end(const SmallMapTy& impl) { + return const_it(impl, impl.end()); + } + static iterator end(BigMapTy& impl) { + return impl.end(); + } + static const_iterator end(const BigMapTy& impl) { + return impl.end(); + } + }; +} + +#endif /* MULTIIMPLEMENTATIONMAP_H_ */ diff --git a/include/llvm/ADT/SmallMap.h b/include/llvm/ADT/SmallMap.h new file mode 100644 index 0000000000..42d27ce77e --- /dev/null +++ b/include/llvm/ADT/SmallMap.h @@ -0,0 +1,37 @@ +//===- llvm/ADT/SmallMap.h - 'Normally small' pointer set -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the SmallMap class. +// SmallMap is DenseMap compatible MultiImplMap. +// It uses FlatArrayMap for small mode, and DenseMap for big mode. +// See MultiMapImpl comments for more details on the algorithm is used. +// +//===----------------------------------------------------------------------===// + +#ifndef SMALLPTRMAP_H_ +#define SMALLPTRMAP_H_ + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/FlatArrayMap.h" +#include "llvm/ADT/MultiImplMap.h" + +namespace llvm { + + //===--------------------------------------------------------------------===// + /// SmallMap is wrapper around MultiImplMap. It uses FlatArrayMap for + /// small mode, and DenseMap for big mode. + template <typename KeyTy, typename MappedTy, unsigned N = 16> + class SmallMap : public MultiImplMap< + FlatArrayMap<KeyTy, MappedTy, N>, + DenseMap<KeyTy, MappedTy>, + N, true> { + }; +} + +#endif /* SMALLPTRMAP_H_ */ diff --git a/unittests/ADT/SmallMapTest.cpp b/unittests/ADT/SmallMapTest.cpp new file mode 100644 index 0000000000..91319dede2 --- /dev/null +++ b/unittests/ADT/SmallMapTest.cpp @@ -0,0 +1,133 @@ +//===- llvm/unittest/ADT/SmallMapTest.cpp ------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// SmallMap unit tests. +// +//===----------------------------------------------------------------------===// + +#include "gtest/gtest.h" +#include "llvm/ADT/SmallMap.h" + +using namespace llvm; + +// SmallMap test. +TEST(SmallMapTest, GeneralTest) { + + int buf[10]; + + SmallMap<int *, int, 3> a; + SmallMap<int *, int, 3> b; + SmallMap<int *, int, 3>::iterator found; + std::pair<SmallMap<int *, int, 3>::iterator, bool> insRes; + SmallMap<int *, int, 3>::const_iterator foundc; + + a.insert(std::make_pair(&buf[0], 0)); + insRes = a.insert(std::make_pair(&buf[1], 1)); + EXPECT_TRUE(insRes.second); + + // Check insertion, looking up, and data editing in small mode. + insRes = a.insert(std::make_pair(&buf[1], 6)); + EXPECT_FALSE(insRes.second); + EXPECT_EQ(insRes.first->second, 1); + insRes.first->second = 5; + found = a.find(&buf[1]); + EXPECT_NE(found, a.end()); + EXPECT_EQ(found->second, 5); + a[&buf[1]] = 10; + EXPECT_EQ(found->second, 10); + // Check "not found" case. + found = a.find(&buf[8]); + EXPECT_EQ(found, a.end()); + + // Check increment for small mode. + found = a.begin(); + ++found; + EXPECT_EQ(found->second, 10); + + b.insert(std::make_pair(&buf[2], 2)); + + std::swap(a, b); + a.swap(b); + std::swap(a, b); + + EXPECT_EQ(1U, a.size()); + EXPECT_EQ(2U, b.size()); + EXPECT_TRUE(a.count(&buf[2])); + EXPECT_TRUE(b.count(&buf[0])); + EXPECT_TRUE(b.count(&buf[1])); + + insRes = b.insert(std::make_pair(&buf[3], 3)); + EXPECT_TRUE(insRes.second); + + // Check insertion, looking up, and data editing in big mode. + insRes = b.insert(std::make_pair(&buf[3], 6)); + EXPECT_FALSE(insRes.second); + EXPECT_EQ(insRes.first->second, 3); + insRes.first->second = 7; + found = b.find(&buf[3]); + EXPECT_EQ(found->second, 7); + b[&buf[3]] = 14; + EXPECT_EQ(found->second, 14); + // Check constant looking up. + foundc = b.find(&buf[3]); + EXPECT_EQ(foundc->first, &buf[3]); + EXPECT_EQ(foundc->second, 14); + // Check not found case. + found = b.find(&buf[8]); + EXPECT_EQ(found, b.end()); + + // Check increment for big mode. + found = b.find(&buf[1]); + ++found; + EXPECT_EQ(found->second, 14); + + std::swap(a, b); + a.swap(b); + std::swap(a, b); + + EXPECT_EQ(3U, a.size()); + EXPECT_EQ(1U, b.size()); + EXPECT_TRUE(a.count(&buf[0])); + EXPECT_TRUE(a.count(&buf[1])); + EXPECT_TRUE(a.count(&buf[3])); + EXPECT_TRUE(b.count(&buf[2])); + EXPECT_EQ(b.find(&buf[2])->second, 2); + + std::swap(a, b); + a.swap(b); + std::swap(a, b); + + EXPECT_EQ(1U, a.size()); + EXPECT_EQ(3U, b.size()); + EXPECT_TRUE(a.count(&buf[2])); + EXPECT_TRUE(b.count(&buf[0])); + EXPECT_TRUE(b.count(&buf[1])); + EXPECT_TRUE(b.count(&buf[3])); + + a.insert(std::make_pair(&buf[4], 4)); + a.insert(std::make_pair(&buf[5], 5)); + a.insert(std::make_pair(&buf[6], 6)); + + std::swap(b, a); + + EXPECT_EQ(3U, a.size()); + EXPECT_EQ(4U, b.size()); + EXPECT_TRUE(b.count(&buf[2])); + EXPECT_TRUE(b.count(&buf[4])); + EXPECT_TRUE(b.count(&buf[5])); + EXPECT_TRUE(b.count(&buf[6])); + EXPECT_TRUE(a.count(&buf[0])); + EXPECT_TRUE(a.count(&buf[1])); + EXPECT_TRUE(a.count(&buf[3])); + + // Check findAndConstruct + SmallMap<int *, int, 3>::value_type Buf7; + Buf7 = a.FindAndConstruct(&buf[7]); + EXPECT_EQ(Buf7.second, 0); +} |