diff options
Diffstat (limited to 'include/std/util')
-rw-r--r-- | include/std/util/impl/iterator.h | 149 | ||||
-rw-r--r-- | include/std/util/impl/qsort.H | 191 | ||||
-rw-r--r-- | include/std/util/traits/has_lessthan.H | 40 | ||||
-rw-r--r-- | include/std/util/traits/has_minus.H | 40 | ||||
-rw-r--r-- | include/std/util/traits/has_plusequals.H | 40 | ||||
-rw-r--r-- | include/std/util/traits/impl/has_comparison.H | 135 | ||||
-rw-r--r-- | include/std/util/traits/remove_const.H | 71 |
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 |