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>

4 files changed, 1482 insertions, 0 deletions

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