Columns

Questions & Answers

Getting Rid of goto

Pete Becker

Pete Becker is Senior QA Project Manager for C++ at Borland International. He has been involved with C++ as a developer and manager at Borland for the past six years, and is Borland's principal representative to the ANSI/ISO C++ standardization committee.

Q

How do I get rid of the goto in this code?

int i, j;
for( i = 0; i < 10; i++ )
    for( j = 0; j < 10; j++ )
        {
        do_something (i,j);
        if( test() )
            goto done;
        do_something_else();
        }
done:
    ;
A

Many people ask questions like this when they are learning about structured programming. What they often miss is that avoiding goto is not an end in itself — it is a means to an end. Programmers must work hard at making their code clear and concise. In most cases, using goto is a shortcut used to avoid thinking about a problem more deeply. However, if you have done the work of thinking about the alternatives to goto and concluded that goto is the best way to express what the code is doing, don't be afraid to use goto.

Here's a first pass at rewriting the code without a goto:

int i,j;
for( i = 0; i < 10; i++ )
    for( j = 0; j < 10; j++ )
         {
         do_something ( i, j );
         if( test() )
             {
             i = 10;
             j = 10;
             }
         else
            do_something_else( );
         }
By setting the loop indices to their maximum values we force both loops to terminate. Of course, if the original code relied on the indices maintaining their values when the inner loop terminated, it would no longer work. Further, it's not particularly clear from a glance at the code that setting these values is supposed to terminate the loop. That's probably the reason that the gurus of structured programming do not permit loop control variables to be reset by the code in the loop. It obscures the control logic.

Another way to avoid this goto would be to rewrite the code with an explicit variable to control termination. Like this:

int i, j, done = 0;
for( i = 0; i < 10 && !done; i++ )
    for( j = 0; j < 10 && !done; j++ )
         {
         do_something (i,j);
         if( test() )
             done = 1;
         else
             do_something_else( );
         }
This code doesn't look too bad, and I wouldn't get too upset if someone submitted it in a project that I was in charge of. As a general style of programming, however, it has some problems that may not be obvious. In particular, if the outer loop does some further processing after running the inner loop, the code becomes a bit more complex:

int i, j, done = 0;
for( i = 0; i < 10 && !done; i++ )
    {
    for( j = 0; j < 10 && !done; j++ )
        {
        do_something (i,j);
        if( test() )
            done = 1;
        else
            do_something_else();
        }
    if( !done )
        do_further_processing();
    }
The additional if statement above serves the same role as the second branch of the if statement in the inner loop: it makes sure we don't do any unnecessary processing when we are abnormally exiting from these loops. That is, we are making the same decision in two different places. Furthermore, we now have four function calls wrapped inside four control constructs, and the logic of the program is nowhere near as clear as it was in the original version.

Another approach to all this is to put the inner loop in a function of its own, and simply call that function repeatedly from the outer loop. Then the code looks like this:

int inner_loop( int i )
{
int j;
for( j = 0; j < 10; j++ )
    {
    do_something(i,j);
    if( test() )
        return 1;
    do_something_else();
    }
return 0;
}
int done = 0;
for( i = 0; i < 10 && !done; i++ )
    {
    done = inner_loop(i);
    if( !done )
        do_further_processing( );
    }
This is more clear, in large part because we have removed the nested loop. By putting it into a separate function we have increased the total amount of code that must be read for comprehension, but we have reduced the complexity of the individual pieces, making it easier to read overall. A potentially significant drawback of this approach is that by moving the inner loop out into a separate function we lose access to other variables that were available when it was directly nested in the outer loop. That's why we have to pass i as an argument to the function. If there are more values needed inside the inner loop they all must be passed as arguments in the function call, and the call quickly becomes unwieldy. In such a case we're probably better off keeping the inner loop directly nested in the outer loop, and choosing one of the other ways we've seen to provide clear, readable code.

On the other hand, all these control constructs may well be necessary in a somewhat different case. Suppose that the outer loop contained some startup code and some cleanup code that had to be executed around each execution of the inner loop. In that case, it's much easier to write a solution using flags than the comparable code using a goto:

int done = 0;
for( i = 0; i < 10 && !done; i++ )
    {
    setup();
    for( j = 0; j < 10 && !done; j++ )
        {
        do_something();
        if( test() )
            done = 1;
        else
            do_something_else();
        }
    if( !done )
        do_further_processing();
    cleanup();
    }
I wouldn't want to try to write this code with a goto. That is, not unless I was programming in C++, where this sort of thing is easy. All we need to do is create an object whose constructor takes care of setting up the loop and whose destructor takes care of the cleanup:

struct LoopHelper
{
LoopHelper() { setup(); }
~LoopHelper() { cleanup(); }
};

for( i = 0; i < 10; i++ )
    {
    LoopHelper helper;
    for( j = 0; j < 10; j++ )
         {
         do_something (i,j);
         if( test() )
             goto done;
         do_something_else();
         }
    do_further_processing();
    }
done:
    ;
