Hashtable Class Reference

#include <Hashtable.hpp>

Collaboration diagram for Hashtable:

List of all members.

Public Member Functions
	Hashtable (UINT32(*func1)(void *), SINT32(*func2)(void *, void *), SINT32 capacity=1000, float loadFactor=0.75)
	~Hashtable ()
CAMutex *	getMutex ()
bool	isEmpty ()
	Tests if the hashtable is empty.
bool	containsKey (void *key)
	Testet, ob ein bestimmter Schlssel im Hashtable enthalten ist.
void *	getValue (void *key)
	Sucht den zu einem Schlssel (key) passenden Wert (value)
UINT32	getSize ()
UINT32	getCapacity ()
void *	put (void *key, void *value)
	Mit dieser Funktion wird ein neuer Eintrag bestehend aus einem Zugriffsschlssel (key) und dessen Wert (value) in den Hashtable eingefgt.
void *	remove (void *key)
	entfernt einen Eintrag aus einem Hashtable
void	clear (SINT8 keyMode=HASH_EMPTY_NONE, SINT8 valueMode=HASH_EMPTY_NONE)
Static Public Member Functions
static UINT32	stringHash (UINT8 *str)
static SINT32	stringCompare (UINT8 *a, UINT8 **b)
static UINT32	hashUINT64 (UINT64 *a_number)
static SINT32	compareUINT64 (UINT64 *a_numberA, UINT64 *a_numberB)
static UINT32	hashUINT32 (UINT32 *a_number)
static SINT32	compareUINT32 (UINT32 *a_numberA, UINT32 *a_numberB)
Protected Member Functions
bool	rehash ()
	Der Hashtable wird in der Kapazitt verdoppelt und neu aufgebaut.
struct Entry *	getHashEntry (void *key)
	Gibt den zu einem Schlssel passenden Eintrag eines Hashtables zurueck.
Protected Attributes
SINT32	m_capacity
SINT32	m_count
SINT32	m_threshold
SINT32	m_modCount
float	m_loadFactor
struct Entry **	m_table
UINT32(*	m_hashFunc )(void *)
SINT32(*	m_compareFunc )(void *, void *)
Private Attributes
CAMutex *	m_pMutex

---

Detailed Description

Definition at line 14 of file Hashtable.hpp.

---

Constructor & Destructor Documentation

Hashtable::Hashtable	(	UINT32(*)(void *)	func1,
		SINT32(*)(void *, void *)	func2,
		SINT32	capacity = 1000,
		float	loadFactor = 0.75
	)

Definition at line 74 of file Hashtable.cpp.

References m_capacity, m_compareFunc, m_count, m_hashFunc, m_loadFactor, m_modCount, m_pMutex, m_table, and m_threshold.

{
  m_pMutex = new CAMutex();
  
  if (capacity < 0 || loadFactor <= 0)
  {
    return;
  }

  if (!capacity)
  {
    capacity = 1;
  } 
  
  m_table = new Entry*[capacity];
  for (SINT32 i = 0; i < capacity; i++)
  {
    m_table[i] = NULL;
  }
  
  m_threshold = (UINT32)(capacity * loadFactor);
  m_modCount = 0;
  m_count = 0;
  m_loadFactor = loadFactor;
  m_capacity = capacity;

  //m_hashFunc = (UINT32 (*)(void *))stringHash;
  m_hashFunc = hashFunc;
  //m_compareFunc = (SINT32 (*)(void *,void *))stringCompare;
  m_compareFunc = compareFunc;
}

Hashtable::~Hashtable

(

)

Definition at line 107 of file Hashtable.cpp.

References Entry::e_Next, CAMutex::lock(), m_capacity, m_compareFunc, m_count, m_hashFunc, m_loadFactor, m_modCount, m_pMutex, m_table, m_threshold, and CAMutex::unlock().

