memory.h

Go to the documentation of this file.

/*
 *  Copyright (c) 2000-2022 Inria
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions are met:
 *
 *  * Redistributions of source code must retain the above copyright notice,
 *  this list of conditions and the following disclaimer.
 *  * Redistributions in binary form must reproduce the above copyright notice,
 *  this list of conditions and the following disclaimer in the documentation
 *  and/or other materials provided with the distribution.
 *  * Neither the name of the ALICE Project-Team nor the names of its
 *  contributors may be used to endorse or promote products derived from this
 *  software without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 *  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 *  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 *  ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 *  LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 *  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 *  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 *  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 *  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 *  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 *  POSSIBILITY OF SUCH DAMAGE.
 *
 *  Contact: Bruno Levy
 *
 *     https://www.inria.fr/fr/bruno-levy
 *
 *     Inria,
 *     Domaine de Voluceau,
 *     78150 Le Chesnay - Rocquencourt
 *     FRANCE
 *
 */
 
#ifndef GEOGRAM_BASIC_MEMORY
#define GEOGRAM_BASIC_MEMORY
 
#include <geogram/basic/common.h>
#include <geogram/basic/assert.h>
#include <geogram/basic/numeric.h>
#include <geogram/basic/argused.h>
#include <vector>
#include <string.h>
#include <stdlib.h>
 
#ifdef GEO_OS_WINDOWS
 
#include <windows.h>
#ifdef min
#undef min
#endif
#ifdef max
#undef max
#endif
 
#else
 
#include <unistd.h>
 
#endif
 
// Stack size depending on OS:
// Linux: 10 Mb
// Windows: 1 Mb
// Mac OSX: 512 Kb
// GEO_HAS_BIG_STACK is defined under Linux
// and lets some of the functions that
// manipulate exact precision numbers
// allocate temporaries on the stack.
 
#ifdef GEO_OS_LINUX
#define GEO_HAS_BIG_STACK
#endif
 
namespace GEO {
 
    namespace Memory {
        typedef unsigned char byte;
 
        typedef unsigned char word8;
 
        typedef unsigned short word16;
 
        typedef unsigned int word32;
 
        typedef byte* pointer;
 
        typedef const byte* const_pointer;
 
        typedef void (*function_pointer)();
 
        inline void clear(void* addr, size_t size) {
            ::memset(addr, 0, size);
        }
 
        inline void copy(void* to, const void* from, size_t size) {
            ::memcpy(to, from, size);
        }
 
        template <class FPTR=function_pointer>
        inline pointer function_pointer_to_generic_pointer(FPTR fptr) {
            // I know this is ugly, but I did not find a simpler warning-free
            // way that is portable between all compilers.
            pointer result = nullptr;
            ::memcpy(&result, &fptr, sizeof(pointer));
            return result;
        }
 
        template <class FPTR = function_pointer>
        inline FPTR generic_pointer_to_function_pointer(pointer ptr) {
            // I know this is ugly, but I did not find a simpler warning-free
            // way that is portable between all compilers.
            FPTR result = nullptr;
            ::memcpy(&result, &ptr, sizeof(pointer));
            return result;
        }
 
        template <class FPTR = function_pointer>
        inline FPTR generic_pointer_to_function_pointer(void* ptr) {
            // I know this is ugly, but I did not find a simpler warning-free
            // way that is portable between all compilers.
            FPTR result = nullptr;
            ::memcpy(&result, &ptr, sizeof(pointer));
            return result;
        }
 
 
        template <class T> inline T& pointer_as_reference(void* ptr) {
            // This is the recommended way of converting between pointers
            // of different types. Casting the pointer directly is undefined
            // behavior. Note: the call to memcpy() is eliminated by the
            // compiler (that generates the same thing as when casting the
            // pointer).
            T* T_ptr;
            ::memcpy(&T_ptr, &ptr, sizeof(pointer));
            return *T_ptr;
        }
 
