@@ -678,6 +678,89 @@ bsearch_linkcmp(void const *key, void const *b)
678 678
return strcmp(key, m->l_linkname);
679 679
}
680 680 681 +
/* Make the links specified by the Link lines. */
682 +
static void
683 +
make_links(void)
684 +
{
685 +
ptrdiff_t i, j, nalinks;
686 +
qsort(links, nlinks, sizeof *links, qsort_linkcmp);
687 + 688 +
/* Ignore each link superseded by a later link with the same name. */
689 +
j = 0;
690 +
for (i = 0; i < nlinks; i++) {
691 +
while (i + 1 < nlinks
692 +
&& strcmp(links[i].l_linkname, links[i + 1].l_linkname) == 0)
693 +
i++;
694 +
links[j++] = links[i];
695 +
}
696 +
nlinks = j;
697 + 698 +
/* Walk through the link array making links. However,
699 +
if a link's target has not been made yet, append a copy to the
700 +
end of the array. The end of the array will gradually fill
701 +
up with a small sorted subsequence of not-yet-made links.
702 +
nalinks counts all the links in the array, including copies.
703 +
When we reach the copied subsequence, it may still contain
704 +
a link to a not-yet-made link, so the process repeats.
705 +
At any given point in time, the link array consists of the
706 +
following subregions, where 0 <= i <= j <= nalinks and
707 +
0 <= nlinks <= nalinks:
708 + 709 +
0 .. (i - 1):
710 +
links that either have been made, or have been copied to a
711 +
later point point in the array (this later point can be in
712 +
any of the three subregions)
713 +
i .. (j - 1):
714 +
not-yet-made links for this pass
715 +
j .. (nalinks - 1):
716 +
not-yet-made links that this pass has skipped because
717 +
they were links to not-yet-made links
718 + 719 +
The first subregion might not be sorted if nlinks < i;
720 +
the other two subregions are sorted. This algorithm does
721 +
not alter entries 0 .. (nlinks - 1), which remain sorted.
722 + 723 +
If there are L links, this algorithm is O(C*L*log(L)) where
724 +
C is the length of the longest link chain. Usually C is
725 +
short (e.g., 3) though its worst-case value is L. */
726 + 727 +
j = nalinks = nlinks;
728 + 729 +
for (i = 0; i < nalinks; i++) {
730 +
struct link *l;
731 + 732 +
eat(links[i].l_filenum, links[i].l_linenum);
733 + 734 +
/* If this pass examined all its links, start the next pass. */
735 +
if (i == j)
736 +
j = nalinks;
737 + 738 +
/* Make this link unless its target has not been made yet. */
739 +
l = bsearch(links[i].l_target, &links[i + 1], j - (i + 1),
740 +
sizeof *links, bsearch_linkcmp);
741 +
if (!l)
742 +
l = bsearch(links[i].l_target, &links[j], nalinks - j,
743 +
sizeof *links, bsearch_linkcmp);
744 +
if (!l)
745 +
dolink(links[i].l_target, links[i].l_linkname, false);
746 +
else {
747 +
/* The link target has not been made yet; copy the link to the end. */
748 +
links = growalloc (links, sizeof *links, nalinks, &nlinks_alloc);
749 +
links[nalinks++] = links[i];
750 +
}
751 + 752 +
if (noise && i < nlinks) {
753 +
if (l)
754 +
warning(_("link %s targeting link %s mishandled by pre-2023 zic"),
755 +
links[i].l_linkname, links[i].l_target);
756 +
else if (bsearch(links[i].l_target, links, nlinks, sizeof *links,
757 +
bsearch_linkcmp))
758 +
warning(_("link %s targeting link %s"),
759 +
links[i].l_linkname, links[i].l_target);
760 +
}
761 +
}
762 +
}
763 + 681 764
/* Simple signal handling: just set a flag that is checked
682 765
periodically outside critical sections. To set up the handler,
683 766
prefer sigaction if available to close a signal race. */
@@ -992,19 +1075,7 @@ _("%s: invalid time range: %s\n"),
992 1075
continue;
993 1076
outzone(&zones[i], j - i);
994 1077
}
995 -
/*
996 -
** Make links.
997 -
*/
998 -
if (noise)
999 -
qsort(links, nlinks, sizeof *links, qsort_linkcmp);
1000 -
for (i = 0; i < nlinks; ++i) {
1001 -
eat(links[i].l_filenum, links[i].l_linenum);
1002 -
dolink(links[i].l_target, links[i].l_linkname, false);
1003 -
if (noise
1004 -
&& bsearch(links[i].l_target, links, nlinks, sizeof *links,
1005 -
bsearch_linkcmp))
1006 -
warning(_("link to link"));
1007 -
}
1078 +
make_links();
1008 1079
if (lcltime != NULL) {
1009 1080
eat(COMMAND_LINE_FILENUM, 1);
1010 1081
dolink(lcltime, tzdefault, true);
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4