wcsbase.mh

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

    inline node_ptr base_remove_but_not_delete( const Type &elem
                                              , int &num_ptrs ) {
        return( WCSkipNonTempBase::base_remove_but_not_delete( &elem
                                                             , num_ptrs ) );
    };

    WCbool base_val_find( const Type &search, Type &return_val ) const;

    // Create a new node containing elem, and with (level_less_1 + 1)
    // forward pointers.  Uses the user_allocator function if provided.
    virtual node_ptr base_new_node( TTypePtr elem, unsigned level_less_1 );

    // Delete a node, using either delete or the user deallocator function.
    // If there a user deallocator function, then level_less_1 is correct.
    virtual void base_delete_node( node_ptr node, unsigned level_less_1 );

public:
    inline WCSkipListBase( unsigned prob, unsigned max_ptrs
                         , WCbool duplicates = FALSE )
              : WCSkipNonTempBase( prob, max_ptrs, duplicates ) {};

    inline WCSkipListBase( unsigned prob, unsigned max_ptrs
                         , void * (*user_alloc)( size_t )
                         , void (*user_dealloc)( void *, size_t )
                         , WCbool duplicates = FALSE )
              : WCSkipNonTempBase( prob, max_ptrs, user_alloc, user_dealloc
                                 , duplicates ) {};

    // clear can not be called by WCSkipNonTempBase, since it calls the
    // funtion base_delete_node, which is pure virtual in WCSkipNonTempBase's
    // destructor.
    virtual ~WCSkipListBase() {
        if( num_entries != 0 ) {
            base_throw_not_empty();
        };
        clear();
    };

    inline WCbool contains( const Type &elem ) const {
        return( base_find( elem ) != 0 );
    };

    inline unsigned entries() const {
        return( num_entries );
    };

    void forAll( void(*)( Type, void * ), void * ) const;

    inline WCbool insert( const Type &elem ) {
        return( base_insert( elem ) != 0 );
    };

    inline WCbool isEmpty() const {
        return( num_entries == 0 );
    };

    inline WCbool remove( const Type & elem ) {
        return( WCSkipNonTempBase::remove( &elem ) );
    };

    inline int operator==( const WCSkipListBase &rhs ) const {
        return( this == &rhs );
    };

    friend class WCSkipListIterBase;
};



// if dealloc_fn == 0, base_delete_node is assumed to ignore level_less_1
template<class Type>
void WCSkipListBase<Type>::base_delete_node( node_ptr node
                                           , unsigned level_less_1 ) {
    if( node ) {
        NodeType *whole_node = base_whole_node( node );
        whole_node->~NodeType();
        if( dealloc_fn ) {
            size_t size = WCValSkipListItemSize( Type, level_less_1 + 1 );
            dealloc_fn( whole_node, size );
        } else {
            delete [] (char *)whole_node;
        }
    }
};


template<class Type>
WCSkipListPtrs *WCSkipListBase<Type>::base_new_node( TTypePtr elem
                                            , unsigned level_less_1 ) {
    NodeType *new_node;
    size_t size = WCValSkipListItemSize( Type, level_less_1 + 1 );

    // get raw memory
    if( alloc_fn ) {
        new_node = (NodeType *)alloc_fn( size );
    } else {
        new_node = (NodeType *)new char[ size ];
    }
    if( new_node ) {
        // call WCSkipListNode's constructor with the raw chunk of memory
        new( new_node ) NodeType( *(const Type *)elem );
        return( &new_node->ptrs );
    } else {
        return( 0 );
    }
};


template<class Type>
WCbool WCSkipListBase<Type>::base_val_find( const Type &search
                                          , Type &return_val ) const {
    node_ptr found_node = base_find( search );
    if( found_node ) {
        return_val = base_whole_node( found_node )->data;
        return( TRUE );
    } else {
        return( FALSE );
    }
}


