Logo ROOT  
Reference Guide
XrdClientVector.hh
Go to the documentation of this file.
1#ifndef XRD_CLIIDXVEC_H
2#define XRD_CLIIDXVEC_H
3/******************************************************************************/
4/* */
5/* X r d C l i e n t V e c t o r . h h */
6/* */
7/* Author: Fabrizio Furano (INFN Padova, 2006) */
8/* */
9/* This file is part of the XRootD software suite. */
10/* */
11/* XRootD is free software: you can redistribute it and/or modify it under */
12/* the terms of the GNU Lesser General Public License as published by the */
13/* Free Software Foundation, either version 3 of the License, or (at your */
14/* option) any later version. */
15/* */
16/* XRootD is distributed in the hope that it will be useful, but WITHOUT */
17/* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or */
18/* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public */
19/* License for more details. */
20/* */
21/* You should have received a copy of the GNU Lesser General Public License */
22/* along with XRootD in a file called COPYING.LESSER (LGPL license) and file */
23/* COPYING (GPL license). If not, see <http://www.gnu.org/licenses/>. */
24/* */
25/* The copyright holder's institutional names and contributor's names may not */
26/* be used to endorse or promote products derived from this software without */
27/* specific prior written permission of the institution or contributor. */
28/******************************************************************************/
29
30//////////////////////////////////////////////////////////////////////////
31// //
32// A vector class optimized for insertions and deletions //
33// indexed access takes O(1) //
34// insertion takes O(1) plus a very small fraction of O(n) //
35// deletion takes O(1) plus a very small fraction of O(n) //
36// //
37// Better suited than XrdClientVector to hold complex objects //
38// //
39//////////////////////////////////////////////////////////////////////////
40
41#include <stdlib.h>
42#include <string.h>
43
44#include "XrdSys/XrdSysHeaders.hh"
45
46#define IDXVEC_MINCAPACITY 128
47
48template<class T>
50
51private:
52
53 // We keep the corrected size of T
55
56 char *rawdata; // A raw mem block to hold (casted) T instances
57
58 struct myindex {
59 long offs; // Offset to a T inside rawdata
62
63 // the number of holes inside rawdata
64 // each hole is sizeof_t bytes
66
67 long size, mincap;
69
70 // Completely packs rawdata
71 // Eventually adjusts the sizes in order to contain at least
72 // newsize elements
73 int BufRealloc(int newsize);
74
75 inline void Init(int cap = -1) {
76 if (rawdata) free(rawdata);
77 if (index) free(index);
78
79 mincap = (cap > 0) ? cap : IDXVEC_MINCAPACITY;
80
81 rawdata = static_cast<char *>(malloc(mincap * sizeof_t));
82
83 index = static_cast<myindex *>(malloc(mincap * sizeof(myindex)));
84
85 if (!rawdata || !index) {
86 std::cerr << "XrdClientIdxVector::Init .... out of memory. sizeof_t=" << sizeof_t <<
87 " sizeof(myindex)=" << sizeof(myindex) << " capacity=" << mincap << std::endl;
88 abort();
89 }
90
91 // and we make every item as empty, i.e. not pointing to anything
92 memset(index, 0, mincap * sizeof(myindex));
93
94 holecount = 0;
95
96 size = 0;
98 }
99
100 // Makes a null position... not to be exposed
101 // Because after this the element pointed to by el becomes invalid
102 // Typically el will be moved at the end, at the size+holecount position
104 reinterpret_cast<T*>(rawdata+el->offs)->~T();
105 // el->notempty = false;
106 }
107
108 void put(T& item, long pos) {
109 // Puts an element in position pos
110 // Hence write at pos in the index array
111 // Use a new chunk of rawdata if the item does not point to a chunk
112 if (size+holecount >= capacity) {
113 std::cerr << "XrdClientIdxVector::put .... internal error." << std::endl;
114 abort();
115 }
116
117 T *p;
118 long offs = (size+holecount)*sizeof_t;
119
120 if (index[pos].notempty) {
121 offs = index[pos].offs;
122
123 // did we fill a hole?
124 holecount--;
125 }
126
127 p = new(rawdata + offs) T(item);
128
129 if (p) {
130 index[pos].offs = offs;
131 index[pos].notempty = true;
132 }
133 else {
134 std::cerr << "XrdClientIdxVector::put .... out of memory." << std::endl;
135 abort();
136 }
137
138 }
139
140public:
141
142 inline int GetSize() const { return size; }
143
144 void Clear() {
145 for (long i = 0; i < size; i++)
146 if (index[i].notempty) DestroyElem(&index[i]);
147
148 Init(mincap);
149 }
150
151 XrdClientVector(int cap = -1):
152 sizeof_t(0), rawdata(0), index(0)
153 {
154 // We calculate a size which is aligned on 4-bytes
155 sizeof_t = (sizeof(T) + 3) >> 2 << 2;
156 Init(cap);
157 }
158
160 rawdata(0), index(0) {
161
162 sizeof_t = (sizeof(T) + 3) >> 2 << 2;
163
164 Init(v.capacity);
165 BufRealloc(v.size);
166
167 for (int i = 0; i < v.size; i++)
168 Push_back( v[i] );
169 }
170
172 for (long i = 0; i < size; i++)
173 if (index[i].notempty) DestroyElem(&index[i]);
174
175 if (rawdata) free(rawdata);
176 if (index) free(index);
177 }
178
179 void Resize(int newsize) {
180 long oldsize = size;
181
182 if (newsize > oldsize) {
183 BufRealloc(newsize);
184 T *item = new T;
185 // Add new elements if needed
186 for (long i = oldsize; i < newsize; i++) {
187 put(*item, size++);
188 }
189 delete item;
190 }
191 else {
192 for (long i = oldsize; i > newsize; i--)
193 Erase(i-1, false);
194 }
195 }
196
197 void Push_back(T& item) {
198
199 if ( BufRealloc(size+1) )
200 put(item, size++);
201
202 }
203
204// // Inserts an item in the given position
205// void Insert(T& item, int pos) {
206
207// if (pos >= size) {
208// Push_back(item);
209// return;
210// }
211
212// if ( BufRealloc(size+1) ) {
213
214// memmove(&index[pos+1], &index[pos], (size+holecount-pos) * sizeof(myindex));
215// index[pos].notempty = false;
216// size++;
217// put(item, pos);
218// }
219
220// }
221
222
223 // Inserts an item in the given position
224 void Insert(T& item, int pos) {
225
226 if (pos >= size) {
227 Push_back(item);
228 return;
229 }
230
231 if ( BufRealloc(size+1) ) {
232
233 if (holecount > 0) {
234 struct myindex tmpi = index[size];
235 memmove(&index[pos+1], &index[pos], (size-pos) * sizeof(myindex));
236 index[pos] = tmpi;
237 } else {
238 memmove(&index[pos+1], &index[pos], (size-pos) * sizeof(myindex));
239 index[pos].notempty = false;
240 }
241
242 size++;
243 put(item, pos);
244 }
245
246 }
247
248// // Removes a single element in position pos
249// void Erase(unsigned int pos, bool dontrealloc=true) {
250// // We make the position empty, then move the free index to the end
251// DestroyElem(index + pos);
252
253// index[size+holecount] = index[pos];
254// holecount++;
255
256// memmove(&index[pos], &index[pos+1], (size+holecount-pos) * sizeof(myindex));
257
258// size--;
259
260// if (!dontrealloc)
261// BufRealloc(size);
262
263// }
264
265 // Removes a single element in position pos
266 void Erase(unsigned int pos, bool dontrealloc=true) {
267 // We make the position empty, then move the free index to the end of the full items
268 DestroyElem(index + pos);
269
270 struct myindex tmpi = index[pos];
271 holecount++;
272
273 memmove(&index[pos], &index[pos+1], (size-pos-1) * sizeof(myindex));
274
275 size--;
276 index[size] = tmpi;
277 if (!dontrealloc)
279
280 }
281
283 T r( At(size-1) );
284
286
287 holecount++;
288 size--;
289 //BufRealloc(size);
290
291 return (r);
292 }
293
295 T res;
296
297 res = At(0);
298
299 Erase(0);
300 return (res);
301 }
302
303 // Bounded array like access
304 inline T &At(int pos) {
305 if ((pos < 0) || (static_cast<unsigned long>(pos) >=
306 static_cast<unsigned long>(size))) abort();
307
308 return *( reinterpret_cast<T*>(rawdata + index[pos].offs));
309 }
310
311 inline T &operator[] (int pos) {
312 return At(pos);
313 }
314
315};
316
317
318// Completely packs rawdata if needed
319// Eventually adjusts the sizes in order to fit newsize elements
320template <class T>
322
323 // If for some reason we have too many holes, we repack everything
324 // this is very heavy!!
325 if ((size+holecount >= capacity-2) && (holecount > 4*size))
326 while (size+holecount >= capacity-2) {
327 long lastempty = size+holecount-1; // The first hole to fill
328
329 // Pack everything in rawdata
330 // Keep the pointers updated
331
332 // Do the trick
333
334 // Move the last filled to the first encountered hole
335 memmove(rawdata + index[lastempty].offs, rawdata + index[lastempty].offs + sizeof_t,
336 (size+holecount)*sizeof_t - index[lastempty].offs );
337
338 // Drop the index
339 index[lastempty].notempty = false;
340 holecount--;
341
342 // Adjust all the pointers to the subsequent chunks
343 for (long i = 0; i < size+holecount; i++)
344 if (index[i].notempty && (index[i].offs > index[lastempty].offs))
345 index[i].offs -= sizeof_t;
346
347 }
348
349 if (newsize > maxsize) maxsize = newsize;
350
351 while (newsize+holecount > capacity*2/3) {
352 // Too near to the end?
353 // double the capacity
354
355 capacity *= 2;
356
357 rawdata = static_cast<char *>(realloc(rawdata, capacity*sizeof_t));
358 if (!rawdata) {
359 std::cerr << "XrdClientIdxVector::BufRealloc .... out of memory." << std::endl;
360 abort();
361 }
362
363 index = static_cast<myindex *>(realloc(index, capacity*sizeof(myindex)));
364 memset(index+capacity/2, 0, capacity*sizeof(myindex)/2);
365
366 }
367
368 while ((newsize+holecount < capacity/3) && (capacity > 2*mincap)) {
369 // Too near to the beginning?
370 // half the capacity
371
372
373 capacity /= 2;
374
375 rawdata = static_cast<char *>(realloc(rawdata, capacity*sizeof_t));
376 if (!rawdata) {
377 std::cerr << "XrdClientIdxVector::BufRealloc .... out of memory." << std::endl;
378 abort();
379 }
380
381 index = static_cast<myindex *>(realloc(index, capacity*sizeof(myindex)));
382
383 }
384
385 return 1;
386
387}
388#endif
ROOT::R::TRInterface & r
Definition: Object.C:4
size_t size(const MatrixT &matrix)
retrieve the size of a square matrix
#define IDXVEC_MINCAPACITY
#define realloc
Definition: civetweb.c:1538
#define free
Definition: civetweb.c:1539
#define malloc
Definition: civetweb.c:1536
XrdClientVector(XrdClientVector &v)
void Erase(unsigned int pos, bool dontrealloc=true)
int GetSize() const
void Init(int cap=-1)
void Push_back(T &item)
void put(T &item, long pos)
XrdClientVector(int cap=-1)
void Resize(int newsize)
struct XrdClientVector::myindex * index
T & operator[](int pos)
void DestroyElem(myindex *el)
void Insert(T &item, int pos)
int BufRealloc(int newsize)
double T(double x)
Definition: ChebyshevPol.h:34