Implement Free in dax/file providers, by changing coarse provider to internal data structure. #916
Description
-
Based on coarse provider create data structure to store blocks. Each Block can be "Free" or "Used" . If should be allways merge free blocks which are next to each other.
-
This data structure should be used to implement Free in file and dax provider.
-
Coarse provider should be removed from the project.
/**
* @brief Creates a new coarse allocator data structure.
*
* @param[out] coarse Pointer to the location where the newly created `coarse_t` structure will be stored.
* @return `umf_result_t` indicating success or failure.
*
* @note **Time Complexity:** O(1)
*/
umf_result_t coarseCreate(coarse_t** coarse);
/**
* @brief Destroys the coarse allocator and frees all associated resources.
*
* @param coarse Pointer to the `coarse_t` structure to destroy.
*
* @note **Time Complexity:** O(N), where N is the number of blocks managed.
*/
void coarseDestroy(coarse_t* coarse);
/**
* @brief Adds a non-free memory block to the allocator.
*
* @param coarse Pointer to the `coarse_t` structure.
* @param ptr Pointer to the memory block.
* @param size Size of the memory block in bytes.
* @param[out] block Optional pointer to store the newly created `block_t` structure.
* @return `umf_result_t` indicating success or failure.
*
* @note **Time Complexity:** O(log N) or better, where N is the number of blocks.
*/
umf_result_t coarseAddBlock(coarse_t* coarse, void* ptr, size_t size, block_t** block);
/**
* @brief Retrieves the block associated with a given memory address.
*
* @param coarse Pointer to the `coarse_t` structure.
* @param ptr Pointer to the memory block.
* @param[out] block Pointer to store the retrieved `block_t`.
* @return `umf_result_t` indicating success or failure.
*
* @note **Time Complexity:** O(log N)
*/
umf_result_t coarseGetBlock(coarse_t* coarse, void* ptr, block_t** block);
/**
* @brief Retrieves the memory address of a given block.
*
* @param block Pointer to the `block_t` structure.
* @return Pointer to the memory address of the block.
*
* @note **Time Complexity:** O(1)
*/
void* coarseGetAddress(block_t* block);
/**
* @brief Retrieves the size of a given block.
*
* @param block Pointer to the `block_t` structure.
* @return Size of the memory block in bytes.
*
* @note **Time Complexity:** O(1)
*/
size_t coarseGetSize(block_t* block);
/**
* @brief Finds a free block that is at least as large as the requested size.
*
* @param coarse Pointer to the `coarse_t` structure.
* @param size Minimum size required in bytes.
* @param[out] block Pointer to store the suitable free `block_t`.
* @return `umf_result_t` indicating success or failure.
*
* @note **Time Complexity:** O(log N)
*/
umf_result_t coarseFindBlock(coarse_t* coarse, size_t size, block_t** block);
/**
* @brief Splits a block into two blocks.
*
* The original block will be resized to `newSize`, and a new block will be created with the remaining size.
* The `block` pointer is updated to point to the resized block of size `newSize`.
*
* @param coarse Pointer to the `coarse_t` structure.
* @param[in,out] block Pointer to the `block_t` to split. After the function call, it will point to the resized block.
* @param newSize New size for the original block in bytes.
*
* @note **Time Complexity:** O(1)
*/
void coarseSplitBlock(coarse_t* coarse, block_t** block, size_t newSize);
/**
* @brief Marks a block as free and attempts to merge it with adjacent free blocks.
*
* If merging is successful, the `block_t` pointer is updated to the new merged block.
*
* @param coarse Pointer to the `coarse_t` structure.
* @param block Pointer to a pointer of the `block_t` to set as free.
* @return `true` if a merge occurred and the `block_t` pointer was updated; `false` otherwise.
*
* @note **Time Complexity:** O(1)
*/
bool coarseSetFree(coarse_t* coarse, block_t** block);
/**
* @brief Marks a block as used.
*
* @param coarse Pointer to the `coarse_t` structure.
* @param block Pointer to the `block_t` to set as used.
*
* @note **Time Complexity:** O(1)
*/
void coarseSetUsed(coarse_t* coarse, block_t* block);
/**
* @brief Retrieves the previous block in address order.
*
* @param block Pointer to the current `block_t` structure.
* @return Pointer to the previous `block_t` in address order, or `NULL` if there is none.
*
* @note Blocks are sorted by their memory address.
*
* @note **Time Complexity:** O(1)
*/
block_t* coarsePreviousBlock(block_t* block);
/**
* @brief Retrieves the next block in address order.
*
* @param block Pointer to the current `block_t` structure.
* @return Pointer to the next `block_t` in address order, or `NULL` if there is none.
*
* @note Blocks are sorted by their memory address.
*
* @note **Time Complexity:** O(1)
*/
block_t* coarseNextBlock(block_t* block);
/**
* @brief Merges two adjacent blocks if possible.
*
* Attempts to merge `block1` and `block2` if they are adjacent in memory.
* If merging is successful:
* - `*block1` is updated to point to the new merged block.
* - `*block2` is set to `NULL`.
*
* @param coarse Pointer to the `coarse_t` structure.
* @param[in,out] block1 Pointer to the first `block_t`. Will be updated to the merged block on success.
* @param[in,out] block2 Pointer to the second `block_t`. Will be set to `NULL` on success.
* @return `true` if the blocks were successfully merged; `false` otherwise.
*
* @note **Time Complexity:** O(1)
*/
bool coarseMergeBlocks(coarse_t* coarse, block_t** block1, block_t** block2);