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 FLANN_ALLOCATOR_H_ 32 #define FLANN_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 */ ~PooledAllocator()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 */ allocateMemory(int size)123 void* allocateMemory(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.\n"); 148 return NULL; 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->allocateMemory((int)(sizeof(T)*count)); 181 return mem; 182 } 183 184 }; 185 186 } 187 188 #endif //FLANN_ALLOCATOR_H_ 189