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.
_______________________________________________ Toybox mailing list Toybox@lists.landley.net http://lists.landley.net/listinfo.cgi/toybox-landley.net