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.

Answer 4

I am not even sure one can add pointers in C.

Subtracting two pointers returns the distance between them: the number of elements between them (not the size in bytes or anything else).

This sub-expression, as you said, first goes one past the last element:

allocbuf + ALLOCSIZE

Then, by subtracting allocp, it returns the distance between this one-past-the-last-element pointer, and the next free position stored in allocp

(allocbuf + ALLOCSIZE) - allocp

If this distance is superior to n, it means there is still room for at least n more elements in allocbuf.

Answer 5

In the end, think of allocbuf and allocp as numbers:

Now, we do not know which number, but lets say we know that allocp'' points to some element ofallocbuf``.

Then, allocp - allocbuf is the index of the element that allocp is pointing to (remember, think of them as numbers - at least as long as they point to the same memory object).

So in conclusion, allocbuf + ALLOCSIZE - allocp is ALLOCSIZE - "the index of allocbuf that allocp is pointing to". In other words, the number of leftover elements.

The condition then checks if there are enough leftover elements.

Answer 6

allocbuf + ALLOCSIZE - allocp >= n

Can be expanded to

(allocbuf + ALLOCSIZE) - allocp >= n

To show what is happening.

(allocbuf + ALLOCSIZE) returns a pointer ALLOCSIZE elements in memory after wherever allocbuf points. For example, as allocbuf points to the first element, and ALLOCSIZE is 1000, the operation returns the element (pointer) 1000 elements after allocbuf (this is actually undefined memory; it is one element after the last allocated element, so undefined behaviour would occur if this pointer were to be dereferenced).

Once (allocbuf + ALLOCSIZE) has been deduced, once the pointer allocp has been taken from it, it will return a type like size_t (unsigned), which gives the amount of elements between (allocbuf + ALLOCSIZE) and allocp. For example, if allocp pointed to the 403rd element, and someone wanted to allocate 637 elements from the function alloc, it would do the following:

allocbuf + ALLOCSIZE - allocp - get the amount of spare elements

allocbuf + ALLOCSIZE - allocp >= n see if it is larger than or equal to n. If so, it can allocate.