OpenCV 2.4.8 components for OpenCVgrabber.
[mmanager-3rdparty.git] / OpenCV2.4.8 / build / include / opencv2 / flann / 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 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
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* 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 //OPENCV_FLANN_ALLOCATOR_H_