[tz] [PROPOSED 7/7] Improve zic -v performance on links to links

[Paul Eggert]

* 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