什么时候确定指针差异?
我有一个关于指针差异和结果类型的问题, ptrdiff_t
。
C99§6.5.6(9)说:
当减去两个指针时,两个指针都指向同一个数组对象的元素,或者指向数组对象的最后一个元素的元素; 结果是两个数组元素的下标的差异。 结果的大小是实现定义的,其类型(有符号整数类型)是标头中定义的
ptrdiff_t
。 如果结果在该类型的对象中无法表示,则行为未定义。 换句话说,如果表达式P和Q分别指向数组对象的第i和第j个元素,则表达式(P) – (Q)具有值i-j,条件是该值适合于ptrdiff_t
类型的对象。
§7.18.3(2)要求ptrdiff_t
的范围至少为[-65535,+ 65535]
我感兴趣的是如果结果太大则未定义的行为。 我无法在标准中找到任何保证至少与size_t
的签名版本或类似内容相同的范围。 所以,现在我的问题是:一致的实现是否可以使ptrdiff_t
成为带符号的16位类型但size_t
64位? [编辑:正如Guntram Blohm所指出的那样,16位有符号最多会产生32767,所以我的例子显然不符合]据我所知,我不能在严格符合代码甚至超过65535个元素的数组上做任何指针减法如果实现支持比这大得多的对象。 此外,该程序甚至可能崩溃。
理由(V5.10)§6.5.6说:
重要的是要对这种类型[
ptrdiff_t
]进行签名,以便在处理同一数组中的指针时获得正确的代数排序。 但是,指针差异的大小可以与可以声明的最大对象的大小一样大; 由于这是一个无符号类型,两个指针之间的差异可能会导致某些实现溢出。
这可以解释为什么不需要指定每个指针差异(对同一个数组的元素),但是它没有解释为什么对PTRDIFF_MAX
没有限制至少为SIZE_MAX/2
(具有整数除法) 。
为了说明,假设T
是任何对象类型,并且n
是在编译时未知的size_t
对象。 我想为T
n
对象分配空间,我想用指定范围内的地址进行指针减法。
size_t half = sizeof(T)>1 ? 1 : 2; // (*) if( SIZE_MAX/half/sizeof(T)<n ) /* do some error handling */; size_t size = n * sizeof(T); T *foo = malloc(size); if(!foo) /* ... */;
我不得不严格遵守
if( SIZE_MAX/sizeof(T) < n || PTRDIFF_MAX < n )
代替。 真的那样吗? 如果是这样,有人知道原因(即不要求PTRDIFF_MAX >= SIZE_MAX/2
[编辑:更改>
到>=
]或类似的东西)?
(*)第一版中的一半是我在写这篇文章时认出的东西,我有
if( SIZE_MAX/2/sizeof(T) < n )
首先,用SIZE_MAX
的一半来解决基本原理中提到的问题; 但后来我意识到,如果sizeof(T)
为1,我们只需要一半SIZE_MAX
。鉴于此代码,第二个版本(肯定严格符合的版本)似乎并不那么糟糕。 但是,如果我是对的,我仍感兴趣。
C11保留了§6.5.6(9)的措辞,C ++相关的答案也很受欢迎。
为了给出标题中问题的答案:指针差异本身不能用于确定两个指针的差异而不会最终导致未定义的行为。 正如您所注意到的,在PTRDIFF_MAX
远小于对象的可能大小的系统上,这将是一个严重的限制。 但是这样的系统很少见(我不知道),所以如果你的代码依赖于能够与大对象区别开来的话,你总会把
#if PTRDIFF_MAX < SIZE_MAX/2 # error "we need an architecture with sufficiently wide ptrdiff_t" #endif
但即使在这种情况下( ptrdiff_t
太窄),您也总是可以计算同一个较大对象的两个指针之间的差异。
- 确定两个(
p
或q
)中的哪一个更小。 这总是很明确。 - 假设
p
是较小的一个,然后测试所有p + i
的size_t i
从1
开始直到你达到q
或者i
是SIZE_MAX
。 - 如果最终的
i
是SIZE_MAX
且你没有达到q
则差异无法表示。 否则,i
加上最终的标志就是你要找的信息。
这不是很令人满意,但我无法弄清楚如何将线性算法改进为对数:为了避免UB,我们不允许在比较时超越q
。
而且,正如我所说,你只需要一些非常奇特的建筑。
编辑:
使用mafso获取指针差异的最高位的技巧,这可以在O(log(n))
中完成,其中n
是所需的距离。 首先声明两个假设p < q
内部函数
// computes the maximum value bit of the pointer difference // // assumes that p < q inline uintmax_t ptrdiff_maxbit(char const* p, char const* q) { uintmax_t len = 1; while (p+len <= q-len) len <<= 1; return len; } // compute the pointer difference // // assumes that p < q // assumes that len2 is a power of two // assumes that the difference is strictly less than 2*len2 inline uintmax_t ptrdiff_bounded(char const* p, char const* q, uintmax_t len2) { if (len2 < 2) return len2; uintmax_t len = (len2 >> 1); p += len; q -= len; for (; len; len >>= 1) if (p + len <= q) { len2 |= len; p += len; } return len2; }
然后定义计算字节差异的函数,并在intmax_t
无法表示差异时添加约定:
inline intmax_t ptrdiff_byte(void const* p0, void const* q0) { char const * p = p0; char const * q = q0; if (p == q) return 0; if (p < q) { uintmax_t ret = ptrdiff_bounded(p, q, ptrdiff_maxbit(p, q)); if (ret > (-(INTMAX_MIN+1))+UINTMAX_C(1)) return INTMAX_MIN; else return -ret; } else { uintmax_t ret = ptrdiff_bounded(q, p, ptrdiff_maxbit(q, p)); if (ret > INTMAX_MAX) return INTMAX_MAX; else return ret; } }
最后,一个适合它与*p
类型的宏。
#define ptrdiff(P, Q) (ptrdiff_byte((P), (Q))/(intmax_t)sizeof(*Q))
我记得,在过去,一些16位80×86编译器有“大”或“巨大”数据模型,其中指针有32位,但整数仍然只有16位。 这些编译器允许您创建大于65536字节的数组,但是,只有16位整数,访问不在第一个64K所需指针操作中的元素(这是非常奇怪的,一个由16位段组成的指针值和16位偏移值,实际地址为((段<< 4)+偏移))
我不知道这些编译器的兼容性如何,但他们必须将SIZE_MAX定义为类似1M的东西(因为这是你可以在奇怪的指针模型下解决的最大对象),但是ptrdiff_t将是一个16位整数(由于范围仅为-32768到+32767,因此不符合要求。
因此,在理智的硬件上实现理智的C实现没有任何理由让PTRDIFF_MAX小于SIZE_MAX。 但是可能存在奇特的硬件(在80×86的情况下,当时并不是异国情调),它允许您定义大型数组,但不允许您“同时”访问所有这些硬件。 在这种情况下,PTRDIFF_MAX可能低于SIZE_MAX / 2。