XrdClientVector.hh

Go to the documentation of this file.

#ifndef XRD_CLIIDXVEC_H
#define XRD_CLIIDXVEC_H
/******************************************************************************/
/*                                                                            */
/*                  X r d C l i e n t V e c t o r . h h                       */
/*                                                                            */
/* Author: Fabrizio Furano (INFN Padova, 2006)                                */
/*                                                                            */
/* This file is part of the XRootD software suite.                            */
/*                                                                            */
/* XRootD is free software: you can redistribute it and/or modify it under    */
/* the terms of the GNU Lesser General Public License as published by the     */
/* Free Software Foundation, either version 3 of the License, or (at your     */
/* option) any later version.                                                 */
/*                                                                            */
/* XRootD is distributed in the hope that it will be useful, but WITHOUT      */
/* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or      */
/* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public       */
/* License for more details.                                                  */
/*                                                                            */
/* You should have received a copy of the GNU Lesser General Public License   */
/* along with XRootD in a file called COPYING.LESSER (LGPL license) and file  */
/* COPYING (GPL license).  If not, see <http://www.gnu.org/licenses/>.        */
/*                                                                            */
/* The copyright holder's institutional names and contributor's names may not */
/* be used to endorse or promote products derived from this software without  */
/* specific prior written permission of the institution or contributor.       */
/******************************************************************************/

//////////////////////////////////////////////////////////////////////////
//                                                                      //
// A vector class optimized for insertions and deletions                //
//   indexed access takes O(1)                                          //
//   insertion takes O(1) plus a very small fraction of O(n)            //
//   deletion takes O(1) plus a very small fraction of O(n)             //
//                                                                      //
// Better suited than XrdClientVector to hold complex objects           //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

#include <stdlib.h>
#include <string.h>

#include "XrdSys/XrdSysHeaders.hh"

#define IDXVEC_MINCAPACITY       128

template<class T>
class XrdClientVector {

private:

    // We keep the corrected size of T
    int sizeof_t;

    char *rawdata; // A raw mem block to hold (casted) T instances

    struct myindex {
   long offs; // Offset to a T inside rawdata
   bool notempty;
    } *index;

    // the number of holes inside rawdata
    // each hole is sizeof_t bytes
    int holecount;

    long size, mincap;
    long capacity, maxsize;

    // Completely packs rawdata
    // Eventually adjusts the sizes in order to contain at least
    // newsize elements
    int BufRealloc(int newsize);

    inline void Init(int cap = -1) {
   if (rawdata) free(rawdata);
   if (index) free(index);

        mincap = (cap > 0) ? cap : IDXVEC_MINCAPACITY;

   rawdata = static_cast<char *>(malloc(mincap * sizeof_t));

   index = static_cast<myindex *>(malloc(mincap * sizeof(myindex)));

   if (!rawdata || !index) {
     std::cerr << "XrdClientIdxVector::Init .... out of memory. sizeof_t=" << sizeof_t <<
       " sizeof(myindex)=" << sizeof(myindex) << " capacity=" << mincap << std::endl;
     abort();
   }

   // and we make every item as empty, i.e. not pointing to anything
   memset(index, 0, mincap * sizeof(myindex));

   holecount = 0;

   size = 0;
   maxsize = capacity = mincap;
    }

    // Makes a null position... not to be exposed
    // Because after this the element pointed to by el becomes invalid
    // Typically el will be moved at the end, at the size+holecount position
    void DestroyElem(myindex *el) {
      reinterpret_cast<T*>(rawdata+el->offs)->~T();
      //      el->notempty = false;
    }

    void put(T& item, long pos) {
   // Puts an element in position pos
   // Hence write at pos in the index array
   // Use a new chunk of rawdata if the item does not point to a chunk
   if (size+holecount >= capacity) {
     std::cerr << "XrdClientIdxVector::put .... internal error." << std::endl;
     abort();
   }
   
   T *p;
   long offs = (size+holecount)*sizeof_t;

   if (index[pos].notempty) {
       offs = index[pos].offs;

       // did we fill a hole?
       holecount--;
   }

   p = new(rawdata + offs) T(item);

   if (p) {
       index[pos].offs = offs;
       index[pos].notempty = true;
   }
   else {
       std::cerr << "XrdClientIdxVector::put .... out of memory." << std::endl;
       abort();
   }

    }

public:

    inline int GetSize() const { return size; }

    void Clear() {
   for (long i = 0; i < size; i++)
       if (index[i].notempty) DestroyElem(&index[i]);

   Init(mincap);
    }

    XrdClientVector(int cap = -1):
   sizeof_t(0), rawdata(0), index(0)
    {
   // We calculate a size which is aligned on 4-bytes
   sizeof_t = (sizeof(T) + 3) >> 2 << 2;
   Init(cap);
    }

    XrdClientVector(XrdClientVector &v):
   rawdata(0), index(0) {

        sizeof_t = (sizeof(T) + 3) >> 2 << 2;

   Init(v.capacity);
   BufRealloc(v.size);

   for (int i = 0; i < v.size; i++)
       Push_back( v[i] );
    }

    ~XrdClientVector() {
        for (long i = 0; i < size; i++)
          if (index[i].notempty) DestroyElem(&index[i]);

   if (rawdata) free(rawdata);
   if (index) free(index);
    }