{
  m_pMutex->lock();
  
  for(SINT32 index = 0; index < m_capacity; index++)
  {
    struct Entry *e,*next;

    for(e = m_table[index]; e; e = next)
    {
      next = e->e_Next;
      delete e;
      e = NULL;
    }
    m_table[index] = NULL;
  }
  delete m_table;
  m_table = NULL;
  m_capacity = 0;
  m_count = 0;
  m_threshold = 0;
  m_loadFactor = 0;
  m_modCount = 0;
  m_hashFunc = NULL;
  m_compareFunc = NULL;
  
  m_pMutex->unlock();
  
  delete m_pMutex;
  m_pMutex = NULL;
}

Here is the call graph for this function:

---

Member Function Documentation

void Hashtable::clear	(	SINT8	keyMode = HASH_EMPTY_NONE,
		SINT8	valueMode = HASH_EMPTY_NONE
	)

Definition at line 306 of file Hashtable.cpp.

References Entry::e_Key, Entry::e_Next, Entry::e_Value, HASH_EMPTY_DELETE, m_capacity, m_count, and m_table.

Referenced by CAAccountingInstance::~CAAccountingInstance().

{ 
  if (!m_table)
  {
    return;
  }
  
  //CAMsg::printMsg(LOG_INFO, "Hashtable: Clearing...\n");

  for(SINT32 index = 0; index < m_capacity; index++)
  {
    struct Entry *e,*next;

    for(e = m_table[index]; e; e = next)
    {
      switch(keyMode)
      {
        case HASH_EMPTY_DELETE:
          if (e->e_Key)
          {
            delete e->e_Key;
            e->e_Key = NULL;
          }
          break;
//        case HASH_EMPTY_FREE:
//          free(e->e_Key);
        default:
          e->e_Key = NULL;    
      }
      switch(valueMode)
      {
        case HASH_EMPTY_DELETE:
          if (e->e_Value)
          {
            delete e->e_Value;
            e->e_Value = NULL;
          }
          break;
//        case HASH_EMPTY_FREE:
//          free(e->e_Value);
        default:
          e->e_Value = NULL;
      }
      next = e->e_Next;
      delete e;
      e = NULL;
    }
    m_table[index] = NULL;
  }
  m_count = 0;
  
  //CAMsg::printMsg(LOG_INFO, "Hashtable: Has been cleared!\n");
}

static SINT32 Hashtable::compareUINT32	(	UINT32 *	a_numberA,
		UINT32 *	a_numberB
	)		[inline, static]

Definition at line 64 of file Hashtable.hpp.

    {
      return (*a_numberA == *a_numberB)? 0 : ((*a_numberA > *a_numberB)? 1 : -1);
    }

static SINT32 Hashtable::compareUINT64	(	UINT64 *	a_numberA,
		UINT64 *	a_numberB
	)		[inline, static]

Definition at line 43 of file Hashtable.hpp.

Referenced by CAAccountingInstance::CAAccountingInstance().

    {
      return (*a_numberA == *a_numberB)? 0 : ((*a_numberA > *a_numberB)? 1 : -1);
      /*
      if (*a_numberA == *a_numberB)
      {
        return 0;
      }
      else if (*a_numberA > *a_numberB)
      {
        return 1;
      }
      else
      {
        return -1;
      }*/
    } 

bool Hashtable::containsKey

(

void *

key

)

Testet, ob ein bestimmter Schlssel im Hashtable enthalten ist.

Parameters:

key	der gesuchte Schlssel

Returns:

success TRUE, wenn der Schlssel enthalten ist, FALSE, wenn nicht

Definition at line 159 of file Hashtable.cpp.

References getHashEntry().

{
  return getHashEntry(key) ? true : false;
}

Here is the call graph for this function:

UINT32 Hashtable::getCapacity

(

)

Definition at line 365 of file Hashtable.cpp.

References m_capacity.

{
  return m_capacity;
}

struct Entry * Hashtable::getHashEntry

(

void *

key

)

[read, protected]

Gibt den zu einem Schlssel passenden Eintrag eines Hashtables zurueck.

Parameters:

key	der zu suchende Schlssel

