concurrent_vector.h

C语言库函数的原型,有用的拿去

/***
* ==++==
*
* Copyright (c) Microsoft Corporation.  All rights reserved.
* Microsoft would like to acknowledge that this concurrency data structure implementation
* is based on Intel抯 implementation in its Threading Building Blocks ("Intel Material").
*
* ==--==
* =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
*
* concurrent_vector.h
*
* =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
****/

/*
    Intel Material Copyright 2005-2008 Intel Corporation.  All Rights Reserved.
*/


#pragma once

#include <crtdefs.h>
#include <memory>
#include <iterator>
#include <limits>
#include <algorithm>
#include <cstring>
#include <crtdbg.h>
#include <concrt.h>

#if !(defined (_M_AMD64) || defined (_M_IX86))
    #error ERROR: Concurrency Runtime is supported only on X64 and X86 architectures.
#endif  /* !(defined (_M_AMD64) || defined (_M_IX86)) */

#if defined (_M_CEE)
    #error ERROR: Concurrency Runtime is not supported when compiling /clr.
#endif  /* defined (_M_CEE) */

#pragma pack(push,_CRT_PACKING)

/// <summary>
///     The <c>Concurrency</c> namespace provides classes and functions that give you access to the Concurrency Runtime,
///     a concurrent programming framework for C++. For more information, see <see cref="Concurrency Runtime"/>.
/// </summary>
/**/
namespace Concurrency
{

template<typename _Ty, class _Ax = std::allocator<_Ty> >
class concurrent_vector;

namespace details
{

    // Bad allocation marker
    #define _BAD_ALLOC_MARKER reinterpret_cast<void*>(63)

    // Base class of concurrent vector implementation.
    class _Concurrent_vector_base_v4
    {
    protected:

        // Basic types declarations
        typedef size_t _Segment_index_t;
        typedef size_t _Size_type;

        // Size constants
        static const _Segment_index_t _Default_initial_segments = 1; // 2 initial items

        // Number of slots for segment's pointers inside the class
        static const _Segment_index_t _Pointers_per_short_table = 3; // to fit into 8 words of entire structure
        static const _Segment_index_t _Pointers_per_long_table = sizeof(_Segment_index_t) * 8; // one segment per bit

        // Segment pointer. Can be zero-initialized
        struct _Segment_t
        {
            void* _My_array;
        };

        // Data fields

        // allocator function pointer
        void* (*_My_vector_allocator_ptr)(_Concurrent_vector_base_v4 &, size_t);

        // embedded storage of segment pointers
        _Segment_t _My_storage[_Pointers_per_short_table];

        // Methods

        _Concurrent_vector_base_v4()
        {
            _My_early_size = 0;
            _My_first_block = 0; // here is not _Default_initial_segments
            for( _Segment_index_t _I = 0; _I < _Pointers_per_short_table; _I++)
                _My_storage[_I]._My_array = NULL;
            _My_segment = _My_storage;
        }
        _CRTIMP2 ~_Concurrent_vector_base_v4();

        _CRTIMP2 static _Segment_index_t __cdecl _Segment_index_of( _Size_type _Index );

        static _Segment_index_t _Segment_base( _Segment_index_t _K )
        {
            return (_Segment_index_t(1)<<_K & ~_Segment_index_t(1));
        }

        static _Segment_index_t _Segment_base_index_of( _Segment_index_t &_Index )
        {
            _Segment_index_t _K = _Segment_index_of( _Index );
            _Index -= _Segment_base(_K);
            return _K;
        }

        static _Size_type _Segment_size( _Segment_index_t _K )
        {
            return _Segment_index_t(1)<<_K; // fake value for _K==0
        }

        // An operation on an n-element array starting at begin.
        typedef void (*_My_internal_array_op1)(void* _Begin, _Size_type _N );

        // An operation on n-element destination array and n-element source array.
        typedef void (*_My_internal_array_op2)(void* _Dst, const void* _Src, _Size_type _N );

        // Internal structure for shrink_to_fit()
        struct _Internal_segments_table
        {
            _Segment_index_t _First_block;
            void* _Table[_Pointers_per_long_table];
        };

        _CRTIMP2 void _Internal_reserve( _Size_type _N, _Size_type _Element_size, _Size_type _Max_size );
        _CRTIMP2 _Size_type _Internal_capacity() const;
        void _Internal_grow( _Size_type _Start, _Size_type _Finish, _Size_type _Element_size, _My_internal_array_op2 _Init, const void *_Src );
        _Size_type _Internal_grow_segment( const _Size_type _Start, _Size_type _Finish, _Size_type _Element_size, _Segment_t** _PPSegment, _Size_type* _PSegStart, _Size_type* _PSegFinish );
        _CRTIMP2 _Size_type _Internal_grow_by( _Size_type _Delta, _Size_type _Element_size, _My_internal_array_op2 _Init, const void *_Src );
        _CRTIMP2 void* _Internal_push_back( _Size_type _Element_size, _Size_type& _Index );
        _CRTIMP2 _Segment_index_t _Internal_clear( _My_internal_array_op1 _Destroy );
        void _Internal_truncate( _Size_type _Old_size, _Size_type _New_size, _Size_type _Element_size, _My_internal_array_op1 _Destroy);
        _CRTIMP2 void* _Internal_compact( _Size_type _Element_size, void *_Table, _My_internal_array_op1 _Destroy, _My_internal_array_op2 _Copy );
        _CRTIMP2 void _Internal_copy( const _Concurrent_vector_base_v4& _Src, _Size_type _Element_size, _My_internal_array_op2 _Copy );
        _CRTIMP2 void _Internal_assign( const _Concurrent_vector_base_v4& _Src, _Size_type _Element_size,
                              _My_internal_array_op1 _Destroy, _My_internal_array_op2 _Assign, _My_internal_array_op2 _Copy );
        _CRTIMP2 void _Internal_throw_exception(_Size_type) const;
        _CRTIMP2 void _Internal_swap(_Concurrent_vector_base_v4&);

