c++ stl algorithm and iterator support

Change-Id: I170e3bb96651dfedc77a273d2d14a11c4dd002ad
Reviewed-on: http://gfw160.aus.stglabs.ibm.com:8080/gerrit/21159
Tested-by: Jenkins Server
Reviewed-by: Sachin Gupta <sgupta2m@in.ibm.com>
Reviewed-by: Gregory S. Still <stillgs@us.ibm.com>

12 files changed, 1718 insertions, 2 deletions

diff --git a/include/std/algorithm b/include/std/algorithm
new file mode 100644
index 00000000..e47671fd
--- /dev/null
+++ b/include/std/algorithm
@@ -0,0 +1,762 @@
+/* IBM_PROLOG_BEGIN_TAG                                                   */
+/* This is an automatically generated prolog.                             */
+/*                                                                        */
+/* $Source: src/include/algorithm $                                       */
+/*                                                                        */
+/* OpenPOWER HostBoot Project                                             */
+/*                                                                        */
+/* Contributors Listed Below - COPYRIGHT 2011,2014                        */
+/* [+] International Business Machines Corp.                              */
+/*                                                                        */
+/*                                                                        */
+/* Licensed under the Apache License, Version 2.0 (the "License");        */
+/* you may not use this file except in compliance with the License.       */
+/* You may obtain a copy of the License at                                */
+/*                                                                        */
+/*     http://www.apache.org/licenses/LICENSE-2.0                         */
+/*                                                                        */
+/* Unless required by applicable law or agreed to in writing, software    */
+/* distributed under the License is distributed on an "AS IS" BASIS,      */
+/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        */
+/* implied. See the License for the specific language governing           */
+/* permissions and limitations under the License.                         */
+/*                                                                        */
+/* IBM_PROLOG_END_TAG                                                     */
+#ifndef ALGORITHM
+#define ALGORITHM
+
+#include <iterator>
+#include <util/impl/qsort.H>
+#include <type_traits>
+
+#ifdef __cplusplus
+namespace std
+{
+    /**
+     * Copy a range of elements
+     * @param[in] first InputIterator to the initial position in the source sequence.
+     * @param[in] last  InputIterator to last position + 1 in the source sequence.
+     * @param[in] result OutputIterator to initial position in the destination sequence.
+     * @return an iterator to the last element in the destination range
+     * @note If both ranges overlap in such a way that result points to an elmenent in the source
+     * range then fuction copy_backward should be used.
+     */
+    template <class InputIterator, class OutputIterator>
+    inline OutputIterator
+    copy (InputIterator first, InputIterator last, OutputIterator result )
+    {
+        while(first!=last)
+        {
+            *result = *first;
+            ++result;
+            ++first;
+        }
+        return result;
+    }
+
+    /**
+     * Copy a range of elements backwards
+     * @param[in] first Bidirectional iterator to the initial source position
+     * @param[in] last  Bidirectional iterator to the final source position + 1
+     * @param[in] result Bidirectional iterator to end of the destination sequence + 1.
+     * @return an iterator to the first element in the destination sequence.
+     * @note If both ranges overlap in such a way that result points to an element in the  source
+     * range, the function copy should be used instead.
+     */
+    template <class BidirectionalIterator1, class BidirectionalIterator2>
+    inline BidirectionalIterator2 
+    copy_backward (  BidirectionalIterator1 first,
+                     BidirectionalIterator1 last,
+                     BidirectionalIterator2 result )
+    {
+        while(last!=first)
+        {
+            --result;
+            --last;
+            *result = *last;
+        }
+        return result;
+    }
+
+    /**
+     * Exchange values of two objects
+     * @param[in] a reference to an object to be swaped with b
+     * @param[in] b reference to an object to be swaped with a
+     * @note this function may not be an efficient way to swap large objects.
+     */
+    template <class T> 
+        inline void 
+        swap(T& a, T&b )
+    {
+        T c(a);
+        a=b;
+        b=c;
+    }
+
+    /**
+     * Fill a range with value
+     * @param[in] first ForwardIterator to the first position in the source range.
+     * @param[in] last  ForwardIterator to the last position +1 in the source range.
+     * @param[in] value reference to the object used to fill the sequence.
+     */
+    template < class ForwardIterator, class T >
+    inline void
+    fill (ForwardIterator first, ForwardIterator last, const T& value )
+    {
+        while (first != last)
+        {
+            *first = value;
+            ++first;
+        }
+    }
+
+    /**
+     * Fill a sequence with value
+     * @param[in] first OutputIterator to the first position in the sequence.
+     * @param[in] n number of elements in the sequence
+     * @param[in] value reference to the value used to fill the sequence.
+     */
+    template < class OutputIterator, class Size, class T >
+    inline void
+    fill_n( OutputIterator first, Size n, const T& value )
+    {
+        for(; n>0; --n)
+        {
+            *first = value;
+            ++first;
+        }
+    }
+
+    /**
+     * Fill a sequence with a generated value
+     * @param[in] first OutputIterator to the first position in the sequence.
+     * @param[in] n number of elements in the sequence
+     * @param[in] gen functor to create values used to fill the sequence.
+     */
+    template <typename OutputIterator, typename Size, typename Generator>
+    OutputIterator generate_n(OutputIterator first, Size n, Generator gen)
+    {
+        for(; n>0; --n)
+        {
+            *first = gen();
+            ++first;
+        }
+
+        return first;
+    }
+
+    /**
+     * Return the lesser of two arguments
+     * @param[in] a object reference
+     * @param[in] b object reference
+     * @return reference to te lesser object
+     */
+    template <class T>
+    inline const T& 
+    min(const T& a, const T& b)
+    {
+        if( b < a) return b;
+        return a;
+    }
+
+    /**
+     * Return the greater of two arguments
+     * @param[in] a object reference
+     * @param[in] b object reference
+     * @return reference to te greater object
+     */    
+    template <class T>
+    inline const T&
+    max(const T& a, const T& b)
+    {
+        if(a < b) return b;
+        return a;
+    }
+
+    /**
+     * Find the location of an element within a range.
+     * @param[in] first InputIterator to the first position in the range.
+     * @param[in] last  InputIterator to the last position in the range.
+     * @param[in] value Value to use for comparison.
+     *
+     * Returns the first iterator i in the range [first,last) such that
+     *     (*i == value) or else last if no element is found.
+     *
+     * @return An iterator in the range [first,last].  last implies that no
+     *         matching element was found.
+     */
+    template <typename InputIterator, typename EqualityComparable>
+    inline InputIterator
+    find(InputIterator first, InputIterator last,
+         const EqualityComparable& value)
+    {
+        while(first != last)
+        {
+            if ((*first) == value)
+                return first;
+
+            ++first;
+        }
+
+        return last;
+    }
+
+    /**
+     * Find the location of an element within a range.
+     * @param[in] first InputIterator to the first position in the range.
+     * @param[in] last  InputIterator to the last position in the range.
+     * @param[in] pred  Predicate used to compare equality.
+     *
+     * Returns the first iterator i in the range [first,last) such that
+     *     pred(*i) is true or else last if no element is found.
+     *
+     * @return An iterator in the range [first,last].  last implies that no
+     *         matching element was found.
+     */
+    template <typename InputIterator, typename Predicate>
+    inline InputIterator
+    find_if(InputIterator first, InputIterator last,
+            Predicate pred)
+    {
+        while(first != last)
+        {
+            if (pred(*first))
+                return first;
+
+            ++first;
+        }
+
+        return last;
+    }
+
+    /**
+     * Find the minimum element within a range.
+     * @param[in] first - FwdIterator to the first position in the range.
+     * @param[in] last - FwdIterator to the last position in the range.
+     *
+     * Returns the first element (i) such that (*j) < (*i) is false for all
+     * other iterators.
+     *
+     * The iterator last is returned only when the range contains no elements.
+     *
+     * @return An iterator in [first, last) containing the minimum element.
+     *
+     */
+    template <typename FwdIterator>
+    inline FwdIterator min_element(FwdIterator first, FwdIterator last)
+    {
+        if (first == last) return last;
+        FwdIterator e = first++;
+        while(first != last)
+        {
+            if ((*first) < (*e)) 
+            {
+                e = first;
+            }
+            ++first;
+        }
+        return e;
+    }
+
+    /**
+     * Find the minimum element within a range.
+     * @param[in] first - FwdIterator to the first position in the range.
+     * @param[in] last - FwdIterator to the last position in the range.
+     * @param[in] comp - BinaryPredicate used to perform comparison.
+     *
+     * Returns the first element (i) such that comp(*j,*i) is false for all
+     * other iterators.
+     *
+     * The iterator last is returned only when the range contains no elements.
+     *
+     * @return An iterator in [first, last) containing the minimum element.
+     *
+     */
+    template <typename FwdIterator, typename BinaryPredicate>
+    inline FwdIterator min_element(FwdIterator first, FwdIterator last, 
+                                   BinaryPredicate comp)
+    {
+        if (first == last) return last;
+        FwdIterator e = first++;
+        while(first != last)
+        {
+            if (comp((*first),(*e)))
+            {
+                e = first;
+            }
+            ++first;
+        }
+        return e;
+    }
+
+    /**
+     * Find the maximum element within a range.
+     * @param[in] first - FwdIterator to the first position in the range.
+     * @param[in] last - FwdIterator to the last position in the range.
+     *
+     * Returns the first element (i) such that (*i) < (*j) is false for all
+     * other iterators.
+     *
+     * The iterator last is returned only when the range contains no elements.
+     *
+     * @return An iterator in [first, last) containing the minimum element.
+     *
+     */
+    template <typename FwdIterator>
+    inline FwdIterator max_element(FwdIterator first, FwdIterator last)
+    {
+        if (first == last) return last;
+        FwdIterator e = first++;
+        while(first != last)
+        {
+            if ((*e) < (*first)) 
+            {
+                e = first;
+            }
+            ++first;
+        }
+        return e;
+    }
+
+    /**
+     * Find the maximum element within a range.
+     * @param[in] first - FwdIterator to the first position in the range.
+     * @param[in] last - FwdIterator to the last position in the range.
+     * @param[in] comp - BinaryPredicate used to perform comparison.
+     *
+     * Returns the first element (i) such that comp(*i,*j) is false for all
+     * other iterators.
+     *
+     * The iterator last is returned only when the range contains no elements.
+     *
+     * @return An iterator in [first, last) containing the minimum element.
+     *
+     */
+    template <typename FwdIterator, typename BinaryPredicate>
+    inline FwdIterator max_element(FwdIterator first, FwdIterator last, 
+                                   BinaryPredicate comp)
+    {
+        if (first == last) return last;
+        FwdIterator e = first++;
+        while(first != last)
+        {
+            if (comp((*e),(*first)))
+            {
+                e = first;
+            }
+            ++first;
+        }
+        return e;
+    }
+
+
+    /**
+     * Find the element value in an ordered range [first, last].  Specifically,
+     * it returns the first position where value could be inserted without
+     * violating the ordering.
+     *
+     * @param[in] first ForwardIterator to the first position in the range.
+     * @param[in] last  ForwardIterator to the last position in the range.
+     * @param[in] value Value to use for comparison.
+     */
+
+    template <class ForwardIterator, class LessThanComparable>
+    inline ForwardIterator
+    lower_bound ( ForwardIterator first,
+                  ForwardIterator last,
+                  const LessThanComparable& value )
+    {
+        ForwardIterator it;
+        int num = 0x0;
+        int range = std::distance<ForwardIterator>( first,
+                                                    last );
+
+        while( range > 0 )
+        {
+            it = first;
+            num = range / 2;
+            std::advance( it, num );
+
+            if( (*it) < value )
+            {
+                first = ++it;
+                range = (range - (num+1));
+            }
+            else
+            {
+                range = num;
+            }
+        }
+
+        return first;
+    }
+
+    /**
+     * Find the element value in an ordered range [first, last].  Specifically,
+     * it returns the first position where value could be inserted without
+     * violating the ordering.  This is done using the comparison function
+     * parameter that is passed in.
+     *
+     * @param[in] first ForwardIterator to the first position in the range.
+     * @param[in] last  ForwardIterator to the last position in the range.
+     * @param[in] value Value to use for comparison.
+     * @param[in] comp  Function to do the comparison
+     */
+    template <class ForwardIterator, class T, class StrictWeakOrdering>
+    inline ForwardIterator
+    lower_bound ( ForwardIterator first,
+                  ForwardIterator last,
+                  const T& value,
+                  StrictWeakOrdering comp )
+    {
+        ForwardIterator it;
+        int num = 0x0;
+        int range = std::distance<ForwardIterator>( first,
+                                                    last );
+
+        while( range > 0 )
+        {
+            it = first;
+            num = range / 2;
+            std::advance( it, num );
+
+            if( comp( (*it), value ) )
+            {
+                first = ++it;
+                range = (range - (num+1));
+            }
+            else
+            {
+                range = num;
+            }
+        }
+
+        return first;
+    }
+
+    /**
+     * Apply a functor to each element in a range.
+     *
+     * Applies functor 'f' to each element in [first, last).
+     *
+     * @param[in] first - The beginning of the range.
+     * @param[in] last - The end of the range.
+     * @param[in] f - The functor.
+     *
+     * @return The functor after being having been applied.
+     */
+    template <typename InputIterator, typename UnaryFunction>
+    UnaryFunction for_each(InputIterator first, InputIterator last,
+                           UnaryFunction f)
+    {
+        while(first != last)
+        {
+            f(*first);
+            ++first;
+        }
+        return f;
+    }
+
+    /**
+     * Remove a value from a range.
+     *
+     * Removes all instances matching 'value' in the range [first, last)
+     * and returns an iterator to the end of the new range [first, new_last)
+     * where nothing in the new range has 'value'.
+     *
+     * Remove does not decrease the size of the container.
+     *
+     * @param[in] first - The beginning of the range.
+     * @param[in] last - The end of the range.
+     * @param[in] value - The value to remove.
+     *
+     * @return An iterator 'new_last' from [first, new_last).
+     */
+    template <typename ForwardIterator, typename T>
+    ForwardIterator remove(ForwardIterator first, ForwardIterator last,
+                           const T& value)
+    {
+        // Find first match.
+        first = find(first, last, value);
+
+        if (first == last) // No match found, return un-changed 'last'.
+        {
+            return last;
+        }
+
+        // Match was found.  'new_last' is now the first removed element.
+        ForwardIterator new_last = first;
+        ++first;
+
+        // Iterate through all the others.
+        while(first != last)
+        {
+            // If 'first' is a desired value, we need to copy it and move
+            // 'new_last'.
+            if (!(*first == value))
+            {
+                *new_last = *first;
+                ++new_last;
+            }
+
+            ++first;
+        }
+
+        return new_last;
+
+    }
+
+    /**
+     * Remove a value from a range using a predicate.
+     *
+     * Removes all instances pred(*i) is true in the range [first, last)
+     * and returns an iterator to the end of the new range [first, new_last)
+     * where nothing in the new range has pred(*i) true.
+     *
+     * Remove does not decrease the size of the container.
+     *
+     * @param[in] first - The beginning of the range.
+     * @param[in] last - The end of the range.
+     * @param[in] pred - The predicate to use for comparison.
+     *
+     * @return An iterator 'new_last' from [first, new_last).
+     */
+    template <typename ForwardIterator, typename Predicate>
+    ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
+                              Predicate pred)
+    {
+        // Find first match.
+        first = find_if(first, last, pred);
+
+        if (first == last) // No match found, return un-changed 'last'.
+        {
+            return last;
+        }
+
+        // Match was found.  'new_last' is now the first removed element.
+        ForwardIterator new_last = first;
+        ++first;
+
+        // Iterate through all the others.
+        while(first != last)
+        {
+            // If 'first' is a desired value, we need to copy it and move
+            // 'new_last'.
+            if (!(pred(*first)))
+            {
+                *new_last = *first;
+                ++new_last;
+            }
+
+            ++first;
+        }
+
+        return new_last;
+
+    }
+
+    /**
+     * Removes consecutive duplicate entries from a range.
+     *
+     * Removes all instances where (*i == *(i-1)) in the range [first, last)
+     * and returns an iterator to the end of the new range [first, new_last)
+     * where nothing in the new range is a consecutive duplicate.
+     *
+     * Unique does not decrease the size of the container.
+     *
+     * @param[in] first - The beginning of the range.
+     * @param[in] last - The end of the range.
+     *
+     * @return An iterator 'new_last' from [first, new_last).
+     *
+     */
+    template <typename ForwardIterator>
+    ForwardIterator unique(ForwardIterator first, ForwardIterator last)
+    {
+        // Trivial case of 0 items, return.
+        if (first == last) return last;
+
+        // The algorithm keeps 3 iterators 'prev', 'first', and 'last'.  The
+        // 'prev' iterator is always the last instance to be kept.  'last' is
+        // the end of the original range.  'first' is kept to be the item
+        // being compared.
+
+        // Point 'prev' at the first element of the range since first item is 
+        // a keeper.
+        ForwardIterator prev = first;
+        ++first;
+
+        while (first != last)
+        {
+            // If the two items are not the same, we found a new item to keep.
+            if (!(*prev == *first))
+            {
+                // Increment the "keep slot".
+                ++prev;
+
+                // If the "keep slot" is not the element being compared, we
+                // need to move the new item down to that keep slot.
+                if (prev != first)
+                {
+                    *prev = *first;
+                }
+            }
+
+            // Advance to the next element.
+            ++first;
+        }
+
+        // 'prev' points to the last item to be kept.  Increment it to make 
+        // it point to the one past.
+        ++prev;
+        return prev;
+    }
+
+    /**
+     * Removes consecutive duplicate entries from a range by predicate.
+     *
+     * Removes all instances where pred(*i,*(i-1)) is true in the
+     * range [first, last) and returns an iterator to the end of the new 
+     * range [first, new_last) where nothing in the new range is a 
+     * consecutive duplicate.
+     *
+     * Unique does not decrease the size of the container.
+     *
+     * @param[in] first - The beginning of the range.
+     * @param[in] last - The end of the range.
+     * @param[in] pred - The predicate.
+     *
+     * @return An iterator 'new_last' from [first, new_last).
+     *
+     */
+    template <typename ForwardIterator, typename BinaryPredicate>
+    ForwardIterator unique(ForwardIterator first, ForwardIterator last,
+                           BinaryPredicate pred)
+    {
+        // Trivial case of 0 items, return.
+        if (first == last) return last;
+
+        // The algorithm keeps 3 iterators 'prev', 'first', and 'last'.  The
+        // 'prev' iterator is always the last instance to be kept.  'last' is
+        // the end of the original range.  'first' is kept to be the item
+        // being compared.
+
+        // Point 'prev' at the first element of the range since first item is 
+        // a keeper.
+        ForwardIterator prev = first;
+        ++first;
+
+        while (first != last)
+        {
+            // If the two items are not the same, we found a new item to keep.
+            if (!(pred(*prev,*first)))
+            {
+                // Increment the "keep slot".
+                ++prev;
+
+                // If the "keep slot" is not the element being compared, we
+                // need to move the new item down to that keep slot.
+                if (prev != first)
+                {
+                    *prev = *first;
+                }
+            }
+
+            // Advance to the next element.
+            ++first;
+        }
+
+        // 'prev' points to the last item to be kept.  Increment it to make 
+        // it point to the one past.
+        ++prev;
+        return prev;
+    }
+
+    /** Sort a range.
+     *
+     *  Sorts all the elements in [first, last) using such that *i < *(i+1)
+     *  for all items in the range.
+     *
+     *  @param[in] first - The beginning of the range.
+     *  @param[in] last - The end of the range.
+     */
+    template <typename RandomAccessIterator>
+    void sort(RandomAccessIterator first, RandomAccessIterator last)
+    {
+        Util::__Util_QSort_Impl::sort(first, last);
+    }
+
+    /** Sort a range using a predicate
+     *
+     *  Sorts all the elements in [first, last) using such that 
+     *  pred(*i, *(i+1)) is true for all items in the range.
+     *
+     *  @param[in] first - The beginning of the range.
+     *  @param[in] last - The end of the range.
+     *  @param[in] pred - The predicate to use for comparison.
+     */
+    template <typename RandomAccessIterator, typename StrictWeakOrdering>
+    void sort(RandomAccessIterator first, RandomAccessIterator last,
+              StrictWeakOrdering pred)
+    {
+        Util::__Util_QSort_Impl::sort(first, last, pred);
+    }
+
+    /** Transform one sequence into another. 
+     *
+     *  Executes an operator against all elements in [first, last) and writes
+     *  the result to another sequence.
+     *
+     *  @param first - Beginning of the input range.
+     *  @param last - Ending of the input range.
+     *  @param result - Beginning of the output range.
+     *  @param op - The transformation operator.
+     */
+    template <typename InputIterator, typename OutputIterator, 
+              typename UnaryFunction>
+    OutputIterator transform(InputIterator first, InputIterator last,
+                             OutputIterator result, UnaryFunction op)
+    {
+        while (first != last)
+        {
+            *result = op(*first);
+            ++result;
+            ++first;
+        }
+        return result;
+    }
+
+    /** Transform two sequences into another. 
+     *
+     *  Executes an operator against all elements in [first1, last1) along
+     *  with the peer from [first2, ...) and writes the result to 
+     *  another sequence.
+     *
+     *  @param first1 - Beginning of the first input range.
+     *  @param last1 - Ending of the first input range.
+     *  @param first2 - Beginning of the second input range.
+     *  @param result - Beginning of the output range.
+     *  @param op - The transformation operator.
+     */
+    template <typename InputIterator1, typename InputIterator2,
+              typename OutputIterator, typename BinaryFunction>
+    OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
+                             InputIterator2 first2, OutputIterator result, 
+                             BinaryFunction op)
+    {
+        while (first1 != last1)
+        {
+            *result = op(*first1, *first2);
+            ++result;
+            ++first1; ++first2;
+        }
+        return result;
+    }
+
+
+
+};
+#endif
+
+#endif
+/* vim: set filetype=cpp : */
diff --git a/include/std/iterator b/include/std/iterator
new file mode 100644
index 00000000..396e1b59
--- /dev/null
+++ b/include/std/iterator
@@ -0,0 +1,185 @@
+/* IBM_PROLOG_BEGIN_TAG                                                   */
+/* This is an automatically generated prolog.                             */
+/*                                                                        */
+/* $Source: src/include/iterator $                                        */
+/*                                                                        */
+/* OpenPOWER HostBoot Project                                             */
+/*                                                                        */
+/* COPYRIGHT International Business Machines Corp. 2012,2014              */
+/*                                                                        */
+/* Licensed under the Apache License, Version 2.0 (the "License");        */
+/* you may not use this file except in compliance with the License.       */
+/* You may obtain a copy of the License at                                */
+/*                                                                        */
+/*     http://www.apache.org/licenses/LICENSE-2.0                         */
+/*                                                                        */
+/* Unless required by applicable law or agreed to in writing, software    */
+/* distributed under the License is distributed on an "AS IS" BASIS,      */
+/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        */
+/* implied. See the License for the specific language governing           */
+/* permissions and limitations under the License.                         */
+/*                                                                        */
+/* IBM_PROLOG_END_TAG                                                     */
+#ifndef __STL_ITERATOR
+#define __STL_ITERATOR
+
+#include <stdint.h>
+
+#ifdef __cplusplus
+
+#include <util/impl/iterator.h>
+
+namespace std
+{
+
+/** @struct iterator_traits
+ *  Template class defining a mapping typenames to ones defined in an iterator.
+ */
+template <typename Iterator>
+struct iterator_traits
+{
+    typedef typename Iterator::value_type value_type;
+    typedef typename Iterator::difference_type difference_type;
+    typedef typename Iterator::pointer pointer;
+    typedef typename Iterator::reference reference;
+};
+
+/** @struct iterator_traits
+ *  Template specialization of iterator traits for treating pointer types
+ *  as an iterator.
+ */
+template <typename T>
+struct iterator_traits<T*>
+{
+    typedef T value_type;
+    typedef ptrdiff_t difference_type;
+    typedef T* pointer;
+    typedef T& reference;
+};
+
+/** Advance an iterator.
+ *
+ * @param[in] i - The iterator to advance.
+ * @param[in] n - The distance to advance the iterator.
+ *
+ * This function is equivalent to calling (++i) n times.  
+ *
+ * If the iterator supports random access then this function will be 
+ * implemented in linear time with respect to n.
+ * 
+ */
+template <typename InputIterator, typename Distance>
+void advance(InputIterator& i, Distance n)
+{
+    Util::__Util_Iterator_Impl::advance<InputIterator, Distance>(i, n);
+}
+
+/** Determine the distance between two iterators.
+ *
+ *  @param[in] first - The first iterator.
+ *  @param[in] last - The last iterator.
+ *
+ *  @return The distance between the two iterators.
+ *
+ *  The distance between two iterators is the number of times first would
+ *  need to be incremented so that it is equal to last.
+ *
+ *  If the iterator supports random access then this function will be
+ *  implemented in linear time with respect to the distance between the
+ *  two iterators.  A negative distance can only be obtained with random
+ *  access iterators.
+ */
+template <typename InputIterator>
+typename iterator_traits<InputIterator>::difference_type 
+    distance(InputIterator first, InputIterator last)
+{
+    return Util::__Util_Iterator_Impl::distance<
+                InputIterator, 
+                typename iterator_traits<InputIterator>::difference_type>
+        (first, last);
+}
+
+/** A OutputIterator which operates by push_back onto a container.
+ *
+ *  See public std::back_insert_iterator documentation.
+ */
+template <typename BackInsertionSequence>
+class back_insert_iterator
+{
+    public:
+            // Common iterator typedefs.
+        typedef typename BackInsertionSequence::value_type value_type;
+        typedef typename BackInsertionSequence::difference_type difference_type;
+        typedef typename BackInsertionSequence::pointer pointer;
+        typedef typename BackInsertionSequence::reference reference;
+
+            /** Default constructor from a container reference. */
+        back_insert_iterator(BackInsertionSequence& s) : sequence(s) {};
+            /** Copy constructor.  Reuses container reference. */
+        back_insert_iterator(const back_insert_iterator& i)
+            : sequence(i.sequence) {};
+
+            /** Assignment (copy) operator. */
+        back_insert_iterator& operator=(const back_insert_iterator& i)
+        {
+            sequence = i.sequence;
+            return *this;
+        }
+
+        /** Dereference operator.
+         *
+         *  This is used to make the standard pattern '*i = x' work on
+         *  an iterator.  Since we need to 'push_back' into the 
+         *  container we don't actually return anything except ourself,
+         *  which allows the operator= to be called.
+         */
+        back_insert_iterator& operator*() { return *this; }
+
+        /** Assignment operator.
+         *
+         *  This is the second part of the standard pattern '*i = x'.
+         *
+         *  Adds the value to the container by calling push_back.
+         *
+         *  @param[in] v - The value to insert to the container.
+         */
+        back_insert_iterator& operator=(const value_type& v)
+        {
+            sequence.push_back(v);
+            return *this;
+        }
+
+            /** Preincrement operator - no-op */
+        back_insert_iterator& operator++() { return *this; };
+            /** Postincrement operator - no-op */
+        back_insert_iterator& operator++(int unused) { return *this; };
+
+    private:
+            /** The container to insert into. */
+        BackInsertionSequence& sequence;
+};
+
+/** Create a back_insert_iterator from a container.
+ *
+ *  Utility function to allow back_insert_iterators to be created without
+ *  needing to specify the underlying container type.
+ *
+ *  Example:  Reverse copy elements from one vector into a new vector.
+ *      copy(v.rbegin(), v.rend(), back_inserter(v2));
+ *
+ *  @param[in] s - Sequence to create an iterator for.
+ *  
+ *  @return The back_insert_iterator.
+ */
+template <typename BackInsertionSequence>
+back_insert_iterator<BackInsertionSequence> 
+    back_inserter(BackInsertionSequence& s)
+{
+    return back_insert_iterator<BackInsertionSequence>(s);
+}
+
+}; // namespace std.
+#endif
+
+#endif
+/* vim: set filetype=cpp : */
diff --git a/include/std/new b/include/std/new
new file mode 100755
index 00000000..8fd81bec
--- /dev/null
+++ b/include/std/new
@@ -0,0 +1,40 @@
+/* IBM_PROLOG_BEGIN_TAG                                                   */
+/* This is an automatically generated prolog.                             */
+/*                                                                        */
+/* $Source: src/include/new $                                             */
+/*                                                                        */
+/* OpenPOWER HostBoot Project                                             */
+/*                                                                        */
+/* COPYRIGHT International Business Machines Corp. 2011,2014              */
+/*                                                                        */
+/* Licensed under the Apache License, Version 2.0 (the "License");        */
+/* you may not use this file except in compliance with the License.       */
+/* You may obtain a copy of the License at                                */
+/*                                                                        */
+/*     http://www.apache.org/licenses/LICENSE-2.0                         */
+/*                                                                        */
+/* Unless required by applicable law or agreed to in writing, software    */
+/* distributed under the License is distributed on an "AS IS" BASIS,      */
+/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        */
+/* implied. See the License for the specific language governing           */
+/* permissions and limitations under the License.                         */
+/*                                                                        */
+/* IBM_PROLOG_END_TAG                                                     */
+#ifndef __NEW_H
+#define __NEW_H
+
+#ifdef __cplusplus
+inline
+void *operator new(size_t, void* place)
+{
+    return place;
+}
+
+inline
+void *operator new[](size_t, void* place)
+{
+    return place;
+}
+#endif
+
+#endif
diff --git a/include/std/type_traits b/include/std/type_traits
new file mode 100644
index 00000000..8498a976
--- /dev/null
+++ b/include/std/type_traits
@@ -0,0 +1,63 @@
+#if !defined(_TYPE_TRAITS)
+#define _TYPE_TRAITS
+
+namespace std
+{
+    /// integral_constant
+    template<typename _Tp, _Tp __v>
+        struct integral_constant
+        {
+            static const _Tp                      value = __v;
+            typedef _Tp                           value_type;
+            typedef integral_constant<_Tp, __v>   type;
+        };
+
+    /// typedef for true_type
+    typedef integral_constant<bool, true>     true_type;
+
+    /// typedef for false_type
+    typedef integral_constant<bool, false>    false_type;
+
+    template<typename _Tp, _Tp __v>
+        const _Tp integral_constant<_Tp, __v>::value;
+
+    /// remove_const
+    template<typename _Tp>
+        struct remove_const
+        { typedef _Tp     type; };
+
+    /// remove_volatile
+    template<typename _Tp>
+        struct remove_volatile
+        { typedef _Tp     type; };
+
+    /// remove_cv
+    template<typename _Tp>
+        struct remove_cv
+        {
+            typedef typename
+                remove_const<typename remove_volatile<_Tp>::type>::type     type;
+        };
+
+    template<typename> struct _is_integral_type : public false_type { };
+    template<> struct _is_integral_type<bool>: public integral_constant<bool,true> {};
+    template<> struct _is_integral_type<char>: public integral_constant<bool,true> {};
+    template<> struct _is_integral_type<signed char>: public integral_constant<bool,true> {};
+    template<> struct _is_integral_type<unsigned char>: public integral_constant<bool,true> {};
+    template<> struct _is_integral_type<short>: public integral_constant<bool,true> {};
+    template<> struct _is_integral_type<unsigned short>: public integral_constant<bool,true> {};
+    template<> struct _is_integral_type<int>: public integral_constant<bool,true> {};
+    template<> struct _is_integral_type<unsigned int>: public integral_constant<bool,true> {};
+    template<> struct _is_integral_type<long>: public integral_constant<bool,true> {};
+    template<> struct _is_integral_type<unsigned long>: public integral_constant<bool,true> {};
+    template<> struct _is_integral_type<long long>: public integral_constant<bool,true> {};
+    template<> struct _is_integral_type<unsigned long long>: public integral_constant<bool,true> {};
+
+    /// is_integral
+    template<typename _Tp>
+        struct is_integral
+        : public integral_constant<bool, (_is_integral_type<typename
+                                          remove_cv<_Tp>::type>::value)>
+    { };
+}
+#endif
diff --git a/include/std/util/impl/iterator.h b/include/std/util/impl/iterator.h
new file mode 100644
index 00000000..fdb03145
--- /dev/null
+++ b/include/std/util/impl/iterator.h
@@ -0,0 +1,149 @@
+/* IBM_PROLOG_BEGIN_TAG                                                   */
+/* This is an automatically generated prolog.                             */
+/*                                                                        */
+/* $Source: src/include/util/impl/iterator.h $                            */
+/*                                                                        */
+/* OpenPOWER HostBoot Project                                             */
+/*                                                                        */
+/* Contributors Listed Below - COPYRIGHT 2012,2015                        */
+/* [+] International Business Machines Corp.                              */
+/*                                                                        */
+/*                                                                        */
+/* Licensed under the Apache License, Version 2.0 (the "License");        */
+/* you may not use this file except in compliance with the License.       */
+/* You may obtain a copy of the License at                                */
+/*                                                                        */
+/*     http://www.apache.org/licenses/LICENSE-2.0                         */
+/*                                                                        */
+/* Unless required by applicable law or agreed to in writing, software    */
+/* distributed under the License is distributed on an "AS IS" BASIS,      */
+/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        */
+/* implied. See the License for the specific language governing           */
+/* permissions and limitations under the License.                         */
+/*                                                                        */
+/* IBM_PROLOG_END_TAG                                                     */
+
+#ifndef __UTIL_IMPL_ITERATOR_H
+#define __UTIL_IMPL_ITERATOR_H
+
+/** @file iterator.h
+ *
+ *  Contains the internal implementation details of the stl <iterator> header.
+ */
+
+#include <util/traits/has_plusequals.H>
+#include <util/traits/has_minus.H>
+
+namespace Util
+{
+    namespace __Util_Iterator_Impl
+    {
+
+        /**
+         *  Template definition of an iterator advance functor.
+         */
+        template <typename InputIterator, typename Distance,
+                  bool HasPlusEquals> struct AdvanceImpl;
+
+        /**
+         *  Template specialization of the advance functor for iterators
+         *  which do not support random access.
+         */
+        template <typename InputIterator, typename Distance>
+        struct AdvanceImpl<InputIterator, Distance, false>
+        {
+            static void advance(InputIterator& i, Distance n)
+            {
+                while(n--)
+                    ++i;
+            }
+        };
+
+        /**
+         *  Template specialization of the advance functor for iterators
+         *  which do support random access.
+         */
+        template <typename RandomIterator, typename Distance>
+        struct AdvanceImpl<RandomIterator, Distance, true>
+        {
+            static void advance(RandomIterator& i, Distance n)
+            {
+                i += n;
+            }
+        };
+
+        /**
+         *  Template wrapper function for the iterator advance.
+         *
+         *  Uses the existence of a += operator on the iterator to determine
+         *  if the random-access or non-random-access version should be used.
+         */
+        template <typename InputIterator, typename Distance>
+        void advance(InputIterator& i, Distance n)
+        {
+            AdvanceImpl<InputIterator, Distance,
+                    Util::Traits::has_plusequals<InputIterator,Distance,
+                                                 InputIterator>::value
+                >::advance(i,n);
+        }
+
+        /**
+         *  Template definition of an iterator distance functor.
+         */
+        template <typename InputIterator, typename Distance,
+                  bool HasMinus> struct DistanceImpl;
+
+        /**
+         *  Template specialization of the distance functor for iterators
+         *  which do not support random access.
+         */
+        template <typename InputIterator, typename Distance>
+        struct DistanceImpl<InputIterator, Distance, false>
+        {
+            static Distance distance(InputIterator& first,
+                                     InputIterator& last)
+            {
+                Distance i = 0;
+                while (first != last)
+                {
+                    ++i;
+                    ++first;
+                }
+                return i;
+            }
+        };
+
+        /**
+         *  Template specialization of the distance functor for iterators
+         *  which do support random access.
+         */
+        template <typename RandomIterator, typename Distance>
+        struct DistanceImpl<RandomIterator, Distance, true>
+        {
+            static Distance distance(RandomIterator& first,
+                                     RandomIterator& last)
+            {
+                return last - first;
+            }
+        };
+
+        /**
+         *  Template wrapper function for the iterator distance.
+         *
+         *  Uses the existence of a - operator on the iterator to determine
+         *  if the random-access or non-random-access version should be used.
+         */
+        template <typename InputIterator, typename Distance>
+        Distance distance(InputIterator& first,
+                          InputIterator& last)
+        {
+            return DistanceImpl<InputIterator, Distance,
+                        Util::Traits::has_minus<InputIterator, InputIterator,
+                                                Distance>::value
+                    >::distance(first,last);
+        }
+
+    };
+};
+
+#endif
diff --git a/include/std/util/impl/qsort.H b/include/std/util/impl/qsort.H
new file mode 100644
index 00000000..718e3f64
--- /dev/null
+++ b/include/std/util/impl/qsort.H
@@ -0,0 +1,191 @@
+/* IBM_PROLOG_BEGIN_TAG                                                   */
+/* This is an automatically generated prolog.                             */
+/*                                                                        */
+/* $Source: src/include/util/impl/qsort.H $                               */
+/*                                                                        */
+/* OpenPOWER HostBoot Project                                             */
+/*                                                                        */
+/* Contributors Listed Below - COPYRIGHT 2012,2015                        */
+/* [+] International Business Machines Corp.                              */
+/*                                                                        */
+/*                                                                        */
+/* Licensed under the Apache License, Version 2.0 (the "License");        */
+/* you may not use this file except in compliance with the License.       */
+/* You may obtain a copy of the License at                                */
+/*                                                                        */
+/*     http://www.apache.org/licenses/LICENSE-2.0                         */
+/*                                                                        */
+/* Unless required by applicable law or agreed to in writing, software    */
+/* distributed under the License is distributed on an "AS IS" BASIS,      */
+/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        */
+/* implied. See the License for the specific language governing           */
+/* permissions and limitations under the License.                         */
+/*                                                                        */
+/* IBM_PROLOG_END_TAG                                                     */
+
+#ifndef __UTIL_IMPL_QSORT_H
+#define __UTIL_IMPL_QSORT_H
+
+/** @file qsort.H
+ *
+ *  Contains the internal implementation details of std::sort implemented as
+ *  quick-sort.
+ */
+
+#include <iterator>
+
+// Forward declaration due to 'swap' being defined in <algorithm> which is
+// including this file itself.
+namespace std
+{
+    template <typename T> void swap(T& a, T& b);
+};
+
+namespace Util
+{
+    namespace __Util_QSort_Impl
+    {
+        template <typename RandomAccessIterator>
+        void sort(RandomAccessIterator first, RandomAccessIterator last)
+        {
+            size_t length = std::distance(first, last);
+
+            // A range of length 0 or 1 is already sort.
+            if ((length == 0) || (length == 1))
+            {
+                return;
+            }
+
+            // A range of length 2 has a trivial sort.
+            if (length == 2)
+            {
+                RandomAccessIterator next = first;
+                std::advance(next, 1);
+
+                if (*next < *first)
+                {
+                    std::swap(*first, *next);
+                }
+                return;
+            }
+
+            // Choose pivot as middle and move pivot to end.
+            //     This is done to eliminate the O(n^2) behavior when the
+            //     range is already sorted.
+            RandomAccessIterator pivot = first;
+            std::advance(pivot,length - 1);
+            RandomAccessIterator middle = first;
+            std::advance(middle, length / 2);
+            std::swap(*pivot, *middle);
+
+            // Perform partitioning...
+
+            // Division points to the first element greater than the pivot or
+            // else the farthest point partitioned if no elements greater than
+            // the pivot have been found yet.
+            RandomAccessIterator division = first;
+            RandomAccessIterator pos = first;
+            while(pos != pivot)
+            {
+                // Element less than the pivot is found, so move it to the
+                // "less than" side of the division line.
+                if (*pos < *pivot)
+                {
+                    if (pos != division)
+                    {
+                        std::swap(*pos, *division);
+                    }
+                    ++division;
+                }
+
+                ++pos;
+            }
+
+            // Move the pivot down to the division line, which is its sorted
+            // position in the range.
+            if (pivot != division)
+            {
+                std::swap(*pivot,*division);
+            }
+
+            // Sort each partition
+            __Util_QSort_Impl::sort(first,division);
+            std::advance(division, 1);
+            __Util_QSort_Impl::sort(division, last);
+        };
+
+
+        template <typename RandomAccessIterator, typename StrictWeakOrdering>
+        void sort(RandomAccessIterator first, RandomAccessIterator last,
+                  StrictWeakOrdering pred)
+        {
+            size_t length = std::distance(first, last);
+
+            // A range of length 0 or 1 is already sort.
+            if ((length == 0) || (length == 1))
+            {
+                return;
+            }
+
+            // A range of length 2 has a trivial sort.
+            if (length == 2)
+            {
+                RandomAccessIterator next = first;
+                std::advance(next, 1);
+
+                if (pred(*next,*first))
+                {
+                    std::swap(*first, *next);
+                }
+                return;
+            }
+
+            // Choose pivot as middle and move pivot to end.
+            //     This is done to eliminate the O(n^2) behavior when the
+            //     range is already sorted.
+            RandomAccessIterator pivot = first;
+            std::advance(pivot,length - 1);
+            RandomAccessIterator middle = first;
+            std::advance(middle, length / 2);
+            std::swap(*pivot, *middle);
+
+            // Perform partitioning...
+
+            // Division points to the first element greater than the pivot or
+            // else the farthest point partitioned if no elements greater than
+            // the pivot have been found yet.
+            RandomAccessIterator division = first;
+            RandomAccessIterator pos = first;
+            while(pos != pivot)
+            {
+                // Element less than the pivot is found, so move it to the
+                // "less than" side of the division line.
+                if (pred(*pos,*pivot))
+                {
+                    if (pos != division)
+                    {
+                        std::swap(*pos, *division);
+                    }
+                    ++division;
+                }
+
+                ++pos;
+            }
+
+            // Move the pivot down to the division line, which is its sorted
+            // position in the range.
+            if (pivot != division)
+            {
+                std::swap(*pivot,*division);
+            }
+
+            // Sort each partition.
+             __Util_QSort_Impl::sort(first,division,pred);
+            std::advance(division, 1);
+             __Util_QSort_Impl::sort(division, last,pred);
+        };
+
+    };
+};
+
+#endif
diff --git a/include/std/util/traits/has_lessthan.H b/include/std/util/traits/has_lessthan.H
new file mode 100644
index 00000000..7a411468
--- /dev/null
+++ b/include/std/util/traits/has_lessthan.H
@@ -0,0 +1,40 @@
+/* IBM_PROLOG_BEGIN_TAG                                                   */
+/* This is an automatically generated prolog.                             */
+/*                                                                        */
+/* $Source: src/include/util/traits/has_lessthan.H $                      */
+/*                                                                        */
+/* OpenPOWER HostBoot Project                                             */
+/*                                                                        */
+/* COPYRIGHT International Business Machines Corp. 2012,2014              */
+/*                                                                        */
+/* Licensed under the Apache License, Version 2.0 (the "License");        */
+/* you may not use this file except in compliance with the License.       */
+/* You may obtain a copy of the License at                                */
+/*                                                                        */
+/*     http://www.apache.org/licenses/LICENSE-2.0                         */
+/*                                                                        */
+/* Unless required by applicable law or agreed to in writing, software    */
+/* distributed under the License is distributed on an "AS IS" BASIS,      */
+/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        */
+/* implied. See the License for the specific language governing           */
+/* permissions and limitations under the License.                         */
+/*                                                                        */
+/* IBM_PROLOG_END_TAG                                                     */
+
+#ifndef __UTIL_TRAITS_HAS_LESSTHAN
+#define __UTIL_TRAITS_HAS_LESSTHAN
+
+/** @file has_lessthan.H
+ *  Creates a template class has_lessthan<T> who's value variable will tell
+ *  if T has a valid < comparison operation.
+ */
+
+#define UTIL_COMPARISON_OPERATOR <
+#define UTIL_COMPARISON_OPERATOR_NAME lessthan
+
+#include <util/traits/impl/has_comparison.H>
+
+#undef UTIL_COMPARISON_OPERATOR
+#undef UTIL_COMPARISON_OPERATOR_NAME
+
+#endif
diff --git a/include/std/util/traits/has_minus.H b/include/std/util/traits/has_minus.H
new file mode 100644
index 00000000..ce3c59b7
--- /dev/null
+++ b/include/std/util/traits/has_minus.H
@@ -0,0 +1,40 @@
+/* IBM_PROLOG_BEGIN_TAG                                                   */
+/* This is an automatically generated prolog.                             */
+/*                                                                        */
+/* $Source: src/include/util/traits/has_minus.H $                         */
+/*                                                                        */
+/* OpenPOWER HostBoot Project                                             */
+/*                                                                        */
+/* COPYRIGHT International Business Machines Corp. 2012,2014              */
+/*                                                                        */
+/* Licensed under the Apache License, Version 2.0 (the "License");        */
+/* you may not use this file except in compliance with the License.       */
+/* You may obtain a copy of the License at                                */
+/*                                                                        */
+/*     http://www.apache.org/licenses/LICENSE-2.0                         */
+/*                                                                        */
+/* Unless required by applicable law or agreed to in writing, software    */
+/* distributed under the License is distributed on an "AS IS" BASIS,      */
+/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        */
+/* implied. See the License for the specific language governing           */
+/* permissions and limitations under the License.                         */
+/*                                                                        */
+/* IBM_PROLOG_END_TAG                                                     */
+
+#ifndef __UTIL_TRAITS_HAS_MINUS
+#define __UTIL_TRAITS_HAS_MINUS
+
+/** @file has_minus.H
+ *  Creates a template class has_minus<T> who's value variable will tell
+ *  if T has a valid - operation.
+ */
+
+#define UTIL_COMPARISON_OPERATOR -
+#define UTIL_COMPARISON_OPERATOR_NAME minus
+
+#include <util/traits/impl/has_comparison.H>
+
+#undef UTIL_COMPARISON_OPERATOR
+#undef UTIL_COMPARISON_OPERATOR_NAME
+
+#endif
diff --git a/include/std/util/traits/has_plusequals.H b/include/std/util/traits/has_plusequals.H
new file mode 100644
index 00000000..5d66b403
--- /dev/null
+++ b/include/std/util/traits/has_plusequals.H
@@ -0,0 +1,40 @@
+/* IBM_PROLOG_BEGIN_TAG                                                   */
+/* This is an automatically generated prolog.                             */
+/*                                                                        */
+/* $Source: src/include/util/traits/has_plusequals.H $                    */
+/*                                                                        */
+/* OpenPOWER HostBoot Project                                             */
+/*                                                                        */
+/* COPYRIGHT International Business Machines Corp. 2012,2014              */
+/*                                                                        */
+/* Licensed under the Apache License, Version 2.0 (the "License");        */
+/* you may not use this file except in compliance with the License.       */
+/* You may obtain a copy of the License at                                */
+/*                                                                        */
+/*     http://www.apache.org/licenses/LICENSE-2.0                         */
+/*                                                                        */
+/* Unless required by applicable law or agreed to in writing, software    */
+/* distributed under the License is distributed on an "AS IS" BASIS,      */
+/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        */
+/* implied. See the License for the specific language governing           */
+/* permissions and limitations under the License.                         */
+/*                                                                        */
+/* IBM_PROLOG_END_TAG                                                     */
+
+#ifndef __UTIL_TRAITS_HAS_PLUSEQUALS
+#define __UTIL_TRAITS_HAS_PLUSEQUALS
+
+/** @file has_plusequals.H
+ *  Creates a template class has_plusequals<T> who's value variable will tell
+ *  if T has a valid += operation.
+ */
+
+#define UTIL_COMPARISON_OPERATOR +=
+#define UTIL_COMPARISON_OPERATOR_NAME plusequals
+
+#include <util/traits/impl/has_comparison.H>
+
+#undef UTIL_COMPARISON_OPERATOR
+#undef UTIL_COMPARISON_OPERATOR_NAME
+
+#endif
diff --git a/include/std/util/traits/impl/has_comparison.H b/include/std/util/traits/impl/has_comparison.H
new file mode 100644
index 00000000..61eae94c
--- /dev/null
+++ b/include/std/util/traits/impl/has_comparison.H
@@ -0,0 +1,135 @@
+/* IBM_PROLOG_BEGIN_TAG                                                   */
+/* This is an automatically generated prolog.                             */
+/*                                                                        */
+/* $Source: src/include/util/traits/impl/has_comparison.H $               */
+/*                                                                        */
+/* OpenPOWER HostBoot Project                                             */
+/*                                                                        */
+/* COPYRIGHT International Business Machines Corp. 2012,2014              */
+/*                                                                        */
+/* Licensed under the Apache License, Version 2.0 (the "License");        */
+/* you may not use this file except in compliance with the License.       */
+/* You may obtain a copy of the License at                                */
+/*                                                                        */
+/*     http://www.apache.org/licenses/LICENSE-2.0                         */
+/*                                                                        */
+/* Unless required by applicable law or agreed to in writing, software    */
+/* distributed under the License is distributed on an "AS IS" BASIS,      */
+/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        */
+/* implied. See the License for the specific language governing           */
+/* permissions and limitations under the License.                         */
+/*                                                                        */
+/* IBM_PROLOG_END_TAG                                                     */
+
+/** @file has_comparison.H
+ *
+ *  Defines the guts of a has_foo<T> template where 'foo' is a binary
+ *  comparison operator on a type T.  This template can be used for
+ *  template meta-programming purposes.
+ *
+ *  The macros UTIL_COMPARISON_OPERATOR and UTIL_COMPARISON_OPERATOR_NAME
+ *  can be defined to create a template. For instance (<, lessthan) will
+ *  create a template has_lessthan that allows determination to be made on
+ *  if T has a valid < operator.
+ *
+ *  This file purposefully omits an include-guard to allow multiple templates
+ *  to be defined for all the various comparison operators.
+ *
+ *  Notice that a heavy dose of SFINAE techniques follow.
+ */
+
+// Ensure UTIL_COMPARISON_OPERATOR has been defined.
+#ifndef UTIL_COMPARISON_OPERATOR
+    #error Comparison operator is not defined.
+#endif
+
+// Ensure UTIL_COMPARISON_OPERATOR_NAME has been defined.
+#ifndef UTIL_COMPARISON_OPERATOR_NAME
+    #error Comparison operator name is not defined.
+#endif
+
+// Macro magic to make well-formed variable names from existing #defines.
+#define __UTIL_TRAIT_COMPARISON_MAKENAME(X,Y)   X ## Y
+#define _UTIL_TRAIT_COMPARISON_MAKENAME(X,Y)    \
+                __UTIL_TRAIT_COMPARISON_MAKENAME(X,Y)
+#define UTIL_TRAIT_COMPARISON_MAKENAME(X) \
+                _UTIL_TRAIT_COMPARISON_MAKENAME(X,\
+                                                UTIL_COMPARISON_OPERATOR_NAME)
+
+namespace Util
+{
+
+// Creates a namespace of the form Util::__Util_Trait_Impl_OPERATOR_NAME to
+// hide the template implementation in.
+namespace UTIL_TRAIT_COMPARISON_MAKENAME(__Util_Trait_Impl_)
+{
+    // If "T op S" is valid, it is going to return a type R.  If it is not
+    // valid, we still need it to compile cleanly.  So what we do is
+    // create a type (convert_from_any_type) that causes implicit type
+    // conversion from any other type.  We ensure that the operator against
+    // convert_from_any_type returns a special type (bad_type).
+    //
+    // If "T op S" is valid then the implicit type conversion to
+    // convert_from_any_type will not happen because the native "T op S" takes
+    // precidence.  So "T op S" has type not equal to bad_type.  If "T op S"
+    // is invalid then the implicit type conversion will cause "T op S" to have
+    // type bad_type.
+
+    struct bad_type {};
+    struct convert_from_any_type
+    {
+        template <class C> convert_from_any_type(C const&);
+    };
+    bad_type operator UTIL_COMPARISON_OPERATOR (const convert_from_any_type&,
+                                                const convert_from_any_type&);
+
+
+    // Now, "T op S" is going to return either bad_type or something else.  We
+    // define a function 'has_comparison' that returns a character array of
+    // different size based on the input parameter type.  Then the "sizeof"
+    // can be used to tell if "T op S" returns bad_type or something else.
+    //
+    // The only additional oddity is the get_instance function.  Since some
+    // classes cannot be directly constructed, this is a level of indirection
+    // to get a type of T and S to apply the operator against.
+    template <typename _T, typename _S, typename _R>
+    struct UTIL_TRAIT_COMPARISON_MAKENAME(has_)
+    {
+        typedef char yes[1];
+        typedef char no[2];
+
+        static no& has_comparison(bad_type);
+        static yes& has_comparison(_R);
+
+        template <typename C> static C& get_instance();
+
+        static const bool value =
+            sizeof(has_comparison(get_instance<_T>() UTIL_COMPARISON_OPERATOR
+                                  get_instance<_S>())) == sizeof(yes);
+    };
+
+};
+
+
+// Since the implementation was hidden in a __Util_Trait_Impl_OPERATOR_NAME
+// namespace, we expose just the main comparison class (with the value variable)
+// by defining a class in the Traits namespace that inherits from the one in
+// the __Util_Trait_Impl_OPERATOR_NAME namespace.
+namespace Traits
+{
+    template <typename _T, typename _S = _T,
+              typename _R = typename
+                UTIL_TRAIT_COMPARISON_MAKENAME(Util::__Util_Trait_Impl_)::
+                convert_from_any_type>
+    struct UTIL_TRAIT_COMPARISON_MAKENAME(has_) :
+        public UTIL_TRAIT_COMPARISON_MAKENAME(Util::__Util_Trait_Impl_)::
+               UTIL_TRAIT_COMPARISON_MAKENAME(has_)<_T,_S,_R>
+    {};
+};
+
+};
+
+#undef __UTIL_TRAIT_COMPARISON_MAKENAME
+#undef _UTIL_TRAIT_COMPARISON_MAKENAME
+#undef UTIL_TRAIT_COMPARISON_MAKENAME
+
diff --git a/include/std/util/traits/remove_const.H b/include/std/util/traits/remove_const.H
new file mode 100644
index 00000000..2a7aabb4
--- /dev/null
+++ b/include/std/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 $                      */
+/*                                                                        */
+/* OpenPOWER HostBoot Project                                             */
+/*                                                                        */
+/* COPYRIGHT International Business Machines Corp. 2012,2014              */
+/*                                                                        */
+/* Licensed under the Apache License, Version 2.0 (the "License");        */
+/* you may not use this file except in compliance with the License.       */
+/* You may obtain a copy of the License at                                */
+/*                                                                        */
+/*     http://www.apache.org/licenses/LICENSE-2.0                         */
+/*                                                                        */
+/* Unless required by applicable law or agreed to in writing, software    */
+/* distributed under the License is distributed on an "AS IS" BASIS,      */
+/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        */
+/* implied. See the License for the specific language governing           */
+/* permissions and limitations under the License.                         */
+/*                                                                        */
+/* IBM_PROLOG_END_TAG                                                     */
+
+#ifndef __UTIL_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/sbe/hwpf/include/fapi2_hw_access.H b/sbe/hwpf/include/fapi2_hw_access.H
index fca775b1..7ce2af37 100644
--- a/sbe/hwpf/include/fapi2_hw_access.H
+++ b/sbe/hwpf/include/fapi2_hw_access.H
@@ -37,11 +37,11 @@ typedef uint64_t spyId_t;
 #endif
 
 #include <stdint.h>
-#include <thread>
 #include <buffer.H>
 
-// variable_buffer isn't supported on PPE
+// thread/variable_buffer isn't supported on PPE
 #ifndef __PPE__
+#include <thread>
 #include <variable_buffer.H>
 #endif