Re:Tree traversal without recursion: the tree as a state mac...
by PeCaN on Tuesday September 03, 2019 @03:39AM
(#20864384)
upper 16 bits are usually unused on x86_64 as well (since the x86_64 virtual address space is only 48-bit), though whether they're one or zero depends on bit 48
Re:Tree traversal without recursion: the tree as a state mac...
by rrobukef on Tuesday September 03, 2019 @02:26PM
(#20869555)
And doubles have some 2^50 NaN's. It's possible to create a tagged pointer of either a double, 32-bit integer, pointer or a small string and still have space for more.
Sadly the original Mozilla link is broken. https://wingolog.org/archives/2011/05/18/value-representatio...
Re:Tree traversal without recursion: the tree as a state mac...
by msla on Tuesday September 03, 2019 @09:46AM
(#20866385)
This reminds me of all the problems Apple had with 24 bit addressing and smuggling data in the unused eight bits at the top of each pointer. Andy Hertzfeld considers that his worst blunder:
http://www.folklore.org/StoryView.py?project=Macintosh&story...
Re:Tree traversal without recursion: the tree as a state mac...
by xxs on Tuesday September 03, 2019 @03:41AM
(#20864395)
yeah, 64bit is a lot of address space, and masking/shifting provides quite a few bits if one is willing to manage their own pointers.
Re:Tree traversal without recursion: the tree as a state mac...
by rocqua on Tuesday September 03, 2019 @03:47AM
(#20864422)
Hard to get this done properly in C I imagine. You're getting into UB the moment you start bit-fiddling with pointers I think.
Re:Tree traversal without recursion: the tree as a state mac...
by vnorilo on Tuesday September 03, 2019 @04:10AM
(#20864545)
Not UB but rather implementation defined. The compiler will not do anything weird here, but you rely on platform behavior that's not specified by the C lang spec.
Re:Tree traversal without recursion: the tree as a state mac...
by PeCaN on Tuesday September 03, 2019 @03:53AM
(#20864461)
Nah, so long as you cast to an integer (preferably uintptr_t) before fiddling with it you're fine¹
―
¹ I think, but to be honest it's been some time since I really knew the arcane C rules and I'm not confident anymore
Re:Tree traversal without recursion: the tree as a state mac...
by Asooka on Tuesday September 03, 2019 @04:52AM
(#20864756)
Not UB in the slightest. You can take a pointer, cast it to uintptr_t, do whatever you want to that int, then cast it back to a pointer. It's only UB if the resulting pointer isn't valid or you cast it to the wrong type (and strict aliasing is enabled.
Yep, the lower 1-3 bits in many pointers will always be zero due to how C run-time allocators and structure alignment works out of the box.