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 <[EMAIL PROTECTED]>
* 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)
_______________________________________________
Bug-make mailing list
Bug-make@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-make
