key64_t? ino64_t?

Robert Collins
Wed May 14 09:09:00 GMT 2003

On Wed, 2003-05-14 at 16:36, Charles Wilson wrote:

>  People expect key_t to be a
> primitive, don't they?  Sure, key1 < key2 doesn't mean anything, but key1
> == key2 ought to be meaningful.  So, you'd have to implement operator==,
> which makes key_t a class, not a struct.  

Actually, both C and C++ implement synthetic operator == for structs. No
class magic needed. They simply compare the bit pattern of the two

> But that kills packing (e.g. a key_t object is no longer '72 bits of id
> data') because key_t now has vtables, ctor, dtor, etc etc. 

No, none of the above apply.

>  I *really*
> don't like the idea of making key_t a non-primitive type.  Why should we
> -- linux doesn't, and they've decided to live with aliasing into 32bits. 
> Surely we can live with a 64bit space, and its one billion times lower
> probability of clashing?

Aliasing isn't bad. However: we *must* prevent clashes. Probability has
nothing to do with it. I can't comment on the Linux implementation: I
haven't reviewed it.

I don't like the patch : Hashing is bad. We hash today ... if we are
going to change *at all*, lets Do It Right.

/* pseduo code
assuming we have a typedef long key_t;
ftok (const char *path, int id)
    return cygserver_ftok(canonical_path(path), id);

in cygserver

cygserver_ftok(const char *path, int id)
    /* 24 bits for the trie node, 8 bits for the userspace id. */
    FTOKNode * aNode = FTOKNode::Keys.find(path);
    if (!aNode) {
        aNode = new FTOKNode();
        FTOKNode::Keys.insert (path, aNode);
    return aNode->key || id;

   key = NextKey++;

Keys can be a tree or a trie, for most common uses (say less than a 1000
unique ftok's) either will perform *just fine*. A trie would be needed
for larger implementations...

Should give a reasonably performing implementation with space for
16.7Million ftok() calls on unique paths. It will use space linear to
the path length of each unique path presented to ftok().

This is what I meant by a lookaside table.


GPG key available at: <>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
URL: <>

More information about the Cygwin-developers mailing list