xrootd
|
00001 00002 // // 00003 // XrdClientIdxVector // 00004 // // 00005 // Author: Fabrizio Furano (INFN Padova, 2006) // 00006 // // 00007 // A vector class optimized for insertions and deletions // 00008 // indexed access takes O(1) // 00009 // insertion takes O(1) plus a very small fraction of O(n) // 00010 // deletion takes O(1) plus a very small fraction of O(n) // 00011 // // 00012 // Better suited than XrdClientVector to hold complex objects // 00013 // // 00015 00016 // $Id$ 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 // We keep the corrected size of T 00037 int sizeof_t; 00038 00039 char *rawdata; // A raw mem block to hold (casted) T instances 00040 00041 struct myindex { 00042 long offs; // Offset to a T inside rawdata 00043 bool notempty; 00044 } *index; 00045 00046 // the number of holes inside rawdata 00047 // each hole is sizeof_t bytes 00048 int holecount; 00049 00050 long size, mincap; 00051 long capacity, maxsize; 00052 00053 // Completely packs rawdata 00054 // Eventually adjusts the sizes in order to contain at least 00055 // newsize elements 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 // and we make every item as empty, i.e. not pointing to anything 00075 memset(index, 0, mincap * sizeof(myindex)); 00076 00077 holecount = 0; 00078 00079 size = 0; 00080 maxsize = capacity = mincap; 00081 } 00082 00083 // Makes a null position... not to be exposed 00084 // Because after this the element pointed to by el becomes invalid 00085 // Typically el will be moved at the end, at the size+holecount position 00086 void DestroyElem(myindex *el) { 00087 reinterpret_cast<T*>(rawdata+el->offs)->~T(); 00088 // el->notempty = false; 00089 } 00090 00091 void put(T& item, long pos) { 00092 // Puts an element in position pos 00093 // Hence write at pos in the index array 00094 // Use a new chunk of rawdata if the item does not point to a chunk 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 // did we fill a hole? 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 // We calculate a size which is aligned on 4-bytes 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 // Add new elements if needed 00169 for (long i = oldsize; i < newsize; i++) { 00170 put(*item, size++); 00171 } 00172 } 00173 else { 00174 for (long i = oldsize; i > newsize; i--) 00175 Erase(i-1, false); 00176 } 00177 } 00178 00179 void Push_back(T& item) { 00180 00181 if ( BufRealloc(size+1) ) 00182 put(item, size++); 00183 00184 } 00185 00186 // // Inserts an item in the given position 00187 // void Insert(T& item, int pos) { 00188 00189 // if (pos >= size) { 00190 // Push_back(item); 00191 // return; 00192 // } 00193 00194 // if ( BufRealloc(size+1) ) { 00195 00196 // memmove(&index[pos+1], &index[pos], (size+holecount-pos) * sizeof(myindex)); 00197 // index[pos].notempty = false; 00198 // size++; 00199 // put(item, pos); 00200 // } 00201 00202 // } 00203 00204 00205 // Inserts an item in the given position 00206 void Insert(T& item, int pos) { 00207 00208 if (pos >= size) { 00209 Push_back(item); 00210 return; 00211 } 00212 00213 if ( BufRealloc(size+1) ) { 00214 00215 if (holecount > 0) { 00216 struct myindex tmpi = index[size]; 00217 memmove(&index[pos+1], &index[pos], (size-pos) * sizeof(myindex)); 00218 index[pos] = tmpi; 00219 } else { 00220 memmove(&index[pos+1], &index[pos], (size-pos) * sizeof(myindex)); 00221 index[pos].notempty = false; 00222 } 00223 00224 size++; 00225 put(item, pos); 00226 } 00227 00228 } 00229 00230 // // Removes a single element in position pos 00231 // void Erase(unsigned int pos, bool dontrealloc=true) { 00232 // // We make the position empty, then move the free index to the end 00233 // DestroyElem(index + pos); 00234 00235 // index[size+holecount] = index[pos]; 00236 // holecount++; 00237 00238 // memmove(&index[pos], &index[pos+1], (size+holecount-pos) * sizeof(myindex)); 00239 00240 // size--; 00241 00242 // if (!dontrealloc) 00243 // BufRealloc(size); 00244 00245 // } 00246 00247 // Removes a single element in position pos 00248 void Erase(unsigned int pos, bool dontrealloc=true) { 00249 // We make the position empty, then move the free index to the end of the full items 00250 DestroyElem(index + pos); 00251 00252 struct myindex tmpi = index[pos]; 00253 holecount++; 00254 00255 memmove(&index[pos], &index[pos+1], (size-pos-1) * sizeof(myindex)); 00256 00257 size--; 00258 index[size] = tmpi; 00259 if (!dontrealloc) 00260 BufRealloc(size); 00261 00262 } 00263 00264 T Pop_back() { 00265 T r( At(size-1) ); 00266 00267 DestroyElem(index+size-1); 00268 00269 holecount++; 00270 size--; 00271 //BufRealloc(size); 00272 00273 return (r); 00274 } 00275 00276 T Pop_front() { 00277 T res; 00278 00279 res = At(0); 00280 00281 Erase(0); 00282 return (res); 00283 } 00284 00285 // Bounded array like access 00286 inline T &At(int pos) { 00287 // if ( (pos < 0) || (pos >= size) ) 00288 // abort(); 00289 00290 return *( reinterpret_cast<T*>(rawdata + index[pos].offs)); 00291 } 00292 00293 inline T &operator[] (int pos) { 00294 return At(pos); 00295 } 00296 00297 }; 00298 00299 00300 // Completely packs rawdata if needed 00301 // Eventually adjusts the sizes in order to fit newsize elements 00302 template <class T> 00303 int XrdClientVector<T>::BufRealloc(int newsize) { 00304 00305 // If for some reason we have too many holes, we repack everything 00306 // this is very heavy!! 00307 if ((size+holecount >= capacity-2) && (holecount > 4*size)) 00308 while (size+holecount >= capacity-2) { 00309 long lastempty = size+holecount-1; // The first hole to fill 00310 00311 // Pack everything in rawdata 00312 // Keep the pointers updated 00313 00314 // Do the trick 00315 00316 // Move the last filled to the first encountered hole 00317 memmove(rawdata + index[lastempty].offs, rawdata + index[lastempty].offs + sizeof_t, 00318 (size+holecount)*sizeof_t - index[lastempty].offs ); 00319 00320 // Drop the index 00321 index[lastempty].notempty = false; 00322 holecount--; 00323 00324 // Adjust all the pointers to the subsequent chunks 00325 for (long i = 0; i < size+holecount; i++) 00326 if (index[i].notempty && (index[i].offs > index[lastempty].offs)) 00327 index[i].offs -= sizeof_t; 00328 00329 } 00330 00331 if (newsize > maxsize) maxsize = newsize; 00332 00333 while (newsize+holecount > capacity*2/3) { 00334 // Too near to the end? 00335 // double the capacity 00336 00337 capacity *= 2; 00338 00339 rawdata = static_cast<char *>(realloc(rawdata, capacity*sizeof_t)); 00340 if (!rawdata) { 00341 std::cerr << "XrdClientIdxVector::BufRealloc .... out of memory." << std::endl; 00342 abort(); 00343 } 00344 00345 index = static_cast<myindex *>(realloc(index, capacity*sizeof(myindex))); 00346 memset(index+capacity/2, 0, capacity*sizeof(myindex)/2); 00347 00348 } 00349 00350 while ((newsize+holecount < capacity/3) && (capacity > 2*mincap)) { 00351 // Too near to the beginning? 00352 // half the capacity 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 00365 } 00366 00367 return 1; 00368 00369 } 00370 00371 00372 #endif