[tz] [PROPOSED 7/7] Improve zic -v performance on links to links
Paul Eggert
eggert at cs.ucla.edu
Thu Oct 20 19:44:06 UTC 2022
* zic.c (qsort_linkcmp, bsearch_linkcmp): New functions.
(main): Use these functions so that the cost of checking for links
to links is O(N log N), not O(N**2).
---
zic.c | 41 +++++++++++++++++++++++++++++++++--------
1 file changed, 33 insertions(+), 8 deletions(-)
diff --git a/zic.c b/zic.c
index 59fd4e4..82e1a4d 100644
--- a/zic.c
+++ b/zic.c
@@ -651,6 +651,33 @@ change_directory(char const *dir)
}
}
+/* Compare the two links A and B, for a stable sort by link name. */
+static int
+qsort_linkcmp(void const *a, void const *b)
+{
+ struct link const *l = a;
+ struct link const *m = b;
+ int cmp = strcmp(l->l_linkname, m->l_linkname);
+ if (cmp)
+ return cmp;
+
+ /* The link names are the same. Make the sort stable by comparing
+ file numbers (where subtraction cannot overflow) and possibly
+ line numbers (where it can). */
+ cmp = l->l_filenum - m->l_filenum;
+ if (cmp)
+ return cmp;
+ return (l->l_linenum > m->l_linenum) - (l->l_linenum < m->l_linenum);
+}
+
+/* Compare the string KEY to the link B, for bsearch. */
+static int
+bsearch_linkcmp(void const *key, void const *b)
+{
+ struct link const *m = b;
+ return strcmp(key, m->l_linkname);
+}
+
/* Simple signal handling: just set a flag that is checked
periodically outside critical sections. To set up the handler,
prefer sigaction if available to close a signal race. */
@@ -968,17 +995,15 @@ _("%s: invalid time range: %s\n"),
/*
** Make links.
*/
+ if (noise)
+ qsort(links, nlinks, sizeof *links, qsort_linkcmp);
for (i = 0; i < nlinks; ++i) {
eat(links[i].l_filenum, links[i].l_linenum);
dolink(links[i].l_target, links[i].l_linkname, false);
- if (noise)
- for (j = 0; j < nlinks; ++j)
- if (strcmp(links[i].l_linkname,
- links[j].l_target) == 0) {
- eat(links[j].l_filename,
- links[j].l_linenum);
- warning(_("link to link"));
- }
+ if (noise
+ && bsearch(links[i].l_target, links, nlinks, sizeof *links,
+ bsearch_linkcmp))
+ warning(_("link to link"));
}
if (lcltime != NULL) {
eat(COMMAND_LINE_FILENUM, 1);
--
2.37.3
More information about the tz
mailing list