summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorPatrick Williams <iawillia@us.ibm.com>2012-03-06 14:46:28 -0600
committerA. Patrick Williams III <iawillia@us.ibm.com>2012-03-29 21:31:40 -0500
commitdf3648d7cd33ee146de3041d3f0d93a713075e26 (patch)
tree118a6a7502b65beab3619e20dab076eb9bde7b0d /src
parent05cf6b567b9dd13d7ac763cc4b2740cd7766508d (diff)
downloadtalos-hostboot-df3648d7cd33ee146de3041d3f0d93a713075e26.tar.gz
talos-hostboot-df3648d7cd33ee146de3041d3f0d93a713075e26.zip
Improve std::map by using a SplayTree container.
Originally std::map was implemented as a linked list. Some of the maps in PORE and PRD code will be big enough that this is very inefficient. Converted std::map to a binary search tree implementation based on the Splay-Tree algorithm. RTC: 34071 Change-Id: If77c017f5d95920f8010991e7f087cbe571ca2e9 Reviewed-on: http://gfw160.austin.ibm.com:8080/gerrit/790 Tested-by: Jenkins Server Reviewed-by: MIKE J. JONES <mjjones@us.ibm.com> Reviewed-by: Douglas R. Gilbert <dgilbert@us.ibm.com> Reviewed-by: Bradley W. Bishop <bradleyb@us.ibm.com> Reviewed-by: A. Patrick Williams III <iawillia@us.ibm.com>
Diffstat (limited to 'src')
-rw-r--r--src/include/functional7
-rw-r--r--src/include/map358
-rw-r--r--src/include/util/algorithm.H57
-rw-r--r--src/include/util/impl/splaytree.H703
-rw-r--r--src/include/util/impl/stlmap.H651
-rw-r--r--src/include/util/traits/remove_const.H71
-rw-r--r--src/lib/makefile2
-rw-r--r--src/lib/splaytree.C514
-rw-r--r--src/makefile2
-rw-r--r--src/usr/testcore/lib/stltest.H37
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.");
+ }
+
}
OpenPOWER on IntegriCloud