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 or incomplete 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.

If we have two pointers referencing the same type arrays and we have lengths of those arrays can we find if those arrays do not overlap without invoking a UB?

Remark: I am not interested in examples showing me that in the real life (implementation etc) it can be done. So please do not show the code (unless you can prove that is UB free).

CodePudding user response：

It is possible in standard C, though not as efficient as a non-standard approach.

The above quoted passage from section 6.5.8p5 of the C11 standard applies to relational operators, i.e. <, >, <=, and >=. The equality operators == and != do not have this restriction. They can be used to compare any two object pointers for equality.

Specifically, section 6.5.9p6 regarding the equality operators state:

Two pointers compare equal if and only if both are null pointers, both are pointers to the same object (including a pointer to an object and a subobject at its beginning) or function, both are pointers to one past the last element of the same array object, or one is a pointer to one past the end of one array object and the other is a pointer to the start of a different array object that happens to immediately follow the first array object in the address space.

So you can check for overlap in a standard-compliant way by using == along with a pair of unsigned char * to iterate through the bytes of each object and compare their addresses for equality.

For example:

int overlap = 0;
unsigned char *o1 = (unsigned char *)&obj1;
unsigned char *o2 = (unsigned char *)&obj2;
for (int i=0; !overlap && i < sizeof obj1; i  ) {
    for (int j=0; !overlap && j < sizeof obj2; j  ) {
        if (o1   i == o2   j) {
            overlap = 1;
        }
    }
}

A more efficient approach would be to check the addresses of only the first and last bytes of one object against the addresses of each byte in the other object, since if there is an overlap then one of the two must overlap:

int overlap(const void *p1, size_t size1, const void *p2, size_t size2)
{
    const unsigned char *o1 = p1;
    const unsigned char *o2 = p2;
    for (int i=0; i < size1; i  ) {
        if ((o1   i == o2) || (o1   i == o2   size2 - 1)) {
            return 1;
        }
    }
    return 0;
}