TwoLevelIterator.h File Reference

Two Level Iterator for Per-thread workList-*- C++ -*-. More...

#include "Galois/config.h"
#include <iterator>
#include <cstdlib>
#include <cassert>

Classes
class	Galois::TwoLevelIterBase< Outer, Inner, InnerBegFn, InnerEndFn >
	Common functionality of TwoLevelIterators. More...
class	Galois::TwoLevelFwdIter< Outer, Inner, InnerBegFn, InnerEndFn >
	Two-Level forward iterator. More...
class	Galois::TwoLevelBiDirIter< Outer, Inner, InnerBegFn, InnerEndFn >
	Two-Level bidirectional iterator. More...
class	Galois::TwoLevelRandIter< Outer, Inner, InnerBegFn, InnerEndFn >
	Two-Level random access iterator. More...
struct	Galois::TwoLevelIteratorImpl::ByCategory< Outer, Inner, InnerBegFn, InnerEndFn, Cat >
struct	Galois::TwoLevelIteratorImpl::ByCategory< Outer, Inner, InnerBegFn, InnerEndFn, std::forward_iterator_tag >
struct	Galois::TwoLevelIteratorImpl::ByCategory< Outer, Inner, InnerBegFn, InnerEndFn, std::bidirectional_iterator_tag >
struct	Galois::TwoLevelIteratorImpl::ByCategory< Outer, Inner, InnerBegFn, InnerEndFn, std::random_access_iterator_tag >
struct	Galois::ChooseTwoLevelIterator< Outer, Inner, InnerBegFn, InnerEndFn >
	Type function to select appropriate two-level iterator. More...
struct	Galois::TwoLevelIteratorImpl::GetBegin< C >
struct	Galois::TwoLevelIteratorImpl::GetEnd< C >
struct	Galois::TwoLevelIteratorImpl::GetCbegin< C >
struct	Galois::TwoLevelIteratorImpl::GetCend< C >
struct	Galois::TwoLevelIteratorImpl::GetRbegin< C >
struct	Galois::TwoLevelIteratorImpl::GetRend< C >
struct	Galois::TwoLevelIteratorImpl::GetCRbegin< C >
struct	Galois::TwoLevelIteratorImpl::GetCRend< C >
struct	Galois::TwoLevelIteratorImpl::IsConstIter< C, I >
struct	Galois::TwoLevelIteratorImpl::IsConstIter< C, typename C::const_iterator >
struct	Galois::TwoLevelIteratorImpl::IsRvrsIter< C, I >
struct	Galois::TwoLevelIteratorImpl::IsRvrsIter< C, typename C::reverse_iterator >
struct	Galois::TwoLevelIteratorImpl::IsRvrsConstIter< C, I >
struct	Galois::TwoLevelIteratorImpl::IsRvrsConstIter< C, typename C::const_reverse_iterator >
struct	Galois::TwoLevelIteratorImpl::GetStlIterKind< C, I >
struct	Galois::TwoLevelIteratorImpl::ChooseStlIter< C, I, StlIterKind >
struct	Galois::TwoLevelIteratorImpl::ChooseStlIter< C, I, NORMAL >
struct	Galois::TwoLevelIteratorImpl::ChooseStlIter< C, I, CONST >
struct	Galois::TwoLevelIteratorImpl::ChooseStlIter< C, I, REVERSE >
struct	Galois::TwoLevelIteratorImpl::ChooseStlIter< C, I, CONST_REVERSE >
struct	Galois::TwoLevelIteratorImpl::ChooseStlTwoLevelIterImpl< Outer, Inner >
struct	Galois::TwoLevelIteratorImpl::StlInnerIsIterator< Outer >
struct	Galois::TwoLevelIteratorImpl::StlInnerIsConstIterator< Outer >
struct	Galois::TwoLevelIteratorImpl::StlInnerIsRvrsIterator< Outer >
struct	Galois::TwoLevelIteratorImpl::StlInnerIsConstRvrsIterator< Outer >
struct	Galois::ChooseStlTwoLevelIterator< Outer, Inner >
	Type function to select appropriate two-level iterator. More...
Namespaces
namespace	Galois
	Main Galois namespace.
namespace	Galois::TwoLevelIteratorImpl
Enumerations
enum	Galois::TwoLevelIteratorImpl::StlIterKind { Galois::TwoLevelIteratorImpl::NORMAL, Galois::TwoLevelIteratorImpl::CONST, Galois::TwoLevelIteratorImpl::REVERSE, Galois::TwoLevelIteratorImpl::CONST_REVERSE }
Functions
template<typename Iter >
void	Galois::TwoLevelIteratorImpl::safe_decrement (Iter &it, const Iter &beg, const Iter &end, std::forward_iterator_tag)
template<typename Iter >
void	Galois::TwoLevelIteratorImpl::safe_decrement (Iter &it, const Iter &beg, const Iter &end, std::bidirectional_iterator_tag)
template<typename Iter >
void	Galois::TwoLevelIteratorImpl::safe_decrement (Iter &it, const Iter &beg, const Iter &end)
template<typename Outer , typename InnerBegFn , typename InnerEndFn >
ChooseTwoLevelIterator< Outer, typename InnerBegFn::result_type, InnerBegFn, InnerEndFn >::type	Galois::make_two_level_begin (Outer beg, Outer end, InnerBegFn innerBegFn, InnerEndFn innerEndFn)
	Creates two level iterator.
