In article <43***********************@news.xs4all.nl>
Skarmander <in*****@dontmailme.com> wrote:
Reading a file in reverse will be one of the most inefficient operations
on any OS, I'd wager.
That would depend on the OS and file system. A file system
implemented via a B-tree with sideways links (B+ or "B-link" or
any of those variations) could be read backwards quite quickly.
A file system designed for use on a DVR/PVR might also use a doubly
linked list, something like the old DOS FAT file system (i.e.
cluster or extent based) except with links going both directions.
The stdio I wrote for BSD (found in 4.4BSD derivatives) also
attempts to optimize fseek() calls on files opened in read-only
mode, so that the sequence:
/* ensure that file is open and contains at least 1 byte */
fseek(fp, -1L, SEEK_END);
for (;;) {
c = getc(fp);
/* do something with c, e.g., putc(c) */
if (ftell(fp) == 0)
break;
fseek(fp, -2L, SEEK_CUR);
}
behaves in a reasonably fast manner, reading one underlying file
system block at a time and otherwise working entirely within the
stdio buffer.
Reading the blocks backwards is not particularly hard on a Unix-like
file system (with inodes containing direct and indirect blocks),
although it does not play well with the OS's read-ahead mechanism.
It *is* particularly hard on the DOS FAT file system, which --
through a design aimed at saving space on 360 kilobyte floppies --
makes it impossible to find block N of any given file without first
finding blocks zero through N-1 inclusive. Modern file systems
(NTFS, ext2, ext3, Reiser, etc) are as good as Version 7 Unix
though, having finally caught up to the 1970s. :-) Some are even
worth of the 1980s, handling files larger than four gigabytes! :-)
(To explain the amusement here, I should add that UFS -- the 4.2BSD
file system that came out in 1983 or 1984 or so -- did all this,
way back then. The newer Linux file systems do have other merits,
but it does seem odd that only recently have other desktop OSes
acquired capabilities we had back in the mid-1980s.)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it
http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.
