cnc.h

//********************************************************************************
// Copyright 2007-2010 Intel Corporation All Rights Reserved.                   **
//                                                                              **
// The source code contained or described herein and all documents related to   **
// the source code ("Material") are owned by Intel Corporation or its suppliers **
// or licensors. Title to the Material remains with Intel Corporation or its    **
// suppliers and licensors. The Material contains trade secrets and proprietary **
// and confidential information of Intel or its suppliers and licensors. The    **
// Material is protected by worldwide copyright and trade secret laws and       **
// treaty provisions. No part of the Material may be used, copied, reproduced,  **
// modified, published, uploaded, posted, transmitted, distributed, or          **
// disclosed in any way without Intel's prior express written permission.       **
//                                                                              **
// No license under any patent, copyright, trade secret or other intellectual   **
// property right is granted to or conferred upon you by disclosure or delivery **
// of the Materials, either expressly, by implication, inducement, estoppel or  **
// otherwise. Any license under such intellectual property rights must be       **
// express and approved by Intel in writing.                                    **
//********************************************************************************

#ifndef _CnC_H_
#define _CnC_H_

#if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
    // Workaround for overzealous compiler warnings 
# pragma warning (push)
# pragma warning (disable: 4251 4275)
#endif


#include <cnc/internal/tag_collection_base.h>
#include <cnc/internal/item_collection_base.h>
#include <cnc/internal/context_base.h>
#include <cnc/internal/no_range.h>

namespace CnC {

    typedef int error_type;
    // forward declaration
    template< class T > class context;
    struct debug;

    /// Steps return CNC_Success if execution was successful
    const int CNC_Success = 0;
    /// Steps return CNC_Failure if execution failed
    const int CNC_Failure = 1;

    /// \brief A tag collection is a set of tags of the same type. It is
    /// used to prescribe steps.  By default, it is not stored.
    ///
    /// Tag must provide copy and default constructors and the assigment
    /// operator.
    ///
    /// If Tag is not convertable into size_t, a suitable hash_compare
    /// class must be provided which satisifies the requirements for
    /// tbb::concurrent_hash_map.  The default cnc_tag_hash_compare works
    /// for types that can be converted to size_t and have an
    /// operator==. You can provide a specialized template for
    /// cnc_tag_hash_compare or specify and implement your own compatible
    /// class.
    template< typename Tag, typename Range = Internal::no_range, typename hash_compare = cnc_tag_hash_compare< Tag > >
    class /*CNC_API*/ tag_collection
    {
    public:
        /// the tag type
        typedef Tag tag_type;

        /// const forward iterator as in STL
        class const_iterator;

        /// \brief constructor which registers collection with given context
        ///
        /// \param ctxt the context this collection belongs to
        /// \param preserveTags when requested, the tag collection can preserve tags, by default tags are not stored
        template< class Derived >
        tag_collection( context< Derived > * ctxt, bool preserveTags = false );

        /// \brief prescribe the associated step.  If we are preserving tags for this collection, make a copy of the tag and store it in the collection.
        /// \param  t the tag to be put
        void put( const Tag & t );

        /// \brief prescribe an entire range of tags
        ///
        /// \param r  A range, which is potentially splittible through a partitioner.
        ///           Following the TBB range/splittable concept, extended by STL container requirements, 
        ///           a range R must provide the following interface:
        ///              - R::R( const R& ) : Copy constructor.
        ///              - bool R::empty() const : true if range is empty.
        ///              - bool R::is_divisible() const : true if range can be partitioned into two subranges.
        ///              - R::R( R& r, tbb::split ) : Split r into two subranges.
        ///              - const_iterator : forward iterator (operator++, operator tag_type() const)
        ///                                 to make it work with tbb::blocked_range, the cast operator is used instead of operator*().
        ///              - const_iterator begin() : first member of range
        ///              - const_iterator end() : Exclusive upper bound on range
        /// \param part optionally a partitioner can be specified, \see default_partitioner for the expected interface
        void put_range( const Range & r );
        void put_range( const Internal::no_range & ) const;

        /// \brief Declare the prescription relationship between a tag collection
        /// and a step collection.
        ///
        /// \param s class representing step collection. s is required to
        /// provide the following const method, where Arg a is the optional
        /// parameter described below.
        ///   \code
        ///   int execute( const Tag & tag, Arg & a ) const;
        ///   \endcode
        /// A copy of s will be created by calling its copy constructor.
        ///
        /// \param tuner You can use default_tuner or define your own tuner to
        /// specify the scheduling priority for the excution of a step, and also
        /// the data dependencies for the step.
        ///
        /// \param arg This argument will be the parameter passed to
        ///            Step::execute and the tuner methods.  The object must exist as
        ///            long as instances of the given step might be executed. Usually
        ///            arg will be the containing context.
        ///
        /// \return 0 if succeeded, error code otherwise
        template< typename Step, typename Tuner, typename Arg >
        error_type prescribe( const Step & s, const Tuner & t, Arg & arg );

