SourcePro® API Reference Guide

 
Loading...
Searching...
No Matches

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>

Inheritance diagram for RWHashTable:
RWCollection RWCollectable RWSet RWFactory RWHashDictionary RWIdentitySet RWIdentityDictionary

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 RWCollectablecopy () const
 
virtual size_t entries () const
 
virtual RWCollectablefind (const RWCollectable *) const
 
virtual RWCollectableinsert (RWCollectable *a)
 
virtual RWClassID isA () const
 
virtual bool isEmpty () const
 
virtual bool isEqual (const RWCollectable *) const
 
virtual RWConstIteratornewConstIterator () const
 
virtual RWIteratornewIterator ()
 
virtual RWCollectablenewSpecies () const
 
virtual size_t occurrencesOf (const RWCollectable *) const
 
bool operator!= (const RWHashTable &) const
 
bool operator<= (const RWHashTable &t) const
 
RWHashTableoperator= (const RWHashTable &t)
 
RWHashTableoperator= (RWHashTable &&t)
 
bool operator== (const RWHashTable &t) const
 
virtual RWCollectableremove (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
 
RWCollectionselect (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
 

Detailed Description

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.

Synopsis
#include <rw/hashtab.h>
A simple hash table for objects inheriting from RWCollectable. Uses chaining (as implemented by class...
Definition hashtab.h:121
Persistence
Polymorphic
Example
#include <rw/hashtab.h>
#include <rw/tools/ctdatetime.h>
int main() {
RWHashTable table;
table.insert(july);
table.insert(may);
table.insert(feb);
table.insert(aug);
std::cout << "Table contains " << table.entries() << " entries ";
std::cout << "and it does" << (table.contains(&key) ? " " : " not ")
<< "contain the key " << key << std::endl;
delete july;
delete may;
delete feb;
delete aug;
return 0;
}
Provides a polymorphically persistable RWDateTime.
Definition ctdatetime.h:56
virtual bool contains(const RWCollectable *target) const
@ setDate
Definition tools/datetime.h:253
virtual RWCollectable * insert(RWCollectable *a)
virtual size_t entries() const
Definition hashtab.h:257

Program output:

Table contains 4 entries and it does contain the key Tue Feb 22 00:00:00 1983

Constructor & Destructor Documentation

◆ RWHashTable() [1/4]

RWHashTable::RWHashTable ( )

Constructs an empty hash table with RWCollection::DEFAULT_CAPACITY buckets.

◆ RWHashTable() [2/4]

RWHashTable::RWHashTable ( size_t N)

Constructs an empty hash table with N buckets.

◆ RWHashTable() [3/4]

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() [4/4]

RWHashTable::RWHashTable ( RWHashTable && t)

Move constructor. The constructed RWHashTable takes ownership of the data owned by t.

Condition:
This method is available only on platforms with rvalue reference support.

Member Function Documentation

◆ apply()

virtual void RWHashTable::apply ( RWapplyCollectable ap,
void *  )
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.

◆ clear()

virtual void RWHashTable::clear ( )
virtual

Removes all objects from the collection. Does not delete the objects themselves.

Implements RWCollection.

Reimplemented in RWHashDictionary.

◆ copy()

virtual RWCollectable * RWHashTable::copy ( ) const
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.

◆ entries()

virtual size_t RWHashTable::entries ( ) const
inlinevirtual

Returns the total number of items in the collection.

Implements RWCollection.

◆ find()

virtual RWCollectable * RWHashTable::find ( const RWCollectable * target) const
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.

◆ insert()

virtual RWCollectable * RWHashTable::insert ( RWCollectable * a)
virtual

Returns a if successful, otherwise rwnil.

Note
If self is a collection of key-value pairs (e.g. RWHashDictionary), this function throws std::bad_cast if c does not inherit from RWCollectableAssociation. If the collection does not contain an association with a key that "matches" the key of c, then a copy of the association is inserted and that association's key is returned. Otherwise, the insert fails by returning either rwnil or a pointer to the existing association's key.

Implements RWCollection.

Reimplemented in RWHashDictionary, RWIdentitySet, and RWSet.

◆ isA()

virtual RWClassID RWHashTable::isA ( ) const
virtual

Returns __RWHASHTABLE.

Reimplemented from RWCollection.

Reimplemented in RWHashDictionary, RWIdentityDictionary, RWIdentitySet, and RWSet.

◆ isEmpty()

virtual bool RWHashTable::isEmpty ( ) const
inlinevirtual

Returns true if the collection is empty, otherwise returns false.

Implements RWCollection.

◆ isEqual()

virtual bool RWHashTable::isEqual ( const RWCollectable * t) const
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.

◆ newConstIterator()

virtual RWConstIterator * RWHashTable::newConstIterator ( ) const
virtual

Returns a const pointer to a dynamically allocated iterator for the collection.

Implements RWCollection.

Reimplemented in RWHashDictionary, and RWSet.

◆ newIterator()

virtual RWIterator * RWHashTable::newIterator ( )
virtual

Returns a dynamically allocated iterator for the collection.

Implements RWCollection.

Reimplemented in RWHashDictionary, and RWSet.

◆ newSpecies()

virtual RWCollectable * RWHashTable::newSpecies ( ) const
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.

◆ occurrencesOf()

virtual size_t RWHashTable::occurrencesOf ( const RWCollectable * t) const
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.

◆ operator!=()

bool RWHashTable::operator!= ( const RWHashTable & ) const

Returns the negation of operator==().

◆ 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().

◆ operator=() [1/2]

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.

◆ operator=() [2/2]

RWHashTable & RWHashTable::operator= ( RWHashTable && t)

Move assignment. Self takes ownership of the data owned by t.

Condition:
This method is available only on platforms with rvalue reference support.

◆ operator==()

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().

◆ remove()

virtual RWCollectable * RWHashTable::remove ( const RWCollectable * target)
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.

◆ resize()

virtual void RWHashTable::resize ( size_t n = 0)
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.

◆ swap()

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.