| Line | Branch | Exec | Source |
|---|---|---|---|
| 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 <new> | ||
| 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 | |||
| 68 | // Stack size depending on OS: | ||
| 69 | // Linux: 10 Mb | ||
| 70 | // Windows: 1 Mb | ||
| 71 | // Mac OSX: 512 Kb | ||
| 72 | // GEO_HAS_BIG_STACK is defined under Linux | ||
| 73 | // and lets some of the functions that | ||
| 74 | // manipulate exact precision numbers | ||
| 75 | // allocate temporaries on the stack. | ||
| 76 | |||
| 77 | #ifdef GEO_OS_LINUX | ||
| 78 | #define GEO_HAS_BIG_STACK | ||
| 79 | #endif | ||
| 80 | |||
| 81 | /** | ||
| 82 | * \file geogram/basic/memory.h | ||
| 83 | * \brief Types and functions for memory manipulation | ||
| 84 | */ | ||
| 85 | |||
| 86 | namespace GEO { | ||
| 87 | |||
| 88 | /** | ||
| 89 | * \brief Utilities for memory management. | ||
| 90 | */ | ||
| 91 | namespace Memory { | ||
| 92 | /** \brief Unsigned byte type */ | ||
| 93 | typedef unsigned char byte; | ||
| 94 | |||
| 95 | /** \brief Unsigned 8 bits integer */ | ||
| 96 | typedef unsigned char word8; | ||
| 97 | |||
| 98 | /** \brief Unsigned 16 bits integer */ | ||
| 99 | typedef unsigned short word16; | ||
| 100 | |||
| 101 | /** \brief Unsigned 32 bits integer */ | ||
| 102 | typedef unsigned int word32; | ||
| 103 | |||
| 104 | /** \brief Pointer to unsigned byte(s) */ | ||
| 105 | typedef byte* pointer; | ||
| 106 | |||
| 107 | /** \brief Const pointer to unsigned byte(s) */ | ||
| 108 | typedef const byte* const_pointer; | ||
| 109 | |||
| 110 | /** \brief Generic function pointer */ | ||
| 111 | typedef void (*function_pointer)(); | ||
| 112 | |||
| 113 | /** | ||
| 114 | * \brief Clears a memory block | ||
| 115 | * \details Clears (set to zero) the first \p size bytes of array \p | ||
| 116 | * addr. | ||
| 117 | * \param[in] addr an array of bytes | ||
| 118 | * \param[in] size the number of bytes to clear | ||
| 119 | */ | ||
| 120 | 331586 | inline void clear(void* addr, size_t size) { | |
| 121 | 331586 | ::memset(addr, 0, size); | |
| 122 | 331586 | } | |
| 123 | |||
| 124 | /** | ||
| 125 | * \brief Copies a memory block | ||
| 126 | * \details Copies the first \p size bytes of array \p from to array | ||
| 127 | * \p to. Note that this function has unpredictable results if the | ||
| 128 | * memory areas pointed to by \p to and \p from overlap. | ||
| 129 | * \param[in] to the destination array of bytes | ||
| 130 | * \param[in] from the array of bytes to copy | ||
| 131 | * \param[in] size the number of bytes to copy | ||
| 132 | */ | ||
| 133 | 10559857 | inline void copy(void* to, const void* from, size_t size) { | |
| 134 | 10559857 | ::memcpy(to, from, size); | |
| 135 | 10559857 | } | |
| 136 | |||
| 137 | /** | ||
| 138 | * \brief Converts a function pointer to a generic pointer. | ||
| 139 | * \details In C++ it is not legal to convert between function pointers | ||
| 140 | * and generic pointers using casts. Such conversion may be | ||
| 141 | * required when retrieving symbols in dynamically linked libraries, | ||
| 142 | * or when interfacing with scripting languages. | ||
| 143 | * \tparam FPTR function pointer type | ||
| 144 | * \param[in] fptr the function pointer | ||
| 145 | * \return a generic pointer with the same address as \p fptr | ||
| 146 | */ | ||
| 147 | template <class FPTR=function_pointer> | ||
| 148 | inline pointer function_pointer_to_generic_pointer(FPTR fptr) { | ||
| 149 | // I know this is ugly, but I did not find a simpler warning-free | ||
| 150 | // way that is portable between all compilers. | ||
| 151 | pointer result = nullptr; | ||
| 152 | ::memcpy(&result, &fptr, sizeof(pointer)); | ||
| 153 | return result; | ||
| 154 | } | ||
| 155 | |||
| 156 | /** | ||
| 157 | * \brief Converts a generic pointer to a function pointer. | ||
| 158 | * \details In C++ it is not legal to convert between function pointers | ||
| 159 | * and generic pointers using casts. Such conversion may be required | ||
| 160 | * when retrieving symbols in dynamically linked libraries, or when | ||
| 161 | * interfacing with scripting languages. | ||
| 162 | * \tparam FPTR function pointer type | ||
| 163 | * \param[in] ptr the generic pointer | ||
| 164 | * \return a function pointer with the same address as \p ptr | ||
| 165 | */ | ||
| 166 | template <class FPTR = function_pointer> | ||
| 167 | inline FPTR generic_pointer_to_function_pointer(pointer ptr) { | ||
| 168 | // I know this is ugly, but I did not find a simpler warning-free | ||
| 169 | // way that is portable between all compilers. | ||
| 170 | FPTR result = nullptr; | ||
| 171 | ::memcpy(&result, &ptr, sizeof(pointer)); | ||
| 172 | return result; | ||
| 173 | } | ||
| 174 | |||
| 175 | /** | ||
| 176 | * \brief Converts a generic pointer to a function pointer. | ||
| 177 | * \details In C++ it is not legal to convert between function pointers | ||
| 178 | * and generic pointers using casts. Such conversion may be | ||
| 179 | * required when retrieving symbols in dynamically linked libraries, | ||
| 180 | * or when interfacing with scripting languages. | ||
| 181 | * \tparam FPTR function pointer type | ||
| 182 | * \param[in] ptr the generic pointer | ||
| 183 | * \return a function pointer with the same address as \p ptr | ||
| 184 | */ | ||
| 185 | template <class FPTR = function_pointer> | ||
| 186 | inline FPTR generic_pointer_to_function_pointer(void* ptr) { | ||
| 187 | // I know this is ugly, but I did not find a simpler warning-free | ||
| 188 | // way that is portable between all compilers. | ||
| 189 | FPTR result = nullptr; | ||
| 190 | ::memcpy(&result, &ptr, sizeof(pointer)); | ||
| 191 | return result; | ||
| 192 | } | ||
| 193 | |||
| 194 | |||
| 195 | /** | ||
| 196 | * \brief Converts a pointer to a reference | ||
| 197 | * \tparam T the type for the reference | ||
| 198 | * \param[in] ptr the pointer | ||
| 199 | * \return a reference of type T& | ||
| 200 | */ | ||
| 201 | 262835923 | template <class T> inline T& pointer_as_reference(void* ptr) { | |
| 202 | // This is the recommended way of converting between pointers | ||
| 203 | // of different types. Casting the pointer directly is undefined | ||
| 204 | // behavior. Note: the call to memcpy() is eliminated by the | ||
| 205 | // compiler (that generates the same thing as when casting the | ||
| 206 | // pointer). | ||
| 207 | T* T_ptr; | ||
| 208 | 262835923 | ::memcpy(&T_ptr, &ptr, sizeof(pointer)); | |
| 209 | 262835923 | return *T_ptr; | |
| 210 | } | ||
| 211 | |||
| 212 | /** | ||
| 213 | * \brief Converts a const pointer to a reference | ||
| 214 | * \tparam T the type for the reference | ||
| 215 | * \param[in] ptr the pointer | ||
| 216 | * \return a const reference of type const T& | ||
| 217 | */ | ||
| 218 | 3415663 | template <class T> inline const T& pointer_as_reference( | |
| 219 | const void* ptr | ||
| 220 | ) { | ||
| 221 | // This is the recommended way of converting between pointers | ||
| 222 | // of different types. Casting the pointer directly is undefined | ||
| 223 | // behavior. Note: the call to memcpy() is eliminated by the | ||
| 224 | // compiler (that generates the same thing as when casting the | ||
| 225 | // pointer). | ||
| 226 | const T* T_ptr; | ||
| 227 | 3415663 | ::memcpy(&T_ptr, &ptr, sizeof(pointer)); | |
| 228 | 3415663 | return *T_ptr; | |
| 229 | } | ||
| 230 | |||
| 231 | |||
| 232 | /** | ||
| 233 | * \brief Default memory alignment for efficient vector operations | ||
| 234 | * \details The memory alignment is given in bytes. Here is a list of | ||
| 235 | * commonly used alignment values for various architectures: | ||
| 236 | * - SSE: 16 | ||
| 237 | * - AVX: 32 | ||
| 238 | * - AVX-512: 64 | ||
| 239 | */ | ||
| 240 | #define GEO_MEMORY_ALIGNMENT 64 | ||
| 241 | |||
| 242 | /** | ||
| 243 | * \brief Defines the memory alignment of points in a vector | ||
| 244 | * \details PointAlignment defines the memory alignment of points of | ||
| 245 | * dimension \p DIM when they are stored contiguously in an array. The | ||
| 246 | * alignment value is contained in the static data member \c value. | ||
| 247 | * The PointAlignment template defines a default alignment of 1. | ||
| 248 | * PointAlignment template specializations define specific values for | ||
| 249 | * the most commonly used point dimensions. | ||
| 250 | * \tparam DIM the dimension of the point. | ||
| 251 | */ | ||
| 252 | template <int DIM> | ||
| 253 | struct PointAlignment { | ||
| 254 | /** | ||
| 255 | * \brief Alignment value in bytes | ||
| 256 | * \details The default value is 1 byte. | ||
| 257 | */ | ||
| 258 | static const size_t value = 1; | ||
| 259 | }; | ||
| 260 | |||
| 261 | /** | ||
| 262 | * \brief PointAlignment specialization for points of dimension 2 | ||
| 263 | * \see PointAlignment | ||
| 264 | */ | ||
| 265 | template <> | ||
| 266 | struct PointAlignment<2> { | ||
| 267 | static const size_t value = 16; | ||
| 268 | }; | ||
| 269 | |||
| 270 | /** | ||
| 271 | * \brief PointAlignment specialization for points of dimension 3 | ||
| 272 | * \see PointAlignment | ||
| 273 | */ | ||
| 274 | template <> | ||
| 275 | struct PointAlignment<3> { | ||
| 276 | static const size_t value = 8; | ||
| 277 | }; | ||
| 278 | |||
| 279 | /** | ||
| 280 | * \brief PointAlignment specialization for points of dimension 4 | ||
| 281 | * \see PointAlignment | ||
| 282 | */ | ||
| 283 | template <> | ||
| 284 | struct PointAlignment<4> { | ||
| 285 | static const size_t value = 32; | ||
| 286 | }; | ||
| 287 | |||
| 288 | /** | ||
| 289 | * \brief PointAlignment specialization for points of dimension 6 | ||
| 290 | * \see PointAlignment | ||
| 291 | */ | ||
| 292 | template <> | ||
| 293 | struct PointAlignment<6> { | ||
| 294 | static const size_t value = 16; | ||
| 295 | }; | ||
| 296 | |||
| 297 | /** | ||
| 298 | * \brief PointAlignment specialization for points of dimension 8 | ||
| 299 | * \see PointAlignment | ||
| 300 | */ | ||
| 301 | template <> | ||
| 302 | struct PointAlignment<8> { | ||
| 303 | static const size_t value = 64; | ||
| 304 | }; | ||
| 305 | |||
| 306 | /** | ||
| 307 | * \brief Gets a point alignment | ||
| 308 | * \details This gives the alignment of a point of dimension \p dim | ||
| 309 | * within an array of points aligned on GEO_MEMORY_ALIGNMENT bytes | ||
| 310 | * \param[in] dim the dimension of the point | ||
| 311 | * \see GEO::Memory::PointAlignment | ||
| 312 | * \see GEO_MEMORY_ALIGNMENT | ||
| 313 | */ | ||
| 314 | #define geo_dim_alignment(dim) GEO::Memory::PointAlignment<dim>::value | ||
| 315 | |||
| 316 | /** | ||
| 317 | * \brief Allocates aligned memory. | ||
| 318 | * \details The address of the allocated block will be a multiple of | ||
| 319 | * \p alignment. Aligned memory blocks are required by vector | ||
| 320 | * processing instructions (SSE, AVX...) | ||
| 321 | * \param[in] size size of the block to allocate | ||
| 322 | * \param[in] alignment memory alignment (must be a power of 2) | ||
| 323 | * \note Memory alignment is not supported under Android. | ||
| 324 | */ | ||
| 325 | 151861 | inline void* aligned_malloc( | |
| 326 | size_t size, size_t alignment = GEO_MEMORY_ALIGNMENT | ||
| 327 | ) { | ||
| 328 | #if defined(GEO_OS_ANDROID) | ||
| 329 | // Alignment not supported under Android. | ||
| 330 | geo_argused(alignment); | ||
| 331 | return malloc(size); | ||
| 332 | #elif defined(GEO_COMPILER_INTEL) | ||
| 333 | return _mm_malloc(size, alignment); | ||
| 334 | #elif defined(GEO_COMPILER_GCC) || defined(GEO_COMPILER_CLANG) | ||
| 335 | void* result; | ||
| 336 | 151861 | return posix_memalign(&result, alignment, size) == 0 | |
| 337 |
1/2✓ Branch 0 taken 151861 times.
✗ Branch 1 not taken.
|
151861 | ? result : nullptr; |
| 338 | #elif defined(GEO_COMPILER_MSVC) | ||
| 339 | return _aligned_malloc(size, alignment); | ||
| 340 | #else | ||
| 341 | geo_argused(alignment); | ||
| 342 | return malloc(size); | ||
| 343 | #endif | ||
| 344 | } | ||
| 345 | |||
| 346 | /** | ||
| 347 | * \brief Deallocates aligned memory | ||
| 348 | * \details Deallocates the block of memory pointed to by \p p. Note | ||
| 349 | * \p p that must have been previously allocated by aligned_malloc() | ||
| 350 | * \see aligned_malloc() | ||
| 351 | * \note Memory alignment is not supported under Android. | ||
| 352 | */ | ||
| 353 | 151861 | inline void aligned_free(void* p) { | |
| 354 | #if defined(GEO_OS_ANDROID) | ||
| 355 | // Alignment not supported under Android. | ||
| 356 | free(p); | ||
| 357 | #elif defined(GEO_COMPILER_INTEL) | ||
| 358 | _mm_free(p); | ||
| 359 | #elif defined(GEO_COMPILER_GCC_FAMILY) | ||
| 360 | 151861 | free(p); | |
| 361 | #elif defined(GEO_COMPILER_MSVC) | ||
| 362 | _aligned_free(p); | ||
| 363 | #else | ||
| 364 | free(p); | ||
| 365 | #endif | ||
| 366 | 151861 | } | |
| 367 | |||
| 368 | /** | ||
| 369 | * \def geo_decl_aligned(var) | ||
| 370 | * \brief Specifies that a given variable should be memory-aligned. | ||
| 371 | * \details | ||
| 372 | * It helps the compiler vectorizing loops, | ||
| 373 | * i.e. generating SSE/AVX/... code. | ||
| 374 | * \param[in] var a variable in the current scope | ||
| 375 | * \par Example | ||
| 376 | * \code | ||
| 377 | * geo_decl_aligned(double x); | ||
| 378 | * \endcode | ||
| 379 | * \note Memory alignment is not supported under Android. | ||
| 380 | */ | ||
| 381 | #if defined(GEO_OS_ANDROID) | ||
| 382 | #define geo_decl_aligned(var) var | ||
| 383 | #elif defined(GEO_COMPILER_INTEL) | ||
| 384 | #define geo_decl_aligned(var) __declspec(aligned(GEO_MEMORY_ALIGNMENT)) var | ||
| 385 | #elif defined(GEO_COMPILER_GCC_FAMILY) | ||
| 386 | #define geo_decl_aligned(var) var __attribute__((aligned(GEO_MEMORY_ALIGNMENT))) | ||
| 387 | #elif defined(GEO_COMPILER_MSVC) | ||
| 388 | #define geo_decl_aligned(var) __declspec(align(GEO_MEMORY_ALIGNMENT)) var | ||
| 389 | #elif defined(GEO_COMPILER_EMSCRIPTEN) | ||
| 390 | #define geo_decl_aligned(var) var | ||
| 391 | #endif | ||
| 392 | |||
| 393 | /** | ||
| 394 | * \def geo_assume_aligned(var, alignment) | ||
| 395 | * \brief Informs the compiler that a given pointer is memory-aligned. | ||
| 396 | * \details | ||
| 397 | * It helps the compiler vectorizing loops, i.e. | ||
| 398 | * generating SSE/AVX/... code. | ||
| 399 | * \param[in] var a pointer variable in the current scope | ||
| 400 | * \param[in] alignment the memory alignment (must be a power of 2) | ||
| 401 | * \par Example | ||
| 402 | * \code | ||
| 403 | * double* p = ...; | ||
| 404 | * geo_assume_aligned(p,alignment); | ||
| 405 | * \endcode | ||
| 406 | * \note Memory alignment is not supported under Android. | ||
| 407 | * \note C++20 has std::assume_aligned() | ||
| 408 | */ | ||
| 409 | #if defined(GEO_OS_ANDROID) | ||
| 410 | #define geo_assume_aligned(var, alignment) | ||
| 411 | #elif defined(GEO_COMPILER_INTEL) | ||
| 412 | #define geo_assume_aligned(var, alignment) \ | ||
| 413 | __assume_aligned(var, alignment) | ||
| 414 | #elif defined(GEO_COMPILER_CLANG) | ||
| 415 | #define geo_assume_aligned(var, alignment) | ||
| 416 | // GCC __builtin_assume_aligned is not yet supported by clang-3.3 | ||
| 417 | #elif defined(GEO_COMPILER_GCC) | ||
| 418 | #if __GNUC__ >= 4 && __GNUC_MINOR__ >= 7 | ||
| 419 | #define geo_assume_aligned(var, alignment) \ | ||
| 420 | *(void**) (&var) = __builtin_assume_aligned(var, alignment) | ||
| 421 | // the GCC way of specifying that a pointer is aligned returns | ||
| 422 | // the aligned pointer (I can't figure out why). It needs to be | ||
| 423 | // affected otherwise it is not taken into account (verified by | ||
| 424 | // looking at the output of gcc -S) | ||
| 425 | #else | ||
| 426 | #define geo_assume_aligned(var, alignment) | ||
| 427 | #endif | ||
| 428 | #elif defined(GEO_COMPILER_MSVC) | ||
| 429 | #define geo_assume_aligned(var, alignment) | ||
| 430 | // TODO: I do not know how to do that with MSVC | ||
| 431 | #elif defined(GEO_COMPILER_EMSCRIPTEN) | ||
| 432 | #define geo_assume_aligned(var, alignment) | ||
| 433 | #elif defined(GEO_COMPILER_MINGW) | ||
| 434 | #define geo_assume_aligned(var, alignment) | ||
| 435 | #endif | ||
| 436 | |||
| 437 | /** | ||
| 438 | * \def geo_restrict | ||
| 439 | * \brief Informs the compiler that a given pointer has no aliasing | ||
| 440 | * \details | ||
| 441 | * No aliasing means that no other pointer points to the same area of | ||
| 442 | * memory. | ||
| 443 | * \code | ||
| 444 | * double* geo_restrict p = ...; | ||
| 445 | * \endcode | ||
| 446 | */ | ||
| 447 | #if defined(GEO_COMPILER_INTEL) | ||
| 448 | #define geo_restrict __restrict | ||
| 449 | #elif defined(GEO_COMPILER_GCC_FAMILY) | ||
| 450 | #define geo_restrict __restrict__ | ||
| 451 | #elif defined(GEO_COMPILER_MSVC) | ||
| 452 | #define geo_restrict __restrict | ||
| 453 | #elif defined(GEO_COMPILER_EMSCRIPTEN) | ||
| 454 | #define geo_restrict | ||
| 455 | #endif | ||
| 456 | |||
| 457 | /** | ||
| 458 | * \brief Checks whether a pointer is aligned. | ||
| 459 | * \param[in] p the pointer to check | ||
| 460 | * \param[in] alignment memory alignment (must be a power of 2) | ||
| 461 | * \retval true if \p is aligned on \p alignment bytes | ||
| 462 | * \retval false otherwise | ||
| 463 | */ | ||
| 464 | inline bool is_aligned( | ||
| 465 | void* p, size_t alignment = GEO_MEMORY_ALIGNMENT | ||
| 466 | ) { | ||
| 467 | return (reinterpret_cast<size_t>(p) & (alignment - 1)) == 0; | ||
| 468 | } | ||
| 469 | |||
| 470 | /** | ||
| 471 | * \brief Returns the smallest aligned memory address from p. | ||
| 472 | */ | ||
| 473 | inline void* align(void* p) { | ||
| 474 | size_t offset = ( | ||
| 475 | GEO_MEMORY_ALIGNMENT - | ||
| 476 | (reinterpret_cast<size_t>(p) & (GEO_MEMORY_ALIGNMENT - 1)) | ||
| 477 | ) & (GEO_MEMORY_ALIGNMENT - 1); | ||
| 478 | return reinterpret_cast<char*>(p) + offset; | ||
| 479 | } | ||
| 480 | |||
| 481 | /** | ||
| 482 | * \brief Allocates aligned memory on the stack | ||
| 483 | * \brief Allocates \p size bytes on the stack. The returned address | ||
| 484 | * is guaranteed to be aligned on \c GEO_MEMORY_ALIGNMENT bytes. To | ||
| 485 | * guarantee the memory alignment, the function may allocate more than | ||
| 486 | * \p size, but not more than <tt>GEO_MEMORY_ALIGNMENT - 1</tt>. | ||
| 487 | * \param[in] size Number of bytes to allocate. | ||
| 488 | * \return An aligned pointer to a memory block of \p size bytes. | ||
| 489 | */ | ||
| 490 | #define geo_aligned_alloca(size) \ | ||
| 491 | GEO::Memory::align(alloca(size + GEO_MEMORY_ALIGNMENT - 1)) | ||
| 492 | |||
| 493 | /** | ||
| 494 | * \brief An allocator that performs aligned memory allocations | ||
| 495 | * \details | ||
| 496 | * The allocator can be used as a template argument for STL | ||
| 497 | * containers. It is required for efficient vectorization of the code | ||
| 498 | * using vector processing units (SSE,AVX or AVX-512). | ||
| 499 | */ | ||
| 500 | template <class T, int ALIGN = GEO_MEMORY_ALIGNMENT> | ||
| 501 | class aligned_allocator { | ||
| 502 | public: | ||
| 503 | /** \brief Element type */ | ||
| 504 | typedef T value_type; | ||
| 505 | |||
| 506 | /** \brief Pointer to element */ | ||
| 507 | typedef T* pointer; | ||
| 508 | |||
| 509 | /** \brief Reference to element */ | ||
| 510 | typedef T& reference; | ||
| 511 | |||
| 512 | /** \brief Pointer to constant element */ | ||
| 513 | typedef const T* const_pointer; | ||
| 514 | |||
| 515 | /** \brief Reference to constant element */ | ||
| 516 | typedef const T& const_reference; | ||
| 517 | |||
| 518 | /** \brief Quantities of elements */ | ||
| 519 | typedef ::std::size_t size_type; | ||
| 520 | |||
| 521 | /** \brief Difference between two pointers */ | ||
| 522 | typedef ::std::ptrdiff_t difference_type; | ||
| 523 | |||
| 524 | /** \brief Alignment in bytes */ | ||
| 525 | static constexpr int ALIGNMENT = ALIGN; | ||
| 526 | |||
| 527 | /** | ||
| 528 | * \brief Defines the same allocator for other types | ||
| 529 | * \tparam U type of the elements to allocate | ||
| 530 | */ | ||
| 531 | template <class U> | ||
| 532 | struct rebind { | ||
| 533 | /**Equivalent allocator type to allocate elements of type \p U*/ | ||
| 534 | typedef aligned_allocator<U,ALIGN> other; | ||
| 535 | }; | ||
| 536 | |||
| 537 | /* \brief default constructor */ | ||
| 538 | constexpr aligned_allocator() noexcept = default; | ||
| 539 | |||
| 540 | /* \brief conversion copy constructor */ | ||
| 541 | template <class U, int A2> constexpr aligned_allocator( | ||
| 542 | const aligned_allocator<U, A2>& | ||
| 543 | ) noexcept { | ||
| 544 | } | ||
| 545 | |||
| 546 | /** | ||
| 547 | * \brief Gets the address of an object | ||
| 548 | * \param[in] x a reference to an object of type T | ||
| 549 | * \return a pointer to \p x | ||
| 550 | */ | ||
| 551 | pointer address(reference x) { | ||
| 552 | return &x; | ||
| 553 | } | ||
| 554 | |||
| 555 | /** | ||
| 556 | * \brief Gets the address of a object | ||
| 557 | * \param[in] x a const reference to an object of type T | ||
| 558 | * \return a const_pointer to \p x | ||
| 559 | */ | ||
| 560 | const_pointer address(const_reference x) { | ||
| 561 | return &x; | ||
| 562 | } | ||
| 563 | |||
| 564 | /** | ||
| 565 | * \brief Allocates a block of storage | ||
| 566 | * \details Attempts to allocate a block of storage with a size | ||
| 567 | * large enough to contain \p n elements of member type | ||
| 568 | * \c value_type (an alias of the allocator's template parameter), | ||
| 569 | * and returns a pointer to the first element. | ||
| 570 | * The storage is aligned on ALIGN bytes, but they are \b not | ||
| 571 | * constructed. | ||
| 572 | * \param[in] nb_elt number of elements to allocate | ||
| 573 | * \param[in] hint Either 0 or a value previously | ||
| 574 | * obtained by another call to allocate and not yet freed with | ||
| 575 | * deallocate. When it is not 0, this value may be used as a hint | ||
| 576 | * to improve performance by allocating the new block near the one | ||
| 577 | * specified. The address of an adjacent element is often a good | ||
| 578 | * choice. | ||
| 579 | * \return A pointer to the initial element in the block of storage | ||
| 580 | */ | ||
| 581 | 301050 | pointer allocate( | |
| 582 | size_type nb_elt, const void* hint = nullptr | ||
| 583 | ) { | ||
| 584 | 301050 | nb_elt = std::max(nb_elt,size_type(1)); | |
| 585 | 301050 | geo_argused(hint); | |
| 586 | ✗ | while(true) { | |
| 587 | pointer result = static_cast<pointer>( | ||
| 588 | 301050 | aligned_malloc(sizeof(T) * nb_elt, ALIGNMENT) | |
| 589 | ); | ||
| 590 |
1/2✓ Branch 0 taken 150998 times.
✗ Branch 1 not taken.
|
301050 | if(result != nullptr) { |
| 591 | 301050 | return result; | |
| 592 | } | ||
| 593 | // under Linux, a process requesting more mem than available | ||
| 594 | // is killed (and there is nothing we can capture). Under | ||
| 595 | // other OSes, the standard mechanism to let the runtime | ||
| 596 | // know is as follows: | ||
| 597 | // see: https://stackoverflow.com/questions/7194127/ | ||
| 598 | // how-should-i-write-iso-c-standard-conformant-custom- | ||
| 599 | // new-and-delete-operators | ||
| 600 | // (if there is a handler, call it repeatedly until | ||
| 601 | // allocation succeeds, else throw a bad_alloc exception) | ||
| 602 | ✗ | std::new_handler handler = std::get_new_handler(); | |
| 603 | ✗ | if(handler != nullptr) { | |
| 604 | ✗ | (*handler)(); | |
| 605 | } else { | ||
| 606 | ✗ | throw std::bad_alloc(); | |
| 607 | } | ||
| 608 | } | ||
| 609 | } | ||
| 610 | |||
| 611 | /** | ||
| 612 | * \brief Releases a block of storage | ||
| 613 | * \details Releases a block of storage previously allocated with | ||
| 614 | * member allocate()) and not yet released. The elements in the | ||
| 615 | * array \b are not destroyed by a call to this member function. | ||
| 616 | * \param[in] p Pointer to a block of storage previously allocated | ||
| 617 | * with aligned_allocator::allocate. | ||
| 618 | * \param[in] nb_elt Number of elements allocated on the call to | ||
| 619 | * aligned_allocator::allocate() for this block of storage. | ||
| 620 | * \see allocate() | ||
| 621 | */ | ||
| 622 | 301118 | void deallocate(pointer p, size_type nb_elt) { | |
| 623 | 301118 | geo_argused(nb_elt); | |
| 624 | 301118 | aligned_free(p); | |
| 625 | 301118 | } | |
| 626 | |||
| 627 | /** | ||
| 628 | * \brief Gets the maximum size possible to allocate | ||
| 629 | * \return the maximum number of elements, each of member type | ||
| 630 | * \c value_type that could potentially be allocated by a call to | ||
| 631 | * member allocate(). | ||
| 632 | */ | ||
| 633 | 25517426 | size_type max_size() const { | |
| 634 | ::std::allocator<char> a; | ||
| 635 | 25517426 | return std::allocator_traits<decltype(a)>::max_size(a) / | |
| 636 | 25517426 | sizeof(T); | |
| 637 | } | ||
| 638 | |||
| 639 | /** | ||
| 640 | * \brief Constructs an object | ||
| 641 | * \details Constructs an element object on the location pointed | ||
| 642 | * by \p p. | ||
| 643 | * Notice that this does not allocate space for the element. It | ||
| 644 | * should already be available at p (see member allocate() to | ||
| 645 | * allocate space). | ||
| 646 | * \param[in] p pointer to a location with enough storage space to | ||
| 647 | * contain an element of type value_type. | ||
| 648 | * \param[in] val value to initialize the constructed element to. | ||
| 649 | * \see allocate() | ||
| 650 | */ | ||
| 651 | 434520404 | void construct(pointer p, const_reference val) { | |
| 652 |
2/7✗ Branch 1 not taken.
✓ Branch 2 taken 220883589 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 413881 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
434520404 | new (static_cast<void*>(p))value_type(val); |
| 653 | 434520404 | } | |
| 654 | |||
| 655 | /** | ||
| 656 | * \brief Destroys an object | ||
| 657 | * \details Destroys in-place the object pointed by p. Notice that | ||
| 658 | * this does not deallocate the storage for the element (see | ||
| 659 | * member deallocate() to release storage space). | ||
| 660 | * \param[in] p pointer to the object to be destroyed. | ||
| 661 | * \see deallocate() | ||
| 662 | */ | ||
| 663 | 3164390384 | void destroy(pointer p) { | |
| 664 | 3164390384 | geo_argused(p); // else MSVC complains | |
| 665 | 3164390384 | p->~value_type(); | |
| 666 | 3164390384 | } | |
| 667 | }; | ||
| 668 | |||
| 669 | /** | ||
| 670 | * \brief Tests whether two aligned_allocator%s are equal. | ||
| 671 | * \return Always true. | ||
| 672 | */ | ||
| 673 | template <typename T1, int A1, typename T2, int A2> | ||
| 674 | 4127505 | inline bool operator== ( | |
| 675 | const aligned_allocator<T1, A1>&, const aligned_allocator<T2, A2>& | ||
| 676 | ) { | ||
| 677 | 4127505 | return true; | |
| 678 | } | ||
| 679 | |||
| 680 | /** | ||
| 681 | * \brief Tests whether two aligned_allocator%s are different. | ||
| 682 | * \return Always false. | ||
| 683 | */ | ||
| 684 | template <typename T1, int A1, typename T2, int A2> | ||
| 685 | ✗ | inline bool operator!= ( | |
| 686 | const aligned_allocator<T1, A1>&, const aligned_allocator<T2, A2>& | ||
| 687 | ) { | ||
| 688 | ✗ | return false; | |
| 689 | } | ||
| 690 | } | ||
| 691 | |||
| 692 | /************************************************************************/ | ||
| 693 | |||
| 694 | /** | ||
| 695 | * \brief Vector with aligned memory allocation | ||
| 696 | * \details | ||
| 697 | * Class vector is a \c std::vector that uses a memory-aligned allocator | ||
| 698 | * Memory-aligned allocation makes it well suited for SSE/AVX/... vector | ||
| 699 | * code generation. | ||
| 700 | * \see Memory::aligned_allocator | ||
| 701 | */ | ||
| 702 | template <class T> | ||
| 703 | class vector : public ::std::vector<T, Memory::aligned_allocator<T> > { | ||
| 704 | /** | ||
| 705 | * \brief Shortcut to the allocator type. | ||
| 706 | */ | ||
| 707 | typedef Memory::aligned_allocator<T> allocator; | ||
| 708 | |||
| 709 | /** | ||
| 710 | * \brief Shortcut to the base class type | ||
| 711 | */ | ||
| 712 | typedef ::std::vector<T, Memory::aligned_allocator<T> > baseclass; | ||
| 713 | |||
| 714 | |||
| 715 | |||
| 716 | public: | ||
| 717 | /** | ||
| 718 | * \brief Creates an empty vector | ||
| 719 | */ | ||
| 720 | 97612 | vector() : | |
| 721 | 97612 | baseclass() { | |
| 722 | 97612 | } | |
| 723 | |||
| 724 | /** | ||
| 725 | * \brief Creates a pre-allocated vector | ||
| 726 | * \details Constructs a container with \p size elements. | ||
| 727 | * Each element is default-constructed. | ||
| 728 | * \param[in] size Number of elements to allocate | ||
| 729 | */ | ||
| 730 | 3978 | explicit vector(index_t size) : | |
| 731 |
1/2✓ Branch 1 taken 2661 times.
✗ Branch 2 not taken.
|
3978 | baseclass(size) { |
| 732 | 3978 | } | |
| 733 | |||
| 734 | /** | ||
| 735 | * \brief Creates a pre-initialized vector | ||
| 736 | * \details Constructs a container with \p size elements. | ||
| 737 | * Each element is a copy of \p val. | ||
| 738 | * \param[in] size Number of elements to allocate | ||
| 739 | * \param[in] val Initial value of the elements | ||
| 740 | */ | ||
| 741 | 4705 | explicit vector(index_t size, const T& val) : | |
| 742 |
1/2✓ Branch 1 taken 4665 times.
✗ Branch 2 not taken.
|
4705 | baseclass(size, val) { |
| 743 | 4705 | } | |
| 744 | |||
| 745 | /** | ||
| 746 | * \brief Gets the number of elements | ||
| 747 | * \return The actual number of elements in the vector | ||
| 748 | */ | ||
| 749 | 12113349171 | index_t size() const { | |
| 750 | // casts baseclass::size() from size_t (64 bits) | ||
| 751 | // to index_t (32 bits), because all | ||
| 752 | // indices in Vorpaline are supposed to fit in 32 bits (index_t). | ||
| 753 | // TODO: geo_debug_assert(baseclass::size() < max index_t) | ||
| 754 | 12113349171 | return index_t(baseclass::size()); | |
| 755 | } | ||
| 756 | |||
| 757 | /** | ||
| 758 | * \brief Gets a vector element | ||
| 759 | * \param[in] i index of the element | ||
| 760 | * \return A reference to the element at position \p i in the vector. | ||
| 761 | */ | ||
| 762 | 1814703690 | T& operator[] (index_t i) { | |
| 763 |
1/6✗ Branch 1 not taken.
✓ Branch 2 taken 907547208 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
1814703690 | geo_debug_assert(i < size()); |
| 764 | 1814703690 | return baseclass::operator[] (i); | |
| 765 | } | ||
| 766 | |||
| 767 | /** | ||
| 768 | * \brief Gets a vector element | ||
| 769 | * \param[in] i index of the element | ||
| 770 | * \return A const reference to the element at position | ||
| 771 | * \p i in the vector. | ||
| 772 | */ | ||
| 773 | 4239234751 | const T& operator[] (index_t i) const { | |
| 774 |
1/6✗ Branch 1 not taken.
✓ Branch 2 taken 2515395105 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
4239234751 | geo_debug_assert(i < size()); |
| 775 | 4239234751 | return baseclass::operator[] (i); | |
| 776 | } | ||
| 777 | |||
| 778 | /** | ||
| 779 | * \brief Gets a vector element | ||
| 780 | * \param[in] i index of the element | ||
| 781 | * \return A reference to the element at position \p i in the vector. | ||
| 782 | */ | ||
| 783 | 16561575 | T& operator[] (signed_index_t i) { | |
| 784 |
3/10✓ Branch 0 taken 16561575 times.
✗ Branch 1 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 16561575 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 16561575 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
|
16561575 | geo_debug_assert(i >= 0 && index_t(i) < size()); |
| 785 | 16561575 | return baseclass::operator[] (index_t(i)); | |
| 786 | } | ||
| 787 | |||
| 788 | /** | ||
| 789 | * \brief Gets a vector element | ||
| 790 | * \param[in] i index of the element | ||
| 791 | * \return A const reference to the element at position \p i | ||
| 792 | * in the vector. | ||
| 793 | */ | ||
| 794 | 3612 | const T& operator[] (signed_index_t i) const { | |
| 795 |
3/10✓ Branch 0 taken 3612 times.
✗ Branch 1 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 3612 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 3612 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
|
3612 | geo_debug_assert(i >= 0 && index_t(i) < size()); |
| 796 | 3612 | return baseclass::operator[] (index_t(i)); | |
| 797 | } | ||
| 798 | |||
| 799 | |||
| 800 | #ifdef GARGANTUA // If compiled with 64 bits index_t | ||
| 801 | |||
| 802 | /** | ||
| 803 | * \brief Gets a vector element | ||
| 804 | * \param[in] i index of the element | ||
| 805 | * \return A reference to the element at position \p i in the vector. | ||
| 806 | */ | ||
| 807 | 64986080 | T& operator[] (int i) { | |
| 808 |
3/10✓ Branch 0 taken 35171415 times.
✗ Branch 1 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 35171415 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 35171415 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
|
64986080 | geo_debug_assert(i >= 0 && index_t(i) < size()); |
| 809 | 64986080 | return baseclass::operator[] (index_t(i)); | |
| 810 | } | ||
| 811 | |||
| 812 | /** | ||
| 813 | * \brief Gets a vector element | ||
| 814 | * \param[in] i index of the element | ||
| 815 | * \return A const reference to the element at position \p i | ||
| 816 | * in the vector. | ||
| 817 | */ | ||
| 818 | 29440802 | const T& operator[] (int i) const { | |
| 819 |
3/10✓ Branch 0 taken 29440404 times.
✗ Branch 1 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 29440404 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 29440404 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
|
29440802 | geo_debug_assert(i >= 0 && index_t(i) < size()); |
| 820 | 29440802 | return baseclass::operator[] (index_t(i)); | |
| 821 | } | ||
| 822 | |||
| 823 | /** | ||
| 824 | * \brief Gets a vector element | ||
| 825 | * \param[in] i index of the element | ||
| 826 | * \return A reference to the element at position \p i in the vector. | ||
| 827 | */ | ||
| 828 | ✗ | T& operator[] (unsigned int i) { | |
| 829 | ✗ | geo_debug_assert(index_t(i) < size()); | |
| 830 | ✗ | return baseclass::operator[] (index_t(i)); | |
| 831 | } | ||
| 832 | |||
| 833 | /** | ||
| 834 | * \brief Gets a vector element | ||
| 835 | * \param[in] i index of the element | ||
| 836 | * \return A const reference to the element at position \p i | ||
| 837 | * in the vector. | ||
| 838 | */ | ||
| 839 | ✗ | const T& operator[] (unsigned int i) const { | |
| 840 | ✗ | geo_debug_assert(index_t(i) < size()); | |
| 841 | ✗ | return baseclass::operator[] (index_t(i)); | |
| 842 | } | ||
| 843 | #endif | ||
| 844 | |||
| 845 | /** | ||
| 846 | * \brief Gets a pointer to the array of elements | ||
| 847 | * \return a pointer to the first element of the vector | ||
| 848 | */ | ||
| 849 | 4837196 | T* data() { | |
| 850 | 4837196 | T* result = baseclass::data(); | |
| 851 | // Tell the compiler that the pointer is aligned, to enable AVX | ||
| 852 | // vectorization, can be useful when using vector<double> | ||
| 853 | // with blas-like operations. I hope the hint will propagate to | ||
| 854 | // the caller (not sure...) | ||
| 855 | geo_assume_aligned(result, allocator::ALIGNMENT); | ||
| 856 | 4837196 | return result; | |
| 857 | } | ||
| 858 | |||
| 859 | /** | ||
| 860 | * \brief Gets a pointer to the array of elements | ||
| 861 | * \return a const pointer to the first element of the vector | ||
| 862 | */ | ||
| 863 | 46001870 | const T* data() const { | |
| 864 | 46001870 | const T* result = baseclass::data(); | |
| 865 | // Tell the compiler that the pointer is aligned, to enable AVX | ||
| 866 | // vectorization, can be useful when using vector<double> | ||
| 867 | // with blas-like operations. I hope the hint will propagate to | ||
| 868 | // the caller (not sure...) | ||
| 869 | geo_assume_aligned(result, allocator::ALIGNMENT); | ||
| 870 | 46001870 | return result; | |
| 871 | } | ||
| 872 | |||
| 873 | |||
| 874 | /** | ||
| 875 | * \brief Resizes this vector to zero and deallocated | ||
| 876 | * all the memory. | ||
| 877 | * \details clear() does not deallocate. | ||
| 878 | */ | ||
| 879 | void clear_and_deallocate() { | ||
| 880 | vector<T> other; | ||
| 881 | this->swap(other); | ||
| 882 | } | ||
| 883 | }; | ||
| 884 | |||
| 885 | /** | ||
| 886 | * \brief Specialization of vector for elements of type bool | ||
| 887 | * \details This specialization uses std::vector<bool> directly without | ||
| 888 | * memory alignment. | ||
| 889 | * \see vector | ||
| 890 | */ | ||
| 891 | template <> | ||
| 892 | class vector<bool> : public ::std::vector<bool> { | ||
| 893 | typedef ::std::vector<bool> baseclass; | ||
| 894 | |||
| 895 | public: | ||
| 896 | /** \copydoc vector::vector() */ | ||
| 897 | 865 | vector() : | |
| 898 | 865 | baseclass() { | |
| 899 | 865 | } | |
| 900 | |||
| 901 | /** \copydoc vector::vector(index_t) */ | ||
| 902 | ✗ | explicit vector(index_t size) : | |
| 903 | ✗ | baseclass(size) { | |
| 904 | ✗ | } | |
| 905 | |||
| 906 | /** \copydoc vector::vector(index_t,const T&) */ | ||
| 907 | 1708 | explicit vector(index_t size, bool val) : | |
| 908 |
1/2✓ Branch 1 taken 1708 times.
✗ Branch 2 not taken.
|
3416 | baseclass(size, val) { |
| 909 | 1708 | } | |
| 910 | |||
| 911 | /** \copydoc vector::size() */ | ||
| 912 | 2495932 | index_t size() const { | |
| 913 | // casts baseclass::size() from size_t (64 bits) | ||
| 914 | // to index_t (32 bits), because all | ||
| 915 | // indices in Vorpaline are supposed to fit in 32 bits (index_t). | ||
| 916 | // TODO: geo_debug_assert(baseclass::size() < max index_t) | ||
| 917 | 2495932 | return index_t(baseclass::size()); | |
| 918 | } | ||
| 919 | |||
| 920 | // TODO: operator[] with bounds checking (more complicated | ||
| 921 | // than just returning bool&, check implementation in STL). | ||
| 922 | }; | ||
| 923 | } | ||
| 924 | |||
| 925 | #endif | ||
| 926 |