On Wed, Nov 18, 2009 at 10:03:05AM +0000, Julian Foad wrote: > Alan Barrett wrote: > > By the way, patch(1) is described in > > <http://www.opengroup.org/onlinepubs/009695399/utilities/patch.html>. > > The algorithm described under "Patch Application" there is the minimal > requirement, and is really simple compared to Stefan's. We don't have to > try to be too clever. A simple algorithm can work reasonably well.
This description is very similar to the one given in OpenBSD's patch(1) man page. The problem with this algorithm is that it assumes that seeking backwards in the file line-by-line is easy. But it's not. We can only seek to byte offsets. We need to potentially read the entire file line-by-line anyway to find out where the line endings are. That's why my algorithm simply reads everything line-by-line and does the matching while at it. Seeking backwards will just complicate the code, also because we can't use our stream abstraction to go backwards. Stefan
