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>

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.");
+            }
+
         }