wcskip.mh

来自「开放源码的编译器open watcom 1.6.0版的源代码」· MH 代码 · 共 519 行 · 第 1/2 页

//
//  wcskip.h    Definitions and implementation for the WATCOM Container Skip
//              List class
//
:keep CPP_HDR
:include crwat.sp
//
#ifndef _WCSKIP_H_INCLUDED
#define _WCSKIP_H_INCLUDED
:include readonly.sp

#ifndef __cplusplus
#error wcskip.h is for use with C++
#endif

//
// Skip Lists are a probabilistic alternative to balanced trees, as
// described in the June 1990 issue of CACM and were invented by
// William Pugh in 1987.
//


#ifndef _WCDEFS_H_INCLUDED
 #include <wcdefs.h>
#endif
#ifndef _WCEXCEPT_H_INCLUDED
 #include <wcexcept.h>
#endif
#ifndef _WCSBASE_H_INCLUDED
 #include <wcsbase.h>
#endif


//
// WCValSkipList - the skip list value class which allows duplicates
//

template<class Type>
class WCValSkipList : public WCSkipListDuplicatesBase<Type> {
private:
    // define equivalence and less than for the base classes
    // second parameters are really typed (Type *)
    virtual int base_equiv( node_ptr elem1, TTypePtr elem2 ) const {
        return( (const Type)base_whole_node( elem1 )->data
                == *(const Type *)elem2 );
    };

    virtual int base_less( node_ptr lhs, TTypePtr rhs ) const {
        return( (const Type)base_whole_node( lhs )->data
                < *(const Type *)rhs );
    };

public:
    inline WCValSkipList( unsigned prob = WCSKIPLIST_PROB_QUARTER
                        , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
                        ) : WCSkipListDuplicatesBase( prob, max_ptrs ) {};

    inline WCValSkipList( unsigned prob, unsigned max_ptrs
                        , void * (*user_alloc)( size_t )
                        , void (*user_dealloc)( void *, size_t )
                        ) : WCSkipListDuplicatesBase( prob, max_ptrs
                                        , user_alloc, user_dealloc ) {};

    inline WCValSkipList( const WCValSkipList &orig )
                 : WCSkipListDuplicatesBase( orig.probability
                                           , orig.max_ptrs_in_node ) {
        base_construct( &orig );
    };

    inline virtual ~WCValSkipList() {};

    inline WCbool find( const Type &search, Type &return_val ) const {
        return( base_val_find( search, return_val ) );
    }

    inline WCValSkipList &operator=( const WCValSkipList &orig ) {
        base_assign( &orig );
        return( *this );
    };
};




//
// WCPtrSkipList - the skip list pointer class which allows duplicates
//

template<class Type>
class WCPtrSkipList
        : public WCPtrSkipListBase<Type,WCSkipListDuplicatesBase<void *> > {
public:
    inline WCPtrSkipList( unsigned prob = WCSKIPLIST_PROB_QUARTER
                        , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
                        ) : WCPtrSkipListBase( prob, max_ptrs ) {};

    inline WCPtrSkipList( unsigned prob, unsigned max_ptrs
                        , void * (*user_alloc)( size_t )
                        , void (*user_dealloc)( void *, size_t )
                        ) : WCPtrSkipListBase( prob, max_ptrs
                                             , user_alloc, user_dealloc ) {};

    inline WCPtrSkipList( const WCPtrSkipList &orig )
                         : WCPtrSkipListBase( orig.probability
                                            , orig.max_ptrs_in_node ) {
        base_construct( &orig );
    };

    inline virtual ~WCPtrSkipList() {};

    inline unsigned occurrencesOf( const Type *elem ) const {
        return( WCSkipListDuplicatesBase
                        ::occurrencesOf( (const TypePtr) elem ) );
    };

    inline unsigned removeAll( const Type *elem ) {
        return( WCSkipListDuplicatesBase::removeAll( (const TypePtr) elem ) );
    };

    inline WCPtrSkipList &operator=( const WCPtrSkipList &orig ) {
        base_assign( &orig );
        return( *this );
    };
};




//
// WCValSkipListSet - the skip list value class which does not allow duplicates
//

template<class Type>
class WCValSkipListSet : public WCSkipListBase<Type> {
private:
    // defines equivalence and less than for the base class
    // second parameters are really typed (Type *)
    virtual int base_equiv( node_ptr elem1, TTypePtr elem2 ) const {
        return( (const Type)base_whole_node( elem1 )->data
                == *(const Type *)elem2 );
    };

