allocator.h

00001 /***********************************************************************
00002  * Software License Agreement (BSD License)
00003  *
00004  * Copyright 2008-2009  Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
00005  * Copyright 2008-2009  David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
00006  *
00007  * THE BSD LICENSE
00008  *
00009  * Redistribution and use in source and binary forms, with or without
00010  * modification, are permitted provided that the following conditions
00011  * are met:
00012  *
00013  * 1. Redistributions of source code must retain the above copyright
00014  *    notice, this list of conditions and the following disclaimer.
00015  * 2. Redistributions in binary form must reproduce the above copyright
00016  *    notice, this list of conditions and the following disclaimer in the
00017  *    documentation and/or other materials provided with the distribution.
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00020  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00021  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00022  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00023  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00024  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00025  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00026  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00028  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  *************************************************************************/
00030 
00031 #ifndef OPENCV_FLANN_ALLOCATOR_H_
00032 #define OPENCV_FLANN_ALLOCATOR_H_
00033 
00034 #include <stdlib.h>
00035 #include <stdio.h>
00036 
00037 
00038 namespace cvflann
00039 {
00040 
00041 /**
00042  * Allocates (using C's malloc) a generic type T.
00043  *
00044  * Params:
00045  *     count = number of instances to allocate.
00046  * Returns: pointer (of type T*) to memory buffer
00047  */
00048 template <typename T>
00049 T* allocate(size_t count = 1)
00050 {
00051     T* mem = (T*) ::malloc(sizeof(T)*count);
00052     return mem;
00053 }
00054 
00055 
00056 /**
00057  * Pooled storage allocator
00058  *
00059  * The following routines allow for the efficient allocation of storage in
00060  * small chunks from a specified pool.  Rather than allowing each structure
00061  * to be freed individually, an entire pool of storage is freed at once.
00062  * This method has two advantages over just using malloc() and free().  First,
00063  * it is far more efficient for allocating small objects, as there is
00064  * no overhead for remembering all the information needed to free each
00065  * object or consolidating fragmented memory.  Second, the decision about
00066  * how long to keep an object is made at the time of allocation, and there
00067  * is no need to track down all the objects to free them.
00068  *
00069  */
00070 
00071 const size_t     WORDSIZE=16;
00072 const  size_t     BLOCKSIZE=8192;
00073 
00074 class PooledAllocator
00075 {
00076     /* We maintain memory alignment to word boundaries by requiring that all
00077         allocations be in multiples of the machine wordsize.  */
00078     /* Size of machine word in bytes.  Must be power of 2. */
00079     /* Minimum number of bytes requested at a time from the system.  Must be multiple of WORDSIZE. */
00080 
00081 
00082     int     remaining;  /* Number of bytes left in current block of storage. */
00083     void*   base;     /* Pointer to base of current block of storage. */
00084     void*   loc;      /* Current location in block to next allocate memory. */
00085     int     blocksize;
00086 
00087 
00088 public:
00089     int     usedMemory;
00090     int     wastedMemory;
00091 
00092     /**
00093         Default constructor. Initializes a new pool.
00094      */
00095     PooledAllocator(int blockSize = BLOCKSIZE)
00096     {
00097         blocksize = blockSize;
00098         remaining = 0;
00099         base = NULL;
00100 
00101         usedMemory = 0;
00102         wastedMemory = 0;
00103     }
00104 
00105     /**
00106      * Destructor. Frees all the memory allocated in this pool.
00107      */
00108     ~PooledAllocator()
00109     {
00110         void* prev;
00111 
00112         while (base != NULL) {
00113             prev = *((void**) base); /* Get pointer to prev block. */
00114             ::free(base);
00115             base = prev;
00116         }
00117     }
00118 
00119     /**
00120      * Returns a pointer to a piece of new memory of the given size in bytes
00121      * allocated from the pool.
00122      */
00123     void* allocateMemory(int size)
00124     {
00125         int blockSize;
00126 
00127         /* Round size up to a multiple of wordsize.  The following expression
00128             only works for WORDSIZE that is a power of 2, by masking last bits of
00129             incremented size to zero.
00130          */
00131         size = (size + (WORDSIZE - 1)) & ~(WORDSIZE - 1);
00132 
00133         /* Check whether a new block must be allocated.  Note that the first word
00134             of a block is reserved for a pointer to the previous block.
00135          */
00136         if (size > remaining) {
00137 
00138             wastedMemory += remaining;
00139 
00140             /* Allocate new storage. */
00141             blockSize = (size + sizeof(void*) + (WORDSIZE-1) > BLOCKSIZE) ?
00142                         size + sizeof(void*) + (WORDSIZE-1) : BLOCKSIZE;
00143 
00144             // use the standard C malloc to allocate memory
00145             void* m = ::malloc(blockSize);
00146             if (!m) {
00147                 fprintf(stderr,"Failed to allocate memory.\n");
00148                 return NULL;
00149             }
00150 
00151             /* Fill first word of new block with pointer to previous block. */
00152             ((void**) m)[0] = base;
00153             base = m;
00154 
00155             int shift = 0;
00156             //int shift = (WORDSIZE - ( (((size_t)m) + sizeof(void*)) & (WORDSIZE-1))) & (WORDSIZE-1);
00157 
00158             remaining = blockSize - sizeof(void*) - shift;
00159             loc = ((char*)m + sizeof(void*) + shift);
00160         }
00161         void* rloc = loc;
00162         loc = (char*)loc + size;
00163         remaining -= size;
00164 
00165         usedMemory += size;
00166 
00167         return rloc;
00168     }
00169 
00170     /**
00171      * Allocates (using this pool) a generic type T.
00172      *
00173      * Params:
00174      *     count = number of instances to allocate.
00175      * Returns: pointer (of type T*) to memory buffer
00176      */
00177     template <typename T>
00178     T* allocate(size_t count = 1)
00179     {
00180         T* mem = (T*) this->allocateMemory((int)(sizeof(T)*count));
00181         return mem;
00182     }
00183 
00184 };
00185 
00186 }
00187 
00188 #endif //OPENCV_FLANN_ALLOCATOR_H_
00189