restack.h

vsstylemanager1.0.4希望对大家有用啊,

//+---------------------------------------------------------------------------
//
//  Copyright ( C ) Microsoft, 1994 - 2002.
//
//  File:       restack.h
//
//  Functions:  a quick-'n'-dirty, type-unsafe stack used by the iterative
//              regular expression algorithm
//
//  Notes:      Care must be taken when using this stack. You must pop off
//              the correct type of object, otherwise you get garbage. Also,
//              if you push anything that has a non-trivial destructor, then
//              be sure to explicitely pop everything off the stack and don't
//              use the unsafe_long_jump method.
//
//  Author:     Eric Niebler ( [e-mail] )
//
//  History:    11/15/2001   ericne   Created
//
//----------------------------------------------------------------------------

#ifndef HETERO_STACK_H
#define HETERO_STACK_H

#include <string>
#include <utility>
#include <typeinfo>
#include <stdexcept>
#include <functional>

#ifndef REGEX_CDECL
#ifdef _MSC_VER
#define REGEX_CDECL __cdecl
#else
#define REGEX_CDECL
#endif
#endif

#define COMMA ,
#if !defined(_MSC_VER) | 1200 < _MSC_VER
# define REGEX_VC6(x)
# define REGEX_NVC6(x) x
#else
# define REGEX_VC6(x) x
# define REGEX_NVC6(x)
#endif

namespace regex
{

namespace detail
{

// For compile-time assertions that generate
// no run-time overhead.
template< bool f > struct static_assert;
template<>         struct static_assert<true> { static_assert() {} };

// Work-around for a template-template parameter problem on VC7.0
template< typename T > struct type2type { typedef T type; };

template< bool F > struct bool2type { enum { value = F }; };

typedef bool2type<true>  true_t;
typedef bool2type<false> false_t;

#ifdef _MSC_VER
// warning C4127: conditional expression is constant
// warning C4189: local variable is initialized but not referenced
// warning C4244: conversion from 'T' to 'int', possible loss of data
// warning C4510: default constructor could not be generated
// warning C4610: struct can never be instantiated - user defined constructor required
// warning C4800: forcing value to bool 'true' or 'false' (performance warning)
#pragma warning( push )
#pragma warning( disable : 4127 4189 4244 4510 4610 4800 )

// Make sure nobody has tampered with the packing before defining the
// alignof structure
#pragma pack( push )
#pragma pack() // use the default packing
#endif

template< typename T >
class alignof
{
    struct helper
    {
        helper();
        char    m_c;
        T       m_t;
    };
public:
    enum { value = sizeof(helper)-sizeof(T) < sizeof(T) ? sizeof(helper)-sizeof(T) : sizeof(T) };
};

#ifdef _MSC_VER
#pragma pack( pop )
#endif

//
// Type traits
//

typedef char (&yes_type)[1];
typedef char (&no_type)[2];

template< bool >
struct select_helper
{
    template< typename T, typename U >
    struct nested
    {
        typedef T type;
    };
};

template<>
struct select_helper<false>
{
    template< typename T, typename U >
    struct nested
    {
        typedef U type;
    };
};

// For use in conditional typedefs
template< bool F, typename T, typename U >
struct select
{
    typedef typename select_helper<F>::template nested<T,U>::type type;
};

template< typename U >
struct convertible_helper
{
    static yes_type             check( U );
    static no_type  REGEX_CDECL check(...);
};

template< typename T >
struct factory
{
    static T& make();
};

template< typename T, typename U >
struct is_convertible
{
    enum { value = (sizeof(convertible_helper<U>::check(factory<T>::make()))==sizeof(yes_type)) };
};

template< size_t N >
struct is_power_of_two
{
    enum { value = 1==N || 0==(N%2) && is_power_of_two<N/2>::value };
};

template<>
struct is_power_of_two<0>
{
    enum { value = false };
};

// Very primative implementation of is_scalar. This doesn't work
// for void, reference types, array types or function types, but
// we don't use those types from hetero_stack.
struct bool_convertible { bool_convertible(bool); };

template< typename T >
struct is_scalar
{
    enum { value = is_convertible<T,bool_convertible>::value };
};

template< typename T >
struct has_trivial_copy
{
    enum { value = is_scalar<T>::value };
};

template< typename T >
struct has_trivial_assignment
{
    enum { value = is_scalar<T>::value };
};

template< typename T >
struct has_trivial_destructor
{
    enum { value = is_scalar<T>::value };
};

template< bool > struct destroyer_helper
{
    template< typename T >
    static void destroy( T const * pT )
    {
        pT, pT->~T();
    }
};
template<> struct destroyer_helper<true>
{
    template< typename T >
    static void destroy( T const * )
    {
    }
};
template< typename T >
void destroy( T const * pT )
{
    destroyer_helper<has_trivial_destructor<T>::value>::destroy( pT );
}

struct type_vtable
{
    std::type_info const *  typeinfo_ptr;
    size_t             size;
    size_t             aligned_size;
    void (*destroy)( void * );
    void (*copy)( void *, void const * );
};

template< typename T, size_t AlignmentT >
class type_info_ex
{
    static void destroy( void * pv )
    {
        T const * pT = static_cast<T const*>( pv );
        regex::detail::destroy( pT );
        (void)pv;
        (void)pT;
    }
    static void copy( void * dst, void const * src )
    {
        new ( dst ) T( *static_cast<T const *>( src ) );
    }
public:
    static type_vtable const vtable;

