radix tree implementation for quota ?

[Manuel Bouyer <bouyer%antioche.eu.org@localhost>]

Hello,
our FFS quota system is pretty outdated and is less and less suitable
for modern storage (quotacheck is long and can't be avoided). I'm thinking
about coding a new quota system with would be more closely integrated
with the filesystem, where quotas would be integrated with filesystem
metadata (maybe as part of a hidden indode, the same way WAPBL has a
inode for in-filesystem log). With this, quotas can be checked by fsck_ffs(8)
at almost 0 cost in time, and it can be covered by WAPBL, completely
eliminating the need for quotacheck(8) on reboot.

One open question is how to store quota informations on disk.
At this time we use one big array indexed by uid or gid. This can
be very space-consuming if you have a very sparse uid/gid allocation,
this is why I don't think this simple format is suitable any more
(especially with 32bits uid/gid, and 64bit storage for various values).
Linux uses a radix tree for this, and I coudln't come up with a better idea :)

Do we have a generic enough radix implementation somewhere wich could be
used for this ? We already use it for network routing table, but it
didn't look generic to me.

-- 
Manuel Bouyer <bouyer%antioche.eu.org@localhost>
     NetBSD: 26 ans d'experience feront toujours la difference
--