I agree that it's simple, but not that it's
efficient. For small micros,
finding the first "0" bit in an arbitrarily long bit string takes a few
cycles.
You would just look for the first byte that is not a 255.
That's absolutely true, you can do that, and from there it's fairly
straightforward. But here's what I'm thinking. Let's say you have just a
1.44MB floppy, with a 512 byte sector size. A convenient allocation size
might be one sector, because you can easily fit the total number of
allocation units (2880) into a 16-bit unsigned integer (that which is used
in the file link blocks). That takes about 360 bytes to store on disk,
which fits nicely into a single sector as well. So far, so good.
But now let's say you go to an 80MB partition with 512 byte sectors. You
then have approximately 163,840 allocation units (not discounting any space
used for boot and other common structures). That's too many for a 16-bit
word, so you decide to make your allocation units four sectors. That means
you have 40,960 allocation units, each of which is 2K in size. Your
free-space bitmap, then, would be 5,120 bytes, which takes 10 sectors or 3
allocation units to store depending on your implementation choices, but
let's just go with the smaller 10-sector size.
I'm thinking about two things: first, trying to keep the entire volume
bitmap in memory chews up almost 5K of RAM, and that's probably not good for
an 8-bit machine, at least, it's not sufficiently memory-efficient, IMO.
Second, if you decide then that you'll only deal with one sector of it at a
time to save RAM, you may have to read-then-write juggle those ten sectors a
lot. If you do a linear search for a free block, it may be that you can rip
through the 255-valued bytes quickly, but they have to be in RAM, so you may
have to do several reads to find what you want, which saps time.
I wonder if it really would sap a lot of time. Modern IDE drives have
large cache buffers so I would think that system could very likely read the
data from the buffer. I'm thinking that as slow as these old systems are
and as fast as the modern drives are that it would be better to use a
simple and fast algorithim even if it means more drive accesses.
Joe