schmidt@bonnie.ics.uci.edu (Douglas C. Schmidt) (08/17/88)
Hi,
Assume the following recursive type declaration for a linked
list:
struct list {
int item;
struct list *next;
};
Is the following always guaranteed to produce the "intended"
result:
...
struct list foo()
{
struct list head;
return(head->next = head = (struct list *) malloc(sizeof(struct list)));
}
...
My intention is to create a dummy node in a circularly-linked list,
and assign the dummy node's next field to point to the head of
the list. Since assignment associates from right-to-left this
will alway work, right (cryptic style notwithstanding !! ;-)).
thanks,
Doug Schmidt
--
Douglas Schmidt
"If our behavior is strict, we do not need fun." -Zippy th' Pinhead
"If our behavior is struct, we do not need defun." -Anonchris@mimsy.UUCP (Chris Torek) (08/17/88)
In article <957@orion.cf.uci.edu> schmidt@bonnie.ics.uci.edu (Douglas C. Schmidt) writes: >Is the following always guaranteed to produce the "intended" result: > >struct list foo() >{ > struct list head; > > return(head->next = head = (struct list *) malloc(sizeof(struct list))); >} Aside from the fact that there are two `*'s missing, and that malloc can return NULL, the answer is no. >My intention is to create a dummy node in a circularly-linked list, >and assign the dummy node's next field to point to the head of >the list. Since assignment associates from right-to-left this >will alway work, right (cryptic style notwithstanding !! ;-)). Not so. If you must use cryptic style, try /* assuming emalloc() is declared, and is like malloc but never returns NULL: */ struct list *foo() { struct list *head; return (head = (struct list *)emalloc(sizeof *head), head->next = head); } -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
lmiller@venera.isi.edu (Larry Miller) (08/18/88)
In article <957@orion.cf.uci.edu> schmidt@bonnie.ics.uci.edu (Douglas C. Schmidt) writes: >Hi, > > Assume the following recursive type declaration for a linked >list: > >struct list { > int item; > struct list *next; >}; > >Is the following always guaranteed to produce the "intended" >result: > >... >struct list foo() (1) >{ (2) > struct list head; (3) > > return(head->next = head = (struct list *) malloc(sizeof(struct list))); (4) >} (5) >... > >My intention is to create a dummy node in a circularly-linked list, >and assign the dummy node's next field to point to the head of >the list. Since assignment associates from right-to-left this >will alway work, right (cryptic style notwithstanding !! ;-)). [Line numbers added]. Well, let's see, it's not clear what you want to return, an entire structure (struct list), or a pointer to one. The usual way that a routine such as this is written is to return a POINTER to one, so line (1) probably should be struct list * foo() There are several problems at line (4): You correctly cast the return from malloc, but you have a type mis- match. head is type (struct list). You've cast the return from malloc to be a (struct list *). What you wanted to do was to declare head to be a struct list * at line (3): struct list *head; Assuming this new correct definition/declaration of head, you still risk a NULL return from malloc, so the reference through head to head->next could produce an illegal pointer reference through NULL. Finally, you're returning head->next, a (struct list *), but you originally declared foo() to return a struct list. Your explanation of what you want done won't work even with the fixes described above, since when you're done what you'll get is a pointer to a (struct list), with its next field pointing back to itself: +---------+------+ | item | next +-----+ +---------+------+ | ^ | | | +--------------------+ Larry Miller lmiller@venera.isi.edu (no uucp) USC/ISI 213-822-1511 4676 Admiralty Way Marina del Rey, CA. 90292
brister@td2cad.intel.com (James Brister) (08/18/88)
In article <13036@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes: >In article <957@orion.cf.uci.edu> schmidt@bonnie.ics.uci.edu (Douglas >C. Schmidt) writes: >>Is the following always guaranteed to produce the "intended" result: >> >> return(head->next = head = (struct list *) malloc(sizeof(struct list))); > >Aside from the fact that there are two `*'s missing, and that malloc >can return NULL, the answer is no. > I'm curious; Why not? (assuming the two '*' were there and that malloc never returned NULL. ------------------------------------------------------------------------------- James Brister "In my previous life I was Shirley McLaine" brister@td2cad.intel.com brister@td2cad.UUCP
nevin1@ihlpb.ATT.COM (Liber) (08/18/88)
In article <957@orion.cf.uci.edu> schmidt@bonnie.ics.uci.edu (Douglas C. Schmidt) writes: >Is the following always guaranteed to produce the "intended" result: >[...] > return(head->next = head = (struct list *) malloc(sizeof(struct list))); >Since assignment associates from right-to-left this >will alway work, right (cryptic style notwithstanding !! ;-)). No (you should probably get a compiler warning). Although assignment *associates* from right-to-left, assignment does not (necessarily) *evaluate* from right-to-left. All that associativity means is that (a) = (b) = (c); (where a, b, c are expressions and a,b both produce lvalues) is equivalent to ( (a) = ( (b) = (c) ) ); and not ( ( (a) = (b) ) = (c) ); order of evaluation of the expressions a, b, c is still undefined. -- _ __ NEVIN J. LIBER ..!att!ihlpb!nevin1 (312) 979-???? IH 4F-410 ' ) ) There is something embarrassing about working at / / _ , __o ____ AT&T and not being able to get a *PHONE*! :-) / (_</_\/ <__/ / <_ These are solely MY opinions, not AT&T's, blah blah blah
chris@mimsy.UUCP (Chris Torek) (08/18/88)
>In article <13036@mimsy.UUCP> I noted that the expression >>> head->next = head = <expression>; is not guaranteed to produce the intended result; that instead, one must use head = <expression>; head->next = head; or, equivalently, head = <expression>, head->next = head; In article <1045@td2cad.intel.com> brister@td2cad.intel.com (James Brister) asks: >I'm curious; Why not? In simplest terms: because the compiler is allowed to figure out where `head->next' is before bothering to do the `head = <expression>' part. In other words, you might get what was intended, but you might instead get the equivalent of temp = head; head = <expression>; temp->next = head; which is obviously quite different. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
throopw@xyzzy.UUCP (Wayne A. Throop) (08/20/88)
> schmidt@bonnie.ics.uci.edu (Douglas C. Schmidt) > Is the following always guaranteed to produce the "intended" result: > > struct list { > int item; > struct list *next; > }; > > struct list foo() > { > struct list head; > > return(head->next = head = (struct list *) malloc(sizeof(struct list))); > } > > My intention is to create a dummy node in a circularly-linked list, > and assign the dummy node's next field to point to the head of > the list. Since assignment associates from right-to-left this > will alway work, right (cryptic style notwithstanding !! ;-)). This intent is very hard to deduce from the code, since the code is, in fact, illegal C. To whit, lint has this to say about the return statement: x1.c ============== (10) operands of = have incompatible types (10) operands of RETURN have incompatible types (10) warning: head evaluation order undefined warning: illegal combination of pointer and integer: (10) operator = warning: struct/union or struct/union pointer required (10) Further, another tool found this extra problem: ./x1.c 10 incorrect expression type The expression is: head->next Its type is: struct list The expected type is: a pointer type So, translating "foo" to be what was probably meant: struct list *foo(){ struct list *head; return(head->next = head = (struct list *) malloc(sizeof(struct list))); } And running THAT through lint, we find: (9) warning: head evaluation order undefined SO, the final result we come up with is: "No, that code will not portably do what you intend." The reason for this is that a side-effect takes place to the variable "head" within the expression, and the sequencing of side effects are not guaranteed in C. Thus, the head in "head->next" might be pointing to the newly allocated node, or to whatever the garbage it contained was pointing to. So, the return would have to be coded like so, introducing a sequence point to guarantee order of evaluation: return(head = (struct list *) malloc(sizeof(struct list)), head->next = head ); > thanks, You're welcome. -- Standards should be discovered, not decreed. --- Padlipsky -- Wayne Throop <the-known-world>!mcnc!rti!xyzzy!throopw