XrdClientVector.hh

Go to the documentation of this file.
00001 #ifndef XRD_CLIIDXVEC_H
00002 #define XRD_CLIIDXVEC_H
00003 /******************************************************************************/
00004 /*                                                                            */
00005 /*                  X r d C l i e n t V e c t o r . h h                       */
00006 /*                                                                            */
00007 /* Author: Fabrizio Furano (INFN Padova, 2006)                                */
00008 /*                                                                            */
00009 /* This file is part of the XRootD software suite.                            */
00010 /*                                                                            */
00011 /* XRootD is free software: you can redistribute it and/or modify it under    */
00012 /* the terms of the GNU Lesser General Public License as published by the     */
00013 /* Free Software Foundation, either version 3 of the License, or (at your     */
00014 /* option) any later version.                                                 */
00015 /*                                                                            */
00016 /* XRootD is distributed in the hope that it will be useful, but WITHOUT      */
00017 /* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or      */
00018 /* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public       */
00019 /* License for more details.                                                  */
00020 /*                                                                            */
00021 /* You should have received a copy of the GNU Lesser General Public License   */
00022 /* along with XRootD in a file called COPYING.LESSER (LGPL license) and file  */
00023 /* COPYING (GPL license).  If not, see <http://www.gnu.org/licenses/>.        */
00024 /*                                                                            */
00025 /* The copyright holder's institutional names and contributor's names may not */
00026 /* be used to endorse or promote products derived from this software without  */
00027 /* specific prior written permission of the institution or contributor.       */
00028 /******************************************************************************/
00029 
00031 //                                                                      //
00032 // A vector class optimized for insertions and deletions                //
00033 //   indexed access takes O(1)                                          //
00034 //   insertion takes O(1) plus a very small fraction of O(n)            //
00035 //   deletion takes O(1) plus a very small fraction of O(n)             //
00036 //                                                                      //
00037 // Better suited than XrdClientVector to hold complex objects           //
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     // We keep the corrected size of T
00054     int sizeof_t;
00055 
00056     char *rawdata; // A raw mem block to hold (casted) T instances
00057 
00058     struct myindex {
00059         long offs; // Offset to a T inside rawdata
00060         bool notempty;
00061     } *index;
00062 
00063     // the number of holes inside rawdata
00064     // each hole is sizeof_t bytes
00065     int holecount;
00066 
00067     long size, mincap;
00068     long capacity, maxsize;
00069 
00070     // Completely packs rawdata
00071     // Eventually adjusts the sizes in order to contain at least
00072     // newsize elements
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         // and we make every item as empty, i.e. not pointing to anything
00092         memset(index, 0, mincap * sizeof(myindex));
00093 
00094         holecount = 0;
00095 
00096         size = 0;
00097         maxsize = capacity = mincap;
00098     }
00099 
00100     // Makes a null position... not to be exposed
00101     // Because after this the element pointed to by el becomes invalid
00102     // Typically el will be moved at the end, at the size+holecount position
00103     void DestroyElem(myindex *el) {
00104       reinterpret_cast<T*>(rawdata+el->offs)->~T();
00105       //      el->notempty = false;
00106     }
00107 
00108     void put(T& item, long pos) {
00109         // Puts an element in position pos
00110         // Hence write at pos in the index array
00111         // Use a new chunk of rawdata if the item does not point to a chunk
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             // did we fill a hole?
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         // We calculate a size which is aligned on 4-bytes
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            // Add new elements if needed
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 //     // Inserts an item in the given position
00205 //     void Insert(T& item, int pos) {
00206       
00207 //      if (pos >= size) {
00208 //          Push_back(item);
00209 //          return;
00210 //      }
00211 
00212 //      if ( BufRealloc(size+1) ) {
00213 
00214 //          memmove(&index[pos+1], &index[pos], (size+holecount-pos) * sizeof(myindex));
00215 //          index[pos].notempty = false;
00216 //          size++;
00217 //          put(item, pos);
00218 //      }
00219 
00220 //     }
00221 
00222 
00223     // Inserts an item in the given position
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 //     // 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
00251 //      DestroyElem(index + pos);
00252 
00253 //      index[size+holecount] = index[pos];
00254 //      holecount++;
00255 
00256 //      memmove(&index[pos], &index[pos+1], (size+holecount-pos) * sizeof(myindex));
00257 
00258 //      size--;
00259 
00260 //         if (!dontrealloc)
00261 //            BufRealloc(size);
00262 
00263 //     }
00264 
00265     // Removes a single element in position pos
00266    void Erase(unsigned int pos, bool dontrealloc=true) {
00267         // We make the position empty, then move the free index to the end of the full items
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         //BufRealloc(size);
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     // Bounded array like access
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 // Completely packs rawdata if needed
00319 // Eventually adjusts the sizes in order to fit newsize elements
00320 template <class T>
00321 int XrdClientVector<T>::BufRealloc(int newsize) {
00322 
00323     // If for some reason we have too many holes, we repack everything
00324     // this is very heavy!!
00325     if ((size+holecount >= capacity-2) && (holecount > 4*size))
00326         while (size+holecount >= capacity-2) {
00327             long lastempty = size+holecount-1;  // The first hole to fill
00328 
00329             // Pack everything in rawdata
00330             // Keep the pointers updated
00331 
00332             // Do the trick
00333 
00334             // Move the last filled to the first encountered hole
00335             memmove(rawdata + index[lastempty].offs, rawdata + index[lastempty].offs + sizeof_t,
00336                     (size+holecount)*sizeof_t - index[lastempty].offs );
00337 
00338             // Drop the index
00339             index[lastempty].notempty = false;
00340             holecount--;
00341 
00342             // Adjust all the pointers to the subsequent chunks
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         // Too near to the end?
00353         // double the capacity
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         // Too near to the beginning?
00370         // half the capacity
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

Generated on 13 Mar 2017 for xrootd by  doxygen 1.4.7