Wed, 18 Sep 2024 00:02:18 +0200
apply binary search in cx_array_insert_sorted()
resolves #416
relates to #424
/* * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. * * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. 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. * * 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. */ /** * \file allocator.h * Interface for custom allocators. */ #ifndef UCX_ALLOCATOR_H #define UCX_ALLOCATOR_H #include "common.h" #ifdef __cplusplus extern "C" { #endif /** * The class definition for an allocator. */ typedef struct { /** * The allocator's malloc() implementation. */ void *(*malloc)( void *data, size_t n ); /** * The allocator's realloc() implementation. */ void *(*realloc)( void *data, void *mem, size_t n ) __attribute__((__warn_unused_result__)); /** * The allocator's calloc() implementation. */ void *(*calloc)( void *data, size_t nelem, size_t n ); /** * The allocator's free() implementation. */ void (*free)( void *data, void *mem ) __attribute__((__nonnull__)); } cx_allocator_class; /** * Structure holding the data for an allocator. */ struct cx_allocator_s { /** * A pointer to the instance of the allocator class. */ cx_allocator_class *cl; /** * A pointer to the data this allocator uses. */ void *data; }; /** * High-Level type alias for the allocator type. */ typedef struct cx_allocator_s CxAllocator; /** * A default allocator using standard library malloc() etc. */ extern CxAllocator *cxDefaultAllocator; /** * Function pointer type for destructor functions. * * A destructor function deallocates possible contents and MAY free the memory * pointed to by \p memory. Read the documentation of the respective function * pointer to learn if a destructor SHALL, MAY, or MUST NOT free the memory in that * particular implementation. * * @param memory a pointer to the object to destruct */ typedef void (*cx_destructor_func)(void *memory) __attribute__((__nonnull__)); /** * Function pointer type for destructor functions. * * A destructor function deallocates possible contents and MAY free the memory * pointed to by \p memory. Read the documentation of the respective function * pointer to learn if a destructor SHALL, MAY, or MUST NOT free the memory in that * particular implementation. * * @param data an optional pointer to custom data * @param memory a pointer to the object to destruct */ typedef void (*cx_destructor_func2)( void *data, void *memory ) __attribute__((__nonnull__(2))); /** * Re-allocate a previously allocated block and changes the pointer in-place, if necessary. * * \par Error handling * \c errno will be set by realloc() on failure. * * @param mem pointer to the pointer to allocated block * @param n the new size in bytes * @return zero on success, non-zero on failure */ int cx_reallocate( void **mem, size_t n ) __attribute__((__nonnull__)); /** * Allocate \p n bytes of memory. * * @param allocator the allocator * @param n the number of bytes * @return a pointer to the allocated memory */ void *cxMalloc( CxAllocator const *allocator, size_t n ) __attribute__((__malloc__)) __attribute__((__alloc_size__(2))); /** * Re-allocate the previously allocated block in \p mem, making the new block \p n bytes long. * This function may return the same pointer that was passed to it, if moving the memory * was not necessary. * * \note Re-allocating a block allocated by a different allocator is undefined. * * @param allocator the allocator * @param mem pointer to the previously allocated block * @param n the new size in bytes * @return a pointer to the re-allocated memory */ void *cxRealloc( CxAllocator const *allocator, void *mem, size_t n ) __attribute__((__warn_unused_result__)) __attribute__((__alloc_size__(3))); /** * Re-allocate a previously allocated block and changes the pointer in-place, if necessary. * This function acts like cxRealloc() using the pointer pointed to by \p mem. * * \note Re-allocating a block allocated by a different allocator is undefined. * * \par Error handling * \c errno will be set, if the underlying realloc function does so. * * @param allocator the allocator * @param mem pointer to the pointer to allocated block * @param n the new size in bytes * @return zero on success, non-zero on failure */ int cxReallocate( CxAllocator const *allocator, void **mem, size_t n ) __attribute__((__nonnull__)); /** * Allocate \p nelem elements of \p n bytes each, all initialized to zero. * * @param allocator the allocator * @param nelem the number of elements * @param n the size of each element in bytes * @return a pointer to the allocated memory */ void *cxCalloc( CxAllocator const *allocator, size_t nelem, size_t n ) __attribute__((__malloc__)) __attribute__((__alloc_size__(2, 3))); /** * Free a block allocated by this allocator. * * \note Freeing a block of a different allocator is undefined. * * @param allocator the allocator * @param mem a pointer to the block to free */ void cxFree( CxAllocator const *allocator, void *mem ) __attribute__((__nonnull__)); #ifdef __cplusplus } // extern "C" #endif #endif // UCX_ALLOCATOR_H