xrootd
XrdClientVector.hh
Go to the documentation of this file.
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