[patch] Remove a linear search in a double-colon rule.

[Kazu Hirata]

Hi,

Attached is a patch to remove a linear search in a double-colon rule.

OK?

p.s.
CodeSourcery has a blanket copyright assignment with FSF.

Kazu Hirata

2008-01-05  Paul Brook  <address@hidden>

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

Index: remake.c
===================================================================
--- remake.c    (revision 187684)
+++ remake.c    (revision 187685)
@@ -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)