When a C program runs, it usually receives any command-line arguments through
argc (argument count) and
argv (argument vector). It is up
to the program to interpret the contents of this array of strings.
There are many ways to do this, one of the simpler solutions is the getopt
function (in the following, getopt will refer to both getopt and getopt_long).
One extension some getopt implementations offer, is that they reorder the
argv as they process it, resulting in an array where all the
options appear first followed by the nonoptions.
This reordering partitions the array. And we want a stable partition, so the relative order of all the options, and of all the nonoptions is the same.
Last year I released parg, a simple parser for
argv that works similarly
to getopt. It has a separate function,
parg_reorder(), that performs this
reordering. I used a simple algorithm for this – allocate a temporary array
the size of
argv, parse the arguments, and fill in the options from the start
and nonoptions from the end of the new array. Then copy them back, reversing
the nonoptions to their original order in the process. In hindsight, I could
have moved the options into their final place in
argv right away.
This runs in time, but also requires additional space. The space requirement could be a problem (for instance on embedded systems), so let’s see if we can do better.
The code examples in the following are pseudo-code, and glance over some details. Please see the examples on GitHub for working C++ code.
We note that if we already partitioned the two halves of an array, , we can compute the partition of both by swapping and . Swapping adjacent blocks in an array is sometimes called rotating, and can be done in linear time, for instance using reversal (observing that ).
So we can use divide and conquer. With a recursive function that splits the array at the middle, this runs in time and requires stack space.
Much better, but ideally we would like to use only constant extra space. To achieve this, we can use the same technique as in bottom-up merge sort. We first process the array in blocks of size 2, then again in blocks of size 4 (whose two halves of size 2 are already partitioned), and so on, until we process the entire array as one block.
This runs in time and uses constant extra space.
In a sense, the price we pay to avoid the recursion is that we do not remember the partition points of the two halves, and need to find them again. This means we use the predicate times instead of .
However, since the two halves are already partitioned, we can use binary search to find the partition points. This reduces the number of predicate applications to (since ), which means we have the same time complexities as the recursive algorithm, but using only constant extra space.
If the array is almost partitioned, these algorithms still go through every step. We can do something similar to natural merge sort, and repeatedly look for the next place where a rotate is needed, stopping if we find none. We must be careful though, if we simply look for areas and rotate them, we get quadratic time on alternating patterns. Instead we can look for and rotate the middle two, just like above.
At best this runs in , while the worst-case complexity is the same as the bottom-up version. Since the widths are no longer fixed size, we have to perform a linear search for the partition points, so the number of predicate applications is back to . Also, we have to use the predicate to find the middle and next starting point, so we may use more predicate applications than the bottom-up version.
There is an algorithm that can perform stable partitioning in using constant extra space (PDF), but it is somewhat more involved, and not practical given the constraints of the specific task.
Let us return to the problem of reordering arguments. One issue here is that we cannot tell if any given element is an option, an option argument, or a nonoption, without parsing the entire array up to that point (i.e. we cannot assume random access).
This is because any given element could be preceded by an option that uses it
as its option argument (looking at the previous element is not enough, since
that might be an option argument instead of an option). Or there could be a
-- somewhere, which means the remaining elements are nonoptions (unless that
-- is in fact the option argument of a preceding option).
This makes the natural algorithm a good fit, since it applies the predicate linearly from left to right in each loop.
So how does this all compare to getopt implementations? The two I checked perform the reordering in each call by scanning over any nonoptions from the current position, and then rotating them to the end of the array. This effectively builds the array of nonoptions at the end, while moving down the part that has not yet been processed.
This requires constant extra space, but takes worst-case time.
While this could theoretically be used in an algorithmic complexity attack,
most systems limit the size of the command-line arguments in some way. As an
example of the worst-case behavior, the following line runs
ls with 200,000
nonoptions (redirecting the error messages for missing file), and takes about
0.3 seconds (Fedora 24 running in a VM):
Whereas this line runs
ls with the same number of arguments, but alternating
nonoptions and options (the
-a option enables showing files that start with
a period, and has no effect in this case), and takes 11 seconds: