summaryrefslogtreecommitdiffstats
path: root/include/std/util
diff options
context:
space:
mode:
Diffstat (limited to 'include/std/util')
-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
7 files changed, 666 insertions, 0 deletions
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