/* IBM_PROLOG_BEGIN_TAG */ /* This is an automatically generated prolog. */ /* */ /* $Source: src/include/util/impl/stlmap.H $ */ /* */ /* OpenPOWER HostBoot Project */ /* */ /* COPYRIGHT International Business Machines Corp. 2012,2014 */ /* */ /* Licensed under the Apache License, Version 2.0 (the "License"); */ /* you may not use this file except in compliance with the License. */ /* You may obtain a copy of the License at */ /* */ /* http://www.apache.org/licenses/LICENSE-2.0 */ /* */ /* Unless required by applicable law or agreed to in writing, software */ /* distributed under the License is distributed on an "AS IS" BASIS, */ /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or */ /* implied. See the License for the specific language governing */ /* permissions and limitations under the License. */ /* */ /* IBM_PROLOG_END_TAG */ #ifndef __UTIL_IMPL_STLMAP_H #define __UTIL_IMPL_STLMAP_H /** @file stlmap.H * Implementation details of the std::map class. * * See (or your favorite STL reference) for documentation on most of * the functions. * * This class is implemented as a wrapper around a Splay-Tree found * in util/impl/splaytree.H. */ #include #include #include #include #ifndef __UTIL_SPLAYTREE_NS #define __UTIL_SPLAYTREE_NS ::Util::__Util_SplayTree_Impl #endif namespace Util { namespace __Util_StlMap_Impl { // Forward definition of the Map template class. template class Map; /** Template class to form a redirection from the Splay-Tree * iterators and the required STL constructs. * * The map iterators are bidirectional. */ template struct GenericIterator : protected Itr { // Standard typedefs. typedef T value_type; typedef ptrdiff_t difference_type; typedef T* pointer; typedef T& reference; // Allow Map and other GenericIterators to be friends. template friend class GenericIterator; template friend class Map; /** Default copy constructor */ GenericIterator() : Itr() {}; /** Copy Constructor * * Allows copy from any iterator type to another, but pointing to * the same node in the map. */ template GenericIterator(const GenericIterator& r) : Itr((Itr2&) r) {} /** Prefix Increment */ GenericIterator& operator++() { Itr::increment(); return *this; } /** Postfix Increment */ GenericIterator operator++(int) { GenericIterator t = *this; Itr::increment(); return t; } /** Prefix Decrement */ GenericIterator& operator--() { Itr::decrement(); return *this; } /** Postfix Decrement */ GenericIterator operator--(int) { GenericIterator t = *this; Itr::decrement(); return t; } /** Dereference Operator */ reference operator*() { return reinterpret_cast<__UTIL_SPLAYTREE_NS::Node*>( const_cast<__UTIL_SPLAYTREE_NS::Node*>( (Itr::getNode())))->data_T(); } /** Pointer Operator */ pointer operator->() { return &reinterpret_cast<__UTIL_SPLAYTREE_NS::Node*>( const_cast<__UTIL_SPLAYTREE_NS::Node*>( (Itr::getNode())))->data_T(); } /** Equality Comparison operator */ bool operator==(const GenericIterator& r) const { return Itr::operator==(r); } /** Non-equality Comparison operator */ bool operator!=(const GenericIterator& r) const { return Itr::operator!=(r); } protected: /** Copy constructor from a SplayTree::Iterator. * * This is protected because only the Map itself should be * doing this. */ GenericIterator(Itr r) : Itr(r) {}; }; /** Forward iterator version of GenericIterator. */ template struct Iterator : public GenericIterator { typedef GenericIterator iterator; typedef typename iterator::value_type value_type; typedef typename iterator::difference_type difference_type; typedef typename iterator::pointer pointer; typedef typename iterator::reference reference; Iterator() : iterator() {}; Iterator(iterator r) : iterator(r) {}; template friend class Map; protected: Iterator(__UTIL_SPLAYTREE_NS::Iterator r) : iterator(r) {}; }; /** Constant Forward iterator version of GenericIterator */ template struct ConstIterator : public GenericIterator { typedef GenericIterator iterator; typedef typename iterator::value_type value_type; typedef typename iterator::difference_type difference_type; typedef typename iterator::pointer pointer; typedef typename iterator::reference reference; ConstIterator() : iterator() {}; ConstIterator(iterator r) : iterator(r) {}; /** Copy constructor from a non-constant iterator */ ConstIterator(const Iterator& r) : iterator(r) {}; template friend class Map; protected: ConstIterator(__UTIL_SPLAYTREE_NS::ConstIterator r) : iterator(r) {}; }; /** Reverse iterator version of GenericIterator */ template struct RIterator : public GenericIterator { typedef GenericIterator iterator; typedef typename iterator::value_type value_type; typedef typename iterator::difference_type difference_type; typedef typename iterator::pointer pointer; typedef typename iterator::reference reference; RIterator() : iterator() {}; RIterator(iterator r) : iterator(r) {}; template friend class Map; protected: RIterator(__UTIL_SPLAYTREE_NS::RIterator r) : iterator(r) {}; }; /** Constant Reverse iterator version of GenericIterator */ template struct ConstRIterator : public GenericIterator { typedef GenericIterator iterator; typedef typename iterator::value_type value_type; typedef typename iterator::difference_type difference_type; typedef typename iterator::pointer pointer; typedef typename iterator::reference reference; ConstRIterator() : iterator() {}; ConstRIterator(iterator r) : iterator(r) {}; /** Copy constructor from a non-constant iterator */ ConstRIterator(const RIterator& r) : iterator(r) {}; template friend class Map; protected: ConstRIterator(__UTIL_SPLAYTREE_NS::ConstRIterator r) : iterator(r) {}; }; /** Template class to form a redirection from the Splay-Tree * to required STL constructs for an std::map. */ template class Map { public: // Standard STL types. typedef Key key_type; typedef T data_type; typedef std::pair value_type; typedef Compare key_compare; typedef T* pointer; typedef T& reference; typedef const T& const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef Iterator iterator; typedef ConstIterator const_iterator; typedef RIterator reverse_iterator; typedef ConstRIterator const_reverse_iterator; protected: // Internal types for code read-ability. typedef Map _Self; typedef std::pair _value_type; typedef __UTIL_SPLAYTREE_NS::Node<_value_type> _Node; typedef __UTIL_SPLAYTREE_NS::SplayTree _Tree; typedef __UTIL_SPLAYTREE_NS::Iterator _TreeItr; typedef __UTIL_SPLAYTREE_NS::ConstIterator _TreeCItr; _Tree iv_tree; //!< Storage container. key_compare iv_comp; //!< Compare functor. public: /** Default Constructor * * Takes the comparison function which is defaulted in * std::map. */ explicit Map(const key_compare& c) : iv_tree(&_Self::comparator, &_Self::copier, &_Self::deleter), iv_comp(c) {}; /** Copy constructor */ Map(const Map& x) : iv_tree(x.iv_tree), iv_comp(x.iv_comp) {}; iterator begin() { return iv_tree.begin(); } const_iterator begin() const { return iv_tree.begin(); } iterator end() { return iv_tree.end(); } const_iterator end() const { return iv_tree.end(); } reverse_iterator rbegin() { return iv_tree.rbegin(); } const_reverse_iterator rbegin() const { return iv_tree.rbegin(); } reverse_iterator rend() { return iv_tree.rend(); } const_reverse_iterator rend() const { return iv_tree.rend(); } bool empty() const { return iv_tree.empty(); } size_type size() const { return iv_tree.size(); } T& operator[] (const key_type& k) { std::pair result = insert(value_type(k,T())); return (result.first)->second; } std::pair insert(const value_type& x) { _Tree::node* n = NULL; bool rc = iv_tree.insert_by_value(makeSplayTreeValue(x), n); return make_pair(iterator(_TreeItr(&iv_tree, n)), rc); } iterator insert(iterator hint, const value_type& x) { // I don't anticipate much performance improvement with // the splay tree to add the extra code to honor the hint. // To keep the code smaller, we're going to ignore it. return insert(x).first; } void insert(iterator first, iterator last) { iv_tree.insert_range(first.getNode(), last.getNode()); } void insert(const_iterator first, const_iterator last) { iv_tree.insert_range(first.getNode(), last.getNode()); } template void insert(InputIterator first, InputIterator last) { while(first != last) { insert(*first); ++first; } } void erase(iterator position) { iv_tree.remove(position.getNode()); delete reinterpret_cast<_Node*>(position.getNode()); } size_type erase (const key_type& k) { return iv_tree.remove_by_value(makeSplayTreeValue(k)); } void erase(iterator first, iterator last) { while(first != last) { erase(first++); } } void swap(Map& r) { iv_tree.swap(r.iv_tree); std::swap(iv_comp, r.iv_comp); } void clear() { iv_tree.clear(); } key_compare key_comp() const { return iv_comp; } iterator find(const key_type& k) { return iterator( _TreeItr(&iv_tree, iv_tree.find_by_value(makeSplayTreeValue(k)) ) ); } const_iterator find(const key_type& k) const { return const_iterator( _TreeCItr(&iv_tree, iv_tree.find_by_value(makeSplayTreeValue(k)) ) ); } size_type count(const key_type& k) const { _Tree::node* unused = NULL; if (iv_tree.find_hint_by_value(makeSplayTreeValue(k), unused)) { return 1; } else { return 0; } } iterator lower_bound(const key_type& k) { return iterator( _TreeItr(&iv_tree, iv_tree.lower_bound_by_value( makeSplayTreeValue(k) ) ) ); } const_iterator lower_bound(const key_type& k) const { return const_iterator( _TreeCItr(&iv_tree, iv_tree.lower_bound_by_value( makeSplayTreeValue(k) ) ) ); } iterator upper_bound(const key_type& k) { return iterator( _TreeItr(&iv_tree, iv_tree.lower_bound_by_value( makeSplayTreeValue(k) ) ) ); } const_iterator upper_bound(const key_type& k) const { return const_iterator( _TreeCItr(&iv_tree, iv_tree.lower_bound_by_value( makeSplayTreeValue(k) ) ) ); } std::pair equal_range( const key_type& k) { return make_pair(lower_bound(k),upper_bound(k)); } std::pair equal_range( const key_type& k) const { return make_pair(lower_bound(k),upper_bound(k)); } private: /** * Utility function to convert a key to a SplayTree "value". * * This is safe assuming that the comparison function never * uses anything outside of the key. Since map's compare only * based on the key, this is a valid assumption. * * The code is pretty messy here due to all the casting but * what it does is: * (pair*)(&k - (distance pair to * pair.first)) * * As in, it finds the pointer to the beginning key-value pair * based on the address of just the key. */ const void** makeSplayTreeValue(const key_type& k) const { typename Util::Traits::remove_const::type key = const_cast::type>(&k); value_type* unused = NULL; const size_t offset = reinterpret_cast(&unused->first) - reinterpret_cast(unused); return reinterpret_cast( reinterpret_cast(key) - offset); } /** * Utility function to convert a pair into a * SplayTree "value". * * This is a fairly straight-forward cast since no address * translation is necessary. */ const void** makeSplayTreeValue(const value_type& x) const { return reinterpret_cast( const_cast(&x)); } /** * Compare two key's using the map's compare function. * * @param[in] k1 - First key to compare. * @param[in] k2 - Second key to compare. * * @return A strcmp-style integer (-1, 0, 1) with the * comparison results. */ int compare(const key_type& k1, const key_type& k2) const { if (iv_comp(k1,k2)) { return -1; } else if (iv_comp(k2,k1)) { return 1; } else { return 0; } } /** * Functor to compare two SplayTree nodes using the comparison * function for this tree. * * This will call this->compare(n1.key, n2,key) to get the * result. * * @param[in] t - The address of the SplayTree (&iv_tree), * which can be used to find "this". * @param[in] n1 - The first node to compare. * @param[in] n2 - The second node to compare. * * @return See compare. * * This function involves some messy casting: * - The 't' is the address of this->iv_tree. Using t, * this function must find "this", so that it can call * this->compare(...). * * - The 'n1' and 'n2' parameters are SplayTree nodes, * which must be converted to our node types, and then * the keys are retrieved from the nodes to call the * comparison function. * */ static int comparator(const _Tree* t, const _Tree::node* n1, const _Tree::node* n2) { const _Self* unused = NULL; const size_t offset = reinterpret_cast(&unused->iv_tree) - reinterpret_cast(unused); return reinterpret_cast( reinterpret_cast(t) - offset)-> compare( reinterpret_cast(n1)->data_T().first, reinterpret_cast(n2)->data_T().first); } /** * Functor to copy a SplayTree node into a newly created node. * * This function must cast the SplayTree node into our node * type, call the copy constructor, and then return a cast-back * to SplayTree node. * * The result is similar to 'return new _Node(n)'. * * @param[in] n - The node to be copied. * * @return A pointer to a newly created node, being a copy of * the parameter 'n'. */ static _Tree::node* copier(const _Tree::node* n) { return reinterpret_cast<_Tree::node*>(new _Node( *reinterpret_cast(n))); } /** * Functor to delete a SplayTree node. * * This function must cast the SplayTree node into our node * type and delete it. * * @param[in] n - The node to be deleted. */ static void deleter(_Tree::node* n) { delete reinterpret_cast<_Node*>(n); } }; }; }; #endif