bug#6524: RFC: modules for generic unordered sets and mappings

[Eric Blake]

On 07/01/2010 06:44 PM, Paul Eggert wrote:
> I've just gone through "du", and it's fresh in my
> mind, so I thought I'd run through what I needed there, to see how
> well it maps to the proposal.
> 
> I needed three kinds of hash tables.
> 
> * Table A is indexed by device number (a dev_t value) and the value is a
>   secondary hash table.  Typically the number of devices is relatively
>   small.
> 
> * Table B is indexed by inode number (an ino_t value) and has no value.
>   All that matters is whether the key is present.  So it is a set,
>   not a general mapping.  Often there are many, many inode numbers.
> 
> * The gnulib hash package uses void * keys, but having a void * value
>   that exists only to point to an ino_t value wastes memory.  So, if
>   an inode number is small (less than M, say), it maps to itself.  If
>   it is large, it is a key into a third table (table C) whose values
>   are mapped inode numbers.  (Values in table C are always M or
>   greater.)  The mapped inode number (whether taken from table C, or
>   used directly) is cast to void * and then used as the index into
>   table B.  In practice, most inode numbers are less than M so this is
>   a storage win.

We need to be careful on cygwin.

$ ls -i | head
 1125899907178954 ABOUT-NLS
28147497671067760 AUTHORS
 1970324837308495 COPYING
 9851624184873962 ChangeLog
 4785074604197847 ChangeLog-2005
 1970324837180710 ChangeLog-2006
 1970324837078885 ChangeLog-2007
 2251799813904421 ChangeLog-2008
  281474977732635 GNUmakefile
 1125899907781258 GNUmakefile~

sizeof(void*) == sizeof(size_t) == 4, but sizeof(ino_t) == 8, and most
inodes are quite randomly dispersed but definitely larger than 4 bytes.
 Does your scheme work well at mapping cygwin's 8-byte inodes into
4-byte pointers?

-- 
Eric Blake   address@hidden    +1-801-349-2682
Libvirt virtualization library http://libvirt.org

signature.asc
Description: OpenPGP digital signature