//*-- Author : Damir Buskulic 20/05/99//////////////////////////////////////////////////////////////////////////// //// VHashTable //// //// Special hash table for quick frame file determination //// Instead of generating a hash value for each stored object, //// this table stores lists of names of frame file descriptors. //// (The name of frame file descriptors is defined by the start time //// of the first frame in the file) //// The hashing is done with respect to the start time of //// the first frame in a file. Global duration represented by //// the database is simply cut into equal portions, each file being //// assigned to one portion. So, after the build of the database, //// each portion contains a list of files for which the first frame //// begins inside the given time portion. //// On retrieval, one asks for information on a given time and gets //// a list of files that may contain the requested time. //// The average collision rate is the average number of files in each //// slot. The optimum average collision rate is decided by the user, it //// may not be 1. This depends on the frame seek time and is experimental//// ////////////////////////////////////////////////////////////////////////////
#include "VHashTable.h"
#include "VFrameMetaDB.h"
ClassImp(VHashTable)
//______________________________________________________________________________VHashTable::VHashTable()
{
mGlobalStartTime = 0;
mGlobalEndTime = 0;
mCapacity = 0;
mFilesHashTable = 0;
mFilesUnique = 0;
mOptimalCollision = 5;
mUsedSlots = 0;
mSize = 0;
mNFiles = 0;
}
//______________________________________________________________________________VHashTable::VHashTable(Int_t capacity, Double_t gstart, Double_t gend, Int_t optcol)
{
// Creates a VHashTable. gstart and gend are the initial values for// the global start and end times.
if (capacity < 0) {
Warning("VHashTable", "capacity (%d) < 0", capacity);
capacity = 10;
} else if (capacity == 0)
capacity = 10;
mCapacity = capacity;
mGlobalStartTime = gstart;
mGlobalEndTime = gend;
mSize = 0;
mNFiles = 0;
mOptimalCollision = optcol;
mUsedSlots = 0;
mFilesHashTable = new TObjArray* [mCapacity];
memset(mFilesHashTable, 0, mCapacity*sizeof(TObjArray*));
mFilesUnique = new TObjArray(mCapacity);
}
//______________________________________________________________________________VHashTable::~VHashTable()
{
// Deletes a VHashTable. All elements contained in it are deletedDelete();
delete [] mFilesHashTable;
SafeDelete(mFilesUnique);
}
//______________________________________________________________________________voidVHashTable::Delete(Option_t*)
{
// Deletes all elements contained in this VHashTable
for (Int_t i=0;i<mCapacity;i++) {
if(mFilesHashTable[i]) {
mFilesHashTable[i]->Delete();
delete mFilesHashTable[i];
mFilesHashTable[i] = 0;
}
}
}
//______________________________________________________________________________voidVHashTable::Add(Double_t filestart, Double_t fileend, Int_t firstindex, Int_t lastindex, Int_t condindex, Int_t firstgroup, Int_t lastgroup)
{
// Inserts a file times in the hash table. If the file spans more than one// slot in the table, it will be inserted in all the slots it spans.Int_t hashstart, hashend, hashval;
VFrFileIndex* frfileind;
TObjArray* strarray;
if (fileend >= mGlobalEndTime) Expand(fileend+1);
if (filestart < mGlobalStartTime) Rehash(mCapacity, filestart-1, mGlobalEndTime);
hashstart = GetHashValue(filestart);
hashend = GetHashValueExclude(fileend);
frfileind = new VFrFileIndex(filestart, fileend, firstindex, lastindex, condindex, firstgroup, lastgroup);
// The file start is inserted in all the slots that are spanned by the file.
for (hashval=hashstart; hashval<=hashend; hashval++) {
// Creates a new TObjArray if empty slot
if (!mFilesHashTable[hashval]) {
strarray = new TObjArray(mOptimalCollision+2);
mFilesHashTable[hashval] = strarray;
mUsedSlots++;
}
mFilesHashTable[hashval]->Add(frfileind);
mSize++;
}
mFilesUnique->Add(frfileind);
mNFiles++;
// Rehashing done if necessary// i.e if average collision rate > mOptimalCollisionFloat_t nav = AverageCollisions();
if (nav > mOptimalCollision+1) {
Int_t newcap = Int_t(mCapacity*(((Float_t)nav)/mOptimalCollision));
Rehash(newcap, mGlobalStartTime, mGlobalEndTime);
}
}
//______________________________________________________________________________TObjArray* VHashTable::GetFilesInfo(Double_t time) const
{
// Returns the info on files potentially containing "time"
if (time < mGlobalStartTime) return 0;
if (time > mGlobalEndTime) return 0;
Int_t hashval = GetHashValue(time);
return mFilesHashTable[hashval];
}
//______________________________________________________________________________TObjArray* VHashTable::GetFilesInfoDirect(Int_t hashval) const
{
// Returns the info on files for hash value hashval
if (hashval < 0) return 0;
if (hashval > mCapacity-1) return 0;
return mFilesHashTable[hashval];
}
//______________________________________________________________________________voidVHashTable::Print(Option_t* opt)
{
// Prints the content of the hash table. May be VERY long in case of// big tables. Mainly for test. Set option to "small" if a reduced// listing is needed. Only the first and last slots will be printedInt_t smallprint = 0;
Int_t endprint = 0;
TString option = opt;
option.ToLower();
if (option.Contains("small")) smallprint=1;
printf("n Hash table contents :n");
printf( " _____________________n\n");
printf(" Global start time : %12.2f, End time : %12.2fn", mGlobalStartTime, mGlobalEndTime);
printf(" Capacity : %d, Used slots : %d, Size : %d, Files : %dn",mCapacity,mUsedSlots,mSize,mNFiles);
printf(" Optimal collision rate : %dn",mOptimalCollision);
printf("n Contents of the table :n\n");
// Determine where to start from to see 3 last non empty slotsInt_t curnonempty=0;
for (endprint=mCapacity-1;endprint>=0;endprint--) {
TObjArray* obj = mFilesHashTable[endprint];
if (obj) curnonempty++;
if (curnonempty>3) break;
}
Int_t curprinted=0;
for (Int_t i=0;i<mCapacity;i++) {
TObjArray* obj;
obj = mFilesHashTable[i];
if (obj) {
for (Int_t j=0;j<obj->Capacity();j++) {
if (obj->At(j)) printf(" slot %d, number %d, object %p, start time %f, end time %f n",
i,j,obj,((VFrFileIndex*)(obj->At(j)))->GetStartTime(),
((VFrFileIndex*)(obj->At(j)))->GetEndTime());
}
curprinted++;
if (curprinted>3 && smallprint) { // prints only a subset of the hash table
curprinted=0;
i = endprint;
printf("nSkipping slots........n\n");
}
}
}
}
//______________________________________________________________________________voidVHashTable::SetGlobalStartTime(Double_t gstart)
{
// Sets the start time of the hash table. Rehash if necessary
if (gstart < mGlobalStartTime) Rehash(mCapacity, gstart, mGlobalEndTime);
}
//______________________________________________________________________________voidVHashTable::SetGlobalEndTime(Double_t gend)
{
// Sets the start time of the hash table. Rehash if necessary
if (gend > mGlobalEndTime) Expand(gend);
}
//______________________________________________________________________________voidVHashTable::Expand(Double_t gend)
{
// Expands the hash table. gend must be > mGlobalEndTime.// If the capacity has to be extended more than "rehashlimit" slots,// a rehashing is done without changing the old capacity.Int_t rehashlimit = mCapacity/10+1;
Int_t newcapacity = mCapacity+rehashlimit;
Double_t newendtime = mGlobalEndTime + rehashlimit*(Double_t)(mGlobalEndTime-mGlobalStartTime)/mCapacity;
if (gend <= mGlobalEndTime) return;
if (gend < newendtime) {
mFilesHashTable = (TObjArray**) TStorage::ReAlloc(mFilesHashTable, newcapacity * sizeof(TObjArray*),
mCapacity * sizeof(TObjArray*));
mGlobalEndTime = newendtime;
mCapacity = newcapacity;
} else {
Rehash(mCapacity, mGlobalStartTime, gend);
}
}
//______________________________________________________________________________voidVHashTable::Rehash(Int_t newcapacity, Double_t gstart, Double_t gend)
{
// Rehash the time hash table
TObjArray** tmpfdnames;
Int_t tmpusedslots;
Int_t tmpsize;
TObjArray* tmpfdstart1;
VFrFileIndex* vfileindex;
Double_t filestart, fileend;
Int_t slot, slotstart, slotend;
tmpfdnames = new TObjArray* [newcapacity];
memset(tmpfdnames, 0, newcapacity*sizeof(TObjArray*));
tmpusedslots = 0;
tmpsize = 0;
// Read the times in the unique names array and put them in the new hash table
TObjArrayIter next(mFilesUnique);
if (mFilesUnique !=0) {
while ((vfileindex = (VFrFileIndex*)(next()))!=0) {
filestart = vfileindex->GetStartTime();
fileend = vfileindex->GetEndTime();
slotstart = (Int_t)(newcapacity*(filestart - gstart)/(gend-gstart));
if (filestart>=gend) slotstart = -1;
slotend = (Int_t)(newcapacity*(fileend - gstart)/(gend-gstart));
if (fabs(fileend - (gstart+slotend*(gend-gstart)/newcapacity))<1e-6)
slotend--;
for (slot = slotstart; slot<=slotend; slot++) {
// If necessary, create a new slot
if (!tmpfdnames[slot]) {
tmpfdstart1 = new TObjArray(mOptimalCollision+2);
tmpfdnames[slot] = tmpfdstart1;
tmpusedslots++;
}
tmpfdnames[slot]->Add(vfileindex);
tmpsize++;
}
}
}
for (Int_t i=0;i<mCapacity;i++) {
if (mFilesHashTable[i]) mFilesHashTable[i]->Clear();
SafeDelete(mFilesHashTable[i]);
}
delete [] mFilesHashTable;
mFilesHashTable = tmpfdnames;
mGlobalStartTime = gstart;
mGlobalEndTime = gend;
mCapacity = newcapacity;
mUsedSlots = tmpusedslots;
mSize = tmpsize;
// Reste : - si new capacity = old and start = old and end = old(dans le slot),// ne rien faire// - proteger si gstart>mGlobalStart ou gend<mGlobalEnd
}
//______________________________________________________________________________voidVHashTable::Streamer(TBuffer &R__b)
{
// Stream an object of class VHashTable.UInt_t R__s, R__c;
if (R__b.IsReading()) {
Version_t R__v = R__b.ReadVersion(&R__s, &R__c); if (R__v) { }
TNamed::Streamer(R__b);
R__b >> mGlobalStartTime;
R__b >> mGlobalEndTime;
R__b >> mCapacity;
R__b >> mUsedSlots;
R__b >> mSize;
R__b >> mNFiles;
R__b >> mFilesUnique;
R__b >> mOptimalCollision;
//R__b.ReadArray(mFilesHashTable);mFilesHashTable = new TObjArray* [mCapacity];
memset(mFilesHashTable, 0, mCapacity*sizeof(TObjArray*));
TObjArray* obj;
for (Int_t i=0; i<mCapacity;i++) {
R__b >> obj;
if (obj) mFilesHashTable[i] = obj;
}
R__b.CheckByteCount(R__s, R__c, VHashTable::IsA());
} else {
R__c = R__b.WriteVersion(VHashTable::IsA(), kTRUE);
TNamed::Streamer(R__b);
R__b << mGlobalStartTime;
R__b << mGlobalEndTime;
R__b << mCapacity;
R__b << mUsedSlots;
R__b << mSize;
R__b << mNFiles;
R__b << mFilesUnique;
R__b << mOptimalCollision;
//R__b.WriteArray(mFilesHashTable, __COUNTER__);
for (Int_t i=0; i<mCapacity;i++) {
R__b << mFilesHashTable[i];
}
R__b.SetByteCount(R__c, kTRUE);
}
}
- ROOT page - VEGA 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
, or
contact
with any questions or problems regarding ROOT or VEGA.
- ROOT page - VEGA page - Class index - Top of the page