wchashst.gml

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

:CLFNM cl2='WC&lpref.HashSet<Type>'.WC&lpref.HashTable<Type>
:CMT.========================================================================
:LIBF fmt='hdr'.WC&lpref.HashTable<Type>, WC&lpref.HashSet<Type>
:HFILE.wchash.h
:CLSS.
&cls. are templated classes used to store objects in a hash.
A hash saves objects in such a way as to make it efficient to locate
and retrieve an element.
As an element is looked up or inserted into the hash, the value of the
element is hashed.
Hashing results in a numeric index which is used to locate the value.
The storage area referenced by the hash value is usually called a
bucket.
If more than one element results in the same hash, the value
associated with the hash is placed in a list stored in the bucket.
A hash table allows more than one copy of an element that is
equivalent, while the hash set allows only one copy.
The equality operator of the element's type is used to locate the
value.
:P.
In the description of each member function, the text
.MONO Type
is used to indicate the template parameter defining
.if &lpref. eq Val .do begin
the type of the data to be stored in the hash.
.do end
.el .do begin
the type of the data pointed to by the pointers stored in the hash.
.do end

:P.
The constructor for the &cls.
requires a hashing function, which given a reference to
.MONO Type,
returns an
.MONO unsigned
value.
The returned value modulo the number of buckets determines the
bucket into which the element will be located.
The return values of the hash function
can be spread over the entire range of unsigned numbers.
The hash function return value
must be the same for values which are equivalent by the
equivalence operator for
.MONO Type.

.if &lpref. eq Val .do begin
:P.
Values are copied into the hash, which could be undesirable
if the stored objects are complicated and copying is expensive.
Value hashes should not be used to store objects of a base class if any
derived types of different sizes would be stored in the hash, or if the
destructor for a derived class must be called.
.do end
.el .do begin
:P.
Note that pointers to the elements are stored in the hash.
Destructors are not called on the elements pointed to.
The data values pointed to in the hash should not be changed such
that the equivalence to the old value is modified.
.do end

:P.
:INCLUDE file='_EXPT_BC'.

:HDG.Requirements of Type

The &cls requires
.MONO Type
to have:
.if &lpref. eq Val .do begin
:P.
A default constructor (
.MONO Type::Type()
).
:P.
A well defined copy constructor (
.MONO Type::Type( const Type & )
).
:P.
A well defined assignment operator (
.MONO Type & operator =( const Type & )
).
.do end
:P.
A well defined equivalence operator with constant parameters
.br
(
.MONO int operator ==( const Type & ) const
).