    virtual int base_less( node_ptr lhs, TTypePtr rhs ) const {
        return( (const Type)base_whole_node( lhs )->data
                < *(const Type *)rhs );
    };

public:
    inline WCValSkipListSet( unsigned prob = WCSKIPLIST_PROB_QUARTER
                           , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
                           ) : WCSkipListBase( prob, max_ptrs ) {};

    inline WCValSkipListSet( unsigned prob, unsigned max_ptrs
                           , void * (*user_alloc)( size_t )
                           , void (*user_dealloc)( void *, size_t )
                           ) : WCSkipListBase( prob, max_ptrs
                                        , user_alloc, user_dealloc ) {};

    inline WCValSkipListSet( const WCValSkipListSet &orig )
                         : WCSkipListBase( orig.probability
                                         , orig.max_ptrs_in_node ) {
        base_construct( &orig );
    };

    inline virtual ~WCValSkipListSet() {};

    inline WCbool find( const Type &search, Type &return_val ) const {
        return( base_val_find( search, return_val ) );
    }

    inline WCValSkipListSet &operator=( const WCValSkipListSet &orig ) {
        base_assign( &orig );
        return( *this );
    };
};




//
// WCPtrSkipListSet - the skip list pointer class which does not
// allow duplicates
//

template<class Type>
class WCPtrSkipListSet
        : public WCPtrSkipListBase<Type,WCSkipListBase<void *> > {
public:
    inline WCPtrSkipListSet( unsigned prob = WCSKIPLIST_PROB_QUARTER
                           , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
                           ) : WCPtrSkipListBase( prob, max_ptrs ) {};

    inline WCPtrSkipListSet( unsigned prob, unsigned max_ptrs
                           , void * (*user_alloc)( size_t )
                           , void (*user_dealloc)( void *, size_t )
                           ) : WCPtrSkipListBase( prob, max_ptrs
                                             , user_alloc, user_dealloc ) {};

    inline WCPtrSkipListSet( const WCPtrSkipListSet &orig )
                         : WCPtrSkipListBase( orig.probability
                                            , orig.max_ptrs_in_node ) {
        base_construct( &orig );
    };

    inline virtual ~WCPtrSkipListSet() {};

    inline WCPtrSkipListSet &operator=( const WCPtrSkipListSet &orig ) {
        base_assign( &orig );
        return( *this );
    };
};




//
// WCValSkipListDict - the skip list value dictionary class.  Key-Value
// pairs are stored in a skip list, and all lookups are base on Key
//

template<class Key, class Value>
class WCValSkipListDict
        : public WCSkipListBase<WCSkipListDictKeyVal<Key, Value> > {
protected:
    typedef WCSkipListDictKeyVal<Key, Value> KeyVal;
    // for const member functions which modify temp_key_val, but not the
    // skip list
    typedef WCValSkipListDict *const NonConstThis;

    // temp_key_val is used in finds, removes, etc., where only the key is
    // given. it is also used by the operator[] to insert.  The value must
    // remain default initialized
    KeyVal temp_key_val;

    // second parameters are really typed (KeyVal *)
    virtual int base_equiv( node_ptr elem1, TTypePtr elem2 ) const {
        return( (const Key)base_whole_node( elem1 )->data.key
                == ( (const KeyVal *)elem2 )->key );
    };

    virtual int base_less( node_ptr lhs, TTypePtr rhs ) const {
        return( (const Key)base_whole_node( lhs )->data.key
                < ( (const KeyVal *)rhs )->key );
    };

public:
    inline WCValSkipListDict( unsigned prob = WCSKIPLIST_PROB_QUARTER
                            , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
                            ) : WCSkipListBase( prob, max_ptrs ) {};

    inline WCValSkipListDict( unsigned prob, unsigned max_ptrs
                            , void * (*user_alloc)( size_t )
                            , void (*user_dealloc)( void *, size_t )
                            ) : WCSkipListBase( prob, max_ptrs
                                              , user_alloc, user_dealloc ) {};

    inline WCValSkipListDict( const WCValSkipListDict &orig )
                 : WCSkipListBase( orig.probability, orig.max_ptrs_in_node ) {
        base_construct( &orig );
    };