Home Research Papers Posters Manuals Talks Download People Help Internal

util/cklists.h

Go to the documentation of this file.

#ifndef _CKLISTS_H
#define _CKLISTS_H

//#include <converse.h> // for size_t
#include "pup.h"
#include "pup_stl.h"
#include <stdlib.h> // for size_t
#include <string.h> // for memcpy
#include <vector>

//"Documentation" class: prevents people from using copy constructors 
struct CkNoncopyable {
    CkNoncopyable(void) {}
    CkNoncopyable(const CkNoncopyable &c) = delete;
    CkNoncopyable& operator=(const CkNoncopyable &c) = delete;
    CkNoncopyable(CkNoncopyable&&) = default;
    CkNoncopyable& operator=(CkNoncopyable &&) = default;
    ~CkNoncopyable() = default;
};

//Implementation class 
template <class T>
class CkSTLHelper {
protected:
    //Copy nEl elements from src into dest
    void elementCopy(T *dest,const T *src,int nEl) {
      for (int i=0;i<nEl;i++) dest[i]=src[i];
    }
};

// Forward declarations:
template <class T> class CkQ;
template <class T> void pupCkQ(PUP::er &p,CkQ<T> &q);

template <class T>
class CkQ {
    std::vector<T> block;
    int first;
    int len;
    int mask;
    void _expand(void) {
      // block.size() is always kept as a power of 2
      int blklen = block.size();
      int newlen = blklen<<1;
      mask |= blklen;
      if (blklen==0) {
    CmiAssert(first == 0);
    newlen = 16;
    mask = 0x0f;
      }
      block.resize(newlen);
      if (first != 0) {
        // Rearrange elements of block so that first = 0
        CmiAssert(first > 0 && first < blklen);
        CmiAssert(newlen >= 2*blklen);
        std::move(block.begin(), block.begin()+first, block.begin()+blklen);
        std::move(block.begin()+first, block.begin()+blklen, block.begin());
        std::move(block.begin()+blklen, block.begin()+(blklen+first), block.begin()+(blklen-first));
        first = 0;
      }
    }
  public:
    CkQ() : first(0),len(0),mask(0) {}
    CkQ(CkQ &&rhs)
      : block(rhs.block)
      , first(rhs.first)
      , len(rhs.len)
      , mask(rhs.mask)
    {
      rhs.block.clear();
      rhs.len = 0;
    }
    CkQ(int sz) :first(0),len(0) {
      int size = 2;
      mask = 0x03;
      while (1<<size < sz) { mask |= 1<<size; size++; }
      int blklen = 1<<size;
      block.resize(blklen);
    }
    CkQ(const CkQ&) = delete;
    void operator=(const CkQ&) = delete;
    void operator=(CkQ&&) = delete; // Assignment of one queue to another makes no sense
    ~CkQ() {}
    inline int length() const { return len; }
    inline int isEmpty() const { return (len==0); }
    T deq() {
      if(len>0) {
        T &ret = block[first];
    first = (first+1)&mask;
        len--;
        return ret;
      } else return T(); //For builtin types like int, void*, this is equivalent to T(0)
    }
    void enq(const T &elt) {
      if((size_t)len==block.size()) _expand();
      block[(first+len)&mask] = elt;
      len++;
    }
    // stack semantics, needed to replace FIFO_QUEUE of converse
    void push(const T &elt) {
      if(len==block.size()) _expand();
      first = (first-1+block.size())&mask;
      block[first] = elt;
      len++;
    }
    // stack semantics: look at the element on top of the stack
    inline T& peek() {
      return block[first];
    }
    // insert an element at pos.
    void insert(int pos, const T &elt) {
      while(len==block.size() || pos>=block.size()) _expand();
      for (int i=len; i>pos; i--)
        block[(i+first)&mask] = std::move(block[(i-1+first)&mask]);
      block[(pos+first)&mask] = elt;
      if (pos > len) len = pos+1;
      else len++;
    }
    // delete an element at pos
    T remove(int pos) {
      if (pos >= len) return T(0);
      T ret = block[(pos+first)&mask];
      for (int i=pos; i<len-1; i++)
        block[(i+first)&mask] = std::move(block[(i+1+first)&mask]);
      len--;
      return ret;
    }
    // delete all elements from pos
    inline void removeFrom(int pos) {
      CmiAssert (pos < len && pos>=0);
      len = pos;
    }
    //Peek at the n'th item from the queue
    inline T& operator[](size_t n)
    {
        n=(n+first)&mask;
        return block[n];
    }
    // needed to replace FIFO_Enumerate
    T* getArray(void) {
      T *newblk = new T[len];
      int i,j;
      for(i=0,j=first;i<len;i++){
        newblk[i] = block[j];
        j = (j+1)&mask;
      }
      return newblk;
    }
     void pup(PUP::er &p) {
       p.syncComment(PUP::sync_begin_array);
       p|len;
       for (int i=0;i<len;i++) {
         p.syncComment(PUP::sync_item);
         if (p.isUnpacking()) {
           T t;
           p|t;
           enq(t);
         } else {
           p|block[(i+first)&mask];
         }
       }
       p.syncComment(PUP::sync_end_array);
     }
};

