[Toybox] [PATCH] cut: simplify by replacing slist.

[Daniel K. Levy]

After looking at it more, I decided the slist linked list is too
complicated. It requires the pfield allocation and free every line, and
associated logic, just to keep track of what fields had already been
visited.

I changed things to keep the list of intervals in toybuf, and to clean
up the list so we don't have to keep track of fields already visited.

I also rewrote the do_*cut functions. They're much simpler now, and I
think easier to understand.

As a bonus, there's less heap usage and churn, an array has better
locality of reference than a linked list, and the O(n^2) insertion sort
of the list parsing has turned into (presumably) O(n log n) of qsort.

Note that holding the list in toybuf does limit the number of intervals
to 512 -- 4096/(2*sizeof(int)). If this is a problem, it's a
straightforward change to count commas and malloc exactly how much
space we'd need.

This passes all tests in the suite. I'm not 100% confident I didn't
miss an off-by-one or boundary condition somewhere, because the tests
aren't very thorough.

I figured it's a significant enough change to add my name to the
copyright. If you disagree, just remove it.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-cut-simplify-by-replacing-slist.patch
Type: text/x-patch
Size: 7797 bytes
Desc: not available
URL: <http://lists.landley.net/pipermail/toybox-landley.net/attachments/20170217/193f0516/attachment-0003.bin>