是否可以在C(不调用UB)中检查两个对象是否重叠?

这在标准C中是可能的,尽管不如非标准方法有效。

上述引用的段落来自 C11 standard 适用于关系运算符,即。 < , > , <= 和 >= .相等运算符 == 和 != 没有这个限制。它们可以用来比较 任何 两个相等的对象指针。

具体而言,关于等式运算符的第6.5.9p6节规定:

两个指针比较相等当且仅当两者都是空指针,两者 是指向同一对象的指针(包括指向对象的指针和 开头的子对象)或函数,两者都是指向一个的指针 经过同一数组对象的最后一个元素,或者其中一个是指向 一个经过一个数组对象的末尾,另一个是指向 恰好紧随其后的另一个数组对象的开头 地址空间中的第一个数组对象。

因此,您可以通过使用以符合标准的方式检查重叠 == 以及一对 unsigned char * 以遍历每个对象的字节,并比较它们的地址是否相等。

例如:

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;
        }
    }
}

一种更有效的方法是仅检查一个对象的第一个字节的地址与另一个对象中每个字节的地址,因为如果存在重叠,则一个对象必须在另一个内:

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) {
            return 1;
        }
    }
    for (int i=0; i < size2; i++) {
        if (o2 + i == o1) {
            return 1;
        }
    }
    return 0;
}

公认的答案是通过参考语言标准的适当部分来解决OP的问题。但是,如果第一个对象(数组)是第二个对象(阵列)的子集,使得第一个对象与第二个物体完全重叠,但排除了第二个目标的开始和结束元素,即像这样重叠,则在接受答案中发布的第二段代码将失败-

                             object 2
                                |
    +-----------------------------------------------------------+
    |                                                           |
    |                                                           |

    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
    |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

        |                                                   |
        |                                                   |
        +---------------------------------------------------+
                                |
                             object 1 (any subset of this region)

这篇文章只是为了解决@dbushpost第二个代码片段中的问题而进行的几次修改,并通过考虑所讨论的数组的元素类型的大小使其更加高效。

/*
 * Parameters:
 * obj1    : Pointer to array1
 * obj1_sz : Size of array1
 * obj2    : Pointer to array2
 * obj2_sz : Size of array2
 * type_sz : Size of type of elements of array
 *
 * Return:
 * 0 - No overlap
 * 1 - Overlap
 *
 * [Assumption: Both array1 and array2 are of same type]
 */

int check_overlap (const void *obj1, size_t obj1_sz, const void *obj2, size_t obj2_sz, size_t type_sz) {
    const unsigned char *pobj1 = obj1;
    const unsigned char *pobj2 = obj2;
    size_t sz1 = obj1_sz;
    size_t sz2 = obj2_sz;

    if (obj1_sz < obj2_sz) {
            pobj1 = obj2;
            pobj2 = obj1;
            sz1 = obj2_sz;
            sz2 = obj1_sz;
    }

    for (size_t i = 0; i < sz1; ++i) {
            if ((pobj1 + (i * type_sz) == pobj2) ||
                (pobj1 + (i * type_sz) == pobj2 + ((sz2 - 1) * type_sz))) {
                    return 1;
            }
    }
    return 0;
}

您可以在线性时间中检查是否&obj1[i]==&obj2[0]对于一些i,或者&obj1[0]==&obj2[i]对于一些i,并以此方式确定是否存在重叠。

在执行此操作之前,您将obj1和obj2强制转换为uintptr_t,假设(没有证据)强制转换到uintpttr_t的指针的行为类似于char*,并计算i,j,使得&obj1[i]应该等于&obj2[j]根据您的假设,并且这两个指数都是有效的。由于比较相等或不相等的不相关指针不会调用UB,因此 可以 能够以这种方式证明阵列是重叠的。如果您的实现很奇怪,那么这没有帮助,但也不会给您带来错误的结果。如果数组不重叠,它也不起作用。在这种情况下,请返回第一种方法。