Logo ROOT  
Reference Guide
TMap.cxx
Go to the documentation of this file.
1// @(#)root/cont:$Id$
2// Author: Fons Rademakers 12/11/95
3
4/*************************************************************************
5 * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers. *
6 * All rights reserved. *
7 * *
8 * For the licensing terms see $ROOTSYS/LICENSE. *
9 * For the list of contributors see $ROOTSYS/README/CREDITS. *
10 *************************************************************************/
11
12/** \class TMap
13\ingroup Containers
14TMap implements an associative array of (key,value) pairs using a
15THashTable for efficient retrieval (therefore TMap does not conserve
16the order of the entries). The hash value is calculated
17using the value returned by the keys Hash() function and the
18key comparison is done via the IsEqual() function.
19Both key and value must inherit from TObject.
20*/
21
22#include "TMap.h"
23#include "THashTable.h"
24#include "TROOT.h"
25#include "TBuffer.h"
26#include "TBrowser.h"
27#include "TRegexp.h"
28
30
31////////////////////////////////////////////////////////////////////////////////
32/// TMap ctor. See THashTable for a description of the arguments.
33
34TMap::TMap(Int_t capacity, Int_t rehashlevel)
35{
36 fSize = 0;
37 fTable = new THashTable(capacity, rehashlevel);
38}
39
40////////////////////////////////////////////////////////////////////////////////
41/// TMap dtor. Objects are not deleted unless the TMap is the
42/// owner (set via SetOwner()).
43
45{
46 Clear();
47 delete fTable;
48}
49
50////////////////////////////////////////////////////////////////////////////////
51/// This function may not be used (but we need to provide it since it is
52/// a pure virtual in TCollection). Use Add(key,value) instead.
53
55{
56 MayNotUse("Add(TObject *obj)");
57}
58
59////////////////////////////////////////////////////////////////////////////////
60/// Add a (key,value) pair to the map.
61
62void TMap::Add(TObject *key, TObject *value)
63{
64 if (IsArgNull("Add", key)) return;
65
66 fTable->Add(new TPair(key, value));
67 fSize++;
68}
69
70////////////////////////////////////////////////////////////////////////////////
71/// Return the ratio of entries vs occupied slots.
72
74{
75 return fTable->AverageCollisions();
76}
77
78////////////////////////////////////////////////////////////////////////////////
79/// Return number of slots in the hashtable. Use GetSize() to get the
80/// number of objects stored in the TMap.
81
83{
84 return fTable->Capacity();
85}
86
87////////////////////////////////////////////////////////////////////////////////
88/// Remove all (key,value) pairs from the map. The keys/values are
89/// deleted depending on the state of key-ownership (SetOwner()) and
90/// value-ownership (SetOwnerValue()).
91///
92/// To delete these objects regardless of the ownership state use:
93/// - Delete() to delete only keys;
94/// - DeleteValues() to delete only values;
95/// - DeleteAll() to delete both keys and values.
96
97void TMap::Clear(Option_t *option)
98{
99 if (IsOwner() && IsOwnerValue())
100 DeleteAll();
101 else if (IsOwner())
102 Delete();
103 else if (IsOwnerValue())
104 DeleteValues();
105 else {
106 fTable->Delete(option); // delete the TPair's
107 fSize = 0;
108 }
109}
110
111////////////////////////////////////////////////////////////////////////////////
112/// Returns the number of collisions for a key with a certain name
113/// (i.e. number of objects in same slot in the hash table, i.e. length
114/// of linked list).
115
116Int_t TMap::Collisions(const char *keyname) const
117{
118 return fTable->Collisions(keyname);
119}
120
121////////////////////////////////////////////////////////////////////////////////
122/// Returns the number of collisions for a key (i.e. number of objects
123/// in same slot in the hash table, i.e. length of linked list).
124
126{
127 return fTable->Collisions(key);
128}
129
130////////////////////////////////////////////////////////////////////////////////
131/// Remove all (key,value) pairs from the map AND delete the keys
132/// when they are allocated on the heap.
133
135{
136 TIter next(fTable);
137 TPair *a;
138
139 while ((a = (TPair *)next()))
140 if (a->Key() && a->Key()->IsOnHeap())
142
143 fTable->Delete(option); // delete the TPair's
144 fSize = 0;
145}
146
147////////////////////////////////////////////////////////////////////////////////
148/// Remove all (key,value) pairs from the map AND delete the values
149/// when they are allocated on the heap.
150
152{
153 TIter next(fTable);
154 TPair *a;
155
156 while ((a = (TPair *)next()))
157 if (a->Value() && a->Value()->IsOnHeap())
159
160 fTable->Delete(); // delete the TPair's
161 fSize = 0;
162}
163
164////////////////////////////////////////////////////////////////////////////////
165/// Remove all (key,value) pairs from the map AND delete the keys AND
166/// values when they are allocated on the heap.
167
169{
170 TIter next(fTable);
171 TPair *a;
172
173 while ((a = (TPair *)next())) {
174 if (a->Key() && a->Key()->IsOnHeap())
176 if (a->Value() && a->Value()->IsOnHeap())
178 }
179
180 fTable->Delete(); // delete the TPair's
181 fSize = 0;
182}
183
184////////////////////////////////////////////////////////////////////////////////
185/// Remove (key,value) pair with key from the map. Returns true
186/// if the key was found and removed, false otherwise.
187/// The key and value objects are deleted if map is the owner
188/// of keys and values respectively.
189
191{
192 if (!key) return kFALSE;
193
194 TPair *a;
195 if ((a = (TPair *)fTable->FindObject(key))) {
196 if (fTable->Remove(key)) {
197 if (IsOwner() && a->Key() && a->Key()->IsOnHeap())
199 if (IsOwnerValue() && a->Value() && a->Value()->IsOnHeap())
201 delete a;
202 fSize--;
203 return kTRUE;
204 }
205 }
206 return kFALSE;
207}
208
209////////////////////////////////////////////////////////////////////////////////
210/// Check if a (key,value) pair exists with keyname as name of the key.
211/// Returns a TPair* (need to downcast from TObject). Use Key() and
212/// Value() to get the pointers to the key and value, respectively.
213/// Returns 0 if not found.
214
215TObject *TMap::FindObject(const char *keyname) const
216{
217 return fTable->FindObject(keyname);
218}
219
220////////////////////////////////////////////////////////////////////////////////
221/// Check if a (key,value) pair exists with key as key.
222/// Returns a TPair* (need to downcast from TObject). Use Key() and
223/// Value() to get the pointers to the key and value, respectively.
224/// Returns 0 if not found.
225
227{
228 if (IsArgNull("FindObject", key)) return 0;
229
230 return fTable->FindObject(key);
231}
232
233////////////////////////////////////////////////////////////////////////////////
234/// Returns a pointer to the value associated with keyname as name of the key.
235
236TObject *TMap::GetValue(const char *keyname) const
237{
238 TPair *a = (TPair *)fTable->FindObject(keyname);
239 if (a) return a->Value();
240 return 0;
241}
242
243////////////////////////////////////////////////////////////////////////////////
244/// Returns a pointer to the value associated with key.
245
247{
248 if (IsArgNull("GetValue", key)) return 0;
249
250 TPair *a = (TPair *)fTable->FindObject(key);
251 if (a) return a->Value();
252 return 0;
253}
254
255////////////////////////////////////////////////////////////////////////////////
256/// Create an iterator for TMap.
257
259{
260 return new TMapIter(this, dir);
261}
262
263////////////////////////////////////////////////////////////////////////////////
264/// Print the collection entry.
265
266void TMap::PrintCollectionEntry(TObject* entry, Option_t* option, Int_t recurse) const
267{
268 TObject* val = GetValue(entry);
269
271 printf("Key: ");
272 entry->Print();
274 printf("Value: ");
275 TCollection* coll = dynamic_cast<TCollection*>(val);
276 if (coll) {
277 coll->Print(option, recurse);
278 } else {
279 val->Print(option);
280 }
281}
282
283////////////////////////////////////////////////////////////////////////////////
284/// Rehash the underlaying THashTable (see THashTable::Rehash()).
285
286void TMap::Rehash(Int_t newCapacity, Bool_t checkObjValidity)
287{
288 fTable->Rehash(newCapacity, checkObjValidity);
289}
290
291////////////////////////////////////////////////////////////////////////////////
292/// Remove the (key,value) pair with key from the map. Returns the
293/// key object or 0 in case key was not found. If map is the owner
294/// of values, the value is deleted.
295
297{
298 if (!key) return 0;
299
300 TPair *a;
301 if ((a = (TPair *)fTable->FindObject(key))) {
302 if (fTable->Remove(key)) {
303 if (IsOwnerValue() && a->Value() && a->Value()->IsOnHeap())
305 TObject *kobj = a->Key();
306 delete a;
307 fSize--;
308 return kobj;
309 }
310 }
311 return 0;
312}
313
314////////////////////////////////////////////////////////////////////////////////
315/// Remove (key,value) pair with key from the map. Returns the
316/// pair object or 0 in case the key was not found.
317/// It is caller's responsibility to delete the pair and, eventually,
318/// the key and value objects.
319
321{
322 if (!key) return 0;
323
324 TPair *a;
325 if ((a = (TPair *)fTable->FindObject(key))) {
326 if (fTable->Remove(key)) {
327 fSize--;
328 return a;
329 }
330 }
331 return 0;
332}
333
334////////////////////////////////////////////////////////////////////////////////
335/// Set whether this map is the owner (enable==true)
336/// of its values. If it is the owner of its contents,
337/// these objects will be deleted whenever the collection itself
338/// is deleted. The objects might also be deleted or destructed when Clear
339/// is called (depending on the collection).
340
342{
343 if (enable)
345 else
347}
348
349////////////////////////////////////////////////////////////////////////////////
350/// Set ownership for keys and values.
351
353{
354 SetOwner(ownkeys);
355 SetOwnerValue(ownvals);
356}
357
358////////////////////////////////////////////////////////////////////////////////
359/// Stream all key/value pairs in the map to or from the I/O buffer.
360
361void TMap::Streamer(TBuffer &b)
362{
363 TObject *obj=0;
364 UInt_t R__s, R__c;
365
366 if (b.IsReading()) {
367 Int_t nobjects;
368 TObject *value=0;
369
370 Version_t v = b.ReadVersion(&R__s, &R__c);
371 if (v > 2)
372 TObject::Streamer(b);
373 if (v > 1)
374 fName.Streamer(b);
375 b >> nobjects;
376 for (Int_t i = 0; i < nobjects; i++) {
377 b >> obj;
378 b >> value;
379 if (obj) Add(obj, value);
380 }
381 b.CheckByteCount(R__s, R__c,TMap::IsA());
382 } else {
383 R__c = b.WriteVersion(TMap::IsA(), kTRUE);
384 TObject::Streamer(b);
385 fName.Streamer(b);
386 b << GetSize();
387 TIter next(fTable);
388 TPair *a;
389 while ((a = (TPair*) next())) {
390 b << a->Key();
391 b << a->Value();
392 }
393 b.SetByteCount(R__c, kTRUE);
394 }
395}
396
397////////////////////////////////////////////////////////////////////////////////
398/// Write all objects in this map. By default all objects in
399/// the collection are written individually (each object gets its
400/// own key). Note, this is recursive, i.e. objects in collections
401/// in the collection are also written individually. To write all
402/// objects using a single key specify a name and set option to
403/// TObject::kSingleKey (i.e. 1).
404
405Int_t TMap::Write(const char *name, Int_t option, Int_t bsize) const
406{
407 if ((option & kSingleKey)) {
408 return TObject::Write(name, option, bsize);
409 } else {
410 option &= ~kSingleKey;
411 Int_t nbytes = 0;
412 TIter next(fTable);
413 TPair *a;
414 while ((a = (TPair*) next())) {
415 if (a->Key())
416 nbytes += a->Key()->Write(name, option, bsize);
417 if (a->Value())
418 nbytes += a->Value()->Write(name, option, bsize);
419 }
420 return nbytes;
421 }
422}
423
424////////////////////////////////////////////////////////////////////////////////
425/// Write all objects in this map. By default all objects in
426/// the collection are written individually (each object gets its
427/// own key). Note, this is recursive, i.e. objects in collections
428/// in the collection are also written individually. To write all
429/// objects using a single key specify a name and set option to
430/// TObject::kSingleKey (i.e. 1).
431
432Int_t TMap::Write(const char *name, Int_t option, Int_t bsize)
433{
434 return ((const TMap*)this)->Write(name,option,bsize);
435}
436
437/** \class TPair
438Class used by TMap to store (key,value) pairs.
439*/
440
441////////////////////////////////////////////////////////////////////////////////
442/// TPair destructor.
443
445{
446 // Required since we overload TObject::Hash.
448}
449
450////////////////////////////////////////////////////////////////////////////////
451/// Browse the pair.
452
454{
455 if (b) {
456 if (fKey) b->Add(fKey);
457 if (fValue) b->Add(fValue);
458 } else {
459 if (fKey) fKey->Browse(b);
460 if (fValue) fValue->Browse(b);
461 }
462}
463
464/** \class TMapIter
465Iterator of map.
466*/
467
469
470////////////////////////////////////////////////////////////////////////////////
471/// Create a map iterator. Use dir to specify the desired iteration direction.
472
474{
475 fMap = m;
476 fDirection = dir;
477 fCursor = 0;
478}
479
480////////////////////////////////////////////////////////////////////////////////
481/// Copy ctor.
482
484{
485 fMap = iter.fMap;
486 fDirection = iter.fDirection;
487 fCursor = 0;
488 if (iter.fCursor) {
490 if (fCursor)
491 fCursor->operator=(*iter.fCursor);
492 }
493}
494
495////////////////////////////////////////////////////////////////////////////////
496/// Overridden assignment operator.
497
499{
500 if (this != &rhs && rhs.IsA() == TMapIter::Class()) {
501 const TMapIter &rhs1 = (const TMapIter &)rhs;
502 fMap = rhs1.fMap;
503 fDirection = rhs1.fDirection;
504 if (rhs1.fCursor) {
506 if (fCursor)
507 fCursor->operator=(*rhs1.fCursor);
508 }
509 }
510 return *this;
511}
512
513////////////////////////////////////////////////////////////////////////////////
514/// Overloaded assignment operator.
515
517{
518 if (this != &rhs) {
519 fMap = rhs.fMap;
521 if (rhs.fCursor) {
523 if (fCursor)
524 fCursor->operator=(*rhs.fCursor);
525 }
526 }
527 return *this;
528}
529
530////////////////////////////////////////////////////////////////////////////////
531/// Map iterator dtor.
532
534{
535 Reset();
536}
537
538////////////////////////////////////////////////////////////////////////////////
539/// Returns the next key from a map. Use TMap::GetValue() to get the value
540/// associated with the key. Returns 0 when no more items in map.
541
543{
544 if (!fCursor)
546
547 TPair *a = (TPair *)fCursor->Next();
548 if (a) return a->Key();
549 return 0;
550}
551
552////////////////////////////////////////////////////////////////////////////////
553/// Reset the map iterator.
554
556{
558}
559
560////////////////////////////////////////////////////////////////////////////////
561/// This operator compares two TIterator objects.
562
564{
565 if (aIter.IsA() == TMapIter::Class()) {
566 const TMapIter &iter(dynamic_cast<const TMapIter &>(aIter));
567 return (fCursor->operator*() != iter.fCursor->operator*());
568 }
569 return false; // for base class we don't implement a comparison
570}
571
572////////////////////////////////////////////////////////////////////////////////
573/// This operator compares two TMapIter objects.
574
576{
577 return (fCursor->operator*() != aIter.fCursor->operator*());
578}
579
580////////////////////////////////////////////////////////////////////////////////
581/// Return pointer to current object (a TPair) or nullptr.
582
584{
585 return (fCursor ? fCursor->operator*() : nullptr);
586}
void Class()
Definition: Class.C:29
#define SafeDelete(p)
Definition: RConfig.hxx:543
#define b(i)
Definition: RSha256.hxx:100
int Int_t
Definition: RtypesCore.h:43
short Version_t
Definition: RtypesCore.h:63
unsigned int UInt_t
Definition: RtypesCore.h:44
const Bool_t kFALSE
Definition: RtypesCore.h:90
float Float_t
Definition: RtypesCore.h:55
const Bool_t kTRUE
Definition: RtypesCore.h:89
const char Option_t
Definition: RtypesCore.h:64
#define ClassImp(name)
Definition: Rtypes.h:361
char name[80]
Definition: TGX11.cxx:109
Using a TBrowser one can browse all ROOT objects.
Definition: TBrowser.h:37
Buffer base class used for serializing objects.
Definition: TBuffer.h:42
Collection abstract base class.
Definition: TCollection.h:63
virtual TIterator * MakeIterator(Bool_t dir=kIterForward) const =0
Bool_t IsArgNull(const char *where, const TObject *obj) const
Returns true if object is a null pointer.
Int_t Capacity() const
Definition: TCollection.h:165
virtual void Print(Option_t *option="") const
Default print for collections, calls Print(option, 1).
virtual void SetOwner(Bool_t enable=kTRUE)
Set whether this collection is the owner (enable==true) of its content.
TString fName
Definition: TCollection.h:147
Bool_t IsOwner() const
Definition: TCollection.h:188
static void GarbageCollect(TObject *obj)
Add to the list of things to be cleaned up.
virtual Int_t GetSize() const
Return the capacity of the collection, i.e.
Definition: TCollection.h:182
Iterator of hash table.
Definition: THashTable.h:113
TObject * Next()
Return next object in hashtable. Returns 0 when no more objects in table.
Definition: THashTable.cxx:549
const TCollection * GetCollection() const
Definition: THashTable.h:131
THashTable implements a hash table to store TObject's.
Definition: THashTable.h:35
Float_t AverageCollisions() const
Definition: THashTable.h:84
TObject * Remove(TObject *obj)
Remove object from the hashtable.
Definition: THashTable.cxx:417
void Add(TObject *obj)
Add object to the hash table.
Definition: THashTable.cxx:92
void Rehash(Int_t newCapacity, Bool_t checkObjValidity=kTRUE)
Rehash the hashtable.
Definition: THashTable.cxx:365
TObject * FindObject(const char *name) const
Find object using its name.
Definition: THashTable.cxx:238
void Delete(Option_t *option="")
Remove all objects from the table AND delete all heap based objects.
Definition: THashTable.cxx:220
Int_t Collisions(const char *name) const
Returns the number of collisions for an object with a certain name (i.e.
Definition: THashTable.cxx:191
Iterator abstract base class.
Definition: TIterator.h:30
Iterator of map.
Definition: TMap.h:147
THashTableIter * fCursor
Definition: TMap.h:151
~TMapIter()
Map iterator dtor.
Definition: TMap.cxx:533
TIterator & operator=(const TIterator &rhs)
Overridden assignment operator.
Definition: TMap.cxx:498
const TMap * fMap
Definition: TMap.h:150
void Reset()
Reset the map iterator.
Definition: TMap.cxx:555
Bool_t fDirection
Definition: TMap.h:152
TMapIter()
Definition: TMap.h:154
TObject * operator*() const
Return pointer to current object (a TPair) or nullptr.
Definition: TMap.cxx:583
TObject * Next()
Returns the next key from a map.
Definition: TMap.cxx:542
Bool_t operator!=(const TIterator &aIter) const
This operator compares two TIterator objects.
Definition: TMap.cxx:563
TMap implements an associative array of (key,value) pairs using a THashTable for efficient retrieval ...
Definition: TMap.h:40
void DeleteAll()
Remove all (key,value) pairs from the map AND delete the keys AND values when they are allocated on t...
Definition: TMap.cxx:168
TMap(const TMap &map)
TIterator * MakeIterator(Bool_t dir=kIterForward) const
Create an iterator for TMap.
Definition: TMap.cxx:258
TPair * RemoveEntry(TObject *key)
Remove (key,value) pair with key from the map.
Definition: TMap.cxx:320
virtual ~TMap()
TMap dtor.
Definition: TMap.cxx:44
virtual void PrintCollectionEntry(TObject *entry, Option_t *option, Int_t recurse) const
Print the collection entry.
Definition: TMap.cxx:266
Int_t Collisions(const char *keyname) const
Returns the number of collisions for a key with a certain name (i.e.
Definition: TMap.cxx:116
void Add(TObject *obj)
This function may not be used (but we need to provide it since it is a pure virtual in TCollection).
Definition: TMap.cxx:54
THashTable * fTable
Definition: TMap.h:45
virtual void SetOwnerKeyValue(Bool_t ownkeys=kTRUE, Bool_t ownvals=kTRUE)
Set ownership for keys and values.
Definition: TMap.cxx:352
void Delete(Option_t *option="")
Remove all (key,value) pairs from the map AND delete the keys when they are allocated on the heap.
Definition: TMap.cxx:134
friend class TMapIter
Definition: TMap.h:42
Float_t AverageCollisions() const
Return the ratio of entries vs occupied slots.
Definition: TMap.cxx:73
void DeleteValues()
Remove all (key,value) pairs from the map AND delete the values when they are allocated on the heap.
Definition: TMap.cxx:151
Bool_t DeleteEntry(TObject *key)
Remove (key,value) pair with key from the map.
Definition: TMap.cxx:190
virtual Int_t Write(const char *name=0, Int_t option=0, Int_t bufsize=0)
Write all objects in this map.
Definition: TMap.cxx:432
@ kIsOwnerValue
Definition: TMap.h:51
Bool_t IsOwnerValue() const
Definition: TMap.h:78
virtual void SetOwnerValue(Bool_t enable=kTRUE)
Set whether this map is the owner (enable==true) of its values.
Definition: TMap.cxx:341
Int_t Capacity() const
Return number of slots in the hashtable.
Definition: TMap.cxx:82
TObject * GetValue(const char *keyname) const
Returns a pointer to the value associated with keyname as name of the key.
Definition: TMap.cxx:236
TObject * FindObject(const char *keyname) const
Check if a (key,value) pair exists with keyname as name of the key.
Definition: TMap.cxx:215
TObject * Remove(TObject *key)
Remove the (key,value) pair with key from the map.
Definition: TMap.cxx:296
void Rehash(Int_t newCapacity, Bool_t checkObjValidity=kTRUE)
Rehash the underlaying THashTable (see THashTable::Rehash()).
Definition: TMap.cxx:286
void Clear(Option_t *option="")
Remove all (key,value) pairs from the map.
Definition: TMap.cxx:97
Mother of all ROOT objects.
Definition: TObject.h:37
virtual Int_t Write(const char *name=0, Int_t option=0, Int_t bufsize=0)
Write this object to the current directory.
Definition: TObject.cxx:796
@ kSingleKey
write collection with single key
Definition: TObject.h:87
virtual void Browse(TBrowser *b)
Browse object. May be overridden for another default action.
Definition: TObject.cxx:119
void MayNotUse(const char *method) const
Use this method to signal that a method (defined in a base class) may not be called in a derived clas...
Definition: TObject.cxx:944
void SetBit(UInt_t f, Bool_t set)
Set or unset the user status bits as specified in f.
Definition: TObject.cxx:694
virtual void Print(Option_t *option="") const
This method must be overridden when a class wants to print itself.
Definition: TObject.cxx:550
void ResetBit(UInt_t f)
Definition: TObject.h:186
Class used by TMap to store (key,value) pairs.
Definition: TMap.h:102
TObject * fValue
Definition: TMap.h:106
virtual void Browse(TBrowser *b)
Browse the pair.
Definition: TMap.cxx:453
TObject * fKey
Definition: TMap.h:105
virtual ~TPair()
TPair destructor.
Definition: TMap.cxx:444
static void IndentLevel()
Functions used by ls() to indent an object hierarchy.
Definition: TROOT.cxx:2781
void CallRecursiveRemoveIfNeeded(TObject &obj)
call RecursiveRemove for obj if gROOT is valid and obj.TestBit(kMustCleanup) is true.
Definition: TROOT.h:395
auto * m
Definition: textangle.C:8
auto * a
Definition: textangle.C:12