1

I have just came to the problem of having to cut some lines from a large (gigabyte) sized file, and being aware of potential CPU hog trying to read it in memory, I wanted to edit it in-place instead... and so came upon these questions:

... and further also these:

However, I was wandering about something else: I believe (but I'm not sure) that any filesystem (like ext3) would have to employ something like a linked list, in order to be able to describe something like fragments of a file that are mapped to areas of disk.

Thus, it should be possible to do something like this - for example, let's say, I have a file bigfile.dat like this (numbers should indicate byte offset, but it's a bit difficult to align them):

0  1 2  3   4  5  6  7  8  9 10 11  12 13 14 15 16 17 18 19 20 21 22 23

L 1\n L 2\n L 3\n L 4\n L 5\n L 6\n

This file could then, in principle, be loaded in a terminal application for browsing - let's imagine we call a tool editsegments bigfile.dat, and let's say it similar to how less -N bigfile.dat would display the same file (with line numbers):

      1      1      L 1
      2      2      L 2 *
      3      3      L 3
      4      4      L 4 *
      5      5      L 5
      6      6      L 6
bigfile.dat (END) 

Let's say, I could enter a command there (say d for delete lines), click another key or the mouse where it is indicated above with * - meaning that everything between lines 2 and 4 should be deleted. The program would then respond with this being shown:

      1      1      L 1
      2      5      L 5
      3      6      L 6
bigfile.dat (END) 

Now we can see that leftmost first column shows "new" line number (after cut), second column is "old" line number (before cut) - and then the actual line contents follow.

Now, what I imagine happens after this pseudoapplication editsegments is exited, is that first and foremost, bigfile.dat is untouched; however, now there would be also an extra text file in same directory, say bigfile.dat.segments; with these contents:

d 4:15 # line 2-4

... and additionally, a special file (like a "symlink") - let's call it bigfile.dat.iedit - would appear.

Now, basically, the result of all this would be, that if I now try to open bigfile.dat.iedit with something like less -N bigfile.dat.iedit, I'd want to get the "edited" contents:

      1 L 1
      2 L 5
      3 L 6
bigfile.dat (END) 

... which could be achieved, I guess, by somehow instructing the operating system, that when $FILE.iedit is opened, first $FILE.segments should be opened and read; the d 4:15 would instruct that bytes 4 to 15 in the original file should be left out - which would result with something like:

0  1 2  3   4 5  6  7  8 9 10 11 12,3,4 15 16 17 18 19 20 21 22 23

L 1\n L 2\n L 3\n L 4\n L 5\n L 6\n

0  1 2  3  ------------------------------->16 17 18 19 20 21 22 23

In other words - assuming that in a filesystem concept of a file, each byte of content also contains a "link" to the next byte in the chain - it should be possible to instruct the filesystem to establish a new linked list based on a script, and provide the contents as represented by this modified linked list through a special file (symlink or pipe).

That is what I meant by "scripted" in the title - that the "new" linked list can be controlled by a script file ($FILE.segments), user-editable in a text editor (or generated by a front end application). What I meant by "multipass" is the fact that bigfile.dat in this process is not modified at all; so I could edit the first (original) gigabyte today, saving progress in ($FILE.segments) - then I could edit the second gigabyte tomorrow, again saving progress in ($FILE.segments) etc. - all the while, the original bigfile.dat is unchanged.

When all edits are complete, one could probably call a command of sorts (say, editsegments --finalize bigfile.dat), which would simply permanently encode the new linked list as the contents of bigfile.dat (and in line with that, remove bigfile.dat.segments and bigfile.dat.iedit). Or even easier, one could just do:

cp bigfile.dat.iedit /path/to/somewhere/else/bigfile.modified.dat

Of course, besides a delete script command, one could have a replace command as well, say:

r 16:18 AAA 

... saying: replace the content between bytes 16 and 18 with the next 18-16+1=3 bytes after the space (that is, the AAA) - the linked list could in fact "hook" into the script command content itself (the below chart containing also the delete):

0  1 2  3   4 5  6  7  8 9 10 11 12,3,4 15 16 17 18 19 20 21 22 23

L 1\n L 2\n L 3\n L 4\n L  5\n L 6\n

