Malcolm said:
John Bode said:
Didn't you just say that evidence isn't proof?
This is priceless. The bug had dick all to do with the preincrement
operator; like Michael pointed out, the same UB would have shown up if
I hadn't used the preincrement. The root cause of the bug is that C
arrays are 0-origin (and that I wasn't paying close enough attention).
Here's the code
added by Malcolm
int stack[STACK_SIZE];
int sp;
if (sp < STACK_SIZE)
{
/*
** The following statement replaces these two statements
**
** sp = sp + 1;
** stack[sp] = value;
*/
stack[++sp] = value;
}
else
{
/* handle overflow */
}
Seems to me quite clearly that the pre-increment is contributing to the
problem.
What if I had written
if (sp < STACK_SIZE)
{
sp = sp + 1;
stack[sp] = value;
}
The pre-increment operator is nowhere in sight, yet the bug is still
there. It seems to me that the problem is in the test (actually, the
problem's in the overall logic; more on that below).
On entry, sp < STACK_SIZE, so writing "stack[sp++] = value;" would
give you the right behaviour, at the price of making sp no longer pointing
to stack top but to the empty space above it.
Which is not what I want sp to do. I want sp to point to the last
thing pushed onto the stack, not the next available slot.
Actually, now that I've thought about it, the *right* solution is to
grow from the top down:
static int sp = STACK_SIZE;
void push (int value)
{
if (sp > 0)
stack[--sp] = value;
else
/* overflow */
}
int pop (void)
{
if (sp < STACK_SIZE)
return stack[sp++];
else
/* underflow */
}
A little cleaner, and all array elements actually get used. Like I
said, I tossed off the original example while waiting for something
else to finish and didn't verify it properly. Bad me. No cookie.
However we all make mistakes, so to conclude that pre-increment is confusing
on the basis of one bug is a bit premature. To conclude that it is not
confusing (evidence isn't proof, therefore evidence that falls short of
proof is evidence against) is a fallacy.
You're in good company here. No less than the authors of "Numerical Recipies
in C" endorse 1-based arrays. Mathematicians count 1, 2, 3 ..., computers
count 0, 1, 2 ... . However the consensus is that 1-based arrays in C are a
bad idea.
I don't *endorse* the idea of 1-based arrays in C. I was merely
pointing out that the bug in my code was due to not taking 0-origin
arrays into account, not because I used a preincrement operator.
Since the bug still exists if I replace the preincrement with a
separate increment statement, I'd say my point is valid.
And my *actual* point was that the physical and logical
representations of a stack didn't have to map exactly.