Fix O(n^2) algorithm for double colon rules.

[Paul Brook]

The fix for bug #14334 introduced O(n^2) time behavior for double colon rules.

Specifically remake.c:notice_finished_file does a linear search to determine 
whether all double colon rules for the current file have been updated yet.

This can be safely short-circuited by checking if the next file has been 
updated. Under normal circumstances we process double colon rules in order, 
so O(n^2) worst-case behaviour is reduced to O(n) in practice.

In a project with ~100k double colon rules this cuts make overhead from 
several minutes to a few seconds.

Paul

2007-11-20  Paul Brook  <address@hidden>

        * remake.c (notice_finished_file): Avoid O(N) search in common case.

Index: remake.c
===================================================================
--- remake.c    (revision 187570)
+++ remake.c    (working copy)
@@ -887,15 +887,21 @@ notice_finished_file (struct file *file)
 
       /* Check that all rules were updated and at the same time find
          the max timestamp.  We assume UNKNOWN_MTIME is newer then
-         any other value.  */
-      for (f = file->double_colon; f != 0 && f->updated; f = f->prev)
-        if (max_mtime != UNKNOWN_MTIME
-            && (f->last_mtime == UNKNOWN_MTIME || f->last_mtime > max_mtime))
-          max_mtime = f->last_mtime;
-
-      if (f == 0)
-        for (f = file->double_colon; f != 0; f = f->prev)
-          f->last_mtime = max_mtime;
+         any other value.  Avoid doing a full linear search in the common
+        case that we are updating the rules in order, and file->prev has
+        not been updated yet.*/
+      if (!file->prev || file->prev->updated)
+       {
+         for (f = file->double_colon; f != 0 && f->updated; f = f->prev)
+           if (max_mtime != UNKNOWN_MTIME
+               && (f->last_mtime == UNKNOWN_MTIME
+                   || f->last_mtime > max_mtime))
+             max_mtime = f->last_mtime;
+
+         if (f == 0)
+           for (f = file->double_colon; f != 0; f = f->prev)
+             f->last_mtime = max_mtime;
+       }
     }
 
   if (ran && file->update_status != -1)