]> git.ipfire.org Git - thirdparty/coreutils.git/commit
Avoid O(N**2) behavior when there are many temporary files.
authorPaul Eggert <eggert@cs.ucla.edu>
Sat, 13 Nov 2004 00:50:56 +0000 (00:50 +0000)
committerPaul Eggert <eggert@cs.ucla.edu>
Sat, 13 Nov 2004 00:50:56 +0000 (00:50 +0000)
commit8aed6ea305f6e55aad18e42340f8706d2dadcdc4
tree152a4808dae2fad532dd34ed2725bff7edd3f37d
parent0174a06214ff42127d57bece3062f2c30633ec55
Avoid O(N**2) behavior when there are many temporary files.
(temptail): New variable, so that we can easily append to list.
(create_temp_file): Create new files at end of list, so that
searching the list has O(N**NMERGE) behavior instead of O(N**2).
(zaptemp): Update temptail if needed.
(mergefps, merge): Accept new arg that counts temp files, and keep it
up to date as we create and remove temporaries.  This is for
efficiency, so that we don't call zaptemp so often.
All callers changed.
(sort): Don't create array in reverse order, since the list of
temporaries is now in the correct order.

(zaptemp): Protect against race condition: if 'sort' is
interrupted in the middle of zaptemp, it might unlink the
temporary file twice, and the second time this happens the file
might already have been created by some other process.

(create_temp_file): Use offsetof for clarity.
(die): Move it up earlier, to clean up the code a bit.
src/sort.c