Arena Allocator in Rust

Arena allocators, also known as pool allocators, are a memory allocation strategy that pre-allocates a large chunk of memory (the "arena") and then allocates smaller blocks from within that arena. This approach can be significantly faster than traditional heap allocation, especially when dealing with many small allocations and deallocations of objects of similar size. This challenge asks you to implement a basic arena allocator in Rust, focusing on efficiency and safety.

Problem Description

You are tasked with creating a simple arena allocator in Rust. The arena allocator should provide methods for allocating and deallocating memory blocks from a pre-allocated arena. The allocator should manage a list of free blocks within the arena, allowing for efficient allocation and deallocation. The primary goal is to demonstrate understanding of memory management and data structures in Rust, while ensuring memory safety.

Key Requirements:

Initialization: The arena allocator should be initialized with a specified arena size.
Allocation: The allocate() method should allocate a block of memory of a given size from the arena. If sufficient memory is available, it should return a pointer to the allocated block. If not, it should return None.
Deallocation: The deallocate() method should deallocate a previously allocated block of memory, returning a boolean indicating success (true) or failure (false).
Safety: The allocator must be memory-safe, preventing double-free errors, use-after-free errors, and out-of-bounds access.
Efficiency: The allocator should be reasonably efficient in allocating and deallocating blocks. A simple linked list for free blocks is acceptable.

Expected Behavior:

The arena should be initialized with a given size.
allocate() should return Some(pointer) if allocation is successful, and None otherwise.
deallocate() should return true if deallocation is successful, and false otherwise (e.g., if the pointer is invalid or has already been freed).
The arena should prevent allocation of blocks larger than the remaining free space.
The arena should prevent deallocation of invalid pointers.

Edge Cases to Consider:

Allocation requests exceeding the arena's remaining free space.
Deallocating the same block twice.
Deallocating a pointer that was not allocated by the arena.
Arena initialization with a size of 0.

Examples

Example 1:

Input: Arena::new(1024)
allocate(100); // Returns Some(pointer)
allocate(200); // Returns Some(pointer)
allocate(800);  // Returns None (not enough space)
deallocate(first_pointer); // Returns true
allocate(100); // Returns Some(pointer)

Output: Some(pointer1), Some(pointer2), None, true, Some(pointer3) Explanation: The arena is initialized with 1024 bytes. Two blocks of 100 and 200 bytes are allocated. The third allocation of 800 bytes fails because there isn't enough space. The first block is deallocated, freeing up 100 bytes. The fourth allocation of 100 bytes succeeds.

Example 2:

Input: Arena::new(512)
allocate(256); // Returns Some(pointer)
deallocate(pointer); // Returns true
deallocate(pointer); // Returns false (already freed)

Output: Some(pointer), true, false Explanation: A block of 256 bytes is allocated. It is then deallocated successfully. Attempting to deallocate the same block again results in failure.

Example 3: (Edge Case)

Input: Arena::new(0)
allocate(100); // Returns None

Output: None Explanation: Initializing the arena with a size of 0 should immediately prevent any allocations.

Constraints

The arena size will be a positive integer (or 0 for the edge case).
Allocation sizes will be positive integers.
The arena size should be large enough to accommodate at least one allocation of size 1.
The allocator should be implemented without using external crates (e.g., linked-list). You can use standard library features.
Performance is not the primary focus, but the implementation should be reasonably efficient. Avoid unnecessary copying or allocations.

Notes

Consider using a linked list to manage free blocks within the arena.
Use Rust's ownership and borrowing system to ensure memory safety.
Think about how to handle allocation failures gracefully.
The allocate() method should return a raw pointer (*mut u8) to the allocated memory.
The deallocate() method should take a raw pointer as input.
Error handling should be done through Option and Result types where appropriate.
Focus on clarity and correctness over extreme optimization. A functional, safe, and understandable implementation is preferred.