<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>