SourcePro® 2024.1 |
SourcePro® API Reference Guide |
A simple hash table for objects inheriting from RWCollectable. Uses chaining (as implemented by class RWSlistCollectables) to resolve hash collisions. More...
#include <rw/hashtab.h>
Public Member Functions | |
RWHashTable () | |
RWHashTable (const RWHashTable &t) | |
RWHashTable (RWHashTable &&t) | |
RWHashTable (size_t N) | |
virtual void | apply (RWapplyCollectable ap, void *) |
virtual void | clear () |
virtual RWCollectable * | copy () const |
virtual size_t | entries () const |
virtual RWCollectable * | find (const RWCollectable *) const |
virtual RWCollectable * | insert (RWCollectable *a) |
virtual RWClassID | isA () const |
virtual bool | isEmpty () const |
virtual bool | isEqual (const RWCollectable *) const |
virtual RWConstIterator * | newConstIterator () const |
virtual RWIterator * | newIterator () |
virtual RWCollectable * | newSpecies () const |
virtual size_t | occurrencesOf (const RWCollectable *) const |
bool | operator!= (const RWHashTable &) const |
bool | operator<= (const RWHashTable &t) const |
RWHashTable & | operator= (const RWHashTable &t) |
RWHashTable & | operator= (RWHashTable &&t) |
bool | operator== (const RWHashTable &t) const |
virtual RWCollectable * | remove (const RWCollectable *) |
virtual void | resize (size_t n=0) |
void | swap (RWHashTable &t) |
Public Member Functions inherited from RWCollection | |
virtual | ~RWCollection () |
RWBag | asBag () const |
RWBinaryTree | asBinaryTree () const |
RWOrdered | asOrderedCollection () const |
RWSet | asSet () const |
RWBinaryTree | asSortedCollection () const |
virtual RWspace | binaryStoreSize () const |
virtual void | clearAndDestroy () |
virtual bool | contains (const RWCollectable *target) const |
void | operator+= (const RWCollection &c) |
void | operator-= (const RWCollection &c) |
virtual void | removeAndDestroy (const RWCollectable *target) |
virtual void | restoreGuts (RWFile &) |
virtual void | restoreGuts (RWvistream &) |
virtual void | saveGuts (RWFile &) const |
virtual void | saveGuts (RWvostream &) const |
RWCollection * | select (RWtestCollectable tst, void *vp) const |
Public Member Functions inherited from RWCollectable | |
virtual | ~RWCollectable () |
virtual int | compareTo (const RWCollectable *) const |
virtual unsigned | hash () const |
RWspace | recursiveStoreSize () const |
RWStringID | stringID () const |
Friends | |
class | RWHashTableConstIterator |
class | RWHashTableIterator |
Additional Inherited Members | |
Static Public Member Functions inherited from RWCollectable | |
static RWClassID | classID (const RWStringID &name) |
static RWClassID | classIsA () |
static bool | isAtom (RWClassID id) |
static RWspace | nilStoreSize () |
Static Public Attributes inherited from RWCollection | |
static size_t | DEFAULT_CAPACITY |
Related Symbols inherited from RWCollection | |
typedef void(* | RWapplyCollectable) (RWCollectable *, void *) |
typedef bool(* | RWtestCollectable) (const RWCollectable *, const void *) |
typedef bool(* | RWtestCollectablePair) (const RWCollectable *, const RWCollectable *, const void *) |
This class is a simple hash table for objects inheriting from RWCollectable. It uses chaining (as implemented by class RWSlistCollectables) to resolve hash collisions. Duplicate objects are allowed. An object stored by RWHashTable must inherit from the abstract base class RWCollectable, with suitable definition for virtual functions hash() and isEqual().
To find an object that matches a key, the key's virtual function hash() is first called to determine in which bucket the object occurs. The bucket is then searched linearly by calling the virtual function isEqual() for each candidate, with the key as the argument. The first object to return true
is the returned object.
The initial number of buckets in the table is set by the constructor. There is a default value. If the number of items in the collection greatly exceeds the number of buckets then efficiency sags because each bucket must be searched linearly. The number of buckets can be changed by calling member function resize(). This requires that all objects be rehashed.
The iterator for this class is RWHashTableIterator.
Program output:
RWHashTable::RWHashTable | ( | ) |
Constructs an empty hash table with RWCollection::DEFAULT_CAPACITY buckets.
RWHashTable::RWHashTable | ( | size_t | N | ) |
Constructs an empty hash table with N buckets.
RWHashTable::RWHashTable | ( | const RWHashTable & | t | ) |
Copy constructor. Creates a new hash table as a shallow copy of the table t. The new table has the same number of buckets as the old table. Hence, the members need not be and will not be rehashed.
RWHashTable::RWHashTable | ( | RWHashTable && | t | ) |
Move constructor. The constructed RWHashTable takes ownership of the data owned by t.
|
virtual |
Invokes the function pointer ap on each item in the collection in no particular order, due to the nature of hashing collections. The function pointed to by ap should take no action that could change the hash value or equality properties of the objects.
Implements RWCollection.
|
virtual |
Removes all objects from the collection. Does not delete the objects themselves.
Implements RWCollection.
Reimplemented in RWHashDictionary.
|
virtual |
Returns a new, copy-constructed object of the same type as self. The caller is responsible for deleting the object.
Reimplemented from RWCollectable.
Reimplemented in RWHashDictionary, RWIdentityDictionary, RWIdentitySet, and RWSet.
|
inlinevirtual |
Returns the total number of items in the collection.
Implements RWCollection.
|
virtual |
Returns a pointer to the first item in the collection which "matches" the object pointed to by target or rwnil if no item was found. For most collections, an item "matches" the target if either isEqual() or compareTo() find equivalence, whichever is appropriate for the actual collection type. However, the "identity collections" (i.e., RWIdentitySet and RWIdentityDictionary) look for an item with the same address (i.e., "is identical to").
Implements RWCollection.
Reimplemented in RWHashDictionary, and RWIdentitySet.
|
virtual |
Returns a if successful, otherwise rwnil.
Implements RWCollection.
Reimplemented in RWHashDictionary, RWIdentitySet, and RWSet.
|
virtual |
Returns __RWHASHTABLE
.
Reimplemented from RWCollection.
Reimplemented in RWHashDictionary, RWIdentityDictionary, RWIdentitySet, and RWSet.
|
inlinevirtual |
Returns true
if the collection is empty, otherwise returns false
.
Implements RWCollection.
|
virtual |
Behaves as if compareTo(t) was invoked, returning true
if the result equals 0, false
otherwise.
Reimplemented from RWCollectable.
Reimplemented in RWHashDictionary, RWIdentityDictionary, RWIdentitySet, and RWSet.
|
virtual |
Returns a const pointer to a dynamically allocated iterator for the collection.
Implements RWCollection.
Reimplemented in RWHashDictionary, and RWSet.
|
virtual |
Returns a dynamically allocated iterator for the collection.
Implements RWCollection.
Reimplemented in RWHashDictionary, and RWSet.
|
virtual |
Returns a new, default-constructed object of the same type as self. The caller is responsible for deleting the object.
Reimplemented from RWCollectable.
Reimplemented in RWHashDictionary, RWIdentityDictionary, RWIdentitySet, and RWSet.
|
virtual |
Returns the number of items in the collection which are "matches" for t. See function find() for a definition of matches.
Implements RWCollection.
Reimplemented in RWSet.
bool RWHashTable::operator!= | ( | const RWHashTable & | ) | const |
Returns the negation of operator==().
bool RWHashTable::operator<= | ( | const RWHashTable & | t | ) | const |
Returns true
if self is a subset of t, that is, every element of self has a counterpart in t which isEqual().
RWHashTable & RWHashTable::operator= | ( | const RWHashTable & | t | ) |
Assignment operator. Sets self as a shallow copy of t. Afterwards, the two tables have the same number of buckets. Hence, the members need not be and will not be rehashed.
RWHashTable & RWHashTable::operator= | ( | RWHashTable && | t | ) |
Move assignment. Self takes ownership of the data owned by t.
bool RWHashTable::operator== | ( | const RWHashTable & | t | ) | const |
Returns true
if self and t have the same number of elements and if for every key in self there is a corresponding key in t which isEqual().
|
virtual |
Removes and returns a pointer to the first item in the collection which "matches" the object pointed to by target. Returns nil
if no object was found. Does not delete the object. See function find() for a definition of matches.
Implements RWCollection.
Reimplemented in RWHashDictionary, and RWIdentitySet.
|
virtual |
Resizes the internal hash table to have n buckets. This causes rehashing all the members of the collection. If n is zero, resizes to 3*
entries()/2
.
void RWHashTable::swap | ( | RWHashTable & | t | ) |
Swaps the data owned by self with the data owned by t.
Copyright © 2024 Rogue Wave Software, Inc., a Perforce company. All Rights Reserved. |