There’s a “smart” shortcut one can take when writing a comparison function (such as for qsort or an RB tree): return the difference between two numbers. Unfortunately, it’s not very smart.

int
compar(int x, int y)
{
        return x - y;
}

Consider x = 4 and y = 6. This does indeed return a negative number (-2), to indicate that x is less than y. If x = 5 and y = -3, then it returns 8 (positive). Two test cases, all passing. Mark it done.

But wait. What if x = 1987654321 and y = -1987654321? Then the difference between them is -319658654 (negative) which proves that x is less than y. That’s less than correct. (Never mind the undefinedness of sign overflow; unsigned won’t save you here.)

Unfortunately, this idiom keeps coming back, probably because some people cheat when writing examples and then other people cheat and copy example code without thinking. Long ago, I fixed one example in the tree man page. A Google search reveals that the practice is both common and widely known to be dangerous.

Even so, it continues to happen even in production code. I noticed in passing this problem existed in nsd. Coincidentally, otto just spent a few days pulling his hair out because nsd was spinning in an infinite loop because a corrupted tree contained a loop, only to find the broken comparison was precisely the problem.

Moral: Don’t do subtraction instead of comparison, even if they tell you “look how cool this is” at school!