Embedded in Academia

Iterating Over The Full Range

Every couple of months I need to write code that runs for every value of, for example, a char. This is usually to exhaustively test something so the code should be fast, so I write it in C. At first I always want to write:

for (c = CHAR_MIN; c <= CHAR_MAX; c++) {
  use (c);
}

This is very wrong when c has type “char.” Declaring c as “int” is one solution, and here’s another:

c = CHAR_MIN;
do {
  use (c);
} while (c++ != CHAR_MAX);

There is no signed overflow because the char is promoted to int before being incremented. However, neither solution can iterate over all values of an int. It would be possible to cast to unsigned before incrementing (ugly) or use a larger type than int (not supported by all compilers, and not fast on some platforms). Thus I usually end up with something like this:

i = INT_MIN;
while (1) {
  use (i);
  if (i == INT_MAX) break;
  i++;
}

But this is super clunky. Anyone have a better idiom for this case?

regehr

34 responses to “Iterating Over The Full Range”

  1. This is similar to what I do, but not quite the same. I don’t think mine is any less clunky, but it does eliminate a comparison each time through the loop:

    for (i = INT_MIN; i < INT_MAX; i++)
    {
    use (i);
    }
    use (i); // Here i is INT_MAX

  3. Would this not accomplish the task?

    i = INT_MAX;
    do {
    use (i);
    } while(i– > INT_MIN);

  4. Hi Yan, your code stops at zero instead of going down to INT_MIN. Also, for various reasons I usually prefer to go from min to max.

  5. Sorry, I’ve since submitted a correction to compare against INT_MIN (guess it was removed), but I find it easier to reason about completeness when it’s decrementing, can’t really explain why.

  7. I love the final version. It reminds me of Forth’s BEGIN-WHILE-REPEAT structure, that you would use like (untested):

    INT_MIN DO DUP USE DUP INT_MAX WHILE 1+ REPEAT DROP

  9. comma operator to the rescue?

    c = CHAR_MIN;
    do {
    use (c);
    } while (c != CHAR_MAX && (c++, 1));

  11. Dan and BCS I think your solutions are roughly in the same equivalence class as my third solution — perfectly reasonable, but not especially pleasing. Somehow I failed to think of either of these. Thanks!

  12. If you don’t like the looks of mine (but don’t mind the form) you can hide it in a macro.

    #define IncUpTo(var, limit) ((var) != limit && ((var++), a))
    …
    do {} while(IncUpTo(c, CHAR_MAX))

  13. Sometime early on, all good programmers internalize the avoidance of while loops with counters in favor of for loops (or analogues, such as foreach loops in many languages). It takes time to learn that some “iterating while loops” are actually correct, readable, and concise.

    Your “super clunky” while loop is one of these. Don’t fret over changing it.

  19. I agree with Roger Pate. In fact, whenever I find myself struggling with a for-loop and can’t get it to look elegant and concise, I’ve usually forgotten to consider loop-with-test-in-the-middle, i.e. while (true) { … if (c) break; … } Just because most C-like languages have no explicit construct for this doesn’t mean the construct itself is any less useful. I would immediately recognize what you’re doing here, and so would most experienced programmers, I’d wager.

    It’s true that for an enumeration a “for” would look better, but C has no idiom for reliably ranging over all values in a domain (and you really need a separate one if you’re not even allowed to mention invalid values), so you take what you can get.

  20. Roger and Jeroen, that is an interesting reaction.

    I’ve noticed myself writing a lot more “while (1) … break/continue” loops during the last 5 years or so. I had been a tiny bit (privately) embarrassed by this code, but maybe I shouldn’t be.

    I had been guessing that these loops came from looking at so much assembly language and that I was actually regressing farther and farther away from some Haskell-like perfect programming world…

  21. 5 years ago I would also have thrown my vote on the while(1) …break wagon. These days I generally write that code as:

    for i in range(INT_MIN, INT_MAX):
    use(i)

    Sure, it’s slower, but that’s a problem that you can address with more work at the platform level. It’s certainly possible to rewire your brain to recognize the more diffuse C loop as elegant, but I don’t find that to be a very satisfying answer.

  25. I’m exposing my ignorance here, but what exactly is wrong with the first solution — too many comparisons?

  27. Thanks! I can’t believe I missed that after staring at it — it looks innocuous though. I guess that’s why it’s always your first solution, because it certainly would have been mine.
    Lesson Learned 🙂

  28. I find a certain appeal in this solution, too:

    for (int i = INT_MIN; use(i), i != INT_MAX; ++i);

    However, it assumes that “use(i)” can be expressed as one expression or a sequence of comma-separated expressions. Is that a reasonable assumption?

  29. large_enough_to_avoid_overflow_t i;

    for(i=CHAR_MIN; i<=CHAR_MAX; i++)
    {
    c = i;
    use(c);
    }

  30. Too be more generic, why not use something similar to

    template
    void UseEveryValue( T const startValue) {
    T i = startValue;
    do {
    Use(i);
    } while( startValue != ++i);
    }

    This should work for both signed and unsigned of ints, shorts, and chars. It also has the advantage of not requiring limits explicitly named.

  31. @Bo Rydberg (30): That definitely doesn’t work. If “T” is “signed int”, then if you initialize “i” to “startValue” and then keep ++’ing it, you’ll only hit values greater than “startValue”. You’ll never get back to “startValue” a second time (unless signed overflow were defined to wrap around modulo 2^32, which it’s not), and so the loop will never terminate.

  32. First, I plead guilty to Roger Pate’s observation that rejecting while loops with counters is knee-jerk reaction, but I’m going to stand by it anyway. Further, I group loops-having-a-test-in-the-middle with gotos, i.e., constructs to be avoided if at all possible.

    I’d love to use Terrence Cole’s suggestion of “for i in renge”, but that’s not a feature available in most languages, and is the effect we’re discussing replicating in other languages.

    Dan Saks’ comment on the limitaion of using the comma operator in the loop exit condition is an overriding concern. If the contents of the loop don’t very easily showhorn into the condition, the code fragment becomes one that hides its meaning.

    Finally, I think that Jeroen Mostert hit the nail on the head when he observed that we’re really exploring iterating over every value of an enum.

    With all of the above considerations, I must stand in favor of Dan’s solution:

    for (i = ENUM_FIRST; i < ENUM_LAST; i++)
    {
    use (i);
    }
    use (i); // Here i is ENUM_LAST

    Which leaves me twitching with unease because i has a scope beyond the loop to which it belongs. Eww…

    Lance ==)—————

  33. Even editing offline can’t save me from myself: “showhorn” should have been “shoehorn”.

    Lance ==)—————

  34. Dan and Lance, the issue of what “use(i)” actually looks like is interesting and I confess that I hadn’t even considered it. I was assuming that use(i) was actually a function call and not just a shorthand for some other code.

    It happens that I seldom use a compiler that lacks a trustworthy inliner, so I tend to put code into new functions whenever this serves software engineering goals. Of course I realize that there exist embedded compilers that cannot be trusted to do this, and so use(i) might be a macro or just a pile of statements.