1 /***********************************************************************
2 * Software License Agreement (BSD License)
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.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
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.
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 *************************************************************************/
42 * Allocates (using C's malloc) a generic type T.
45 * count = number of instances to allocate.
46 * Returns: pointer (of type T*) to memory buffer
49 T* allocate(size_t count = 1)
51 T* mem = (T*) ::malloc(sizeof(T)*count);
57 * Pooled storage allocator
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.
71 const size_t WORDSIZE=16;
72 const size_t BLOCKSIZE=8192;
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. */
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. */
93 Default constructor. Initializes a new pool.
95 PooledAllocator(int blocksize = BLOCKSIZE)
97 this->blocksize = blocksize;
106 * Destructor. Frees all the memory allocated in this pool.
112 while (base != NULL) {
113 prev = *((void **) base); /* Get pointer to prev block. */
120 * Returns a pointer to a piece of new memory of the given size in bytes
121 * allocated from the pool.
123 void* malloc(int size)
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.
131 size = (size + (WORDSIZE - 1)) & ~(WORDSIZE - 1);
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.
136 if (size > remaining) {
138 wastedMemory += remaining;
140 /* Allocate new storage. */
141 blocksize = (size + sizeof(void*) + (WORDSIZE-1) > BLOCKSIZE) ?
142 size + sizeof(void*) + (WORDSIZE-1) : BLOCKSIZE;
144 // use the standard C malloc to allocate memory
145 void* m = ::malloc(blocksize);
147 fprintf(stderr,"Failed to allocate memory.");
151 /* Fill first word of new block with pointer to previous block. */
152 ((void **) m)[0] = base;
156 //int shift = (WORDSIZE - ( (((size_t)m) + sizeof(void*)) & (WORDSIZE-1))) & (WORDSIZE-1);
158 remaining = blocksize - sizeof(void*) - shift;
159 loc = ((char*)m + sizeof(void*) + shift);
162 loc = (char*)loc + size;
171 * Allocates (using this pool) a generic type T.
174 * count = number of instances to allocate.
175 * Returns: pointer (of type T*) to memory buffer
177 template <typename T>
178 T* allocate(size_t count = 1)
180 T* mem = (T*) this->malloc(sizeof(T)*count);