Re: Hash tables and singly linked lists

From: Lois Goldthwaite (loisg_at_[hidden])
Date: 2001-01-12 07:48:50

There's a raging debate going on currently on the Austin Group reflector
(the Austin Group is a joint effort to reconcile and merge the Unix
standards from Posix/The Open Group/WG15), over what guarantees should
be continued in force for size_t. Up to now programmers have been able
to count on the ability to represent a size_t value in an unsigned long, 

        printf( "%lu", sizeof( foo ) );

but C99's introduction of long long has opened the possibility that
size_t may now exceed the size of a long int. off_t and ptrdiff_t have
already caused problems when processors went to 64 bits. This affects a
lot of other opaque types like pid_t as well. 

If I understand the debate (I have to keep ducking under the desk as
items whiz by my head), C99 specifies a (u)intmax_t which is the largest
size of integer type available. There are also printf "%ju" format
specifiers for same. I don't suppose you'll find it available on many
systems yet, though. 

Because of its possible impact on libraries and ABIs, this may be
something C++ programmers would want to keep an eye on. From a safe
place. Registration is free at www.opengroup.org/austin.

Lois

> > 
> > Have you considered the old xor double'ly linked list? Has the single
> > address space of a slist and the bi-directional capability of a list? The
> > iterators are invalidated easier because if the node before or after changes
> > the addressing won't work.
> 
> It's a cute trick, yes.  One problem with it, of course, is that 
> it isn't portable.  You can't xor pointers, only integers, and
> the C++ standard does not guarantee that there is any integer type
> large enough to store a pointer.  (This may be a purely theoretical
> issue, since I don't know of any common architecture that lacks such
> a type.)