0  1 2  3  ------------------------------->|     |  19 20 21 22 23

. . ...\n r 1  6  :18  AAA \n  . .  . .


Now, I guess that programs like hexedit (as mentioned here) do change files in-place - but I'd just like the benefit of possibility of scripting (even better if it could be regulated by a GUI application, even if a terminal one), and the benefit of not actually having the original file changed, until one confirms all edits are as required.

I'm not sure if something like this is possible at all - and even if it is, I guess it may require a dedicated driver (rather than just a user program)... But I guess it is worth asking anyways - is there anything like this for Linux?

Many thanks in advance for any answers,
Cheers!

0

5 Answers 5

1

The structure of files on disk depend on the filesystem in use. None of the real-world filesystems use linked lists as you describe (that would make fseek(3) unbearable). The closest thing to this is Microsoft's FAT, essentially moving the pointers out of the data blocks into an array shadowing them.

But most filesystems do use some pointer-based references to data blocks in the file, so in principle one could cut out a block of a file by just shuffling a handfull of pointers around (not the whole file contents) and marking a block in the middle of the file as free. Sadly, that isn't a very useful operation, file blocks are rather large (typically 4KiB), and will rarely align reasonably with the structures in the file (be it lines or other subdivisions).

0

What you describe sounds a lot lke like a replay of a text-editor's redo list against the unchanged original file to which that redo list belongs. I'm pretty sure that gvim has such a persistant undo/redo list, which you may(?) be able to utilize, and I know that emacs definitely has such a list which you could most likely coax to do whatever you want (via an elisp script), eg. Save Emacs undo history between sessions.

As a side note, turning off all the unwanted actions could be a good idea for such large files, eg: auto-save, syntax highlightling (slow on a big emacs file), etc.. and emacs on a 32-bit system has a 256 MB file size limit.

It certainly won't be as concise as what you have suggested, but may be usable if there aren't huge numbers of changes.

0

Generally, you can't edit a file in place without bringing the entire file into memory. I'm assuming that what you actually want to do is just have a new file that is a copy of the old one sans specific lines. This can easily be accomplished using the unix utilities head and tail. For instance, to copy everything except lines 5, 12, and 52 from a file, you can do

head -n 4 bigfile.dat > tempfile.dat
tail -n +6 bigfile.dat | head -n 6 >> tempfile.dat 
tail -n +13 bigfile.dat | head -n 39 >> tempfile.dat 
tail -n 53 bigfile.dat >> tempfile.dat

In case you're not familiar with these utilities, I will explain in more detail.

The head utility prints out the first n lines from a file. If it is not given a positional argument, it will use standard input as the file. The -n flag tells head how many lines to print out. So, head -n 2 will print just the first 2 lines from standard input.

The tail utility prints out the last n lines of a file. Like head, it can read from a file or standard input. The -n flag tells tail how many lines to print out from the end. You can also prefix the number with a plus sign to tell tail to print out the lines from the end of the file starting with that many lines from the beginning. For instance tail -n 2 prints the last two lines from standard input. However tail -n +2 prints out the all the lines starting with line number 2 (omits line 1).

So in general, if you want to print lines in the range [x, y) from a file, you would do

`tail -n +x | head -n d`

where d = y - x. These commands will produce a new file. You can then delete the old file if you wish. The advantage of doing it this way is that head and tail only need to keep one line in memory at any single time, so it will not quickly fill up your RAM.

0

A bit of lateral thinking made me think that if the editing behaviour of the Unix sed command can do what is needed then we are left with the issue of the large file.

How about working with compressed files instead. You could bzip your original input then do something like:

bzcat input.bz2 | sed -e '...' | bzip > output.bz2

If your data is anything like your example then you could expect large savings in space when storing the compressed file, and although you have to incur the cost of decompression/compression, you might save something as you are moving less data to and from secondary storage.

The editor vim can display some compressed files but I think it just decompresses them fully internally, which would not help you.

0

Sounds like a job for a sed script. IIRC it was designed for such tasks. Line by line processing, repeated processing of the same group of commands, and regex all combine in one tool. While I know it will do the job, I cannot guide you further other than directing you to their fine man page.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .