allocators.hpp

Go to the documentation of this file.

#ifndef ALLOCATORS_HPP_050402
#define ALLOCATORS_HPP_050402

#include <list>
#include <vector>
#include <stack>

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

#ifdef __SSE__
#include <xmmintrin.h>
#endif

#include "common/log.h"

#include <inttypes.h>




template<class T> class NewWrapperAlloc
{
  public:
   NewWrapperAlloc(){}
   T* DINLINE allocate(){
      return new T();
   }
   void free(T* data){
      delete data;
   }   
};

namespace bracz {
  class alignalloc {
    //must be a power of 2
    static const size_t alignment=16;
#ifdef __SSE__
    //    typedef int _v2q_t __attribute__((__mode__(V2DI)));
    typedef __m128i _v2q_t;

    static inline void DINLINE mymemzeroa(void *p,size_t len) {
      register int l=((len)+15)>>4;
      register _v2q_t a = {0,0};
      register _v2q_t *b=(_v2q_t*)p;
      while (l) {
        *b=a;
        ++b;
        --l;
      }
      //  memset(p,0,len<<2);
    }

    static inline void DINLINE mymemzerola(void *p,size_t len) {
      register int l=((len))>>4;
      register _v2q_t a = {0,0};
      register _v2q_t *b=(_v2q_t*)p;
      while (l) {
        *b=a;
        ++b;
        --l;
      }
      //zero remaining
      if (len & 15) {
        bzero(b,len & 15);
      }
    }

#else 
    #warning Enable SSE instructions to gain speed.

#define mymemzeroa bzero
#define mymemzerola bzero
    
#endif
  public:

    template<class T> static void DINLINE alloc(T*& array, size_t size) {
      size_t tots=size*sizeof(T);
      //round up the length to a multiple of alignment
      tots+=2*(alignment-1)+sizeof(void*);
      void * base=malloc(tots);
      if(!base) {
        log_err(0,"Memory allocation failed.");
        abort();
      }
      //skip the size of a void* and align
      uintptr_t nb = reinterpret_cast<uintptr_t>(base);
      nb+=sizeof(void*)+alignment-1;
      nb&=~(alignment-1);
      array=reinterpret_cast<T*>(nb);
      //make place for the saved pointer
      void** saveptr=reinterpret_cast<void**>(nb);
      saveptr--;
      //save the original pointer
      *saveptr=base;
    }

    template<class T> static void DINLINE allocz(T*& array, size_t size) {
      alloc(array,size);
      mymemzeroa(array,size*sizeof(T));
      //round up the length to a multiple of alignment
      //zero the array
      // **** MMX/SSE memory zero routine!
      //      memset(array,0,tots);
      //      bzero(array,tots);
    }
    

    template<class T> static inline void DINLINE zero(T* array, size_t size) {
      // **** MMX/SSE memory zero routine!
      //      memset(array,0,tots);
      //      bzero(array,tots);        
      mymemzeroa(array,size*sizeof(T));
    }

    template<class T> static void NOINLINE free(T* array) {
      //look up the saved pointer
      void** ob = reinterpret_cast<void**>(array);
      ob--;
      //free
      ::free(*ob);
    }

    template<class T> static void DINLINE freeifnonnull(T* array) {
      if (array)
        alignalloc::free(array);
    }
    

