00001 #ifndef XRD_CLIIDXVEC_H
00002 #define XRD_CLIIDXVEC_H
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00031
00032
00033
00034
00035
00036
00037
00038
00040
00041 #include <stdlib.h>
00042 #include <string.h>
00043
00044 #include "XrdSys/XrdSysHeaders.hh"
00045
00046 #define IDXVEC_MINCAPACITY 128
00047
00048 template<class T>
00049 class XrdClientVector {
00050
00051 private:
00052
00053
00054 int sizeof_t;
00055
00056 char *rawdata;
00057
00058 struct myindex {
00059 long offs;
00060 bool notempty;
00061 } *index;
00062
00063
00064
00065 int holecount;
00066
00067 long size, mincap;
00068 long capacity, maxsize;
00069
00070
00071
00072
00073 int BufRealloc(int newsize);
00074
00075 inline void Init(int cap = -1) {
00076 if (rawdata) free(rawdata);
00077 if (index) free(index);
00078
00079 mincap = (cap > 0) ? cap : IDXVEC_MINCAPACITY;
00080
00081 rawdata = static_cast<char *>(malloc(mincap * sizeof_t));
00082
00083 index = static_cast<myindex *>(malloc(mincap * sizeof(myindex)));
00084
00085 if (!rawdata || !index) {
00086 std::cerr << "XrdClientIdxVector::Init .... out of memory. sizeof_t=" << sizeof_t <<
00087 " sizeof(myindex)=" << sizeof(myindex) << " capacity=" << mincap << std::endl;
00088 abort();
00089 }
00090
00091
00092 memset(index, 0, mincap * sizeof(myindex));
00093
00094 holecount = 0;
00095
00096 size = 0;
00097 maxsize = capacity = mincap;
00098 }
00099
00100
00101
00102
00103 void DestroyElem(myindex *el) {
00104 reinterpret_cast<T*>(rawdata+el->offs)->~T();
00105
00106 }
00107
00108 void put(T& item, long pos) {
00109
00110
00111
00112 if (size+holecount >= capacity) {
00113 std::cerr << "XrdClientIdxVector::put .... internal error." << std::endl;
00114 abort();
00115 }
00116
00117 T *p;
00118 long offs = (size+holecount)*sizeof_t;
00119
00120 if (index[pos].notempty) {
00121 offs = index[pos].offs;
00122
00123
00124 holecount--;
00125 }
00126
00127 p = new(rawdata + offs) T(item);
00128
00129 if (p) {
00130 index[pos].offs = offs;
00131 index[pos].notempty = true;
00132 }
00133 else {
00134 std::cerr << "XrdClientIdxVector::put .... out of memory." << std::endl;
00135 abort();
00136 }
00137
00138 }
00139
00140 public:
00141
00142 inline int GetSize() const { return size; }
00143
00144 void Clear() {
00145 for (long i = 0; i < size; i++)
00146 if (index[i].notempty) DestroyElem(&index[i]);
00147
00148 Init(mincap);
00149 }
00150
00151 XrdClientVector(int cap = -1):
00152 sizeof_t(0), rawdata(0), index(0)
00153 {
00154
00155 sizeof_t = (sizeof(T) + 3) >> 2 << 2;
00156 Init(cap);
00157 }
00158
00159 XrdClientVector(XrdClientVector &v):
00160 rawdata(0), index(0) {
00161
00162 sizeof_t = (sizeof(T) + 3) >> 2 << 2;
00163
00164 Init(v.capacity);
00165 BufRealloc(v.size);
00166
00167 for (int i = 0; i < v.size; i++)
00168 Push_back( v[i] );
00169 }
00170
00171 ~XrdClientVector() {
00172 for (long i = 0; i < size; i++)
00173 if (index[i].notempty) DestroyElem(&index[i]);
00174
00175 if (rawdata) free(rawdata);
00176 if (index) free(index);
00177 }
00178
00179 void Resize(int newsize) {
00180 long oldsize = size;
00181
00182 if (newsize > oldsize) {
00183 BufRealloc(newsize);
00184 T *item = new T;
00185
00186 for (long i = oldsize; i < newsize; i++) {
00187 put(*item, size++);
00188 }
00189 delete item;
00190 }
00191 else {
00192 for (long i = oldsize; i > newsize; i--)
00193 Erase(i-1, false);
00194 }
00195 }
00196
00197 void Push_back(T& item) {
00198
00199 if ( BufRealloc(size+1) )
00200 put(item, size++);
00201
00202 }
00203
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224 void Insert(T& item, int pos) {
00225
00226 if (pos >= size) {
00227 Push_back(item);
00228 return;
00229 }
00230
00231 if ( BufRealloc(size+1) ) {
00232
00233 if (holecount > 0) {
00234 struct myindex tmpi = index[size];
00235 memmove(&index[pos+1], &index[pos], (size-pos) * sizeof(myindex));
00236 index[pos] = tmpi;
00237 } else {
00238 memmove(&index[pos+1], &index[pos], (size-pos) * sizeof(myindex));
00239 index[pos].notempty = false;
00240 }
00241
00242 size++;
00243 put(item, pos);
00244 }
00245
00246 }
00247
00248
00249
00250
00251
00252
00253
00254
00255
00256
00257
00258
00259
00260
00261
00262
00263
00264
00265
00266 void Erase(unsigned int pos, bool dontrealloc=true) {
00267
00268 DestroyElem(index + pos);
00269
00270 struct myindex tmpi = index[pos];
00271 holecount++;
00272
00273 memmove(&index[pos], &index[pos+1], (size-pos-1) * sizeof(myindex));
00274
00275 size--;
00276 index[size] = tmpi;
00277 if (!dontrealloc)
00278 BufRealloc(size);
00279
00280 }
00281
00282 T Pop_back() {
00283 T r( At(size-1) );
00284
00285 DestroyElem(index+size-1);
00286
00287 holecount++;
00288 size--;
00289
00290
00291 return (r);
00292 }
00293
00294 T Pop_front() {
00295 T res;
00296
00297 res = At(0);
00298
00299 Erase(0);
00300 return (res);
00301 }
00302
00303
00304 inline T &At(int pos) {
00305 if ((pos < 0) || (static_cast<unsigned long>(pos) >=
00306 static_cast<unsigned long>(size))) abort();
00307
00308 return *( reinterpret_cast<T*>(rawdata + index[pos].offs));
00309 }
00310
00311 inline T &operator[] (int pos) {
00312 return At(pos);
00313 }
00314
00315 };
00316
00317
00318
00319
00320 template <class T>
00321 int XrdClientVector<T>::BufRealloc(int newsize) {
00322
00323
00324
00325 if ((size+holecount >= capacity-2) && (holecount > 4*size))
00326 while (size+holecount >= capacity-2) {
00327 long lastempty = size+holecount-1;
00328
00329
00330
00331
00332
00333
00334
00335 memmove(rawdata + index[lastempty].offs, rawdata + index[lastempty].offs + sizeof_t,
00336 (size+holecount)*sizeof_t - index[lastempty].offs );
00337
00338
00339 index[lastempty].notempty = false;
00340 holecount--;
00341
00342
00343 for (long i = 0; i < size+holecount; i++)
00344 if (index[i].notempty && (index[i].offs > index[lastempty].offs))
00345 index[i].offs -= sizeof_t;
00346
00347 }
00348
00349 if (newsize > maxsize) maxsize = newsize;
00350
00351 while (newsize+holecount > capacity*2/3) {
00352
00353
00354
00355 capacity *= 2;
00356
00357 rawdata = static_cast<char *>(realloc(rawdata, capacity*sizeof_t));
00358 if (!rawdata) {
00359 std::cerr << "XrdClientIdxVector::BufRealloc .... out of memory." << std::endl;
00360 abort();
00361 }
00362
00363 index = static_cast<myindex *>(realloc(index, capacity*sizeof(myindex)));
00364 memset(index+capacity/2, 0, capacity*sizeof(myindex)/2);
00365
00366 }
00367
00368 while ((newsize+holecount < capacity/3) && (capacity > 2*mincap)) {
00369
00370
00371
00372
00373 capacity /= 2;
00374
00375 rawdata = static_cast<char *>(realloc(rawdata, capacity*sizeof_t));
00376 if (!rawdata) {
00377 std::cerr << "XrdClientIdxVector::BufRealloc .... out of memory." << std::endl;
00378 abort();
00379 }
00380
00381 index = static_cast<myindex *>(realloc(index, capacity*sizeof(myindex)));
00382
00383 }
00384
00385 return 1;
00386
00387 }
00388 #endif