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 OPENCV_FLANN_ALLOCATOR_H_
32 #define OPENCV_FLANN_ALLOCATOR_H_
33 
34 #include <stdlib.h>
35 #include <stdio.h>
36 
37 
38 namespace cvflann
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         blocksize = blockSize;
98         remaining = 0;
99         base = NULL;
100         loc = NULL;
101 
102         usedMemory = 0;
103         wastedMemory = 0;
104     }
105 
106     /**
107      * Destructor. Frees all the memory allocated in this pool.
108      */
~PooledAllocator()109     ~PooledAllocator()
110     {
111         void* prev;
112 
113         while (base != NULL) {
114             prev = *((void**) base); /* Get pointer to prev block. */
115             ::free(base);
116             base = prev;
117         }
118     }
119 
120     /**
121      * Returns a pointer to a piece of new memory of the given size in bytes
122      * allocated from the pool.
123      */
allocateMemory(int size)124     void* allocateMemory(int size)
125     {
126         int blockSize;
127 
128         /* Round size up to a multiple of wordsize.  The following expression
129             only works for WORDSIZE that is a power of 2, by masking last bits of
130             incremented size to zero.
131          */
132         size = (size + (WORDSIZE - 1)) & ~(WORDSIZE - 1);
133 
134         /* Check whether a new block must be allocated.  Note that the first word
135             of a block is reserved for a pointer to the previous block.
136          */
137         if (size > remaining) {
138 
139             wastedMemory += remaining;
140 
141             /* Allocate new storage. */
142             blockSize = (size + sizeof(void*) + (WORDSIZE-1) > BLOCKSIZE) ?
143                         size + sizeof(void*) + (WORDSIZE-1) : BLOCKSIZE;
144 
145             // use the standard C malloc to allocate memory
146             void* m = ::malloc(blockSize);
147             if (!m) {
148                 fprintf(stderr,"Failed to allocate memory.\n");
149                 return NULL;
150             }
151 
152             /* Fill first word of new block with pointer to previous block. */
153             ((void**) m)[0] = base;
154             base = m;
155 
156             int shift = 0;
157             //int shift = (WORDSIZE - ( (((size_t)m) + sizeof(void*)) & (WORDSIZE-1))) & (WORDSIZE-1);
158 
159             remaining = blockSize - sizeof(void*) - shift;
160             loc = ((char*)m + sizeof(void*) + shift);
161         }
162         void* rloc = loc;
163         loc = (char*)loc + size;
164         remaining -= size;
165 
166         usedMemory += size;
167 
168         return rloc;
169     }
170 
171     /**
172      * Allocates (using this pool) a generic type T.
173      *
174      * Params:
175      *     count = number of instances to allocate.
176      * Returns: pointer (of type T*) to memory buffer
177      */
178     template <typename T>
179     T* allocate(size_t count = 1)
180     {
181         T* mem = (T*) this->allocateMemory((int)(sizeof(T)*count));
182         return mem;
183     }
184 
185 private:
186     PooledAllocator(const PooledAllocator &); // copy disabled
187     PooledAllocator& operator=(const PooledAllocator &); // assign disabled
188 };
189 
190 }
191 
192 #endif //OPENCV_FLANN_ALLOCATOR_H_
193