From fc19c2ddadad27eefa25a06e19f6b45c319ce2da Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Sat, 13 Nov 2004 00:53:23 +0000 Subject: [PATCH] * src/sort.c: Avoid O(N**2) behavior when there are many temporary files. Fix a race condition. --- ChangeLog | 24 +++++++++++++++++++++++- 1 file changed, 23 insertions(+), 1 deletion(-) diff --git a/ChangeLog b/ChangeLog index fb6522edb6..bca8e7880e 100644 --- a/ChangeLog +++ b/ChangeLog @@ -2,7 +2,29 @@ * Version 5.3.0. - * NEWS: Document the following change. + * NEWS: Document the following changes. + + * src/sort.c: 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/pr.c (strtoumax): Declare if not declared. (skip_to_page, first_page_number, last_page_number, page_number, first_last_page, print_header): -- 2.47.2