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
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
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
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 nullptr;
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 nullptr;
241}
242
243////////////////////////////////////////////////////////////////////////////////
244/// Returns a pointer to the value associated with key.
245
247{
248 if (IsArgNull("GetValue", key)) return nullptr;
249
250 TPair *a = (TPair *)fTable->FindObject(key);
251 if (a) return a->Value();
252 return nullptr;
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
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 nullptr;
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 nullptr;
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 nullptr;
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 nullptr;
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
362{
363 TObject *obj = nullptr;
364 UInt_t R__s, R__c;
365
366 if (b.IsReading()) {
367 Int_t nobjects;
368 TObject *value = nullptr;
369
370 Version_t v = b.ReadVersion(&R__s, &R__c);
371 if (v > 2)
373 if (v > 1)
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);
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
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 = nullptr;
478}
479
480////////////////////////////////////////////////////////////////////////////////
481/// Copy ctor.
482
484{
485 fMap = iter.fMap;
486 fDirection = iter.fDirection;
487 fCursor = nullptr;
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 nullptr;
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}
#define SafeDelete(p)
Definition RConfig.hxx:542
#define b(i)
Definition RSha256.hxx:100
#define a(i)
Definition RSha256.hxx:99
short Version_t
Definition RtypesCore.h:65
float Float_t
Definition RtypesCore.h:57
constexpr Bool_t kFALSE
Definition RtypesCore.h:101
constexpr Bool_t kTRUE
Definition RtypesCore.h:100
const char Option_t
Definition RtypesCore.h:66
#define ClassImp(name)
Definition Rtypes.h:377
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
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
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
void Print(Option_t *option="") const override
Default print for collections, calls Print(option, 1).
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
virtual TClass * IsA() const
Definition TIterator.h:48
Iterator of map.
Definition TMap.h:144
TObject * operator*() const override
Return pointer to current object (a TPair) or nullptr.
Definition TMap.cxx:583
TObject * Next() override
Returns the next key from a map.
Definition TMap.cxx:542
THashTableIter * fCursor
Definition TMap.h:148
~TMapIter()
Map iterator dtor.
Definition TMap.cxx:533
Bool_t operator!=(const TIterator &aIter) const override
This operator compares two TIterator objects.
Definition TMap.cxx:563
const TMap * fMap
Definition TMap.h:147
static TClass * Class()
void Reset() override
Reset the map iterator.
Definition TMap.cxx:555
Bool_t fDirection
Definition TMap.h:149
TMapIter()
Definition TMap.h:151
TIterator & operator=(const TIterator &rhs) override
Overridden assignment operator.
Definition TMap.cxx:498
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
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
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:134
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
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:54
virtual void SetOwnerKeyValue(Bool_t ownkeys=kTRUE, Bool_t ownvals=kTRUE)
Set ownership for keys and values.
Definition TMap.cxx:352
TObject * FindObject(const char *keyname) const override
Check if a (key,value) pair exists with keyname as name of the key.
Definition TMap.cxx:215
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:266
Float_t AverageCollisions() const
Return the ratio of entries vs occupied slots.
Definition TMap.cxx:73
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:432
TObject * Remove(TObject *key) override
Remove the (key,value) pair with key from the map.
Definition TMap.cxx:296
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
void Clear(Option_t *option="") override
Remove all (key,value) pairs from the map.
Definition TMap.cxx:97
TIterator * MakeIterator(Bool_t dir=kIterForward) const override
Create an iterator for TMap.
Definition TMap.cxx:258
@ 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:361
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: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
TMap(const TMap &map)=delete
void Rehash(Int_t newCapacity, Bool_t checkObjValidity=kTRUE)
Rehash the underlaying THashTable (see THashTable::Rehash()).
Definition TMap.cxx:286
Mother of all ROOT objects.
Definition TObject.h:41
@ kSingleKey
write collection with single key
Definition TObject.h:91
virtual void Browse(TBrowser *b)
Browse object. May be overridden for another default action.
Definition TObject.cxx:198
virtual void Streamer(TBuffer &)
Stream an object of class TObject.
Definition TObject.cxx:888
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:1029
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:880
void SetBit(UInt_t f, Bool_t set)
Set or unset the user status bits as specified in f.
Definition TObject.cxx:780
virtual void Print(Option_t *option="") const
This method must be overridden when a class wants to print itself.
Definition TObject.cxx:636
void ResetBit(UInt_t f)
Definition TObject.h:200
Class used by TMap to store (key,value) pairs.
Definition TMap.h:102
void Browse(TBrowser *b) override
Browse the pair.
Definition TMap.cxx:453
TObject * fValue
Definition TMap.h:106
TObject * fKey
Definition TMap.h:105
virtual ~TPair()
TPair destructor.
Definition TMap.cxx:444
TObject * Key() const
Definition TMap.h:120
static void IndentLevel()
Functions used by ls() to indent an object hierarchy.
Definition TROOT.cxx:2844
virtual void Streamer(TBuffer &)
Stream a string object.
Definition TString.cxx:1412
void CallRecursiveRemoveIfNeeded(TObject &obj)
call RecursiveRemove for obj if gROOT is valid and obj.TestBit(kMustCleanup) is true.
Definition TROOT.h:395
TMarker m
Definition textangle.C:8