wcskip.mh

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

    inline virtual ~WCValSkipListDict() {};

    inline WCbool contains( const Key &key ) const {
        NonConstThis This = (NonConstThis)this;
        This->temp_key_val.key = key;
        return( base_find( temp_key_val ) != 0 );
    };

    WCbool find( const Key &search, Value &ret_value ) const;

    WCbool findKeyAndValue( const Key &search, Key &ret_key
                          , Value &ret_value ) const;

    void forAll( void(*)( Key, Value, void * ), void * ) const;

    inline WCbool insert( const Key &key, const Value &value ) {
        KeyVal temp( key, value );
        return( WCSkipListBase::insert( temp ) );
    };

    inline WCbool remove( const Key &key ) {
        temp_key_val.key = key;
        return( WCSkipListBase::remove( temp_key_val ) );
    };

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

    Value &operator[]( const Key &key );

    const Value &operator[]( const Key &key ) const;
};


template<class Key, class Value>
WCbool WCValSkipListDict<Key, Value>::find( const Key &search
                                         , Value &ret_value ) const {
    NonConstThis This = (NonConstThis)this;
    This->temp_key_val.key = search;
    node_ptr node = base_find( temp_key_val );
    if( node != 0 ) {
        ret_value = base_whole_node( node )->data.value;
        return( TRUE );
    } else {
        return( FALSE );
    }
};


template<class Key, class Value>
WCbool WCValSkipListDict<Key, Value>::findKeyAndValue( const Key &search
                                , Key &ret_key, Value &ret_value ) const {
    NonConstThis This = (NonConstThis)this;
    This->temp_key_val.key = search;
    node_ptr node = base_find( temp_key_val );
    if( node != 0 ) {
        ret_key = base_whole_node( node )->data.key;
        ret_value = base_whole_node( node )->data.value;
        return( TRUE );
    } else {
        return( FALSE );
    }
};


template<class Key, class Value>
void WCValSkipListDict<Key, Value>
                ::forAll( register void(*user_fn)( Key, Value, void * )
                        , void * data) const {
    register node_ptr curr;

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


template<class Key, class Value>
Value &WCValSkipListDict<Key, Value>::operator[]( const Key &key ) {
    NonConstThis This = (NonConstThis)this;
    This->temp_key_val.key = key;
    node_ptr node = base_find( temp_key_val );
    if( node == 0 ) {
        node = base_insert( temp_key_val );
        if( !node ) {
            // insert failed because allocation failed and out_of_memory
            // exception disabled
            return( *(Value *)0 );
        }
    }
    return( base_whole_node( node )->data.value );
};


template<class Key, class Value>
const Value &WCValSkipListDict<Key, Value>
                ::operator[]( const Key &key ) const {
    NonConstThis This = (NonConstThis)this;
    This->temp_key_val.key = key;
    node_ptr node = base_find( temp_key_val );
    if( node != 0 ) {
        return( base_whole_node( node )->data.value );
    } else {
        base_throw_index_range();
        // find failed, index_range exception off, but must return reference
        return( *(Value *)0 );
    }
};




//
// WCPtrSkipListDict - 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 WCPtrSkipListDict
        : public WCValSkipListDict<void *, void *> {
protected:
    // for const member functions which modify temp_key_val, but not the
    // skip list
    typedef WCPtrSkipListDict *const NonConstThis;
    // the pointer stored by WCValSkipListDict
    typedef void *Stored_Ptr;
    // the user function passed to the forAll member function is passed
    // to WCValSkipListDict::forAll using this cast type
    typedef void (*_ForAllFnCast)( void *, void *, void * );

    // defines equivalence and less than based on the keys pointed to
    // 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 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 Key *)( (const KeyVal *)rhs )->key );
    };

    // for the clearAndDestroy member function
    static void base_destroy( Key *key, Value *value, void * ) {
        delete( key );
        delete( value );
    };

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

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

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

    inline virtual ~WCPtrSkipListDict() {};

    inline void clearAndDestroy() {
        forAll( base_destroy, 0 );
        clear();
    };

    inline WCbool contains( const Key *key ) const {
        return( WCValSkipListDict::contains( (const Stored_Ptr)key ) );
    };

    Value *find( const Key *search ) const;

    Value *findKeyAndValue( const Key *search, Key * &ret_key ) const;

    void forAll( void(*fn)( Key *, Value *, void * ), void * data ) const {
        WCValSkipListDict::forAll( (_ForAllFnCast)fn, data );
    };

    inline WCbool insert( Key *key, Value *value ) {
        return( WCValSkipListDict::insert( (const Stored_Ptr)key
                                         , (const Stored_Ptr)value ) );
    };

    Value* remove( const Key *key );

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

    inline Value * &operator[]( const Key *key ) {
        return( (Value * &)WCValSkipListDict
                                ::operator[]( (const Stored_Ptr)key ) );
    };

    inline Value * const &operator[]( const Key *key ) const {
        return( (Value * const &)WCValSkipListDict
                                ::operator[]( (const Stored_Ptr)key ) );
    };
};


template<class Key, class Value>
Value *WCPtrSkipListDict<Key, Value>::find( const Key *search ) const {
    NonConstThis This = (NonConstThis)this;
    This->temp_key_val.key = (Stored_Ptr)search;
    node_ptr node = base_find( temp_key_val );
    if( node != 0 ) {
        return( (Value *)base_whole_node( node )->data.value );
    } else {
        return( 0 );
    }
};


template<class Key, class Value>
Value *WCPtrSkipListDict<Key, Value>::findKeyAndValue( const Key *search
                                , Key * &ret_key ) const {
    NonConstThis This = (NonConstThis)this;
    This->temp_key_val.key = (Stored_Ptr)search;
    node_ptr node = base_find( temp_key_val );
    if( node != 0 ) {
        ret_key = (Key *)base_whole_node( node )->data.key;
        return( (Value *)base_whole_node( node )->data.value );
    } else {
        return( 0 );
    }
};


template<class Key, class Value>
Value *WCPtrSkipListDict<Key, Value>::remove( const Key *elem ) {
    int num_ptrs_in_node;

    temp_key_val.key = (Stored_Ptr)elem;
    node_ptr node = base_remove_but_not_delete( temp_key_val
                                         , num_ptrs_in_node );
    if( node ) {
        Value *ret_ptr = (Value *)base_whole_node( node )->data.value;
        base_delete_node( node, num_ptrs_in_node );
        return( ret_ptr );
    } else {
        return( 0 );
    }
}

#endif