:HDG.Public Member Functions
The following member functions are declared in the public interface:
:MFNL.
:MFN index='WC&lpref.HashSet' .WC&lpref.HashSet( unsigned (*hash_fn)( const Type & ), unsigned = WC_DEFAULT_HASH_SIZE );
:MFN index='WC&lpref.HashSet' .WC&lpref.HashSet( unsigned (*hash_fn)( const Type & ), unsigned = WC_DEFAULT_HASH_SIZE, void * (*user_alloc)( size_t size ), void (*user_dealloc)( void *old, size_t size ) );
:MFN index='WC&lpref.HashSet' .WC&lpref.HashSet( const WC&lpref.HashSet & );
:MFN index='~~WC&lpref.HashSet' .virtual ~~WC&lpref.HashSet();
:MFN index='WC&lpref.HashTable' .WC&lpref.HashTable( unsigned (*hash_fn)( const Type & ), unsigned = WC_DEFAULT_HASH_SIZE );
:MFN index='WC&lpref.HashTable' .WC&lpref.HashTable( unsigned (*hash_fn)( const Type & ), unsigned = WC_DEFAULT_HASH_SIZE, void * (*user_alloc)( size_t size ), void (*user_dealloc)( void *old, size_t size ) );
:MFN index='WC&lpref.HashTable' .WC&lpref.HashTable( const WC&lpref.HashTable & );
:MFN index='~~WC&lpref.HashTable' .virtual ~~WC&lpref.HashTable();
:MFN index='bitHash'        .static unsigned bitHash( const void *, size_t );
:MFN index='buckets'        .unsigned buckets() const;
:MFN index='clear'          .void clear();
.if &lpref eq Ptr .do begin
:MFN index='clearAndDestroy'.void clearAndDestroy();
.do end
.if &lpref eq Val .do begin
:MFN index='contains'       .int contains( const Type & ) const;
.do end
.el .do begin
:MFN index='contains'       .int contains( const Type * ) const;
.do end
:MFN index='entries'        .unsigned entries() const;
.if &lpref eq Val .do begin
:MFN index='find'           .int find( const Type &, Type & ) const;
:MFN index='forall'         .void forAll( void (*user_fn)( Type, void * ), void * );
:MFN index='insert'         .int insert( const Type & );
.do end
.if &lpref eq Ptr .do begin
:MFN index='find'            .Type * find( const Type * ) const;
:MFN index='forall'         .void forAll( void (*user_fn)( Type *, void * ) , void * );
:MFN index='insert'         .int insert( Type * );
.do end
:MFN index='isEmpty'        .int isEmpty() const;
.if &lpref eq Val .do begin
:MFN index='remove'         .int remove( const Type & );
.do end
.el .do begin
:MFN index='remove'         .Type * remove( const Type * );
.do end
:MFN index='resize'         .void resize( unsigned );
:eMFNL.
The following public member functions are available for the
.MONO WC&lpref.HashTable
class only:
:MFNL.
.if &lpref eq Val .do begin
:MFN index='occurrencesOf'  .unsigned occurrencesOf( const Type & ) const;
.do end
.el .do begin
:MFN index='occurrencesOf'  .unsigned occurrencesOf( const Type * ) const;
.do end
.if &lpref eq Val .do begin
:MFN index='removeAll'      .unsigned removeAll( const Type & );
.do end
.el .do begin
:MFN index='removeAll'      .unsigned removeAll( const Type * );
.do end
:eMFNL.
:HDG.Public Member Operators
The following member operators are declared in the public interface:
:MFNL.
:MFN index='operator ='      .WC&lpref.HashSet & operator =( const WC&lpref.HashSet & );
:MFN index='operator =='     .int operator ==( const WC&lpref.HashSet & ) const;
:MFN index='operator ='      .WC&lpref.HashTable & operator =( const WC&lpref.HashTable & );
:MFN index='operator =='     .int operator ==( const WC&lpref.HashTable & ) const;
:eMFNL.
:eCLSS.
:eLIBF.
:CMT.========================================================================
:LIBF cltype='WC&lpref.HashSet<Type>' fmt='ctor' prot='public'.WC&lpref.HashSet
:SNPL.
:SNPFLF                    .#include <wchash.h>
:SNPFLF                    .public:
:SNPCD cd_idx='c'.WC&lpref.HashSet( unsigned (*hash_fn)( const Type & ),
:SNPFLF          .            unsigned = WC_DEFAULT_HASH_SIZE );
:eSNPL.
:SMTICS.
The
.MONO WC&lpref.HashSet<Type>
constructor creates a
.MONO WC&lpref.HashSet
object with no entries and with the number of buckets
in the second optional parameter, which defaults to the constant
.MONO WC_DEFAULT_HASH_SIZE
(currently defined as 101).
The number of buckets specified must be greater than zero, and will be forced
to at least one.
If the hash object can be created, but an allocation failure
occurs when creating the buckets, the
table will be created with zero buckets.
If the
.MONO out_of_memory
.ix out_of_memory exception
exception is enabled, then attempting to insert into a hash
table with zero buckets with throw an
.MONO out_of_memory
error.
:P.
The hash function
.MONO hash_fn
is used to determine which bucket each value will be assigned to.
If no hash function exists, the
static member function
.MONO bitHash
is available to help create one.

