如果我们有两个指向相同类型的数组的指针,并且我们有这些数组的长度,我们能否找到这些数组是否不重叠而不引发未定义行为?
备注:我不感兴趣的是展示在实际生活中(实现等)可以完成的示例。因此,请不要展示代码(除非您可以证明[标准上]没有未定义行为)。
在标准C中是可能的,但不如非标准方法高效。
上述引用来自第6.5.8p5节的C11标准,适用于关系运算符,即<
、>
、<=
和>=
。相等运算符==
和!=
没有此限制。它们可以用于比较任何两个对象指针的相等性。
具体而言,关于相等运算符的第6.5.9p6节规定:
当且仅当两个空指针都是null指针、都是指向同一对象(包括指向对象及其开头的子对象)或函数、都是指向同一数组对象的最后一个元素之后的一个指针,或者一个是指向一个数组对象的末尾之后的一个指针,另一个是指向紧随第一个数组对象之后的不同数组对象的开头的指针时,两个指针才相等。
你可以通过使用一对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)
这篇文章只是对@dbush的第二个代码片段中出现的问题进行了一些修改,并通过考虑所讨论数组的元素类型的大小,使其更加高效。
/*
* 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;
}
不具备可移植性。存在几个误判情况。
设备(例如 RAM、ROM 或内存映射 I/O)通常不会使用处理器的所有地址引脚。通常,设备需要的地址线数量会连接到处理器的最低位地址线,最高位地址线用于选择设备,中间的地址线未连接:
MSB -------- Address bus -------- LSB
| | ... | | x x ... x x | | ... | |
chip select unconnected to device
这样的设备可以在地址空间中被称为块。然而,该设备在地址空间中也出现为其他几个块;每个块物理上指向设备上相同的位置!这种效果被称为内存别名,比你想象的要常见得多。
例如,假设一个系统有16位地址。可能使用顶部4个地址线来选择正在寻址的芯片。假设我们将一个设备分配给A15:A12 == 0xE。此外,该设备只有8条地址线输出,因此我们将其连接到A7:A0。
该设备出现在地址0xE000到0xE0FF处。但是,它还出现在0xE100到0xE1FF处。实际上,它在地址空间中出现了16次,在任何块0xEz00到0xEzFF处。更糟糕的是,每个块物理上都指向同一件事情。对0xE123的访问与对0xE223、0xE323、0xE423等的访问相同。
因此,您可以在内存中拥有两个对象,它们似乎指向内存的不同区域,但实际上指向相同的事物:
char *x = (char *)0xE000;
char *y = (char *)0xE300;
if (overlap(x, y, 16)) { ... }
overlap()
会将它们报告为两个不同的对象。但是,它们是同一个对象;对x[]
的写入会改变y[]
。因此,在这种情况下,您将得到一个错误的负数。正确的overlap()
实现需要并依赖于系统内存映射的完全了解,使得这样的函数完全不可移植。
x
和y
是进程A中重叠的对象。然后,我们使用操作系统在进程A和进程B之间创建共享内存。具体而言,xx
是进程B中指向x
的共享内存指针,yy
是进程B中指向y
的共享内存指针。x
和y
确实重叠的函数并不难。
但是,根据操作系统的不同,进程B中的指针xx
和yy
可能看起来与重叠对象完全不同。但实际上,它们确实指向重叠对象。因此,您将得到一个错误的负面结果。
理论上是否可能编写一个跨进程检查重叠的函数?可能,但请记住,我可以让问题变得更加困难。我可以创建xx
和yy
的子集,仍然重叠;我可以共享从进程B到第三个进程的内存等。无论如何,任何这样的解决方案都是不可移植的。
原始IBM PC上使用了一种称为“分段”的内存映射类型。一个名为“段”的16位寄存器乘以16,然后加上另一个带有“基地址”的16位寄存器,以获得20位物理地址。
需要少于64k内存的程序可以只使用16位基地址,称为“近指针”。但是需要超过64k内存的程序必须维护32位“远指针”,其中包含段和基地址。
由于分段的指针算术,很容易使两个看起来非常不同但指向同一对象的远指针:
far char *x = (far char *)0x12340005L;
far char *y = (far char *)0x10002345L;
x
和y
都指向相同的物理地址0x12345,尽管它们的位模式非常不同。x == y
视为false,因为它们具有不同的位模式。其他编译器会进行计算(带来性能损失)并返回true。还有一些编译器可以通过命令行开关或#pragma
让您选择其中一种行为。
OP 抱怨这些示例所代表的编译器并不符合“标准规范”。他们认为,如果两个指针确实指向同一对象,则标准要求它们必须进行==
比较。
如果您要成为这样的 语言律师,那么没有任何编译器符合标准。不是gcc,也不是微软C(两个自豪地遵守规范的编译器)。基本上每个拥有C编译器的系统都存在某种程度的内存别名(反例#1)。因此,每个C编译器都允许两个!=
指针指向同一个东西。
另一方面,如果您根据其预期含义而不是字面含义解释标准,则这些编译器确实符合标准。
当然,这些是边缘情况。大多数程序都在用户空间中,在那里#1被隐藏了起来。很少有程序使用共享内存(#2)。没有人喜欢在分段内存模型(#3)中进行编程。但是像这样的异常情况是标准具有许多未定义行为实例的原因;许多在一种情况下可以正常工作的事情在其他情况下无法以同样的方式工作。==
方面正确地表现。在标准之外创建的对象自然不受标准约束。实现会小心确保它们自己创建的对象行为正确。如果您开始以非标准的方式创建对象,则实现没有义务以标准方式处理它们。 - Raymond Chen好吧,如果我们要语言律师的话,我给你提出这个问题:
// SPDX-License-Identifier: CC0-1.0
#include <stddef.h>
#include <stdbool.h>
#include <stdint.h>
bool overlap(const void *p1, size_t s1, const void *p2, size_t s2)
{
const uintptr_t p1b = (uintptr_t) p1;
const uintptr_t p2b = (uintptr_t) p2;
const uintptr_t p1e = (uintptr_t) ((char*) p1 + (s1 - 1));
const uintptr_t p2e = (uintptr_t) ((char*) p2 + (s2 - 1));
return (p1b <= p2b && p2b <= p1e)
|| (p2b <= p1b && p1b <= p2e);
}
[1]: ISO/IEC 9899:2018,§ 6.3.2.3,第6段("任何指针类型都可以转换为整数类型。除非先前指定,否则结果是实现定义的。")。
好的,既然您没有提到保留数据的事情:
#include <stdbool.h>
#include <stddef.h>
#include <string.h>
bool overlaps(void* p1, void* p2, size_t sz1, size_t sz2) {
if (!p1 || !p2 || !sz1 || !sz2) return false; /* empty ranges ignored */
memset(p1, 0, sz1);
memset(p2, 1, sz2);
return !!memchr(p1, 1, sz1);
}
这是完全定义明确的。
overlaps("123456", "123", 7,4);
- 0___________你可以在线性时间内检查 &obj1[i] == &obj2[0] 是否成立,或者 &obj1[0] == &obj2[i] 是否成立,从而确定是否存在重叠。
在进行此操作之前,你需要将 obj1 和 obj2 转换为 uintptr_t 类型,并假设(没有证据)指针转换为 uintptr_t 类型类似于 char*,并计算 i、j 使得根据您的假设 &obj1[i] 应该等于 &obj2[j],同时两个索引都是有效的。由于比较不相关的指针的相等或不相等不会引发 UB,因此你也许能够通过这种方式证明数组是否重叠。如果你的实现很奇怪,则这并没有什么帮助,但也不会给你错误的结果。如果数组不重叠,这种方法也无效。在这些情况下,你需要回到第一种方法。
当这些对象有其他(不同的)对象作为成员(子对象)时,问题可能会更加复杂,而这些子对象也可能重叠,例如字符串数组。
您的重叠问题实际上是一个程序逻辑问题,因为每个对象都应该有自己的内存或一些共享数据来自于数据存储,这样就没有人拥有它了。 根据问题的不同,您还可以使用一个额外的内存结构体数组,维护所有组件的起始和结束地址,然后只需比较地址即可。
language-lawyer
标签表明这是严格的语言层面学术问题。 - 0___________
union
中? - Karl Knechtel