<div dir="ltr">After seeing your comments about tsort in your blog, I thought about trying to implement Knuth's algorithm, but after I saw how far you'd got with your version I decided not to for now. I haven't analyzed your version carefully. It seems to be O(N^2) due to all the work to close up the list with each item removed, on average? Not sure, but it measures roughly O(N^2).<br><br>I looked at the code and also saw in your blog about the problem of creating a pointer to an element "below" the keep[] array. Instead of doing the "usual LP64 trick", had you considered using another array? Something like this:<br><br><div><div><font face="monospace">--- "..\\1005\\toys\\posix\\tsort.c" 2023-10-05 23:28:19.000000000 -0600<br>+++ "toys\\posix\\tsort.c"       2023-10-06 10:14:01.448795400 -0600<br>@@ -43,23 +43,13 @@<br> static void do_tsort(int fd, char *name)<br> {<br>  Â off_t plen = 0;<br>- Â char *ss, **pair, *keep[2];<br>+ Â char *ss, **pair, *keep[2], *keepfake[2];<br>  Â long count, Â  Â // remaining unprocessed pairs<br>  Â  Â  Â  len, Â  Â  Â // total strings in pair list<br>  Â  Â  Â  out, Â  Â  Â // most recently added output (counts down from len)<br>  Â  Â  Â  otop, Â  Â  // out at start of this loop over pair[]<br>  Â  Â  Â  otop2, Â  Â // out at start of previous loop over pair[]<br>  Â  Â  Â  ii, jj, kk;<br>- Â unsigned long sigh;<br>-<br>- Â // bsearch()'s first argument is the element to search for,<br>- Â // and sbse() compares the second element of each pair, so to find<br>- Â // which FIRST element matches a second element, we need to feed bsearch<br>- Â // keep-1 but the compiler clutches its pearls about this even when<br>- Â // typecast to (void *), so do the usual LP64 trick to MAKE IT SHUT UP.<br>- Â // (The search function adds 1 to each argument so we never access<br>- Â // memory outside the pair.)<br>- Â sigh = ((unsigned long)keep)-sizeof(*keep);<br> <br>  Â // Count input entries in data block read from fd<br>  Â if (!(ss = readfd(fd, 0, &plen))) return;<br>@@ -92,8 +82,12 @@<br>  Â  Â for (ii = 0; ii<count; ii++) {<br>  Â  Â  Â // Find pair that depends on itself or no other pair depends on first str<br>  Â  Â  Â memcpy(keep, pair+2*ii, sizeof(keep));<br>- Â  Â  Â // The compiler won't shut up about keep-1 no matter how we typecast it.<br>- Â  Â  Â if (keep[0]!=keep[1] && bsearch((void *)sigh, pair, count, sizeof(keep),<br>+ Â  Â  Â // bsearch()'s first argument is the element to search for,<br>+ Â  Â  Â // and sbse() compares the second element of each pair, so to find<br>+ Â  Â  Â // which FIRST element matches a second element, we need to feed bsearch<br>+ Â  Â  Â // an array with a second element == keep[0].<br>+ Â  Â  Â keepfake[1] = keep[0];<br>+ Â  Â  Â if (keep[0]!=keep[1] && bsearch(keepfake, pair, count, sizeof(keep),<br>  Â  Â  Â  Â  Â (void *)sbse)) continue;<br> <br>  Â  Â  Â // Remove from pair list<br></font></div><div><br></div><div>I think it's clearer, I believe it's a little shorter in code size, and the run time difference is negligible.</div></div><div><br></div><div>I can post here about how I tested, if you're interested.</div></div>