[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[patch] Remove a linear search in a double-colon rule.
From: |
Kazu Hirata |
Subject: |
[patch] Remove a linear search in a double-colon rule. |
Date: |
Sat, 5 Jan 2008 18:59:01 -0800 (PST) |
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)
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [patch] Remove a linear search in a double-colon rule.,
Kazu Hirata <=