        template <class T> inline const T& pointer_as_reference(
            const void* ptr
        ) {
            // This is the recommended way of converting between pointers
            // of different types. Casting the pointer directly is undefined
            // behavior. Note: the call to memcpy() is eliminated by the
            // compiler (that generates the same thing as when casting the
            // pointer).
            const T* T_ptr;
            ::memcpy(&T_ptr, &ptr, sizeof(pointer));
            return *T_ptr;
        }
 
 
#define GEO_MEMORY_ALIGNMENT 64
 
        template <int DIM>
        struct PointAlignment {
            static const size_t value = 1;
        };
 
        template <>
        struct PointAlignment<2> {
            static const size_t value = 16;
        };
 
        template <>
        struct PointAlignment<3> {
            static const size_t value = 8;
        };
 
        template <>
        struct PointAlignment<4> {
            static const size_t value = 32;
        };
 
        template <>
        struct PointAlignment<6> {
            static const size_t value = 16;
        };
 
        template <>
        struct PointAlignment<8> {
            static const size_t value = 64;
        };
 
#define geo_dim_alignment(dim) GEO::Memory::PointAlignment<dim>::value
 
        inline void* aligned_malloc(
            size_t size, size_t alignment = GEO_MEMORY_ALIGNMENT
        ) {
#if   defined(GEO_OS_ANDROID)
            // Alignment not supported under Android.
            geo_argused(alignment);
            return malloc(size);
#elif defined(GEO_COMPILER_INTEL)
            return _mm_malloc(size, alignment);
#elif defined(GEO_COMPILER_GCC) || defined(GEO_COMPILER_CLANG)
            void* result;
            return posix_memalign(&result, alignment, size) == 0
                ? result : nullptr;
#elif defined(GEO_COMPILER_MSVC)
            return _aligned_malloc(size, alignment);
#else
            geo_argused(alignment);
            return malloc(size);
#endif
        }
 
        inline void aligned_free(void* p) {
#if   defined(GEO_OS_ANDROID)
            // Alignment not supported under Android.
            free(p);
#elif defined(GEO_COMPILER_INTEL)
            _mm_free(p);
#elif defined(GEO_COMPILER_GCC_FAMILY)
            free(p);
#elif defined(GEO_COMPILER_MSVC)
            _aligned_free(p);
#else
            free(p);
#endif
        }
 
#if   defined(GEO_OS_ANDROID)
#define geo_decl_aligned(var) var
#elif defined(GEO_COMPILER_INTEL)
#define geo_decl_aligned(var) __declspec(aligned(GEO_MEMORY_ALIGNMENT)) var
#elif defined(GEO_COMPILER_GCC_FAMILY)
#define geo_decl_aligned(var) var __attribute__((aligned(GEO_MEMORY_ALIGNMENT)))
#elif defined(GEO_COMPILER_MSVC)
#define geo_decl_aligned(var) __declspec(align(GEO_MEMORY_ALIGNMENT)) var
#elif defined(GEO_COMPILER_EMSCRIPTEN)
#define geo_decl_aligned(var) var
#endif
 
#if   defined(GEO_OS_ANDROID)
#define geo_assume_aligned(var, alignment)
#elif defined(GEO_COMPILER_INTEL)
#define geo_assume_aligned(var, alignment)      \
        __assume_aligned(var, alignment)
#elif defined(GEO_COMPILER_CLANG)
#define geo_assume_aligned(var, alignment)
        // GCC __builtin_assume_aligned is not yet supported by clang-3.3
#elif defined(GEO_COMPILER_GCC)
#if __GNUC__ >= 4 && __GNUC_MINOR__ >= 7
#define geo_assume_aligned(var, alignment)                              \
        *(void**) (&var) = __builtin_assume_aligned(var, alignment)
        // the GCC way of specifying that a pointer is aligned returns
        // the aligned pointer (I can't figure out why). It needs to be
        // affected otherwise it is not taken into account (verified by
        // looking at the output of gcc -S)
#else
#define geo_assume_aligned(var, alignment)
#endif
#elif defined(GEO_COMPILER_MSVC)
#define geo_assume_aligned(var, alignment)
        // TODO: I do not know how to do that with MSVC
#elif defined(GEO_COMPILER_EMSCRIPTEN)
#define geo_assume_aligned(var, alignment)
#elif defined(GEO_COMPILER_MINGW)
#define geo_assume_aligned(var, alignment)
#endif
 
#if   defined(GEO_COMPILER_INTEL)
#define geo_restrict __restrict
#elif defined(GEO_COMPILER_GCC_FAMILY)
#define geo_restrict __restrict__
#elif defined(GEO_COMPILER_MSVC)
#define geo_restrict __restrict
#elif defined(GEO_COMPILER_EMSCRIPTEN)
#define geo_restrict
#endif
 