template<class Type>
void WCSkipListBase<Type>::forAll( register void(*user_fn)( Type, void * )
                                 , void * data) const {
    register node_ptr curr;

    curr = header->forward[ 0 ];
    while ( curr != 0 ) {
        user_fn( base_whole_node( curr )->data, data );
        curr = curr->forward[ 0 ];
    }
};



//
// WCSkipListDuplicatesBase provides skip list functionality for
// WCValSkipList and WCPtrSkipList where duplicates are allowed
//

template<class Type>
class WCSkipListDuplicatesBase : public WCSkipListBase<Type> {
public:
    inline WCSkipListDuplicatesBase( unsigned prob, unsigned max_ptrs
                         ) : WCSkipListBase( prob, max_ptrs, TRUE ) {};

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

    inline ~WCSkipListDuplicatesBase() {};

    unsigned occurrencesOf( const Type &elem ) const {
        return( base_occurrencesOf( &elem ) );
    };

    inline unsigned removeAll( const Type &elem ) {
        return( base_removeAll( &elem ) );
    };
};


//
// WCPtrSkipListBase provides the skip list interface for pointers.
//
// This is an abstract class to prevent objects of this type being created.
//
// Type is the type pointed to, and SkipListBase is either
// WCSkipListDuplicatesBase<void *> or WCSkipListBase<void *>.
//

template<class Type, class SkipListBase >
class WCPtrSkipListBase : public SkipListBase {
protected:
    // the pointers stored in the skip list by SkipListBase
    typedef void *StoredPtr;
    // the real type of the pointers
    typedef Type *TypePtr;
    // the user function passed to the forAll member function is passed
    // to SkipListBase::forAll using this cast type
    typedef void (*forAll_fn)( StoredPtr, void * );

    // define equivalence and less than based on the == and < operator of
    // the object pointed to
    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 WCPtrSkipListBase( unsigned prob, unsigned max_ptrs )
              : SkipListBase( prob, max_ptrs ) {};

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

    inline virtual ~WCPtrSkipListBase() = 0;

    void clearAndDestroy();

    inline WCbool contains( const Type *elem ) const {
        return( SkipListBase::contains( (const TypePtr)elem ) );
    };

    Type *find( const Type *elem ) const;

    inline void forAll( void(*fn)( Type *, void * ), void * data ) const {
        SkipListBase::forAll( (forAll_fn)fn, data );
    };

    inline WCbool insert( Type *elem ) {
        return( SkipListBase::insert( (const TypePtr)elem ) );
    };

    Type *remove( const Type *elem );
};


template<class Type, class SkipListBase>
WCPtrSkipListBase<Type, SkipListBase>::~WCPtrSkipListBase() {};


template<class Type, class SkipListBase >
void WCPtrSkipListBase<Type, SkipListBase>::clearAndDestroy() {
    register node_ptr curr;

    curr = header->forward[ 0 ];
    while ( curr != 0 ) {
        delete( (Type *)base_whole_node( curr )->data );
        curr = curr->forward[ 0 ];
    }
    clear();
};


template<class Type, class SkipListBase >
Type *WCPtrSkipListBase<Type, SkipListBase>::find( const Type *elem ) const {
    node_ptr found_node = base_find( (const TypePtr)elem );
    if( found_node ) {
        return( (Type *)base_whole_node( found_node )->data );
    } else {
        return( 0 );
    }
};


template<class Type, class SkipListBase>
Type *WCPtrSkipListBase<Type, SkipListBase>::remove( const Type *elem ) {
    int num_ptrs_in_node;

    node_ptr node = base_remove_but_not_delete( (const TypePtr)elem
                                         , num_ptrs_in_node );
    if( node ) {
        Type *ret_ptr = (Type *)base_whole_node( node )->data;
        base_delete_node( node, num_ptrs_in_node );
        return( ret_ptr );
    } else {
        return( 0 );
    }
}

:include redefnew.sp

#endif