00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
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
00043
00044
00045
00046
00047
00048
00049
00050
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
00072
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
00084
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
00104
00105
00106
00107
00108
00109 Int_t sumEntries=fEntries+col->GetEntries();
00110 Bool_t rehashBefore=fRehashLevel && (sumEntries > fSize*fRehashLevel);
00111 if (rehashBefore)
00112 Rehash(sumEntries);
00113
00114
00115 Int_t saveRehashLevel=fRehashLevel;
00116 fRehashLevel=0;
00117
00118 TCollection::AddAll(col);
00119
00120 fRehashLevel=saveRehashLevel;
00121
00122
00123 if (!rehashBefore && fRehashLevel && AverageCollisions() > fRehashLevel)
00124 Rehash(fEntries);
00125 }
00126
00127
00128 void THashTable::Clear(Option_t *option)
00129 {
00130
00131
00132
00133 for (int i = 0; i < fSize; i++) {
00134
00135
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
00152
00153
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
00164
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
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
00192
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
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
00215
00216
00217
00218 return fCont[GetHashValue(name)];
00219 }
00220
00221
00222 TList *THashTable::GetListForObject(const TObject *obj) const
00223 {
00224
00225
00226
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
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
00248
00249 return new THashTableIter(this, dir);
00250 }
00251
00252
00253 void THashTable::Rehash(Int_t newCapacity, Bool_t checkObjValidity)
00254 {
00255
00256
00257
00258
00259
00260
00261
00262
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;
00283 fEntries = ht->fEntries;
00284 fUsedSlots = ht->fUsedSlots;
00285
00286
00287
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
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
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
00339
00340
00341
00342
00343
00344 ClassImp(THashTableIter)
00345
00346
00347 THashTableIter::THashTableIter(const THashTable *ht, Bool_t dir)
00348 {
00349
00350
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
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
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
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
00412
00413 delete fListCursor;
00414 }
00415
00416
00417 TObject *THashTableIter::Next()
00418 {
00419
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
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
00461
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
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;
00483 }
00484
00485
00486 bool THashTableIter::operator!=(const THashTableIter &aIter) const
00487 {
00488
00489
00490 if (nullptr == (&aIter))
00491 return fListCursor;
00492
00493 return (fListCursor != aIter.fListCursor);
00494 }
00495
00496
00497 TObject *THashTableIter::operator*() const
00498 {
00499
00500
00501 return (fListCursor ? fListCursor->operator*() : nullptr);
00502 }