git.maemo.org Git - opencv/blob - 3rdparty/flann/util/allocator.h

   1 /***********************************************************************
   2  * Software License Agreement (BSD License)
   3  *
   4  * Copyright 2008-2009  Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
   5  * Copyright 2008-2009  David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
   6  *
   7  * THE BSD LICENSE
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  *
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  20  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  21  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  22  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  24  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  28  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  *************************************************************************/
  30
  31 #ifndef ALLOCATOR_H
  32 #define ALLOCATOR_H
  33
  34 #include <stdlib.h>
  35 #include <stdio.h>
  36
  37
  38 namespace flann
  39 {
  40
  41 /**
  42  * Allocates (using C's malloc) a generic type T.
  43  *
  44  * Params:
  45  *     count = number of instances to allocate.
  46  * Returns: pointer (of type T*) to memory buffer
  47  */
  48 template <typename T>
  49 T* allocate(size_t count = 1)
  50 {
  51         T* mem = (T*) ::malloc(sizeof(T)*count);
  52         return mem;
  53 }
  54
  55
  56 /**
  57  * Pooled storage allocator
  58  *
  59  * The following routines allow for the efficient allocation of storage in
  60  * small chunks from a specified pool.  Rather than allowing each structure
  61  * to be freed individually, an entire pool of storage is freed at once.
  62  * This method has two advantages over just using malloc() and free().  First,
  63  * it is far more efficient for allocating small objects, as there is
  64  * no overhead for remembering all the information needed to free each
  65  * object or consolidating fragmented memory.  Second, the decision about
  66  * how long to keep an object is made at the time of allocation, and there
  67  * is no need to track down all the objects to free them.
  68  *
  69  */
  70
  71 const size_t     WORDSIZE=16;
  72 const  size_t     BLOCKSIZE=8192;
  73
  74 class PooledAllocator
  75 {
  76         /* We maintain memory alignment to word boundaries by requiring that all
  77                 allocations be in multiples of the machine wordsize.  */
  78           /* Size of machine word in bytes.  Must be power of 2. */
  79         /* Minimum number of bytes requested at a time from     the system.  Must be multiple of WORDSIZE. */
  80
  81
  82         int     remaining;  /* Number of bytes left in current block of storage. */
  83         void*   base;     /* Pointer to base of current block of storage. */
  84         void*   loc;      /* Current location in block to next allocate memory. */
  85         int     blocksize;
  86
  87
  88 public:
  89         int     usedMemory;
  90         int     wastedMemory;
  91
  92         /**
  93                 Default constructor. Initializes a new pool.
  94         */
  95         PooledAllocator(int blocksize = BLOCKSIZE)
  96         {
  97         this->blocksize = blocksize;
  98                 remaining = 0;
  99                 base = NULL;
 100
 101                 usedMemory = 0;
 102                 wastedMemory = 0;
 103         }
 104
 105         /**
 106          * Destructor. Frees all the memory allocated in this pool.
 107          */
 108         ~PooledAllocator()
 109         {
 110                 void *prev;
 111
 112                 while (base != NULL) {
 113                         prev = *((void **) base);  /* Get pointer to prev block. */
 114                         ::free(base);
 115                         base = prev;
 116                 }
 117         }
 118
 119         /**
 120          * Returns a pointer to a piece of new memory of the given size in bytes
 121          * allocated from the pool.
 122          */
 123         void* malloc(int size)
 124         {
 125                 int blocksize;
 126
 127                 /* Round size up to a multiple of wordsize.  The following expression
 128                         only works for WORDSIZE that is a power of 2, by masking last bits of
 129                         incremented size to zero.
 130                 */
 131                 size = (size + (WORDSIZE - 1)) & ~(WORDSIZE - 1);
 132
 133                 /* Check whether a new block must be allocated.  Note that the first word
 134                         of a block is reserved for a pointer to the previous block.
 135                 */
 136                 if (size > remaining) {
 137
 138                         wastedMemory += remaining;
 139
 140                 /* Allocate new storage. */
 141                         blocksize = (size + sizeof(void*) + (WORDSIZE-1) > BLOCKSIZE) ?
 142                                                 size + sizeof(void*) + (WORDSIZE-1) : BLOCKSIZE;
 143
 144                         // use the standard C malloc to allocate memory
 145                         void* m = ::malloc(blocksize);
 146                         if (!m) {
 147                 fprintf(stderr,"Failed to allocate memory.");
 148                 exit(1);
 149                         }
 150
 151                         /* Fill first word of new block with pointer to previous block. */
 152                         ((void **) m)[0] = base;
 153                         base = m;
 154
 155                         int shift = 0;
 156                         //int shift = (WORDSIZE - ( (((size_t)m) + sizeof(void*)) & (WORDSIZE-1))) & (WORDSIZE-1);
 157
 158                         remaining = blocksize - sizeof(void*) - shift;
 159                         loc = ((char*)m + sizeof(void*) + shift);
 160                 }
 161                 void* rloc = loc;
 162                 loc = (char*)loc + size;
 163                 remaining -= size;
 164
 165                 usedMemory += size;
 166
 167                 return rloc;
 168         }
 169
 170         /**
 171          * Allocates (using this pool) a generic type T.
 172          *
 173          * Params:
 174          *     count = number of instances to allocate.
 175          * Returns: pointer (of type T*) to memory buffer
 176          */
 177     template <typename T>
 178         T* allocate(size_t count = 1)
 179         {
 180                 T* mem = (T*) this->malloc(sizeof(T)*count);
 181                 return mem;
 182         }
 183
 184 };
 185
 186 }
 187
 188 #endif //ALLOCATOR_H