diff options
| -rw-r--r-- | libstdc++-v3/ChangeLog | 6 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/search_n/iterator.cc | 103 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/performance/25_algorithms/search_n.cc | 72 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/testsuite_iterators.h | 539 |
4 files changed, 720 insertions, 0 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 2a182b5d227..75fd077bb99 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,9 @@ +2004-11-23 Chris Jefferson <chris@bubblescope.net> + + * testsuite/testsuite_iterators.h: New. + * testsuite/25_algorithms/search_n/iterator.cc: New. + * testsuite/performance/25_algorithms/search_n.cc: New. + 2004-11-23 John David Anglin <dave.anglin@nrc-cnrc.gc.ca> * testsuite/lib/libstdc++.exp: Use new procs in target-libpath.exp. diff --git a/libstdc++-v3/testsuite/25_algorithms/search_n/iterator.cc b/libstdc++-v3/testsuite/25_algorithms/search_n/iterator.cc new file mode 100644 index 00000000000..f822745be22 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/search_n/iterator.cc @@ -0,0 +1,103 @@ +// Copyright (C) 2004 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 2, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING. If not, write to the Free +// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// USA. + +// 25 algorithms, search_n + +#include <algorithm> +#include <functional> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +#define TEST_DEPTH 14 +int array1[11] = {0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0}; +int array2[TEST_DEPTH]; + +bool +pred(int i, int j) +{ + return i == j; +} + +bool +lexstep(int* start, int length) +{ + int i = 0; + int carry = 1; + while(i < length && carry) + { + if(start[i] == 1) + start[i] = 0; + else + { + start[i] = 1; + carry = 0; + } + i++; + } + return !carry; +} + +using __gnu_test::test_container; +using __gnu_test::random_access_iterator_wrapper; +using __gnu_test::bidirectional_iterator_wrapper; +using __gnu_test::forward_iterator_wrapper; + +int main() { + test_container<int,forward_iterator_wrapper> con(array1,array1 + 10); + VERIFY(search_n(con.end(), con.end(), 0, 1) == con.end()); + VERIFY(search_n(con.end(), con.end(), 1, 1) == con.end()); + VERIFY(search_n(con.begin(), con.end(), 1, 1).ptr == array1 + 1); + VERIFY(search_n(con.begin(), con.end(), 2, 1).ptr == array1 + 4); + VERIFY(search_n(con.begin(), con.end(), 3, 1).ptr == array1 + 7); + VERIFY(search_n(con.begin(), con.end(), 3, 0) == con.end()); + + // Now do a brute-force comparison of the different types + for(int i = 0; i < TEST_DEPTH; i++) + { + for(int j = 0; j < i; j++) + array2[i] = 0; + do { + for(int j = 0; j < i; j++) + { + test_container<int, forward_iterator_wrapper> + forwardcon(array2, array2 + i); + test_container<int, bidirectional_iterator_wrapper> + randomcon(array2, array2 + i); + test_container<int, bidirectional_iterator_wrapper> + bidircon(array2, array2 + i); + + int* t1 = search_n(forwardcon.begin(), + forwardcon.end(), j, 1).ptr; + int* t2 = search_n(forwardcon.begin(), + forwardcon.end(), j, 1, pred).ptr; + int* t3 = search_n(bidircon.begin(), + bidircon.end(), j, 1).ptr; + int* t4 = search_n(bidircon.begin(), + bidircon.end(), j, 1, pred).ptr; + int* t5 = search_n(randomcon.begin(), + randomcon.end(), j, 1).ptr; + int* t6 = search_n(randomcon.begin(), + randomcon.end(), j, 1, pred).ptr; + VERIFY((t1 == t2) && (t2 == t3) && (t3 == t4) && + (t4 == t5) && (t5 == t6)); + } + } + while(lexstep(array2, i)); + } + return 0; +} diff --git a/libstdc++-v3/testsuite/performance/25_algorithms/search_n.cc b/libstdc++-v3/testsuite/performance/25_algorithms/search_n.cc new file mode 100644 index 00000000000..6ffa0a9bcaf --- /dev/null +++ b/libstdc++-v3/testsuite/performance/25_algorithms/search_n.cc @@ -0,0 +1,72 @@ +// Copyright (C) 2004 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 2, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING. If not, write to the Free +// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// USA. + +// As a special exception, you may use this file as part of a free software +// library without restriction. Specifically, if other files instantiate +// templates or use macros or inline functions from this file, or you compile +// this file and link it with other files to produce an executable, this +// file does not by itself cause the resulting executable to be covered by +// the GNU General Public License. This exception does not however +// invalidate any other reasons why the executable file might be covered by +// the GNU General Public License. + +#define DISABLE_ITERATOR_DEBUG 1 + +#include<cstdlib> +#include<vector> +#include<algorithm> + +#include<sstream> +#include<testsuite_performance.h> +#include<testsuite_iterators.h> + +using namespace std; +using namespace __gnu_test; + +const int length = 10000000; +const int match_length = 3; +int array[length]; + +int +main(void) +{ + time_counter time; + resource_counter resource; + int match = rand() % (match_length - 1); + for(int i = 0; i < length; i++) + { + array[i] = (match != 0) ? 1 : 0; + if(--match < 0) match = rand() % (match_length - 1); + } + test_container<int, forward_iterator_wrapper> fcon(array, array + length); + start_counters(time, resource); + for(int i = 0; i < 100; i++) + search_n(fcon.begin(), fcon.end(), 10, 1); + stop_counters(time, resource); + report_performance(__FILE__, "forward iterator", time, resource); + clear_counters(time, resource); + + test_container<int, random_access_iterator_wrapper> rcon(array, array + length); + start_counters(time, resource); + for(int i = 0; i < 100; i++) + search_n(rcon.begin(), rcon.end(), 10, 1); + stop_counters(time, resource); + report_performance(__FILE__, "random acess iterator", time, resource); + clear_counters(time, resource); +} + diff --git a/libstdc++-v3/testsuite/testsuite_iterators.h b/libstdc++-v3/testsuite/testsuite_iterators.h new file mode 100644 index 00000000000..435bb1d26b5 --- /dev/null +++ b/libstdc++-v3/testsuite/testsuite_iterators.h @@ -0,0 +1,539 @@ +// -*- C++ -*- +// Iterator Wrappers for the C++ library testsuite. +// +// Copyright (C) 2004 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 2, or (at your option) +// any later version. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING. If not, write to the Free +// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// USA. +// +// As a special exception, you may use this file as part of a free software +// library without restriction. Specifically, if other files instantiate +// templates or use macros or inline functions from this file, or you compile +// this file and link it with other files to produce an executable, this +// file does not by itself cause the resulting executable to be covered by +// the GNU General Public License. This exception does not however +// invalidate any other reasons why the executable file might be covered by +// the GNU General Public License. + +// This file provides the following: +// +// input_iterator_wrapper, output_iterator_wrapper +// forward_iterator_wrapper, bidirectional_iterator_wrapper and +// random_access_wrapper, which attempt to exactly perform the requirements +// of these types of iterators. These are constructed from the class +// test_container, which is given two pointers to T and an iterator type. + +#include <testsuite_hooks.h> +#include <iterator> + +#ifndef _TESTSUITE_ITERATORS +#define _TESTSUITE_ITERATORS + +#ifdef DISABLE_ITERATOR_DEBUG +#define ITERATOR_VERIFY(x) +#else +#define ITERATOR_VERIFY(x) VERIFY(x) +#endif + +namespace __gnu_test +{ + /** + * @brief Simple container for holding two pointers. + * + * Note that input_iterator_wrapper changes first to denote + * how the valid range of == , ++, etc. change as the iterators are used. + */ + template<typename T> + struct BoundsContainer + { + T* first; + T* last; + BoundsContainer(T* _first, T* _last) + : first(_first), last(_last) + { } + }; + + // Simple container for holding state of a set of output iterators. + template<typename T> + struct OutputContainer : public BoundsContainer<T> + { + T* incrementedto; + bool* writtento; + OutputContainer(T* _first, T* _last) + : BoundsContainer<T>(_first, _last), incrementedto(_first) + { + writtento = new bool[this->last - this->first]; + for(int i = 0; i < this->last - this->first; i++) + writtento = false; + } + + ~OutputContainer() + { delete[] writtento; } + }; + + // Produced by output_iterator to allow limited writing to pointer + template<class T> + class WritableObject + { + T* ptr; + + public: + OutputContainer<T>* SharedInfo; + WritableObject(T* ptr_in,OutputContainer<T>* SharedInfo_in): + ptr(ptr_in), SharedInfo(SharedInfo_in) + { } + + void + operator=(T& new_val) + { + ITERATOR_VERIFY(SharedInfo->writtento[ptr - SharedInfo->first] == 0); + SharedInfo->writtento[ptr - SharedInfo->first] = 1; + ptr = new_val; + } + }; + + /** + * @brief output_iterator wrapper for pointer + * + * This class takes a pointer and wraps it to provide exactly + * the requirements of a output_iterator. It should not be + * instansiated directly, but generated from a test_container + */ + template<class T> + struct output_iterator_wrapper: public std::iterator + <std::output_iterator_tag, T, ptrdiff_t, T*, T&> + { + typedef OutputContainer<T> ContainerType; + T* ptr; + ContainerType* SharedInfo; + + output_iterator_wrapper(T* _ptr, ContainerType* SharedInfo_in) + :ptr(_ptr), SharedInfo(SharedInfo_in) + { + ITERATOR_VERIFY(ptr >= SharedInfo->first && ptr <= SharedInfo->last); + } + + output_iterator_wrapper(const output_iterator_wrapper& in) + :ptr(in.ptr), SharedInfo(in.SharedInfo) + { } + + WritableObject<T> + operator*() const + { + ITERATOR_VERIFY(ptr < SharedInfo->last); + ITERATOR_VERIFY(SharedInfo->writtento[ptr - SharedInfo->first] == false); + return WritableObject<T>(ptr, SharedInfo); + } + + output_iterator_wrapper& + operator=(const output_iterator_wrapper& in) + { + ptr = in.ptr; + SharedInfo = in.SharedInfo; + } + + output_iterator_wrapper& + operator++() + { + ITERATOR_VERIFY(SharedInfo && ptr < SharedInfo->last); + ITERATOR_VERIFY(ptr>=SharedInfo->first); + ptr++; + SharedInfo->first=ptr; + return *this; + } + + output_iterator_wrapper + operator++(int) + { + output_iterator_wrapper<T> tmp = *this; + ++*this; + return tmp; + } + + }; + + /** + * @brief input_iterator wrapper for pointer + * + * This class takes a pointer and wraps it to provide exactly + * the requirements of a input_iterator. It should not be + * instansiated directly, but generated from a test_container + */ + template<class T> + class input_iterator_wrapper:public std::iterator + <std::input_iterator_tag, T, ptrdiff_t, T*, T&> + { + protected: + input_iterator_wrapper() + { } + + public: + typedef BoundsContainer<T> ContainerType; + T* ptr; + ContainerType* SharedInfo; + + input_iterator_wrapper(T* _ptr, ContainerType* SharedInfo_in) + : ptr(_ptr), SharedInfo(SharedInfo_in) + { ITERATOR_VERIFY(ptr >= SharedInfo->first && ptr <= SharedInfo->last); } + + input_iterator_wrapper(const input_iterator_wrapper& in) + : ptr(in.ptr), SharedInfo(in.SharedInfo) + { } + + bool + operator==(const input_iterator_wrapper& in) const + { + ITERATOR_VERIFY(SharedInfo != NULL && SharedInfo == in.SharedInfo); + ITERATOR_VERIFY(ptr>=SharedInfo->first && in.ptr>=SharedInfo->first); + return ptr == in.ptr; + } + + bool + operator!=(const input_iterator_wrapper& in) const + { + return !(*this == in); + } + + T& + operator*() const + { + ITERATOR_VERIFY(SharedInfo && ptr < SharedInfo->last); + ITERATOR_VERIFY(ptr >= SharedInfo->first); + return *ptr; + } + + T* + operator->() const + { + return &**this; + } + + input_iterator_wrapper& + operator=(const input_iterator_wrapper& in) + { + ptr = in.ptr; + SharedInfo = in.SharedInfo; + return *this; + } + + input_iterator_wrapper& + operator++() + { + ITERATOR_VERIFY(SharedInfo && ptr < SharedInfo->last); + ITERATOR_VERIFY(ptr>=SharedInfo->first); + ptr++; + SharedInfo->first=ptr; + return *this; + } + + void + operator++(int) + { + ++*this; + } + }; + + + /** + * @brief forward_iterator wrapper for pointer + * + * This class takes a pointer and wraps it to provide exactly + * the requirements of a forward_iterator. It should not be + * instansiated directly, but generated from a test_container + */ + template<class T> + struct forward_iterator_wrapper:public input_iterator_wrapper<T> + { + typedef BoundsContainer<T> ContainerType; + typedef std::forward_iterator_tag iterator_category; + forward_iterator_wrapper(T* _ptr, ContainerType* SharedInfo_in) + :input_iterator_wrapper<T>(_ptr, SharedInfo_in) + { } + + forward_iterator_wrapper(const forward_iterator_wrapper& in) + :input_iterator_wrapper<T>(in) + { } + + forward_iterator_wrapper() + { + this->ptr = NULL; + this->SharedInfo = NULL; + } + + T& + operator*() const + { + ITERATOR_VERIFY(this->SharedInfo && this->ptr < this->SharedInfo->last); + return *(this->ptr); + } + + T* + operator->() const + { return &**this; } + + forward_iterator_wrapper& + operator++() + { + ITERATOR_VERIFY(this->SharedInfo && this->ptr < this->SharedInfo->last); + this->ptr++; + return *this; + } + + forward_iterator_wrapper + operator++(int) + { + forward_iterator_wrapper<T> tmp = *this; + ++*this; + return tmp; + } + }; + + /** + * @brief bidirectional_iterator wrapper for pointer + * + * This class takes a pointer and wraps it to provide exactly + * the requirements of a forward_iterator. It should not be + * instansiated directly, but generated from a test_container + */ + template<class T> + struct bidirectional_iterator_wrapper:public forward_iterator_wrapper<T> + { + typedef BoundsContainer<T> ContainerType; + typedef std::bidirectional_iterator_tag iterator_category; + bidirectional_iterator_wrapper(T* _ptr, ContainerType* SharedInfo_in) + :forward_iterator_wrapper<T>(_ptr, SharedInfo_in) + { } + + bidirectional_iterator_wrapper(const bidirectional_iterator_wrapper& in) + :forward_iterator_wrapper<T>(in) + { } + + bidirectional_iterator_wrapper(): forward_iterator_wrapper<T>() + { } + + bidirectional_iterator_wrapper& + operator=(const bidirectional_iterator_wrapper& in) + { + this->ptr = in.ptr; + this->SharedInfo = in.SharedInfo; + return *this; + } + + bidirectional_iterator_wrapper& + operator++() + { + ITERATOR_VERIFY(this->SharedInfo && this->ptr < this->SharedInfo->last); + this->ptr++; + return *this; + } + + bidirectional_iterator_wrapper + operator++(int) + { + bidirectional_iterator_wrapper<T> tmp = *this; + ++*this; + return tmp; + } + + bidirectional_iterator_wrapper& + operator--() + { + ITERATOR_VERIFY(this->SharedInfo && this->ptr > this->SharedInfo->first); + this->ptr--; + return *this; + } + + bidirectional_iterator_wrapper + operator--(int) + { + bidirectional_iterator_wrapper<T> tmp = *this; + --*this; + return tmp; + } + }; + + /** + * @brief random_access_iterator wrapper for pointer + * + * This class takes a pointer and wraps it to provide exactly + * the requirements of a forward_iterator. It should not be + * instansiated directly, but generated from a test_container + */ + template<class T> + struct random_access_iterator_wrapper:public bidirectional_iterator_wrapper<T> + { + typedef BoundsContainer<T> ContainerType; + typedef std::random_access_iterator_tag iterator_category; + random_access_iterator_wrapper(T* _ptr, ContainerType* SharedInfo_in) + : bidirectional_iterator_wrapper<T>(_ptr, SharedInfo_in) + { } + + random_access_iterator_wrapper(const random_access_iterator_wrapper<T>& in) + : bidirectional_iterator_wrapper<T>(in) + { } + + random_access_iterator_wrapper():bidirectional_iterator_wrapper<T>() + { } + + random_access_iterator_wrapper& + operator=(const random_access_iterator_wrapper& in) + { + this->ptr = in.ptr; + this->SharedInfo = in.SharedInfo; + } + + random_access_iterator_wrapper& + operator++() + { + ITERATOR_VERIFY(this->SharedInfo && this->ptr < this->SharedInfo->last); + this->ptr++; + return *this; + } + + random_access_iterator_wrapper + operator++(int) + { + random_access_iterator_wrapper<T> tmp = *this; + ++*this; + return tmp; + } + + random_access_iterator_wrapper& + operator--() + { + ITERATOR_VERIFY(this->SharedInfo && this->ptr > this->SharedInfo->first); + this->ptr--; + return *this; + } + + random_access_iterator_wrapper + operator--(int) + { + random_access_iterator_wrapper<T> tmp = *this; + ++*this; + return tmp; + } + + random_access_iterator_wrapper& + operator+=(ptrdiff_t n) + { + if(n > 0) + { + ITERATOR_VERIFY(n <= this->SharedInfo->last - this->ptr); + this->ptr += n; + } + else + { + ITERATOR_VERIFY(n <= this->ptr - this->SharedInfo->first); + this->ptr += n; + } + return *this; + } + + random_access_iterator_wrapper + operator+(ptrdiff_t n) + { + random_access_iterator_wrapper<T> tmp = *this; + return tmp += n; + } + + random_access_iterator_wrapper& + operator-=(ptrdiff_t n) + { return *this += -n; } + + random_access_iterator_wrapper + operator-(ptrdiff_t n) + { + random_access_iterator_wrapper<T> tmp = *this; + return tmp -= n; + } + + ptrdiff_t + operator-(const random_access_iterator_wrapper<T>& in) + { + ITERATOR_VERIFY(this->SharedInfo == in.SharedInfo); + return this->ptr - in.ptr; + } + + T& + operator[](ptrdiff_t n) + { return *(this + n); } + + bool + operator<(const random_access_iterator_wrapper<T>& in) const + { + ITERATOR_VERIFY(this->SharedInfo == in.SharedInfo); + return this->ptr < in.ptr; + } + + bool + operator>(const random_access_iterator_wrapper<T>& in) const + { + return in < *this; + } + + bool + operator>=(const random_access_iterator_wrapper<T>& in) const + { + return !(*this < in); + } + + bool + operator<=(const random_access_iterator_wrapper<T>& in) const + { + return !(*this > in); + } + }; + + + /** + * @brief A container-type class for holding iterator wrappers + * test_container takes two parameters, a class T and an iterator + * wrapper templated by T (for example forward_iterator_wrapper<T>. + * It takes two pointers representing a range and presents them as + * a container of iterators. + */ + template <class T, template<class T> class ItType> + struct test_container + { + typename ItType<T>::ContainerType bounds; + test_container(T* _first, T* _last):bounds(_first, _last) + { } + + ItType<T> + it(int pos) + { + ITERATOR_VERIFY(pos >= 0 && pos <= (bounds.last - bounds.first)); + return ItType<T>(bounds.first + pos, &bounds); + } + + ItType<T> + it(T* pos) + { + ITERATOR_VERIFY(pos >= bounds.first && pos <= bounds.last); + return ItType<T>(pos, &bounds); + } + + ItType<T> + begin() + { return it(bounds.first); } + + ItType<T> + end() + { return it(bounds.last); } + }; +} +#endif |
