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