Re: key64_t? ino64_t?

[Robert Collins <rbcollins at cygwin dot com>]

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
structs.

> 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;
*/
key_t
ftok (const char *path, int id)
{
    return cygserver_ftok(canonical_path(path), id);
}

/*
in cygserver
*/

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

where 
FTOKNode::FTOKNode() 
{
   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.

Cheers,
Rob 


-- 
GPG key available at: <http://users.bigpond.net.au/robertc/keys.txt>.

Attachment: signature.asc
Description: This is a digitally signed message part