RooHashTable.cxx

Go to the documentation of this file.
00001 /*****************************************************************************
00002  * Project: RooFit                                                           *
00003  * Package: RooFitCore                                                       *
00004  * @(#)root/roofitcore:$Id: RooHashTable.cxx 24278 2008-06-15 15:21:16Z wouter $
00005  * Authors:                                                                  *
00006  *   WV, Wouter Verkerke, UC Santa Barbara, verkerke@slac.stanford.edu       *
00007  *   DK, David Kirkby,    UC Irvine,         dkirkby@uci.edu                 *
00008  *                                                                           *
00009  * Copyright (c) 2000-2005, Regents of the University of California          *
00010  *                          and Stanford University. All rights reserved.    *
00011  *                                                                           *
00012  * Redistribution and use in source and binary forms,                        *
00013  * with or without modification, are permitted according to the terms        *
00014  * listed in LICENSE (http://roofit.sourceforge.net/license.txt)             *
00015  *****************************************************************************/
00016 
00017 #include "RooFit.h"
00018 
00019 #include "TMath.h"
00020 #include "TMath.h"
00021 #include "TCollection.h"
00022 #include "RooHashTable.h"
00023 #include "RooLinkedList.h"
00024 #include "RooAbsArg.h"
00025 #include "RooSetPair.h"
00026 
00027 ClassImp(RooHashTable)
00028 ;
00029 
00030 //////////////////////////////////////////////////////////////////////////////
00031 //
00032 // BEGIN_HTML
00033 // RooHashTable implements a hash table for TObjects. The hashing can be
00034 // done on the object addresses, object names, or using the objects
00035 // internal hash method. This is a utility class for RooLinkedList
00036 // that uses RooHashTable to speed up direct access to large collections.
00037 // END_HTML
00038 //
00039 
00040 //_____________________________________________________________________________
00041 RooHashTable::RooHashTable(Int_t capacity, HashMethod hashMethod) :
00042   _hashMethod(hashMethod)
00043 {
00044   // Construct a hash table with given capacity and hash method
00045 
00046   if (capacity <= 0) {
00047     capacity = TCollection::kInitHashTableCapacity;
00048   }  
00049   _size = (Int_t)TMath::NextPrime(TMath::Max(capacity,(int)TCollection::kInitHashTableCapacity));
00050   _arr  = new RooLinkedList* [_size] ;
00051   memset(_arr, 0, _size*sizeof(RooLinkedList*));
00052 
00053   _usedSlots = 0 ;
00054   _entries   = 0 ;
00055 }
00056 
00057 
00058 
00059 //_____________________________________________________________________________
00060 RooHashTable::RooHashTable(const RooHashTable& other) :
00061   TObject(other),
00062   _hashMethod(other._hashMethod),
00063   _usedSlots(other._usedSlots), 
00064   _entries(other._entries), 
00065   _size(other._size)
00066 {
00067   // Copy constructor
00068 
00069   _arr  = new RooLinkedList* [_size] ;
00070   memset(_arr, 0, _size*sizeof(RooLinkedList*));  
00071   Int_t i ;
00072   for (i=0 ; i<_size ; i++) {
00073     if (other._arr[i]) {
00074       _arr[i] = new RooLinkedList(*other._arr[i]) ;
00075     }
00076   }
00077 }
00078 
00079 
00080 
00081 //_____________________________________________________________________________
00082 void RooHashTable::add(TObject* arg, TObject* hashArg) 
00083 {
00084   // Add given object to table. If hashArg is given, hash will be calculation
00085   // on that rather than on 'arg'
00086 
00087   Int_t slot = hash(hashArg?hashArg:arg) % _size ;
00088   if (!_arr[slot]) {
00089     _arr[slot] = new RooLinkedList(0) ;
00090     _usedSlots++ ;
00091    }
00092    _arr[slot]->Add(arg);
00093    _entries++;
00094 }
00095 
00096 
00097 
00098 //_____________________________________________________________________________
00099 Bool_t RooHashTable::remove(TObject* arg, TObject* hashArg)
00100 {
00101   // Remove given object from table. If hashArg is given, hash will be calculation
00102   // on that rather than on 'arg'
00103 
00104   Int_t slot = hash(hashArg?hashArg:arg) % _size ;
00105   if (_arr[slot]) {
00106     if (_arr[slot]->Remove(arg)) {
00107       _entries-- ;
00108       if (_arr[slot]->GetSize()==0) {
00109         delete _arr[slot] ;
00110         _arr[slot] = 0 ;
00111         _usedSlots-- ;
00112       }
00113       return kTRUE ;
00114     }
00115   }
00116   return kFALSE ;
00117 }
00118 
00119 
00120 
00121 //_____________________________________________________________________________
00122 Double_t RooHashTable::avgCollisions() const 
00123 {
00124   // Calculate the average number of collisions (table slots with >1 filled entry)
00125   
00126   Int_t i,h[20] ;
00127   for (i=0 ;  i<20 ; i++) h[i]=0 ; 
00128 
00129   for (i=0 ; i<_size ; i++) {
00130     if (_arr[i]) {
00131       Int_t count = _arr[i]->GetSize() ;
00132       if (count<20) {
00133         h[count]++ ;
00134       } else {
00135         h[19]++ ;
00136       }
00137     } else {
00138       h[0]++ ;
00139     }
00140   }
00141 
00142   return 0 ;
00143 }
00144 
00145 
00146 
00147 //_____________________________________________________________________________
00148 Bool_t RooHashTable::replace(const TObject* oldArg, const TObject* newArg, const TObject* oldHashArg) 
00149 {
00150   // Replace oldArg with newArg in the table. If oldHashArg is given, use that to calculate
00151   // the hash associated with oldArg
00152 
00153   Int_t slot = hash(oldHashArg?oldHashArg:oldArg) % _size ;
00154   if (_arr[slot]) {
00155     return _arr[slot]->Replace(oldArg,newArg) ;
00156   }
00157   return kFALSE ;
00158 }
00159 
00160 
00161 
00162 //_____________________________________________________________________________
00163 TObject* RooHashTable::find(const char* name) const 
00164 {
00165   // Return the object with given name from the table.
00166 
00167   if (_hashMethod != Name) assert(0) ;
00168 
00169   Int_t slot = TMath::Hash(name) % _size ;
00170   if (_arr[slot]) return _arr[slot]->find(name) ;
00171   return 0;  
00172 }
00173 
00174 
00175 
00176 //_____________________________________________________________________________
00177 TObject* RooHashTable::find(const TObject* hashArg) const 
00178 {
00179   // Return object with the given pointer from the table
00180 
00181   if (_hashMethod != Pointer) assert(0) ;
00182 
00183   Int_t slot = hash(hashArg) % _size ;
00184   if (_arr[slot]) return _arr[slot]->FindObject(hashArg) ;
00185   return 0;  
00186 }
00187 
00188 
00189 
00190 //_____________________________________________________________________________
00191 RooLinkedListElem* RooHashTable::findLinkTo(const TObject* hashArg) const 
00192 {
00193   // Return RooLinkedList element link to object 'hashArg'
00194 
00195   if (_hashMethod != Pointer) assert(0) ;
00196 
00197   Int_t slot = hash(hashArg) % _size ;
00198   if (_arr[slot]) {
00199     Int_t i ; 
00200     for (i=0 ; i<_arr[slot]->GetSize() ; i++) {
00201       RooLinkedListElem* elem = (RooLinkedListElem*)_arr[slot]->At(i) ;
00202       if (elem->_arg == hashArg) return elem ;
00203     }
00204   }
00205   return 0;  
00206 }
00207 
00208 
00209 
00210 //_____________________________________________________________________________
00211 RooSetPair* RooHashTable::findSetPair(const RooArgSet* set1, const RooArgSet* set2) const 
00212 {  
00213   // Return RooSetPair with given pointers in table
00214 
00215   if (_hashMethod != Intrinsic) assert(0) ;
00216 
00217   Int_t slot = RooSetPair(set1,set2).Hash() % _size ;
00218   if (_arr[slot]) {
00219     Int_t i ; 
00220     for (i=0 ; i<_arr[slot]->GetSize() ; i++) {
00221       RooSetPair* pair = (RooSetPair*)_arr[slot]->At(i) ;
00222       if (pair->_set1==set1 && pair->_set2==set2) {
00223         return pair ;
00224       }
00225     }
00226   }
00227 
00228   return 0 ;
00229 }
00230 
00231 
00232 
00233 
00234 //_____________________________________________________________________________
00235 RooHashTable::~RooHashTable() 
00236 {  
00237   // Destructor
00238 
00239   Int_t i ;
00240   for (i=0 ; i<_size ; i++) {
00241     if (_arr[i]) delete _arr[i] ;  
00242   }
00243   delete[] _arr ;
00244 }

Generated on Tue Jul 5 15:06:41 2011 for ROOT_528-00b_version by  doxygen 1.5.1