PLearn 0.1
Public Member Functions | Public Attributes | Private Member Functions | Private Attributes
PLearn::Hash< KeyType, DataType > Class Template Reference

#include <Hash.h>

Inheritance diagram for PLearn::Hash< KeyType, DataType >:
Inheritance graph
[legend]
Collaboration diagram for PLearn::Hash< KeyType, DataType >:
Collaboration graph
[legend]

List of all members.

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

Detailed Description

template<class KeyType, class DataType>
class PLearn::Hash< KeyType, DataType >

Definition at line 88 of file Hash.h.


Constructor & Destructor Documentation

template<class KeyType , class DataType >
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();
}

Here is the call graph for this function:

template<class KeyType , class DataType >
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;
    }
}

Here is the call graph for this function:

template<class KeyType , class DataType >
PLearn::Hash< KeyType, DataType >::Hash ( const Hash< KeyType, DataType > &  obj) [inline, private]

The copy constructor is not yet defined...

Definition at line 147 of file Hash.h.


Member Function Documentation

template<class KeyType , class DataType >
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; 
}

Here is the caller graph for this function:

template<class KeyType , class DataType >
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);
}

Here is the call graph for this function:

template<class KeyType , class DataType >
unsigned int PLearn::Hash< KeyType, DataType >::cardinal ( ) const

returns number of elements

!<

returns the number of used slots.

Definition at line 394 of file Hash.h.

{ 
    return elements;
}
template<class KeyType , class DataType >
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;
}

Here is the call graph for this function:

template<class KeyType , class DataType >
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().

{
    unsigned int t = (tableSize * 6) / 10;
    while (pgcd(tableSize,t)!=1) t--;
    pace = t;
}

Here is the caller graph for this function:

template<class KeyType , class DataType >
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;
}

Here is the call graph for this function:

template<class KeyType , class DataType >
void PLearn::Hash< KeyType, DataType >::diagnostics ( unsigned int clusters,
unsigned int maxCluster 
) const
Parameters:
clusters...and average cluster size is cardinal()/clusters

Definition at line 607 of file Hash.h.

References __max, c, and d.

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);
        }
    }
}

Here is the caller graph for this function:

template<class KeyType , class DataType >
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);
}

Here is the call graph for this function:

template<class KeyType , class DataType >
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 h = hashKey(key);
    jumps=0;
    while ( (table[h]) && (jumps<tableSize) && 
            ((table[h]==Hash_DELETED_SLOT) || (*table[h]->key!=key) ) )
    {
        h = (h+pace) % tableSize;
        jumps++;
    }

    return h;
}
template<class KeyType , class DataType >
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.

{
    unsigned int h = hashKey(key);

    jumps=0;
    while ((table[h]>Hash_DELETED_SLOT) && (jumps<tableSize))
    {
        h = (h+pace) % tableSize;
        jumps++;
    }

    return h;
}
template<class KeyType , class DataType >
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;
    }
}

Here is the caller graph for this function:

template<class KeyType , class DataType >
bool PLearn::Hash< KeyType, DataType >::full ( ) const

diagnostics

is the table full?

Tells you if you should resize the table now.

Definition at line 417 of file Hash.h.

{
    return elements == tableSize;
}
template<class KeyType , class DataType >
HashKeyDataPair<KeyType,DataType>** PLearn::Hash< KeyType, DataType >::getTable ( ) const [inline]

Definition at line 123 of file Hash.h.

{ return table; }
template<class KeyType , class DataType >
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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class KeyType , class DataType >
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.

{
    int l = key.byteLength();
    unsigned int hashKey=0u;
    unsigned char *pKey = l>0?((unsigned char *)(char *)key):(unsigned char*)0;
  
    for (int i=0;i<l;i++)
    {
        unsigned char t = (hashKey >> 24);
        hashKey = (hashKey << 8) + pKey[i];
        hashKey ^= Hash_NOMBRES_MAGIQUES[t];
    }

    return hashKey % tableSize;
}
template<class KeyType , class DataType >
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;
}
template<class KeyType , class DataType >
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;
}
template<class KeyType , class DataType >
void PLearn::Hash< KeyType, DataType >::operator= ( const Hash< KeyType, DataType > &  obj) [inline, private]

not permitted...

Definition at line 148 of file Hash.h.

template<class KeyType , class DataType >
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;
}
template<class KeyType , class DataType >
unsigned int PLearn::Hash< KeyType, DataType >::pgcd ( unsigned int  a,
unsigned int  b 
) const [private]

Definition at line 204 of file Hash.h.

References a, and b.

{
    while (b)
    {
        unsigned int r=(a % b);
        a=b;
        b=r;
    }
    return a;
}
template<class KeyType , class DataType >
unsigned int PLearn::Hash< KeyType, DataType >::probes ( ) const

returns the number of probe generate by last query

Definition at line 595 of file Hash.h.

{
    return jumps+1;
}
template<class KeyType , class DataType >
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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class KeyType , class DataType >
bool PLearn::Hash< KeyType, DataType >::resizeTime ( ) const

is it time to resize the table?

Tells you if you should resize the table now.

Definition at line 406 of file Hash.h.

{
    return (elements > (tableSize * 7) / 10);
}
template<class KeyType , class DataType >
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;
}

Here is the caller graph for this function:


Member Data Documentation

template<class KeyType , class DataType >
DataType* PLearn::Hash< KeyType, DataType >::data_table [private]

Definition at line 107 of file Hash.h.

template<class KeyType , class DataType >
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().

template<class KeyType , class DataType >
HashKeyDataPair<KeyType,DataType>* PLearn::Hash< KeyType, DataType >::hash_table [private]

Definition at line 108 of file Hash.h.

template<class KeyType , class DataType >
bool PLearn::Hash< KeyType, DataType >::isStatic

static or dynamic memory allocation

Definition at line 112 of file Hash.h.

template<class KeyType , class DataType >
unsigned int PLearn::Hash< KeyType, DataType >::jumps [private]

number of probes in last operation

Definition at line 95 of file Hash.h.

template<class KeyType , class DataType >
KeyType* PLearn::Hash< KeyType, DataType >::key_table [private]

Definition at line 106 of file Hash.h.

template<class KeyType , class DataType >
unsigned int PLearn::Hash< KeyType, DataType >::next_free_slot [private]

the next free slot in the 3 tables

Definition at line 109 of file Hash.h.

template<class KeyType , class DataType >
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().

template<class KeyType , class DataType >
bool PLearn::Hash< KeyType, DataType >::static_tables_initialized [private]

the following field are only used in static mode

true when the tables are initialized

Definition at line 105 of file Hash.h.

template<class KeyType , class DataType >
HashKeyDataPair<KeyType,DataType>** PLearn::Hash< KeyType, DataType >::table [private]
template<class KeyType , class DataType >
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().


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines