Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Yet another binary search tree library

Reply
Thread Tools

Yet another binary search tree library

 
 
Francis Moreau
Guest
Posts: n/a
 
      07-20-2010
Tim Rentsch <(E-Mail Removed)> writes:

> Francis Moreau <(E-Mail Removed)> writes:


[...]

>>
>> No, the item of 6.5p7 which I pointed out doesn't deal about:
>>
>> struct object {
>> int a;
>> };
>>
>> [...]
>>
>> struct object an_object;
>> int *p = &an_object.a;
>>
>> As you said, this is clearly defined, since we're accessing the
>> (member) object "an_object.a" with a pointer whose type is compatible.

>
> Right, but this case isn't what I was asking about.


But this is the case for all examples you gave below, I think.

>
>> However doing this:
>>
>> struct object *obj;
>> int a = 5;
>> obj = (struct object *)&a;
>>
>> is defined by the C standard AFAIK (by what you call 'effective type
>> rules' I believe, but 'strict aliasing rules' defined by GCC breaks
>> this rules. [snip]

>
> For starters this is (usually) undefined behavior anyway, because
> of pointer alignments and size mismatches if nothing else.
>
> However, suppose we have this:
>
> int *p;
> struct { int a; int b; } *x, *y;
> x = malloc( sizeof *x );
> y = malloc( sizeof *y );
> /* presume the mallocs succeed */
>
> y->a = y->b = 0;
> *x = *y;
> p = &x->a;


So 'p' is an alias to the object 'x->a'. They both have the same type.

>
>
> *p = 5;
> *x = *y;
> /* under strict aliasing must '*p == 0' still be true? */
>
> *x = *y;
> *p = 7;
> *y = *x;
> /* under strict aliasing must 'y->a == 7' still be true? */
>
> y->a = y->b = 0;
> *x = *y;
> *p = 9;
> x = (void*) p;
> *x = *y;
> /* under strict aliasing must '*p == 0' still be true? */
>
> Do you believe, even under gcc strict aliasing, that any of the
> comment questions can have an answer other than "Yes"?. If so,
> what leads you to that conclusion?


I don't think that GCC strict aliasing rule deals about these cases.
All
of these 3 cases are about a (member) object (whose type is 'int')
that
can be accessed by a pointer with the _same_ type.

However GCC strict aliasing rule deals about the case where an object
is
accessed by another one which has a _different_ type. For example:

int i;
struct A { int a; } *x;

x = (struct A *)&i;
x->a = 0;

where we're accessing an object (type of 'int') through a pointer to a
structure. So we're accessing an object through a pointer which has a
_different_ (not even /almost/ the same) type. Note that this example
is
perfectly legal C AFAIK.

GCC strict aliasing rule claims that can't happen, for the sake of
optimizations despite the C standard.

Of course, all of these is from my best understanding. I found, as you
said previously, the GCC man page quite badly written regarding the
strict aliasing stuff.
 
Reply With Quote
 
 
 
 
Seebs
Guest
Posts: n/a
 
      07-20-2010
On 2010-07-19, Ersek, Laszlo <(E-Mail Removed)> wrote:
> On Sat, 17 Jul 2010, Tim Rentsch wrote:


>> I find it useful to read the Standard in two distinct modes. One, what I
>> might call the "comp.std.c mode", is a more literal and less assuming
>> reading (or interpretation, some might say). The other, what I might
>> call the "comp.lang.c mode", is less literal and allows more reading
>> between the lines, in an effort to discover what the committee expects
>> for how the words will be read. Mostly these two modes produce the same
>> conclusions, but there are some obvious counterexamples [...]


> It's great to see these "modes" "formalized"; being aware of them will
> help me read the Standard.


It's a useful tool, and there's a lot of very similar mode-changes going on
in conversations. I spend most of my time talking about C in terms of a
pure abstract machine, but if I need to write target-specific code, I
switch to talking about what actually happens on that implementation or
family of implementations, which may be quite a bit different.

The big problem is that people tend to unconsciously translate statements
from another mode into the mode they're in. The most obvious example is a
bit off-topic, but it's a very informative one. There are several
fundamentally different approaches to describing ethics, and among the most
obvious are:
1. Deontological ("duty-based") ethics; actions are defined to be
right and wrong in and of themselves, and you accept whatever
outcomes result from behaving in right manners.
2. Teleological ("outcome-based") ethics; actions are defined to be
right or wrong in terms of the desireability of their outcomes, and
you accept whatever actions result in the best outcomes.

Both of these systems are in moderately widespread use, and they tend to
come up with similar answers upwards of 90% of the time. However, when you
present people with a carefully-crafted "moral dilemma" problem, they tend
to resolve to one of these or the other (or one of the other systems...)

If you have a debate between two people, each of whom presupposes one of
these modes of ethical debate, they usually end up massively failing to
communicate. If the outcome-based ethicist says that, in a particular
situation, the best available course of action is to kill a given person
(usually Hitler), the duty-based ethicist tends to hear the claim "because
we have found this weird case, it is morally right to kill people". And
then they start arguing against the general claim that it is a moral duty
to kill, or at least, not a violation of a moral duty to do so. In general.
You get similar misunderstandings the other way.

The key is to learn to recognize when something is coming from a different
mode, and to know that the translation between modes *changes* what's been
said.

To bring this back to C examples, consider the vast gap you get in responses
to "what happens if I write ++i*++i?" in comp.lang.c. Some people are going
to attempt to describe the likely range of actual outputs from instructions
compilers might generate for the expression, other people are going to draw
the line at "it's undefined, and anything is all right".

In practice, no one probably really expects that it'll result in, say,
reloading inetd.conf -- but they may well use that kind of example as a way
to express that you really don't know, and can't know, and that attempting
to know is likely to result in you making even worse mistakes.

YMMV.

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / http://www.velocityreviews.com/forums/(E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
 
Reply With Quote
 
 
 
 
Franck Bui-Huu
Guest
Posts: n/a
 
      07-22-2010
Tim Rentsch <(E-Mail Removed)> writes:

> Franck Bui-Huu <(E-Mail Removed)> writes:


[...]

>> So to sum up, I think:
>>
>> struct my_struct obj;
>> char *p = (char *)&obj;
>> p += offsetof(struct my_struct, my_node);
>> p -= offsetof(struct my_struct, my_node);
>> ((struct my_struct *)p)->a;
>>
>> is a defined case of type punning.

>
> Actually there isn't any type punning going on here, since the
> types used to reference objects are the same in each case that
> the respective object actually holds. (And ignoring that member
> 'a' hasn't been initialized, which is orthogonal to the question
> of type punning.) Type punning refers to the case when a region
> of memory has been stored (or perhaps declared) using one type,
> then accessed using another. That hasn't happened here. The
> pointer conversions are legal and portable, but the converted
> pointers are accessing objects whose types match those of the
> access in each case -- ergo, no type punning.


Correct.

Since no reinterpretation of the value happened, there's actually no
type punning involved.

--
Franck
 
Reply With Quote
 
Franck Bui-Huu
Guest
Posts: n/a
 
      07-22-2010
"Ersek, Laszlo" <(E-Mail Removed)> writes:

[snip]

> I probably misused the term "type punning" (see above what I meant --
> nothing more than manipulating a pointer-to-char and then casting it
> to a pointer-to-struct).
>
> My real problem was, again, that the compiler sees two pointers to
> different types, and the areas occupied by the pointed-to objects
> overlap. I was worried whether this breaks "strict aliasing rules".
>
> Of course, it doesn't; the outer structure declaration ("struct
> object_type") is visible, so if the compiler sees a (struct
> object_type *) and a (struct node_type *), it cannot assume the latter
> doesn't point into the target of the former -- unless "restrict" is in
> effect.


