Subject: Re: I can't count, can someone help me with this?
From: Peter Seebach <email@example.com>
Date: 03/01/2003 19:28:00
In message <200303020016.h220GgY01051@guild.plethora.net>, Peter Seebach writes
>Okay. I call dibs! Unless someone else REALLY wants to fix this, I want to
>see if I can have a go at it. I just spent two hours working with my wife
>on plotting a novel involving time travel, and I am desparate for something
>to think about that's a little easier to sink my teeth into.
Boy, this is tricky. I think I found it, but I'm not sure what it *should* be
Here's the basic idea: When a numeric sort is being done, what sort does
is build a little buffer whose values express, as compactly as possible,
the numeric value of a field. This is then stored in something called
"keybuf", and the line is concatenated to it. So, for instance, the value
"-5" is converted into
Thus, when we call libc's radix sort, we figure that the first keys will
solve all our problems.
In fields.c, starting on line 129, we have:
* Make [s]radixsort() only sort by relevant part of key if:
* 1. we want to choose unique items by relevant field[s]
* 2. we want stable sort and so the items should be sorted only by
* the relevant field[s]
if (UNIQUE || (stable_sort && keybuf->offset < line->size))
keypos[-1] = REC_D;
Now, "keybuf->offset" is "the number of bytes long our initial key is".
What we then do is shove a record delimiter into the first position of keybuf.
What's happening is, for 0, the "key" is just \x80. So, "line" is "0\n" (size
2), and "keybuf->offset" is 1... so we smash the \x80, which would have
worked, and replace it with \n, which doesn't.
It looks to me like this logic would be correct in the case where we're
building up a series of *non-numeric* fields - but it's clearly wrong with
The trick is presumably that radixsort and sradixsort both support an optional
"endbyte" which is a magic cookie which tells radixsort to ignore everything
past a certain point.
So... It looks to me like it *might* be correct to just replace the smashing
of the last byte of the "key" with
*keypos++ = REC_D;
This means we need to update keybuf->length. One of the CVS logs suggests
this is a culprit:
date: 2001/02/19 19:41:31; author: jdolecek; state: Exp; lines: +9 -8
* move the test for keybuf size before keypos[-1] assignment, "just in case"
* move the keypos assignment to improve readability
Sure enough, changing this fixes the problem.
I am *SO* not convinced this is the right solution, but I'm send-pr'ing it
Those who are more clear on how sort(1) works may wish to have a look at
what has become pr #bin/20542.