    template<class T> static inline void DINLINE zerola(T* array, size_t size) {
      // **** MMX/SSE memory zero routine
      //bzero(array,size*sizeof(T));
      mymemzerola(array,size*sizeof(T));
    }

  };//class alignalloc


template<class T, int bigblklen> class blockalloc {
public:
  blockalloc() {
    cbigblk=NULL;
    cfree=0;
  }

  T* DINLINE allocate(int ns) {
    if ((int)cfree<ns) {
      cfree=bigblklen;
      cbigblk=new T[bigblklen];
      //alignalloc::alloc(cbigblk,bigblklen);
      bigblocks.push_back(cbigblk);
    }
    T* ret=cbigblk;
    cfree-=ns;
    cbigblk+=ns;
    return ret;
  }

  T* DINLINE allocate() {
    if (!cfree) {
      cfree=bigblklen;
      cbigblk=new T[bigblklen];
      //alignalloc::alloc(cbigblk,bigblklen);

      bigblocks.push_back(cbigblk);
    }
    T* ret=cbigblk;
    --cfree;
    ++cbigblk;
    return ret;
  }

  void freeall() {
    for (TYPENAME bigblocks_t::iterator i=bigblocks.begin();
         i!=bigblocks.end(); ++i) {
       delete [] *i;
       //alignalloc::free(*i);

    }
    //be prepared for another call of freeall() or allocate()
    bigblocks.clear();
    cbigblk=NULL;
    cfree=0;
  }

  ~blockalloc() {
    freeall();
  }

private:
  typedef std::list<T*> bigblocks_t; 
  bigblocks_t bigblocks;
  
  T* cbigblk;
  
  size_t cfree;
};

/*template<class T, int bigblklen> class singlealloc {
public:
  singlealloc() :freelist(NULL){
  }

  T* DINLINE allocate() {
    if (freelist) {
      T* ret = (T*)freelist;
      freelist=freelist->next;
      return ret;
    }
    return (T*) allocator.allocate();
  }

  void freeall() {
    freelist=NULL;
    allocator.freeall();
  }

  void free(T* data) {
    newdata_t *d=static_cast<newdata_t*>(data);
    d->next=freelist;
    freelist=d;
  }

  ~singlealloc() {
    freeall();
  }

private:
  typedef union newdata_t {
    T data;
    newdata_t *next;
  } newdata_t;

  typedef blockalloc<newdata_t, bigblklen> realalloc_t;
  
  realalloc_t allocator;
  
  T* freelist;
}; //class singlealloc
*/

template<class WRP, int bigblklen> class singlewrpalloc {
public:
  typedef typename WRP::data_t data_t;
  singlewrpalloc() :freelist(NULL){
  }

  data_t* DINLINE allocate() {
    if (freelist) {
      WRP* ret = freelist;
      freelist=freelist->next;
      return ret->getData();
    }
    return allocator.allocate()->getData();
  }

  void freeall() {
    freelist=NULL;
    allocator.freeall();
  }

  void free(data_t* data) {
    WRP *d=(WRP*) data;
    d->next=freelist;
    freelist=d;
  }

  ~singlewrpalloc() {
    freeall();
  }

private:
  typedef WRP newdata_t;

  typedef blockalloc<WRP, bigblklen> realalloc_t;
  
  realalloc_t allocator;
  
  WRP* freelist;
}; //class singlealloc


  template<class T> class singleunionwrapper {
  public:
    typedef T data_t;
    union {
      T data;
      singleunionwrapper *next;
    };
    T* DINLINE getData() {
      return (T*) this;
    }
    singleunionwrapper *& DINLINE getNext() {
      return next;
    }
  }; //singleunionwrapper

  template<class T> class singlestructwrapper : T {
  public:
    typedef T data_t;

    singlestructwrapper *next;

    T* DINLINE getData() {
      return this;
    }
    singlestructwrapper *& DINLINE getNext() {
      return next;
    }
  }; //singlestructwrapper

  template<class T, int bigblklen> class singlesalloc: public singlewrpalloc<singlestructwrapper<T>, bigblklen> {};