Returns:

entry der gefundene Eintrag oder NULL

Definition at line 442 of file Hashtable.cpp.

References Entry::e_Key, Entry::e_Next, m_capacity, m_compareFunc, m_hashFunc, and m_table.

Referenced by containsKey(), and getValue().

{ 
  if (!key || !m_table)
  {
    return NULL;
  }
  
  struct Entry *e;
  UINT32 hash = m_hashFunc(key);
  
  for(e = m_table[hash % m_capacity]; e; e = e->e_Next)
  {   
    if (m_hashFunc(e->e_Key) == hash && !m_compareFunc(e->e_Key,key))
    {
      return e;
    }
  }
  
  return NULL;
}

CAMutex * Hashtable::getMutex

(

)

Definition at line 55 of file Hashtable.cpp.

References m_pMutex.

Referenced by CAAccountingInstance::__newSettlementTransaction(), CAAccountingInstance::cleanupTableEntry(), CAAccountingInstance::finishLoginProcess(), CAAccountingInstance::handleChallengeResponse_internal(), CAAccountingInstance::handleJapPacket_internal(), CAAccountingInstance::settlementTransaction(), CAAccountingInstance::unlockLogin(), and CAAccountingInstance::~CAAccountingInstance().

{
  return m_pMutex;
}

UINT32 Hashtable::getSize

(

)

Definition at line 360 of file Hashtable.cpp.

References m_count.

Referenced by CAAccountingInstance::getNrOfUsers().

{
  return m_count;
}

void * Hashtable::getValue

(

void *

key

)

Sucht den zu einem Schlssel (key) passenden Wert (value)

Parameters:

key	der gesuchte Schlssel

Returns:

value der zum Schlssel gehrige Wert

Definition at line 171 of file Hashtable.cpp.

References Entry::e_Value, and getHashEntry().

Referenced by CAAccountingInstance::__commitSettlementToLoginTable(), CAAccountingInstance::cascadeMatchesCC(), CAAccountingInstance::cleanupTableEntry(), CAAccountingInstance::finishLoginProcess(), CAAccountingInstance::handleChallengeResponse_internal(), CAAccountingInstance::handleJapPacket_internal(), CAAccountingInstance::settlementTransaction(), and CAAccountingInstance::unlockLogin().

{   
  struct Entry *e = getHashEntry(key);

  return e ? e->e_Value : NULL;
}

Here is the call graph for this function:

static UINT32 Hashtable::hashUINT32

(

UINT32 *

a_number

)

[inline, static]

Definition at line 60 of file Hashtable.hpp.

    {     
      return *a_number;
    }

static UINT32 Hashtable::hashUINT64

(

UINT64 *

a_number

)

[inline, static]

Definition at line 39 of file Hashtable.hpp.

Referenced by CAAccountingInstance::CAAccountingInstance().

    {
      return ((*a_number) % 4294967295u);
    }

bool Hashtable::isEmpty

(

)

Tests if the hashtable is empty.

Returns:

true if empty; false otherwise

Definition at line 147 of file Hashtable.cpp.

References m_count.

{
  return m_count == 0;
}

void * Hashtable::put	(	void *	key,
		void *	value
	)

Mit dieser Funktion wird ein neuer Eintrag bestehend aus einem Zugriffsschlssel (key) und dessen Wert (value) in den Hashtable eingefgt.

Gibt es diesen Schlssel bereits im Hashtable, wird der alte Eintrag berschrieben.

einen neuen Eintrag in einen Hashtable einfgen

Parameters:

key	der Schlssel
value	der zugehrige Wert

Returns:

the old value if a value has been overwritten, or NULL if the value did not exist before

Definition at line 192 of file Hashtable.cpp.

References Entry::e_Key, Entry::e_Next, Entry::e_Value, m_capacity, m_compareFunc, m_count, m_hashFunc, m_table, m_threshold, and rehash().

Referenced by CAAccountingInstance::CAAccountingInstance(), and CAAccountingInstance::handleChallengeResponse_internal().

