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