I am trying to build a system for slab allocation, where slabs are contiguous of memory of int data that are constantly recycled. A slab is allocated independently, and stored in a block. If I am done with the int, I want to mark it as done for recycling / garbage collection / reference counting. To find out what slab the int pointer is in, I have decided that I will do a binary search on the memory addresses of the blocks. The blocks are arranged in order by their memory addresses, except block zero, which is the active block.
struct block { size_t size; int *slab; };
struct blocks { struct block *data; size_t size, capacity; };
/** @return Index of block that is higher than `x` in `blocks`.
@order \O(\log `blocks`) */
static size_t upper(const struct blocks *const blocks,
const int *const x) {
const struct block *const base = blocks->data;
size_t n, b0, b1;
if(!(n = blocks->size)) return 0;
if(!--n) return 1;
/* The last one is a special case: it doesn't have an upper bound. */
for(b0 = 1, --n; n; n /= 2) {
b1 = b0 + n / 2;
if(x < base[b1].slab) { continue; }
else if(base[b1 + 1].slab <= x) { b0 = b1 + 1; n--; continue; }
else { return b1 + 1; }
}
return b0 + (x >= base[slots->size - 1].slab);
}
static size_t slab_idx(const struct blocks *const blocks,
const int *const x) {
struct block *const base = blocks->data;
/* One chunk, assume it's in that chunk; first slab is `capacity`. */
if(blocks->size == 1
|| (x >= base[0].slab && x < base[0].slab + blocks->capacity))
return 0;
return upper(blocks, x) - 1;
}
The C11 standard 6.5.8¶5, reads,
When two pointers are compared, the result depends on the relative locations in the address space of the objects pointed to. If two pointers to object types both point to the same object, or both point one past the last element of the same array object, they compare equal. If the objects pointed to are members of the same aggregate object, pointers to structure members declared later compare greater than pointers to members declared earlier in the structure, and pointers to array elements with larger subscript values compare greater than pointers to elements of the same array with lower subscript values. All pointers to members of the same union object compare equal. If the expression P points to an element of an array object and the expression Q points to the last element of the same array object, the pointer expression Q+1 compares greater than P. In all other cases, the behavior is undefined.
This works, but invokes undefined behaviour. Would converting them into uintptr_t work? Specifically any solutions for C90?
