Logo ROOT  
Reference Guide
 
Loading...
Searching...
No Matches
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
29
30////////////////////////////////////////////////////////////////////////////////
31/// TMap ctor. See THashTable for a description of the arguments.
32
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
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
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
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
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
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 nullptr;
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{
238 if (a) return a->Value();
239 return nullptr;
240}
241
242////////////////////////////////////////////////////////////////////////////////
243/// Returns a pointer to the value associated with key.
244
246{
247 if (IsArgNull("GetValue", key)) return nullptr;
248
249 TPair *a = (TPair *)fTable->FindObject(key);
250 if (a) return a->Value();
251 return nullptr;
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
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
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 nullptr;
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 nullptr;
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 nullptr;
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 nullptr;
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
356
357////////////////////////////////////////////////////////////////////////////////
358/// Stream all key/value pairs in the map to or from the I/O buffer.
359
361{
362 TObject *obj = nullptr;
364
365 if (b.IsReading()) {
367 TObject *value = nullptr;
368
369 Version_t v = b.ReadVersion(&R__s, &R__c);
370 if (v > 2)
372 if (v > 1)
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);
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
405{
406 if ((option & kSingleKey)) {
408 } else {
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, bufsize);
416 if (a->Value())
417 nbytes += a->Value()->Write(name, option, bufsize);
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
432{
433 return ((const TMap*)this)->Write(name,option,bufsize);
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
467
468////////////////////////////////////////////////////////////////////////////////
469/// Create a map iterator. Use dir to specify the desired iteration direction.
470
472{
473 fMap = m;
474 fDirection = dir;
475 fCursor = nullptr;
476}
477
478////////////////////////////////////////////////////////////////////////////////
479/// Copy ctor.
480
482{
483 fMap = iter.fMap;
484 fDirection = iter.fDirection;
485 fCursor = nullptr;
486 if (iter.fCursor) {
487 fCursor = (THashTableIter *)iter.fCursor->GetCollection()->MakeIterator();
488 if (fCursor)
489 fCursor->operator=(*iter.fCursor);
490 }
491}
492
493////////////////////////////////////////////////////////////////////////////////
494/// Overridden assignment operator.
495
497{
498 if (this != &rhs && rhs.IsA() == TMapIter::Class()) {
499 const TMapIter &rhs1 = (const TMapIter &)rhs;
500 fMap = rhs1.fMap;
501 fDirection = rhs1.fDirection;
502 if (rhs1.fCursor) {
503 fCursor = (THashTableIter *)rhs1.fCursor->GetCollection()->MakeIterator();
504 if (fCursor)
505 fCursor->operator=(*rhs1.fCursor);
506 }
507 }
508 return *this;
509}
510
511////////////////////////////////////////////////////////////////////////////////
512/// Overloaded assignment operator.
513
515{
516 if (this != &rhs) {
517 fMap = rhs.fMap;
518 fDirection = rhs.fDirection;
519 if (rhs.fCursor) {
520 fCursor = (THashTableIter *)rhs.fCursor->GetCollection()->MakeIterator();
521 if (fCursor)
522 fCursor->operator=(*rhs.fCursor);
523 }
524 }
525 return *this;
526}
527
528////////////////////////////////////////////////////////////////////////////////
529/// Map iterator dtor.
530
532{
533 Reset();
534}
535
536////////////////////////////////////////////////////////////////////////////////
537/// Returns the next key from a map. Use TMap::GetValue() to get the value
538/// associated with the key. Returns 0 when no more items in map.
539
541{
542 if (!fCursor)
543 fCursor = new THashTableIter(fMap->fTable, fDirection);
544
545 TPair *a = (TPair *)fCursor->Next();
546 if (a) return a->Key();
547 return nullptr;
548}
549
550////////////////////////////////////////////////////////////////////////////////
551/// Reset the map iterator.
552
554{
556}
557
558////////////////////////////////////////////////////////////////////////////////
559/// This operator compares two TIterator objects.
560
562{
563 if (aIter.IsA() == TMapIter::Class()) {
564 const TMapIter &iter(dynamic_cast<const TMapIter &>(aIter));
565 return (fCursor->operator*() != iter.fCursor->operator*());
566 }
567 return false; // for base class we don't implement a comparison
568}
569
570////////////////////////////////////////////////////////////////////////////////
571/// This operator compares two TMapIter objects.
572
574{
575 return (fCursor->operator*() != aIter.fCursor->operator*());
576}
577
578////////////////////////////////////////////////////////////////////////////////
579/// Return pointer to current object (a TPair) or nullptr.
580
582{
583 return (fCursor ? fCursor->operator*() : nullptr);
584}
#define SafeDelete(p)
Definition RConfig.hxx:533
#define b(i)
Definition RSha256.hxx:100
#define a(i)
Definition RSha256.hxx:99
short Version_t
Class version identifier (short)
Definition RtypesCore.h:79
float Float_t
Float 4 bytes (float)
Definition RtypesCore.h:71
constexpr Bool_t kFALSE
Definition RtypesCore.h:108
constexpr Bool_t kTRUE
Definition RtypesCore.h:107
const char Option_t
Option string (const char)
Definition RtypesCore.h:80
ROOT::Detail::TRangeCast< T, true > TRangeDynCast
TRangeDynCast is an adapter class that allows the typed iteration through a TCollection.
Option_t Option_t option
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void value
char name[80]
Definition TGX11.cxx:110
Using a TBrowser one can browse all ROOT objects.
Definition TBrowser.h:37
Buffer base class used for serializing objects.
Definition TBuffer.h:43
Collection abstract base class.
Definition TCollection.h:65
Bool_t IsArgNull(const char *where, const TObject *obj) const
Returns true if object is a null pointer.
Int_t Capacity() const
virtual void SetOwner(Bool_t enable=kTRUE)
Set whether this collection is the owner (enable==true) of its content.
TString fName
Bool_t IsOwner() const
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.
Iterator of hash table.
Definition THashTable.h:114
const TCollection * GetCollection() const override
Definition THashTable.h:132
TObject * Next() override
Return next object in hashtable. Returns 0 when no more objects in table.
THashTable implements a hash table to store TObject's.
Definition THashTable.h:35
Float_t AverageCollisions() const
Definition THashTable.h:85
void Add(TObject *obj) override
Add object to the hash table.
TObject * Remove(TObject *obj) override
Remove object from the hashtable.
void Rehash(Int_t newCapacity, Bool_t checkObjValidity=kTRUE)
Rehash the hashtable.
TObject * FindObject(const char *name) const override
Find object using its name.
Int_t Collisions(const char *name) const
Returns the number of collisions for an object with a certain name (i.e.
void Delete(Option_t *option="") override
Remove all objects from the table AND delete all heap based objects.
Iterator abstract base class.
Definition TIterator.h:30
Iterator of map.
Definition TMap.h:144
TObject * operator*() const override
Return pointer to current object (a TPair) or nullptr.
Definition TMap.cxx:581
TObject * Next() override
Returns the next key from a map.
Definition TMap.cxx:540
THashTableIter * fCursor
Definition TMap.h:148
~TMapIter()
Map iterator dtor.
Definition TMap.cxx:531
Bool_t operator!=(const TIterator &aIter) const override
This operator compares two TIterator objects.
Definition TMap.cxx:561
const TMap * fMap
Definition TMap.h:147
static TClass * Class()
void Reset() override
Reset the map iterator.
Definition TMap.cxx:553
Bool_t fDirection
Definition TMap.h:149
TMapIter()
Definition TMap.h:151
TIterator & operator=(const TIterator &rhs) override
Overridden assignment operator.
Definition TMap.cxx:496
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
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
void Delete(Option_t *option="") override
Remove all (key,value) pairs from the map AND delete the keys when they are allocated on the heap.
Definition TMap.cxx:133
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
THashTable * fTable
Definition TMap.h:45
void Add(TObject *obj) override
This function may not be used (but we need to provide it since it is a pure virtual in TCollection).
Definition TMap.cxx:53
virtual void SetOwnerKeyValue(Bool_t ownkeys=kTRUE, Bool_t ownvals=kTRUE)
Set ownership for keys and values.
Definition TMap.cxx:351
TObject * FindObject(const char *keyname) const override
Check if a (key,value) pair exists with keyname as name of the key.
Definition TMap.cxx:214
friend class TMapIter
Definition TMap.h:42
void PrintCollectionEntry(TObject *entry, Option_t *option, Int_t recurse) const override
Print the collection entry.
Definition TMap.cxx:265
Float_t AverageCollisions() const
Return the ratio of entries vs occupied slots.
Definition TMap.cxx:72
Int_t Write(const char *name=nullptr, Int_t option=0, Int_t bufsize=0) override
Write all objects in this map.
Definition TMap.cxx:431
TObject * Remove(TObject *key) override
Remove the (key,value) pair with key from the map.
Definition TMap.cxx:295
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
void Clear(Option_t *option="") override
Remove all (key,value) pairs from the map.
Definition TMap.cxx:96
TIterator * MakeIterator(Bool_t dir=kIterForward) const override
Create an iterator for TMap.
Definition TMap.cxx:257
@ kIsOwnerValue
Definition TMap.h:51
void Streamer(TBuffer &) override
Stream all key/value pairs in the map to or from the I/O buffer.
Definition TMap.cxx:360
Bool_t IsOwnerValue() const
Definition TMap.h:78
TClass * IsA() const override
Definition TMap.h:90
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
TMap(const TMap &map)=delete
void Rehash(Int_t newCapacity, Bool_t checkObjValidity=kTRUE)
Rehash the underlaying THashTable (see THashTable::Rehash()).
Definition TMap.cxx:285
Mother of all ROOT objects.
Definition TObject.h:41
@ kSingleKey
write collection with single key
Definition TObject.h:97
virtual void Browse(TBrowser *b)
Browse object. May be overridden for another default action.
Definition TObject.cxx:217
virtual void Streamer(TBuffer &)
Stream an object of class TObject.
Definition TObject.cxx:972
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:1133
virtual Int_t Write(const char *name=nullptr, Int_t option=0, Int_t bufsize=0)
Write this object to the current directory.
Definition TObject.cxx:964
void SetBit(UInt_t f, Bool_t set)
Set or unset the user status bits as specified in f.
Definition TObject.cxx:864
virtual void Print(Option_t *option="") const
This method must be overridden when a class wants to print itself.
Definition TObject.cxx:655
void ResetBit(UInt_t f)
Definition TObject.h:201
Class used by TMap to store (key,value) pairs.
Definition TMap.h:102
void Browse(TBrowser *b) override
Browse the pair.
Definition TMap.cxx:452
TObject * fValue
Definition TMap.h:106
TObject * fKey
Definition TMap.h:105
virtual ~TPair()
TPair destructor.
Definition TMap.cxx:443
TObject * Key() const
Definition TMap.h:120
static void IndentLevel()
Functions used by ls() to indent an object hierarchy.
Definition TROOT.cxx:2898
virtual void Streamer(TBuffer &)
Stream a string object.
Definition TString.cxx:1418
void CallRecursiveRemoveIfNeeded(TObject &obj)
call RecursiveRemove for obj if gROOT is valid and obj.TestBit(kMustCleanup) is true.
Definition TROOT.h:400
TMarker m
Definition textangle.C:8