class CkSkipInitialization {};

// Forward declarations:
template <class T> class CkVec;
template <class T> void pupCkVec(PUP::er &p,CkVec<T> &vec);

template <class T>
class CkVec : private CkSTLHelper<T> {
    typedef CkVec<T> this_type;

    T *block; //Elements of vector
    size_t blklen; //Allocated size of block (STL capacity) 
    size_t len; //Number of used elements in block (STL size; <= capacity)
    void makeBlock(int blklen_,int len_) {
       if (blklen_==0) block=NULL; //< saves 1-byte allocations
       else {
         block=new T[blklen_];
         if (block == NULL) blklen_=len_= 0;
       }
       blklen=blklen_; len=len_;
    }
    void freeBlock(void) {
       len=0; blklen=0;
       delete[] block; 
       block=NULL;
    }
    void copyFrom(const this_type &src) {
       makeBlock(src.blklen, src.len);
       this->elementCopy(block,src.block,blklen);
    }
  public:
    CkVec(): block(NULL), blklen(0), len(0) {}
    ~CkVec() { freeBlock(); }
    CkVec(const this_type &src) {copyFrom(src);}
    CkVec(int size) { makeBlock(size,size); } 
    CkVec(int size, int used) { makeBlock(size,used); } 
    CkVec(const CkSkipInitialization &skip) {/* don't initialize */}
    this_type &operator=(const this_type &src) {
      freeBlock();
      copyFrom(src);
      return *this;
    }

    size_t &length(void) { return len; }
    size_t length(void) const {return len;}
    T *getVec(void) { return block; }
    const T *getVec(void) const { return block; }
    
    T& operator[](size_t n) {
      CmiAssert(n<len);
      return block[n]; 
    }
    
    const T& operator[](size_t n) const { 
      CmiAssert(n<len);
      return block[n]; 
    }
    
    int reserve(size_t newcapacity) {
      if (newcapacity<=blklen) return 1; /* already there */
      T *oldBlock=block; 
      makeBlock(newcapacity,len);
      if (newcapacity != blklen) return 0;
      this->elementCopy(block,oldBlock,len);
      delete[] oldBlock; //WARNING: leaks if element copy throws exception
      return 1;
    }
    inline size_t capacity(void) const {return blklen;}

    int resize(size_t newsize) {
      if (!reserve(newsize)) return 0;
      len=newsize;
      return 1;
    }

    void free() {
      freeBlock();
    }

