5

In c99, my understanding is that comparing two pointers which do not point within the same aggregate results in undefined behavior. Given an aggregate A, a pointer p_good which is known to point within A, and a pointer p_unknown which may or may not point within A, is it possible to construct a portable test with defined behavior which determines whether it is safe to compare p_good and p_unknown?

Obviously, this test cannot itself fall afoul of the restrictions on comparing pointers.

I suspect that the answer is 'no', but I'd be happy to be shown otherwise.

acm
  • 12,183
  • 5
  • 39
  • 68
  • 1
    What do you mean by 'aggregate'? And what are you exactly trying to achieve? – Michał Górny Aug 28 '12 at 18:30
  • Do you have a pointer to `A`? Or just two pointers that point into `A`? – James McNellis Aug 28 '12 at 18:33
  • I think "no", but still, something like "x >= y && x < y + 10" in practice works to determine if x points into a given array or not. – Ambroz Bizjak Aug 28 '12 at 18:35
  • There's nothing UB about comparing unrelated pointers for equality. – eq- Aug 28 '12 at 18:35
  • 3
    @eq there is no UB in comparing pointers from distinct arrays for *equality*, but it is UB to compare pointers from distinct arrays for inequality, i.e. <, <=, >, >=. – Ambroz Bizjak Aug 28 '12 at 18:36
  • @JamesMcNellis For the first question, yes, or or even A's definition. For the second question, I have one 'known good' pointer, and one 'questionable' pointer. – acm Aug 28 '12 at 18:37
  • @AmbrozBizjak, inequality comparison is `!=`; you listed relational comparisons. – eq- Aug 28 '12 at 18:42
  • @AmbrozBizjak right. Another way to frame the question would be like this: Given the definition of an aggregate 'A' and a pointer p, is it possible to answer the question 'does p point within A' without violating the rules on comparing pointers to different aggregates. – acm Aug 28 '12 at 18:43
  • 2
    If you have an array and a candidate pointer, you can compare (==) this pointer to each possible element pointer, and see if it is equal to any of them. So, technically, the answer is yes :) – Ambroz Bizjak Aug 28 '12 at 18:47
  • So it looks as if the answer, relying on the fact that equality testing is allowed, is that it is possible to make this determination, but not in constant time. That may be ok; I only need to be able to do this one time, at startup. @AmbrozBizjak, it looks like eq beat you to the punch to make it an answer I can accept. – acm Aug 28 '12 at 19:12
  • 2
    This question is related: http://stackoverflow.com/questions/4023320/how-to-implement-memmove-in-standard-c-without-an-intermediate-copy – Pascal Cuoq Aug 28 '12 at 19:55

1 Answers1

5

You commented:

Another way to frame the question would be like this: Given the definition of an aggregate 'A' and a pointer p, is it possible to answer the question 'does p point within A' without violating the rule on inequality testing of pointers to different aggregates

The only way I can interpret this meaningfully is that you either have an object of type Aggregate type or a pointer to one. Then the answer is simple:

Pseudo-code:

bool p_in_A = false;
for (each element in Aggregate A)
    if (&element == p)
        p_in_A = true;

There is no way to tell whether a stray pointer belongs to an unknown aggregate object (or points to "between" elements in an aggregate).

eq-
  • 9,986
  • 36
  • 38
  • Yes, this makes sense. I agree there is no way to do it in the case of an unknown aggregate, but in my case I do know enough about A to use the iterated equality check. Interesting that avoiding the UB requires a O(sizeof(A)) algorithm. – acm Aug 28 '12 at 19:16
  • 1
    @acm, for an agreagate of unknown type where you only know the base pointer and the size you would have to do all this on a byte base by casting your pointers to `unsigned char*`. – Jens Gustedt Aug 28 '12 at 19:18
  • @JensGustedt In the motivating case, I do know A's type, and it happens to be char[], so it will work without casting. – acm Aug 28 '12 at 19:19
  • @JensGustedt, yes. The most important part is a way of calculating the base address of the aggregate (in addition to it's size) – eq- Aug 28 '12 at 19:19