//*CMZ : 2.22/07 05/07/99 18.54.36 by Fons Rademakers
//*CMZ : 2.22/01 19/04/99 18.22.33 by Fons Rademakers
//*CMZ : 2.20/00 06/11/98 12.37.08 by Fons Rademakers
//*CMZ : 1.03/09 07/12/97 13.26.16 by Fons Rademakers
//*-- Author : Fons Rademakers 27/09/95
//*KEEP,CopyRight,T=C.
/*************************************************************************
* Copyright(c) 1995-1999, The ROOT System, All rights reserved. *
* Authors: Rene Brun, Fons Rademakers. *
* For list of contributors see $ROOTSYS/AA_CREDITS. *
* *
* Permission to use, copy, modify and distribute this software and its *
* documentation for non-commercial purposes is hereby granted without *
* fee, provided that the above copyright notice appears in all copies *
* and that both the copyright notice and this permission notice appear *
* in the supporting documentation. The authors make no claims about the *
* suitability of this software for any purpose. It is provided "as is" *
* without express or implied warranty. *
*************************************************************************/
//*KEND.
//////////////////////////////////////////////////////////////////////////
// //
// THashTable //
// //
// THashTable implements a hash table to store TObject's. The hash //
// value is calculated using the value returned by the TObject's //
// Hash() function. Each class inheriting from TObject can override //
// Hash() as it sees fit. //
// THashTable does not preserve the insertion order of the objects. //
// If the insertion order is important AND fast retrieval is needed //
// use THashList instead. //
//
/*
*/
//
// //
//////////////////////////////////////////////////////////////////////////
//*KEEP,THashTable.
#include "THashTable.h"
//*KEEP,TObjectTable.
#include "TObjectTable.h"
//*KEEP,TList.
#include "TList.h"
//*KEEP,TMath.
#include "TMath.h"
//*KEEP,TError.
#include "TError.h"
//*KEND.
ClassImp(THashTable)
//______________________________________________________________________________
THashTable::THashTable(Int_t capacity, Int_t rehashlevel)
{
// Create a THashTable object. Capacity is the initial hashtable capacity
// (i.e. number of slots), by default kInitHashTableCapacity = 17, and
// rehashlevel is the value at which a rehash will be triggered. I.e. when
// the average size of the linked lists at a slot becomes longer than
// rehashlevel then the hashtable will be resized and refilled to reduce
// the collision rate to about 1. The higher the collision rate, i.e. the
// longer the linked lists, the longer lookup will take. If rehashlevel=0
// the table will NOT automatically be rehashed. Use Rehash() for manual
// rehashing.
if (capacity < 0) {
Warning("THashTable", "capacity (%d) < 0", capacity);
capacity = TCollection::kInitHashTableCapacity;
} else if (capacity == 0)
capacity = TCollection::kInitHashTableCapacity;
fSize = (Int_t)TMath::NextPrime(TMath::Max(capacity,(int)TCollection::kInitHashTableCapacity));
fCont = new TList* [fSize];
memset(fCont, 0, fSize*sizeof(TList*));
fEntries = 0;
fUsedSlots = 0;
if (rehashlevel < 2) rehashlevel = 0;
fRehashLevel = rehashlevel;
}
//______________________________________________________________________________
THashTable::~THashTable()
{
// Delete a hashtable. All objects will be removed from the table before the
// table will be deleted.
if (fCont) Clear();
delete [] fCont;
fCont = 0;
fSize = 0;
}
//______________________________________________________________________________
void THashTable::Add(TObject *obj)
{
// Add object to the hash table. Its position in the table will be
// determined by the value returned by its Hash() function.
if (IsArgNull("Add", obj)) return;
Int_t slot = GetHashValue(obj);
if (!fCont[slot]) {
fCont[slot] = new TList;
fUsedSlots++;
}
fCont[slot]->Add(obj);
fEntries++;
if (fRehashLevel && AverageCollisions() > fRehashLevel)
Rehash(fEntries);
}
//______________________________________________________________________________
void THashTable::Clear(Option_t *option)
{
// Remove all objects from the table. Does not delete the objects.
for (int i = 0; i < fSize; i++) {
// option "nodelete" is passed when Clear is called from
// THashList::Clear() or THashList::Delete().
if (fCont[i]) fCont[i]->Clear(option);
SafeDelete(fCont[i]);
}
fEntries = 0;
fUsedSlots = 0;
}
//______________________________________________________________________________
Int_t THashTable::Collisions(const char *name) const
{
// Returns the number of collisions for an object with a certain name
// (i.e. number of objects in same slot in the hash table, i.e. length
// of linked list).
Int_t slot = GetHashValue(name);
if (fCont[slot]) return fCont[slot]->GetSize();
return 0;
}
//______________________________________________________________________________
Int_t THashTable::Collisions(TObject *obj) const
{
// Returns the number of collisions for an object (i.e. number of objects
// in same slot in the hash table, i.e. length of linked list).
if (IsArgNull("Collisions", obj)) return 0;
Int_t slot = GetHashValue(obj);
if (fCont[slot]) return fCont[slot]->GetSize();
return 0;
}
//______________________________________________________________________________
void THashTable::Delete(Option_t *)
{
// Remove all objects from the table AND delete all heap based objects.
for (int i = 0; i < fSize; i++)
if (fCont[i]) {
fCont[i]->Delete();
SafeDelete(fCont[i]);
}
Clear();
}
//______________________________________________________________________________
TObject *THashTable::FindObject(const Text_t *name) const
{
// Find object using its name. Uses the hash value returned by the
// TString::Hash() after converting name to a TString.
Int_t slot = GetHashValue(name);
if (fCont[slot]) return fCont[slot]->FindObject(name);
return 0;
}
//______________________________________________________________________________
TObject *THashTable::FindObject(TObject *obj) const
{
// Find object using its hash value (returned by its Hash() member).
if (IsArgNull("FindObject", obj)) return 0;
Int_t slot = GetHashValue(obj);
if (fCont[slot]) return fCont[slot]->FindObject(obj);
return 0;
}
//______________________________________________________________________________
TIterator *THashTable::MakeIterator(Bool_t dir) const
{
// Returns a hash table iterator.
return new THashTableIter(this, dir);
}
//______________________________________________________________________________
void THashTable::Rehash(Int_t newCapacity, Bool_t checkObjValidity)
{
// Rehash the hashtable. If the collision rate becomes too high (i.e.
// the average size of the linked lists become too long) then lookup
// efficiency decreases since relatively long lists have to be searched
// every time. To improve performance rehash the hashtable. This resizes
// the table to newCapacity slots and refills the table. Use
// AverageCollisions() to check if you need to rehash. Set checkObjValidity
// to kFALSE if you know that all objects in the table are still valid
// (i.e. have not been deleted from the system in the meanwhile).
THashTable *ht = new THashTable(newCapacity);
TIter next(this);
TObject *obj;
if (checkObjValidity && TObject::GetObjectStat() && gObjectTable) {
while ((obj = next()))
if (gObjectTable->PtrIsValid(obj)) ht->Add(obj);
} else {
while ((obj = next()))
ht->Add(obj);
}
Clear();
delete [] fCont;
fCont = ht->fCont;
ht->fCont = 0;
fParent = ht->fParent; // TCollection part
fSize = ht->fSize; // idem
fEntries = ht->fEntries;
fUsedSlots = ht->fUsedSlots;
// this should not happen, but it will prevent an endless loop
// in case of a very bad hash function
if (fRehashLevel && AverageCollisions() > fRehashLevel)
fRehashLevel = (int)AverageCollisions() + 1;
delete ht;
}
//______________________________________________________________________________
TObject *THashTable::Remove(TObject *obj)
{
// Remove object from the hashtable.
Int_t slot = GetHashValue(obj);
if (fCont[slot]) {
TObject *ob = fCont[slot]->Remove(obj);
if (ob) {
fEntries--;
if (fCont[slot]->GetSize() == 0) {
SafeDelete(fCont[slot]);
fUsedSlots--;
}
return ob;
}
}
return 0;
}
//////////////////////////////////////////////////////////////////////////
// //
// THashTableIter //
// //
// Iterator of hash table. //
// //
//////////////////////////////////////////////////////////////////////////
ClassImp(THashTableIter)
//______________________________________________________________________________
THashTableIter::THashTableIter(const THashTable *ht, Bool_t dir)
{
// Create a hashtable iterator. By default the iteration direction
// is kIterForward. To go backward use kIterBackward.
fTable = ht;
fDirection = dir;
fListCursor = 0;
Reset();
}
//______________________________________________________________________________
THashTableIter::THashTableIter(const THashTableIter &iter)
{
// Copy ctor.
fTable = iter.fTable;
fDirection = iter.fDirection;
fCursor = iter.fCursor;
if (iter.fListCursor) {
fListCursor = (TListIter *)iter.fListCursor->GetCollection()->MakeIterator();
fListCursor->operator=(*iter.fListCursor);
}
}
//______________________________________________________________________________
TIterator &THashTableIter::operator=(const TIterator &rhs)
{
// Overridden assignment operator.
if (this != &rhs && rhs.IsA() == THashTableIter::Class()) {
const THashTableIter &rhs1 = (const THashTableIter &)rhs;
fTable = rhs1.fTable;
fDirection = rhs1.fDirection;
fCursor = rhs1.fCursor;
if (rhs1.fListCursor) {
fListCursor = (TListIter *)rhs1.fListCursor->GetCollection()->MakeIterator();
fListCursor->operator=(*rhs1.fListCursor);
}
}
return *this;
}
//______________________________________________________________________________
THashTableIter &THashTableIter::operator=(const THashTableIter &rhs)
{
// Overloaded assignment operator.
if (this != &rhs) {
fTable = rhs.fTable;
fDirection = rhs.fDirection;
fCursor = rhs.fCursor;
if (rhs.fListCursor) {
fListCursor = (TListIter *)rhs.fListCursor->GetCollection()->MakeIterator();
fListCursor->operator=(*rhs.fListCursor);
}
}
return *this;
}
//______________________________________________________________________________
THashTableIter::~THashTableIter()
{
// Delete hashtable iterator.
delete fListCursor;
}
//______________________________________________________________________________
TObject *THashTableIter::Next()
{
// Return next object in hashtable. Returns 0 when no more objects in table.
if (!fListCursor) {
int slot = NextSlot();
if (slot == -1) return 0;
fListCursor = new TListIter(fTable->fCont[slot], fDirection);
}
TObject *obj = fListCursor->Next();
if (!obj) {
SafeDelete(fListCursor);
return Next();
}
return obj;
}
//______________________________________________________________________________
Int_t THashTableIter::NextSlot()
{
// Returns index of next slot in table containing list to be iterated.
if (fDirection == kIterForward) {
for ( ; fCursor < fTable->Capacity() && fTable->fCont[fCursor] == 0;
fCursor++) { }
if (fCursor < fTable->Capacity())
return fCursor++;
} else {
for ( ; fCursor >= 0 && fTable->fCont[fCursor] == 0;
fCursor--) { }
if (fCursor >= 0)
return fCursor--;
}
return -1;
}
//______________________________________________________________________________
void THashTableIter::Reset()
{
// Reset the hashtable iterator. Either to beginning or end, depending on
// the initial iteration direction.
if (fDirection == kIterForward)
fCursor = 0;
else
fCursor = fTable->Capacity() - 1;
SafeDelete(fListCursor);
}
ROOT page - Class index - Top of the page
This page has been automatically generated. If you have any comments or suggestions about the page layout send a mail to ROOT support, or contact the developers with any questions or problems regarding ROOT.