Geogram  Version 1.9.1
A programming library of geometric algorithms
memory.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2000-2022 Inria
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  *
8  * * Redistributions of source code must retain the above copyright notice,
9  * this list of conditions and the following disclaimer.
10  * * Redistributions in binary form must reproduce the above copyright notice,
11  * this list of conditions and the following disclaimer in the documentation
12  * and/or other materials provided with the distribution.
13  * * Neither the name of the ALICE Project-Team nor the names of its
14  * contributors may be used to endorse or promote products derived from this
15  * software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27  * POSSIBILITY OF SUCH DAMAGE.
28  *
29  * Contact: Bruno Levy
30  *
31  * https://www.inria.fr/fr/bruno-levy
32  *
33  * Inria,
34  * Domaine de Voluceau,
35  * 78150 Le Chesnay - Rocquencourt
36  * FRANCE
37  *
38  */
39 
40 #ifndef GEOGRAM_BASIC_MEMORY
41 #define GEOGRAM_BASIC_MEMORY
42 
43 #include <geogram/basic/common.h>
44 #include <geogram/basic/assert.h>
45 #include <geogram/basic/numeric.h>
46 #include <geogram/basic/argused.h>
47 #include <vector>
48 #include <string.h>
49 #include <stdlib.h>
50 
51 #ifdef GEO_OS_WINDOWS
52 
53 #include <windows.h>
54 #ifdef min
55 #undef min
56 #endif
57 #ifdef max
58 #undef max
59 #endif
60 
61 #else
62 
63 #include <unistd.h>
64 
65 #endif
66 
67 // Stack size depending on OS:
68 // Linux: 10 Mb
69 // Windows: 1 Mb
70 // Mac OSX: 512 Kb
71 // GEO_HAS_BIG_STACK is defined under Linux
72 // and lets some of the functions that
73 // manipulate exact precision numbers
74 // allocate temporaries on the stack.
75 
76 #ifdef GEO_OS_LINUX
77 #define GEO_HAS_BIG_STACK
78 #endif
79 
85 namespace GEO {
86 
90  namespace Memory {
92  typedef unsigned char byte;
93 
95  typedef unsigned char word8;
96 
98  typedef unsigned short word16;
99 
101  typedef unsigned int word32;
102 
104  typedef byte* pointer;
105 
107  typedef void (*function_pointer)();
108 
116  inline void clear(void* addr, size_t size) {
117  ::memset(addr, 0, size);
118  }
119 
129  inline void copy(void* to, const void* from, size_t size) {
130  ::memcpy(to, from, size);
131  }
132 
143  function_pointer fptr
144  ) {
145  // I know this is ugly, but I did not find a simpler warning-free
146  // way that is portable between all compilers.
147  pointer result = nullptr;
148  ::memcpy(&result, &fptr, sizeof(pointer));
149  return result;
150  }
151 
162  pointer ptr
163  ) {
164  // I know this is ugly, but I did not find a simpler warning-free
165  // way that is portable between all compilers.
166  function_pointer result = nullptr;
167  ::memcpy(&result, &ptr, sizeof(pointer));
168  return result;
169  }
170 
181  // I know this is ugly, but I did not find a simpler warning-free
182  // way that is portable between all compilers.
183  function_pointer result = nullptr;
184  ::memcpy(&result, &ptr, sizeof(pointer));
185  return result;
186  }
187 
196 #define GEO_MEMORY_ALIGNMENT 64
197 
208  template <int DIM>
209  struct PointAlignment {
214  static const size_t value = 1;
215  };
216 
221  template <>
222  struct PointAlignment<2> {
223  static const size_t value = 16;
224  };
225 
230  template <>
231  struct PointAlignment<3> {
232  static const size_t value = 8;
233  };
234 
239  template <>
240  struct PointAlignment<4> {
241  static const size_t value = 32;
242  };
243 
248  template <>
249  struct PointAlignment<6> {
250  static const size_t value = 16;
251  };
252 
257  template <>
258  struct PointAlignment<8> {
259  static const size_t value = 64;
260  };
261 
270 #define geo_dim_alignment(dim) GEO::Memory::PointAlignment<dim>::value
271 
281  inline void* aligned_malloc(
282  size_t size, size_t alignment = GEO_MEMORY_ALIGNMENT
283  ) {
284 #if defined(GEO_OS_ANDROID)
285  // Alignment not supported under Android.
286  geo_argused(alignment);
287  return malloc(size);
288 #elif defined(GEO_COMPILER_INTEL)
289  return _mm_malloc(size, alignment);
290 #elif defined(GEO_COMPILER_GCC) || defined(GEO_COMPILER_CLANG)
291  void* result;
292  return posix_memalign(&result, alignment, size) == 0
293  ? result : nullptr;
294 #elif defined(GEO_COMPILER_MSVC)
295  return _aligned_malloc(size, alignment);
296 #else
297  geo_argused(alignment);
298  return malloc(size);
299 #endif
300  }
301 
309  inline void aligned_free(void* p) {
310 #if defined(GEO_OS_ANDROID)
311  // Alignment not supported under Android.
312  free(p);
313 #elif defined(GEO_COMPILER_INTEL)
314  _mm_free(p);
315 #elif defined(GEO_COMPILER_GCC_FAMILY)
316  free(p);
317 #elif defined(GEO_COMPILER_MSVC)
318  _aligned_free(p);
319 #else
320  free(p);
321 #endif
322  }
323 
337 #if defined(GEO_OS_ANDROID)
338 #define geo_decl_aligned(var) var
339 #elif defined(GEO_COMPILER_INTEL)
340 #define geo_decl_aligned(var) __declspec(aligned(GEO_MEMORY_ALIGNMENT)) var
341 #elif defined(GEO_COMPILER_GCC_FAMILY)
342 #define geo_decl_aligned(var) var __attribute__((aligned(GEO_MEMORY_ALIGNMENT)))
343 #elif defined(GEO_COMPILER_MSVC)
344 #define geo_decl_aligned(var) __declspec(align(GEO_MEMORY_ALIGNMENT)) var
345 #elif defined(GEO_COMPILER_EMSCRIPTEN)
346 #define geo_decl_aligned(var) var
347 #endif
348 
364 #if defined(GEO_OS_ANDROID)
365 #define geo_assume_aligned(var, alignment)
366 #elif defined(GEO_COMPILER_INTEL)
367 #define geo_assume_aligned(var, alignment) \
368  __assume_aligned(var, alignment)
369 #elif defined(GEO_COMPILER_CLANG)
370 #define geo_assume_aligned(var, alignment)
371  // GCC __builtin_assume_aligned is not yet supported by clang-3.3
372 #elif defined(GEO_COMPILER_GCC)
373 #if __GNUC__ >= 4 && __GNUC_MINOR__ >= 7
374 #define geo_assume_aligned(var, alignment) \
375  *(void**) (&var) = __builtin_assume_aligned(var, alignment)
376  // the GCC way of specifying that a pointer is aligned returns
377  // the aligned pointer (I can't figure out why). It needs to be
378  // affected otherwise it is not taken into account (verified by
379  // looking at the output of gcc -S)
380 #else
381 #define geo_assume_aligned(var, alignment)
382 #endif
383 #elif defined(GEO_COMPILER_MSVC)
384 #define geo_assume_aligned(var, alignment)
385  // TODO: I do not know how to do that with MSVC
386 #elif defined(GEO_COMPILER_EMSCRIPTEN)
387 #define geo_assume_aligned(var, alignment)
388 #elif defined(GEO_COMPILER_MINGW)
389 #define geo_assume_aligned(var, alignment)
390 #endif
391 
402 #if defined(GEO_COMPILER_INTEL)
403 #define geo_restrict __restrict
404 #elif defined(GEO_COMPILER_GCC_FAMILY)
405 #define geo_restrict __restrict__
406 #elif defined(GEO_COMPILER_MSVC)
407 #define geo_restrict __restrict
408 #elif defined(GEO_COMPILER_EMSCRIPTEN)
409 #define geo_restrict
410 #endif
411 
419  inline bool is_aligned(
420  void* p, size_t alignment = GEO_MEMORY_ALIGNMENT
421  ) {
422  return (reinterpret_cast<size_t>(p) & (alignment - 1)) == 0;
423  }
424 
428  inline void* align(void* p) {
429  size_t offset = (
431  (reinterpret_cast<size_t>(p) & (GEO_MEMORY_ALIGNMENT - 1))
432  ) & (GEO_MEMORY_ALIGNMENT - 1);
433  return reinterpret_cast<char*>(p) + offset;
434  }
435 
445 #define geo_aligned_alloca(size) \
446  GEO::Memory::align(alloca(size + GEO_MEMORY_ALIGNMENT - 1))
447 
455  template <class T, int ALIGN = GEO_MEMORY_ALIGNMENT>
457  public:
459  typedef T value_type;
460 
462  typedef T* pointer;
463 
465  typedef T& reference;
466 
468  typedef const T* const_pointer;
469 
471  typedef const T& const_reference;
472 
474  typedef ::std::size_t size_type;
475 
477  typedef ::std::ptrdiff_t difference_type;
478 
483  template <class U>
484  struct rebind {
487  };
488 
495  return &x;
496  }
497 
504  return &x;
505  }
506 
525  size_type nb_elt, const void* hint = nullptr
526  ) {
527  geo_argused(hint);
528  pointer result = static_cast<pointer>(
529  aligned_malloc(sizeof(T) * nb_elt, ALIGN)
530  );
531  return result;
532  }
533 
545  void deallocate(pointer p, size_type nb_elt) {
546  geo_argused(nb_elt);
547  aligned_free(p);
548  }
549 
556  size_type max_size() const {
557  ::std::allocator<char> a;
558  return std::allocator_traits<decltype(a)>::max_size(a) / sizeof(T);
559  }
560 
574  new (static_cast<void*>(p))value_type(val);
575  }
576 
585  void destroy(pointer p) {
586  p->~value_type();
587 #ifdef GEO_COMPILER_MSVC
588  (void) p; // to avoid a "unreferenced variable" warning
589 #endif
590  }
591 
596  template <class T2, int A2> operator aligned_allocator<T2, A2>() {
597  return aligned_allocator<T2,A2>();
598  }
599  };
600 
605  template <typename T1, int A1, typename T2, int A2>
606  inline bool operator== (
608  ) {
609  return true;
610  }
611 
616  template <typename T1, int A1, typename T2, int A2>
617  inline bool operator!= (
619  ) {
620  return false;
621  }
622  }
623 
624  /************************************************************************/
625 
634  template <class T>
635  class vector : public ::std::vector<T, Memory::aligned_allocator<T> > {
639  typedef ::std::vector<T, Memory::aligned_allocator<T> > baseclass;
640 
641  public:
645  vector() :
646  baseclass() {
647  }
648 
655  explicit vector(index_t size) :
656  baseclass(size) {
657  }
658 
666  explicit vector(index_t size, const T& val) :
667  baseclass(size, val) {
668  }
669 
674  index_t size() const {
675  // casts baseclass::size() from size_t (64 bits)
676  // to index_t (32 bits), because all
677  // indices in Vorpaline are supposed to fit in 32 bits (index_t).
678  // TODO: geo_debug_assert(baseclass::size() < max index_t)
679  return index_t(baseclass::size());
680  }
681 
688  geo_debug_assert(i < size());
689  return baseclass::operator[] (i);
690  }
691 
698  const T& operator[] (index_t i) const {
699  geo_debug_assert(i < size());
700  return baseclass::operator[] (i);
701  }
702 
709  geo_debug_assert(i >= 0 && index_t(i) < size());
710  return baseclass::operator[] (index_t(i));
711  }
712 
719  const T& operator[] (signed_index_t i) const {
720  geo_debug_assert(i >= 0 && index_t(i) < size());
721  return baseclass::operator[] (index_t(i));
722  }
723 
724 
725 #ifdef GARGANTUA // If compiled with 64 bits index_t
726 
732  T& operator[] (int i) {
733  geo_debug_assert(i >= 0 && index_t(i) < size());
734  return baseclass::operator[] (index_t(i));
735  }
736 
743  const T& operator[] (int i) const {
744  geo_debug_assert(i >= 0 && index_t(i) < size());
745  return baseclass::operator[] (index_t(i));
746  }
747 
753  T& operator[] (unsigned int i) {
754  geo_debug_assert(index_t(i) < size());
755  return baseclass::operator[] (index_t(i));
756  }
757 
764  const T& operator[] (unsigned int i) const {
765  geo_debug_assert(index_t(i) < size());
766  return baseclass::operator[] (index_t(i));
767  }
768 #endif
769 
774  T* data() {
775  return size() == 0 ? nullptr : &(*this)[0];
776  }
777 
782  const T* data() const {
783  return size() == 0 ? nullptr : &(*this)[0];
784  }
785 
786  };
787 
794  template <>
795  class vector<bool> : public ::std::vector<bool> {
796  typedef ::std::vector<bool> baseclass;
797 
798  public:
800  vector() :
801  baseclass() {
802  }
803 
805  explicit vector(index_t size) :
806  baseclass(size) {
807  }
808 
810  explicit vector(index_t size, bool val) :
811  baseclass(size, val) {
812  }
813 
815  index_t size() const {
816  // casts baseclass::size() from size_t (64 bits)
817  // to index_t (32 bits), because all
818  // indices in Vorpaline are supposed to fit in 32 bits (index_t).
819  // TODO: geo_debug_assert(baseclass::size() < max index_t)
820  return index_t(baseclass::size());
821  }
822 
823  // TODO: operator[] with bounds checking (more complicated
824  // than just returning bool&, check implementation in STL).
825  };
826 }
827 
828 #endif
A function to suppress unused parameters compilation warnings.
Assertion checking mechanism.
#define geo_debug_assert(x)
Verifies that a condition is met.
Definition: assert.h:196
An allocator that performs aligned memory allocations.
Definition: memory.h:456
size_type max_size() const
Gets the maximum size possible to allocate.
Definition: memory.h:556
T * pointer
Pointer to element.
Definition: memory.h:462
const T & const_reference
Reference to constant element.
Definition: memory.h:471
void destroy(pointer p)
Destroys an object.
Definition: memory.h:585
const T * const_pointer
Pointer to constant element.
Definition: memory.h:468
pointer address(reference x)
Gets the address of an object.
Definition: memory.h:494
pointer allocate(size_type nb_elt, const void *hint=nullptr)
Allocates a block of storage.
Definition: memory.h:524
T value_type
Element type.
Definition: memory.h:459
const_pointer address(const_reference x)
Gets the address of a object.
Definition: memory.h:503
T & reference
Reference to element.
Definition: memory.h:465
void construct(pointer p, const_reference val)
Constructs an object.
Definition: memory.h:573
::std::size_t size_type
Quantities of elements.
Definition: memory.h:474
void deallocate(pointer p, size_type nb_elt)
Releases a block of storage.
Definition: memory.h:545
::std::ptrdiff_t difference_type
Difference between two pointers.
Definition: memory.h:477
index_t size() const
Gets the number of elements.
Definition: memory.h:815
vector(index_t size)
Creates a pre-allocated vector.
Definition: memory.h:805
vector(index_t size, bool val)
Creates a pre-initialized vector.
Definition: memory.h:810
vector()
Creates an empty vector.
Definition: memory.h:800
Vector with aligned memory allocation.
Definition: memory.h:635
const T * data() const
Gets a pointer to the array of elements.
Definition: memory.h:782
vector()
Creates an empty vector.
Definition: memory.h:645
vector(index_t size, const T &val)
Creates a pre-initialized vector.
Definition: memory.h:666
T * data()
Gets a pointer to the array of elements.
Definition: memory.h:774
vector(index_t size)
Creates a pre-allocated vector.
Definition: memory.h:655
T & operator[](index_t i)
Gets a vector element.
Definition: memory.h:687
index_t size() const
Gets the number of elements.
Definition: memory.h:674
Common include file, providing basic definitions. Should be included before anything else by all head...
#define GEO_MEMORY_ALIGNMENT
Default memory alignment for efficient vector operations.
Definition: memory.h:196
unsigned short word16
Unsigned 16 bits integer.
Definition: memory.h:98
unsigned char byte
Unsigned byte type.
Definition: memory.h:92
void(* function_pointer)()
Generic function pointer.
Definition: memory.h:107
void * aligned_malloc(size_t size, size_t alignment=GEO_MEMORY_ALIGNMENT)
Allocates aligned memory.
Definition: memory.h:281
void * align(void *p)
Returns the smallest aligned memory address from p.
Definition: memory.h:428
pointer function_pointer_to_generic_pointer(function_pointer fptr)
Converts a function pointer to a generic pointer.
Definition: memory.h:142
void aligned_free(void *p)
Deallocates aligned memory.
Definition: memory.h:309
unsigned int word32
Unsigned 32 bits integer.
Definition: memory.h:101
byte * pointer
Pointer to unsigned byte(s)
Definition: memory.h:104
unsigned char word8
Unsigned 8 bits integer.
Definition: memory.h:95
void clear(void *addr, size_t size)
Clears a memory block.
Definition: memory.h:116
bool is_aligned(void *p, size_t alignment=GEO_MEMORY_ALIGNMENT)
Checks whether a pointer is aligned.
Definition: memory.h:419
bool operator!=(const aligned_allocator< T1, A1 > &, const aligned_allocator< T2, A2 > &)
Tests whether two aligned_allocators are different.
Definition: memory.h:617
function_pointer generic_pointer_to_function_pointer(pointer ptr)
Converts a generic pointer to a function pointer.
Definition: memory.h:161
bool operator==(const aligned_allocator< T1, A1 > &, const aligned_allocator< T2, A2 > &)
Tests whether two aligned_allocators are equal.
Definition: memory.h:606
void copy(void *to, const void *from, size_t size)
Copies a memory block.
Definition: memory.h:129
Global Vorpaline namespace.
Definition: basic.h:55
void geo_argused(const T &)
Suppresses compiler warnings about unused parameters.
Definition: argused.h:60
geo_signed_index_t signed_index_t
The type for storing and manipulating indices differences.
Definition: numeric.h:343
geo_index_t index_t
The type for storing and manipulating indices.
Definition: numeric.h:329
Types and functions for numbers manipulation.
Functions for string manipulation.
Defines the memory alignment of points in a vector.
Definition: memory.h:209
static const size_t value
Alignment value in bytes.
Definition: memory.h:214
Defines the same allocator for other types.
Definition: memory.h:484
aligned_allocator< U > other
Definition: memory.h:486