  template<class T, int bigblklen> class singleualloc: public singlewrpalloc<singleunionwrapper<T>, bigblklen> {};


template<class T,int base, int bigblklen> class arrayalloc{
public:
  static  size_t DINLINE BLOCKLEN(int size)  {
    return (base << size);
  }

  T* DINLINE allocate(unsigned int size) {
    if (freelists.size()<=size) {
      freelists.resize(size+1);
    }
    T* ret;
<<<<<<< allocators.hpp
    if ((ret=freelists[size])) {
=======
    if ((ret=freelists[size])) { //double parenthesis to avoid warnings
>>>>>>> 1.5
      //we have a cached block
      T** d=(T**)ret;
      freelists[size]=*d;
      return ret;
    } else {
      //allocate a new block      
      size_t ns=BLOCKLEN(size);
      return thealloc.allocate(ns);
    }
  }//allocate

  void DINLINE free(T* data,unsigned int size) {
    if (freelists.size()<=size) {
      freelists.resize(size+1);
    }
    T** d=(T**)data;
    *d=freelists[size];
    freelists[size]=data;
  }//free
  
  
  arrayalloc() :thealloc(){
  }

private:

  std::vector<T*> freelists;

  blockalloc<T,bigblklen> thealloc;

};




  template <class BLOCK> class debugblockstack {
  public:
    void DINLINE pushAndGetBlock(size_t length, typename BLOCK::dataget_t &d) {
      blocks.push(length);
      getCurrBlock().getData(d);
    }

    void DINLINE freeBlock() {
      if (blocks.empty()) {
        log_err(0,"freeBlock when stack is empty!");
      }
      blocks.pop();
    }

    BLOCK& getCurrBlock() {
      return blocks.top();
    }

    ~debugblockstack() {
      while (!blocks.empty()) {
        log_dbg(0,"Freeing block");
        blocks.top().free();
        blocks.pop();
      }
    }

  private:
    class smemblock_t : public BLOCK {
    public:
      size_t length;
      smemblock_t(size_t _length): BLOCK(_length),length(_length){}
    };

    typedef std::stack<smemblock_t> blocklist_t;
    
    blocklist_t blocks;

  }; //class debugblockstack

  template <class BLOCK> class blockstack {
  public:
    void DINLINE ensureCurrBlock(size_t length) {
      if ((currblock==blocks.end())||(length>currblock->length)) {
        //allocate block
        length+=length>>1;//allocate somewhat more memory
        smemblock_t newblock(length);
        blocks.insert(currblock,newblock);
        --currblock;
      }
    }

    void DINLINE stepBlock() {
      ++currblock;
    }

    void DINLINE pushAndGetBlock(size_t length, typename BLOCK::dataget_t &d) {
      ensureCurrBlock(length);
      getCurrBlock().getData(d);
      stepBlock();
    }

    void DINLINE freeBlock() {
      --currblock;
    }

    BLOCK& getCurrBlock() {
      return *currblock;
    }

    blockstack() {
      currblock=blocks.end();
    }

    ~blockstack() {
      for (typename blocklist_t::iterator it=blocks.begin();it!=blocks.end();++it) {
        it->free();
      }
    }

  private:
    class smemblock_t : public BLOCK {
    public:
      size_t length;
      smemblock_t(size_t _length): BLOCK(_length),length(_length){}
    };

    typedef std::list<smemblock_t> blocklist_t;
    
    blocklist_t blocks;
    
    TYPENAME blocklist_t::iterator currblock;

  }; //class blockstack


  template<class T, bool PREZERO> class stacksingleblock {
  public:
    stacksingleblock(size_t length) {
      if (PREZERO) {
        alignalloc::allocz(data,length);
      } else {
        alignalloc::alloc(data,length);
      }
    }

    typedef T* dataget_t;

    void getData(dataget_t & r) {
      r=data;
    }
    
    void free() {
      alignalloc::freeifnonnull(data);
      data=NULL;
    }

  private:
    T* data;
  };//class stacksingleblock

  template<class T, bool PREZERO, class PARENT> class stackmultiblock : PARENT {
  public:
    stackmultiblock(size_t length) : PARENT(length) {
      if (PREZERO) {
        alignalloc::allocz(data,length);
      } else {
        alignalloc::alloc(data,length);
      }
    }

    typedef std::pair<T*, typename PARENT::dataget_t> dataget_t;
    void DINLINE getData(dataget_t &r) {
      PARENT::getData(r.second);
      r.first=data;
    }

    void free() {
      PARENT::free();
      alignalloc::freeifnonnull(data);
      data=NULL;
    }

  private:
    T* data;
  };//class stackmultiblock


} //namespace bracz


#endif //ALLOCATORS_HPP_050402

---