[Toybox] tsort

[Ray Gardner]

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

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:

--- "..\\1005\\toys\\posix\\tsort.c" 2023-10-05 23:28:19.000000000 -0600
+++ "toys\\posix\\tsort.c" 2023-10-06 10:14:01.448795400 -0600
@@ -43,23 +43,13 @@
 static void do_tsort(int fd, char *name)
 {
   off_t plen = 0;
-  char *ss, **pair, *keep[2];
+  char *ss, **pair, *keep[2], *keepfake[2];
   long count,    // remaining unprocessed pairs
        len,      // total strings in pair list
        out,      // most recently added output (counts down from len)
        otop,     // out at start of this loop over pair[]
        otop2,    // out at start of previous loop over pair[]
        ii, jj, kk;
-  unsigned long sigh;
-
-  // bsearch()'s first argument is the element to search for,
-  // and sbse() compares the second element of each pair, so to find
-  // which FIRST element matches a second element, we need to feed bsearch
-  // keep-1 but the compiler clutches its pearls about this even when
-  // typecast to (void *), so do the usual LP64 trick to MAKE IT SHUT UP.
-  // (The search function adds 1 to each argument so we never access
-  // memory outside the pair.)
-  sigh = ((unsigned long)keep)-sizeof(*keep);

   // Count input entries in data block read from fd
   if (!(ss = readfd(fd, 0, &plen))) return;
@@ -92,8 +82,12 @@
     for (ii = 0; ii<count; ii++) {
       // Find pair that depends on itself or no other pair depends on
first str
       memcpy(keep, pair+2*ii, sizeof(keep));
-      // The compiler won't shut up about keep-1 no matter how we typecast
it.
-      if (keep[0]!=keep[1] && bsearch((void *)sigh, pair, count,
sizeof(keep),
+      // bsearch()'s first argument is the element to search for,
+      // and sbse() compares the second element of each pair, so to find
+      // which FIRST element matches a second element, we need to feed
bsearch
+      // an array with a second element == keep[0].
+      keepfake[1] = keep[0];
+      if (keep[0]!=keep[1] && bsearch(keepfake, pair, count, sizeof(keep),
           (void *)sbse)) continue;

       // Remove from pair list

I think it's clearer, I believe it's a little shorter in code size, and
the run time difference is negligible.

I can post here about how I tested, if you're interested.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.landley.net/pipermail/toybox-landley.net/attachments/20231010/c7e7b615/attachment.htm>