diff options
| -rw-r--r-- | src/include/functional | 7 | ||||
| -rw-r--r-- | src/include/map | 358 | ||||
| -rw-r--r-- | src/include/util/algorithm.H | 57 | ||||
| -rw-r--r-- | src/include/util/impl/splaytree.H | 703 | ||||
| -rw-r--r-- | src/include/util/impl/stlmap.H | 651 | ||||
| -rw-r--r-- | src/include/util/traits/remove_const.H | 71 | ||||
| -rw-r--r-- | src/lib/makefile | 2 | ||||
| -rw-r--r-- | src/lib/splaytree.C | 514 | ||||
| -rw-r--r-- | src/makefile | 2 | ||||
| -rw-r--r-- | src/usr/testcore/lib/stltest.H | 37 |
10 files changed, 2214 insertions, 188 deletions
diff --git a/src/include/functional b/src/include/functional index 5ef81bf49..ac0b070f4 100644 --- a/src/include/functional +++ b/src/include/functional @@ -35,6 +35,13 @@ namespace std typedef R result_type; ///< type of the return type }; + template<typename A, typename R> + struct unary_function + { + typedef A argument_type; + typedef R result_type; + }; + /** * less template */ diff --git a/src/include/map b/src/include/map index 90af2a8c2..115cee504 100644 --- a/src/include/map +++ b/src/include/map @@ -20,8 +20,8 @@ // Origin: 30 // // IBM_PROLOG_END -#ifndef stl_map -#define stl_map +#ifndef __STL_MAP_H +#define __STL_MAP_H #include <stddef.h> @@ -29,79 +29,98 @@ #if !defined( __STDC_LIMIT_MACROS) #define __STDC_LIMIT_MACROS #endif + #include <stdint.h> -#include <new> #include <utility> -#include <list> #include <functional> +#include <util/impl/stlmap.H> + +#ifndef __UTIL_STLMAP_NS +#define __UTIL_STLMAP_NS ::Util::__Util_StlMap_Impl +#endif + namespace std { /** - * Simple map template class based on list - * @Note value_comp not supported. + * STL map template class. + * + * @note value_comp not supported. + * + * This class inherits from Util::__Util_StlMap_Impl::Map, which hides all + * of the implementation details of the map. Most of the functions here + * are simply a redirection to the Util::...::Map version. */ template <typename Key, typename T, typename Compare = std::less<Key> > - class map + class map : public __UTIL_STLMAP_NS::Map<Key, T, Compare> { + private: + typedef typename __UTIL_STLMAP_NS::Map<Key, T, Compare> submap; public: - typedef Key key_type; - typedef T mapped_type; - typedef pair<const Key, T> value_type; - typedef T& reference; - typedef const T& const_reference; - typedef ListIterator_t< value_type > iterator; - typedef ListConstIterator_t< value_type > const_iterator; -// typedef MapIterator_t<Key,T> iterator; -// typedef MapConstIterator_t<Key,T> const_iterator; - typedef size_t size_type; - typedef Compare key_compare; - + // Inherit all of the standard typedefs from the Map class. +#define __STLMAP_INHERIT_TYPEDEF(type) \ + typedef typename submap::type type + + __STLMAP_INHERIT_TYPEDEF(key_type); + __STLMAP_INHERIT_TYPEDEF(data_type); + __STLMAP_INHERIT_TYPEDEF(value_type); + __STLMAP_INHERIT_TYPEDEF(key_compare); + __STLMAP_INHERIT_TYPEDEF(pointer); + __STLMAP_INHERIT_TYPEDEF(reference); + __STLMAP_INHERIT_TYPEDEF(const_reference); + __STLMAP_INHERIT_TYPEDEF(size_type); + __STLMAP_INHERIT_TYPEDEF(difference_type); + __STLMAP_INHERIT_TYPEDEF(iterator); + __STLMAP_INHERIT_TYPEDEF(const_iterator); + __STLMAP_INHERIT_TYPEDEF(reverse_iterator); + __STLMAP_INHERIT_TYPEDEF(const_reverse_iterator); + +#undef __STLMAP_INHERIT_TYPEDEF /** * Default constructor */ - __attribute__ ((always_inline)) - explicit map(const key_compare& c = Compare()) : iv_comp(c) {} + explicit map(const key_compare& c = Compare()) : submap(c) {} /** - * Constructor + * Range-Insert Constructor * @param[in] first InputIterator * @param[in] last InputIterator + * + * Copies all of the elements from [first, last) into the map. */ template <typename InputIterator> __attribute__ ((always_inline)) - map( InputIterator first, InputIterator last, const key_compare& c = Compare()) - : iv_comp(c) - { iv_list(first, last); } + map( InputIterator first, InputIterator last, + const key_compare& c = Compare()) + : submap(c) + { + this->insert(first, last); + } /** * Copy Constructor * @param i_x Source map */ __attribute__ ((always_inline)) - map (const map<Key,T,Compare>& i_x) - { - iv_list(i_x.iv_list); - iv_comp(i_x.iv_comp); - } + map (const map<Key,T,Compare>& i_x) : submap(i_x) {} /** * Destructor */ __attribute__ ((always_inline)) - ~map () {} + ~map () { } /** * operator= * @param[in] x Source map */ __attribute__ ((always_inline)) - map<Key,T, Compare> & operator= (const map<Key, T, Compare>& x) + map<Key,T, Compare>& operator= (const map<Key, T, Compare>& x) { - iv_list = x.iv_list; - iv_comp = x.iv_comp; + submap::iv_comp = x.iv_comp; + submap::iv_tree = x.iv_tree; return *this; } @@ -110,49 +129,88 @@ namespace std * @return iterator */ __attribute__ ((always_inline)) - iterator begin() { return iv_list.begin(); } + iterator begin() + { return submap::begin(); } /** * Get iterator to the beginning element * @return const_iterator */ __attribute__ ((always_inline)) - const_iterator begin() const { return iv_list.begin(); } + const_iterator begin() const + { return submap::begin(); } /** * Get iterator to the last element + 1 * @return iterator */ __attribute__ ((always_inline)) - iterator end() { return iv_list.end(); } + iterator end() + { return submap::end(); } /** * Get iterator to the last element + 1 * @return const_iterator */ __attribute__ ((always_inline)) - const_iterator end() const { return iv_list.end(); } + const_iterator end() const + { return submap::end(); } + + /** + * Get reverse iterator to the last element + * @return reverse_iterator + */ + __attribute__ ((always_inline)) + reverse_iterator rbegin() + { return submap::rbegin(); } + + /** + * Get reverse iterator to the last element + * @return reverse_const_iterator + */ + __attribute__ ((always_inline)) + const_reverse_iterator rbegin() const + { return submap::rbegin(); } + + /** + * Get reverse iterator to the first element - 1 + * @return reverse_iterator + */ + __attribute__ ((always_inline)) + reverse_iterator rend() + { return submap::rend(); } + + /** + * Get reverse iterator to the first element - 1 + * @return reverse_const_iterator + */ + __attribute__ ((always_inline)) + const_reverse_iterator rend() const + { return submap::rend(); } /** * Query empty container * @return true if container is empty otherwise false */ __attribute__ ((always_inline)) - bool empty() const { return iv_list.empty(); } + bool empty() const + { return submap::empty(); } /** * Query number of elements in the container * @return number of elements in the container */ __attribute__ ((always_inline)) - size_type size() const { return iv_list.size(); } + size_type size() const + { return submap::size(); } /** * Max size of container * @return theoretical maximum size based on cpu word size */ __attribute__ ((always_inline)) - size_type max_size() const { return UINT64_MAX/sizeof(T); } + size_type max_size() const + { return UINT64_MAX/sizeof(T); } /** * operator[] @@ -160,88 +218,82 @@ namespace std * @return a reference to the element whos key is x */ __attribute__ ((always_inline)) - T& operator[] (const key_type& k) - { - pair<iterator,bool> result = insert(value_type(k,T())); - return (result.first)->second; - } - + T& operator[] (const key_type& k) + { return submap::operator[](k); } /** * Insert element * @param[in] x map key/value pair - * @return std::pair.first is iterator pointing to new or existing element, - * std::pair.second is true if new element inserted, false if already existing. + * @return std::pair.first is iterator pointing to new or existing + * element, std::pair.second is true if new element + * inserted, false if already existing. + * * @note won't add element if it's key already exists in the map */ - pair<iterator,bool> - insert (const value_type& x ) - { - iterator i = lower_bound(x.first); // x.first <= i->first - if(i != end() && !key_comp()(x.first,i->first)) // x.first == i->first - { - return make_pair(i,false); - } - - i = insert(i,x); - return make_pair(i,true); - } - + pair<iterator,bool> insert (const value_type& x ) + { return submap::insert(x); } /** * Insert element - * @param[in] hint bidi iterator that is a hint to where to insert the element + * @param[in] hint bidi iterator that is a hint to where to insert + * the element * @param[in] x map key/value to insert (copy in) - * @return an iterator pointing to either the new or existing element - * @note A good hint makes this very efficient. A bad hint slows it down. An element - * will never be inserted out of order. Will never insert if key already exists. - */ - iterator - insert ( iterator hint, const value_type& x) - { - iterator i = iv_list.begin(); - if(hint != i) --hint; - if(hint != end() && key_comp()(hint->first,x.first)) // potential good hint - { - i = hint; - } - while(i != end() && key_comp()(i->first,x.first)) ++i; - // x.first <= i->first - - if(i == end() || key_comp()(x.first, i->first)) - { - i = iv_list.insert(i,x); - } - // else was already in the list - return i; - } + * + * @return an iterator pointing to either the new or existing + * element + * @note A good hint makes this very efficient. A bad hint slows + * it down. An element will never be inserted out of order. + * Will never insert if key already exists. + */ + iterator insert ( iterator hint, const value_type& x) + { return submap::insert(hint, x); } + + /** + * Insert a range of new elements + * + * (optimized function for iterator) + * + * @param[in] first Beginning of the range + * @param[in] last End of the range. + * @post Elements inserted + */ + void insert( iterator first, iterator last) + { return submap::insert(first, last); } + + /** + * Insert a range of new elements + * + * (optimized function for const_iterator) + * + * @param[in] first Beginning of the range + * @param[in] last End of the range. + * @post Elements inserted + */ + void insert( const_iterator first, const_iterator last) + { return submap::insert(first, last); } /** * Insert a range of new elements + * + * (generic version for any iterator) + * * @param[in] first InputIterator * @param[in] last InputIterator * @post Elements inserted */ template <typename InputIterator> - void insert( InputIterator first, InputIterator last ) - { - while(first != last) - { - insert(*first); - ++first; - } - } + void insert( InputIterator first, InputIterator last ) + { return submap::insert(first, last); } /** * Remove an element from the container * @param position iterator - * @post element pointed to by iterator is removed from the container + * @post element pointed to by iterator is removed from the + * container */ __attribute__ ((always_inline)) void erase (iterator position ) - { - iv_list.erase(position); - } + { submap::erase(position); } /** * Remove an element from the container by key @@ -249,16 +301,7 @@ namespace std * @return Number of elements removed. For map, 0 or 1. */ size_type erase (const key_type& k) - { - size_type result = 0; - iterator i = find(k); - if(i != end()) - { - erase(i); - result = 1; - } - return result; - } + { return submap:: erase(k); } /** * Remove a range of elements from the container @@ -266,10 +309,8 @@ namespace std * @param last iterator of element to remove + 1 */ __attribute__ ((always_inline)) - void erase (iterator first, iterator last) - { - iv_list.erase(first,last); - } + void erase (iterator first, iterator last) + { submap::erase(first,last); } /** * Swap this container with another @@ -277,23 +318,23 @@ namespace std */ __attribute__ ((always_inline)) void swap(map<Key,T, Compare>& mp) - { - iv_list.swap(mp.iv_list); - std::swap(iv_comp,mp.iv_comp); - } + { submap::swap(mp); } /** * clear the map */ __attribute__ ((always_inline)) - void clear() { iv_list.clear(); } + void clear() + { submap::clear();; } //Observers /** - * Returns the key comparison object from which the map was constructed + * Returns the key comparison object from which the map was + * constructed * @return Compare */ - key_compare key_comp() const { return iv_comp; } + key_compare key_comp() const + { return submap::key_comp(); } /** * returns a value comparison object, built from the key comparison @@ -308,17 +349,7 @@ namespace std * @return iterator to element or end() if not found */ iterator find (const key_type& k) - { - iterator i = lower_bound(k); - if(i != end()) - { - if(key_comp()(k, i->first)) - { - i = end(); - } - } - return i; - } + { return submap::find(k); } /** * Find an element @@ -326,18 +357,8 @@ namespace std * @return const_iterator to element or end() if not found */ __attribute__ ((always_inline)) - const_iterator find( const key_type& k) const - { - const_iterator i = lower_bound(k); - if(i != end()) - { - if(key_comp()(k, i->first)) - { - i = end(); - } - } - return i; - } + const_iterator find( const key_type& k) const + { return submap::find(k); } /** * Number of elements in the container with the given key @@ -346,11 +367,7 @@ namespace std */ __attribute__ ((always_inline)) size_type count (const key_type& k) const - { - if(find(k) != end()) - return 1; - return 0; - } + { return submap::count(k); } /** * Return an iterator pointing to the first element in the @@ -359,13 +376,7 @@ namespace std * @return iterator */ iterator lower_bound (const key_type& k) - { - iterator i = iv_list.begin(); - while(i != end() && key_comp()(i->first,k)) ++i; - return i; - } - - + { return submap::lower_bound(k); } /** * Return a const_iterator pointing to the first element in the @@ -375,11 +386,7 @@ namespace std */ __attribute__ ((always_inline)) const_iterator lower_bound (const key_type& k) const - { - const_iterator i = iv_list.begin(); - while( i != end() && key_comp()(i->first,k)) ++i; - return i; - } + { return submap::lower_bound(k); } /** * Returns an iterator pointing to the first element in the @@ -388,11 +395,7 @@ namespace std * @return iterator */ iterator upper_bound (const key_type& k) - { - iterator i = lower_bound(k); // k <= i->first - if(i != end() && !key_comp()(k,i->first)) ++i; // k == i->first - return i; - } + { return submap::upper_bound(k); } /** * Returns a const_iterator pointing to the first element in the @@ -402,11 +405,7 @@ namespace std */ __attribute__ ((always_inline)) const_iterator upper_bound (const key_type& k) const - { - const_iterator i = lower_bound(); // k <= i->first - if(i != end() && !key_comp()(k,i->first)) ++i; // k == i->first - return i; - } + { return submap::upper_bound(k); } /** * Return the bounds of a range that includes all the elements in @@ -416,28 +415,15 @@ namespace std * @note map does not allow duplicate keys, so * the range returned will contain at most one element */ - pair<iterator,iterator> - equal_range( const key_type& k) - { - return make_pair(lower_bound(k),upper_bound(k)); - } + pair<iterator,iterator> equal_range( const key_type& k) + { return submap::equal_range(k); } /** * Const verstion of equal_range - see equal_range above */ - pair<const_iterator, const_iterator> + pair<const_iterator, const_iterator> equal_range( const key_type& k) const - { - return make_pair(lower_bound(k),upper_bound(k)); - } - - protected: - - key_compare iv_comp; //!< Compare function/class - - private: // data - - list<value_type> iv_list; //!< The implementation + { return submap::equal_range(k); } }; }; diff --git a/src/include/util/algorithm.H b/src/include/util/algorithm.H new file mode 100644 index 000000000..1ad7358ea --- /dev/null +++ b/src/include/util/algorithm.H @@ -0,0 +1,57 @@ +// IBM_PROLOG_BEGIN_TAG +// This is an automatically generated prolog. +// +// $Source: src/include/util/algorithm.H $ +// +// IBM CONFIDENTIAL +// +// COPYRIGHT International Business Machines Corp. 2012 +// +// p1 +// +// Object Code Only (OCO) source materials +// Licensed Internal Code Source Materials +// IBM HostBoot Licensed Internal Code +// +// The source code for this program is not published or other- +// wise divested of its trade secrets, irrespective of what has +// been deposited with the U.S. Copyright Office. +// +// Origin: 30 +// +// IBM_PROLOG_END +#ifndef __UTIL_ALGORITHM_H +#define __UTIL_ALGORITHM_H + +namespace Util +{ + namespace Algorithm + { + + /** @struct static_min + * @brief Template class to perform a compile-time min calculation. + * + * Example: + * static_min<size_t, 5, 7>::value == 5 + */ + template <typename T, T a, T b> + struct static_min + { + static const T value = (a < b) ? a : b; + }; + + /** @struct static_max + * @brief Template class to perform a compile-time max calculation. + * + * Example: + * static_max<size_t, 5, 7>::value == 7 + */ + template <typename T, T a, T b> + struct static_max + { + static const T value = (a > b) ? a : b; + }; + + }; +}; +#endif diff --git a/src/include/util/impl/splaytree.H b/src/include/util/impl/splaytree.H new file mode 100644 index 000000000..9159ddddc --- /dev/null +++ b/src/include/util/impl/splaytree.H @@ -0,0 +1,703 @@ +// IBM_PROLOG_BEGIN_TAG +// This is an automatically generated prolog. +// +// $Source: src/include/util/impl/splaytree.h $ +// +// IBM CONFIDENTIAL +// +// COPYRIGHT International Business Machines Corp. 2012 +// +// p1 +// +// Object Code Only (OCO) source materials +// Licensed Internal Code Source Materials +// IBM HostBoot Licensed Internal Code +// +// The source code for this program is not published or other- +// wise divested of its trade secrets, irrespective of what has +// been deposited with the U.S. Copyright Office. +// +// Origin: 30 +// +// IBM_PROLOG_END + +#ifndef __UTIL_IMPL_SPLAYTREE_H +#define __UTIL_IMPL_SPLAYTREE_H + +/** @file splaytree.H + * + * Implementation of the Splay-Tree algorithm, which is to be used for + * containers such as STL map. This tree could likely be reused for set, + * multiset, multimap, etc., but is not currently written with support + * for those data structures. + * + * The Splay-Tree algorithm is a standard binary-search-tree with one + * additional operation: splay. Splay is a special sequence of rotations + * that move a node up to the root of the tree. Since Splay-Trees are + * not constantly balanced like AVL or Red-Black trees, the splay operation + * balances the tree, roughly. Since splaying is done on operations like + * "find" it has the effect of speeding up access to frequently utilized + * data because frequently accessed nodes are moved up near the root of the + * tree. + * + * The operations on a standard BST are found in many algorithms books. I + * used "Introduction to Algorithms, 2nd Ed." by Cormen, Leiserson, Rivest, + * and Stein. The additional splay operation was first described in a 1985 + * paper by Sleator and Tarjan, but explaination of it is readily available + * online. + * + * Additional reference: http://en.wikipedia.org/wiki/Splay_tree + * + * Splay-Tree was chosen over AVL or Red-Black for two reasons: + * 1) Simplicity of implementation. + * - Insert and delete are non-trivial on a balanced tree due to + * needing to maintain balance. + * 2) Performance of expected typical cases. + * - This paper (http://benpfaff.org/papers/libavl.pdf) suggests + * that Splay-Trees tend to perform better for any non-random + * work load. + */ + +#include <stdint.h> +#include <util/algorithm.H> +#include <functional> +#include <new> +#include <stdint.h> + +namespace Util +{ + namespace __Util_SplayTree_Impl + { + /** @class NodeTraits + * Defines typedefs and constants needed for all nodes. + */ + struct NodeTraits + { + public: + /** Direction used for accessing the 'child' links */ + typedef uint8_t DIRECTION; + + static const DIRECTION LEFT = 0; + static const DIRECTION RIGHT = 1; + }; + + /** @class Node + * Stores the content for a SplayTree Node. + * + * This is implemented as a template so that the data storage area + * can be of different length (to store the template type). The + * SplayTree assumes all nodes it is operating on can just store a + * void* and it is up to the using container to cast/interpret the + * data storage area differently if needed. + */ + template <typename T> + struct Node : public NodeTraits + { + /** Default constructor. + * + * Initializes the node-links and data storage area. + */ + Node() + { + parent = child[LEFT] = child[RIGHT] = NULL; + + new (&data_T()) T(); + }; + + /** Copy constructor from a Node. + * + * Initializes the node-links and copies the data storage area + * from the copied node. + */ + explicit Node(const Node<T>& r) + { + // Don't want to copy the links out of the other node because + // they're from a different tree. + parent = child[LEFT] = child[RIGHT] = NULL; + + new (&data_T()) T(r.data_T()); + }; + + /** Copy constructor from a T. + * + * Initializes the node-links and copies the data into the data + * storage area. + */ + explicit Node(const T& v) + { + parent = child[LEFT] = child[RIGHT] = NULL; + + new (&data_T()) T(v); + }; + + + /** Access the data storage area as a T&. */ + T& data_T() + { + return *(reinterpret_cast<T*>(data)); + }; + /** Access the data storage area as a const T&. */ + const T& data_T() const + { + return *(reinterpret_cast<const T*>(data)); + } + + // Allow the SplayTree to use our internals. + friend class SplayTree; + + protected: + /** Utility function to converts data-object to a Node. + * + * This is safe assuming that the user of the Node does not + * access anything outside of the data storage area. This + * is typically used in functions like "find" which need to + * convert a pointer-to-data into a Node for searching the + * tree. Since the node-comparison functions only look at + * the data storage area (ex. map key comparison), this is + * a valid assumption. + * + * The code here uses some messy casting to find the start + * of a Node based on the address of its data storage area. + * The optimizing compiler will turn this into a simple + * pointer subtraction. + */ + static Node* convertToNode(T* data) + { + Node<T>* unused = NULL; + const size_t offset = + reinterpret_cast<char*>(&unused->data) - + reinterpret_cast<char*>(unused); + + return reinterpret_cast<Node*>( + reinterpret_cast<char*>(data) - offset); + }; + + /** Assignment operator + * Default copy would work here but define to be explicit. + * + * Only want to allow SplayTree to use this, because we're + * going to copy pointers as well. + */ + Node& operator=(const Node<T>& r) + { + parent = r.parent; + child[LEFT] = r.child[LEFT]; + child[RIGHT] = r.child[RIGHT]; + + new (&data_T()) T(r.data_T()); + + return *this; + } + + + // These members are mutable so that operations like find, + // which are 'const' from an STL perspective, can still do + // splays. Since a splay does not change the content of the + // container nor does it destroy any iterators, operations + // that use it can still be considered "const" from the + // perspective of an external caller. + + /** Node-link to parent node. */ + mutable Node<T>* parent; + /** Node-link to children nodes. */ + mutable Node<T>* child[2]; + + /** Data storage area. + * + * Uses a compile-time calculation (static_max) to + * ensure this will be at least the size of a pointer. + */ + char data[Util::Algorithm::static_max<size_t, + sizeof(void*), + sizeof(T)>::value]; + }; + + // Forward declaration of iterator types. + class Iterator; + class ConstIterator; + class RIterator; + class ConstRIterator; + + /** The SplayTree itself. */ + class SplayTree : public NodeTraits + { + public: + /** Typedef for our Node type, storing a void*. */ + typedef Node<const void*> node; + /** Functor typedef for comparing nodes. */ + typedef int(*comparator)(const SplayTree*, + const node*,const node*); + /** Functor typedef for copying nodes. */ + typedef node*(*copier)(const node*); + /** Functor typedef for deleting nodes. */ + typedef void(*deleter)(node*); + + /** Default constructor. */ + SplayTree(comparator comp, copier copy, deleter del); + + /** Copy constructor. + * + * This will copy the functor (addresses) from the copied + * tree and duplicate all the contents of the tree. + */ + SplayTree(const SplayTree&); + + /** Default destructor. + * + * Calls the 'deleter' functor to clean up all the + * contained nodes. + */ + ~SplayTree(); + + /** Assignment operator. + * + * This has similar behavior as the copy-constructor. + * + * This will copy the functor (addresses) from the copied + * tree and duplicate all the contents of the tree. + */ + SplayTree& operator=(const SplayTree&); + + /** Insert a node into the tree. + * + * This function inserts a node into the correct location + * in the tree. This insert is done without ensuring that + * the node doesn't already exist, so if the container + * requires non-duplicate entries then some other + * mechanism must be used to enforce this (ex. a find + * first). + * + * @param[in] n - The node to be inserted. + */ + void insert(node* n); + + /** Insert a range of nodes into the tree. + * + * This function iterates through all the nodes in the + * range [n1, n2), copying and inserting every node in + * the range. + * + * @param[in] n1 - The beginning of the range. + * @param[in] n2 - The end of the range. + */ + void insert_range(const node* n1, const node* n2); + + /** Remove a node from the tree. + * + * This function assumes that the node is, in fact, in + * the tree. Undefined behavior may occur if it is not. + * + * @param[in] n - The node to be removed. + */ + void remove(node* n); + + /** Find the likely location of a node in the tree. + * + * Searches the tree for a node like 'n'. If it is found + * the similar node is saved in hint. If not found, then + * a node who's child would have been 'n' is saved in + * hint. + * + * @param[in] n - The node to search for. + * @param[out] hint - The node closest to 'n' in the tree. + * + * @retval true - if an exact match of 'n' was found. + * @retval false - if an exact match of 'n' was not found. + */ + bool find_hint(node* n, node*& hint) const; + + + /** Erase all nodes in the tree and deletes them. */ + void clear(); + + /** Swap one tree with another. */ + void swap(SplayTree&); + + /** Insert a node, with a specific value, into the tree. + * + * Searches the tree for a node containing 'v'. If the + * node is found, it is returned as 'n'. If the node is + * not found, a new node is creating containing 'v'. + * + * @param[in] v - The value to insert into the tree. + * @param[out] n - The node created, or already having, v. + * + * @retval true - A new node was created. + * @retval false - An existing node with 'v' was found. + */ + bool insert_by_value(const void** v, node*& n); + + /** Remove a node, with a specific value, from the tree. + * + * Searches the tree for a node containing 'v' and + * removes it if found. The number of nodes removed is + * returned (0 or 1). + * + * @param[in] v - The value to remove from the tree. + * @return The number of nodes removed. + */ + size_t remove_by_value(const void** v); + + /** Find the likely location of a node containing a value + * in the tree. + * + * See 'find_hint'. + * + * @param[in] v - The value to search for. + * @param[out] hint - The node closest to 'v' in the tree. + * + * @return See 'find_hint'. + */ + bool find_hint_by_value(const void** v, node*& hint) const; + + /** Find node containing a value in the tree. + * + * Searches the tree for a node containing 'v' and + * returns it if found. + * + * @param[in] v - The value to search for. + * + * @return The node if found or NULL. + */ + node* find_by_value(const void** v) const; + + /** Find the node in the tree lower-bounding a value. + * + * See STL documentation for what "lower_bound" means. + * + * @param[in] v - The value to lower-bound. + * + * @return The node lower-bounding or NULL. + */ + node* lower_bound_by_value(const void** v) const; + + /** Find the node in the tree upper-bounding a value. + * + * See STL documentation for what "upper_bound" means. + * + * @param[in] v - The value to upper-bound. + * + * @return The node upper-bounding or NULL. + */ + node* upper_bound_by_value(const void** v) const; + + /** Determine if the tree is empty. */ + bool empty() const + { return (header_n()->data_T() == 0); }; + /** Determine the size (in nodes) of the tree. */ + size_t size() const + { return (header_n()->data_T()); }; + + /** Get a pointer to the first node (smallest by value). */ + node* front() + { return header.child[LEFT]; }; + /** Get a pointer to the first node (smallest by value). */ + const node* front() const + { return header.child[LEFT]; }; + + /** Get a pointer to the last node (largest by value). */ + node* back() + { return header.child[RIGHT]; }; + /** Get a pointer to the last node (largest by value). */ + const node* back() const + { return header.child[RIGHT]; }; + + /** Get the iterator to the beginning of the tree. */ + Iterator begin(); + /** Get the iterator to the beginning of the tree. */ + ConstIterator begin() const; + /** Get the iterator past the end of the tree. */ + Iterator end(); + /** Get the iterator past the end of the tree. */ + ConstIterator end() const; + + /** Get the reverse iterator to the beginning. */ + RIterator rbegin(); + /** Get the reverse iterator to the beginning. */ + ConstRIterator rbegin() const; + /** Get the reverse iterator past the end. */ + RIterator rend(); + /** Get the reverse iterator past the end. */ + ConstRIterator rend() const; + + // Allow the iterator classes to access our internal + // methods (successor / predecessor especially). + friend class Iterator; + friend class ConstIterator; + friend class RIterator; + friend class ConstRIterator; + + + private: + /** Root of the tree. + * Contains root of the tree and left-most / right-most + * nodes. Store size in data as a size_t with header_n(). + */ + node header; + + // Storage locations for the functors. + comparator compare_functor; + copier copy_functor; + deleter delete_functor; + + /** Utility function for mapping the Node<void*> to a + * Node<size_t> for accessing tree size out of the + * tree root-header. */ + Node<size_t>* header_n() + { return reinterpret_cast<Node<size_t>*>(&header); }; + /** Utility function for mapping the Node<void*> to a + * Node<size_t> for accessing tree size out of the + * tree root-header. */ + const Node<size_t>* header_n() const + { return + reinterpret_cast<const Node<size_t>*>(&header); }; + + /** Iterate up to the top of a tree from a node. */ + node* topmost(node* n) const + { return n->parent ? + topmost(n->parent) : n; }; + /** Iterate down to the left-most child of a subtree. */ + node* leftmost(node* n) const + { return n->child[LEFT] ? + leftmost(n->child[LEFT]) : n; }; + /** Iterate down to the right-most child of a subtree. */ + node* rightmost(node* n) const + { return n->child[RIGHT] ? + rightmost(n->child[RIGHT]) : n; }; + + /** Determine the direction linking two nodes. + * + * @param[in] p - The "parent" node of the link. + * @param[in] c - The "child" node of a link. + * + * @return The direction linking p -> c. + * @retval LEFT - p->child[LEFT] == c + * @retval RIGHT - p->child[LEFT] != c + */ + DIRECTION direction(node* p, node* c) const + { return (p->child[LEFT] == c) ? LEFT : RIGHT; }; + + /** Find the predecessor of a node within the tree. + * + * This is the standard predecessor operation. + * + * @return The predecessor or NULL if none exists. + */ + const node* predecessor(const node* n) const; + /** Find the successor of a node within the tree. + * + * This is the standard successor operation. + * + * @return The successor or NULL if none exists. + */ + const node* successor(const node* n) const; + + /** Find the predecessor of a node within the tree. */ + node* predecessor(node* n) const + { + return const_cast<node*>( + predecessor( + const_cast<const node*>(n))); + }; + /** Find the successor of a node within the tree. */ + node* successor(node* n) const + { + return const_cast<node*>( + successor( + const_cast<const node*>(n))); + }; + + /** Rotate a node "up" in a direction. + * + * @param[in] n - The node to rotate. + * @param[in] d - The direction to rotate. + * + * If d is left, n->parent will become the left child of + * n. If d is right, n->parent will become the right + * child of n. The sub-trees of n and n->parent are + * adjusted to make this a valid transformation. + */ + void rotate(node* n, DIRECTION d) const; + + /** Splay a node to the root. + * + * @param[in] n - The node to splay. + */ + void splay(node* n) const; + + /** Perform an insert of a node onto a subtree. + * + * @param[in] t - The subtree to insert the node onto. + * @param[in] n - The node to insert. + * + * This function assumes that t is an appropriate + * place to insert n. It adds n onto the left or right + * child location in t, as appropriate by comparison. + */ + void __insert(node* t, node* n); + /** Perform a search of a node within a subtree. + * + * @param[in,out] t - The subtree to find the node in. + * @param[in] n - The node to find. + * + * Searches the subtree for a node like 'n' or a node + * where 'n' would belong as a direct child. The subtree + * is updated to be this node. If an exact match is + * found 'true' is returned. + * + * @return bool of if an exact match of n is found. + */ + bool __find(node*& t, node* n) const; + + }; + + /** Iterator class for SplayTree. + * + * Acts as a STL iterator. + */ + class Iterator + { + public: + /** Default constructor. */ + Iterator(SplayTree* t = NULL, + SplayTree::node* n = NULL) : + tree(t), node(n) {}; + + /** Increment the iterator (like ++iterator). */ + void increment(); + /** Decrement the iterator (like --iterator). */ + void decrement(); + + /** Compare two iterators for equality. */ + bool operator==(const Iterator& r) const + { + return (tree == r.tree) && (node == r.node); + } + /** Compare two iterators for non-equality. */ + bool operator!=(const Iterator& r) const + { + return !((*this)==r); + } + + friend class ConstIterator; + + protected: + /** Get the node pointed to by this iterator. */ + SplayTree::node* getNode() const { return node; } + + private: + SplayTree* tree; + // Typically node points to a node within the tree, but + // the value NULL is special and indicates the STL "end()". + SplayTree::node* node; + + // Standard copy constructor / destructors may be used. + }; + + /** Iterator class for SplayTree. + * + * Acts as a STL const_iterator. + */ + class ConstIterator + { + public: + /** Default constructor. */ + ConstIterator(const SplayTree* t = NULL, + const SplayTree::node* n = NULL) : + tree(t), node(n) {}; + /** Conversion constructor from Iterator. */ + ConstIterator(Iterator& r) : + tree(r.tree), node(r.node) {}; + + /** Increment the iterator (like ++iterator). */ + void increment(); + /** Decrement the iterator (like --iterator). */ + void decrement(); + + /** Compare two iterators for equality. */ + bool operator==(const ConstIterator& r) const + { + return (tree == r.tree) && (node == r.node); + } + /** Compare two iterators for non-equality. */ + bool operator!=(const ConstIterator& r) const + { + return !((*this)==r); + } + + // We get comparison with Iterator for free due to + // conversion constructor. + + protected: + /** Get the node pointed to by this iterator. */ + const SplayTree::node* getNode() const { return node; } + + private: + const SplayTree* tree; + // Typically node points to a node within the tree, but + // the value NULL is special and indicates the STL "end()". + const SplayTree::node* node; + + // Standard copy constructor / destructors may be used. + }; + + /** Iterator class for SplayTree. + * + * Acts as a STL reverse_iterator. + * + * Same as iterator except with increment/decrement reversed. + */ + class RIterator : public Iterator + { + public: + RIterator(SplayTree* t = NULL, + SplayTree::node* n = NULL) : + Iterator(t, n) {}; + + void increment() { Iterator::decrement(); }; + void decrement() { Iterator::increment(); }; + }; + + /** Iterator class for SplayTree. + * + * Acts as a STL const_reverse_iterator. + * + * Same as const_iterator except with increment/decrement reversed. + */ + class ConstRIterator : public ConstIterator + { + public: + ConstRIterator(const SplayTree* t = NULL, + const SplayTree::node* n = NULL) : + ConstIterator(t, n) {}; + + void increment() { ConstIterator::decrement(); }; + void decrement() { ConstIterator::increment(); }; + }; + + // Inline implementations of iterator / const_iterator functions. + inline Iterator SplayTree::begin() + { return Iterator(this, front()); }; + inline ConstIterator SplayTree::begin() const + { return ConstIterator(this, front()); }; + inline Iterator SplayTree::end() + { return Iterator(this, NULL); }; + inline ConstIterator SplayTree::end() const + { return ConstIterator(this, NULL); }; + + // Inline implementations of reverse iterator / const_iterator fns. + inline RIterator SplayTree::rbegin() + { return RIterator(this, back()); }; + inline ConstRIterator SplayTree::rbegin() const + { return ConstRIterator(this, back()); }; + inline RIterator SplayTree::rend() + { return RIterator(this, NULL); }; + inline ConstRIterator SplayTree::rend() const + { return ConstRIterator(this, NULL); }; + + + + }; +}; + +#endif diff --git a/src/include/util/impl/stlmap.H b/src/include/util/impl/stlmap.H new file mode 100644 index 000000000..bed6674b7 --- /dev/null +++ b/src/include/util/impl/stlmap.H @@ -0,0 +1,651 @@ +// IBM_PROLOG_BEGIN_TAG +// This is an automatically generated prolog. +// +// $Source: src/include/util/impl/stlmap.h $ +// +// IBM CONFIDENTIAL +// +// COPYRIGHT International Business Machines Corp. 2012 +// +// p1 +// +// Object Code Only (OCO) source materials +// Licensed Internal Code Source Materials +// IBM HostBoot Licensed Internal Code +// +// The source code for this program is not published or other- +// wise divested of its trade secrets, irrespective of what has +// been deposited with the U.S. Copyright Office. +// +// Origin: 30 +// +// IBM_PROLOG_END + +#ifndef __UTIL_IMPL_STLMAP_H +#define __UTIL_IMPL_STLMAP_H + +/** @file stlmap.H + * Implementation details of the std::map class. + * + * See <map> (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 <util/impl/splaytree.H> +#include <utility> +#include <util/traits/remove_const.H> + +#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 <typename Key, typename T, typename Compare> class Map; + + /** Template class to form a redirection from the Splay-Tree + * iterators and the required STL constructs. + * + * The map iterators are bidirectional. + */ + template <typename T, typename Itr> + 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 <typename S, typename Itr2> + friend class GenericIterator; + template <typename Key, typename S, typename Compare> + 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 <typename Itr2> + GenericIterator(const GenericIterator<T,Itr2>& r) : + Itr((Itr2&) r) {} + + /** Prefix Increment */ + GenericIterator<T, Itr>& operator++() + { + Itr::increment(); + return *this; + } + /** Postfix Increment */ + GenericIterator<T, Itr> operator++(int) + { + GenericIterator<T, Itr> t = *this; + Itr::increment(); + return t; + } + /** Prefix Decrement */ + GenericIterator<T, Itr>& operator--() + { + Itr::decrement(); + return *this; + } + /** Postfix Decrement */ + GenericIterator<T, Itr> operator--(int) + { + GenericIterator<T, Itr> t = *this; + Itr::decrement(); + return t; + } + + /** Dereference Operator */ + reference operator*() + { + return reinterpret_cast<__UTIL_SPLAYTREE_NS::Node<T>*>( + const_cast<__UTIL_SPLAYTREE_NS::Node<const void*>*>( + (Itr::getNode())))->data_T(); + } + /** Pointer Operator */ + pointer operator->() + { + return &reinterpret_cast<__UTIL_SPLAYTREE_NS::Node<T>*>( + const_cast<__UTIL_SPLAYTREE_NS::Node<const void*>*>( + (Itr::getNode())))->data_T(); + } + + /** Equality Comparison operator */ + bool operator==(const GenericIterator<T,Itr>& r) const + { + return Itr::operator==(r); + } + /** Non-equality Comparison operator */ + bool operator!=(const GenericIterator<T,Itr>& 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 <typename T> + struct Iterator : + public GenericIterator<T, __UTIL_SPLAYTREE_NS::Iterator> + + { + typedef GenericIterator<T, __UTIL_SPLAYTREE_NS::Iterator> + 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 <typename Key, typename S, typename Compare> + friend class Map; + + protected: + Iterator(__UTIL_SPLAYTREE_NS::Iterator r) : + iterator(r) {}; + + }; + + /** Constant Forward iterator version of GenericIterator */ + template <typename T> + struct ConstIterator : + public GenericIterator<T, __UTIL_SPLAYTREE_NS::ConstIterator> + { + typedef GenericIterator<T, __UTIL_SPLAYTREE_NS::ConstIterator> + 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<T>& r) : iterator(r) {}; + + template <typename Key, typename S, typename Compare> + friend class Map; + + protected: + ConstIterator(__UTIL_SPLAYTREE_NS::ConstIterator r) : + iterator(r) {}; + }; + + /** Reverse iterator version of GenericIterator */ + template <typename T> + struct RIterator : + public GenericIterator<T, __UTIL_SPLAYTREE_NS::RIterator> + { + typedef GenericIterator<T, __UTIL_SPLAYTREE_NS::RIterator> + 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 <typename Key, typename S, typename Compare> + friend class Map; + + protected: + RIterator(__UTIL_SPLAYTREE_NS::RIterator r) : + iterator(r) {}; + }; + + /** Constant Reverse iterator version of GenericIterator */ + template <typename T> + struct ConstRIterator : + public GenericIterator<const T, __UTIL_SPLAYTREE_NS::ConstRIterator> + { + typedef GenericIterator<const T, + __UTIL_SPLAYTREE_NS::ConstRIterator> + 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<T>& r) : iterator(r) {}; + + template <typename Key, typename S, typename Compare> + 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 <typename Key, typename T, typename Compare> + class Map + { + public: + // Standard STL types. + typedef Key key_type; + typedef T data_type; + typedef std::pair<const Key, T> 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<value_type> iterator; + typedef ConstIterator<value_type> const_iterator; + typedef RIterator<value_type> reverse_iterator; + typedef ConstRIterator<value_type> const_reverse_iterator; + + protected: + // Internal types for code read-ability. + typedef Map<Key, T, Compare> _Self; + typedef std::pair<Key, T> _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<Key,T,Compare>& 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<iterator,bool> result = insert(value_type(k,T())); + return (result.first)->second; + } + + std::pair<iterator,bool> insert(const value_type& x) + { + _Tree::node* n = NULL; + + if (iv_tree.insert_by_value(makeSplayTreeValue(x), n)) + { + return make_pair(iterator(_TreeItr(&iv_tree, n)), + false); + } + else + { + reinterpret_cast<_Node*>(n)->data_T().second = x.second; + return make_pair(iterator(_TreeItr(&iv_tree, n)), + true); + } + + } + + 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 <typename InputIterator> + 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<Key, T, Compare>& 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<iterator,iterator> + equal_range( const key_type& k) + { + return make_pair(lower_bound(k),upper_bound(k)); + } + + std::pair<const_iterator, const_iterator> + 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<key,value>*)(&k - (distance pair<key,value> to + * pair<key,value>.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) + { + typename Util::Traits::remove_const<key_type*>::type key = + const_cast<typename + Util::Traits::remove_const<key_type*>::type>(&k); + + value_type* unused = NULL; + const size_t offset = + reinterpret_cast<const char*>(&unused->first) - + reinterpret_cast<const char*>(unused); + + return reinterpret_cast<const void**>( + reinterpret_cast<char*>(key) - offset); + } + + /** + * Utility function to convert a pair<key,value> into a + * SplayTree "value". + * + * This is a fairly straight-forward cast since no address + * translation is necessary. + */ + const void** makeSplayTreeValue(const value_type& x) + { + return reinterpret_cast<const void**>( + const_cast<value_type*>(&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<const char*>(&unused->iv_tree) - + reinterpret_cast<const char*>(unused); + + return reinterpret_cast<const _Self*>( + reinterpret_cast<const char*>(t) - offset)-> + compare( + reinterpret_cast<const _Node*>(n1)->data_T().first, + reinterpret_cast<const _Node*>(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<const _Node*>(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 diff --git a/src/include/util/traits/remove_const.H b/src/include/util/traits/remove_const.H new file mode 100644 index 000000000..420a7775b --- /dev/null +++ b/src/include/util/traits/remove_const.H @@ -0,0 +1,71 @@ +// IBM_PROLOG_BEGIN_TAG +// This is an automatically generated prolog. +// +// $Source: src/include/util/traits/remove_const.H $ +// +// IBM CONFIDENTIAL +// +// COPYRIGHT International Business Machines Corp. 2012 +// +// p1 +// +// Object Code Only (OCO) source materials +// Licensed Internal Code Source Materials +// IBM HostBoot Licensed Internal Code +// +// The source code for this program is not published or other- +// wise divested of its trade secrets, irrespective of what has +// been deposited with the U.S. Copyright Office. +// +// Origin: 30 +// +// IBM_PROLOG_END + +#ifndef __UTIL_TRAITS_REMOVE_CONST +#define __UTIL_TRAITS_REMOVE_CONST + +/** @file remove_const.H + * Creates a template class remove_const who's type typedef will strip the + * "const" from another type. + * + * Example: + * remove_const<const int>::type == int + * remove_const<int>::type == int + * remove_const<const int*>::type == int* + * + */ + +namespace Util +{ + namespace Traits + { + template <typename T> struct remove_const; + + template <typename T> + struct remove_const<const T> + { + typedef T type; + }; + + template <typename T> + struct remove_const<const T*> + { + typedef T* type; + }; + + template <typename T> + struct remove_const<const T&> + { + typedef T& type; + }; + + template <typename T> + struct remove_const + { + typedef T type; + }; + + }; +}; + +#endif diff --git a/src/lib/makefile b/src/lib/makefile index 7997189f8..b7cd3196e 100644 --- a/src/lib/makefile +++ b/src/lib/makefile @@ -25,6 +25,6 @@ ROOTPATH = ../.. OBJS = string.o string_ext.o stdlib.o ctype.o assert.o stdio.o math.o OBJS += syscall_stub.o syscall_task.o syscall_msg.o OBJS += syscall_mmio.o syscall_time.o sync.o syscall_misc.o -OBJS += syscall_mm.o cxxtest_data.o +OBJS += syscall_mm.o splaytree.o cxxtest_data.o include ${ROOTPATH}/config.mk diff --git a/src/lib/splaytree.C b/src/lib/splaytree.C new file mode 100644 index 000000000..3ce271344 --- /dev/null +++ b/src/lib/splaytree.C @@ -0,0 +1,514 @@ +// IBM_PROLOG_BEGIN_TAG +// This is an automatically generated prolog. +// +// $Source: src/lib/splaytree.C $ +// +// IBM CONFIDENTIAL +// +// COPYRIGHT International Business Machines Corp. 2012 +// +// p1 +// +// Object Code Only (OCO) source materials +// Licensed Internal Code Source Materials +// IBM HostBoot Licensed Internal Code +// +// The source code for this program is not published or other- +// wise divested of its trade secrets, irrespective of what has +// been deposited with the U.S. Copyright Office. +// +// Origin: 30 +// +// IBM_PROLOG_END + +#include <util/impl/splaytree.H> +#include <builtins.h> + +/** @file splaytree.C + * Implementation of the Util::__Util_SplayTree_Impl::SplayTree class. + */ + +namespace Util +{ + namespace __Util_SplayTree_Impl + { + + SplayTree::SplayTree(SplayTree::comparator comp, + SplayTree::copier copy, + SplayTree::deleter del) : + compare_functor(comp), + copy_functor(copy), + delete_functor(del) + { + } + + SplayTree::SplayTree(const SplayTree& t) + { + (*this) = t; + } + + SplayTree::~SplayTree() + { + this->clear(); + } + + SplayTree& SplayTree::operator=(const SplayTree& t) + { + this->clear(); + + compare_functor = t.compare_functor; + copy_functor = t.copy_functor; + delete_functor = t.delete_functor; + + insert_range(t.front(), NULL); + if (likely(NULL != header.child[LEFT])) + { + splay(header.child[LEFT]); + } + + return *this; + } + + void SplayTree::insert(node* n) + { + if (unlikely(header.parent == NULL)) // First element. + { + header.parent = header.child[LEFT] = header.child[RIGHT] = n; + n->parent = n->child[LEFT] = n->child[RIGHT] = NULL; + } + else // Not first element. + { + // Find place to insert node and insert it. + node* insert_location = header.parent; + __find(insert_location, n); + __insert(insert_location, n); + + // Fix up header nodes. + header.child[LEFT] = leftmost(header.child[LEFT]); + header.child[RIGHT] = rightmost(header.child[RIGHT]); + + // Splay new node. + splay(n); + } + + // Increment size count. + (header_n()->data_T())++; + } + + void SplayTree::insert_range(const node* n1, const node* n2) + { + while(n1 != n2) + { + insert(copy_functor(n1)); + n1 = successor(n1); + } + } + + void SplayTree::remove(node* n) + { + // Fix up left-most and right-most node pointers if deleting + // them. We'll fix up the root in the node removal itself. + if (unlikely(header.child[LEFT] == n)) + { + header.child[LEFT] = successor(n); + } + if (unlikely(header.child[RIGHT] == n)) + { + header.child[RIGHT] = predecessor(n); + } + + // Decrement size count. + (header_n()->data_T())--; + + // Find node to splice out of the tree. + // If n has one or no child, splice itself out, otherwise the + // successor. + node* y = ((!n->child[LEFT]) || (!n->child[RIGHT])) ? + n : successor(n); + + // Find the subtree of y and link it with y's parent. + node* x = y->child[LEFT] ? y->child[LEFT] : y->child[RIGHT]; + if (likely(NULL != x)) + { + x->parent = y->parent; + } + if (unlikely(!y->parent)) + { + // Fix root. + header.parent = x; + } + else + { + y->parent->child[direction(y->parent, y)] = x; + } + + // Replace n with y. + if (likely(y != n)) + { + y->parent = n->parent; + if (y->parent) + { + y->parent->child[direction(y->parent, n)] = y; + } + + y->child[LEFT] = n->child[LEFT]; + if (y->child[LEFT]) + { + y->child[LEFT]->parent = y; + } + + y->child[RIGHT] = n->child[RIGHT]; + if (y->child[RIGHT]) + { + y->child[RIGHT]->parent = y; + } + + // Splay y up to the root. + splay(y); + } + } + + bool SplayTree::find_hint(node* n, node*& hint) const + { + if (unlikely(NULL == header.parent)) + { + return false; + } + + hint = header.parent; + + bool found = __find(hint, n); + + // Splay hint up the tree to make future searches quicker. + if (likely(NULL != hint)) + { + splay(hint); + } + + return found; + } + + void SplayTree::clear() + { + node* n = front(); + while(n) + { + node* temp = n; + n = successor(n); + remove(temp); + delete_functor(temp); + } + } + + void SplayTree::swap(SplayTree& tree) + { + node temp(header); + header = tree.header; + tree.header = temp; + } + + bool SplayTree::insert_by_value(const void** v, node*& n) + { + n = find_by_value(v); + + if (unlikely(NULL != n)) + { + return false; + } + else + { + n = copy_functor(node::convertToNode(v)); + insert(n); + return true; + } + } + + size_t SplayTree::remove_by_value(const void** v) + { + if (unlikely(NULL == header.parent)) + { + return 0; + } + + node* v_node = header.parent; + if (likely(__find(v_node, node::convertToNode(v)))) + { + remove(v_node); + delete_functor(v_node); + return 1; + } + return 0; + } + + bool SplayTree::find_hint_by_value(const void** v, node*& hint) const + { + return find_hint(node::convertToNode(v), hint); + } + + SplayTree::node* SplayTree::find_by_value(const void** v) const + { + node* n = NULL; + if (find_hint_by_value(v, n)) + { + return n; + } + else + { + return NULL; + } + } + + SplayTree::node* SplayTree::lower_bound_by_value(const void** v) const + { + node* n = NULL; + node* v_n = node::convertToNode(v); + + if (find_hint(v_n, n) || (NULL == n)) + { + return n; + } + else + { + if (-1 == compare_functor(this, n, v_n)) + { + return successor(n); + } + else + { + return n; + } + } + } + + SplayTree::node* SplayTree::upper_bound_by_value(const void** v) const + { + node* n = NULL; + node* v_n = node::convertToNode(v); + + if (find_hint(v_n, n)) + { + return successor(n); + } + else if (NULL == n) + { + return NULL; + } + else + { + if (-1 == compare_functor(this, n, v_n)) + { + return successor(n); + } + else + { + return n; + } + } + } + + + const SplayTree::node* SplayTree::predecessor(const node* n) const + { + // If left child, predecessor is just the largest of the left + // subtree. + if (likely(NULL != n->child[LEFT])) + { + return rightmost(n->child[LEFT]); + } + + // Else, need to work up the tree to find predecessor. + const node* y = n->parent; + while ((NULL != y) && (n == y->child[LEFT])) + { + n = y; + y = y->parent; + } + + return y; + } + + const SplayTree::node* SplayTree::successor(const node* n) const + { + // If right child, predecessor is just the smallest of the right + // subtree. + if (likely(NULL != n->child[RIGHT])) + { + return leftmost(n->child[RIGHT]); + } + + // Else, need to work up the tree to find successor. + const node* y = n->parent; + while ((NULL != y) && (n == y->child[RIGHT])) + { + n = y; + y = y->parent; + } + + return y; + } + + void SplayTree::rotate(node* n, DIRECTION d) const + { + // Get parent node. + node* p = n->parent; + + // Link n's d-subtree into p. + p->child[!d] = n->child[d]; + if (likely(NULL != n->child[d])) + { + n->child[d]->parent = p; + } + + // Link p's parent to n. + n->parent = p->parent; + if (unlikely(!p->parent)) + { + header.parent = n; + } + else + { + p->parent->child[direction(p->parent, p)] = n; + } + + // Put p onto d-subtree of n. + p->parent = n; + n->child[d] = p; + + } + + void SplayTree::splay(node* n) const + { + // There are three splay operations. "zig", "zig-zig" and + // "zig-zag" based on the shape of the links between child, parent + // and grand-parent. + + if (unlikely(!n->parent)) // This is the root node already. + { + return; + } + + if (unlikely(!n->parent->parent)) // "zig" since no grand-parent. + { + // Rotate n into parent's location. + rotate(n, !direction(n->parent, n)); + } + else if (direction(n->parent, n) == + direction(n->parent->parent, n->parent)) // "zig-zig" + { + // Rotate parent into grand-parent first, then rotate + // n into parent. + rotate(n->parent, !direction(n->parent->parent, n->parent)); + rotate(n, !direction(n->parent, n)); + + // Continue splay. + splay(n); + } + else // "zig-zag" + { + // Rotate n into parent, then n into grand-parent. + rotate(n, !direction(n->parent, n)); + // Note: grand-parent is now parent due to first rotate. + rotate(n, !direction(n->parent, n)); + + // Continue splay. + splay(n); + } + } + + + void SplayTree::__insert(node* t, node* n) + { + node*& child = (0 > (*compare_functor)(this, n, t)) ? + t->child[LEFT] : t->child[RIGHT]; + + if (likely(NULL == child)) // Assumption is the subtree hint is + // correct, so this should be NULL. + { + // Link node into "child" slot. + child = n; + n->parent = t; + } + else + { + // Subtree hint was wrong, recurse tree. + __insert(n, child); + } + } + + bool SplayTree::__find(node*& t, node* n) const + { + int compare = (*compare_functor)(this, n, t); + + if (unlikely(compare == 0)) // Node matches, return true. + { + return true; + } + + node* child = (0 > compare) ? t->child[LEFT] : t->child[RIGHT]; + + if (unlikely(NULL == child)) // No more children, no match. + { + return false; + } + else // Recurse to child. + { + t = child; + return __find(t, n); + } + } + + void Iterator::increment() + { + if (NULL == node) + { + node = tree->front(); // This causes "begin() == ++end()" but + // is necessary so that --rend() becomes + // a reverse iterator to begin(). + } + else + { + node = tree->successor(node); + } + }; + + void Iterator::decrement() + { + if (NULL == node) + { + node = tree->back(); + } + else + { + node = tree->predecessor(node); + } + } + + void ConstIterator::increment() + { + if (NULL == node) + { + node = tree->front(); // This causes "begin() == ++end()" but + // is necessary so that --rend() becomes + // a reverse iterator to begin(). + } + else + { + node = tree->successor(node); + } + } + + void ConstIterator::decrement() + { + if (NULL == node) + { + node = tree->back(); + } + else + { + node = tree->predecessor(node); + } + } + + + }; +}; diff --git a/src/makefile b/src/makefile index d7edfbf71..bf642a119 100644 --- a/src/makefile +++ b/src/makefile @@ -29,7 +29,7 @@ EXTRA_LIDS = dslid BASE_OBJECTS = console.o spinlock.o string.o string_ext.o stdlib.o ctype.o \ assert.o stdio.o builtins.o vfs_init.o heapmgr.o pagemgr.o \ - math.o barrier.o idebug.o intmsghandler.o idletask.o + math.o barrier.o idebug.o intmsghandler.o idletask.o splaytree.o ifdef HOSTBOOT_PROFILE BASE_OBJECTS += gcov.o diff --git a/src/usr/testcore/lib/stltest.H b/src/usr/testcore/lib/stltest.H index ddd2bb46e..b9a16d927 100644 --- a/src/usr/testcore/lib/stltest.H +++ b/src/usr/testcore/lib/stltest.H @@ -97,7 +97,16 @@ class STLTest : public CxxTest::TestSuite } mymap2 = mymap; // map::operator= + if (mymap2.size() != mymap.size()) + { + TS_FAIL("map::operator= test failed"); + } + mymap3.insert(mymap2.begin(),mymap2.end()); + if (mymap3.size() != mymap2.size()) + { + TS_FAIL("map::insert(itr,itr) test failed"); + } mymap.erase(mymap.begin(),mymap.end()); //map::erase(itr,itr) @@ -168,6 +177,34 @@ class STLTest : public CxxTest::TestSuite } --i; } + + // Test copy constructor. + std::map<V,V> mymap4(mymap); + + if (mymap.size() != mymap4.size()) + { + TS_FAIL("stl::map fail Copy constructor size test."); + } + + // Test range constructor. + std::map<V,V> mymap5(mymap.begin(), mymap.end()); + + if (mymap.size() != mymap5.size()) + { + TS_FAIL("stl::map fail Range constructor size test."); + } + + // Test erase by key. + mymap5.erase(v2); + if (mymap5.end() != mymap5.find(v2)) + { + TS_FAIL("std::map fail Erase by iterator test."); + } + if (mymap.size() != (mymap5.size() + 1)) + { + TS_FAIL("std::map fail Erase by iterator size test."); + } + } |
