Author: Dann Corbit
Date: 13:14:51 07/03/02
Go up one level in this thread
On July 03, 2002 at 05:35:05, Sune Fischer wrote:
>On July 03, 2002 at 03:50:36, Omid David wrote:
>
>>On July 02, 2002 at 20:31:30, Dan Andersson wrote:
>>
>>>The proposition is not as clear cut as you might think. For a definitive answer
>>>you might look up Paul Hsieh's programming pages. For an x86 arhitecture the
>>>answer depends: http://www.azillionmonkeys.com/qed/case3.html
>>>
>>>MvH Dan Andersson
>>
>>There are many interesting ways to do it, but the most interesting way I found
>>is:
>>
>>a ^= b ^= a ^= b;
>>
>>Omid.
>
>Yes, it's well known trick :)
>http://www.sjbaker.org/steve/software/cute_code.html
>
>but he says it's strictly illegal as a C++ statement.
>
However Scott Smith <ssmith@tyler.net> pointed out that this is equivelent to
the even more aesthetically pleasing:
This:
x ^= y ^= x ^= y ;
is just a rip-off from the C FAQ, and is an example of undefined behavior.
3.3b: Here's a slick expression:
a ^= b ^= a ^= b
It swaps a and b without using a temporary.
A: Not portably, it doesn't. It attempts to modify the variable a
twice between sequence points, so its behavior is undefined.
For example, it has been reported that when given the code
int a = 123, b = 7654;
a ^= b ^= a ^= b;
the SCO Optimizing C compiler (icc) sets b to 123 and a to 0.
See also questions 3.1, 3.8, 10.3, and 20.15c.
You can easily fix it by separating the statements or even by using the comma
operator. At any rate, it's a lame hack that has had its day. Same goes for
the evil subtraction trick.
They also have places where they break down. For instance, if a and b happen to
be the same object {e.g. invoked from a macro}, you end up with zero.
Some posts on the topic extracted using GOOGLE:
"From: User923005 (user923005@aol.com)
Subject: Re: Free is syntactic cyanide.
Newsgroups: comp.lang.c
View this article only
Date: 1997/07/25
>It's also not lost from the literature; I believe that Knuth used
>XOR for this purpose (or I so I recall reading in one of the papers
>on conservative garbage collection).
>
>Am I being pedantic? Only a little bit. In a previous job, I
>worked on a C/C++ run-time checker, and dealing with this sort
>of code was a mess. The author doesn't usually want to be told
>about it, but it introduces anomalies that tend to rattle around
>into downstream execution. Workarounds compromise other checking.
>"Good citizens" suffer when these workarounds thwart detection
>of their real errors.
In any case, both forward and backwards pointers had better not point to
the same data item or OOPS! {Neither XOR nor subtraction is immune to x^x
or x-x}.
For the cost of one pointer, deadly danger has been purchased. Not to
mention the evils of pointer arithmetic that you already mentioned.
I'm at home, so I say anything I please."
Similarly:
"From: Dann Corbit (dcorbit@solutionsiq.com)
Subject: Re: I have a PROBLEM with my linear List!!!
Newsgroups: comp.lang.c
View: Complete Thread (29 articles) | Original Format
Date: 1998/05/14
Lawrence Kirby wrote in message <895169702snz@genesis.demon.co.uk>...
[snip]
>>6. With an ordinary linked list, removing an item, adding an item or deleting
>>an item is O(1). [Finding it is still O(n).] With this type of list it is
>>O(n).
>
>No, it is still O(1), although there is a bit more work. The problem is that
>other references into the list might be invalidated.
Quoting an older message:
"Subject: Re: Why is there no singly linked list in the STL?
From: Pete Becker <petebecker@acm.org>
Date: 1998/02/06
Message-ID: <34D9D318.6E8922C3@acm.org>
Newsgroups: comp.std.c++
[More Headers]
[Subscribe to comp.std.c++]
Jerry Coffin wrote:
>
> In article <w2xbtwp6bju.fsf@woodstock.cis.ohio-state.edu>,
> wenger@cis.ohio-state.edu says...
> >
> > Why is there no singly linked list in the STL?
>
> I suspect it's because it adds relatively little functionality.
>
> > The STL list
> > supports bidirectional iterators with constant time operations
> > so it must be implemented as a doubly linked list. A singly
> > linked list obviously requires half the pointers of a doubly
> > linked one.
>
> It may be obvious, but it's generally incorrect. If you're really
> excited about saving space, you can generally implement a doubly
> linked list in the same amount of space as a singly linked list.
> Traversing the list becomes marginally slower due to having to do an
> exclusive or before dereferencing each pointer, but other than that
> about the only penalty is in readability.
There's a major loss of capability here: if you have a pointer to a node
in a list like this you cannot unlink it from the list in constant time.
That is, the usual technique for unlinking a node (null checking
ignored) is:
node->next->prev = prev;
node->prev->next = next;
You can't do this with the xor trick -- you have to walk the list from
one end or the other in order to get the information you need to sort
out the pointers.
-- Pete
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://reality.sgi.com/austern/std-c++/faq.html ]"
Now, I will admit that we could possibly use this list something like
strtok(), or save context pointers perhaps with some other information. But
what is our gain now?
--
Hypertext C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
C-FAQ ftp: ftp://rtfm.mit.edu, C-FAQ Book: ISBN 0-201-84519-9
Try "C Programming: A Modern Approach" ISBN 0-393-96945-2
Want Software? Algorithms? Pubs? http://www.infoseek.com"
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.