KVHashList Class Reference

Detailed Description

Extended version of ROOT THashList.

Created by KVClassFactory on Mon Nov 30 15:00:00 2009 Author: John Frankland,,,

This collection class uses a THashList for quick look-up of objects based on the TString::Hash() value of their name, and adds all the extra functionality defined in KVSeqCollection.

Automatic rehashing of the list is enabled by default (with rehash level = 2), unlike THashList (disabled by default). Beware if objects' names change or are changed after being added to the list: a manual Rehash() is required.

Sorting the list

As THashList::Sort() is defined, we implemented a KVHashList::Sort() method which takes exactly the same argument as THashList::Sort().

Examples

MicroStat_example2.C.

Definition at line 29 of file KVHashList.h.

#include <KVHashList.h>

Inheritance diagram for KVHashList:

Public Member Functions
	KVHashList (Int_t capacity=TCollection::kInitHashTableCapacity, Int_t rehash=2)
virtual	~KVHashList ()
	Destructor. More...
Float_t	AverageCollisions () const
template<typename T >
Bool_t	ContainsObjectWithName (const T &o)
const TList *	GetListForObject (const char *name) const
const TList *	GetListForObject (const TObject *obj) const
void	Rehash (Int_t newCapacity=0)
void	Sort (Bool_t order=kSortAscending)
Public Member Functions inherited from KVSeqCollection
	KVSeqCollection ()
	Default constructor. More...
	KVSeqCollection (const Char_t *collection_classname)
	KVSeqCollection (const KVSeqCollection &)
virtual	~KVSeqCollection ()
virtual void	Add (TObject *obj)
virtual void	AddAfter (const TObject *after, TObject *obj)
virtual void	AddAt (TObject *obj, Int_t idx)
virtual void	AddBefore (const TObject *before, TObject *obj)
virtual void	AddFirst (TObject *obj)
virtual void	AddLast (TObject *obj)
virtual TObject *	After (const TObject *obj) const
virtual TObject *	At (Int_t idx) const
virtual TObject *	Before (const TObject *obj) const
virtual void	Clear (Option_t *option="")
const Char_t *	CollectionClassName () const
virtual void	Copy (TObject &obj) const
virtual void	Delete (Option_t *option="")
virtual void	Execute (const char *method, const char *params, Int_t *error=0)
virtual void	Execute (TMethod *method, TObjArray *params, Int_t *error=0)
virtual TObject *	FindObject (const char *name) const
virtual TObject *	FindObject (const TObject *obj) const
virtual TObject *	FindObjectAny (const Char_t *att, const Char_t *keys, Bool_t contains_all=kFALSE, Bool_t case_sensitive=kTRUE) const
TObject *	FindObjectByClass (const Char_t *) const
	Return (first) object in embedded list with given class. More...
TObject *	FindObjectByClass (const TClass *) const
	Return (first) object in embedded list with given class. More...
virtual TObject *	FindObjectByLabel (const Char_t *) const
virtual TObject *	FindObjectByName (const Char_t *name) const
virtual TObject *	FindObjectByNumber (UInt_t num) const
virtual TObject *	FindObjectByTitle (const Char_t *) const
	Will return object with given title (value of TObject::GetTitle() method). More...
virtual TObject *	FindObjectByType (const Char_t *) const
virtual TObject *	FindObjectWithMethod (const Char_t *retvalue, const Char_t *method) const
virtual TObject *	FindObjectWithNameAndType (const Char_t *name, const Char_t *type) const
virtual TObject *	First () const
template<typename T >
T *	get_object (const TString &name) const
TSeqCollection *	GetCollection () const
virtual TObject **	GetObjectRef (const TObject *obj) const
	Return reference to object. More...
virtual Int_t	GetSize () const
KVSeqCollection *	GetSubListWithClass (const Char_t *class_name) const
KVSeqCollection *	GetSubListWithClass (const TClass *_class) const
KVSeqCollection *	GetSubListWithLabel (const Char_t *retvalue) const
KVSeqCollection *	GetSubListWithMethod (const Char_t *retvalue, const Char_t *method) const
KVSeqCollection *	GetSubListWithName (const Char_t *retvalue) const
KVSeqCollection *	GetSubListWithType (const Char_t *retvalue) const
virtual Bool_t	IsCleanup () const
virtual Bool_t	IsSendingModifiedSignals () const
virtual Bool_t	IsSortable () const
virtual Bool_t	IsSorted () const
virtual TObject *	Last () const
virtual TIterator *	MakeIterator (Bool_t dir=kIterForward) const
	Make and return iterator for the list. More...