:RSLTS.
The
.MONO WC&lpref.HashSet<Type>
constructor creates an initialized
.MONO WC&lpref.HashSet
object with the specified number of buckets and
hash function.
:SALSO.
:SAL typ='fun'.~~WC&lpref.HashSet
:SAL typ='fun'.bitHash
:SAL typ='omtyp' ocls='WCExcept'.out_of_memory
:eSALSO.
:eLIBF.
:CMT.========================================================================
:LIBF cltype='WC&lpref.HashSet<Type>' fmt='ctor' prot='public'.WC&lpref.HashSet
:SNPL.
:SNPFLF                    .#include <wchash.h>
:SNPFLF                    .public:
:SNPCD cd_idx='c'.WC&lpref.HashSet( unsigned (*hash_fn)( const Type & ),
:SNPFLF          .            unsigned = WC_DEFAULT_HASH_SIZE,
:SNPFLF          .            void * (*user_alloc)( size_t ),
:SNPFLF          .            void (*user_dealloc)( void *, size_t ) );
:eSNPL.
:SMTICS.
Allocator and deallocator functions are specified
for use when entries are inserted and removed from the hash.
The semantics of this constructor are the same as the constructor without
the memory management functions.
:P.
The allocation function must return a
zero if it cannot perform the allocation.
The deallocation function is passed the size as well
as the pointer to the data.
Your allocation system may take advantage of the characteristic that
the allocation function will always be called with the same size
value for any particular instantiation of a hash.
To determine the size of
the objects that the memory management functions will be
required to allocate and free, the following macro may be used:
.br
.MONO WC&lpref.HashSetItemSize( Type )
:RSLTS.
The
.MONO WC&lpref.HashSet<Type>
constructor creates an initialized
.MONO WC&lpref.HashSet
object with the specified number of buckets and
hash function.
:SALSO.
:SAL typ='fun'.~~WC&lpref.HashSet
:SAL typ='fun'.bitHash
:SAL typ='omtyp' ocls='WCExcept'.out_of_memory
:eSALSO.
:eLIBF.
:CMT.========================================================================
:LIBF cltype='WC&lpref.HashSet<Type>' fmt='ctor' prot='public'.WC&lpref.HashSet
:SNPL.
:SNPFLF                    .#include <wchash.h>
:SNPFLF                    .public:
:SNPCD cd_idx='c'.WC&lpref.HashSet( const WC&lpref.HashSet & );
:eSNPL.
:SMTICS.
The
.MONO WC&lpref.HashSet<Type>
is the copy constructor for the
.MONO WC&lpref.HashSet
class.
The new hash is created with the same number of buckets, hash function,
all values or pointers stored in the hash, and the exception trap states.
If the hash object can be created, but an allocation failure
occurs when creating the buckets, the
hash will be created with zero buckets.
If there is not enough memory to copy all of
the values, 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, then the
.MONO out_of_memory
.ix out_of_memory exception
exception is thrown if it is enabled.
:RSLTS.
The
.MONO WC&lpref.HashSet<Type>
constructor creates a
.MONO WC&lpref.HashSet
object which is a copy of the passed hash.
:SALSO.
:SAL typ='fun'.~~WC&lpref.HashSet
:SAL typ='fun'.operator~b=
:SAL typ='omtyp' ocls='WCExcept'.out_of_memory
:eSALSO.
:eLIBF.
:CMT.========================================================================
:LIBF cltype='WC&lpref.HashSet<Type>' fmt='dtor' prot='public'.~~WC&lpref.HashSet
:SNPL.
:SNPFLF                    .#include <wchash.h>
:SNPFLF                    .public:
:SNPCD cd_idx='d'.virtual ~~WC&lpref.HashSet();
:eSNPL.
:SMTICS.
The
.MONO WC&lpref.HashSet<Type>
destructor is the destructor for the
.MONO WC&lpref.HashSet
class.
If the number of elements is not zero and the
.MONO not_empty
.ix not_empty exception
exception is enabled, the exception is thrown.
Otherwise, the hash elements are cleared using the
.MONO clear
member function.
.if &lpref. eq Ptr .do begin
The objects which the hash elements point to are not deleted unless the
.MONO clearAndDestroy
member function is explicitly called before the destructor is called.
.do end
The call to the
.MONO WC&lpref.HashSet<Type>
destructor is inserted implicitly by the compiler
at the point where the
.MONO WC&lpref.HashSet
object goes out of scope.
:RSLTS.