Merge of itasc branch. Project files, scons and cmake should be working. Makefile...
[blender.git] / extern / Eigen2 / Eigen / src / Core / util / Memory.h
1 // This file is part of Eigen, a lightweight C++ template library
2 // for linear algebra. Eigen itself is part of the KDE project.
3 //
4 // Copyright (C) 2008 Gael Guennebaud <g.gael@free.fr>
5 // Copyright (C) 2008-2009 Benoit Jacob <jacob.benoit.1@gmail.com>
6 // Copyright (C) 2009 Kenneth Riddile <kfriddile@yahoo.com>
7 //
8 // Eigen is free software; you can redistribute it and/or
9 // modify it under the terms of the GNU Lesser General Public
10 // License as published by the Free Software Foundation; either
11 // version 3 of the License, or (at your option) any later version.
12 //
13 // Alternatively, you can redistribute it and/or
14 // modify it under the terms of the GNU General Public License as
15 // published by the Free Software Foundation; either version 2 of
16 // the License, or (at your option) any later version.
17 //
18 // Eigen is distributed in the hope that it will be useful, but WITHOUT ANY
19 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
20 // FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License or the
21 // GNU General Public License for more details.
22 //
23 // You should have received a copy of the GNU Lesser General Public
24 // License and a copy of the GNU General Public License along with
25 // Eigen. If not, see <http://www.gnu.org/licenses/>.
26
27 #ifndef EIGEN_MEMORY_H
28 #define EIGEN_MEMORY_H
29
30 #if defined(__APPLE__) || defined(_WIN64)
31   #define EIGEN_MALLOC_ALREADY_ALIGNED 1
32 #else
33   #define EIGEN_MALLOC_ALREADY_ALIGNED 0
34 #endif
35
36 #if ((defined _GNU_SOURCE) || ((defined _XOPEN_SOURCE) && (_XOPEN_SOURCE >= 600))) && (defined _POSIX_ADVISORY_INFO) && (_POSIX_ADVISORY_INFO > 0)
37   #define EIGEN_HAS_POSIX_MEMALIGN 1
38 #else
39   #define EIGEN_HAS_POSIX_MEMALIGN 0
40 #endif
41
42 #ifdef EIGEN_VECTORIZE_SSE
43   #define EIGEN_HAS_MM_MALLOC 1
44 #else
45   #define EIGEN_HAS_MM_MALLOC 0
46 #endif
47
48 /** \internal like malloc, but the returned pointer is guaranteed to be 16-byte aligned.
49   * Fast, but wastes 16 additional bytes of memory.
50   * Does not throw any exception.
51   */
52 inline void* ei_handmade_aligned_malloc(size_t size)
53 {
54   void *original = malloc(size+16);
55   void *aligned = reinterpret_cast<void*>((reinterpret_cast<size_t>(original) & ~(size_t(15))) + 16);
56   *(reinterpret_cast<void**>(aligned) - 1) = original;
57   return aligned;
58 }
59
60 /** \internal frees memory allocated with ei_handmade_aligned_malloc */
61 inline void ei_handmade_aligned_free(void *ptr)
62 {
63   if(ptr)
64     free(*(reinterpret_cast<void**>(ptr) - 1));
65 }
66
67 /** \internal allocates \a size bytes. The returned pointer is guaranteed to have 16 bytes alignment.
68   * On allocation error, the returned pointer is undefined, but if exceptions are enabled then a std::bad_alloc is thrown.
69   */
70 inline void* ei_aligned_malloc(size_t size)
71 {
72   #ifdef EIGEN_NO_MALLOC
73     ei_assert(false && "heap allocation is forbidden (EIGEN_NO_MALLOC is defined)");
74   #endif
75
76   void *result;  
77   #if !EIGEN_ALIGN
78     result = malloc(size);
79   #elif EIGEN_MALLOC_ALREADY_ALIGNED
80     result = malloc(size);
81   #elif EIGEN_HAS_POSIX_MEMALIGN
82     if(posix_memalign(&result, 16, size)) result = 0;
83   #elif EIGEN_HAS_MM_MALLOC
84     result = _mm_malloc(size, 16);
85   #elif (defined _MSC_VER)
86     result = _aligned_malloc(size, 16);
87   #else
88     result = ei_handmade_aligned_malloc(size);
89   #endif
90     
91   #ifdef EIGEN_EXCEPTIONS
92     if(result == 0)
93       throw std::bad_alloc();
94   #endif
95   return result;
96 }
97
98 /** allocates \a size bytes. If Align is true, then the returned ptr is 16-byte-aligned.
99   * On allocation error, the returned pointer is undefined, but if exceptions are enabled then a std::bad_alloc is thrown.
100   */
101 template<bool Align> inline void* ei_conditional_aligned_malloc(size_t size)
102 {
103   return ei_aligned_malloc(size);
104 }
105
106 template<> inline void* ei_conditional_aligned_malloc<false>(size_t size)
107 {
108   #ifdef EIGEN_NO_MALLOC
109     ei_assert(false && "heap allocation is forbidden (EIGEN_NO_MALLOC is defined)");
110   #endif
111
112   void *result = malloc(size);
113   #ifdef EIGEN_EXCEPTIONS
114     if(!result) throw std::bad_alloc();
115   #endif
116   return result;
117 }
118
119 /** allocates \a size objects of type T. The returned pointer is guaranteed to have 16 bytes alignment.
120   * On allocation error, the returned pointer is undefined, but if exceptions are enabled then a std::bad_alloc is thrown.
121   * The default constructor of T is called.
122   */
123 template<typename T> inline T* ei_aligned_new(size_t size)
124 {
125   void *void_result = ei_aligned_malloc(sizeof(T)*size);
126   return ::new(void_result) T[size];
127 }
128
129 template<typename T, bool Align> inline T* ei_conditional_aligned_new(size_t size)
130 {
131   void *void_result = ei_conditional_aligned_malloc<Align>(sizeof(T)*size);
132   return ::new(void_result) T[size];
133 }
134
135 /** \internal free memory allocated with ei_aligned_malloc
136   */
137 inline void ei_aligned_free(void *ptr)
138 {
139   #if !EIGEN_ALIGN
140     free(ptr);
141   #elif EIGEN_MALLOC_ALREADY_ALIGNED
142     free(ptr);
143   #elif EIGEN_HAS_POSIX_MEMALIGN
144     free(ptr);
145   #elif EIGEN_HAS_MM_MALLOC
146     _mm_free(ptr);
147   #elif defined(_MSC_VER)
148     _aligned_free(ptr);
149   #else
150     ei_handmade_aligned_free(ptr);
151   #endif
152 }
153
154 /** \internal free memory allocated with ei_conditional_aligned_malloc
155   */
156 template<bool Align> inline void ei_conditional_aligned_free(void *ptr)
157 {
158   ei_aligned_free(ptr);
159 }
160
161 template<> inline void ei_conditional_aligned_free<false>(void *ptr)
162 {
163   free(ptr);
164 }
165
166 /** \internal delete the elements of an array.
167   * The \a size parameters tells on how many objects to call the destructor of T.
168   */
169 template<typename T> inline void ei_delete_elements_of_array(T *ptr, size_t size)
170 {
171   // always destruct an array starting from the end.
172   while(size) ptr[--size].~T();
173 }
174
175 /** \internal delete objects constructed with ei_aligned_new
176   * The \a size parameters tells on how many objects to call the destructor of T.
177   */
178 template<typename T> inline void ei_aligned_delete(T *ptr, size_t size)
179 {
180   ei_delete_elements_of_array<T>(ptr, size);
181   ei_aligned_free(ptr);
182 }
183
184 /** \internal delete objects constructed with ei_conditional_aligned_new
185   * The \a size parameters tells on how many objects to call the destructor of T.
186   */
187 template<typename T, bool Align> inline void ei_conditional_aligned_delete(T *ptr, size_t size)
188 {
189   ei_delete_elements_of_array<T>(ptr, size);
190   ei_conditional_aligned_free<Align>(ptr);
191 }
192
193 /** \internal \returns the number of elements which have to be skipped such that data are 16 bytes aligned */
194 template<typename Scalar>
195 inline static int ei_alignmentOffset(const Scalar* ptr, int maxOffset)
196 {
197   typedef typename ei_packet_traits<Scalar>::type Packet;
198   const int PacketSize = ei_packet_traits<Scalar>::size;
199   const int PacketAlignedMask = PacketSize-1;
200   const bool Vectorized = PacketSize>1;
201   return Vectorized
202           ? std::min<int>( (PacketSize - (int((size_t(ptr)/sizeof(Scalar))) & PacketAlignedMask))
203                            & PacketAlignedMask, maxOffset)
204           : 0;
205 }
206
207 /** \internal
208   * ei_aligned_stack_alloc(SIZE) allocates an aligned buffer of SIZE bytes
209   * on the stack if SIZE is smaller than EIGEN_STACK_ALLOCATION_LIMIT.
210   * Otherwise the memory is allocated on the heap.
211   * Data allocated with ei_aligned_stack_alloc \b must be freed by calling ei_aligned_stack_free(PTR,SIZE).
212   * \code
213   * float * data = ei_aligned_stack_alloc(float,array.size());
214   * // ...
215   * ei_aligned_stack_free(data,float,array.size());
216   * \endcode
217   */
218 #ifdef __linux__
219   #define ei_aligned_stack_alloc(SIZE) (SIZE<=EIGEN_STACK_ALLOCATION_LIMIT) \
220                                     ? alloca(SIZE) \
221                                     : ei_aligned_malloc(SIZE)
222   #define ei_aligned_stack_free(PTR,SIZE) if(SIZE>EIGEN_STACK_ALLOCATION_LIMIT) ei_aligned_free(PTR)
223 #else
224   #define ei_aligned_stack_alloc(SIZE) ei_aligned_malloc(SIZE)
225   #define ei_aligned_stack_free(PTR,SIZE) ei_aligned_free(PTR)
226 #endif
227
228 #define ei_aligned_stack_new(TYPE,SIZE) ::new(ei_aligned_stack_alloc(sizeof(TYPE)*SIZE)) TYPE[SIZE]
229 #define ei_aligned_stack_delete(TYPE,PTR,SIZE) do {ei_delete_elements_of_array<TYPE>(PTR, SIZE); \
230                                                    ei_aligned_stack_free(PTR,sizeof(TYPE)*SIZE);} while(0)
231
232
233 #if EIGEN_ALIGN
234   #ifdef EIGEN_EXCEPTIONS
235     #define EIGEN_MAKE_ALIGNED_OPERATOR_NEW_NOTHROW(NeedsToAlign) \
236       void* operator new(size_t size, const std::nothrow_t&) throw() { \
237         try { return Eigen::ei_conditional_aligned_malloc<NeedsToAlign>(size); } \
238         catch (...) { return 0; } \
239         return 0; \
240       }
241   #else
242     #define EIGEN_MAKE_ALIGNED_OPERATOR_NEW_NOTHROW(NeedsToAlign) \
243       void* operator new(size_t size, const std::nothrow_t&) throw() { \
244         return Eigen::ei_conditional_aligned_malloc<NeedsToAlign>(size); \
245       }
246   #endif
247   
248   #define EIGEN_MAKE_ALIGNED_OPERATOR_NEW_IF(NeedsToAlign) \
249       void *operator new(size_t size) { \
250         return Eigen::ei_conditional_aligned_malloc<NeedsToAlign>(size); \
251       } \
252       void *operator new[](size_t size) { \
253         return Eigen::ei_conditional_aligned_malloc<NeedsToAlign>(size); \
254       } \
255       void operator delete(void * ptr) throw() { Eigen::ei_conditional_aligned_free<NeedsToAlign>(ptr); } \
256       void operator delete[](void * ptr) throw() { Eigen::ei_conditional_aligned_free<NeedsToAlign>(ptr); } \
257       /* in-place new and delete. since (at least afaik) there is no actual   */ \
258       /* memory allocated we can safely let the default implementation handle */ \
259       /* this particular case. */ \
260       static void *operator new(size_t size, void *ptr) { return ::operator new(size,ptr); } \
261       void operator delete(void * memory, void *ptr) throw() { return ::operator delete(memory,ptr); } \
262       /* nothrow-new (returns zero instead of std::bad_alloc) */ \
263       EIGEN_MAKE_ALIGNED_OPERATOR_NEW_NOTHROW(NeedsToAlign) \
264       void operator delete(void *ptr, const std::nothrow_t&) throw() { \
265         Eigen::ei_conditional_aligned_free<NeedsToAlign>(ptr); \
266       } \
267       typedef void ei_operator_new_marker_type;
268 #else
269   #define EIGEN_MAKE_ALIGNED_OPERATOR_NEW_IF(NeedsToAlign)
270 #endif
271
272 #define EIGEN_MAKE_ALIGNED_OPERATOR_NEW EIGEN_MAKE_ALIGNED_OPERATOR_NEW_IF(true)
273 #define EIGEN_MAKE_ALIGNED_OPERATOR_NEW_IF_VECTORIZABLE_FIXED_SIZE(Scalar,Size) \
274   EIGEN_MAKE_ALIGNED_OPERATOR_NEW_IF(((Size)!=Eigen::Dynamic) && ((sizeof(Scalar)*(Size))%16==0))
275
276
277 /** \class aligned_allocator
278 *
279 * \brief stl compatible allocator to use with with 16 byte aligned types
280 *
281 * Example:
282 * \code
283 * // Matrix4f requires 16 bytes alignment:
284 * std::map< int, Matrix4f, std::less<int>, aligned_allocator<Matrix4f> > my_map_mat4;
285 * // Vector3f does not require 16 bytes alignment, no need to use Eigen's allocator:
286 * std::map< int, Vector3f > my_map_vec3;
287 * \endcode
288 *
289 */
290 template<class T>
291 class aligned_allocator
292 {
293 public:
294     typedef size_t    size_type;
295     typedef ptrdiff_t difference_type;
296     typedef T*        pointer;
297     typedef const T*  const_pointer;
298     typedef T&        reference;
299     typedef const T&  const_reference;
300     typedef T         value_type;
301
302     template<class U>
303     struct rebind
304     {
305         typedef aligned_allocator<U> other;
306     };
307
308     pointer address( reference value ) const
309     {
310         return &value;
311     }
312
313     const_pointer address( const_reference value ) const
314     {
315         return &value;
316     }
317
318     aligned_allocator() throw()
319     {
320     }
321
322     aligned_allocator( const aligned_allocator& ) throw()
323     {
324     }
325
326     template<class U>
327     aligned_allocator( const aligned_allocator<U>& ) throw()
328     {
329     }
330
331     ~aligned_allocator() throw()
332     {
333     }
334
335     size_type max_size() const throw()
336     {
337         return std::numeric_limits<size_type>::max();
338     }
339
340     pointer allocate( size_type num, const_pointer* hint = 0 )
341     {
342         static_cast<void>( hint ); // suppress unused variable warning
343         return static_cast<pointer>( ei_aligned_malloc( num * sizeof(T) ) );
344     }
345
346     void construct( pointer p, const T& value )
347     {
348         ::new( p ) T( value );
349     }
350
351     void destroy( pointer p )
352     {
353         p->~T();
354     }
355
356     void deallocate( pointer p, size_type /*num*/ )
357     {
358         ei_aligned_free( p );
359     }
360     
361     bool operator!=(const aligned_allocator<T>& other) const
362     { return false; }
363     
364     bool operator==(const aligned_allocator<T>& other) const
365     { return true; }
366 };
367
368 #endif // EIGEN_MEMORY_H