    //Grow to contain at least this position:
    void growAtLeast(size_t pos) {
      if (pos>=blklen) reserve(pos*2+16);
    }
    void insert(size_t pos, const T &elt) {
      if (pos>=len) { 
        growAtLeast(pos);
        len=pos+1;
      }
      block[pos] = elt;
    }
    void remove(size_t pos) {
      if (pos>=len) 
    {
      CmiAbort("CkVec ERROR: out of bounds\n\n"); 
      return;
    }
      for (size_t i=pos; i<len-1; i++)
        block[i] = block[i+1];
      len--;
    }
    void removeAll() {
      len = 0;
    }

    void clear()
    {
    freeBlock();
    }

    void insertAtEnd(const T &elt) {insert(length(),elt);}

//STL-compatability:
    void push_back(const T &elt) {insert(length(),elt);}
    size_t size(void) const {return len;}

//verbose position for easier removal
    size_t push_back_v(const T &elt) {insert(length(),elt);return length()-1;}

 
//PUP routine help:
    //Only pup the length of this vector, which is returned:
    int pupbase(PUP::er &p) {
       size_t l=len;
       p(l);
       if (p.isUnpacking()) resize(l); 
       return l;
    }
    
#ifdef _MSC_VER
/* Visual C++ 6.0's operator overloading is buggy,
   so use default operator|, which calls this pup routine. */
     void pup(PUP::er &p) {
        pupCkVec(p,*this);
     }
#endif

        inline void quickSort(){
          q_sort(0, len - 1,128);
        }

        inline void quickSort(int changeOverSize){
            q_sort(0,len-1,changeOverSize);
        }
        

        inline void q_sort(int left, int right,int changeOverSize){
          int l_hold, r_hold;
            int pivot;
            
            if(left >= right)
                return;
            
            //swap the center element with the left one
            int mid =  (left+right)/2;
            T temp = block[mid];
            block[mid] = block[left];
            block[left] = temp;
            
          l_hold = left;
          r_hold = right;
            pivot = left;
            if(right - left <= changeOverSize){
                bubbleSort(left,right);
                return;
            }
          while (left < right)
          {
            while ((block[right] >= block[pivot]) && (left < right))
              right--;
            while ((block[left] <= block[pivot]) && (left < right))
              left++;
            
                if(left < right){
                    T val = block[left];
                    block[left] = block[right];
                    block[right] = val;
                }
            }
            T val = block[left];
            block[left] = block[pivot];
            block[pivot] = val;
          pivot = left;
          left = l_hold;
          right = r_hold;
          if (left < pivot)
            q_sort(left, pivot-1,changeOverSize);
          if (right > pivot)
            q_sort(pivot+1, right,changeOverSize);
        }

        inline void bubbleSort(int left,int right){
            for(int i=left;i<=right;i++){
                for(int j=i+1;j<=right;j++){
                    if(block[i] >= block[j]){
                        T val = block[i];
                        block[i] = block[j];
                        block[j] = val;
                    }
                }
            }
        }

};

template <class T>
inline void pupCkVec(PUP::er &p,CkVec<T> &vec) {
    size_t len=vec.pupbase(p);
    if (len) PUParray(p,&vec[0],len);
}

#ifndef _MSC_VER
template <class T>
inline void operator|(PUP::er &p,CkVec<T> &vec) {pupCkVec(p,vec);}
#endif

/* OLD: Deprecated name for vector of basic types. */
#define CkPupBasicVec CkVec

template <class T> 
class CkPupAlwaysAllocatePtr {
public:
    void pup(PUP::er &p,T *&ptr) {
        if (p.isUnpacking()) ptr=new T;
        p|*ptr;
    }
};

template <class T> 
class CkPupAllocatePtr {
public:
    void pup(PUP::er &p,T *&ptr) {
        int isNull=(ptr==0);
        p(isNull);
        if (isNull) ptr=0;
        else {
            if (p.isUnpacking()) ptr=new T;
            p|*ptr;
        }
    }
};

template <class T> 
class CkPupAblePtr {
public:
    void pup(PUP::er &p,T *&ptr) {
        p|ptr;
    }
};

