The countdown for the New Year is near to its end, so I want to take this opportunity to discuss how to implement loops that count down from an upper boundary to a lower boundary. I know it sounds mundane, but I will present a technique that is — at least in my experience — not widely known, not even amongst seasoned C coders (with the notable exception of Chuck Norris, of course).
But first, please take a moment to look at the following routine that employs a countdown for-loop and decide if it works correctly or not:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
/* Return the highest index of given character in array. Search from upper (exclusive) to lower (inclusive) index. If character is not found, return upper index. */ size_t rfind(const char* array, size_t lower, size_t upper, char c) { size_t i; for (i = upper - 1; i >= lower; --i) { if (array[i] == c) { return i; } } return upper; } |
This code appears to be fine, but it has a flaw that shows only when the ‘lower’ index is 0: ‘size_t’ is an unsigned type, and when ‘i’ becomes 0, subtracting 1 yields a very large positive number (due to integer wrap-around) which in turn causes an out-of-bounds access to the given ‘array’. So what do we need to change such that the code works as expected, even for a lower bound of 0?
Most developer’s knee-jerk reaction is to change the type of the indices to a signed type, like ‘int’, but this is unfortunate, as it limits (at least halves) the available value range. As often in life, the proper solution is not to fight the enemy but to turn him into a friend: Let’s use unsigned wrap-around to our advantage:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
size_t rfind(const char* array, size_t lower, size_t upper, char c) { size_t i; for (i = upper - 1; i != lower - 1; --i) { if (array[i] == c) { return i; } } return upper; } |
Instead of using the greater-than operator, we now use the not-equals operator and instead of comparing against ‘lower’ we now compare against one less than ‘lower’. If ‘lower’ happens to be 0, ‘lower’ – 1 (again, due to integer wrap-around) will yield the maximum possible value representable by type ‘size_t’. The same will happen to the loop counter ‘i’ when it has a value of 0 and is decremented once more. As a consequence, the expression ‘i != lower – 1’ becomes false and the loop terminates — as desired.
A Happy New Year to all of my faithful readers!