6

I'm implementing iterator through continuous chunk of memory and came to the issue about its conforming usage. My current implementation (assuming I'm iterating through array of chars).

typedef struct iterator{ void *next_ptr; void *limit; //one past last element pointer } iterator_t; void *next(iterator_t *iterator_ptr){ void *limit = iterator_ptr -> limit; void *next_ptr = iterator_ptr -> next_ptr; ptrdiff_t diff = limit - next_ptr; if(diff <= 0){ return NULL; } iterator_ptr -> next_ptr = ((char *) next_ptr) + 1; return next_ptr; }

The issue is the Standard claims at 6.5.6(p9) that:

When two pointers are subtracted, both shall point to elements of the same array object,or one past the last element of the array object

This is true. I assume the area I'm iterating through is an array.

If the result is not representable in an object of that type, the behavior is undefined. In other words, if the expressions point to, respectively, the i-th and j-th elements of an array object, the expression (P)-(Q) has the value i−j provided the value fits in an object of type ptrdiff_t.

The limits of ptrdiff_t are defined at 7.20.3(p2):

limits of ptrdiff_t

PTRDIFF_MIN −65535

PTRDIFF_MAX +65535

There is no any guarantees that all values represented with size_t should be represented with ptrdiff_t.

So we judging by the limits we can conformingly subtract pointers of an array only of 65535 elements at most? So this would not work in general case where I want to subtract two pointers to elements of an array of unknown size?

Improve this question
16
  • Where exactly have you seen PTRDIFF_MIN −65535 and PTRDIFF_MAX +65535? These limits are platform dependent, but 65535 seems tiny to me. Commented Mar 26, 2019 at 15:59
  • SIZE_MAX should agree with PTRDIFF_MIN/MAX on the specific implementation to make sense. Commented Mar 26, 2019 at 16:00
  • 1
    -65535 to +65535 is the guaranteed minimum range, actual ranges are of course higher on current systems. Commented Mar 26, 2019 at 16:00
  • 1
    The only way to go I see now is to convert pointers to convert pointers to intptr_t That won't work. You have to convert to uintptr_t or the resulting difference can be incorrect. Then you run into the same problem of not having enough bits to represent the same magnitude along with a direction for the difference. Commented Mar 26, 2019 at 16:42
  • 1
    Unrelated to the main question, but isn't subtraction of two void* undefined? You can't have an array of void objects. Commented Mar 26, 2019 at 17:00

2 Answers 2

Reset to default
4

This seems to be a problem in the C standard itself.

As you noted, 6.5.6 Additive operators, paragraph 9 states, in part:

When two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object; the result is the difference of the subscripts of the two array elements. The size of the result is implementation-defined, and its type (a signed integer type) is ptrdiff_t defined in the <stddef.h> header. If the result is not representable in an object of that type, the behavior is undefined. In other words, if the expressions P and Q point to, respectively, the i-th and j-th elements of an array object, the expression (P)-(Q) has the value i-j provided the value fits in an object of type ptrdiff_t. ...

There appears to be no guarantee in the C standard that you can represent the difference of two pointers in a ptrdiff_t.

Realistically, this would mean that a ptrdiff_t has to be larger than a size_t. A size_t only has to cover magnitude in a fixed number of bits. ptrdiff_t has to cover both magnitude and direction. If sizeof( size_t ) == sizeof( ptrdiff_t ), then there's no guarantee that the undefined behavior in 6.5.6p9 won't be invoked.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Actually the UB can be easily invoked. char *p = (char *) malloc(SIZE_MAX); ptrdiff_t diff = (p + SIZE_MAX) - p; printf("ptrdiff_t = %td\n", diff); prints -1 on my machine.
Note that this is only a problem if the size of the largest object which can be created is larger than PTRDIFF_MAX-1, which is not the case on any 64-bit implementation I know of. There are implementations with 32-bit size_t and ptrdiff_t which allow single objects bigger than 2GB, and on those implementations overflow is possible (at least for char* pointer subtraction).
@rici There are implementations with 32-bit size_t and ptrdiff_t which allow single objects bigger than 2GB, and on those implementations overflow is possible (at least for char pointer subtraction).* Those are the exact types of implementations that popped into my head when I understood what the OP was asking. I'm surprised the question only has 3 upvotes.
The question comes up from time to time, which might explain that. Here's a couple of examples, maybe dupes: stackoverflow.com/q/49380475 stackoverflow.com/q/38442017
4

From the specification (section 7.20.3)

Its implementation-defined value shall be equal to or greater in magnitude (absolute value) than the corresponding value given below

[Emphasis mine]

So the values mentioned are only minimum values. The implementation could have larger limits. I would expect ptrdiff_t to be the word-length of the target platform (i.e. a 64-bit type of 64-bit systems).

And note that size_t is an unsigned integer type, while ptrdiff_t is a signed integer type. That kind of implies that not all values of a size_t could be represented by a ptrdiff_t.

Improve this answer

5 Comments

Can you please elaborate on the following example: We malloced SIZE_MAX bytes as char *bytes = malloc(SIZE_MAX). So pointer to the last element would be bytes + SIZE_MAX. Isn't ptrdiff_t diff = (bytes + SIZE_MAX) - bytes overflow guaranteely?
@SomeName On a system where SIZE_MAX > PTRDIFF_MAX then that would undoubtedly lead to an overflow.
That was the point I wanted to understand, thanks. Actually this is true for the system I currently use #define PTRDIFF_MAX 9223372036854775807L and #define SIZE_MAX 18446744073709551615UL.
It would be cool if you can give an advice of conforming usage of ptrdiff_t. #if macro would not work with malloced memory where the size to be allocated is not a constant expression...
@SomeName Don't use such large arrays? ;) For normal everyday use, these limitations would never be relevant. If the limits are getting close, then arrays are probably not the best data-structure anyway.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.