Subject: Re: [boost] boost::compressed_bitset
From: Peter Bindels (dascandy_at_[hidden])
Date: 2009-06-11 10:00:59
2009/6/11 Zachary Turner <divisortheory_at_[hidden]>
> The usage in the Windows kernel is similar, although they use it to store
> what they call the "VAD tree" (virtual address descriptor). For every
> process running on the system, there is a 4GB or larger address space
> (depending on architecture). They use this structure to determine which
> parts of this 4GB address space are allocated and which are not, so they
> can
> quickly satisfy allocation requests. It's likely that linux uses something
> similar but I don't know much about linux kernel.
>
More well-engineered filesystems have a similar approach called Extents,
which is basically a run-length encoded FAT table, split across the file
descriptors for quick access. Examples include ReiserFS, NTFS, ZFS and Ext4
(all IIRC).
Kind regards,
Peter Bindels