template<typename Outer , typename InnerBegFn , typename InnerEndFn >
ChooseTwoLevelIterator< Outer, typename InnerBegFn::result_type, InnerBegFn, InnerEndFn >::type	Galois::make_two_level_end (Outer beg, Outer end, InnerBegFn innerBegFn, InnerEndFn innerEndFn)
	Creates two level iterator.
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsIterator < Outer >::type	Galois::stl_two_level_begin (Outer beg, Outer end)
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsIterator < Outer >::type	Galois::stl_two_level_end (Outer beg, Outer end)
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsConstIterator < Outer >::type	Galois::stl_two_level_cbegin (Outer beg, Outer end)
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsConstIterator < Outer >::type	Galois::stl_two_level_cend (Outer beg, Outer end)
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsRvrsIterator < Outer >::type	Galois::stl_two_level_rbegin (Outer beg, Outer end)
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsRvrsIterator < Outer >::type	Galois::stl_two_level_rend (Outer beg, Outer end)
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsConstRvrsIterator < Outer >::type	Galois::stl_two_level_crbegin (Outer beg, Outer end)
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsConstRvrsIterator < Outer >::type	Galois::stl_two_level_crend (Outer beg, Outer end)

Detailed Description

Two Level Iterator for Per-thread workList-*- C++ -*-.

License

Galois, a framework to exploit amorphous data-parallelism in irregular programs.

Copyright (C) 2013, The University of Texas at Austin. All rights reserved. UNIVERSITY EXPRESSLY DISCLAIMS ANY AND ALL WARRANTIES CONCERNING THIS SOFTWARE AND DOCUMENTATION, INCLUDING ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR ANY PARTICULAR PURPOSE, NON-INFRINGEMENT AND WARRANTIES OF PERFORMANCE, AND ANY WARRANTY THAT MIGHT OTHERWISE ARISE FROM COURSE OF DEALING OR USAGE OF TRADE. NO WARRANTY IS EITHER EXPRESS OR IMPLIED WITH RESPECT TO THE USE OF THE SOFTWARE OR DOCUMENTATION. Under no circumstances shall University be liable for incidental, special, indirect, direct or consequential damages or loss of profits, interruption of business, or related expenses which may arise from use of Software or Documentation, including but not limited to those resulting from defects in Software and/or Documentation, or loss or inaccuracy of data of any kind.

Description

Two Level Iterator for per-thread workList.

Assumptions

Outer and Inner iterators are default- and copy-constructible
Inner and Outer must be at least forward_iterator_tag
InnerBegFn and InnerEndFn take an argument of type *Outer and return an Inner pointing to begin or end of inner range.
InnerBegFn and InnerEndFn must inherit from std::unary_function so that argument_type and result_type are available.

Important pitfalls to handle

If Outer and Inner have different categories, which category to choose?. The category of Inner can be chosen after (expensively) supporting moving backwards for outer iterators of forward category. Note: Lowest category currently supported is forward iterators.
Prevent Outer from falling outside the [begin,end) range, because calling container functions e.g. outer->begin () and outer->end () is not valid and may cause a segfault.
The initial position of Outer and Inner iterators must be such that calling operator * or operator -> on at two level iterator yields a valid result (if possible). This means advancing the inner iterator to begin of first non-empty container (else to the end of outer). If the outer iterator is initialized to end of the outer range i.e. [end, end), then inner iterator cannot be initialized.
When incrementing (++), the inner iterator should initially be at a valid begin position, but after incrementing may end up at end of an Inner range. So the next valid local begin must be found, else the end of outer should be reached
1. When jumping forward, outer should not go beyond end. After jump is completed, inner may be at local end, so a valid next begin must be found or else end of outer must be reached
When decrementing (--), the inner iterator may initially be uninitialized due to outer being at end (See 3 above). Inner iterator must be brought to a valid location after decrementing, or, else the begin of outer must be reached (and not exceeded).
1. When jumping backward, inner iterator may be uninitialized due to outer being at end.
When jumping forward or backward, check for jump amount being negative.
1. Jumping outside the range of outer cannot be supported.

Author:: <ahassaan@ices.utexas.edu>

TwoLevelIterator.h File Reference

Classes

Namespaces

Enumerations

Functions

Detailed Description

License

Description