Geogram Version 1.8.5
A programming library of geometric algorithms
Loading...
Searching...
No Matches
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
48#include <vector>
49#include <string.h>
50#include <stdlib.h>
51
52#ifdef GEO_OS_WINDOWS
53
54#include <windows.h>
55#ifdef min
56#undef min
57#endif
58#ifdef max
59#undef max
60#endif
61
62#else
63
64#include <unistd.h>
65
66#endif
67
73namespace GEO {
74
78 namespace Memory {
80 typedef unsigned char byte;
81
83 typedef unsigned char word8;
84
86 typedef unsigned short word16;
87
89 typedef unsigned int word32;
90
92 typedef byte* pointer;
93
95 typedef void (*function_pointer)();
96
104 inline void clear(void* addr, size_t size) {
105 ::memset(addr, 0, size);
106 }
107
117 inline void copy(void* to, const void* from, size_t size) {
118 ::memcpy(to, from, size);
119 }
120
132 ) {
133 // I know this is ugly, but I did not find a simpler warning-free
134 // way that is portable between all compilers.
135 pointer result = nullptr;
136 ::memcpy(&result, &fptr, sizeof(pointer));
137 return result;
138 }
139
150 pointer ptr
151 ) {
152 // I know this is ugly, but I did not find a simpler warning-free
153 // way that is portable between all compilers.
154 function_pointer result = nullptr;
155 ::memcpy(&result, &ptr, sizeof(pointer));
156 return result;
157 }
158
169 // I know this is ugly, but I did not find a simpler warning-free
170 // way that is portable between all compilers.
171 function_pointer result = nullptr;
172 ::memcpy(&result, &ptr, sizeof(pointer));
173 return result;
174 }
175
184#define GEO_MEMORY_ALIGNMENT 64
185
196 template <int DIM>
202 static const size_t value = 1;
203 };
204
209 template <>
210 struct PointAlignment<2> {
211 static const size_t value = 16;
212 };
213
218 template <>
219 struct PointAlignment<3> {
220 static const size_t value = 8;
221 };
222
227 template <>
228 struct PointAlignment<4> {
229 static const size_t value = 32;
230 };
231
236 template <>
237 struct PointAlignment<6> {
238 static const size_t value = 16;
239 };
240
245 template <>
246 struct PointAlignment<8> {
247 static const size_t value = 64;
248 };
249
258#define geo_dim_alignment(dim) GEO::Memory::PointAlignment<dim>::value
259
269 inline void* aligned_malloc(
270 size_t size, size_t alignment = GEO_MEMORY_ALIGNMENT
271 ) {
272#if defined(GEO_OS_ANDROID)
273 // Alignment not supported under Android.
274 geo_argused(alignment);
275 return malloc(size);
276#elif defined(GEO_COMPILER_INTEL)
277 return _mm_malloc(size, alignment);
278#elif defined(GEO_COMPILER_GCC) || defined(GEO_COMPILER_CLANG)
279 void* result;
280 return posix_memalign(&result, alignment, size) == 0
281 ? result : nullptr;
282#elif defined(GEO_COMPILER_MSVC)
283 return _aligned_malloc(size, alignment);
284#else
285 geo_argused(alignment);
286 return malloc(size);
287#endif
288 }
289
297 inline void aligned_free(void* p) {
298#if defined(GEO_OS_ANDROID)
299 // Alignment not supported under Android.
300 free(p);
301#elif defined(GEO_COMPILER_INTEL)
302 _mm_free(p);
303#elif defined(GEO_COMPILER_GCC_FAMILY)
304 free(p);
305#elif defined(GEO_COMPILER_MSVC)
306 _aligned_free(p);
307#else
308 free(p);
309#endif
310 }
311
325#if defined(GEO_OS_ANDROID)
326#define geo_decl_aligned(var) var
327#elif defined(GEO_COMPILER_INTEL)
328#define geo_decl_aligned(var) __declspec(aligned(GEO_MEMORY_ALIGNMENT)) var
329#elif defined(GEO_COMPILER_GCC_FAMILY)
330#define geo_decl_aligned(var) var __attribute__((aligned(GEO_MEMORY_ALIGNMENT)))
331#elif defined(GEO_COMPILER_MSVC)
332#define geo_decl_aligned(var) __declspec(align(GEO_MEMORY_ALIGNMENT)) var
333#elif defined(GEO_COMPILER_EMSCRIPTEN)
334#define geo_decl_aligned(var) var
335#endif
336
352#if defined(GEO_OS_ANDROID)
353#define geo_assume_aligned(var, alignment)
354#elif defined(GEO_COMPILER_INTEL)
355#define geo_assume_aligned(var, alignment) \
356 __assume_aligned(var, alignment)
357#elif defined(GEO_COMPILER_CLANG)
358#define geo_assume_aligned(var, alignment)
359 // GCC __builtin_assume_aligned is not yet supported by clang-3.3
360#elif defined(GEO_COMPILER_GCC)
361#if __GNUC__ >= 4 && __GNUC_MINOR__ >= 7
362#define geo_assume_aligned(var, alignment) \
363 *(void**) (&var) = __builtin_assume_aligned(var, alignment)
364 // the GCC way of specifying that a pointer is aligned returns
365 // the aligned pointer (I can't figure out why). It needs to be
366 // affected otherwise it is not taken into account (verified by
367 // looking at the output of gcc -S)
368#else
369#define geo_assume_aligned(var, alignment)
370#endif
371#elif defined(GEO_COMPILER_MSVC)
372#define geo_assume_aligned(var, alignment)
373 // TODO: I do not know how to do that with MSVC
374#elif defined(GEO_COMPILER_EMSCRIPTEN)
375#define geo_assume_aligned(var, alignment)
376#elif defined(GEO_COMPILER_MINGW)
377#define geo_assume_aligned(var, alignment)
378#endif
379
390#if defined(GEO_COMPILER_INTEL)
391#define geo_restrict __restrict
392#elif defined(GEO_COMPILER_GCC_FAMILY)
393#define geo_restrict __restrict__
394#elif defined(GEO_COMPILER_MSVC)
395#define geo_restrict __restrict
396#elif defined(GEO_COMPILER_EMSCRIPTEN)
397#define geo_restrict
398#endif
399
407 inline bool is_aligned(
408 void* p, size_t alignment = GEO_MEMORY_ALIGNMENT
409 ) {
410 return (reinterpret_cast<size_t>(p) & (alignment - 1)) == 0;
411 }
412
416 inline void* align(void* p) {
417 size_t offset = (
419 (reinterpret_cast<size_t>(p) & (GEO_MEMORY_ALIGNMENT - 1))
420 ) & (GEO_MEMORY_ALIGNMENT - 1);
421 return reinterpret_cast<char*>(p) + offset;
422 }
423
433#define geo_aligned_alloca(size) \
434 GEO::Memory::align(alloca(size + GEO_MEMORY_ALIGNMENT - 1))
435
443 template <class T, int ALIGN = GEO_MEMORY_ALIGNMENT>
445 public:
447 typedef T value_type;
448
450 typedef T* pointer;
451
453 typedef T& reference;
454
456 typedef const T* const_pointer;
457
459 typedef const T& const_reference;
460
462 typedef ::std::size_t size_type;
463
465 typedef ::std::ptrdiff_t difference_type;
466
471 template <class U>
472 struct rebind {
475 };
476
483 return &x;
484 }
485
492 return &x;
493 }
494
513 size_type nb_elt, const void* hint = nullptr
514 ) {
515 geo_argused(hint);
516 pointer result = static_cast<pointer>(
517 aligned_malloc(sizeof(T) * nb_elt, ALIGN)
518 );
519 return result;
520 }
521
533 void deallocate(pointer p, size_type nb_elt) {
534 geo_argused(nb_elt);
535 aligned_free(p);
536 }
537
545 ::std::allocator<char> a;
546 return std::allocator_traits<decltype(a)>::max_size(a) / sizeof(T);
547 }
548
562 new (static_cast<void*>(p))value_type(val);
563 }
564
573 void destroy(pointer p) {
574 p->~value_type();
575#ifdef GEO_COMPILER_MSVC
576 (void) p; // to avoid a "unreferenced variable" warning
577#endif
578 }
579
584 template <class T2, int A2> operator aligned_allocator<T2, A2>() {
586 }
587 };
588
593 template <typename T1, int A1, typename T2, int A2>
594 inline bool operator== (
596 ) {
597 return true;
598 }
599
604 template <typename T1, int A1, typename T2, int A2>
605 inline bool operator!= (
607 ) {
608 return false;
609 }
610 }
611
612 /************************************************************************/
613
622 template <class T>
623 class vector : public ::std::vector<T, Memory::aligned_allocator<T> > {
627 typedef ::std::vector<T, Memory::aligned_allocator<T> > baseclass;
628
629 public:
634 baseclass() {
635 }
636
643 explicit vector(index_t size) :
644 baseclass(size) {
645 }
646
654 explicit vector(index_t size, const T& val) :
655 baseclass(size, val) {
656 }
657
662 index_t size() const {
663 // casts baseclass::size() from size_t (64 bits)
664 // to index_t (32 bits), because all
665 // indices in Vorpaline are supposed to fit in 32 bits (index_t).
666 // TODO: geo_debug_assert(baseclass::size() < max index_t)
667 return index_t(baseclass::size());
668 }
669
676 geo_debug_assert(i < size());
677 return baseclass::operator[] (i);
678 }
679
686 const T& operator[] (index_t i) const {
687 geo_debug_assert(i < size());
688 return baseclass::operator[] (i);
689 }
690
697 geo_debug_assert(i >= 0 && index_t(i) < size());
698 return baseclass::operator[] (index_t(i));
699 }
700
707 const T& operator[] (signed_index_t i) const {
708 geo_debug_assert(i >= 0 && index_t(i) < size());
709 return baseclass::operator[] (index_t(i));
710 }
711
712
713#ifdef GARGANTUA // If compiled with 64 bits index_t
714
720 T& operator[] (int i) {
721 geo_debug_assert(i >= 0 && index_t(i) < size());
722 return baseclass::operator[] (index_t(i));
723 }
724
731 const T& operator[] (int i) const {
732 geo_debug_assert(i >= 0 && index_t(i) < size());
733 return baseclass::operator[] (index_t(i));
734 }
735
741 T& operator[] (unsigned int i) {
742 geo_debug_assert(i >= 0 && index_t(i) < size());
743 return baseclass::operator[] (index_t(i));
744 }
745
752 const T& operator[] (unsigned int i) const {
753 geo_debug_assert(i >= 0 && index_t(i) < size());
754 return baseclass::operator[] (index_t(i));
755 }
756#endif
757
762 T* data() {
763 return size() == 0 ? nullptr : &(*this)[0];
764 }
765
770 const T* data() const {
771 return size() == 0 ? nullptr : &(*this)[0];
772 }
773
774 };
775
782 template <>
783 class vector<bool> : public ::std::vector<bool> {
784 typedef ::std::vector<bool> baseclass;
785
786 public:
789 baseclass() {
790 }
791
793 explicit vector(index_t size) :
794 baseclass(size) {
795 }
796
798 explicit vector(index_t size, bool val) :
799 baseclass(size, val) {
800 }
801
803 index_t size() const {
804 // casts baseclass::size() from size_t (64 bits)
805 // to index_t (32 bits), because all
806 // indices in Vorpaline are supposed to fit in 32 bits (index_t).
807 // TODO: geo_debug_assert(baseclass::size() < max index_t)
808 return index_t(baseclass::size());
809 }
810
811 // TODO: operator[] with bounds checking (more complicated
812 // than just returning bool&, check implementation in STL).
813 };
814}
815
816#endif
817
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:195
Functions for atomic operations.
Common include file, providing basic definitions. Should be included before anything else by all head...
An allocator that performs aligned memory allocations.
Definition memory.h:444
size_type max_size() const
Gets the maximum size possible to allocate.
Definition memory.h:544
T * pointer
Pointer to element.
Definition memory.h:450
const T & const_reference
Reference to constant element.
Definition memory.h:459
void destroy(pointer p)
Destroys an object.
Definition memory.h:573
const T * const_pointer
Pointer to constant element.
Definition memory.h:456
pointer address(reference x)
Gets the address of an object.
Definition memory.h:482
pointer allocate(size_type nb_elt, const void *hint=nullptr)
Allocates a block of storage.
Definition memory.h:512
T value_type
Element type.
Definition memory.h:447
const_pointer address(const_reference x)
Gets the address of a object.
Definition memory.h:491
T & reference
Reference to element.
Definition memory.h:453
void construct(pointer p, const_reference val)
Constructs an object.
Definition memory.h:561
::std::size_t size_type
Quantities of elements.
Definition memory.h:462
void deallocate(pointer p, size_type nb_elt)
Releases a block of storage.
Definition memory.h:533
::std::ptrdiff_t difference_type
Difference between two pointers.
Definition memory.h:465
index_t size() const
Gets the number of elements.
Definition memory.h:803
vector(index_t size)
Creates a pre-allocated vector.
Definition memory.h:793
vector(index_t size, bool val)
Creates a pre-initialized vector.
Definition memory.h:798
vector()
Creates an empty vector.
Definition memory.h:788
Vector with aligned memory allocation.
Definition memory.h:623
vector()
Creates an empty vector.
Definition memory.h:633
const T * data() const
Gets a pointer to the array of elements.
Definition memory.h:770
vector(index_t size, const T &val)
Creates a pre-initialized vector.
Definition memory.h:654
vector(index_t size)
Creates a pre-allocated vector.
Definition memory.h:643
T * data()
Gets a pointer to the array of elements.
Definition memory.h:762
T & operator[](index_t i)
Gets a vector element.
Definition memory.h:675
index_t size() const
Gets the number of elements.
Definition memory.h:662
#define GEO_MEMORY_ALIGNMENT
Default memory alignment for efficient vector operations.
Definition memory.h:184
void * aligned_malloc(size_t size, size_t alignment=GEO_MEMORY_ALIGNMENT)
Allocates aligned memory.
Definition memory.h:269
unsigned short word16
Unsigned 16 bits integer.
Definition memory.h:86
unsigned char byte
Unsigned byte type.
Definition memory.h:80
void(* function_pointer)()
Generic function pointer.
Definition memory.h:95
void * align(void *p)
Returns the smallest aligned memory address from p.
Definition memory.h:416
pointer function_pointer_to_generic_pointer(function_pointer fptr)
Converts a function pointer to a generic pointer.
Definition memory.h:130
void aligned_free(void *p)
Deallocates aligned memory.
Definition memory.h:297
unsigned int word32
Unsigned 32 bits integer.
Definition memory.h:89
byte * pointer
Pointer to unsigned byte(s)
Definition memory.h:92
unsigned char word8
Unsigned 8 bits integer.
Definition memory.h:83
void clear(void *addr, size_t size)
Clears a memory block.
Definition memory.h:104
bool is_aligned(void *p, size_t alignment=GEO_MEMORY_ALIGNMENT)
Checks whether a pointer is aligned.
Definition memory.h:407
bool operator!=(const aligned_allocator< T1, A1 > &, const aligned_allocator< T2, A2 > &)
Tests whether two aligned_allocators are different.
Definition memory.h:605
function_pointer generic_pointer_to_function_pointer(pointer ptr)
Converts a generic pointer to a function pointer.
Definition memory.h:149
bool operator==(const aligned_allocator< T1, A1 > &, const aligned_allocator< T2, A2 > &)
Tests whether two aligned_allocators are equal.
Definition memory.h:594
void copy(void *to, const void *from, size_t size)
Copies a memory block.
Definition memory.h:117
Global Vorpaline namespace.
Definition algorithm.h:64
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:301
geo_index_t index_t
The type for storing and manipulating indices.
Definition numeric.h:287
Types and functions for numbers manipulation.
Functions for string manipulation.
Defines the memory alignment of points in a vector.
Definition memory.h:197
static const size_t value
Alignment value in bytes.
Definition memory.h:202
Defines the same allocator for other types.
Definition memory.h:472
aligned_allocator< U > other
Definition memory.h:474