virtual void	Modified ()
KVSeqCollection &	operator= (const KVSeqCollection &)
virtual void	RecursiveRemove (TObject *obj)
virtual TObject *	Remove (TObject *obj)
	Remove object from list. More...
virtual void	SendModifiedSignals (Bool_t yes=kTRUE)
virtual void	SetCleanup (Bool_t enable=kTRUE)
virtual void	SetOwner (Bool_t enable=kTRUE)
Public Member Functions inherited from TSeqCollection
virtual	~TSeqCollection ()
virtual Int_t	GetLast () const
virtual Int_t	IndexOf (const TObject *obj) const
TClass *	IsA () const override
Int_t	LastIndex () const
Long64_t	Merge (TCollection *list)
virtual void	RemoveAfter (TObject *after)
virtual TObject *	RemoveAt (Int_t idx)
virtual void	RemoveBefore (TObject *before)
virtual void	RemoveFirst ()
virtual void	RemoveLast ()
void	Streamer (TBuffer &) override
void	StreamerNVirtual (TBuffer &ClassDef_StreamerNVirtual_b)
void	UnSort ()
Public Member Functions inherited from TCollection
virtual	~TCollection ()
virtual void	AddAll (const TCollection *col)
void	AddVector (TObject *obj1,...)
Bool_t	AssertClass (TClass *cl) const
TIter	begin () const
void	Browse (TBrowser *b) override
Int_t	Capacity () const
TObject *	Clone (const char *newname="") const override
Int_t	Compare (const TObject *obj) const override
Bool_t	Contains (const char *name) const
Bool_t	Contains (const TObject *obj) const
void	Draw (Option_t *option="") override
void	Dump () const override
TIter	end () const
virtual Int_t	GetEntries () const
const char *	GetName () const override
virtual Int_t	GrowBy (Int_t delta) const
ULong_t	Hash () const override
Bool_t	IsArgNull (const char *where, const TObject *obj) const
virtual Bool_t	IsEmpty () const
Bool_t	IsFolder () const override
Bool_t	IsOwner () const
R__ALWAYS_INLINE Bool_t	IsUsingRWLock () const
void	ls (Option_t *option="") const override
virtual TIterator *	MakeReverseIterator () const
Bool_t	Notify () override
TObject *	operator() (const char *name) const
void	Paint (Option_t *option="") override
virtual void	Print (Option_t *option, const char *wildcard, Int_t recurse=1) const
virtual void	Print (Option_t *option, Int_t recurse) const
virtual void	Print (Option_t *option, TPRegexp &regexp, Int_t recurse=1) const
void	Print (Option_t *option="") const override
void	RemoveAll ()
virtual void	RemoveAll (TCollection *col)
void	SetCurrentCollection ()
void	SetName (const char *name)
void	StreamerNVirtual (TBuffer &ClassDef_StreamerNVirtual_b)
virtual bool	UseRWLock (Bool_t enable=true)
Int_t	Write (const char *name=nullptr, Int_t option=0, Int_t bufsize=0) const override
Int_t	Write (const char *name=nullptr, Int_t option=0, Int_t bufsize=0) override
Public Member Functions inherited from TObject
	TObject ()
	TObject (const TObject &object)
