From 76271a3366731d4c372fdebcd8d3437e6e09a61b Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Wed, 25 Apr 2012 17:09:38 +0000 Subject: [PATCH] First implementation of: - FlatArrayMap. Very simple map container that uses flat array inside. - MultiImplMap. Map container interface, that has two modes, one for small amount of elements and one for big amount. - SmallMap. SmallMap is DenseMap compatible MultiImplMap. It uses FlatArrayMap for small mode, and DenseMap for big mode. Also added unittests for new classes and update for ProgrammersManual. For more details about new classes see ProgrammersManual and comments in sourcecode. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155557 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/ProgrammersManual.html | 81 +++++ include/llvm/ADT/FlatArrayMap.h | 323 +++++++++++++++++++ include/llvm/ADT/MultiImplMap.h | 550 ++++++++++++++++++++++++++++++++ include/llvm/ADT/SmallMap.h | 37 +++ unittests/ADT/SmallMapTest.cpp | 133 ++++++++ 5 files changed, 1124 insertions(+) create mode 100644 include/llvm/ADT/FlatArrayMap.h create mode 100644 include/llvm/ADT/MultiImplMap.h create mode 100644 include/llvm/ADT/SmallMap.h create mode 100644 unittests/ADT/SmallMapTest.cpp diff --git a/docs/ProgrammersManual.html b/docs/ProgrammersManual.html index 854f90e28b3..f81d7130a31 100644 --- a/docs/ProgrammersManual.html +++ b/docs/ProgrammersManual.html @@ -95,6 +95,9 @@ option
  • "llvm/ADT/StringMap.h"
  • "llvm/ADT/IndexedMap.h"
  • "llvm/ADT/DenseMap.h"
    • +
  • "llvm/ADT/MultiImplMap.h"
    • +
  • "llvm/ADT/FlatArrayMap.h"
    • +
  • "llvm/ADT/SmallMap.h"
  • "llvm/ADT/ValueMap.h"
  • "llvm/ADT/IntervalMap.h"
  • <map>
    • @@ -1810,6 +1813,84 @@ a Config parameter to the ValueMap template.

    + +

    + "llvm/ADT/MultiImplMap.h" +

    + +
    + +

    +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 template parameter +DenseMapCompatible = true. Note, that in this case map implementations +should present additional DenseMap specific methods (see below): +isPointerIntoBucketsArray, getPointerIntoBucketsArray +and FindAndConstruct. +

    + +

    +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. +

    + +
    + + +

    + "llvm/ADT/FlatArrayMap.h" +

    + +
    + +

    +FlatArrayMap optimized for small amount of elements. It uses flat array +implementation inside: +

    +
    [ key0, value0, key1, value1, ... keyN, valueN ]
    + + +

    +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 further +attempts to insert new elements ("insert" method returns <end(), +false>). +

    + +

    +FlatArrayMap has interface that is compatible with +DenseMap, so user can replace it with DenseMap +without any code changing and vice versa. +

    + +
    + + +

    + "llvm/ADT/SmallMap.h" +

    + +
    + +

    +SmallMap is wrapper around MultiImplMap. +It uses FlatArrayMap for small mode, and +DenseMap for big mode. +

    + +
    +

    "llvm/ADT/IntervalMap.h" diff --git a/include/llvm/ADT/FlatArrayMap.h b/include/llvm/ADT/FlatArrayMap.h new file mode 100644 index 00000000000..6f920e48bc6 --- /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 +#include +#include "llvm/Support/type_traits.h" + +namespace llvm { + + template + struct FlatArrayMapTypes { + typedef KeyTy key_type; + typedef MappedTy mapped_type; + typedef typename std::pair value_type; + }; + + template + class FlatArrayMapIterator; + + //===--------------------------------------------------------------------===// + /// FlatArrayMap presents map container interface. + /// It uses flat array implementation inside: + /// [ , , ... ] + /// 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 ). + /// + template + class FlatArrayMap { + public: + typedef FlatArrayMapTypes Types; + + typedef typename Types::key_type key_type; + typedef typename Types::mapped_type mapped_type; + typedef typename Types::value_type value_type; + + typedef FlatArrayMapIterator iterator; + typedef FlatArrayMapIterator const_iterator; + + typedef FlatArrayMap self; + + private: + + enum { BadIndex = ~0UL }; + + 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 + 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 ). + std::pair insert(const value_type& KV) { + value_type* Item; + bool Res = insertInternal(KV.first, KV.second, Item); + return std::make_pair(iterator(Item), Res); + } + + template + 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 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 + class FlatArrayMapIterator { + + typedef FlatArrayMapTypes Types; + + typedef typename conditional::type value_type; + typedef value_type *pointer; + typedef value_type &reference; + + typedef FlatArrayMapIterator self; + typedef FlatArrayMapIterator non_const_self; + typedef FlatArrayMapIterator const_self; + + friend class FlatArrayMapIterator; + friend class FlatArrayMapIterator; + + 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 00000000000..d585de68110 --- /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 +// // or std::pair +// 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 insert(const value_type& KV); +// template +// 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 +#include +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/FlatArrayMap.h" +#include "llvm/Support/type_traits.h" + +namespace llvm { + + template + class MultiImplMapIterator; + + template + struct MultiImplMapIteratorsFactory; + + template + struct MultiImplMapTypes { + typedef typename SmallMapTy::key_type key_type; + typedef typename SmallMapTy::mapped_type mapped_type; + typedef typename std::pair 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 MultiImplMap { + + protected: + SmallMapTy SmallMap; + BigMapTy BigMap; + bool UseSmall; + enum { MaxSmallSize = MaxSmallN }; + + public: + typedef MultiImplMapTypes 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 ins_res; + + typedef typename std::pair + small_ins_res; + + typedef typename std::pair + big_ins_res; + + typedef MultiImplMap 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 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 + std::pair insert(const OtherValTy& OtherKV) { + const value_type* KV = reinterpret_cast( + reinterpret_cast(OtherKV)); + return insert(*KV); + } + + template + 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 MultiImplMap : + public MultiImplMap + { + public: + typedef MultiImplMap 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 Res = + this->insert(std::make_pair(Key, mapped_type())); + return *Res.first; + } + }; + + template + class MultiImplMapIterator { + public: + + typedef MultiImplMapTypes Types; + + typedef typename Types::mapped_type mapped_type; + + typedef typename conditional::type value_type; + + typedef typename conditional::type + small_iterator; + + typedef typename conditional::type + big_iterator; + + typedef typename conditional::type void_ptr_ty; + + typedef value_type *pointer; + typedef value_type &reference; + + typedef MultiImplMapIterator self; + + typedef MultiImplMapIterator non_const_self; + typedef MultiImplMapIterator const_self; + + friend class MultiImplMapIterator; + friend class MultiImplMapIterator; + + protected: + + template + static value_type* toValueTypePtr(OtherValTy& ValTyRef) { + return reinterpret_cast( + reinterpret_cast(&ValTyRef)); + } + + template + static value_type& toValueTypeRef(OtherValTy& ValTyRef) { + return *reinterpret_cast( + reinterpret_cast(&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 + struct MultiImplMapIteratorsFactory { + + typedef MultiImplMapIterator iterator; + typedef MultiImplMapIterator const_iterator; + + template + static iterator it(MapImpl& impl, ItTy it) { + return iterator(it); + } + template + static const_iterator const_it(const MapImpl& impl, ConstItTy it) { + return const_iterator(it); + } + template + static iterator begin(MapImpl& impl) { + return iterator(impl.begin()); + } + template + static const_iterator begin(const MapImpl& impl) { + return const_iterator(impl.begin()); + } + template + static iterator end(MapImpl& impl) { + return iterator(impl.end()); + } + template + static const_iterator end(const MapImpl& impl) { + return const_iterator(impl.end()); + } + }; + + template + struct MultiImplMapIteratorsFactory< + FlatArrayMap, + DenseMap > + { + + typedef FlatArrayMap SmallMapTy; + typedef DenseMap BigMapTy; + + typedef DenseMapIterator + iterator; + typedef DenseMapIterator + 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 00000000000..3bfb1556ca5 --- /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 + class SmallMap : public MultiImplMap< + FlatArrayMap, + DenseMap, + N, true> { + }; +} + +#endif /* SMALLPTRMAP_H_ */ diff --git a/unittests/ADT/SmallMapTest.cpp b/unittests/ADT/SmallMapTest.cpp new file mode 100644 index 00000000000..361f0126bf3 --- /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 a; + SmallMap b; + SmallMap::iterator found; + std::pair::iterator, bool> insRes; + SmallMap::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::value_type Buf7; + Buf7 = a.FindAndConstruct(&buf[7]); + EXPECT_EQ(Buf7.second, 0); +} -- 2.34.1