{
  //CAMsg::printMsg(LOG_INFO, "Hashtable: Putting key.\n");
  
  if (!key || !value || !m_table)
  {
    return NULL;
  }
  
  struct Entry *oldEntry = NULL;
  struct Entry *newEntry = NULL;
  UINT32 hash = m_hashFunc(key);
  UINT32 index = hash % m_capacity;
  
  m_count++;
  if (m_count >= m_threshold)
  {   
    rehash();
  }
  
  index = hash % m_capacity;
  
  newEntry = new Entry;
  newEntry->e_Key = key;
  newEntry->e_Value = value;
  newEntry->e_Next = NULL;
  
  oldEntry = m_table[index];
  if (!oldEntry)
  {
    m_table[index] = newEntry;
  }
  else
  {
    struct Entry *prevEntry = NULL;
    for(; oldEntry; oldEntry = oldEntry->e_Next)
    {     
      if (m_hashFunc(oldEntry->e_Key) == hash && !m_compareFunc(oldEntry->e_Key,key))
      {
        // found the same entry
        newEntry->e_Next = oldEntry->e_Next;
        break;
      }
      prevEntry = oldEntry;
    }
    if (prevEntry)
    {
      prevEntry->e_Next = newEntry;
    }
    else
    {
      m_table[index] = newEntry;
    }
  }
  
  return oldEntry;
}

Here is the call graph for this function:

bool Hashtable::rehash

(

)

[protected]

Der Hashtable wird in der Kapazitt verdoppelt und neu aufgebaut.

Returns:

success true, wenn die Kapazitt verdoppelt werden konnte, false, wenn nicht

Definition at line 376 of file Hashtable.cpp.

References Entry::e_Key, Entry::e_Next, m_capacity, m_hashFunc, m_loadFactor, m_modCount, m_table, m_threshold, and CAMsg::printMsg().

Referenced by put().

{
  if (!m_table)
  {
    return false;
  }
  
  CAMsg::printMsg(LOG_INFO, "Hashtable: Rehashing.\n");
  
  UINT32 (*hashCode)(void *) = m_hashFunc;
  struct Entry **oldtable = m_table,**newtable;
  SINT32 oldCapacity = m_capacity;
  UINT32 newCapacity;

  newCapacity = oldCapacity * 2 + 1;
  newtable = new Entry*[newCapacity];
  for (UINT32 i = 0; i < newCapacity; i++)
  {
    newtable[i] = NULL;
  }

  m_modCount++;
  if (m_modCount > 10)
  {
    CAMsg::printMsg(LOG_INFO, "Hashtable: Too many rehash operations! Please adapt hashtable capacity to at least %d.\n", newCapacity);
  }
  
  m_threshold = (UINT32)(newCapacity * m_loadFactor);
  m_table = newtable;
  m_capacity = newCapacity;

  for(SINT32 i = 0; i < oldCapacity; i++)
  {
    struct Entry *nextEntry, *e = NULL;
    UINT32 index;
    
    for (nextEntry = oldtable[i]; nextEntry;)
    {
      e = nextEntry;  
      // save the previous next entry, as it will be deleted later
      nextEntry = nextEntry->e_Next;
            
      index = hashCode(e->e_Key) % newCapacity;
      /* If there has been another entry before, replace it.
       * Delete the previous next entry in the same step.
       */
      e->e_Next = newtable[index]; 
      newtable[index] = e;
    }
  }
  delete oldtable;
  oldtable = NULL;
  
  CAMsg::printMsg(LOG_INFO, "Hashtable: Rehashing complete.\n");
  
  return true;
}

Here is the call graph for this function:

void * Hashtable::remove

(

void *

key

)

entfernt einen Eintrag aus einem Hashtable

Mit dieser Funktion entfernt man den zum Schlssel (key) gehrigen Eintrag aus dem Hashtable.

Parameters:

key	der Schlssel

Returns:

value der zum Schlssel gehrende Wert