Now every time we execute the body of the outer loop the constructor for LoopHelper will call setup at the beginning of the loop and the destructor will call cleanup at the end of the loop. In addition, if we exit the loop through the goto statement, the destructor for LoopHelper will be executed before leaving the block. This guarantees that cleanup will be called for every execution path that terminates the inner loop. This is a significant benefit that C++ provides over C: by guaranteeing destruction of objects on exit from the block in which they are created, C++ lets us write safer code without having to use as many explicit control structures.

Personally, I think the first form of this code is the cleanest. If I needed to ensure cleanup on exit from the inner loop I'd probably use the last version. Ultimately this is a judgment you must make for yourself, based on the maintainability and the performance requirements that you must satisfy. There's no magic formula you can apply in designing control structures. Sometimes a goto is the right way to do things, although usually it is not. Avoiding goto is a good guideline, but it is only a guideline. In order to apply a guideline sensibly you must understand what the guideline is trying to accomplish. That will help you decide when to ignore it.

Q

I enjoy both your comp.lang.c++ postings and Q&A. I think September's Q&A has one of your rare mistakes:

srand(time(NULL));
time returns time_t, an arithmetic but perhaps not integral type. If time_t is a floating type, the conversion to srand's unsigned int argument could invoke undefined behavior.

—Jim Stern

A

You are absolutely right: you caught me in a moment of carelessness. This code is not portable; although it works correctly with many compilers, the C language definition does not guarantee that it will work. If you understand what the problems are with this code, you have a good grasp of implicit conversions in C.

The problem arises because the time function returns a time_t. This is an implementation-defined type that is used to represent times within a C program. The language definition says that time_t must be an integral type or a floating-point type. In particular, a conforming C implementation could define time_t this way:

typedef double time_t;
I don't know of any implementations that actually do this, but the fact that the language definition allows it strongly suggests that at the time that the language definition was written there was at least one compiler that defined time_t as a floating-point type.

If your compiler uses a floating-point type you won't run into problems using that type with the time functions. In fact, that's exactly the reason that the various C functions that deal with time use time_t: you can write code that is independent of the details of your compiler's representation of time. You only run into problems when you use objects of type time_t in ways that are not explicitly provided in the language definition. Unfortunately, that's what my code does. srand takes an argument of type unsigned, so the compiler must convert the value returned by time, which is of type time_t, to an unsigned value. When time_t is an integral type this conversion is well-defined, and the code works reliably. When time_t is a floating-point type things get a little more complicated.

The complications arise because floating-point types can usually represent many more values than integral types can. When you convert a floating-point value to an integral value you almost always lose information. The most obvious aspect of this loss is that integral types cannot represent the fractional part of a floating point value, so you lose the information that appears to the right of the decimal point. For this case the rule in C is simple: the fractional part is dropped, and the remaining integral part is assigned to the integral value. So 1.1, when converted to an integral type, becomes 1. No problem.

There are, however, floating-point conversions that cause problems. A floating-point value can be much larger than any integral value that the system can handle. For example, 1e60 requires about 200 bits in a binary representation. I've heard of systems that support 128-bit values, but even those are not adequate to handle a straight binary representation of 1e60.

There are several ways that the language definition could have been written to deal with this problem. The one chosen was to make the effect of such a conversion undefined. What that means is that the language definition puts no constraints whatsoever on what a conforming compiler can do when you try to convert a floating-point value to an integral type that is too small to hold the result, and that a conforming compiler doesn't have to tell you that your code has something wrong with it. The compiler is free to generate code that fails without telling you that that is what it has done.

That's not as unreasonable as it may at first sound. After all, if you deliberately assigned a floating-point value to an integer variable, you probably knew that the conversion made sense. Requiring an implementation to check the result and handle it differently if the result is out of range would make the cases that work run slower. In the spirit of C, the compiler is not required to do this. You are permitted to write code that might not make sense. It's up to you to figure out whether it will actually do the right thing.

So how can we check whether converting a floating-point type to an integral type makes sense? It's actually easy: just compare the floating-point value to the largest and smallest values that can be represented by the type that you are converting to. These values are available in limits.h. To convert a floating-point value to an unsigned value safely, do something like this:

#include <limits.h>

unsigned safe_convert( double d )
{
if( d > UINT_MAX )
    return UINT_MAX;
else if( d < 0 )
    return 0;
else
    return d;
}
In real code you'd have to be a bit more careful about how you deal with negative values. As written, this function returns 0 in far too many cases.

Using this function, we can now write a safe but slow invocation of srand:

srand( safe_convert( time(NULL)));
The compiler will convert the result returned by time to a double, pass that value to safe_convert, and pass the resulting unsigned integer to srand. That's a lot of work to go through just to seed a random number generator, but if you are interested in writing completely portable code, it's what you need to do. Personally, I'd be tempted to skip it. I know which systems my code is likely to be ported to in the foreseeable future, and none of them uses floating-point values to hold times. We must make such decisions with portability in mind, however, as there is always a danger that someone will do something unexpected, and change our favorite compiler to return time values as doubles. If they did this, I'd have nobody to blame but myself when my programs started to fail mysteriously.

To ask Pete a question about C or C++, send e-mail to pbecker@wpo.borland.com, use subject line: Questions and Answers, or write to Pete Becker, C/C++ Users Journal, 1601 W. 23rd St., Ste. 200, Lawrence, KS 66046.