        inline bool is_aligned(
            void* p, size_t alignment = GEO_MEMORY_ALIGNMENT
        ) {
            return (reinterpret_cast<size_t>(p) & (alignment - 1)) == 0;
        }
 
        inline void* align(void* p) {
            size_t offset = (
                GEO_MEMORY_ALIGNMENT -
                (reinterpret_cast<size_t>(p) & (GEO_MEMORY_ALIGNMENT - 1))
            ) & (GEO_MEMORY_ALIGNMENT - 1);
            return reinterpret_cast<char*>(p) + offset;
        }
 
#define geo_aligned_alloca(size)                                        \
        GEO::Memory::align(alloca(size + GEO_MEMORY_ALIGNMENT - 1))
 
        template <class T, int ALIGN = GEO_MEMORY_ALIGNMENT>
        class aligned_allocator {
        public:
            typedef T value_type;
 
            typedef T* pointer;
 
            typedef T& reference;
 
            typedef const T* const_pointer;
 
            typedef const T& const_reference;
 
            typedef ::std::size_t size_type;
 
            typedef ::std::ptrdiff_t difference_type;
 
            static constexpr int ALIGNMENT = ALIGN;
 
            template <class U>
            struct rebind {
                typedef aligned_allocator<U,ALIGN> other;
            };
 
            /* \brief default constructor */
            constexpr aligned_allocator() noexcept = default;
 
            /* \brief conversion copy constructor */
            template <class U, int A2> constexpr aligned_allocator(
                const aligned_allocator<U, A2>&
            ) noexcept {
            }
 
            pointer address(reference x) {
                return &x;
            }
 
            const_pointer address(const_reference x) {
                return &x;
            }
 
            pointer allocate(
                size_type nb_elt, const void* hint = nullptr
            ) {
                nb_elt = std::max(nb_elt,size_type(1));
                geo_argused(hint);
                while(true) {
                    pointer result = static_cast<pointer>(
                        aligned_malloc(sizeof(T) * nb_elt, ALIGNMENT)
                    );
                    if(result != nullptr) {
                        return result;
                    }
                    // under Linux, a process requesting more mem than available
                    // is killed (and there is nothing we can capture). Under
                    // other OSes, the standard mechanism to let the runtime
                    // know is as follows:
                    // see: https://stackoverflow.com/questions/7194127/
                    // how-should-i-write-iso-c-standard-conformant-custom-
                    // new-and-delete-operators
                    // (if there is a handler, call it repeatedly until
                    // allocation succeeds, else throw a bad_alloc exception)
                    std::new_handler handler = std::get_new_handler();
                    if(handler != nullptr) {
                        (*handler)();
                    } else {
                        throw std::bad_alloc();
                    }
                }
            }
 
            void deallocate(pointer p, size_type nb_elt) {
                geo_argused(nb_elt);
                aligned_free(p);
            }
 
            size_type max_size() const {
                ::std::allocator<char> a;
                return std::allocator_traits<decltype(a)>::max_size(a) /
                    sizeof(T);
            }
 
            void construct(pointer p, const_reference val) {
                new (static_cast<void*>(p))value_type(val);
            }
 
            void destroy(pointer p) {
                geo_argused(p); // else MSVC complains
                p->~value_type();
            }
 
            template <class T2, int A2> operator aligned_allocator<T2, A2>() {
                return aligned_allocator<T2,A2>();
            }
        };
 
        template <typename T1, int A1, typename T2, int A2>
        inline bool operator== (
            const aligned_allocator<T1, A1>&, const aligned_allocator<T2, A2>&
        ) {
            return true;
        }
 