template <class T, class PUP_PTR=CkPupAllocatePtr<T> > 
class CkZeroPtr {
protected:
    T *storage;
public:
    CkZeroPtr() {storage=0;}
    CkZeroPtr(T *sto) {storage=sto;}
    CkZeroPtr(const CkZeroPtr &src) { storage=src.storage; }
    CkZeroPtr &operator=(const CkZeroPtr &src) {
        storage=src.storage; return *this;
    }
    T *operator=(T *sto) {storage=sto; return sto;}
    
    operator T* () const {return storage;}

    T *release() {
        T *ret=storage; storage=0; return ret;
    }
    
    //Stolen from boost::scoped_ptr:
    T & operator*() const // never throws
        { return *storage; }
    T * operator->() const // never throws
        { return storage; }

    
    //Free referenced pointer:
    void destroy(void) {
        delete storage;
        storage=0;
    }
    
        void pup(PUP::er &p) {   
        PUP_PTR ppr;
        ppr.pup(p,storage);
        }
        friend void operator|(PUP::er &p,CkZeroPtr<T,PUP_PTR> &v) {v.pup(p);}
};


template <class T, class PUP_PTR=CkPupAllocatePtr<T> >
class CkPupPtrVec : public CkVec< CkZeroPtr<T, PUP_PTR> > {
  public:
  typedef CkPupPtrVec<T,PUP_PTR> this_type;
  typedef CkVec< CkZeroPtr<T, PUP_PTR> > super;
  CkPupPtrVec() {}
  CkPupPtrVec(int size) :super(size) {}
  
  ~CkPupPtrVec() {
    for (size_t i=0;i<this->length();i++)
      this->operator[] (i).destroy();
  }
  void pup(PUP::er &p) { pupCkVec(p,*this); }
  friend void operator|(PUP::er &p,this_type &v) {v.pup(p);}
};

template <class T>
class CkPupAblePtrVec : public CkVec< CkZeroPtr<T, CkPupAblePtr<T> > > {
 public:
    typedef CkPupAblePtrVec<T> this_type;
    typedef CkVec< CkZeroPtr<T, CkPupAblePtr<T> > > super;
    CkPupAblePtrVec() {}
    CkPupAblePtrVec(int size) :super(size) {}
    CkPupAblePtrVec(const this_type &t) {
        copy_from(t);
    }
    this_type &operator=(const this_type &t) {
        destroy();
        copy_from(t);
        return *this;
    }
    void copy_from(const this_type &t) {
        for (size_t i=0;i<t.length();i++)
            this->push_back((T *)t[i]->clone());
    }
    void destroy(void) {
        for (size_t i=0;i<this->length();i++)
            this->operator[] (i).destroy();
        this->length()=0;
    }
    ~CkPupAblePtrVec() {
        destroy();
    }
    void pup(PUP::er &p) { pupCkVec(p,*this); }
    friend void operator|(PUP::er &p,this_type &v) {v.pup(p);}
};

#define MAXMSGS 32

// thread safe pool, also safe with sig io with immediate messages
template <class T>
class SafePool {
  protected:
    int num;
    T msgs[MAXMSGS];
    typedef T (*allocFn)();
    typedef void (*freeFn)(T);
    typedef void (*resetFn)(T);
    allocFn allocfn;
    freeFn  freefn;
    resetFn resetfn;
  public:
    SafePool(allocFn _afn, freeFn _ffn, resetFn _rfn=NULL): allocfn(_afn), freefn(_ffn), resetfn(_rfn) {
      for(int i=0;i<MAXMSGS;i++)
        msgs[i] = allocfn();
      num = MAXMSGS;
    }
    T get(void) {
      /* CkAllocSysMsg() called in .def.h is not thread of sigio safe */
      if (CmiImmIsRunning()) return allocfn();
      return (num ? msgs[--num] : allocfn());
    }
    void put(T m) {
      if (num==MAXMSGS || CmiImmIsRunning())
        freefn(m);
      else {
        if (resetfn!=NULL) resetfn(m);
        msgs[num++] = m;
      }
    }
};

