Re: [BK PATCH 1/2] Remove NGROUPS hardlimit (resend w/o qsort)

From: William Lee Irwin III (
Date: Thu Nov 14 2002 - 20:53:04 EST

On Thu, Nov 14, 2002 at 08:45:39PM -0500, Pete Zaitcev wrote:
> This sounds intriguing.
> Bill, if I may borrow from your data structure expertise,
> what would you do if you wanted gid_t's indexed by two criteria?
> Obviously, we want them them indexed by value (to look them up
> for access checking), but NFS also needs them sorted by usage,
> to fit the last 3 into the RPC parameters. This looks like
> something requiring two overlaying trees who share leafs,
> and every leaf being a single gid_t, with nightmarish overhead.
> Before Tim came to the scene, the hope was that lookups would
> do exhaustive search of arrays, sorted by LRU, while RPC
> picked N leading elements of said sorted array. Tim busts
> this scheme to pieces, because he sorts arrays by value
> (if I read it right).

B+ trees separate metadata from data entirely, so two distinct
B+ tree "indices" attached will work just fine for this overlaying
of trees that share leaves.

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

This archive was generated by hypermail 2b29 : Fri Nov 15 2002 - 22:00:35 EST