ROOT  6.06/09
Reference Guide
TFree.cxx
Go to the documentation of this file.
1 // @(#)root/io:$Id$
2 // Author: Rene Brun 28/12/94
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 #include "TFree.h"
13 #include "TList.h"
14 #include "TFile.h"
15 #include "Bytes.h"
16 #include "Riostream.h"
17 
19 
20 /**
21 \class TFree
22 \ingroup IO
23 Service class for TFile.
24 
25 Each file has a linked list of free segments. Each free segment is described
26 by its firts and last address.
27 When an object is written to a file, a new Key (see TKey)
28 is created. The first free segment big enough to accomodate the object
29 is used.
30 If the object size has a length corresponding to the size of the free segment,
31 the free segment is deleted from the list of free segments.
32 When an object is deleted from a file, a new TFree object is generated.
33 If the deleted object is contiguous to an already deleted object, the free
34 segments are merged in one single segment.
35 */
36 
37 ////////////////////////////////////////////////////////////////////////////////
38 /// Default constructor.
39 
40 TFree::TFree()
41 {
42  fFirst = fLast = 0;
43 }
44 
45 ////////////////////////////////////////////////////////////////////////////////
46 /// Constructor for a free segment.
47 
48 TFree::TFree(TList *lfree, Long64_t first, Long64_t last)
49 {
50  fFirst = first;
51  fLast = last;
52  lfree->Add(this);
53 }
54 
55 ////////////////////////////////////////////////////////////////////////////////
56 /// Add a new free segment to the list of free segments.
57 ///
58 /// - if last just precedes an existing free segment, then first becomes
59 /// the new starting location of the free segment.
60 /// - if first just follows an existing free segment, then last becomes
61 /// the new ending location of the free segment.
62 /// - if first just follows an existing free segment AND last just precedes
63 /// an existing free segment, these two segments are merged into
64 /// one single segment.
65 ///
66 
68 {
69  TFree *idcur = this;
70  while (idcur) {
71  Long64_t curfirst = idcur->GetFirst();
72  Long64_t curlast = idcur->GetLast();
73  if (curlast == first-1) {
74  idcur->SetLast(last);
75  TFree *idnext = (TFree*)lfree->After(idcur);
76  if (idnext == 0) return idcur;
77  if (idnext->GetFirst() > last+1) return idcur;
78  idcur->SetLast( idnext->GetLast() );
79  lfree->Remove(idnext);
80  delete idnext;
81  return idcur;
82  }
83  if (curfirst == last+1) {
84  idcur->SetFirst(first);
85  return idcur;
86  }
87  if (first < curfirst) {
88  TFree * newfree = new TFree();
89  newfree->SetFirst(first);
90  newfree->SetLast(last);
91  lfree->AddBefore(idcur, newfree);
92  return newfree;
93  }
94  idcur = (TFree*)lfree->After(idcur);
95  }
96  return 0;
97 }
98 
99 ////////////////////////////////////////////////////////////////////////////////
100 /// Destructor.
101 
103 {
104 }
105 
106 ////////////////////////////////////////////////////////////////////////////////
107 /// Encode fre structure into output buffer.
108 
109 void TFree::FillBuffer(char *&buffer)
110 {
111  Version_t version = TFree::Class_Version();
112  if (fLast > TFile::kStartBigFile) version += 1000;
113  tobuf(buffer, version);
114 //printf("TFree::fillBuffer, fFirst=%lld, fLast=%lld, version=%d\n",fFirst,fLast,version);
115  if (version > 1000) {
116  tobuf(buffer, fFirst);
117  tobuf(buffer, fLast);
118  } else {
119  tobuf(buffer, (Int_t)fFirst);
120  tobuf(buffer, (Int_t)fLast);
121  }
122 }
123 
124 ////////////////////////////////////////////////////////////////////////////////
125 /// Return the best free segment where to store nbytes.
126 
128 {
129  TFree *idcur = this;
130  if (idcur == 0) return 0;
131  TFree *idcur1 = 0;
132  do {
133  Long64_t nleft = Long64_t(idcur->fLast - idcur->fFirst +1);
134  if (nleft == nbytes) {
135  // Found an exact match
136  return idcur;
137  }
138  if(nleft > (Long64_t)(nbytes+3)) {
139  if (idcur1 == 0) {
140  idcur1=idcur;
141  }
142  }
143  idcur = (TFree*)lfree->After(idcur);
144  } while (idcur !=0);
145 
146  // return first segment >nbytes
147  if (idcur1) return idcur1;
148 
149  //try big file
150  idcur = (TFree*)lfree->Last();
151  Long64_t last = idcur->fLast+1000000000;
152  idcur->SetLast(last);
153  return idcur;
154 }
155 
156 ////////////////////////////////////////////////////////////////////////////////
157 /// List free segment contents.
158 
159 void TFree::ls(Option_t *) const
160 {
161  std::cout <<"Free Segment: "<<fFirst<<"\t"<<fLast<<std::endl;
162 }
163 
164 ////////////////////////////////////////////////////////////////////////////////
165 /// Decode one free structure from input buffer
166 
167 void TFree::ReadBuffer(char *&buffer)
168 {
169  Version_t version;
170  frombuf(buffer, &version);
171  if (version > 1000) {
172  frombuf(buffer, &fFirst);
173  frombuf(buffer, &fLast);
174  } else {
175  Int_t first,last;
176  frombuf(buffer, &first); fFirst = (Long64_t)first;
177  frombuf(buffer, &last); fLast = (Long64_t)last;
178  }
179 }
180 
181 ////////////////////////////////////////////////////////////////////////////////
182 /// return number of bytes occupied by this TFree on permanent storage
183 
185 {
186  if (fLast > TFile::kStartBigFile) return 18;
187  else return 10;
188 }
189 
void frombuf(char *&buf, Bool_t *x)
Definition: Bytes.h:282
Long64_t fFirst
First free word of segment.
Definition: TFree.h:32
long long Long64_t
Definition: RtypesCore.h:69
short Version_t
Definition: RtypesCore.h:61
const char Option_t
Definition: RtypesCore.h:62
int Int_t
Definition: RtypesCore.h:41
void ls(Option_t *) const
List free segment contents.
Definition: TFree.cxx:159
Int_t Sizeof() const
return number of bytes occupied by this TFree on permanent storage
Definition: TFree.cxx:184
void SetLast(Long64_t last)
Definition: TFree.h:47
virtual void FillBuffer(char *&buffer)
Encode fre structure into output buffer.
Definition: TFree.cxx:109
TFree * AddFree(TList *lfree, Long64_t first, Long64_t last)
Add a new free segment to the list of free segments.
Definition: TFree.cxx:67
virtual TObject * After(const TObject *obj) const
Returns the object after object obj.
Definition: TList.cxx:288
Service class for TFile.
Definition: TFree.h:29
void tobuf(char *&buf, Bool_t x)
Definition: Bytes.h:59
Long64_t fLast
Last free word of segment.
Definition: TFree.h:33
A doubly linked list.
Definition: TList.h:47
Long64_t GetLast() const
Definition: TFree.h:43
virtual TObject * Remove(TObject *obj)
Remove object from the list.
Definition: TList.cxx:674
virtual void AddBefore(const TObject *before, TObject *obj)
Insert object before object before in the list.
Definition: TList.cxx:172
virtual void ReadBuffer(char *&buffer)
Decode one free structure from input buffer.
Definition: TFree.cxx:167
virtual TObject * Last() const
Return the last object in the list. Returns 0 when list is empty.
Definition: TList.cxx:580
void SetFirst(Long64_t first)
Definition: TFree.h:46
#define ClassImp(name)
Definition: Rtypes.h:279
Long64_t GetFirst() const
Definition: TFree.h:42
virtual ~TFree()
Destructor.
Definition: TFree.cxx:102
TFree * GetBestFree(TList *lfree, Int_t nbytes)
Return the best free segment where to store nbytes.
Definition: TFree.cxx:127
virtual void Add(TObject *obj)
Definition: TList.h:81
T1 fFirst
Definition: X11Events.mm:85