    void Resize(int newsize) {
        long oldsize = size;

        if (newsize > oldsize) {
           BufRealloc(newsize);
           T *item = new T;
           // Add new elements if needed
           for (long i = oldsize; i < newsize; i++) {
              put(*item, size++);
           }
           delete item;
        }
        else {
           for (long i = oldsize; i > newsize; i--)
              Erase(i-1, false);
        }
    }

    void Push_back(T& item) {

   if ( BufRealloc(size+1) )
       put(item, size++);

    }

//     // Inserts an item in the given position
//     void Insert(T& item, int pos) {
      
//    if (pos >= size) {
//        Push_back(item);
//        return;
//    }

//    if ( BufRealloc(size+1) ) {

//        memmove(&index[pos+1], &index[pos], (size+holecount-pos) * sizeof(myindex));
//        index[pos].notempty = false;
//        size++;
//        put(item, pos);
//    }

//     }


    // Inserts an item in the given position
    void Insert(T& item, int pos) {
      
        if (pos >= size) {
            Push_back(item);
            return;
        }

        if ( BufRealloc(size+1) ) {

           if (holecount > 0) {
              struct myindex tmpi = index[size];
              memmove(&index[pos+1], &index[pos], (size-pos) * sizeof(myindex));
              index[pos] = tmpi;
           } else {
              memmove(&index[pos+1], &index[pos], (size-pos) * sizeof(myindex));
              index[pos].notempty = false;
           }

           size++;
           put(item, pos);
   }

    }

//     // Removes a single element in position pos
//    void Erase(unsigned int pos, bool dontrealloc=true) {
//    // We make the position empty, then move the free index to the end
//    DestroyElem(index + pos);

//    index[size+holecount] = index[pos];
//    holecount++;

//    memmove(&index[pos], &index[pos+1], (size+holecount-pos) * sizeof(myindex));

//    size--;

//         if (!dontrealloc)
//            BufRealloc(size);

//     }

    // Removes a single element in position pos
   void Erase(unsigned int pos, bool dontrealloc=true) {
   // We make the position empty, then move the free index to the end of the full items
   DestroyElem(index + pos);

   struct myindex tmpi = index[pos];
   holecount++;

   memmove(&index[pos], &index[pos+1], (size-pos-1) * sizeof(myindex));

   size--;
        index[size] = tmpi;
        if (!dontrealloc)
           BufRealloc(size);

    }

    T Pop_back() {
   T r( At(size-1) );

   DestroyElem(index+size-1);

   holecount++;
   size--;
   //BufRealloc(size);

   return (r);
    }

    T Pop_front() {
   T res;

   res = At(0);

   Erase(0);
   return (res);
    }

    // Bounded array like access
    inline T &At(int pos) {
           if ((pos < 0) || (static_cast<unsigned long>(pos) >=
                             static_cast<unsigned long>(size))) abort();

   return *( reinterpret_cast<T*>(rawdata + index[pos].offs));
    }

    inline T &operator[] (int pos) {
   return At(pos);
    }

};


// Completely packs rawdata if needed
// Eventually adjusts the sizes in order to fit newsize elements
template <class T>
int XrdClientVector<T>::BufRealloc(int newsize) {

    // If for some reason we have too many holes, we repack everything
    // this is very heavy!!
    if ((size+holecount >= capacity-2) && (holecount > 4*size))
   while (size+holecount >= capacity-2) {
       long lastempty = size+holecount-1;  // The first hole to fill

       // Pack everything in rawdata
       // Keep the pointers updated

       // Do the trick

       // Move the last filled to the first encountered hole
       memmove(rawdata + index[lastempty].offs, rawdata + index[lastempty].offs + sizeof_t,
          (size+holecount)*sizeof_t - index[lastempty].offs );

       // Drop the index
       index[lastempty].notempty = false;
       holecount--;

       // Adjust all the pointers to the subsequent chunks
       for (long i = 0; i < size+holecount; i++)
      if (index[i].notempty && (index[i].offs > index[lastempty].offs))
          index[i].offs -= sizeof_t;
   
   }

    if (newsize > maxsize) maxsize = newsize;

    while (newsize+holecount > capacity*2/3) {
   // Too near to the end?
   // double the capacity

   capacity *= 2;

   rawdata = static_cast<char *>(realloc(rawdata, capacity*sizeof_t));
   if (!rawdata) {
       std::cerr << "XrdClientIdxVector::BufRealloc .... out of memory." << std::endl;
       abort();
   }

   index = static_cast<myindex *>(realloc(index, capacity*sizeof(myindex)));
   memset(index+capacity/2, 0, capacity*sizeof(myindex)/2);

    }

    while ((newsize+holecount < capacity/3) && (capacity > 2*mincap)) {
   // Too near to the beginning?
   // half the capacity


   capacity /= 2;

   rawdata = static_cast<char *>(realloc(rawdata, capacity*sizeof_t));
   if (!rawdata) {
       std::cerr << "XrdClientIdxVector::BufRealloc .... out of memory." << std::endl;
       abort();
   }

   index = static_cast<myindex *>(realloc(index, capacity*sizeof(myindex)));

    }

    return 1;

}
#endif