On Sun, Nov 28, 2010 at 06:27:07PM +0100, Manuel Bouyer wrote: > > Wouldn't a hash table work? > > I think it's too dependant on uid distribution, or even how much uid you > have. a tree scales and adapts better.
I agree, hash tables often degenerate into a linear search. This means that it is still linear, just 'n' times faster that a simple linear search. It might be worth using a simple hash to cache recent lookups into the tree. OTOH it is worth remembering that there is already a 'per uid' structure (IIRC currently hashed % MAXUSERS) used for counting processes per user. Would seem relevant to hang the per-mount data of this structure. (and maybe use a better lookup than the current hash - it is one of the few uses of MXUSERS). On disk, I'm not sure. Once you've read a disk block, you might as well do a linear search! This probably only happens at user login time. More problematical is some kind of log so that you don't need to scan the entire fs after a system crash... David -- David Laight: da...@l8s.co.uk