_memory.h
00001 /* Copyright (C) 2003-2005  Martin Förg
00002 
00003  * This library is free software; you can redistribute it and/or
00004  * modify it under the terms of the GNU Lesser General Public
00005  * License as published by the Free Software Foundation; either
00006  * version 2.1 of the License, or (at your option) any later version.
00007  * 
00008  * This library is distributed in the hope that it will be useful,
00009  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00010  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00011  * Lesser General Public License for more details.
00012  * 
00013  * You should have received a copy of the GNU Lesser General Public
00014  * License along with this library; if not, write to the Free Software
00015  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
00016  *
00017  * Contact:
00018  *   martin.o.foerg@googlemail.com
00019  *
00020  */
00021 
00022 #ifndef _memory_h
00023 #define _memory_h
00024 
00025 // includes
00026 #include <stdlib.h>
00027 #include <vector>
00028 
00029 // include header given by ALLOCATORHEADER
00030 #ifdef ALLOCATORHEADER
00031 #  define CPPBEGININCLUDE <
00032 #  define CPPENDINCLUDE >
00033 #  include CPPBEGININCLUDE./ALLOCATORHEADER CPPENDINCLUDE
00034 #  undef CPPBEGININCLUDE
00035 #  undef CPPENDINCLUDE
00036 #endif
00037 // use fmatvec::PoolAllocator if no allocator is defined (the default in the configure script)
00038 #ifndef ALLOCATORCLASS
00039 #  define ALLOCATORCLASS fmatvec::PoolAllocator
00040 #endif
00041 
00042 // create some locking and atomic operations dependent on the thread safety method
00043 //
00044 // FMATVEC_LOCKVAR(l) : create a locking/mutex named l
00045 // FMATVEC_LOCKINIT(l) : initialize the locking/mutex named l
00046 // FMATVEC_LOCK(l) : lock the locking/mutex l
00047 // FMATVEC_UNLOCK(l) : unlock the locking/mutex l
00048 //
00049 // FMATVEC_SYNCVAR(l) : create a locking/mutex named l for a syncronized operation
00050 // FMATVEC_SYNCINIT(l) : initialize a locking/mutex named l for a syncronized operation
00051 // FMATVEC_SYNCINC(var, l) : var++ (syncronized by l)
00052 // FMATVEC_SYNCPREDEC(ret, var, l) : ret=--(var) (syncronized by l)
00053 #if defined FMATVEC_THREADSAFE_GCCBUILTIN
00054   #define FMATVEC_LOCKVAR(l) short int l;
00055   #define FMATVEC_LOCKINIT(l) l=0;
00056   #define FMATVEC_LOCK(l) while(__sync_bool_compare_and_swap(&l, 0, 0xffff)==false);
00057   #define FMATVEC_UNLOCK(l) __sync_bool_compare_and_swap(&l, 0xffff, 0);
00058 
00059   #define FMATVEC_SYNCVAR(l)
00060   #define FMATVEC_SYNCINIT(l)
00061   #define FMATVEC_SYNCINC(var, l) __sync_add_and_fetch(&(var), 1);
00062   #define FMATVEC_SYNCPREDEC(ret, var, l) ret=__sync_sub_and_fetch(&(var), 1);
00063 #elif defined FMATVEC_THREADSAFE_PTHREAD
00064   #include <pthread.h> // pthread required a header file
00065 
00066   #define FMATVEC_LOCKVAR(l) pthread_mutex_t l;
00067   #define FMATVEC_LOCKINIT(l) pthread_mutex_init(&l, NULL);
00068   #define FMATVEC_LOCK(l) pthread_mutex_lock(&l);
00069   #define FMATVEC_UNLOCK(l) pthread_mutex_unlock(&l);
00070 
00071   #define FMATVEC_SYNCVAR(l)  pthread_mutex_t l;
00072   #define FMATVEC_SYNCINIT(l) pthread_mutex_init(&l, NULL);
00073   #define FMATVEC_SYNCINC(var, l) pthread_mutex_lock(&l); (var)++; pthread_mutex_unlock(&l);
00074   #define FMATVEC_SYNCPREDEC(ret, var, l) pthread_mutex_lock(&l); ret=--(var); pthread_mutex_unlock(&l);
00075 #elif defined FMATVEC_THREADSAFE_OPENMP
00076   #define FMATVEC_PRAGMA(x) _Pragma(#x) // openmp required the _Pragma operator (defined by C99)
00077 
00078   #define FMATVEC_LOCKVAR(l)
00079   #define FMATVEC_LOCKINIT(l)
00080   #define FMATVEC_LOCK(l) FMATVEC_PRAGMA(omp critical (l)) {
00081   #define FMATVEC_UNLOCK(l) }
00082 
00083   #define FMATVEC_SYNCVAR(l)
00084   #define FMATVEC_SYNCINIT(l)
00085   #define FMATVEC_SYNCINC(var, l) FMATVEC_PRAGMA(omp critical (l)) { (var)++; }
00086   #define FMATVEC_SYNCPREDEC(ret, var, l) FMATVEC_PRAGMA(omp critical (l)) { ret=--(var); }
00087 #else
00088   #define FMATVEC_PRAGMA(l)
00089   #define FMATVEC_LOCKVAR(l)
00090   #define FMATVEC_LOCKINIT(l)
00091   #define FMATVEC_LOCK(l)
00092   #define FMATVEC_UNLOCK(l)
00093 
00094   #define FMATVEC_SYNCVAR(l)
00095   #define FMATVEC_SYNCINIT(l)
00096   #define FMATVEC_SYNCINC(var, l) (var)++;
00097   #define FMATVEC_SYNCPREDEC(ret, var, l) ret=--(var);
00098 #endif
00099 
00100 #if defined MEMORYCLASS_BOOST
00101 #  include <boost/shared_array.hpp>
00102 #endif
00103 
00110 namespace fmatvec {
00111 
00113 
00114   // A STL-like pool memory allocator (being fast)
00115   template <class AT>
00116   class PoolAllocator {
00117     private:
00118       // The minimal allocation size in power of 2: MINSIZE=2^MINEXP
00119       static const size_t MINEXP=4;
00120       // A pool of memory of allocation size 2^(MINEXP+0), 2^(MINEXP+1), 2^(MINEXP+2), ...
00121       // stored at index 0, 1, 2, ... in memoryPool.
00122       // The pointers stored here are already allocated but currently not used.
00123       std::vector<std::vector<AT*> > memoryPool;
00124       // Just a dummy variable used for zero size allocations.
00125       AT sizeZero;
00126       FMATVEC_LOCKVAR(fmatvec_memoryPoolLock)
00127     public:
00128       // Constructor: alloc memoryPool with at least size 1, since the size is doubled each time the size ran out.
00129       PoolAllocator() : memoryPool(1) {
00130         FMATVEC_LOCKINIT(fmatvec_memoryPoolLock)
00131       }
00132       // Destructor: delete all cached memory in the pool.
00133       ~PoolAllocator() {
00134         // loop over all pool sizes and free memory
00135         for(typename std::vector<std::vector<AT*> >::iterator i=memoryPool.begin(); i!=memoryPool.end(); ++i)
00136           for(typename std::vector<AT*>::iterator j=i->begin(); j!=i->end(); ++j)
00137             delete[](*j);
00138       }
00139       // Allocate new memory of at least size size.
00140       AT *allocate(size_t size) { 
00141         // do nothing for zero size, but return a valid memory pointer
00142         if(size==0) return &sizeZero;
00143         // calculate size index: size 0 to 2^MINEXP = index 0; size 2^MINEXP+1 to 2*2^MINEXP = index 1; ...
00144         size_t index=0;
00145         --size>>=MINEXP-1;
00146         while(size>>=1) ++index;
00147         AT* ret=NULL;
00148         FMATVEC_LOCK(fmatvec_memoryPoolLock)
00149           // increase (double) memoryPool if nessasary
00150           if(index>=memoryPool.size()) memoryPool.resize(index<<1);
00151           // try to use cached memory
00152           std::vector<AT*> &memoryPoolIndex=memoryPool[index];
00153           if(memoryPoolIndex.size()>0) {
00154             ret=memoryPoolIndex.back(); // get last cached memory
00155             memoryPoolIndex.pop_back(); // remove last cached memory
00156           }
00157         FMATVEC_UNLOCK(fmatvec_memoryPoolLock)
00158         if(ret) return ret; // return chaced memory
00159         // return new memory
00160         return new AT[1<<(index+MINEXP)]; // allocate 2^(index+MINEXP) elements (max size for this index)
00161       }
00162       // Free memory and release it to the pool.
00163       void deallocate(AT *p, size_t size) {
00164         // do nothing for zero size, a dummy but valid pointer was returned by allocate
00165         if(size==0) return;
00166         // calculate size index: size 0 to 2^MINEXP = index 0; size 2^MINEXP+1 to 2*2^MINEXP = index 1; ...
00167         size_t index=0;
00168         --size>>=MINEXP-1;
00169         while(size>>=1) ++index;
00170         FMATVEC_LOCK(fmatvec_memoryPoolLock)
00171           // release memory
00172           memoryPool[index].push_back(p); // add to cached memory
00173         FMATVEC_UNLOCK(fmatvec_memoryPoolLock)
00174       }
00175   };
00176 
00177 
00178 
00179 
00180 
00181 #ifdef MEMORYCLASS_FMATVEC
00182 
00183   // this is the old fmatvec Memory class which uses different allocators (using the std::allocator interface)
00184   template <class AT> class Memory {
00185       private:
00186         typedef ALLOCATORCLASS<AT> allocator_type;
00187         size_t sz;
00188         AT *ele0;
00189         static allocator_type ms;
00190         size_t *ref;
00191         FMATVEC_SYNCVAR(fmatvec_refLock)
00192         void lock() {
00193           FMATVEC_SYNCINC(*ref, fmatvec_refLock)
00194         };
00195         void unlock() {
00196           size_t refLocal;
00197           FMATVEC_SYNCPREDEC(refLocal, *ref, fmatvec_refLock)
00198           if(!refLocal) {
00199             ms.deallocate(ele0, sz);
00200             delete ref;
00201           }
00202         };
00203 
00204       public:
00205         Memory() : sz(0), ele0(0), ref(new size_t(1)) {
00206           FMATVEC_SYNCINIT(fmatvec_refLock);
00207         };
00208 
00209         Memory(size_t n) : sz(n), ele0(ms.allocate(sz)), ref(new size_t(1)){
00210           FMATVEC_SYNCINIT(fmatvec_refLock);
00211         };
00212 
00213         Memory(const Memory &memory) : sz(memory.sz), ele0(memory.ele0), ref(memory.ref)  {
00214           FMATVEC_SYNCINIT(fmatvec_refLock);
00215           lock();
00216         };
00217 
00218         ~Memory() {
00219           unlock();
00220         }; 
00221 
00222         Memory& operator=(const Memory &memory) {
00223           if(this == &memory)
00224             return *this;
00225           unlock(); sz=memory.sz; ref=memory.ref; ele0=memory.ele0; lock();
00226           return *this;
00227         }
00228 
00229         void resize(size_t n) {
00230           unlock();
00231           ref=new size_t(1);
00232           sz = n;
00233           ele0 = ms.allocate(sz);
00234         };
00235 
00236         AT* get() const {return ele0;};
00237     };
00238 
00239 #elif defined MEMORYCLASS_BOOST
00240 
00241   // Just a wrapper class around boost::shared_array, since the Memory interface differs a little bit from the boost smart-ptr interface
00242   // This wrapper is fully inlined by the compiler if optimization is used!
00243   template <class AT> class Memory {
00244     private:
00245       boost::shared_array<AT> ele0;
00246 
00247     public:
00248       Memory() : ele0() {};
00249 
00250       Memory(size_t n) : ele0(new AT[n]) {};
00251 
00252       Memory(const Memory &memory) : ele0(memory.ele0) {};
00253 
00254       ~Memory() {}; 
00255 
00256       Memory& operator=(const Memory &memory) {
00257         if(this == &memory)
00258           return *this;
00259         ele0=memory.ele0;
00260         return *this;
00261       }
00262 
00263       void resize(size_t n) {
00264         ele0.reset(new AT[n]);
00265       };
00266 
00267       AT* get() const {return ele0.get();};
00268   };
00269 
00270 #else
00271 
00272   // This class uses an "intrusive reference counting" mechanism for memory of n elements of type AT.
00273   // The reference count is stored as the first element of allocate memory. The rest is used for the n element of type AT.
00274   // Hence at least sizeof(size_t)+n*sizeof(AT) bytes are allocated.
00275   // For correct memory alignment the memory is allocated as an array of AT.
00276   template <class AT> class Memory {
00277     private:
00278       static const size_t ele0Start=(sizeof(size_t)-1)/sizeof(AT)+1; // the minimum number of AT elements such that one size_t fits into
00279       size_t *ref; // a pointer to the reference count (this is also the address of the allocated memory)
00280       AT *ele0; // a pointer to the allocated memory (this is also the address ((AT*)ref)+1)
00281       FMATVEC_SYNCVAR(fmatvec_refLock)
00282 
00283       void lock() {
00284         FMATVEC_SYNCINC(*ref, fmatvec_refLock)
00285       };
00286 
00287       void unlock() {
00288         size_t refLocal;
00289         FMATVEC_SYNCPREDEC(refLocal, *ref, fmatvec_refLock)
00290         if(!refLocal) {
00291           delete[]reinterpret_cast<AT*>(ref);
00292         }
00293       };
00294 
00295     public:
00296       Memory() : ref(reinterpret_cast<size_t*>(new AT[ele0Start])), ele0(NULL) {
00297         *ref=1; // initialize the reference count to 1
00298         FMATVEC_SYNCINIT(fmatvec_refLock);
00299       };
00300 
00301       Memory(size_t n) : ref(reinterpret_cast<size_t*>(new AT[ele0Start+n])), ele0(reinterpret_cast<AT*>(ref)+ele0Start) {
00302         *ref=1; // initialize the reference count to 1
00303         FMATVEC_SYNCINIT(fmatvec_refLock);
00304       };
00305 
00306       Memory(const Memory &memory) : ref(memory.ref), ele0(memory.ele0) {
00307         FMATVEC_SYNCINIT(fmatvec_refLock);
00308         lock();
00309       };
00310 
00311       ~Memory() {
00312         unlock();
00313       }; 
00314 
00315       Memory& operator=(const Memory &memory) {
00316         if(this == &memory)
00317           return *this;
00318         unlock(); ref=memory.ref; ele0=memory.ele0; lock();
00319         return *this;
00320       }
00321 
00322       void resize(size_t n) {
00323         unlock();
00324         ref=reinterpret_cast<size_t*>(new AT[ele0Start+n]);
00325         ele0=reinterpret_cast<AT*>(ref)+ele0Start;
00326         *ref=1; // initialize the reference count to 1
00327         };
00328 
00329       AT* get() const {return ele0;};
00330   };
00331 
00332 #endif
00333 
00334 }
00335 
00337  
00338 #endif