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