virtual	~TObject ()
void	AbstractMethod (const char *method) const
virtual void	AppendPad (Option_t *option="")
ULong_t	CheckedHash ()
virtual const char *	ClassName () const
virtual Int_t	DistancetoPrimitive (Int_t px, Int_t py)
virtual void	DrawClass () const
virtual TObject *	DrawClone (Option_t *option="") const
virtual void	Error (const char *method, const char *msgfmt,...) const
virtual void	ExecuteEvent (Int_t event, Int_t px, Int_t py)
virtual void	Fatal (const char *method, const char *msgfmt,...) const
virtual Option_t *	GetDrawOption () const
virtual const char *	GetIconName () const
virtual char *	GetObjectInfo (Int_t px, Int_t py) const
virtual Option_t *	GetOption () const
virtual const char *	GetTitle () const
virtual UInt_t	GetUniqueID () const
virtual Bool_t	HandleTimer (TTimer *timer)
Bool_t	HasInconsistentHash () const
virtual void	Info (const char *method, const char *msgfmt,...) const
virtual Bool_t	InheritsFrom (const char *classname) const
virtual Bool_t	InheritsFrom (const TClass *cl) const
virtual void	Inspect () const
void	InvertBit (UInt_t f)
Bool_t	IsDestructed () const
virtual Bool_t	IsEqual (const TObject *obj) const
R__ALWAYS_INLINE Bool_t	IsOnHeap () const
R__ALWAYS_INLINE Bool_t	IsZombie () const
void	MayNotUse (const char *method) const
void	Obsolete (const char *method, const char *asOfVers, const char *removedFromVers) const
void	operator delete (void *ptr)
void	operator delete (void *ptr, void *vp)
void	operator delete[] (void *ptr)
void	operator delete[] (void *ptr, void *vp)
void *	operator new (size_t sz)
void *	operator new (size_t sz, void *vp)
void *	operator new[] (size_t sz)
void *	operator new[] (size_t sz, void *vp)
TObject &	operator= (const TObject &rhs)
virtual void	Pop ()
virtual Int_t	Read (const char *name)
void	ResetBit (UInt_t f)
virtual void	SaveAs (const char *filename="", Option_t *option="") const
virtual void	SavePrimitive (std::ostream &out, Option_t *option="")
void	SetBit (UInt_t f)
void	SetBit (UInt_t f, Bool_t set)
virtual void	SetDrawOption (Option_t *option="")
virtual void	SetUniqueID (UInt_t uid)
void	StreamerNVirtual (TBuffer &ClassDef_StreamerNVirtual_b)
virtual void	SysError (const char *method, const char *msgfmt,...) const
R__ALWAYS_INLINE Bool_t	TestBit (UInt_t f) const
Int_t	TestBits (UInt_t f) const
virtual void	UseCurrentStyle ()
virtual void	Warning (const char *method, const char *msgfmt,...) const

Additional Inherited Members
Public Types inherited from TObject
enum	EDeprecatedStatusBits
enum	EStatusBits
Static Public Member Functions inherited from KVSeqCollection
static KVSeqCollection *	MakeListFromFile (TFile *file)
static KVSeqCollection *	MakeListFromFileWithClass (TFile *file, const Char_t *class_name)
static KVSeqCollection *	MakeListFromFileWithClass (TFile *file, const TClass *_class)
static KVSeqCollection *	MakeListFromFileWithMethod (TFile *file, const Char_t *retvalue, const Char_t *method)
static void	RehashCleanupList ()
Static Public Member Functions inherited from TSeqCollection
static TClass *	Class ()
static const char *	Class_Name ()
static constexpr Version_t	Class_Version ()
static const char *	DeclFileName ()
static Int_t	ObjCompare (TObject *a, TObject *b)
static void	QSort (TObject **a, Int_t first, Int_t last)
static void	QSort (TObject **a, Int_t nBs, TObject ***b, Int_t first, Int_t last)
static void	QSort (TObject **a, TObject **b, Int_t first, Int_t last)
Static Public Member Functions inherited from TCollection
static TClass *	Class ()
static const char *	Class_Name ()
static constexpr Version_t	Class_Version ()
static const char *	DeclFileName ()
static void	EmptyGarbageCollection ()
static void	GarbageCollect (TObject *obj)
static TCollection *	GetCurrentCollection ()
static void	StartGarbageCollection ()
Static Public Member Functions inherited from TObject
static TClass *	Class ()
static const char *	Class_Name ()
static constexpr Version_t	Class_Version ()
static const char *	DeclFileName ()
static Longptr_t	GetDtorOnly ()
static Bool_t	GetObjectStat ()
static void	SetDtorOnly (void *obj)
static void	SetObjectStat (Bool_t stat)
Public Attributes inherited from TCollection
	kInitCapacity
	kInitHashTableCapacity
