|
PLearn 0.1
|
#include <Hash.h>


Public Member Functions | |
| bool | add (const KeyType &, const DataType &) |
| returns false if table is full | |
| void | addAndResize (const KeyType &, const DataType &) |
| add() and resize() if resizeTime() | |
| bool | element (const KeyType &) |
| bool | del (const KeyType &) |
| unsigned int | hashAddress (const KeyType &) |
| returns Hash_UNUSED_TAG (-1) if not in table | |
| DataType * | operator[] (unsigned int addr) const |
| data at hashAddress (or 0 if none have been put) | |
| KeyType * | operator() (unsigned int addr) const |
| key at hashAddress (or 0 if none have been put) | |
| HashKeyDataPair< KeyType, DataType > ** | getTable () const |
| unsigned int | size () const |
| returns tableSize; | |
| unsigned int | cardinal () const |
| returns number of elements | |
| void | flush () |
| cleans the table without resizing it | |
| void | initializeTable (unsigned int size) |
| initialize the static tables | |
| bool | full () const |
| diagnostics | |
| bool | resizeTime () const |
| is it time to resize the table? | |
| void | resize (int newsize=-1) |
| resizes the table to maintain a good sparseness | |
| void | cleanup () |
| (default=-1 quadruples the table size) | |
| unsigned int | probes () const |
| returns the number of probe generate by last query | |
| void | diagnostics (unsigned int &clusters, unsigned int &maxCluster) const |
| Hash (unsigned int size=10000, bool static_allocation=false) | |
| !< | |
| ~Hash () | |
Public Attributes | |
| bool | isStatic |
| static or dynamic memory allocation | |
Private Member Functions | |
| unsigned int | hashKey (const KeyType &) const |
| computes the primary hash function on the string (length=0 says to look for \0 in bytes to determine length) | |
| void | computePace () |
| computes the magic number used by the secondary hash function | |
| unsigned int | pgcd (unsigned int, unsigned int) const |
| unsigned int | find (const KeyType &) |
| returns either an empty slot or the slot with the key in it | |
| unsigned int | findGap (const KeyType &) |
| returns the first empty slot it finds | |
| Hash (const Hash &obj) | |
| The copy constructor is not yet defined... | |
| void | operator= (const Hash &obj) |
| not permitted... | |
Private Attributes | |
| HashKeyDataPair< KeyType, DataType > ** | table |
| a pointer to a table of <key,data> | |
| unsigned int | tableSize |
| total number of slots | |
| unsigned int | elements |
| number of used slots | |
| unsigned int | pace |
| used by the secondary hash function | |
| unsigned int | jumps |
| number of probes in last operation | |
| bool | static_tables_initialized |
| the following field are only used in static mode | |
| KeyType * | key_table |
| DataType * | data_table |
| HashKeyDataPair< KeyType, DataType > * | hash_table |
| unsigned int | next_free_slot |
| the next free slot in the 3 tables | |
| PLearn::Hash< KeyType, DataType >::Hash | ( | unsigned int | size = 10000, |
| bool | static_allocation = false |
||
| ) |
!<
Creates the table with size entries
allocates a table of 0s
Definition at line 550 of file Hash.h.
References PLearn::Hash< KeyType, DataType >::computePace(), i, PLearn::Hash< KeyType, DataType >::size(), and PLearn::Hash< KeyType, DataType >::table.
: tableSize(size), elements(0), static_tables_initialized(false), next_free_slot(0), isStatic(static_allocation) { //table = (HashKeyDataPair<KeyType,DataType> **)calloc(size, sizeof(HashKeyDataPair<KeyType,DataType> *)); assert (size > 0); typedef HashKeyDataPair<KeyType,DataType>* hash_key_data_table; table = new hash_key_data_table[size]; for (unsigned int i=0; i<size; i++) table[i]=0; computePace(); }

| PLearn::Hash< KeyType, DataType >::~Hash | ( | ) |
before really deleting the hash_table, we set to zero the key and data pointers in the elements of this array, to ensure that they don't get deleted by the delete[] hash_table (since those pointers are not dynamically allocated but rather point into key_table and data_table respectively).
Definition at line 567 of file Hash.h.
References PLearn::flush(), and i.
{
if (table)
{
flush();
delete[] table;
}
if (isStatic) {
long i, maxi=tableSize;
for (i=0; i<maxi; ++i) {
hash_table[i].key = 0;
hash_table[i].data = 0;
}
delete[] key_table;
delete[] data_table;
delete[] hash_table;
}
}

| PLearn::Hash< KeyType, DataType >::Hash | ( | const Hash< KeyType, DataType > & | obj | ) | [inline, private] |
| bool PLearn::Hash< KeyType, DataType >::add | ( | const KeyType & | key, |
| const DataType & | data | ||
| ) |
returns false if table is full
Return False only if the table is full. Use resizeTime() to determine if the table should be resized
if already element delete it
< no slot found (bummer!)
< no slot found (bummer!)
Definition at line 286 of file Hash.h.
References PLearn::Hash_DELETED_SLOT, and PLERROR.
Referenced by PLearn::Hash< KeyType, DataType >::cleanup(), PLearn::SimpleDB< KeyType, QueryResult >::indexColumn(), and PLearn::Hash< KeyType, DataType >::resize().
{
unsigned int h = findGap(key);
if ((table[h]>Hash_DELETED_SLOT) && (*table[h]->key==key))
{
if (!isStatic)
delete table[h];
table[h]=0;
elements--;
}
if ((table[h]==0) || (table[h]==Hash_DELETED_SLOT))
{
if (!isStatic)
table[h] = new HashKeyDataPair<KeyType,DataType>(key, data);
else {
if (static_tables_initialized==false)
PLERROR("You must initialized the static table before using the add method");
if (next_free_slot == tableSize)
return false;
table[h] = &hash_table[next_free_slot];
table[h]->key = &key_table[next_free_slot];
table[h]->data = &data_table[next_free_slot];
key_table[next_free_slot] = key;
data_table[next_free_slot] = data;
next_free_slot++;
}
elements++;
return true;
}
else return false;
}

| void PLearn::Hash< KeyType, DataType >::addAndResize | ( | const KeyType & | key, |
| const DataType & | data | ||
| ) |
add() and resize() if resizeTime()
call add() and resize() if resizeTime()
Definition at line 325 of file Hash.h.
References PLearn::add().
{
if (resizeTime()) resize();
add(key,data);
}

| unsigned int PLearn::Hash< KeyType, DataType >::cardinal | ( | ) | const |
| void PLearn::Hash< KeyType, DataType >::cleanup | ( | ) |
(default=-1 quadruples the table size)
cleanup the table to maintain efficiency
Cleans the table after some "deletes"
< dont deallocate t's table
Definition at line 458 of file Hash.h.
References PLearn::Hash< KeyType, DataType >::add(), PLearn::Hash< KeyType, DataType >::elements, PLearn::flush(), PLearn::Hash_DELETED_SLOT, i, PLearn::Hash< KeyType, DataType >::pace, PLearn::Hash< KeyType, DataType >::table, and PLearn::Hash< KeyType, DataType >::tableSize.
{
Hash t(tableSize);
for (unsigned int i=0;i<tableSize;i++)
if (table[i] > Hash_DELETED_SLOT)
t.add(*table[i]->key,*table[i]->data);
flush();
delete[] table;
table = t.table;
t.table = 0;
tableSize = t.tableSize;
elements = t.elements;
pace = t.pace;
t.table=0;
}

| void PLearn::Hash< KeyType, DataType >::computePace | ( | ) | [private] |
computes the magic number used by the secondary hash function
The pace is the secondary hash function. rather than doing a straight forward linear probing, we do a pseudorandomized probing
Definition at line 222 of file Hash.h.
Referenced by PLearn::Hash< KeyType, DataType >::Hash().

| bool PLearn::Hash< KeyType, DataType >::del | ( | const KeyType & | key | ) |
deletes the entry, but leaves a marker so that probes continue to work properly
Definition at line 337 of file Hash.h.
References PLearn::find(), and PLearn::Hash_DELETED_SLOT.
{
unsigned int h = find(key);
if (table[h]>Hash_DELETED_SLOT)
{
if (!isStatic)
delete table[h];
table[h] = (HashKeyDataPair<KeyType,DataType> *)Hash_DELETED_SLOT;
elements--;
return true;
}
else return false;
}

| void PLearn::Hash< KeyType, DataType >::diagnostics | ( | unsigned int & | clusters, |
| unsigned int & | maxCluster | ||
| ) | const |
| clusters | ...and average cluster size is cardinal()/clusters |
Definition at line 607 of file Hash.h.
Referenced by PLearn::SimpleDB< KeyType, QueryResult >::indexColumn().
{
clusters=0;
maxCluster=0;
unsigned int d=0;
while (d<tableSize)
{
while ((d<tableSize) && (table[d]==0)) d++;
if (d<tableSize)
{
clusters++;
unsigned int c=0;
while ((d<tableSize) && (table[d])) c++,d++;
maxCluster=__max(maxCluster,c);
}
}
}

| bool PLearn::Hash< KeyType, DataType >::element | ( | const KeyType & | key | ) |
returns true if the string is in the table, false otherwise
Definition at line 358 of file Hash.h.
References PLearn::find(), and PLearn::Hash_DELETED_SLOT.
{
unsigned int h = find(key);
return (table[h]>Hash_DELETED_SLOT) && (*table[h]->key==key);
}

| unsigned int PLearn::Hash< KeyType, DataType >::find | ( | const KeyType & | key | ) | [private] |
returns either an empty slot or the slot with the key in it
find will stop either on an empty slot or on a slot that contains the searched string.
PROBLEME GRAVE ICI: si key->h mais h est occupe, donc key-> jump to h' ensuite si table[h] a ete delete un find(key) donnera h (qui contient "Hash_DELETED_SLOT") plutot que h'
while ( (table[h]>Hash_DELETED_SLOT) && //!< FIX ABOVE PROBLEM
Definition at line 236 of file Hash.h.
References PLearn::Hash_DELETED_SLOT.
| unsigned int PLearn::Hash< KeyType, DataType >::findGap | ( | const KeyType & | key | ) | [private] |
returns the first empty slot it finds
find will stop either on an empty slot or on a slot that contains the searched string.
Definition at line 264 of file Hash.h.
References PLearn::Hash_DELETED_SLOT.
| void PLearn::Hash< KeyType, DataType >::flush | ( | ) |
cleans the table without resizing it
Erases all strings, but does not destroy the table itself
Definition at line 509 of file Hash.h.
References PLearn::Hash_DELETED_SLOT, and i.
Referenced by PLearn::SimpleDB< KeyType, QueryResult >::indexColumn().
{
if (table)
{
for (unsigned int i=0;i<tableSize;i++)
if (table[i]>Hash_DELETED_SLOT)
{
if (!isStatic)
delete table[i];
table[i]=0;
}
elements=0;
}
}

| bool PLearn::Hash< KeyType, DataType >::full | ( | ) | const |
| HashKeyDataPair<KeyType,DataType>** PLearn::Hash< KeyType, DataType >::getTable | ( | ) | const [inline] |
| unsigned int PLearn::Hash< KeyType, DataType >::hashAddress | ( | const KeyType & | key | ) |
returns Hash_UNUSED_TAG (-1) if not in table
Gives the address in the table of the string (possibly Hash_UNUSED_TAG if there is no such string in the table)
Definition at line 371 of file Hash.h.
References PLearn::find(), PLearn::Hash_DELETED_SLOT, and PLearn::Hash_UNUSED_TAG.
Referenced by PLearn::SimpleDB< KeyType, QueryResult >::indexColumn().
{
unsigned int h = find(key);
if ( (table[h]>Hash_DELETED_SLOT) && (*table[h]->key==key) )
return h;
else return Hash_UNUSED_TAG;
}


| unsigned int PLearn::Hash< KeyType, DataType >::hashKey | ( | const KeyType & | key | ) | const [private] |
computes the primary hash function on the string (length=0 says to look for \0 in bytes to determine length)
Computes the remainder (mod AMagicNumber) of the key
Definition at line 186 of file Hash.h.
References PLearn::Hash_NOMBRES_MAGIQUES, i, and u.
| void PLearn::Hash< KeyType, DataType >::initializeTable | ( | unsigned int | size | ) |
initialize the static tables
!<
Creates the static table with size entries
Definition at line 529 of file Hash.h.
References PLERROR, and PLWARNING.
{
if (!isStatic)
PLERROR("The static tables can be initialized only in static mode");
if (static_tables_initialized==false) {
key_table = new KeyType[size];
data_table = new DataType[size];
hash_table = new HashKeyDataPair<KeyType,DataType>[size];
}
else
PLWARNING("The static tables are already initialized");
static_tables_initialized = true;
}
| KeyType * PLearn::Hash< KeyType, DataType >::operator() | ( | unsigned int | addr | ) | const |
key at hashAddress (or 0 if none have been put)
!<
Arguments to () is hashAddress
Definition at line 494 of file Hash.h.
References PLearn::Hash_DELETED_SLOT.
{
if ((addr<tableSize) && (table[addr]>Hash_DELETED_SLOT))
return table[addr]->key;
else return 0;
}
| void PLearn::Hash< KeyType, DataType >::operator= | ( | const Hash< KeyType, DataType > & | obj | ) | [inline, private] |
| DataType * PLearn::Hash< KeyType, DataType >::operator[] | ( | unsigned int | addr | ) | const |
data at hashAddress (or 0 if none have been put)
!<
Arguments to [] is hashAddress
Definition at line 482 of file Hash.h.
References PLearn::Hash_DELETED_SLOT.
{
if ((addr<tableSize) && (table[addr]>Hash_DELETED_SLOT))
return table[addr]->data;
else return 0;
}
| unsigned int PLearn::Hash< KeyType, DataType >::pgcd | ( | unsigned int | a, |
| unsigned int | b | ||
| ) | const [private] |
| unsigned int PLearn::Hash< KeyType, DataType >::probes | ( | ) | const |
| void PLearn::Hash< KeyType, DataType >::resize | ( | int | newsize = -1 | ) |
resizes the table to maintain a good sparseness
Resizes the table by producing an enlarged copy (not in situ rehashing)
< dont deallocate t's table
Definition at line 429 of file Hash.h.
References PLearn::Hash< KeyType, DataType >::add(), PLearn::Hash< KeyType, DataType >::elements, PLearn::endl(), PLearn::flush(), PLearn::Hash_DELETED_SLOT, i, PLearn::Hash< KeyType, DataType >::pace, PLearn::Hash< KeyType, DataType >::table, and PLearn::Hash< KeyType, DataType >::tableSize.
Referenced by PLearn::SimpleDB< KeyType, QueryResult >::indexColumn().
{
//PLWARNING("You are resizing the Hash table in static mode");
if (newsize<0) newsize=tableSize*4;
if (newsize<=(int)tableSize) return;
Hash t(newsize);
cout << "Resize Hash table to " << newsize << endl;
for (unsigned int i=0;i<tableSize;i++)
if (table[i] > Hash_DELETED_SLOT)
t.add(*table[i]->key,*table[i]->data);
flush();
delete[] table;
table = t.table;
t.table = 0;
tableSize = t.tableSize;
elements = t.elements;
pace = t.pace;
t.table= 0;
}


| bool PLearn::Hash< KeyType, DataType >::resizeTime | ( | ) | const |
| unsigned int PLearn::Hash< KeyType, DataType >::size | ( | ) | const |
returns tableSize;
!<
returns the total number of slots
Definition at line 385 of file Hash.h.
Referenced by PLearn::Hash< KeyType, DataType >::Hash().
{
return tableSize;
}

DataType* PLearn::Hash< KeyType, DataType >::data_table [private] |
unsigned int PLearn::Hash< KeyType, DataType >::elements [private] |
number of used slots
Definition at line 93 of file Hash.h.
Referenced by PLearn::Hash< KeyType, DataType >::cleanup(), and PLearn::Hash< KeyType, DataType >::resize().
HashKeyDataPair<KeyType,DataType>* PLearn::Hash< KeyType, DataType >::hash_table [private] |
| bool PLearn::Hash< KeyType, DataType >::isStatic |
unsigned int PLearn::Hash< KeyType, DataType >::jumps [private] |
KeyType* PLearn::Hash< KeyType, DataType >::key_table [private] |
unsigned int PLearn::Hash< KeyType, DataType >::next_free_slot [private] |
unsigned int PLearn::Hash< KeyType, DataType >::pace [private] |
used by the secondary hash function
Definition at line 94 of file Hash.h.
Referenced by PLearn::Hash< KeyType, DataType >::cleanup(), and PLearn::Hash< KeyType, DataType >::resize().
bool PLearn::Hash< KeyType, DataType >::static_tables_initialized [private] |
HashKeyDataPair<KeyType,DataType>** PLearn::Hash< KeyType, DataType >::table [private] |
a pointer to a table of <key,data>
Definition at line 91 of file Hash.h.
Referenced by PLearn::Hash< KeyType, DataType >::cleanup(), PLearn::Hash< KeyType, DataType >::Hash(), and PLearn::Hash< KeyType, DataType >::resize().
unsigned int PLearn::Hash< KeyType, DataType >::tableSize [private] |
total number of slots
Definition at line 92 of file Hash.h.
Referenced by PLearn::Hash< KeyType, DataType >::cleanup(), and PLearn::Hash< KeyType, DataType >::resize().
1.7.4