skip.txt

开放源码的编译器open watcom 1.6.0版的源代码

    - unsigned occurrencesOf( const Type &elem ) const
    - int removeAll( const Type &elem )
      these are no longer available since they are of little use with unique
      elements, and are just less efficient versions of the contains and
      remove member functions respectively.


  changed public member fn
  ~~~~~~~~~~~~~~~~~~~~~~~~
  
    - int WCValskip listSet::insert( const Type &elem )
    - int WCPtrskip listSet::insert( Type *elem )
      If an entry equivalent to elem was not previously in the skip list,
      insert elem into the skip list.  If elem was already in the skip list,
      then the skip list remains unchanged, and the not_unique exception will
      be thrown if enabled.  If the exception is not enabled, zero is
      returned.  If elem is unique to the skip list, but allocation of the
      node to store elem
      fails, then an out_of_memory exception will be thrown if enabled.
      Otherwise, if the allocation failed, zero will be returned, and the
      skip list will be unchanged.  Non-zero will be returned on a successful
      insert.


WCValSkipListDict<Key,Value>, WCPtrSkipListDict<Key,Value>:
===========================================================

  These are skip list dictionaries.  The key is used as a handle to the value
  stored.  Key's equality operator and less than operator is used to order and
  find key-value pairs.  Keys must be unique, values do not need to be
  unique.
  

  WCValSkipListDict requires from <Key>:
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    - copy and default constructors
    - assignment constructor
    - equivalence operator (operator==)
    - less than operator (operator<)

  WCValSkipListDict requires from <Value>:
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    - copy and default constructors
    - assignment constructor
    
  WCPtrSkipListDict requires from <Key>:
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    - equivalence operator (operator==)
    - less than operator (operator<)
    
  WCPtrSkipListDict requires from <Value>:
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    - nothing
  

    
  public constructors/destructors:
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    - ..SkipListDict( unsigned probability = WCSKIPLIST_PROB_QUARTER
    		, unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
      constructs a skip list with no entries.  probability is used to determine
      the number of pointers in each skip list node.  If probability is
      WCSKIPLIST_PROB_QUARTER, then each element will have an average of
      1 1/3 pointers linking it into the skip list.  If probability is
      WCSKIPLIST_PROB_HALF, then each element will have an average of
      2 pointers linking it into the skip list.  max_ptrs is the maximum
      number of link pointers which an element can have to link it into the
      skip list.  The default probability and max_ptrs is appropriate for
      upto about 2^16 elements.
      If a max_ptrs is greater than WCSKIPLIST_MAX_PTRS, then
      WCSKIPLIST_MAX_PTRS will be used as the maximum number of pointers.
      For more information on the choice and effects of probability and
      maximum number of pointers, see the description of skip lists in
      the June 1990 issue of CACM.


    - ..SkipListDict( unsigned probability, unsigned max_ptrs
		, void * (*user_alloc)( size_t size )
		, void (*user_dealloc)( void *old, size_t size ) )
      Like the above constructor, but also provides a user allocator and user
      deallocator to allocate and free memory when entries are inserted and
      removed from the skip list.  The user_alloc function must return a
      pointer to allocated memory of at least size bytes, or 0 if it cannot
      perform the allocation (which causes the insert to fail).  The
      user_dealloc function must free "old", which was allocated by the
      user_alloc function, and is of size "size".  The size passed to
      user_alloc will depend on the number of pointers of the inserted element.
      The number of pointers can be from 1 to max_ptrs, but most elements will
      have only one or two pointers.  To determine the size of
      the objects that the user_alloc and user_dealloc functions will be
      required to allocate and free, the following macros may be used:
	WCValSkipListDictItemSize( Key, Value, num_ptrs )
	WCPtrSkipListDictItemSize( Key, Value, num_ptrs )
      For example, WCValSkipListDict<my_key_type, my_value_type> will require
      user_alloc and user_dealloc to handle objects of size
      WCValSkipListDictItemSize( my_key_type, my_value_type, 1 ),
      WCValSkipListDictItemSize( my_key_type, my_value_type, 2 ),
      ...., WCValSkipListDictItemSize( my_key_type, my_value_type, max_ptrs ).

    - ..SkipListDict( const ..SkipListDict &orig )
      the copy constructor.  Makes a copy of orig, including copying
      probability and max_ptrs, all values or pointers stored in the skip
      list, and the exception state.  If there is enough memory to create
      the skip list object, but not enough memory to copy all of
      the values or pointers in the skip list, then only some will be copied,
      and the number of entries will correctly reflect the number copied.
      If all of the elements cannot be copied, an out_of_memory exception
      is thrown if enabled in orig.


    - ~..SkipListDict()
      the destructor:  destroys the skip list object, including clearing the
      entries using the clear member function.  If the skip list is not empty
      (contains at least one entry) when this destructor is invoked, the
      not_empty exception will be thrown if enabled.




  public operators
  ~~~~~~~~~~~~~~~~

    - ..SkipListDict &operator=( const ..SkipListDict &orig )
      the assignment operator.  Clears this (using the clear member function),
      then makes a copy of orig, including copying
      probability and max_ptrs, all values or pointers stored in the skip
      list, and the exception state.  If there is enough memory to create
      the skip list object, but not enough memory to copy all of
      the values or pointers in the skip list, then only some will be copied,
      and the number of entries will correctly reflect the number copied.
      If all of the elements cannot be copied, an out_of_memory exception
      is thrown if enabled in orig.
    
   - int operator==( const ..SkipListDict &rhs ) const
     The skip list Dict equality operator.  Two skip list Dicts are
     equivalent if they are the same object (ie they have the same address).
     Returns 0 if not equal and non-zero if equal.


   - Value & WCValSkipListDict::operator[]( const Key & key );
   - Value * & WCPtrSkipListDict::operator[]( const Key * key );
     The non-constant index operator.  If a key-value pair is found with
     key equivalent to "key", then a reference to value or pointer
     to value is returned.  If no equivalent element is found, then a new
     key-value pair is created with key "key", and value initialized with
     the default constructor (an undefined pointer for WCPtrSkipListDict).  The
     returned reference to the value/pointer to value can be assigned to,
     so that insertions can be done like:
       WCValSkipListDict<int,String> skip_list;
       skip_list[ 5 ] = "Hello";
     If an allocation error occurs when inserting a new key-value pair,
     then the out_of_memory exception is thrown, if enabled.  If the exception
     is not enabled, then a reference to an object/pointer to an object with
     address zero will be returned, CAUSING A RUN-TIME ERROR.

   - const Value & WCValSkipListDict::operator[]( const Key & key ) const;
   - Value * const & WCPtrSkipListDict::operator[]( const Key * key ) const;
     The constant index operator.  If a key-value pair is found with
     key equivalent to "key", then a reference to value or pointer
     to value is returned.  If no equivalent element is found, then an
     index_range exception is thrown, if enabled.  If the exception is not
     enabled, then a reference to a value/pointer to an object with
     address zero will be returned, CAUSING A RUN-TIME ERROR.
      

  public member fns
  ~~~~~~~~~~~~~~~~~

    **NOTE**:  unless otherwise noted, parameters of type "Type &" are for the
    WCValSkipListDict, and the corresponding parameters for WCPtrSkipListDict
    member functions have type "Type *".

    - void clear()
      remove all values or pointers from the skip list Dict, so that the
      Dict has no entries.  Note that for WCPtrSkipListDict, the values
      pointed to are not deleted.

    ** PTR ONLY **
    - void clearAndDestroy()
      call delete for all pointers (both key and value pointers) in the
      skip list, and clear the skip list so that it contains zero entries.
    
    - int contains( const Key &elem ) const
      return non-zero if a element with key equivalent to elem is stored in
      the skip list Dict, or zero if there is no equivalent element.
      Note that equivalence is based on Key's == operator for both
      WCValSkipListDict and WCPtrSkipListDict.

    - unsigned entries() const
      returns the number of entries stored in the skip list Dict.

    ** VAL ONLY **
    - int find( const Key &search, Value &return_val ) const
      attempts to find an element with key equivalent to search in the
      skip list Dict.  If an equivalent key-value pair is found, non-zero is
      returned, and return_val is assigned the found element's Value.
      If no such element is found, zero is returned and return_val is unchanged.
      Note that equivalence is based on Key's == operator.

    ** PTR ONLY **
    - Value *find( const Key *elem ) const
      attempts to find an element with key equivalent to elem in the
      skip list Dict.  If an equivalent key-value pair is found, a pointer
      to its value is returned.  Otherwise zero is returned.
      Note that equivalence is based on Key's == operator (ie the keys
      pointed to are compared).
      
    ** VAL ONLY **
    - int findKeyAndValue( const Key &search, Key &return_key
    			 , Value &return_val ) const
      attempts to find an element with key equivalent to search in the
      skip list Dict.  If an equivalent key-value pair is found, non-zero is
      returned, return_key is assigned the found element's key and
      return_val is assigned the found element's Value.
      If no such element is found, zero is returned and both return_key and
      return_val are unchanged.
      Note that equivalence is based on Key's == operator.

    ** PTR ONLY **
    - Value *findKeyAndValue( const Key *elem, Key * &return_key ) const
      attempts to find an element with key equivalent to elem in the
      skip list Dict.  If an equivalent key-value pair is found, a pointer
      to its value is returned, and return_key is assigned a pointer to its key.
      Otherwise zero is returned, and return_key is unchanged.
      Note that equivalence is based on Key's == operator (ie the keys
      pointed to are compared).
      
    - void WCValSkipListDict::forAll(
    		void (*user_fn)( Key key, Value value, void *data )
	      , void *data )
    - void WCPtrSkipListDict::forAll(
    		void (*user_fn)( Key *key, Value *value, void *data )
    	      , void *data )
      call user_fn for every key-value pair in the skip list Dict (in order
      of least element to greatest, by Key's < operator).  user_fn
      has prototype:
        ** VAL **
	void user_fn( Key key, Value value, void *data );
        ** PTR **
	void user_fn( Key *key, Value *value, void *data );
      and will be passed each element's key and value in turn as the first
      two parameters, and the
      data passed to forAll as the third paramter.  data can be used to
      pass user_fn any information which it requires.

    - int WCValSkipListDict::insert( const Key &key, const Value &value )
    - int WCPtrSkipListDict::insert( Key *key, Value *value )
      Insert key and value into the skip list Dict.  If allocation of the
      node to store the key-value pair fails, then an out_of_memory
      exception will be thrown if enabled.
      Otherwise, if the allocation failed, zero will be returned, and the
      skip list Dict will be unchanged.  Non-zero will be returned on a
      successful insert.

    - int isEmpty() const
      return non-zero if the skip list Dict is empty, zero if the skip list Dict
      contains at least one entry.

    - int WCValSkipListDict::remove( const Key &elem )
    - Type * WCPtrSkipListDict::remove( const Key *elem )
      removes the element equivalent with key equivalent to elem from the
      skip list Dict.  Returns
      non-zero (Val) or the removed pointer (Ptr) if an equivent element was
      found to remove, zero if not.
      Note that equivalence is based on Key's == operator for both
      WCValSkipListDict and WCPtrSkipListDict.


Skip List Iterators
===================

see hash iterators, user interface is identical.  Iterator class type names
are WCVal/PtrSkipListIter, WCVal/PtrSkipListSetIter, WCVal/PtrSkipListDictIter.
Skip Lists are iteratored (using the ++ and call operators) in
Type/Key assending order (based on Type's/Key's < operator).

The include file is <wcskipit.h>