THashTable.cxx

Go to the documentation of this file.
00001 // @(#)root/cont:$Id: THashTable.cxx 31714 2009-12-09 10:01:32Z rdm $
00002 // Author: Fons Rademakers   27/09/95
00003 
00004 /*************************************************************************
00005  * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers.               *
00006  * All rights reserved.                                                  *
00007  *                                                                       *
00008  * For the licensing terms see $ROOTSYS/LICENSE.                         *
00009  * For the list of contributors see $ROOTSYS/README/CREDITS.             *
00010  *************************************************************************/
00011 
00012 //////////////////////////////////////////////////////////////////////////
00013 //                                                                      //
00014 // THashTable                                                           //
00015 //                                                                      //
00016 // THashTable implements a hash table to store TObject's. The hash      //
00017 // value is calculated using the value returned by the TObject's        //
00018 // Hash() function. Each class inheriting from TObject can override     //
00019 // Hash() as it sees fit.                                               //
00020 // THashTable does not preserve the insertion order of the objects.     //
00021 // If the insertion order is important AND fast retrieval is needed     //
00022 // use THashList instead.                                               //
00023 //Begin_Html
00024 /*
00025 <img src=gif/thashtable.gif>
00026 */
00027 //End_Html
00028 //                                                                      //
00029 //////////////////////////////////////////////////////////////////////////
00030 
00031 #include "THashTable.h"
00032 #include "TObjectTable.h"
00033 #include "TList.h"
00034 #include "TError.h"
00035 
00036 
00037 ClassImp(THashTable)
00038 
00039 //______________________________________________________________________________
00040 THashTable::THashTable(Int_t capacity, Int_t rehashlevel)
00041 {
00042    // Create a THashTable object. Capacity is the initial hashtable capacity
00043    // (i.e. number of slots), by default kInitHashTableCapacity = 17, and
00044    // rehashlevel is the value at which a rehash will be triggered. I.e. when
00045    // the average size of the linked lists at a slot becomes longer than
00046    // rehashlevel then the hashtable will be resized and refilled to reduce
00047    // the collision rate to about 1. The higher the collision rate, i.e. the
00048    // longer the linked lists, the longer lookup will take. If rehashlevel=0
00049    // the table will NOT automatically be rehashed. Use Rehash() for manual
00050    // rehashing.
00051 
00052    if (capacity < 0) {
00053       Warning("THashTable", "capacity (%d) < 0", capacity);
00054       capacity = TCollection::kInitHashTableCapacity;
00055    } else if (capacity == 0)
00056       capacity = TCollection::kInitHashTableCapacity;
00057 
00058    fSize = (Int_t)TMath::NextPrime(TMath::Max(capacity,(int)TCollection::kInitHashTableCapacity));
00059    fCont = new TList* [fSize];
00060    memset(fCont, 0, fSize*sizeof(TList*));
00061 
00062    fEntries   = 0;
00063    fUsedSlots = 0;
00064    if (rehashlevel < 2) rehashlevel = 0;
00065    fRehashLevel = rehashlevel;
00066 }
00067 
00068 //______________________________________________________________________________
00069 THashTable::~THashTable()
00070 {
00071    // Delete a hashtable. Objects are not deleted unless the THashTable is the
00072    // owner (set via SetOwner()).
00073 
00074    if (fCont) Clear();
00075    delete [] fCont;
00076    fCont = 0;
00077    fSize = 0;
00078 }
00079 
00080 //______________________________________________________________________________
00081 void THashTable::Add(TObject *obj)
00082 {
00083    // Add object to the hash table. Its position in the table will be
00084    // determined by the value returned by its Hash() function.
00085 
00086    if (IsArgNull("Add", obj)) return;
00087 
00088    Int_t slot = GetHashValue(obj);
00089    if (!fCont[slot]) {
00090       fCont[slot] = new TList;
00091       fUsedSlots++;
00092    }
00093    fCont[slot]->Add(obj);
00094    fEntries++;
00095 
00096    if (fRehashLevel && AverageCollisions() > fRehashLevel)
00097       Rehash(fEntries);
00098 }
00099 
00100 //______________________________________________________________________________
00101 void THashTable::AddAll(const TCollection *col)
00102 {
00103    // Add all objects from collection col to this collection.
00104    // Implemented for more efficient rehashing.
00105 
00106    // Hashing after AddAll can be much more expensive than
00107    // hashing before, as we need to add more elements.
00108    // We assume an ideal hash, i.e. fUsedSlots==fSize.
00109    Int_t sumEntries=fEntries+col->GetEntries();
00110    Bool_t rehashBefore=fRehashLevel && (sumEntries > fSize*fRehashLevel);
00111    if (rehashBefore)
00112       Rehash(sumEntries);
00113 
00114    // prevent Add from Rehashing
00115    Int_t saveRehashLevel=fRehashLevel;
00116    fRehashLevel=0;
00117 
00118    TCollection::AddAll(col);
00119 
00120    fRehashLevel=saveRehashLevel;
00121    // If we didn't Rehash before, we might have to do it
00122    // now, due to a non-perfect hash function.
00123    if (!rehashBefore && fRehashLevel && AverageCollisions() > fRehashLevel)
00124       Rehash(fEntries);
00125 }
00126 
00127 //______________________________________________________________________________
00128 void THashTable::Clear(Option_t *option)
00129 {
00130    // Remove all objects from the table. Does not delete the objects
00131    // unless the THashTable is the owner (set via SetOwner()).
00132 
00133    for (int i = 0; i < fSize; i++) {
00134       // option "nodelete" is passed when Clear is called from
00135       // THashList::Clear() or THashList::Delete() or Rehash().
00136       if (fCont[i]) {
00137          if (IsOwner())
00138             fCont[i]->SetOwner();
00139          fCont[i]->Clear(option);
00140       }
00141       SafeDelete(fCont[i]);
00142    }
00143 
00144    fEntries   = 0;
00145    fUsedSlots = 0;
00146 }
00147 
00148 //______________________________________________________________________________
00149 Int_t THashTable::Collisions(const char *name) const
00150 {
00151    // Returns the number of collisions for an object with a certain name
00152    // (i.e. number of objects in same slot in the hash table, i.e. length
00153    // of linked list).
00154 
00155    Int_t slot = GetHashValue(name);
00156    if (fCont[slot]) return fCont[slot]->GetSize();
00157    return 0;
00158 }
00159 
00160 //______________________________________________________________________________
00161 Int_t THashTable::Collisions(TObject *obj) const
00162 {
00163    // Returns the number of collisions for an object (i.e. number of objects
00164    // in same slot in the hash table, i.e. length of linked list).
00165 
00166    if (IsArgNull("Collisions", obj)) return 0;
00167 
00168    Int_t slot = GetHashValue(obj);
00169    if (fCont[slot]) return fCont[slot]->GetSize();
00170    return 0;
00171 }
00172 
00173 //______________________________________________________________________________
00174 void THashTable::Delete(Option_t *)
00175 {
00176    // Remove all objects from the table AND delete all heap based objects.
00177 
00178    for (int i = 0; i < fSize; i++)
00179       if (fCont[i]) {
00180          fCont[i]->Delete();
00181          SafeDelete(fCont[i]);
00182       }
00183 
00184    fEntries   = 0;
00185    fUsedSlots = 0;
00186 }
00187 
00188 //______________________________________________________________________________
00189 TObject *THashTable::FindObject(const char *name) const
00190 {
00191    // Find object using its name. Uses the hash value returned by the
00192    // TString::Hash() after converting name to a TString.
00193 
00194    Int_t slot = GetHashValue(name);
00195    if (fCont[slot]) return fCont[slot]->FindObject(name);
00196    return 0;
00197 }
00198 
00199 //______________________________________________________________________________
00200 TObject *THashTable::FindObject(const TObject *obj) const
00201 {
00202    // Find object using its hash value (returned by its Hash() member).
00203 
00204    if (IsArgNull("FindObject", obj)) return 0;
00205 
00206    Int_t slot = GetHashValue(obj);
00207    if (fCont[slot]) return fCont[slot]->FindObject(obj);
00208    return 0;
00209 }
00210 
00211 //______________________________________________________________________________
00212 TList *THashTable::GetListForObject(const char *name) const
00213 {
00214    // Return the TList corresponding to object's name based hash value.
00215    // One can iterate this list "manually" to find, e.g. objects with
00216    // the same name.
00217 
00218    return fCont[GetHashValue(name)];
00219 }
00220 
00221 //______________________________________________________________________________
00222 TList *THashTable::GetListForObject(const TObject *obj) const
00223 {
00224    // Return the TList corresponding to object's hash value.
00225    // One can iterate this list "manually" to find, e.g. identical
00226    // objects.
00227 
00228    if (IsArgNull("GetListForObject", obj)) return 0;
00229    return fCont[GetHashValue(obj)];
00230 }
00231 
00232 //______________________________________________________________________________
00233 TObject **THashTable::GetObjectRef(const TObject *obj) const
00234 {
00235    // Return address of pointer to obj
00236 
00237    if (IsArgNull("GetObjectRef", obj)) return 0;
00238 
00239    Int_t slot = GetHashValue(obj);
00240    if (fCont[slot]) return fCont[slot]->GetObjectRef(obj);
00241    return 0;
00242 }
00243 
00244 //______________________________________________________________________________
00245 TIterator *THashTable::MakeIterator(Bool_t dir) const
00246 {
00247    // Returns a hash table iterator.
00248 
00249    return new THashTableIter(this, dir);
00250 }
00251 
00252 //______________________________________________________________________________
00253 void THashTable::Rehash(Int_t newCapacity, Bool_t checkObjValidity)
00254 {
00255    // Rehash the hashtable. If the collision rate becomes too high (i.e.
00256    // the average size of the linked lists become too long) then lookup
00257    // efficiency decreases since relatively long lists have to be searched
00258    // every time. To improve performance rehash the hashtable. This resizes
00259    // the table to newCapacity slots and refills the table. Use
00260    // AverageCollisions() to check if you need to rehash. Set checkObjValidity
00261    // to kFALSE if you know that all objects in the table are still valid
00262    // (i.e. have not been deleted from the system in the meanwhile).
00263 
00264    THashTable *ht = new THashTable(newCapacity);
00265 
00266    TIter next(this);
00267    TObject *obj;
00268 
00269    if (checkObjValidity && TObject::GetObjectStat() && gObjectTable) {
00270       while ((obj = next()))
00271          if (gObjectTable->PtrIsValid(obj)) ht->Add(obj);
00272    } else {
00273       while ((obj = next()))
00274          ht->Add(obj);
00275    }
00276 
00277    Clear("nodelete");
00278    delete [] fCont;
00279    fCont = ht->fCont;
00280    ht->fCont = 0;
00281 
00282    fSize      = ht->fSize;     // idem
00283    fEntries   = ht->fEntries;
00284    fUsedSlots = ht->fUsedSlots;
00285 
00286    // this should not happen, but it will prevent an endless loop
00287    // in case of a very bad hash function
00288    if (fRehashLevel && AverageCollisions() > fRehashLevel)
00289       fRehashLevel = (int)AverageCollisions() + 1;
00290 
00291    delete ht;
00292 }
00293 
00294 //______________________________________________________________________________
00295 TObject *THashTable::Remove(TObject *obj)
00296 {
00297    // Remove object from the hashtable.
00298 
00299    Int_t slot = GetHashValue(obj);
00300    if (fCont[slot]) {
00301       TObject *ob = fCont[slot]->Remove(obj);
00302       if (ob) {
00303          fEntries--;
00304          if (fCont[slot]->GetSize() == 0) {
00305             SafeDelete(fCont[slot]);
00306             fUsedSlots--;
00307          }
00308          return ob;
00309       }
00310    }
00311    return 0;
00312 }
00313 
00314 //______________________________________________________________________________
00315 TObject *THashTable::RemoveSlow(TObject *obj)
00316 {
00317    // Remove object from the hashtable without using the hash value.
00318 
00319    for (int i = 0; i < fSize; i++) {
00320       if (fCont[i]) {
00321          TObject *ob = fCont[i]->Remove(obj);
00322          if (ob) {
00323             fEntries--;
00324             if (fCont[i]->GetSize() == 0) {
00325                SafeDelete(fCont[i]);
00326                fUsedSlots--;
00327             }
00328             return ob;
00329          }
00330       }
00331    }
00332    return 0;
00333 }
00334 
00335 
00336 //////////////////////////////////////////////////////////////////////////
00337 //                                                                      //
00338 // THashTableIter                                                       //
00339 //                                                                      //
00340 // Iterator of hash table.                                              //
00341 //                                                                      //
00342 //////////////////////////////////////////////////////////////////////////
00343 
00344 ClassImp(THashTableIter)
00345 
00346 //______________________________________________________________________________
00347 THashTableIter::THashTableIter(const THashTable *ht, Bool_t dir)
00348 {
00349    // Create a hashtable iterator. By default the iteration direction
00350    // is kIterForward. To go backward use kIterBackward.
00351 
00352    fTable      = ht;
00353    fDirection  = dir;
00354    fListCursor = 0;
00355    Reset();
00356 }
00357 
00358 //______________________________________________________________________________
00359 THashTableIter::THashTableIter(const THashTableIter &iter) : TIterator(iter)
00360 {
00361    // Copy ctor.
00362 
00363    fTable      = iter.fTable;
00364    fDirection  = iter.fDirection;
00365    fCursor     = iter.fCursor;
00366    fListCursor = 0;
00367    if (iter.fListCursor) {
00368       fListCursor = (TListIter *)iter.fListCursor->GetCollection()->MakeIterator();
00369       fListCursor->operator=(*iter.fListCursor);
00370    }
00371 }
00372 
00373 //______________________________________________________________________________
00374 TIterator &THashTableIter::operator=(const TIterator &rhs)
00375 {
00376    // Overridden assignment operator.
00377 
00378    if (this != &rhs && rhs.IsA() == THashTableIter::Class()) {
00379       const THashTableIter &rhs1 = (const THashTableIter &)rhs;
00380       fTable     = rhs1.fTable;
00381       fDirection = rhs1.fDirection;
00382       fCursor    = rhs1.fCursor;
00383       if (rhs1.fListCursor) {
00384          fListCursor = (TListIter *)rhs1.fListCursor->GetCollection()->MakeIterator();
00385          fListCursor->operator=(*rhs1.fListCursor);
00386       }
00387    }
00388    return *this;
00389 }
00390 
00391 //______________________________________________________________________________
00392 THashTableIter &THashTableIter::operator=(const THashTableIter &rhs)
00393 {
00394    // Overloaded assignment operator.
00395 
00396    if (this != &rhs) {
00397       fTable     = rhs.fTable;
00398       fDirection = rhs.fDirection;
00399       fCursor    = rhs.fCursor;
00400       if (rhs.fListCursor) {
00401          fListCursor = (TListIter *)rhs.fListCursor->GetCollection()->MakeIterator();
00402          fListCursor->operator=(*rhs.fListCursor);
00403       }
00404    }
00405    return *this;
00406 }
00407 
00408 //______________________________________________________________________________
00409 THashTableIter::~THashTableIter()
00410 {
00411    // Delete hashtable iterator.
00412 
00413    delete fListCursor;
00414 }
00415 
00416 //______________________________________________________________________________
00417 TObject *THashTableIter::Next()
00418 {
00419    // Return next object in hashtable. Returns 0 when no more objects in table.
00420 
00421    while (kTRUE) {
00422       if (!fListCursor) {
00423          int slot = NextSlot();
00424          if (slot == -1) return 0;
00425          fListCursor = new TListIter(fTable->fCont[slot], fDirection);
00426       }
00427 
00428       TObject *obj = fListCursor->Next();
00429       if (obj) return obj;
00430 
00431       SafeDelete(fListCursor);
00432    }
00433 }
00434 
00435 //______________________________________________________________________________
00436 Int_t THashTableIter::NextSlot()
00437 {
00438    // Returns index of next slot in table containing list to be iterated.
00439 
00440    if (fDirection == kIterForward) {
00441       for ( ; fCursor < fTable->Capacity() && fTable->fCont[fCursor] == 0;
00442               fCursor++) { }
00443 
00444       if (fCursor < fTable->Capacity())
00445          return fCursor++;
00446 
00447    } else {
00448       for ( ; fCursor >= 0 && fTable->fCont[fCursor] == 0;
00449               fCursor--) { }
00450 
00451       if (fCursor >= 0)
00452          return fCursor--;
00453    }
00454    return -1;
00455 }
00456 
00457 //______________________________________________________________________________
00458 void THashTableIter::Reset()
00459 {
00460    // Reset the hashtable iterator. Either to beginning or end, depending on
00461    // the initial iteration direction.
00462 
00463    if (fDirection == kIterForward)
00464       fCursor = 0;
00465    else
00466       fCursor = fTable->Capacity() - 1;
00467    SafeDelete(fListCursor);
00468 }
00469 
00470 //______________________________________________________________________________
00471 bool THashTableIter::operator!=(const TIterator &aIter) const
00472 {
00473    // This operator compares two TIterator objects.
00474 
00475    if (nullptr == (&aIter))
00476       return fListCursor;
00477 
00478    if (aIter.IsA() == THashTableIter::Class()) {
00479       const THashTableIter &iter(dynamic_cast<const THashTableIter &>(aIter));
00480       return (fListCursor != iter.fListCursor);
00481    }
00482    return false; // for base class we don't implement a comparison
00483 }
00484 
00485 //______________________________________________________________________________
00486 bool THashTableIter::operator!=(const THashTableIter &aIter) const
00487 {
00488    // This operator compares two THashTableIter objects.
00489 
00490    if (nullptr == (&aIter))
00491       return fListCursor;
00492 
00493    return (fListCursor != aIter.fListCursor);
00494 }
00495 
00496 //______________________________________________________________________________
00497 TObject *THashTableIter::operator*() const
00498 {
00499    // Return pointer to current object or nullptr.
00500 
00501    return (fListCursor ? fListCursor->operator*() : nullptr);
00502 }

Generated on Tue Jul 5 14:11:37 2011 for ROOT_528-00b_version by  doxygen 1.5.1