        _CRTIMP2 void _Internal_resize( _Size_type _New_size, _Size_type _Element_size, _Size_type _Max_size, _My_internal_array_op1 _Destroy, _My_internal_array_op2 _Init, const void* _Src);
        _CRTIMP2 _Size_type _Internal_grow_to_at_least_with_result( _Size_type _New_size, _Size_type _Element_size, _My_internal_array_op2 _Init, const void *_Src );

        // count of segments in the first block
        _Subatomic<_Size_type> _My_first_block;

        // Requested size of vector
        _Subatomic<_Size_type> _My_early_size;

        // Pointer to the segments table
        _Subatomic<_Segment_t*> _My_segment;


    private:
        // Private functionality
        class _Helper;
        friend class _Helper;
    };

    typedef _Concurrent_vector_base_v4 _Concurrent_vector_base;

    // Meets requirements of a forward iterator for STL.*/
    /** _Value is either the _Ty or const _Ty type of the container. */
    template<typename _Container, typename _Value>
    class _Vector_iterator
    {
        // concurrent_vector over which we are iterating.
        _Container* _My_vector;

        // Index into the vector
        size_t _My_index;

        // Caches _My_vector-&gt;_Internal_subscript(_My_index)
        /** NULL if cached value is not available */
        mutable _Value* _My_item;

        template<typename _C, typename _Ty>
        friend _Vector_iterator<_C,_Ty> operator+( ptrdiff_t _Offset, const _Vector_iterator<_C,_Ty>& _Vec );

        template<typename _C, typename _Ty, typename _U>
        friend bool operator==( const _Vector_iterator<_C,_Ty>&, const _Vector_iterator<_C,_U>& );

        template<typename _C, typename _Ty, typename _U>
        friend bool operator<( const _Vector_iterator<_C,_Ty>&, const _Vector_iterator<_C,_U>& );

        template<typename _C, typename _Ty, typename _U>
        friend ptrdiff_t operator-( const _Vector_iterator<_C,_Ty>&, const _Vector_iterator<_C,_U>& );

        template<typename _C, typename _U>
        friend class ::Concurrency::details::_Vector_iterator;

        template<typename _Ty, class _Ax>
        friend class ::Concurrency::concurrent_vector;

        _Vector_iterator( const _Container& _Vec, size_t _Index, void* _Ptr = NULL )
            : _My_vector(const_cast<_Container*>(&_Vec)),
              _My_index(_Index),
              _My_item(static_cast<_Value*>(_Ptr))
        {
        }

    public:
        // Default constructor
        _Vector_iterator()
            : _My_vector(NULL), _My_index(~size_t(0)), _My_item(NULL)
        {
        }

        _Vector_iterator( const _Vector_iterator<_Container,typename _Container::value_type>& _Other )
            : _My_vector(_Other._My_vector),
              _My_index(_Other._My_index),
              _My_item(_Other._My_item)
        {
        }

        _Vector_iterator operator+( ptrdiff_t _Offset ) const
        {
            return _Vector_iterator( *_My_vector, _My_index+_Offset );
        }
        _Vector_iterator& operator+=( ptrdiff_t _Offset )
        {
            _My_index+=_Offset;
            _My_item = NULL;
            return *this;
        }
        _Vector_iterator operator-( ptrdiff_t _Offset ) const
        {
            return _Vector_iterator( *_My_vector, _My_index-_Offset );
        }
        _Vector_iterator& operator-=( ptrdiff_t _Offset )
        {
            _My_index-=_Offset;
            _My_item = NULL;
            return *this;
        }
        _Value& operator*() const
        {
            _Value* _Item = _My_item;
            if( !_Item )
                _Item = _My_item = &_My_vector->_Internal_subscript(_My_index);
            _ASSERTE( _Item==&_My_vector->_Internal_subscript(_My_index));  // corrupt cache
            return *_Item;
        }
        _Value& operator[]( ptrdiff_t _K ) const
        {
            return _My_vector->_Internal_subscript(_My_index+_K);
        }
        _Value* operator->() const
        {
            return &operator*();
        }

        // Pre increment
        _Vector_iterator& operator++()
        {
            size_t _K = ++_My_index;
            if( _My_item )
            {
                // Following test uses 2's-complement wizardry
                if( (_K& (_K-2))==0 )
                {
                    // _K is a power of two that is at least _K-2
                    _My_item= NULL;
                }
                else
                {
                    ++_My_item;
                }
            }
            return *this;
        }

        // Pre decrement
        _Vector_iterator& operator--()
        {
            _ASSERTE( _My_index>0 ); // operator--() applied to iterator already at beginning of concurrent_vector
            size_t _K = _My_index--;
            if( _My_item )
            {
                // Following test uses 2's-complement wizardry
                if( (_K& (_K-2))==0 )
                {
                    // k is a power of two that is at least k-2
                    _My_item= NULL;
                }
                else
                {
                    --_My_item;
                }
            }
            return *this;
        }

        // Post increment
        _Vector_iterator operator++(int)
        {
            _Vector_iterator _Result = *this;
            operator++();
            return _Result;
        }

        // Post decrement
        _Vector_iterator operator--(int)
        {
            _Vector_iterator _Result = *this;
            operator--();
            return _Result;
        }

        // STL support