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 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 // // Inserts an item in the given position 00188 // void Insert(T& item, int pos) { 00189 00190 // if (pos >= size) { 00191 // Push_back(item); 00192 // return; 00193 // } 00194 00195 // if ( BufRealloc(size+1) ) { 00196 00197 // memmove(&index[pos+1], &index[pos], (size+holecount-pos) * sizeof(myindex)); 00198 // index[pos].notempty = false; 00199 // size++; 00200 // put(item, pos); 00201 // } 00202 00203 // } 00204 00205 00206 // Inserts an item in the given position 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 // // Removes a single element in position pos 00232 // void Erase(unsigned int pos, bool dontrealloc=true) { 00233 // // We make the position empty, then move the free index to the end 00234 // DestroyElem(index + pos); 00235 00236 // index[size+holecount] = index[pos]; 00237 // holecount++; 00238 00239 // memmove(&index[pos], &index[pos+1], (size+holecount-pos) * sizeof(myindex)); 00240 00241 // size--; 00242 00243 // if (!dontrealloc) 00244 // BufRealloc(size); 00245 00246 // } 00247 00248 // Removes a single element in position pos 00249 void Erase(unsigned int pos, bool dontrealloc=true) { 00250 // We make the position empty, then move the free index to the end of the full items 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 //BufRealloc(size); 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 // Bounded array like access 00287 inline T &At(int pos) { 00288 // if ( (pos < 0) || (pos >= size) ) 00289 // abort(); 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 // Completely packs rawdata if needed 00302 // Eventually adjusts the sizes in order to fit newsize elements 00303 template <class T> 00304 int XrdClientVector<T>::BufRealloc(int newsize) { 00305 00306 // If for some reason we have too many holes, we repack everything 00307 // this is very heavy!! 00308 if ((size+holecount >= capacity-2) && (holecount > 4*size)) 00309 while (size+holecount >= capacity-2) { 00310 long lastempty = size+holecount-1; // The first hole to fill 00311 00312 // Pack everything in rawdata 00313 // Keep the pointers updated 00314 00315 // Do the trick 00316 00317 // Move the last filled to the first encountered hole 00318 memmove(rawdata + index[lastempty].offs, rawdata + index[lastempty].offs + sizeof_t, 00319 (size+holecount)*sizeof_t - index[lastempty].offs ); 00320 00321 // Drop the index 00322 index[lastempty].notempty = false; 00323 holecount--; 00324 00325 // Adjust all the pointers to the subsequent chunks 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 // Too near to the end? 00336 // double the capacity 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 // Too near to the beginning? 00353 // half the capacity 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