What is happening with this arithmetic expression involving pointers?

Question

Here is the code in C:

#define ALLOCSIZE 1000 /* size of available space */

static char allocbuf[ALLOCSIZE]; /* storage for alloc */
static char *allocp = allocbuf; /* next free position */

char *alloc(int n) /* return pointer to n characters */
{
    if (allocbuf + ALLOCSIZE - allocp >= n) { /* it fits */
        ...
    }
}

I don't understand what is happening in the following expression:

allocbuf + ALLOCSIZE - allocp >= n

I know allocbuf as an array name is equivalent to a pointer to the first element &allocbuf[0], and obviously allocp is a pointer, and finally that ALLOCSIZE is a simple int. So adding ALLOCSIZE to allocbuff gives the ALLOCSIZE indexed element of allocbuff which is also a pointer. But subtracting the pointer allocp from pointer &allocbuf[ALLOCSIZE] is where I am lost. I am not even sure one can add pointers in C.

Please tell me where I am wrong or what I am missing in this interpretation.

The point of this program is to store characters.

Answer 1

The code is a fixed-buffer allocator, and is checking to make sure you have at least n bytes left. It helps to view things pictorially, and by pictorially I mean with MSPaint:

So breaking down the expression:

allocbuf + ALLOCSIZE - allocp >= n

allocbuf + ALLOCSIZE is the end of the array. The difference between the end and allocp is the remaining bytes. So we just check to make sure that difference is at least n.

Subtracting two pointers, as long as they point to elements within the same array (or one-past-the-end), is well-defined as the number of elements between them. As a simpler example, allocbuf and allocbuf + ALLOCSIZE are both pointers (of type char*), and (allocbuf + ALLOCSIZE) - allocbuf == ALLOCSIZE, the number of elements (of type char, in this case) between them.

Answer 2

Subtracting pointer from pointer will give you (if they are compatible) number of elements (size is determined by the type the pointers point to) between them.

So:

allocbuf + ALLOCSIZE

pointer pointing after the last element of allocbuf

allocbuf + ALLOCSIZE - allocp

amount of elements left between last element of allcobuf (+ 1) and allocp

In which case:

allocbuf + ALLOCSIZE - allocp >= n

determines if enough elements are left in allocbuf to fit n elements.

Edit:

You can compare it to arrays: If you have pointer to first element (which would be indexed with 0) and second pointer, which points 4 times the size of element further (which would point to 5th element indexed with 4), then when you are subtracting these two you will get 4 elements between them (like subtracting index 0 from index 4). But it only makes sense, when pointers point to the same buffer of memory (like in arrays).

So this:

int array[5] = {1, 2, 3, 4, 5, 6};
int a* = &array[0] //equivalent to array
int b* = &array[4]

and this:

int *array = malloc(6 * sizeof(int));
//set array values
int *a = array;
int *b = array + 5;

Is (almost) the same.

Answer 3

The expression allocbuf + ALLOCSIZE - allocp will give the number of elements in between pointers &allocbuf[ALLOCSIZE] and pointer allocp.
allocbuf + ALLOCSIZE - allocp >= n simply checks whether n is less than that of elements in between pointers &allocbuf[ALLOCSIZE] and allocp or not.

Note that

C11: 6.5.6 Additive operators (p9):

When two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object; the result is the difference of the subscripts of the two array elements. [...].
In other words, if the expressions P and Q point to, respectively, the i-th and j-th elements of an array object, the expression (P)-(Q) has the value i−j provided the value fits in an object of type ptrdiff_t.