How to correcly check whether a pointer belongs within an allocated block?

Question

After reading many questions about pointer comparison, I've come to realize that many of my custom allocators does a comparison that's unspecified behavior. An example could be something like this:

template <int N, int CAPACITY>
class BucketList
{
    struct Bucket
    {
        Bucket* next { nullptr };      // The next bucket, to create a linked list.
        size_t  size { 0 };            // Size allocated by the bucket.
        uint8_t data[CAPACITY] { 0 };
    };

    Bucket* free;  // The first bucket that has free space.
    Bucket* next;  // The next bucket, to create a linked list.

public:
    BucketList()
    {
        this->next = new Bucket;
        this->free = this->next;
    }

    uint8_t* allocate()
    {
        auto* bucket = this->free;

        if (bucket->used + N >= CAPACITY)
        {
            bucket->next = new Bucket;
            this->free   = bucket->next;
            bucket       = bucket->next;
        }

        uint8_t* base = bucket->data + bucket->used;
        bucket->used_size += N;
        return base;
    }

    uint8_t* deallocate(uint8_t* ptr)
    {
        auto* bucket = this->next;
        while (bucket && !(bucket->data <= ptr && ptr < bucket->data + CAPACITY))
            bucket = bucket->next;
        
        if (bucket)
            // Bucket found! Continue freeing the object and reorder elements.
        else
            // Not allocated from here. Panic!
    }

    // And other methods like destructor, copy/move assignment, and more...
};

The allocate function returns a small chunk of data from the allocated array. To deallocate, it checks whether the pointer comes from a bucket by checking if its address is within the address range of the bucket (i.e. with (bucket->data <= ptr && ptr < bucket->data + CAPACITY)). However, all buckets come from different allocations, so this comparison is unspecified.

I don't want to change the interface, if possible. I've also read that it's possible to use std::less to get a strict total order on pointer types, but I'm unable to understand whether this would solve my problem or just make the comparison specified.

Is there a correct way to check whether a pointer belongs within an allocated block (and also that a pointer does not belong to a block)?

Answer 1

The short answer is no. A good explanation is here.

Some work-around solutions could be:

1. Return a custom object that has a reference to the allocated base pointer. As equality comparison isn't unspecified, you should be able to compare it to the base pointer of the collection. The custom object could implement the interface of a pointer as well for convenience. Something like:

    class Pointer
    {
        uint8_t* base;
        size_t   offset;
   
    public:
        // Dereference operator.
        uint8_t operator*() { return this->base[offset]; }
   
        // Implement the methods and operators required for 
        // your use case.
    };
   

2. Create a collection (array, hash map, set, ...) to keep track of the pointers. For the same reason as above (you can compare for equality), you can search for the pointer to see if it's something you've given out. This is potentially slow or memory inefficient.

3. Don't give the option to pass in pointers not allocated from new or malloc (if possible). In the collection in the question, it might be better to provide an API for deallocating whole buckets instead of an API for small fragments. This is the best solution is feasible.