Logo ROOT   6.10/09
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 
48 template<class T>
50 
51 private:
52 
53  // We keep the corrected size of T
54  int sizeof_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
60  bool notempty;
61  } *index;
62 
63  // the number of holes inside rawdata
64  // each hole is sizeof_t bytes
65  int holecount;
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;
97  maxsize = capacity = mincap;
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
103  void DestroyElem(myindex *el) {
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 
140 public:
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)
278  BufRealloc(size);
279 
280  }
281 
283  T r( At(size-1) );
284 
285  DestroyElem(index+size-1);
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
320 template <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
XrdClientVector(XrdClientVector &v)
double T(double x)
Definition: ChebyshevPol.h:34
void Resize(int newsize)
#define malloc
Definition: civetweb.c:818
void DestroyElem(myindex *el)
int BufRealloc(int newsize)
int GetSize() const
XrdClientVector(int cap=-1)
#define realloc
Definition: civetweb.c:820
#define IDXVEC_MINCAPACITY
TRandom2 r(17)
SVector< double, 2 > v
Definition: Dict.h:5
void Erase(unsigned int pos, bool dontrealloc=true)
void Insert(T &item, int pos)
T & operator[](int pos)
#define free
Definition: civetweb.c:821
void Push_back(T &item)
void Init(int cap=-1)
struct XrdClientVector::myindex * index
void put(T &item, long pos)