Definition at line 261 of file Hashtable.cpp.

References Entry::e_Key, Entry::e_Next, Entry::e_Value, m_capacity, m_compareFunc, m_count, m_hashFunc, and m_table.

Referenced by CAAccountingInstance::cleanupTableEntry(), CAAccountingInstance::handleChallengeResponse_internal(), and CAAccountingInstance::~CAAccountingInstance().

{
  //CAMsg::printMsg(LOG_INFO, "Hashtable: Removing key.\n");
  
  if (!key || !m_table)
  {
    return NULL;
  }
  
  struct Entry *e,*prev;
  UINT32 hash = m_hashFunc(key);
  
  for(e = m_table[hash % m_capacity], prev = NULL; e; e = e->e_Next)
  {     
    if (m_hashFunc(e->e_Key) == hash && !m_compareFunc(e->e_Key,key))
    {
      void *value;

      //m_modCount++;
      if (prev)
      {
        prev->e_Next = e->e_Next;
      }
      else
      {
        m_table[hash % m_capacity] = e->e_Next;
      }
      
      m_count--;
      value = e->e_Value;
      e->e_Value = NULL;
      e->e_Key = NULL;
      e->e_Next = NULL;
      delete e;
      e = NULL;

      return value;
    }
    prev = e;
  }
  
  return NULL;
}

static SINT32 Hashtable::stringCompare	(	UINT8 *	a,
		UINT8 **	b
	)		[inline, static]

Definition at line 34 of file Hashtable.hpp.

Referenced by CAAccountingInstance::CAAccountingInstance().

    {
      return strcmp((char*)a,(char*)b);
    }

static UINT32 Hashtable::stringHash

(

UINT8 *

str

)

[inline, static]

Definition at line 21 of file Hashtable.hpp.

Referenced by CAAccountingInstance::CAAccountingInstance().

    {
      // djb2 algorithm
      
      UINT32 hash = 5381; 
      SINT32 c; 
      while ((c = *str++)) 
      {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ 
      }
      return hash;      
    }

---

Member Data Documentation

SINT32 Hashtable::m_capacity [protected]

Definition at line 86 of file Hashtable.hpp.

Referenced by clear(), getCapacity(), getHashEntry(), Hashtable(), put(), rehash(), remove(), and ~Hashtable().

SINT32(* Hashtable::m_compareFunc)(void *, void *) [protected]

Definition at line 90 of file Hashtable.hpp.

Referenced by getHashEntry(), Hashtable(), put(), remove(), and ~Hashtable().

SINT32 Hashtable::m_count [protected]

Definition at line 86 of file Hashtable.hpp.

Referenced by clear(), getSize(), Hashtable(), isEmpty(), put(), remove(), and ~Hashtable().

UINT32(* Hashtable::m_hashFunc)(void *) [protected]

Definition at line 89 of file Hashtable.hpp.

Referenced by getHashEntry(), Hashtable(), put(), rehash(), remove(), and ~Hashtable().

float Hashtable::m_loadFactor [protected]

Definition at line 87 of file Hashtable.hpp.

Referenced by Hashtable(), rehash(), and ~Hashtable().

SINT32 Hashtable::m_modCount [protected]

Definition at line 86 of file Hashtable.hpp.

Referenced by Hashtable(), rehash(), and ~Hashtable().

CAMutex* Hashtable::m_pMutex [private]

Definition at line 93 of file Hashtable.hpp.

Referenced by getMutex(), Hashtable(), and ~Hashtable().

struct Entry** Hashtable::m_table [protected]

Definition at line 88 of file Hashtable.hpp.

Referenced by clear(), getHashEntry(), Hashtable(), put(), rehash(), remove(), and ~Hashtable().

SINT32 Hashtable::m_threshold [protected]

Definition at line 86 of file Hashtable.hpp.

Referenced by Hashtable(), put(), rehash(), and ~Hashtable().

---

The documentation for this class was generated from the following files:

• Hashtable.hpp
• Hashtable.cpp