    static bool equals( type_vtable const * ptm )
    {
        return ptm == & vtable || *ptm->typeinfo_ptr == typeid(T);
    }
};

template< typename T,size_t AlignmentT >
type_vtable const type_info_ex<T,AlignmentT>::vtable =
{
    &typeid(T),
    sizeof(T),
    ( sizeof(T) + AlignmentT - 1 ) & ~( AlignmentT - 1 ),
    has_trivial_destructor<T>::value ? 0 : &type_info_ex<T,AlignmentT>::destroy,
    &type_info_ex<T,AlignmentT>::copy
};

template< typename T >
inline T & to_type( void * pv )
{
    return *static_cast<T*>( pv );
}

} // namespace detail

// --------------------------------------------------------------------------
//
// Class:       hetero_stack
//
// Description: Fast, heterogeneous stack.
//
// Methods:     allocate        - reserve space on stack
//              unwind          - unwind the stack
//              hetero_stack    - c'tor
//              ~hetero_stack   - d'tor, release all dynamic memory
//              push            - push an object on the stack
//              pop             - pop an object from the stack
//
// Members:     m_first_node    -
//              m_current_node  -
//
// Typedefs:    byte_t            -
//
// History:     10/19/2001 - ericne - Created
//
// --------------------------------------------------------------------------
template
<
    size_t  AlignmentT         = sizeof(void*),
    bool    RuntimeTypeCheckT  = true,  // should we perform run-time type checking?
    bool    AssumePodT         = false, // assume non-throwing copy/assign/destroy for better perf
    size_t  DynamicBlockSizeT  = 4096,  // blocks allocated from heap are this size
    size_t  StaticBlockSizeT   = 1024   // initial block on stack is this size
>
class hetero_stack
{
    typedef unsigned char byte_t;
    typedef detail::type_vtable const* vtable_ptr;

public:

    typedef hetero_stack<AlignmentT,RuntimeTypeCheckT,AssumePodT,DynamicBlockSizeT,StaticBlockSizeT> stack_type;

    template< typename T >
    struct aligned_sizeof
    {
        enum
        {
            // round up sizeof(T) to the nearest multiple of AlignmentT
            no_rtti   = ( sizeof( T ) + AlignmentT - 1 ) & ~( AlignmentT - 1 ),
            with_rtti = RuntimeTypeCheckT ?
                no_rtti + aligned_sizeof<vtable_ptr>::no_rtti :
                no_rtti
        };
    };

private:

    struct stack_node
    {
        struct header
        {
            stack_node * m_back;
            stack_node * m_next;
            byte_t     * m_current; // ptr into m_mem. alloc from here
            byte_t     * m_end;     // ptr to last+1 byte_t in m_mem
        };

        union
        {
            header  m_head;
            byte_t  m_align[ aligned_sizeof<header>::no_rtti ];
        };

        // This is the buffer into which values will be pushed and popped.
        // It is guaranteed to meet the AlignmentT requirements because of
        // the union above.
        byte_t  m_mem[1];

        size_t size() const // throw()
        {
            return static_cast<size_t>( m_head.m_end - m_mem );
        }
    };

    enum
    {
        DYNAMIC_BLOCK_SIZE =
            DynamicBlockSizeT > sizeof( stack_node ) ?
            DynamicBlockSizeT : sizeof( stack_node )
    };

    union
    {
        stack_node  m_node;
        byte_t      m_buf[ aligned_sizeof<stack_node::header>::no_rtti + StaticBlockSizeT ];
    } m_first_node;

    stack_node * m_current_node;

    // Cache these for faster access
    byte_t * m_begin;
    byte_t * m_current;
    byte_t * m_end;

    byte_t * grow( size_t size ) // throw(std::bad_alloc)
    {
        // write the cached value of current into the node.
        // OK to do this even if later statements throw.
        m_current_node->m_head.m_current = m_current;

        // Do we have a node with available memory already?
        if( m_current_node->m_head.m_next )
        {
            // Does this node have enough room?
            if( size <= m_current_node->m_head.m_next->size() )
            {
                m_current_node  = m_current_node->m_head.m_next;
                m_current       = m_current_node->m_head.m_current = m_current_node->m_mem + size;
                m_end           = m_current_node->m_head.m_end;
                return m_begin  = m_current_node->m_mem;
            }

            // Create a new node and insert it into the list
            stack_node * new_node = static_cast<stack_node*>(
                ::operator new( size + offsetof( stack_node, m_mem ) ) );

            new_node->m_head.m_back = m_current_node;
            new_node->m_head.m_next = m_current_node->m_head.m_next;

            m_current = m_end = new_node->m_head.m_current =
                new_node->m_head.m_end = new_node->m_mem + size;

            m_current_node->m_head.m_next->m_head.m_back = new_node;
            m_current_node->m_head.m_next = new_node;
            m_current_node = new_node;

            return m_begin = m_current_node->m_mem;
        }

        // We need to create a new node from scratch
        size_t new_size = detail::regex_max( size,
            static_cast<size_t>(DYNAMIC_BLOCK_SIZE) - offsetof( stack_node, m_mem ) );

        stack_node * new_node = static_cast<stack_node*>(
            ::operator new( new_size + offsetof( stack_node, m_mem ) ) );

        new_node->m_head.m_back = m_current_node;
        new_node->m_head.m_next = 0;

        m_current = new_node->m_head.m_current = new_node->m_mem + size;
        m_end     = new_node->m_head.m_end     = new_node->m_mem + new_size;

        m_current_node->m_head.m_next = new_node;
        m_current_node = new_node;

        return m_begin = m_current_node->m_mem;
    }

    byte_t * allocate( size_t size ) // throw(std::bad_alloc)
    {
        // This is the ptr to return
        byte_t * mem = m_current;

        // Advance the high-water mark
        m_current += size;

        // Check to see if we have overflowed this buffer
        if( std::less<void*>()( m_end, m_current ) ) // if( m_end < m_current )
        {
            // oops, back this out.
            m_current = mem;