template <class T>
class CkPagedVector : private CkNoncopyable {
    enum {pageSize=256u};
    T **pages;
    int nPages;
    void allocatePages(int nEntries) {
        nPages=(nEntries+pageSize-1)/pageSize; // round up
        pages=new T*[nPages];
        for (int pg=0;pg<nPages;pg++) pages[pg]=0;
    }
    void allocatePage(int pg) {
        T *np=new T[pageSize];
        // Initialize the new elements of the page to 0:
        for (int of=0;of<pageSize;of++) np[of]=T();
        pages[pg]=np;
    }
public:
    CkPagedVector() :pages(0), nPages(0) {}
    CkPagedVector(int nEntries) {init(nEntries);}
    ~CkPagedVector() {
        for (int pg=0;pg<nPages;pg++) 
            if (pages[pg]) 
                delete[] pages[pg];
        delete[] pages;
    }
    void init(int nEntries) {
        allocatePages(nEntries);
    }
    
    inline T &operator[] (unsigned int i) {
        // This divide and mod should be fast, 
        //  as long as pageSize is a power of 2:
        int pg=i/pageSize; 
        int of=i%pageSize;
        if (pages[pg]==NULL) allocatePage(pg);
        return pages[pg][of];
    }
    
        inline T get (unsigned int i) {
        int pg=i/pageSize; 
        int of=i%pageSize;
                return pages[pg]==NULL? T():pages[pg][of];
        }

    void pupPage(PUP::er &p,int pg) {
        if (p.isUnpacking()) allocatePage(pg);
        for (int of=0;of<pageSize;of++) 
            p|pages[pg][of];
    }
    void pup(PUP::er &p) {
        int pg;
        p|nPages;
        if (!p.isUnpacking()) 
        { // Packing phase: save each used page
            for (pg=0;pg<nPages;pg++) 
            if (pages[pg]) {
                p|pg;
                pupPage(p,pg);
            }
            pg=-1;
            p|pg;
        } else 
        { // Unpacking phase: allocate and restore
            allocatePages(nPages*pageSize);
            //cppcheck-suppress uninitvar
            p|pg;
            while (pg!=-1) {
                pupPage(p,pg);
                p|pg;
            }
        }
    }
};

// a special vector, which grows at front, and remove at the end linearly
// the vector keeps an offset, which represents all elements before offset 
// are T(0); lastnull keeps track of the consecutive T(0) (NULL) in the current
// block
template <class T>
class CkCompactVec : private CkSTLHelper<T> {
    typedef CkVec<T> this_type;

    T *block; //Elements of vector
    size_t blklen; //Allocated size of block (STL capacity) 
    size_t len; // total number of used elements in block, including ones before offset
    size_t offset;      // global seqno of the first element in the block
    size_t lastnull;    // the array index of the biggest consecutive NULLs
    void makeBlock(int blklen_,int len_,int offset_=0,int lastnull_=-1) {
       if (blklen_==0) block=NULL; //< saves 1-byte allocations
       else {
         block=new T[blklen_];
         if (block == NULL) blklen_=len_= 0;
       }
       blklen=blklen_; len=len_;
       offset=offset_; lastnull=lastnull_;
    }
    void freeBlock(void) {
       len=0; blklen=0;
       delete[] block; 
       block=NULL;
       offset=0; lastnull=-1;
    }
    void copyFrom(const this_type &src) {
       makeBlock(src.blklen, src.len, src.offset, src.lastnull);
       elementCopy(block,src.block,blklen);
    }
  public:
    CkCompactVec(): block(NULL), blklen(0), len(0), offset(0), lastnull(-1) {}
    ~CkCompactVec() { freeBlock(); }
    CkCompactVec(const this_type &src) {copyFrom(src);}
    CkCompactVec(int size) { makeBlock(size,size); } 
    CkCompactVec(int size, int used) { makeBlock(size,used); } 
    CkCompactVec(const CkSkipInitialization &skip) {/* don't initialize */}
    this_type &operator=(const this_type &src) {
      freeBlock();
      copyFrom(src);
      return *this;
    }

