11-Nov-2007

Added the feature to allow a backup file to be created whenever inputting data. At sometime in the future the idea is to have it connect to a remote machine and write the backup file there. However, right now it only creates the backup file on the local machine.

The backup file is written at the same time as the data is written to the archive the blocks are out of order. Since I wanted the backup file to be identical to a diff_compressed file (so I could use the same patch_compressed program) I needed to sort the backup file into order.

I don't know if it is a new sort algorithm or if there is a similar algorithm already out there, but here is how it works:

1. Start at the beginning of the file and read the blocks into a 1 megabyte buffer in order.
2. Keep two sections of blocks in the buffer, the "lower" and "upper" with empty space in between.
3. When each block is read in compare it to the top of the lower block and the bottom of the upper block.
4. If it is less than the top of the lower block insert it into the proper place in the lower block.
5. If it is greater than the bottom of the upper block insert it into the proper place in the upper block.
6. Otherwise add it to either the top of the lower block or the bottom of the upper block, depending on which one it is closest to.
7. Once the buffer is keep reading blocks from the file and check each block against what is already in the buffer.
8. If it is greater than the block in the top of the buffer, skip it and go on to the next block.
9. Otherwise write the block in the top of the buffer back in it's place in the file and then insert the block just read into it's proper place in the buffer.
10. Continue doing that until the end of the file is reached. When the end of the file is reached, write the buffer back into it's position in the file and reset all the positions to the next 1 megabyte chunk in the file.
11. Repeat the above until the entire file has been processed.

Copyright © 2007 – J. Scott Edwards

105