Re: casting (void *) to (class *)
On Apr 16, 12:41 pm, "Alf P. Steinbach" <al...@start.no> wrote:
* James Kanze:
On Apr 15, 1:58 pm, "Alf P. Steinbach" <al...@start.no> wrote:
* James Kanze:
On Apr 15, 4:04 am, "Alf P. Steinbach" <al...@start.no> wrote:
* Jonathan Lee:
But better, don't use void* pointers (except for the
special case of identifying objects in e.g. a hash table,
in which case you should make sure to have pointers to
complete objects, e.g. obtained by dynamic_cast to
void*).
I'm not sure I understand this one. Do you mean just
using the pointer as the key?
Yes.
(And how do you get a hash value for a pointer, portably?)
Wait a sec, checking Boost...
KO.
// Implementation by Alberto Barbati and Dave Harris.
#if !BOOST_WORKAROUND(__DMC__, <= 0x848)
template <class T> std::size_t hash_value(T* const& v)
#else
template <class T> std::size_t hash_value(T* v)
#endif
{
std::size_t x = static_cast<std::size_t>(
reinterpret_cast<std::ptrdiff_t>(v));
return x + (x >> 3);
}
Then reduction to the internally required range of the
particular hash table is the responsibility of that hash
table.
Of course. But the above isn't guaranteed to work, and I've
worked on systems where it wouldn't work. (By not working,
I mean that two pointers which compare equal will result in
different hash values.)
I think that problem is academic.
Not really.
It is the problem of a platform not supporting Boost. :)
So Boost isn't all that portable. I've known that for a long
time.
If one could find a C++ compiler for 16-bit Windows or MS-DOS
and compile in anything but "large model" there would be a
problem. Actually I still have the CD for such a compiler,
Visual C++ 1.5 :) But it's not standard C++.
Actually, the problem is large model, in real mode. At least
until 2007, Intel was manufacturing the 80186, which only worked
in real mode. Given the date, it wouldn't surprise me if they
had a EDG based C++ compiler for it---in other words, a C++
compiler more modern than what you're probably using under
Windows.
We can *imagine* some embedded system using e.g. an 80286 or
something, and segemented addressing.
But it's a myth that standard C++ is applicable to such systems.
Why not? The goal of the standards committee is that it should
be. And I've certainly used C++ (pre-standard, of course) on an
8086.
I also know of one system where it is almost useless. Where
for any dynamically allocated complete object, x would
always have the same value.
The standard guarantees roundtrip conversion for integer of
"sufficient size".
Only if such an integral type exists. C90 introduced long long
and ptrint_t, so its not existing on a system supporting these
aspects of C++0x is academic. But the code you posted used
size_t, which is NOT guaranteed to be of sufficient size.
So when the integer is of "sufficient size" conversion to
integer can't yield the same value for different pointer
values.
For an integer of "sufficient size", again. The code you posted
used size_t. I've worked on machines (in C++) where that wasn't
"sufficient size".
The above supposes a one to one mapping between pointers and
the integral types involved, which is far from universal.
It can only be far from universal if there are a number of
systems with C++ compilers where those integer types,
ptrdiff_t and size_t, are not of the "sufficient size"
required by the standard for roundtrip conversion.
There are two serious problems with the code, depending on the
implementation of pointers on the system. The first is that
size_t may *not* have sufficient size; on a segmented
architecture, it may only be large enough for the offset, and on
at least one system I've used, every request for dynamic memory
returned a new segment, with an offset of 0. The second is that
is in fact quite common (IBM 360 and successors---including IBM
mainframes today, in some modes; Intel 80x86, etc.) for pointers
to allow more than one bit pattern to point to the same memory.
When you compare pointers for equality, the compiler has to take
this into account, somehow "normalizing" the pointer value if
there isn't a special instruction for the comparison. It
doesn't do this when converting to an integral type, so you end
up with several different hash codes for the same value.
If you're not concerned with such systems, if everything is
Windows for you, fine. Not all code has to be portable. But
don't pretend that it is.
I also don't see why the double cast, rather than casting
directly to size_t,
Me neither.
If anything, perhaps it is designed to encourage discussion
about why the heck they're doing that. :)
But there is a difference, namely that for a sign-and-value
representation of signed integers, it maps binary 00...0 and
10...0 to the same size_t value, 0.
There is a difference, yes. On the machine I'm working on now,
addresses are considered "unsigned" (more or less, but the
machine does use linear addressing, no segments or anything).
And there are addresses which can't correctly be represented in
a ptrdiff_t, so technically, the code shouldn't compile. (But
the compilers I have don't enforce this.)
and the expression in the return statement is a hack.
Sort of. A maximum alignment of 8 is pretty universal. And
it's only a "value adding service" so to speak, for the
hashing can't guarantee lack of collisions in the final
reduction to hast table size; it can only make it less likely.
Given the other restictions (all pointers which compare equal
have a unique bit pattern), they might as well do it right,
treat the pointer as an array of unsigned char, and use
something like a Mersenne prime function or FNV hashing.
(Consider that if the objects in question are big enough, the
dynamic allocator might try to return them page aligned, and if
they are small, the dynamic allocator might use a special pool
of them, resulting in all of the values being very close to one
another.)
If they're willing to restrict the function to architectures
with a one to one mapping, then they might as well restrict
it to architectures without any padding bits in integral
types as well, and just do a classical hash treating the
pointer as an array of bytes.
Well, they're relying on the guaranteed roundtrip conversion
for "sufficient size" integers, which means guaranteed unique
values.
As I see it. :-)
Where do you see a round trip? Or "sufficient size"?
The concrete case I know of (which was current up until at least
two years ago on some Intel embedded processors) is the basic
8086 architecture, in real mode. Typically, pointers were 32
bits, but size_t was only 16 bits. And the Intel real time
kernel only allocated segments, which meant that the results of
converting a dynamically allocated pointer to a size_t (assuming
the compiler accepted it) was always 0. Given an unsigned long,
of course, the pointer fitted. When comparing pointers, the
compilers normalized (segment * 16 + offset), but they didn't do
this when converting to an unsigned long; they just copied the
bits. Which of course causes no problems for round trip, since
you get back the pointer you started with, but does cause
problems because the hash code can be different, even though the
pointers compare equal, and represent the same address.
Of course, if you're only targetting Windows, or even if you're
only targetting desktop computers (Windows, Linux and Mac), it's
not something you should worry about. But that's not what I
understand by "portable" (and I certainly wouldn't consider it
acceptable for something claiming to be a general purpose
library, like Boost).
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34