Whose code should we break? ( was Re: 64 bit C )

[Phil Howard KA9WGN]

gwyn at smoke.brl.mil (Doug Gwyn) writes:

>In article <65469 at brunix.UUCP> cgy at cs.brown.edu (Curtis Yarvin) writes:
>>But I want sizeof long == sizeof char *.  There are quite a few applications
>>in which I find myself writing my own memory manager; I need some type
>>in which I can flick the bits on my pointers, portably.

>As maintainer of several major pieces of software that did just that,
>I highly DISrecommend the practice.  If you can find ANY way to let
>the C implementation handle memory management sufficiently well for
>your actual needs, you are far better off doing so.

>Clearly bit diddling in pointers in far from portable.

Maybe.  Maybe not.  There is one type of data structure in which bit twiddling
will work on every type of pointer I can think of.  Only machine types in which
the size of the pointer itself can vary would have a problem and I know of NO
such machine type.

This data structure is use when you need a doubly-linked list whose elements
are very small and you have a tight memory constraint.  You can construct a
doubly-linked list using ONLY ONE pointer per element (and TWO anchors are
required) by storing the EXCLUSIVE OR of the elements on each side of an
element in that element.

Operating this list is very different.  When you have the pointer to TWO
ADJACENT elements (such as the two anchors as starting point) (I will call
these A and B) you can obtain the pointer to the NEXT element (I will call
it C, not to be confused with any language) by taking the exclusive or of
the pointer to A and the pointer IN B.

One of the interesting things about this approach to scanning through a list
is that if you reverse the starting pointers, the scan will take place in the
opposite direction even though the same exact code is used.  This list is
this symmetrical (which is consistent with there being one pointer item in
each element and the symmetry of exclusive or).

I have had one person tell me that this kind of data structure was too hard
to deal with and non-obvious.  It may not be the most obvious thing around
but once one understand how it works then it would be very clear.  He
complained he would not recognize it when encountering it in code in the
future.  I told him that properly documented code would explain what is
being done and that since he now knows about it, he will recognize it.
I am mentioning this to preempt a bunch of flames about an idea they don't
like.

If you take a pointer, exclusive or it with any bit pattern (usually of the
same size) then later exclusive or it with the SAME bit pattern, you will
get your pointer back.  Is there a machine type in which this is not so?
-- 

--Phil Howard, KA9WGN-- | Individual CHOICE is fundamental to a free society
<phil at ux1.cso.uiuc.edu> | no matter what the particular issue is all about.