diff options
author | Patrick Williams <iawillia@us.ibm.com> | 2012-02-14 16:45:40 -0600 |
---|---|---|
committer | A. Patrick Williams III <iawillia@us.ibm.com> | 2012-02-22 16:11:14 -0600 |
commit | ddb7ed4a1c3da475aa1fd6036171d4bbba75e722 (patch) | |
tree | 6616d24f32e7ff5154bb25bd9366137848ceeced | |
parent | c232f7a5a8b38321edae7a02c3148e67b5b4c3c7 (diff) | |
download | talos-hostboot-ddb7ed4a1c3da475aa1fd6036171d4bbba75e722.tar.gz talos-hostboot-ddb7ed4a1c3da475aa1fd6036171d4bbba75e722.zip |
STL advance / distance.
Change-Id: I9cdf9459f2970def812b1681897fe7d0cdda37ac
Reviewed-on: http://gfw160.austin.ibm.com:8080/gerrit/669
Tested-by: Jenkins Server
Reviewed-by: Douglas R. Gilbert <dgilbert@us.ibm.com>
Reviewed-by: Terry J. Opie <opiet@us.ibm.com>
Reviewed-by: MIKE J. JONES <mjjones@us.ibm.com>
Reviewed-by: A. Patrick Williams III <iawillia@us.ibm.com>
-rw-r--r-- | src/include/iterator | 107 | ||||
-rw-r--r-- | src/include/list | 4 | ||||
-rw-r--r-- | src/include/stdint.h | 2 | ||||
-rw-r--r-- | src/include/util/impl/iterator.h | 147 | ||||
-rw-r--r-- | src/include/util/traits/has_minus.H | 40 | ||||
-rw-r--r-- | src/include/util/traits/has_plusequals.H | 40 | ||||
-rw-r--r-- | src/include/util/traits/impl/has_comparison.H | 17 | ||||
-rw-r--r-- | src/usr/testcore/lib/stltest.H | 94 |
8 files changed, 444 insertions, 7 deletions
diff --git a/src/include/iterator b/src/include/iterator new file mode 100644 index 000000000..dbe4b2baa --- /dev/null +++ b/src/include/iterator @@ -0,0 +1,107 @@ +// IBM_PROLOG_BEGIN_TAG +// This is an automatically generated prolog. +// +// $Source: src/include/iterator $ +// +// IBM CONFIDENTIAL +// +// COPYRIGHT International Business Machines Corp. 2012 +// +// p1 +// +// Object Code Only (OCO) source materials +// Licensed Internal Code Source Materials +// IBM HostBoot Licensed Internal Code +// +// The source code for this program is not published or other- +// wise divested of its trade secrets, irrespective of what has +// been deposited with the U.S. Copyright Office. +// +// Origin: 30 +// +// IBM_PROLOG_END + +#ifndef __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); +} + +}; // namespace std. +#endif + +#endif +/* vim: set filetype=cpp : */ diff --git a/src/include/list b/src/include/list index 34ec4f17a..8e07d6810 100644 --- a/src/include/list +++ b/src/include/list @@ -162,6 +162,8 @@ namespace std typedef ListIterator_t<T> _This; typedef ListNodeData_t<T> _Node; + typedef T value_type; + typedef ptrdiff_t difference_type; typedef T* pointer; typedef T& reference; @@ -292,6 +294,8 @@ namespace std typedef const ListNodeData_t<T> _Node; typedef const ListIterator_t<T> const_iterator; + typedef T value_type; + typedef ptrdiff_t difference_type; typedef const T* pointer; typedef const T& const_reference; diff --git a/src/include/stdint.h b/src/include/stdint.h index 1f9ed95b9..e545e0f29 100644 --- a/src/include/stdint.h +++ b/src/include/stdint.h @@ -38,6 +38,8 @@ typedef unsigned long int uint64_t; typedef uint64_t size_t; typedef int64_t ssize_t; +typedef ssize_t ptrdiff_t; + #define UINT8_MAX (255U) #define UINT16_MAX (65535U) #define UINT32_MAX (4294967295U) diff --git a/src/include/util/impl/iterator.h b/src/include/util/impl/iterator.h new file mode 100644 index 000000000..de6b445aa --- /dev/null +++ b/src/include/util/impl/iterator.h @@ -0,0 +1,147 @@ +// IBM_PROLOG_BEGIN_TAG +// This is an automatically generated prolog. +// +// $Source: src/include/util/impl/iterator.h $ +// +// IBM CONFIDENTIAL +// +// COPYRIGHT International Business Machines Corp. 2012 +// +// p1 +// +// Object Code Only (OCO) source materials +// Licensed Internal Code Source Materials +// IBM HostBoot Licensed Internal Code +// +// The source code for this program is not published or other- +// wise divested of its trade secrets, irrespective of what has +// been deposited with the U.S. Copyright Office. +// +// Origin: 30 +// +// IBM_PROLOG_END + +#ifndef __UTIL_IMPL_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 existance 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 existance 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/src/include/util/traits/has_minus.H b/src/include/util/traits/has_minus.H new file mode 100644 index 000000000..f80be8c89 --- /dev/null +++ b/src/include/util/traits/has_minus.H @@ -0,0 +1,40 @@ +// IBM_PROLOG_BEGIN_TAG +// This is an automatically generated prolog. +// +// $Source: src/include/usr/util/traits/has_minus.H $ +// +// IBM CONFIDENTIAL +// +// COPYRIGHT International Business Machines Corp. 2012 +// +// p1 +// +// Object Code Only (OCO) source materials +// Licensed Internal Code Source Materials +// IBM HostBoot Licensed Internal Code +// +// The source code for this program is not published or other- +// wise divested of its trade secrets, irrespective of what has +// been deposited with the U.S. Copyright Office. +// +// Origin: 30 +// +// IBM_PROLOG_END + +#ifndef __UTIL_TRAITS_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/src/include/util/traits/has_plusequals.H b/src/include/util/traits/has_plusequals.H new file mode 100644 index 000000000..c6fbac557 --- /dev/null +++ b/src/include/util/traits/has_plusequals.H @@ -0,0 +1,40 @@ +// IBM_PROLOG_BEGIN_TAG +// This is an automatically generated prolog. +// +// $Source: src/include/usr/util/traits/has_plusequals.H $ +// +// IBM CONFIDENTIAL +// +// COPYRIGHT International Business Machines Corp. 2012 +// +// p1 +// +// Object Code Only (OCO) source materials +// Licensed Internal Code Source Materials +// IBM HostBoot Licensed Internal Code +// +// The source code for this program is not published or other- +// wise divested of its trade secrets, irrespective of what has +// been deposited with the U.S. Copyright Office. +// +// Origin: 30 +// +// IBM_PROLOG_END + +#ifndef __UTIL_TRAITS_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/src/include/util/traits/impl/has_comparison.H b/src/include/util/traits/impl/has_comparison.H index 4cc7a84c0..fbfb5d7ff 100644 --- a/src/include/util/traits/impl/has_comparison.H +++ b/src/include/util/traits/impl/has_comparison.H @@ -63,8 +63,8 @@ namespace Util // hide the template implementation in. namespace UTIL_TRAIT_COMPARISON_MAKENAME(__Util_Trait_Impl_) { - // If "T op S" is valid, it is going to return some type (likely bool). If - // it is not valid, we still need it to compile cleanly. So what we do is + // 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). @@ -84,7 +84,7 @@ namespace UTIL_TRAIT_COMPARISON_MAKENAME(__Util_Trait_Impl_) const convert_from_any_type&); - // Now, "T op T" is going to return either bad_type or something else. We + // 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. @@ -92,14 +92,14 @@ namespace UTIL_TRAIT_COMPARISON_MAKENAME(__Util_Trait_Impl_) // 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> + 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(...); + static yes& has_comparison(_R); template <typename C> static C& get_instance(); @@ -117,10 +117,13 @@ namespace UTIL_TRAIT_COMPARISON_MAKENAME(__Util_Trait_Impl_) // the __Util_Trait_Impl_OPERATOR_NAME namespace. namespace Traits { - template <typename _T, typename _S = _T> + 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> + UTIL_TRAIT_COMPARISON_MAKENAME(has_)<_T,_S,_R> {}; }; diff --git a/src/usr/testcore/lib/stltest.H b/src/usr/testcore/lib/stltest.H index 8eca620cd..f2bea98c5 100644 --- a/src/usr/testcore/lib/stltest.H +++ b/src/usr/testcore/lib/stltest.H @@ -27,6 +27,8 @@ #include <vector> #include <list> #include <map> +#include <algorithm> +#include <iterator> class STLTest : public CxxTest::TestSuite { @@ -167,5 +169,97 @@ class STLTest : public CxxTest::TestSuite --i; } } + + + void testAdvance() + { + // Test for a non-random-access iterator, such as list. + std::list<int> list; + + for(int i = 0; i < 100; i++) + list.push_back(i); + + for (int i = 0; i < 100; i++) + { + std::list<int>::iterator itr = list.begin(); + std::advance(itr, i); + if (*itr != i) + { + TS_FAIL("List iterator value mismatch %d:%d.", *itr, i); + } + } + + // Test for a random-access iterator, such as vector. + std::vector<int> vector; + + for (int i = 0; i < 100; i++) + vector.push_back(i); + + for (int i = 0; i < 100; i++) + { + std::vector<int>::iterator itr = vector.begin(); + std::advance(itr, i); + if (*itr != i) + { + TS_FAIL("Vector iterator value mismatch %d:%d.", *itr, i); + } + } + } + + void testDistance() + { + // Test for a non-random-access iterator, such as list. + std::list<int> list; + + for (int i = 0; i < 100; i++) + list.push_back(i); + + for (int i = 0; i < 100; i++) + for (int j = 0; j < 100; j++) + { + // distance isn't defined for non-random-access iterator + // when "first" is greater than "last". + if (i > j) continue; + + std::list<int>::iterator itr_i = list.begin(), + itr_j = list.begin(); + + std::advance(itr_i, i); + std::advance(itr_j, j); + + ssize_t d = std::distance(itr_i, itr_j); + + if (d != (j-i)) + { + TS_FAIL("List distance incorrect %d:%d:%d", + i, j, d); + } + } + + // Test for a random-access iterator, such as vector. + std::vector<int> vector; + + for (int i = 0; i < 100; i++) + vector.push_back(i); + + for (int i = 0; i < 100; i++) + for (int j = 0; j < 100; j++) + { + std::vector<int>::iterator itr_i = vector.begin(), + itr_j = vector.begin(); + + std::advance(itr_i, i); + std::advance(itr_j, j); + + ssize_t d = std::distance(itr_i, itr_j); + + if (d != (j-i)) + { + TS_FAIL("Vector distance incorrect %d:%d:%d", + i, j, d); + } + } + + } }; #endif |