        template <typename T1, int A1, typename T2, int A2>
        inline bool operator!= (
            const aligned_allocator<T1, A1>&, const aligned_allocator<T2, A2>&
        ) {
            return false;
        }
    }
 
    /************************************************************************/
 
    template <class T>
    class vector : public ::std::vector<T, Memory::aligned_allocator<T> > {
        typedef Memory::aligned_allocator<T> allocator;
 
        typedef ::std::vector<T, Memory::aligned_allocator<T> > baseclass;
 
 
 
    public:
        vector() :
            baseclass() {
        }
 
        explicit vector(index_t size) :
            baseclass(size) {
        }
 
        explicit vector(index_t size, const T& val) :
            baseclass(size, val) {
        }
 
        index_t size() const {
            //   casts baseclass::size() from size_t (64 bits)
            //   to index_t (32 bits), because all
            //   indices in Vorpaline are supposed to fit in 32 bits (index_t).
            // TODO: geo_debug_assert(baseclass::size() < max index_t)
            return index_t(baseclass::size());
        }
 
        T& operator[] (index_t i) {
            geo_debug_assert(i < size());
            return baseclass::operator[] (i);
        }
 
        const T& operator[] (index_t i) const {
            geo_debug_assert(i < size());
            return baseclass::operator[] (i);
        }
 
        T& operator[] (signed_index_t i) {
            geo_debug_assert(i >= 0 && index_t(i) < size());
            return baseclass::operator[] (index_t(i));
        }
 
        const T& operator[] (signed_index_t i) const {
            geo_debug_assert(i >= 0 && index_t(i) < size());
            return baseclass::operator[] (index_t(i));
        }
 
 
#ifdef GARGANTUA // If compiled with 64 bits index_t
 
        T& operator[] (int i) {
            geo_debug_assert(i >= 0 && index_t(i) < size());
            return baseclass::operator[] (index_t(i));
        }
 
        const T& operator[] (int i) const {
            geo_debug_assert(i >= 0 && index_t(i) < size());
            return baseclass::operator[] (index_t(i));
        }
 
        T& operator[] (unsigned int i) {
            geo_debug_assert(index_t(i) < size());
            return baseclass::operator[] (index_t(i));
        }
 
        const T& operator[] (unsigned int i) const {
            geo_debug_assert(index_t(i) < size());
            return baseclass::operator[] (index_t(i));
        }
#endif
 
        T* data() {
            T* result = baseclass::data();
            // Tell the compiler that the pointer is aligned, to enable AVX
            // vectorization, can be useful when using vector<double>
            // with blas-like operations. I hope the hint will propagate to
            // the caller (not sure...)
            geo_assume_aligned(result, allocator::ALIGNMENT);
            return result;
        }
 
        const T* data() const {
            const T* result = baseclass::data();
            // Tell the compiler that the pointer is aligned, to enable AVX
            // vectorization, can be useful when using vector<double>
            // with blas-like operations. I hope the hint will propagate to
            // the caller (not sure...)
            geo_assume_aligned(result, allocator::ALIGNMENT);
            return result;
        }
 
 
        void clear_and_deallocate() {
            vector<T> other;
            this->swap(other);
        }
    };
 
    template <>
    class vector<bool> : public ::std::vector<bool> {
        typedef ::std::vector<bool> baseclass;
 
    public:
        vector() :
            baseclass() {
        }
 
        explicit vector(index_t size) :
            baseclass(size) {
        }
 
        explicit vector(index_t size, bool val) :
            baseclass(size, val) {
        }
 
        index_t size() const {
            //   casts baseclass::size() from size_t (64 bits)
            //   to index_t (32 bits), because all
            //   indices in Vorpaline are supposed to fit in 32 bits (index_t).
            // TODO: geo_debug_assert(baseclass::size() < max index_t)
            return index_t(baseclass::size());
        }
 
        // TODO: operator[] with bounds checking (more complicated
        // than just returning bool&, check implementation in STL).
    };
}
 
#endif