summaryrefslogtreecommitdiffstats
path: root/include
diff options
context:
space:
mode:
authorDoug Gilbert <dgilbert@us.ibm.com>2015-10-14 09:20:47 -0500
committerGregory S. Still <stillgs@us.ibm.com>2015-12-07 06:57:35 -0600
commit96658ed12b4187865f353248916101e1aaf814f8 (patch)
treeea27d0547ae483c1a597a5f866b086c16f2aa8ae /include
parentfe19e38abc02ef157a2bcbf0bd49b48a6fe2ea3b (diff)
downloadtalos-sbe-96658ed12b4187865f353248916101e1aaf814f8.tar.gz
talos-sbe-96658ed12b4187865f353248916101e1aaf814f8.zip
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>
Diffstat (limited to 'include')
-rw-r--r--include/std/algorithm762
-rw-r--r--include/std/iterator185
-rwxr-xr-xinclude/std/new40
-rw-r--r--include/std/type_traits63
-rw-r--r--include/std/util/impl/iterator.h149
-rw-r--r--include/std/util/impl/qsort.H191
-rw-r--r--include/std/util/traits/has_lessthan.H40
-rw-r--r--include/std/util/traits/has_minus.H40
-rw-r--r--include/std/util/traits/has_plusequals.H40
-rw-r--r--include/std/util/traits/impl/has_comparison.H135
-rw-r--r--include/std/util/traits/remove_const.H71
11 files changed, 1716 insertions, 0 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
OpenPOWER on IntegriCloud