less than comparison for void pointers

Question

I want to compare two void pointers like this:

void foo(void* p1, void* p2) {

  if (p1 < p2) {
    void *tmp = p1;
    p1 = p2;
    p2 = tmp;
  }

  // do something with p1 and p2.
}

Is this correct according to the standard? I mean is the comparison of void pointers a well-defined behaviour?

I'd appreciate if someone can point me to the C standard where this is documented.

Answer 1

As Drew McGowen pointed out in a comment, but I'll post the quote here:

6.5.8 Relational operators

5 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 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.

That's from the C11 standard. C99 is the same.

From C++11, it's more or less the same. Some tweaks about pointer conversions, I can paste it all if you want. More importantly, the behaviour is Unspecified (as Chris pointed out above).

Note that Undefined Behaviour is lethal. If you compare two unrelated pointers, your machine may catch fire, launch nuclear missiles, make demons fly out of your nose, etc.

Unspecified Behaviour has to do something vaguely reasonable. The compiler doesn't have to document it, or even do the same thing for two different programs, but it can't blow up the world. Your program is still considered valid.

So in your particular case, compiling as C, the user could cause Undefined Behaviour depending on what they pass to the function. This seems pretty dangerous.

Also, contrary to my comment on the question, you cannot just use != on two arbitrary void*s: C11

6.5.9 Equality operators

2 One of the following shall hold:

— both operands have arithmetic type;

— both operands are pointers to qualified or unqualified versions of compatible types;

— one operand is a pointer to an object type and the other is a pointer to a qualified or unqualified version of void; or

— one operand is a pointer and the other is a null pointer constant.

Answer 2

Comparing two pointers is only guaranteed to be sane if they point to parts of the same "object" (struct, union or array) (or one past the end for arrays).

In practice, this is because of the existence of segmented memory model computers, where comparing only the segment offset is much faster than comparing both the segment offset and the segment id. If said segments overlap, two pointers with identical segment offsets could compare equal even though they point to different areas of memory.

Such systems are less common now than they were 20 years ago.

By @drawmcgowen, this is in C11 6.5.8.

While the results of comparing pointers to unrelated objects (not in the same struct, union or array) is undefined, I am unaware of a platform where the undefined behavior is more than "does not compare in the order you think it should".

If you really need this, and are willing to restrict which platforms your code is portable to, you can possibly get reasonable guarantees. However be advised that since this is undefined behavior, any future version of your compiler could possibly make this code not function correctly.

What is worse, is that some compilers exploit undefined behavior for optimization opportunities. For example, suppose you have a buffer, and one pointer at the start of the buffer.

If you compare another pointer to it, either (A) it is inside the buffer, so is >= than it, or (B) it isn't inside the buffer, so the result is undefined.

A simple optimization if you can prove a vector is at the front or one-past-the-end of a buffer is to drop the comparison (if >= for front, or <= for back) and replace it with a constant.

Your compiler could figure this out at any point in the optimization of your code, with any point release.

It could even say "this is a pointer to a heap allocated object", and prove that every pointer is either equal to the pointer, or unrelated -- thus < and > are always undefined behavior, and branches that do this can be completely eliminated from your code.

Relying on undefined behavior means you now have to audit the machine code generated by your code now, and in every compile in the future.

---

Originally this question was tagged with c++. In C++, std::less<void*>()( lhs, rhs ) is guaranteed to well order all pointers. (this was added to allow pointers to be sorted in various std containers and algorithms) This may be of use if you are working in a mixed C/C++ system.

20.14.6 [comparisons]/2

For templates less,[...], the specializations for any pointer type yield a strict total order that is consistent among those specializations and is also consistent with the partial order imposed by the built-in operators < [...] For template specializations less [...] if the call operator calls a built-in operator comparing pointers, the call operator yields a strict total order that is consistent among those specializations and is also consistent with the partial order imposed by those built-in operators.