    size_t &length(void) { return len; }
    size_t length(void) const {return len;}
    T *getVec(void) { return block; }
    const T *getVec(void) const { return block; }
    
    T& operator[](size_t n) {
      CmiAssert(n<len && n>=offset);
      return block[n-offset]; 
    }
    
    const T& operator[](size_t n) const { 
      CmiAssert(n-offset<len);
      return n<offset?NULL:block[n-offset]; 
    }
    
    int reserve(size_t newcapacity) {
      if (newcapacity-offset<=blklen) return 1; /* already there */
      T *oldBlock=block; 
      makeBlock(newcapacity-offset-lastnull,len,offset,lastnull);
      //if (newcapacity-offset-lastnull != blklen) return 0;
      elementCopy(block,oldBlock+lastnull+1,len-offset-lastnull-1);
      offset+=lastnull+1;   
      lastnull=-1;
      delete[] oldBlock; //WARNING: leaks if element copy throws exception
      return 1;
    }
    inline size_t capacity(void) const {return blklen;}

    int resize(size_t newsize) {
      if (!reserve(newsize)) return 0;
      len=newsize;
      return 1;
    }

    void free() {
      freeBlock();
    }

    //Grow to contain at least this position:
    void growAtLeast(size_t pos) {
      if (pos>=blklen+offset) reserve(pos*2+16);
    }
    void insert(size_t pos, const T &elt) {
      if (pos>=len) { 
        growAtLeast(pos);
        len=pos+1;
      }
      block[pos-offset] = elt;
    }
    void shrink() {
      for (size_t i=offset+lastnull+1; i<len; i++)
        block[i-offset-lastnull-1] = block[i-offset];
      offset+=lastnull+1; lastnull=-1;
      //printf("shrink: len:%d offset:%d  blklen:%d\n", len, offset, blklen);
    }
    void remove(size_t pos) {
      if (pos < offset) {
        CmiAbort("CkVec ERROR: try to remove non-exisitent element.\n\n");
        return;
      }
      if (pos>=len) 
    {
      CmiAbort("CkVec ERROR: out of bounds\n\n"); 
      return;
    }
      if (lastnull >= blklen/2) {   // shrink
        for (size_t i=offset+lastnull+1; i<pos; i++)
          block[i-offset-lastnull-1] = block[i-offset];
        for (size_t i=pos; i<len-1; i++)
          block[i-offset-lastnull-1] = block[i-offset+1];
        offset+=lastnull+1; lastnull=-1;
      }
      else {
      for (size_t i=pos; i<len-1; i++)
        block[i-offset] = block[i-offset+1];
      if (pos-offset==lastnull+1) lastnull++;
      }
      len--;
    }
    void marknull(size_t pos) {
      block[pos-offset] = T(0);
      if (pos == offset+lastnull+1) lastnull++;
      if (lastnull >= blklen/4) shrink();
    }
    void removeAll() {
      len = 0;
      offset=0; lastnull=-1;
    }

    void clear()
    {
    freeBlock();
    }

    void insertAtEnd(const T &elt) {insert(length(),elt);}

//STL-compatability:
    void push_back(const T &elt) {insert(length(),elt);}
    size_t size(void) const {return len;}

//verbose position for easier removal
    size_t push_back_v(const T &elt) {insert(length(),elt);return length()-1;}

 
//PUP routine help:
    //Only pup the length of this vector, which is returned:
    int pupbase(PUP::er &p) {
       size_t l=len;
       p(l);
       if (p.isUnpacking()) resize(l); 
       return l;
    }
    
#ifdef _MSC_VER
/* Visual C++ 6.0's operator overloading is buggy,
   so use default operator|, which calls this pup routine. */
     void pup(PUP::er &p) {
        pupCkVec(p,*this);
        p|offset;
        p|lastnull;
     }
#endif

};


#endif

---