Public Attributes inherited from TObject
	kBitMask
	kCanDelete
	kCannotPick
	kHasUUID
	kInconsistent
	kInvalidObject
	kIsOnHeap
	kIsReferenced
	kMustCleanup
	kNoContextMenu
	kNotDeleted
	kObjInCanvas
	kOverwrite
	kSingleKey
	kWriteDelete
	kZombie
Protected Types inherited from TCollection
enum	EStatusBits
Protected Member Functions inherited from TSeqCollection
	TSeqCollection ()
Protected Member Functions inherited from TCollection
	TCollection ()
virtual const char *	GetCollectionEntryName (TObject *entry) const
virtual void	PrintCollectionEntry (TObject *entry, Option_t *option, Int_t recurse) const
Protected Member Functions inherited from TObject
virtual void	DoError (int level, const char *location, const char *fmt, va_list va) const
void	MakeZombie ()
Protected Attributes inherited from TSeqCollection
Bool_t	fSorted
Protected Attributes inherited from TCollection
TString	fName
Int_t	fSize
	kIsOwner
	kUseRWLock
Protected Attributes inherited from TObject
	kOnlyPrepStep

Constructor & Destructor Documentation

KVHashList()

KVHashList::KVHashList	(	Int_t	capacity = TCollection::kInitHashTableCapacity,
		Int_t	rehash = 2
	)

Create a THashList object. Capacity is the initial hashtable capacity (i.e. number of slots), by default kInitHashTableCapacity = 17, and rehash 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 rehash 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. The default value of rehash = 2 (minimum allowed value) - automatic rehashing is enabled by default. If rehash=0 the table will NOT automatically be rehashed. Use Rehash() for manual rehashing. WARNING !!! If the name of an object in the HashList is modified, The hashlist must be Rehashed

Definition at line 26 of file KVHashList.cpp.

~KVHashList()

KVHashList::~KVHashList ( )

virtual

Destructor.

Definition at line 52 of file KVHashList.cpp.

Member Function Documentation

AverageCollisions()

Float_t KVHashList::AverageCollisions

(

)

const

Return the average collision rate. The higher the number the longer the linked lists in the hashtable, the slower the lookup. If the number is high, or lookup noticeably too slow, perfrom a Rehash()

Definition at line 64 of file KVHashList.cpp.

ContainsObjectWithName()

template<typename T >

Bool_t KVHashList::ContainsObjectWithName ( const T &  o )

inline

Returns true if list contains an object with the same name as o class T must have a method const char* T::GetName() const

Definition at line 48 of file KVHashList.h.

GetListForObject() [1/2]

const TList * KVHashList::GetListForObject

(

const char *

name

)

const

Return the THashTable's list (bucket) in which obj can be found based on its hash; see THashTable::GetListForObject().

Definition at line 121 of file KVHashList.cpp.

GetListForObject() [2/2]

const TList * KVHashList::GetListForObject

(

const TObject *

obj

)

const

Return the THashTable's list (bucket) in which obj can be found based on its hash; see THashTable::GetListForObject().

Definition at line 140 of file KVHashList.cpp.

Rehash()

void KVHashList::Rehash

(

Int_t

newCapacity = 0

)

Rehash the hashlist.

This needs to be done in two cases:

1. If the collision rate becomes too high (i.e. the average size of the linked lists become too long - use AverageCollisions() to check if you need to rehash.) then lookup efficiency decreases since relatively long lists have to be searched every time. To improve performance rehash the hashtable, increasing the number of slots. This method resizes the table to newCapacity slots and refills the table.
2. If the names of any objects in the list CHANGE, you must rehash the list (as the lookup of objects depends on the TString::Hash() value calculated from their name when they are added to the list). In this case it is not necessary to increase the capacity of the list, just call Rehash() with no arguments.

Definition at line 92 of file KVHashList.cpp.

Sort()

void KVHashList::Sort ( Bool_t  order = kSortAscending )

inline

Definition at line 44 of file KVHashList.h.