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
38namespace 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 */
48template <typename T>
49T* 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
71const size_t     WORDSIZE=16;
72const  size_t     BLOCKSIZE=8192;
73
74class 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
88public:
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_
189