        /// \brief returns begin() as in STL containers
        /// \note iteration through collections is not thread safe, use it only between calls to CnC::context::wait() and putting tags
        const_iterator begin() const;

        /// \brief returns end() as in STL containers
        /// \note iteration through collections is not thread safe, use it only between calls to CnC::context::wait() and putting tags
        const_iterator end() const;

        /// \brief removes all of the tag instances from the collection
        void reset();

        /// returns number of elements in collection
        size_t size();

        /// returns true if size()==0, false otherwise
        bool empty();

    private:
        Internal::tag_collection_base< Tag, Range, hash_compare > m_tagCollection;
        //template< class T > friend class context;
        friend struct ::CnC::debug;
    };

    /// \brief An item collection is a mapping from tags to items.
    ///
    /// Tag and Item must provide copy and default constructors and the
    /// assigment operator.
    ///
    /// If Tag is not convertable into size_t, a suitable
    /// cnc_tag_hash_compare struct must be provided which satisifies the
    /// requirements for tbb::concurrent_hash_map. The default
    /// cnc_tag_hash_compare works for types that can be converted to
    /// size_t and have an operator==. You can provide a specialized
    /// template for cnc_tag_hash_compare or specify and implement your own
    /// compatible class.
    /// 
    /// The CnC runtime will make a copy of your item when it is 'put' into
    /// the item_collection.  The CnC runtime will delete the copied item
    /// copy once the get-count reaches 0 (or, if no get-count was
    /// provided, once the collection is destroyed).  If the item-type is a
    /// pointer type, the runtime will not delete the memory the item
    /// points to.  
    template< typename Tag, typename Item, typename hash_compare = cnc_tag_hash_compare< Tag > >
    class /*CNC_API*/ item_collection
    {
    public:
        /// the tag type
        typedef Tag tag_ype;

        /// const forward iterator as in STL
        class const_iterator;

        /// \brief constructor which registers collection with given context
        ///
        /// \param ctxt the context this collection belongs to
        template< class Derived >
        item_collection( context< Derived > * ctxt );

        /// \brief make copies of the item and the tag and store them in the collection.
        /// \param tag        the tag identifying the item
        /// \param item       the item to be copied and stored
        /// \param get_count  after get_count many 'get()'s the item can be removed
        ///                  by default, the item is not removed until the collection is deleted.
        void put( const Tag & tag, const Item & item, int get_count = -1 );

        /// \brief get an item
        /// \param  tag the tag identifying the item
        /// \param  item reference to item to store result in
        /// \throw DataNotReady throws exception if data not yet available.
        void get( const Tag & tag, Item & item ) const;

        /// \brief try to get an item and store it in given object (non-blocking)
        ///        
        /// \attention This method is unsafe: you can create non-deterministic results if you decide to 
        ///            to perform semantically relevant actions if an item is unavailable (returns false)
        ///
        /// If the item is unavailable, it does not change item.
        /// Make sure you call flush_gets() after last call to this method (of any item collection) within a step.
        /// In any case, you must check the return value before accessing the item.
        /// \param  tat the tag identifying the item
        /// \param  item reference to item to store result in
        /// \return true if item is available
        /// \throw DataNotReady might throw exception if data not available (yet)
        bool unsafe_get( const Tag & t, Item & i ) const;

        /// \brief returns begin() as in STL containers
        /// \note iteration through collections is not thread safe, use it only between calls to CnC::context::wait() and putting tags
        const_iterator begin() const;

        /// \brief returns end() as in STL containers
        /// \note iteration through collections is not thread safe, use it only between calls to CnC::context::wait() and putting tags
        const_iterator end() const;

        /// \brief removes all of the item instances from the collection
        void reset();

        /// returns number of elements in collection
        size_t size();

        /// returns true if size()==0, false otherwise
        bool empty();

    private:
        Internal::item_collection_base< Tag, Item, hash_compare > m_itemCollection;
        friend struct ::CnC::debug;
        friend class Internal::step_delayer;
        friend class const_iterator;
    };

    namespace Internal {
        class distributor;
        template< class T > class creator;
    }