From the point of view of the library API, (struct node_type *)
shouldn't be dereferenced from the user code.

--
Franck
 
Reply With Quote
 
Francis Moreau
Guest
Posts: n/a
 
      07-22-2010
Tim Rentsch <(E-Mail Removed)> writes:

> Francis Moreau <(E-Mail Removed)> writes:
>
>> Tim Rentsch <(E-Mail Removed)> writes:
>>
>>> Francis Moreau <(E-Mail Removed)> writes:

>>
>> [...]
>>
>>>>
>>>> No, the item of 6.5p7 which I pointed out doesn't deal about:
>>>>
>>>> struct object {
>>>> int a;
>>>> };
>>>>
>>>> [...]
>>>>
>>>> struct object an_object;
>>>> int *p = &an_object.a;
>>>>
>>>> As you said, this is clearly defined, since we're accessing the
>>>> (member) object "an_object.a" with a pointer whose type is compatible.
>>>
>>> Right, but this case isn't what I was asking about.

>>
>> But this is the case for all examples you gave below, I think.

>
> It isn't. The cases below access the same memory using two
> distinct types, one type 'int' and the other type a structure
> type.
>
>
>>>> However doing this:
>>>>
>>>> struct object *obj;
>>>> int a = 5;
>>>> obj = (struct object *)&a;
>>>>
>>>> is defined by the C standard AFAIK (by what you call 'effective type
>>>> rules' I believe, but 'strict aliasing rules' defined by GCC breaks
>>>> this rules. [snip]
>>>
>>> For starters this is (usually) undefined behavior anyway, because
>>> of pointer alignments and size mismatches if nothing else.
>>>
>>> However, suppose we have this:
>>>
>>> int *p;
>>> struct { int a; int b; } *x, *y;
>>> x = malloc( sizeof *x );
>>> y = malloc( sizeof *y );
>>> /* presume the mallocs succeed */
>>>
>>> y->a = y->b = 0;
>>> *x = *y;
>>> p = &x->a;

>>
>> So 'p' is an alias to the object 'x->a'. They both have the same type.

>
> The expression 'x->a' is never used in the example code to access
> an object;


Isn't

*x = *y;

equivalent to

x->a = y->a;
x->b = y->b;

?

> it's used only to take its address to assign to 'p'. The other
> accesses to this object are done using a structure type, which is
> different from int.
>
>
>>> *p = 5;
>>> *x = *y;
>>> /* under strict aliasing must '*p == 0' still be true? */
>>>
>>> *x = *y;
>>> *p = 7;
>>> *y = *x;
>>> /* under strict aliasing must 'y->a == 7' still be true? */
>>>
>>> y->a = y->b = 0;
>>> *x = *y;
>>> *p = 9;
>>> x = (void*) p;
>>> *x = *y;
>>> /* under strict aliasing must '*p == 0' still be true? */
>>>
>>> Do you believe, even under gcc strict aliasing, that any of the
>>> comment questions can have an answer other than "Yes"?. If so,
>>> what leads you to that conclusion?

>>
>> I don't think that GCC strict aliasing rule deals about these cases.
>> All of these 3 cases are about a (member) object (whose type is 'int')
>> that can be accessed by a pointer with the _same_ type.

>
> Please look again. They are about accessing an object using two
> very different types.
>
>> However GCC strict aliasing rule deals about the case where an object
>> is accessed by another one which has a _different_ type. For example:
>>
>> int i;
>> struct A { int a; } *x;
>>
>> x = (struct A *)&i;
>> x->a = 0;
>>
>> where we're accessing an object (type of 'int') through a pointer to a
>> structure. So we're accessing an object through a pointer which has a
>> _different_ (not even /almost/ the same) type. Note that this example
>> is perfectly legal C AFAIK.

>
> I'm afraid your understanding of C is somewhat lacking.


Yes probably...

> First, the conversion of '&i' to '(struct A*)' may fail (ie, yield
> undefined behavior) because of alignment requirements.


How did you come to that conclusion ?

Could you show me the 'path' across the standard that leads you to
this conclusion ?

Just for reminder the definition of 'struct A' is:

struct A { int a; };

> Second, even if it succeeds, trying to access 'i' using 'x->a' is
> always undefined behavior, because in such cases '*x' must refer to a
> structure object, and 'i' isn't in any structure.


First, doing 'x->a' (done by my previous example) is accessing the
member object 'a', not the structure object (ie the whole collection
of the member objects of the structure).

Second, 6.5p7 which lists all possible ways to access an object value,
tells me that 'x->a' is a defined way to access _an_ 'int' object
since "typeof(x->a) == int".

So could you tell me (again) how did you come to this conclusion ?

>> GCC strict aliasing rule claims that can't happen, for the sake of
>> optimizations despite the C standard.

>
> That theory doesn't hold up since the behavior in this case is
> already undefined under the Standard.
>
>> Of course, all of these is from my best understanding. I found, as you
>> said previously, the GCC man page quite badly written regarding the
>> strict aliasing stuff.

>
> The writing in the ISO document is much better than that in
> the GCC man page. It might be better to read (or re-read)
> the C Standard more carefully, and only after that try to
> devine what is meant by the GCC man page.


Yes, also asking to the GCC's team to clarify this point might be a
good idea.
 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      07-22-2010
Francis Moreau <(E-Mail Removed)> writes:

> Tim Rentsch <(E-Mail Removed)> writes:
>
>> Francis Moreau <(E-Mail Removed)> writes:
>>
>>> Tim Rentsch <(E-Mail Removed)> writes:
>>>
>>>> Francis Moreau <(E-Mail Removed)> writes:
>>>
>>> [...]
>>>
>>>>>
>>>>> No, the item of 6.5p7 which I pointed out doesn't deal about:
>>>>>
>>>>> struct object {
>>>>> int a;
>>>>> };
>>>>>
>>>>> [...]
>>>>>
>>>>> struct object an_object;
>>>>> int *p = &an_object.a;
>>>>>
>>>>> As you said, this is clearly defined, since we're accessing the
>>>>> (member) object "an_object.a" with a pointer whose type is compatible.
>>>>
>>>> Right, but this case isn't what I was asking about.
>>>
>>> But this is the case for all examples you gave below, I think.

>>
>> It isn't. The cases below access the same memory using two
>> distinct types, one type 'int' and the other type a structure
>> type.
>>
>>
>>>>> However doing this:
>>>>>
>>>>> struct object *obj;
>>>>> int a = 5;
>>>>> obj = (struct object *)&a;
>>>>>
>>>>> is defined by the C standard AFAIK (by what you call 'effective type
>>>>> rules' I believe, but 'strict aliasing rules' defined by GCC breaks
>>>>> this rules. [snip]
>>>>
>>>> For starters this is (usually) undefined behavior anyway, because
>>>> of pointer alignments and size mismatches if nothing else.
>>>>
>>>> However, suppose we have this:
>>>>
>>>> int *p;
>>>> struct { int a; int b; } *x, *y;
>>>> x = malloc( sizeof *x );
>>>> y = malloc( sizeof *y );
>>>> /* presume the mallocs succeed */
>>>>
>>>> y->a = y->b = 0;
>>>> *x = *y;
>>>> p = &x->a;
>>>
>>> So 'p' is an alias to the object 'x->a'. They both have the same type.

>>
>> The expression 'x->a' is never used in the example code to access
>> an object;

>
> Isn't
>
> *x = *y;
>
> equivalent to
>
> x->a = y->a;
> x->b = y->b;
>
> ?


No. Similar, yes, but not equivalent.


>> it's used only to take its address to assign to 'p'. The other
>> accesses to this object are done using a structure type, which is
>> different from int.
>>
>>
>>>> *p = 5;
>>>> *x = *y;
>>>> /* under strict aliasing must '*p == 0' still be true? */
>>>>
>>>> *x = *y;
>>>> *p = 7;
>>>> *y = *x;
>>>> /* under strict aliasing must 'y->a == 7' still be true? */
>>>>
>>>> y->a = y->b = 0;
>>>> *x = *y;
>>>> *p = 9;
>>>> x = (void*) p;
>>>> *x = *y;
>>>> /* under strict aliasing must '*p == 0' still be true? */
>>>>
>>>> Do you believe, even under gcc strict aliasing, that any of the
>>>> comment questions can have an answer other than "Yes"?. If so,
>>>> what leads you to that conclusion?
>>>
>>> I don't think that GCC strict aliasing rule deals about these cases.
>>> All of these 3 cases are about a (member) object (whose type is 'int')
>>> that can be accessed by a pointer with the _same_ type.

>>
>> Please look again. They are about accessing an object using two
>> very different types.
>>
>>> However GCC strict aliasing rule deals about the case where an object
>>> is accessed by another one which has a _different_ type. For example:
>>>
>>> int i;
>>> struct A { int a; } *x;
>>>
>>> x = (struct A *)&i;
>>> x->a = 0;
>>>
>>> where we're accessing an object (type of 'int') through a pointer to a
>>> structure. So we're accessing an object through a pointer which has a
>>> _different_ (not even /almost/ the same) type. Note that this example
>>> is perfectly legal C AFAIK.

>>
>> I'm afraid your understanding of C is somewhat lacking.

>
> Yes probably...
>
>> First, the conversion of '&i' to '(struct A*)' may fail (ie, yield
>> undefined behavior) because of alignment requirements.

>
> How did you come to that conclusion ?
>
> Could you show me the 'path' across the standard that leads you to
> this conclusion ?
>
> Just for reminder the definition of 'struct A' is:
>
> struct A { int a; };


Suppose that 'sizeof(int) == 4'. The alignment of int's in
such an implementation is 1, 2, or 4. The structure, on
the other hand, can have an alignment that is any multiple
of the alignment of int's; so for example, if the alignment
of 'int' is 2, the alignment of the structure could be 14.
(Obviously 14 isn't very likely, but 8 would serve the
example just as well.) So if the address of 'i' not
suitably aligned for the 'struct A' type, converting the
pointer is undefined behavior. 6.3.2.3 p7.


>> Second, even if it succeeds, trying to access 'i' using 'x->a' is
>> always undefined behavior, because in such cases '*x' must refer to a
>> structure object, and 'i' isn't in any structure.

>
> First, doing 'x->a' (done by my previous example) is accessing the
> member object 'a', not the structure object (ie the whole collection
> of the member objects of the structure).


The description of the '->' operator says it designates a member of
a structure or union _object_ (my emphasis). Since in this example
there is no structure or union object, and there is no description
of what happens when there isn't such an object, the behavior is
undefined.

> Second, 6.5p7 which lists all possible ways to access an object value,
> tells me that 'x->a' is a defined way to access _an_ 'int' object
> since "typeof(x->a) == int".


No it doesn't say that. What it /does/ say is that if you do _not_
access an int object using one of a specified set of types, then the
behavior is undefined. It does /not/ say that any access using an
int type is defined and/or legal, and indeed there are many that
aren't.

> So could you tell me (again) how did you come to this conclusion ?


Did you even bother reading the description of the '->' operator?
There's nothing mysterious about the reasoning.


>>> GCC strict aliasing rule claims that can't happen, for the sake of
>>> optimizations despite the C standard.

>>
>> That theory doesn't hold up since the behavior in this case is
>> already undefined under the Standard.
>>
>>> Of course, all of these is from my best understanding. I found, as you
>>> said previously, the GCC man page quite badly written regarding the
>>> strict aliasing stuff.

>>
>> The writing in the ISO document is much better than that in
>> the GCC man page. It might be better to read (or re-read)
>> the C Standard more carefully, and only after that try to
>> devine what is meant by the GCC man page.

>
> Yes, also asking to the GCC's team to clarify this point might be a
> good idea.


Maybe so. Please let the group know how they respond.
 
Reply With Quote
 
Francis Moreau
Guest
Posts: n/a
 
      07-26-2010
On Jul 23, 1:06*am, Tim Rentsch <(E-Mail Removed)> wrote:
> Francis Moreau <(E-Mail Removed)> writes:
> > Tim Rentsch <(E-Mail Removed)> writes:

>
> >> Francis Moreau <(E-Mail Removed)> writes:

>
> >>> Tim Rentsch <(E-Mail Removed)> writes:

>
> >>>> Francis Moreau <(E-Mail Removed)> writes:

>
> >>> [...]

>
> >>>>> No, the item of 6.5p7 which I pointed out doesn't deal about:

>
> >>>>> * * struct object {
> >>>>> * * * * int a;
> >>>>> * * };

>
> >>>>> * * [...]

>
> >>>>> * * struct object an_object;
> >>>>> * * int *p = &an_object.a;

>
> >>>>> As you said, this is clearly defined, since we're accessing the
> >>>>> (member) object "an_object.a" with a pointer whose type is compatible.

>
> >>>> Right, but this case isn't what I was asking about.

>
> >>> But this is the case for all examples you gave below, I think.

>
> >> It isn't. *The cases below access the same memory using two
> >> distinct types, one type 'int' and the other type a structure
> >> type.

>
> >>>>> However doing this:

>
> >>>>> * * struct object *obj;
> >>>>> * * int a = 5;
> >>>>> * * obj = (struct object *)&a;

>
> >>>>> is defined by the C standard AFAIK (by what you call 'effective type
> >>>>> rules' I believe, but 'strict aliasing rules' defined by GCC breaks
> >>>>> this rules. *[snip]

>
> >>>> For starters this is (usually) undefined behavior anyway, because
> >>>> of pointer alignments and size mismatches if nothing else.

>
> >>>> However, suppose we have this:

>
> >>>> * * int *p;
> >>>> * * struct { int a; int b; } *x, *y;
> >>>> * * x = malloc( sizeof *x );
> >>>> * * y = malloc( sizeof *y );
> >>>> * * /* presume the mallocs succeed */

>
> >>>> * * y->a = y->b = 0;
> >>>> * * *x = *y;
> >>>> * * p = &x->a;

>
> >>> So 'p' is an alias to the object 'x->a'. They both have the same type..

>
> >> The expression 'x->a' is never used in the example code to access
> >> an object;

>
> > Isn't

>
> > * *x = *y;

>
> > equivalent to

>
> > * x->a = y->a;
> > * x->b = y->b;

>
> > ?

>
> No. *Similar, yes, but not equivalent.
>
>
>
>
>
> >> it's used only to take its address to assign to 'p'. *The other
> >> accesses to this object are done using a structure type, which is
> >> different from int.

>
> >>>> * * *p = 5;
> >>>> * * *x = *y;
> >>>> * * /* under strict aliasing must '*p == 0' still be true? */

>
> >>>> * * *x = *y;
> >>>> * * *p = 7;
> >>>> * * *y = *x;
> >>>> * * /* under strict aliasing must 'y->a == 7' still be true? */

>
> >>>> * * y->a = y->b = 0;
> >>>> * * *x = *y;
> >>>> * * *p = 9;
> >>>> * * x = (void*) p;
> >>>> * * *x = *y;
> >>>> * * /* under strict aliasing must '*p == 0' still be true? */

>
> >>>> Do you believe, even under gcc strict aliasing, that any of the
> >>>> comment questions can have an answer other than "Yes"?. *If so,
> >>>> what leads you to that conclusion?

>
> >>> I don't think that GCC strict aliasing rule deals about these cases.
> >>> All of these 3 cases are about a (member) object (whose type is 'int')
> >>> that can be accessed by a pointer with the _same_ type.

>
> >> Please look again. *They are about accessing an object using two
> >> very different types.

>
> >>> However GCC strict aliasing rule deals about the case where an object
> >>> is accessed by another one which has a _different_ type. For example:

>
> >>> * int i;
> >>> * struct A { int a; } *x;

>
> >>> * x = (struct A *)&i;
> >>> * x->a = 0;

>
> >>> where we're accessing an object (type of 'int') through a pointer to a
> >>> structure. So we're accessing an object through a pointer which has a
> >>> _different_ (not even /almost/ the same) type. Note that this example
> >>> is perfectly legal C AFAIK.

>
> >> I'm afraid your understanding of C is somewhat lacking.

>
> > Yes probably...

>
> >> First, the conversion of '&i' to '(struct A*)' may fail (ie, yield
> >> undefined behavior) because of alignment requirements.

>
> > How did you come to that conclusion ?

>
> > Could you show me the 'path' across the standard that leads you to
> > this conclusion ?

>
> > Just for reminder the definition of 'struct A' is:

>
> > * *struct A { int a; };

>
> Suppose that 'sizeof(int) == 4'. *The alignment of int's in
> such an implementation is 1, 2, or 4. *The structure, on
> the other hand, can have an alignment that is any multiple
> of the alignment of int's; *so for example, if the alignment
> of 'int' is 2, the alignment of the structure could be 14.


Ok, so all of this is up to the implementation.

Let assume that 'struct A' and 'int' types have the same alignment.

>
> >> Second, even if it succeeds, trying to access 'i' using 'x->a' is
> >> always undefined behavior, because in such cases '*x' must refer to a
> >> structure object, and 'i' isn't in any structure.

>
> > First, doing 'x->a' (done by my previous example) is accessing the
> > member object 'a', not the structure object (ie the whole collection
> > of the member objects of the structure).

>
> The description of the '->' operator says it designates a member of
> a structure or union _object_ (my emphasis). *Since in this example
> there is no structure or union object, and there is no description
> of what happens when there isn't such an object, the behavior is
> undefined.


please see below...

>
> > Second, 6.5p7 which lists all possible ways to access an object value,
> > tells me that 'x->a' is a defined way to access _an_ 'int' object
> > since "typeof(x->a) == int".

>
> No it doesn't say that. *What it /does/ say is that if you do _not_
> access an int object using one of a specified set of types, then the
> behavior is undefined.


and what the specified set of types ?

Answer:

[...]
an aggregate or union type that includes one of the aforementioned
types among its members (including, recursively, a member of a
subaggregate or contained union)

Note that this is one defined way to access _an_ object. This doesn't
say a word about the fact that for this case it must be a _member_
object.


> > So could you tell me (again) how did you come to this conclusion ?

>
> Did you even bother reading the description of the '->' operator?
> There's nothing mysterious about the reasoning.


Please stop asking me to read the standard.

As you probably know, this document is far from trivial to understand.

And if you're skilled enough to understand such paper just after one
reading, then you had probably noticed that comp.lang.c is full of
questions asking to clarify the spec.


 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      07-26-2010
Francis Moreau <(E-Mail Removed)> writes:

> On Jul 23, 1:06 am, Tim Rentsch <(E-Mail Removed)> wrote:
>> Francis Moreau <(E-Mail Removed)> writes:
>> > Tim Rentsch <(E-Mail Removed)> writes:

>>
>> >> Francis Moreau <(E-Mail Removed)> writes:

>>
>> >>> Tim Rentsch <(E-Mail Removed)> writes:

>>
>> >>>> Francis Moreau <(E-Mail Removed)> writes:

>>
>> >>> [...]

>>
>> >>>>> No, the item of 6.5p7 which I pointed out doesn't deal about:

>>
>> >>>>> struct object {
>> >>>>> int a;
>> >>>>> };

>>
>> >>>>> [...]

>>
>> >>>>> struct object an_object;
>> >>>>> int *p = &an_object.a;

>>
>> >>>>> As you said, this is clearly defined, since we're accessing the
>> >>>>> (member) object "an_object.a" with a pointer whose type is compatible.

>>
>> >>>> Right, but this case isn't what I was asking about.

>>
>> >>> But this is the case for all examples you gave below, I think.

>>
>> >> It isn't. The cases below access the same memory using two
>> >> distinct types, one type 'int' and the other type a structure
>> >> type.

>>
>> >>>>> However doing this:

>>
>> >>>>> struct object *obj;
>> >>>>> int a = 5;
>> >>>>> obj = (struct object *)&a;

>>
>> >>>>> is defined by the C standard AFAIK (by what you call 'effective type
>> >>>>> rules' I believe, but 'strict aliasing rules' defined by GCC breaks
>> >>>>> this rules. [snip]

>>
>> >>>> For starters this is (usually) undefined behavior anyway, because
>> >>>> of pointer alignments and size mismatches if nothing else.

>>
>> >>>> However, suppose we have this:

>>
>> >>>> int *p;
>> >>>> struct { int a; int b; } *x, *y;
>> >>>> x = malloc( sizeof *x );
>> >>>> y = malloc( sizeof *y );
>> >>>> /* presume the mallocs succeed */

>>
>> >>>> y->a = y->b = 0;
>> >>>> *x = *y;
>> >>>> p = &x->a;

>>
>> >>> So 'p' is an alias to the object 'x->a'. They both have the same type.

>>
>> >> The expression 'x->a' is never used in the example code to access
>> >> an object;

>>
>> > Isn't

>>
>> > *x = *y;

>>
>> > equivalent to

>>
>> > x->a = y->a;
>> > x->b = y->b;

>>
>> > ?

>>
>> No. Similar, yes, but not equivalent.
>>
>>
>>
>>
>>
>> >> it's used only to take its address to assign to 'p'. The other
>> >> accesses to this object are done using a structure type, which is
>> >> different from int.

>>
>> >>>> *p = 5;
>> >>>> *x = *y;
>> >>>> /* under strict aliasing must '*p == 0' still be true? */

>>
>> >>>> *x = *y;
>> >>>> *p = 7;
>> >>>> *y = *x;
>> >>>> /* under strict aliasing must 'y->a == 7' still be true? */

>>
>> >>>> y->a = y->b = 0;
>> >>>> *x = *y;
>> >>>> *p = 9;
>> >>>> x = (void*) p;
>> >>>> *x = *y;
>> >>>> /* under strict aliasing must '*p == 0' still be true? */

>>
>> >>>> Do you believe, even under gcc strict aliasing, that any of the
>> >>>> comment questions can have an answer other than "Yes"?. If so,
>> >>>> what leads you to that conclusion?

>>
>> >>> I don't think that GCC strict aliasing rule deals about these cases.
>> >>> All of these 3 cases are about a (member) object (whose type is 'int')
>> >>> that can be accessed by a pointer with the _same_ type.

>>
>> >> Please look again. They are about accessing an object using two
>> >> very different types.

>>
>> >>> However GCC strict aliasing rule deals about the case where an object
>> >>> is accessed by another one which has a _different_ type. For example:

>>
>> >>> int i;
>> >>> struct A { int a; } *x;

>>
>> >>> x = (struct A *)&i;
>> >>> x->a = 0;

>>
>> >>> where we're accessing an object (type of 'int') through a pointer to a
>> >>> structure. So we're accessing an object through a pointer which has a
>> >>> _different_ (not even /almost/ the same) type. Note that this example
>> >>> is perfectly legal C AFAIK.

>>
>> >> I'm afraid your understanding of C is somewhat lacking.

>>
>> > Yes probably...

>>
>> >> First, the conversion of '&i' to '(struct A*)' may fail (ie, yield
>> >> undefined behavior) because of alignment requirements.

>>
>> > How did you come to that conclusion ?

>>
>> > Could you show me the 'path' across the standard that leads you to
>> > this conclusion ?

>>
>> > Just for reminder the definition of 'struct A' is:

>>
>> > struct A { int a; };

>>
>> Suppose that 'sizeof(int) == 4'. The alignment of int's in
>> such an implementation is 1, 2, or 4. The structure, on
>> the other hand, can have an alignment that is any multiple
>> of the alignment of int's; so for example, if the alignment
>> of 'int' is 2, the alignment of the structure could be 14.

>
> Ok, so all of this is up to the implementation.
>
> Let assume that 'struct A' and 'int' types have the same alignment.
>
>>
>> >> Second, even if it succeeds, trying to access 'i' using 'x->a' is
>> >> always undefined behavior, because in such cases '*x' must refer to a
>> >> structure object, and 'i' isn't in any structure.

>>
>> > First, doing 'x->a' (done by my previous example) is accessing the
>> > member object 'a', not the structure object (ie the whole collection
>> > of the member objects of the structure).

>>
>> The description of the '->' operator says it designates a member of
>> a structure or union _object_ (my emphasis). Since in this example
>> there is no structure or union object, and there is no description
>> of what happens when there isn't such an object, the behavior is
>> undefined.

>
> please see below...
>
>>
>> > Second, 6.5p7 which lists all possible ways to access an object value,
>> > tells me that 'x->a' is a defined way to access _an_ 'int' object
>> > since "typeof(x->a) == int".

>>
>> No it doesn't say that. What it /does/ say is that if you do _not_
>> access an int object using one of a specified set of types, then the
>> behavior is undefined.

>
> and what the specified set of types ?
>
> Answer:
>
> [...]
> an aggregate or union type that includes one of the aforementioned
> types among its members (including, recursively, a member of a
> subaggregate or contained union)
>
> Note that this is one defined way to access _an_ object. This doesn't
> say a word about the fact that for this case it must be a _member_
> object.


Did you understand the main point I was making? That 6.5p7
doesn't ever guarantee legality, but only excludes cases besides
the ones it lists? 6.5p7 is a /necessary/ condition for an
access to be defined behavior, but it is not a /sufficient/
condition. That's why reading other sections of the Standard
is needed here.


>> > So could you tell me (again) how did you come to this conclusion ?

>>
>> Did you even bother reading the description of the '->' operator?
>> There's nothing mysterious about the reasoning.

>
> Please stop asking me to read the standard.
>
> As you probably know, this document is far from trivial to understand.
>
> And if you're skilled enough to understand such paper just after one
> reading, then you had probably noticed that comp.lang.c is full of
> questions asking to clarify the spec.


I apologize for the tone of my earlier comment. It was
unnecessarily harsh.

However, if someone is making assertions about what the Standard
requires or allows, I don't think it's unreasonable to expect
that they should and will read the Standard to try to understand
what it says. I don't mind answering questions when the
reasoning necessary is convoluted or otherwise hard to find. In
this particular case I thought the reasoning involved would be
obvious to someone who had read the description of the operators
used. I explained that reasoning in the previous posting, and
also explained why 6.5p7 doesn't affect the outcome; 6.5p7
can only make otherwise defined behavior be allowed, it cannot
make undefined behavior be defined. So the semantic provisions
of the '->' operator, having failed to be met, mean this case
is undefined behavior.
 
Reply With Quote
 
Francis Moreau
Guest
Posts: n/a
 
      07-27-2010
On 26 juil, 17:09, Tim Rentsch <(E-Mail Removed)> wrote:
> Francis Moreau <(E-Mail Removed)> writes:
> > On Jul 23, 1:06 am, Tim Rentsch <(E-Mail Removed)> wrote:
> >> Francis Moreau <(E-Mail Removed)> writes:
> >> > Tim Rentsch <(E-Mail Removed)> writes:

>
> >> >> Francis Moreau <(E-Mail Removed)> writes:

>
> >> >>> Tim Rentsch <(E-Mail Removed)> writes:

>
> >> >>>> Francis Moreau <(E-Mail Removed)> writes:

>
> >> >>> [...]

>
> >> >>>>> No, the item of 6.5p7 which I pointed out doesn't deal about:

>
> >> >>>>> * * struct object {
> >> >>>>> * * * * int a;
> >> >>>>> * * };

>
> >> >>>>> * * [...]

>
> >> >>>>> * * struct object an_object;
> >> >>>>> * * int *p = &an_object.a;

>
> >> >>>>> As you said, this is clearly defined, since we're accessing the
> >> >>>>> (member) object "an_object.a" with a pointer whose type is compatible.

>
> >> >>>> Right, but this case isn't what I was asking about.

>
> >> >>> But this is the case for all examples you gave below, I think.

>
> >> >> It isn't. *The cases below access the same memory using two
> >> >> distinct types, one type 'int' and the other type a structure
> >> >> type.

>
> >> >>>>> However doing this:

>
> >> >>>>> * * struct object *obj;
> >> >>>>> * * int a = 5;
> >> >>>>> * * obj = (struct object *)&a;

>
> >> >>>>> is defined by the C standard AFAIK (by what you call 'effective type
> >> >>>>> rules' I believe, but 'strict aliasing rules' defined by GCC breaks
> >> >>>>> this rules. *[snip]

>
> >> >>>> For starters this is (usually) undefined behavior anyway, because
> >> >>>> of pointer alignments and size mismatches if nothing else.

>
> >> >>>> However, suppose we have this:

>
> >> >>>> * * int *p;
> >> >>>> * * struct { int a; int b; } *x, *y;
> >> >>>> * * x = malloc( sizeof *x );
> >> >>>> * * y = malloc( sizeof *y );
> >> >>>> * * /* presume the mallocs succeed */

>
> >> >>>> * * y->a = y->b = 0;
> >> >>>> * * *x = *y;
> >> >>>> * * p = &x->a;

>
> >> >>> So 'p' is an alias to the object 'x->a'. They both have the same type.

>
> >> >> The expression 'x->a' is never used in the example code to access
> >> >> an object;

>
> >> > Isn't

>
> >> > * *x = *y;

>
> >> > equivalent to

>
> >> > * x->a = y->a;
> >> > * x->b = y->b;

>
> >> > ?

>
> >> No. *Similar, yes, but not equivalent.

>
> >> >> it's used only to take its address to assign to 'p'. *The other
> >> >> accesses to this object are done using a structure type, which is
> >> >> different from int.

>
> >> >>>> * * *p = 5;
> >> >>>> * * *x = *y;
> >> >>>> * * /* under strict aliasing must '*p == 0' still be true? */

>
> >> >>>> * * *x = *y;
> >> >>>> * * *p = 7;
> >> >>>> * * *y = *x;
> >> >>>> * * /* under strict aliasing must 'y->a == 7' still be true? */

>
> >> >>>> * * y->a = y->b = 0;
> >> >>>> * * *x = *y;
> >> >>>> * * *p = 9;
> >> >>>> * * x = (void*) p;
> >> >>>> * * *x = *y;
> >> >>>> * * /* under strict aliasing must '*p == 0' still be true? */

>
> >> >>>> Do you believe, even under gcc strict aliasing, that any of the
> >> >>>> comment questions can have an answer other than "Yes"?. *If so,
> >> >>>> what leads you to that conclusion?

>
> >> >>> I don't think that GCC strict aliasing rule deals about these cases.
> >> >>> All of these 3 cases are about a (member) object (whose type is 'int')
> >> >>> that can be accessed by a pointer with the _same_ type.

>
> >> >> Please look again. *They are about accessing an object using two
> >> >> very different types.

>
> >> >>> However GCC strict aliasing rule deals about the case where an object
> >> >>> is accessed by another one which has a _different_ type. For example:

>
> >> >>> * int i;
> >> >>> * struct A { int a; } *x;

>
> >> >>> * x = (struct A *)&i;
> >> >>> * x->a = 0;

>
> >> >>> where we're accessing an object (type of 'int') through a pointer to a
> >> >>> structure. So we're accessing an object through a pointer which has a
> >> >>> _different_ (not even /almost/ the same) type. Note that this example
> >> >>> is perfectly legal C AFAIK.

>
> >> >> I'm afraid your understanding of C is somewhat lacking.

>
> >> > Yes probably...

>
> >> >> First, the conversion of '&i' to '(struct A*)' may fail (ie, yield
> >> >> undefined behavior) because of alignment requirements.

>
> >> > How did you come to that conclusion ?

>
> >> > Could you show me the 'path' across the standard that leads you to
> >> > this conclusion ?

>
> >> > Just for reminder the definition of 'struct A' is:

>
> >> > * *struct A { int a; };

>
> >> Suppose that 'sizeof(int) == 4'. *The alignment of int's in
> >> such an implementation is 1, 2, or 4. *The structure, on
> >> the other hand, can have an alignment that is any multiple
> >> of the alignment of int's; *so for example, if the alignment
> >> of 'int' is 2, the alignment of the structure could be 14.

>
> > Ok, so all of this is up to the implementation.

>
> > Let assume that 'struct A' and 'int' types have the same alignment.

>
> >> >> Second, even if it succeeds, trying to access 'i' using 'x->a' is
> >> >> always undefined behavior, because in such cases '*x' must refer to a
> >> >> structure object, and 'i' isn't in any structure.

>
> >> > First, doing 'x->a' (done by my previous example) is accessing the
> >> > member object 'a', not the structure object (ie the whole collection
> >> > of the member objects of the structure).

>
> >> The description of the '->' operator says it designates a member of
> >> a structure or union _object_ (my emphasis). *Since in this example
> >> there is no structure or union object, and there is no description
> >> of what happens when there isn't such an object, the behavior is
> >> undefined.

>
> > please see below...

>
> >> > Second, 6.5p7 which lists all possible ways to access an object value,
> >> > tells me that 'x->a' is a defined way to access _an_ 'int' object
> >> > since "typeof(x->a) == int".

>
> >> No it doesn't say that. *What it /does/ say is that if you do _not_
> >> access an int object using one of a specified set of types, then the
> >> behavior is undefined.

>
> > and what the specified set of types ?

>
> > Answer:

>
> > *[...]
> > *an aggregate or union type that includes one of the aforementioned
> > types among its members (including, recursively, a member of a
> > subaggregate or contained union)

>
> > Note that this is one defined way to access _an_ object. This doesn't
> > say a word about the fact that for this case it must be a _member_
> > object.

>
> Did you understand the main point I was making? *That 6.5p7
> doesn't ever guarantee legality, but only excludes cases besides
> the ones it lists? *6.5p7 is a /necessary/ condition for an
> access to be defined behavior, but it is not a /sufficient/
> condition. *That's why reading other sections of the Standard
> is needed here.
>
> >> > So could you tell me (again) how did you come to this conclusion ?

>
> >> Did you even bother reading the description of the '->' operator?
> >> There's nothing mysterious about the reasoning.

>
> > Please stop asking me to read the standard.

>
> > As you probably know, this document is far from trivial to understand.

>
> > And if you're skilled enough to understand such paper just after one
> > reading, then you had probably noticed that comp.lang.c is full of
> > questions asking to clarify the spec.

>
> I apologize for the tone of my earlier comment. *It was
> unnecessarily harsh.


no problem.

>
> However, if someone is making assertions about what the Standard
> requires or allows, I don't think it's unreasonable to expect
> that they should and will read the Standard to try to understand
> what it says. *I don't mind answering questions when the
> reasoning necessary is convoluted or otherwise hard to find.


thank you, your answers are valuable to decipher the Standard.

> In
> this particular case I thought the reasoning involved would be
> obvious to someone who had read the description of the operators
> used. *I explained that reasoning in the previous posting, and
> also explained why 6.5p7 doesn't affect the outcome; 6.5p7
> can only make otherwise defined behavior be allowed, it cannot
> make undefined behavior be defined. *So the semantic provisions
> of the '->' operator, having failed to be met, mean this case
> is undefined behavior.


Ok, I see now.

This is really sad to see that just adding a couple of word would have
clarify a lot this point. Instead I have to sail accross the whole
document to get scattered information.

How about this new example, which should make you happier regarding
the '->' operator:

struct A { int a; };
struct B { int b; };

struct A *p;
struct B b_object;

p = (struct A *)&b_object;
p->a = 1;

As you can see, there're no more alignment issues since (in my
understanding) all pointers to structure types have the same
representation and alignment requirements as each other.

And (still in my understanding), there's no more undefined behaviour
since the '->' operator requirement is satisfied now: p now points to
a structure object.

What do you think ?

 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      07-27-2010
Francis Moreau <(E-Mail Removed)> writes:

> On 26 juil, 17:09, Tim Rentsch <(E-Mail Removed)> wrote:
>[snip]
>> [snip] I don't mind answering questions when the
>> reasoning necessary is convoluted or otherwise hard to find.

>
> thank you, your answers are valuable to decipher the Standard.


Glad to hear it.

>> In
>> this particular case I thought the reasoning involved would be
>> obvious to someone who had read the description of the operators
>> used. I explained that reasoning in the previous posting, and
>> also explained why 6.5p7 doesn't affect the outcome; 6.5p7
>> can only make otherwise defined behavior be allowed, it cannot
>> make undefined behavior be defined. So the semantic provisions
>> of the '->' operator, having failed to be met, mean this case
>> is undefined behavior.

>
> Ok, I see now.
>
> This is really sad to see that just adding a couple of word would have
> clarify a lot this point. Instead I have to sail accross the whole
> document to get scattered information.


Yes, for better or worse, some choices of writing style in the
Standard sometimes make it hard to find the information one wants
to find.

> How about this new example, which should make you happier regarding
> the '->' operator:
>
> struct A { int a; };
> struct B { int b; };
>
> struct A *p;
> struct B b_object;
>
> p = (struct A *)&b_object;
> p->a = 1;
>
> As you can see, there're no more alignment issues since (in my
> understanding) all pointers to structure types have the same
> representation and alignment requirements as each other.


Pointers to structures have the same alignment requirements as
each other, but the structures themselves may have different
alignments, and it's the alignments of the structures that is
relevant here.

In principle it's possible for these two structs to have
different alignment requirements, but practically speaking it's
pretty unlikely, so for the sake of discussion let's ignore that
aspect.

> And (still in my understanding), there's no more undefined behaviour
> since the '->' operator requirement is satisfied now: p now points to
> a structure object.
>
> What do you think ?


This question is very good. It seems like a natural thing to
want to do, and finding an answer isn't especially easy or
obvious.

In fact, I believe the Standard means for this to be undefined
behavior. Unfortunately the Standard does not (IMO) address this
question as directly or as clearly as it should. The general
principle is that it's illegal to access members of one kind of
struct by means of member access (ie, using '.' or '->') using
a designator that is a different kind of struct. This principle
does have an exception, and that exception is spelled out
specifically in 6.5.2.3p5:

One special guarantee is made in order to simplify the use
of unions: if a union contains several structures that
share a common initial sequence (see below), and if the
union object currently contains one of these structures, it
is permitted to inspect the common initial part of any of
them anywhere that a declaration of the complete type of the
union is visible. Two structures share a common initial
sequence if corresponding members have compatible types
(and, for bit-fields, the same widths) for a sequence of one
or more initial members.

The argument is that, since the Standard goes to the trouble of
pointing out a case where accessing one struct through a different
type of struct is allowed, in other cases doing that is not allowed
(ie, is undefined behavior). This question may be worth debating
over in comp.std.c, because at the very least it would be nice if
the language were more clear. However, as far as a practical
reading of the Standard goes (ie, for comp.lang.c) I would say this
point settles the question. And, luckily, there is an example that
is pretty much right on point to your question, namely 6.5.2.3p8:

EXAMPLE 3 The following is a valid fragment:

union {
struct {
int alltypes;
} n;
struct {
int type;
int intnode;
} ni;
struct {
int type;
double doublenode;
} nf;
} u;
u.nf.type = 1;
u.nf.doublenode = 3.14;
/* ... */
if (u.n.alltypes == 1)
if (sin(u.nf.doublenode) == 0.0)
/* ... */

The following is not a valid fragment (because the union type is
not visible within function f):

struct t1 { int m; };
struct t2 { int m; };
int f(struct t1 *p1, struct t2 *p2)
{
if (p1->m < 0)
p2->m = -p2->m;
return p1->m;
}
int g()
{
union {
struct t1 s1;
struct t2 s2;
} u;
/* ... */
return f(&u.s1, &u.s2);
}

The second code fragment is very similar to the question you ask,
and is clearly identified as not a valid fragment. Because of
the similarity it seems safe to conclude that the example code
you gave (and other similar sorts of code) is also not valid.
Make sense?
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Binary tree search vs Binary search Bogdan C Programming 22 10-21-2010 09:46 PM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 2 10-31-2007 02:58 AM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 1 10-30-2007 11:01 PM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 4 10-30-2007 08:21 PM
B tree, B+ tree and B* tree Stub C Programming 3 11-12-2003 01:51 PM



Advertisments