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