    /// \brief CnC context bringing together collections and steps and
    /// specifies the prescription relationship.
    ///
    /// The user needs to derive his or her own context from the CnC::context.
    /// The template argument to context is the user's context class itself.
    ///
    /// For example,
    /// @code
    ///   struct my_context : public CnC::context< my_context >
    ///   {
    ///      CnC::tag_collection<int> oddNums;
    ///      CnC::item_collection<int,int> primes;
    ///      my_context() 
    ///          : CnC::context< my_context >(),
    ///            oddNums( this ),
    ///            primes( this )
    ///      {
    ///          prescribe( oddNums, FindPrimes() );
    ///      }
    ///   };
    /// @endcode
    ///
    /// Several contexts can be created and executed simultaneously.
    ///
    /// Execution starts as soon as a step is prescribed.
    /// All ready steps will be executed even if CnC::context::wait() is never be called.
    ///
    /// It is recommended to declare collections as members of a context derived from CnC::context.
    /// This yields more maintanable code and future versions of CnC may require this convention.
    template< class Derived >
    class /*CNC_API*/ context : private Internal::context_base
    {
    public:
        /// default constructor
        context();
        /// destructor
        virtual ~context() {}

        /// \brief Convenient was to declare the prescription relationship between a tag
        /// collection and a step collection.
        ///
        /// \see tag_collection::prescribe
        ///
        /// \param step class/object representing step collection. 
        /// \param tuner is optional.  By default this argument is CnC:default_tuner. 
        /// \param arg is optional.  By default this argument is the derived context class. 
        /// \return 0 if succeeded, error code otherwise
        ///
        // default template arguments for functions not available before C++0X, need to replicate 'prescribe'
        template< typename TagColl, typename Step, typename Tuner, typename Arg >
        error_type prescribe( TagColl & tc, const Step & step, const Tuner & tuner, Arg & arg );
        template< typename TagColl, typename Step, typename Tuner >
        error_type prescribe( TagColl & tc, const Step & step, const Tuner & tuner);
        template< typename TagColl, typename Step >
        error_type prescribe( TagColl & tc, const Step & step );

        /// \brief wait until all the steps prescribed by this context have completed execution.
        /// \return 0 if succeeded, error code otherwise
        error_type wait();

        /// \brief used with the preschedule tuner to finalize 'gets' in the pre-execution of a step
        ///
        /// Call this after last call to the non-blocking item_collection::unsafe_get method.
        void flush_gets();

        /// reset all collections of this context
        void reset();

        /// \brief Execute f( i ) for every i in {first <= i=first+step*x < last and 0 <= x}.
        ///
        /// For different values of i, function execution might occur in parallel.
        /// Returns functor object ocne all iterations have been executed.
        /// Type Index must support operator+.
        /// It uses the tuner default_tuner< Index, derived >
        /// \param first  starting index of parallel iteration
        /// \param last   iteration stops before reaching last
        /// \param step   iteration step: increase ireation index by step in each iteration
        /// \param f      function to be executed
        /// \param gets_items      true (default) if function gets items, false otherwise (might perform better)
        template< class Index, class Functor >
        Functor parallel_for( Index first, Index last, Index step, const Functor & f, bool gets_items = true );

        /// \brief Execute f( i ) for every i in {first <= i=first+step*x < last and 0 <= x}.
        ///
        /// For different values of i, function execution might occur in parallel.
        /// Returns functor object ocne all iterations have been executed.
        /// Type Index must support operator+.
        /// \param first  starting index of parallel iteration
        /// \param last   iteration stops before reaching last
        /// \param step   iteration step: increase ireation index by step in each iteration
        /// \param f      function to be executed
        /// \param tuner  tuner, must accept Index as tag and derived as Arg
        template< class Index, class Functor, class Tuner >
        Functor parallel_for( Index first, Index last, Index step, const Functor & f, const Tuner & tuner );

    private:
        virtual int factory_id();
        template< class Range, class Coll >
        void divide_and_put( Range & range, int grain, Coll * coll, Internal::scheduler_i * sched );
        friend struct ::CnC::debug;
        friend class ::CnC::Internal::distributor;
        template< class T > friend class ::CnC::Internal::creator;
    };

    /// \brief Execute f( i ) for every i in {first <= i=first+step*x < last and 0 <= x}.
    ///
    /// For different values of i, function execution might occur in parallel.
    /// Returns functor object ocne all iterations have been executed.
    /// Type Index must support operator+.
    /// \param first  starting index of parallel iteration
    /// \param last   iteration stops before reaching last
    /// \param f      function to be executed
    /// \param gets_items  true (default) if function gets items, false otherwise (might perform better)
    template< class Index, class Functor >
    Functor parallel_for( Index first, Index last, Index step, const Functor & f, bool gets_items = true );

} // namespace cnc

#include <cnc/internal/tag_collection.h>
#include <cnc/internal/item_collection.h>
#include <cnc/internal/context.h>
#include <cnc/internal/parallel_for.h>

#if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
# pragma warning (pop)
# pragma warning( disable : 4355 )
#endif // warnings 4251 4275 are back, 4355 is hidden

#endif // _CnC_H_