8.2 Selection Statements 359One simple translation of this statement follows:Code to evaluate expression into t
goto branches
label 1 : code for statement 1
goto out
...
labeln: code for statementn
goto out
default: code for statementn+ 1
goto out
branches: if t = constant_expression 1 goto label 1
...
if t = constant_expressionn goto labeln
goto default
out:
The code for the selectable segments precedes the branches so that the targets
of the branches are all known when the branches are generated. An alternative
to these coded conditional branches is to put the case values and labels in a table
and use a linear search with a loop to find the correct label. This requires less
space than the coded conditionals.
The use of conditional branches or a linear search on a table of cases and
labels is a simple but inefficient approach that is acceptable when the number of
cases is small, say less than 10. It takes an average of about half as many tests as
there are cases to find the right one. For the default case to be chosen, all other
cases must be tested. In statements with 10 or more cases, the low efficiency of
this form is not justified by its simplicity.
When the number of cases is 10 or greater, the compiler can build a hash
table of the segment labels, which would result in approximately equal (and
short) times to choose any of the selectable segments. If the language allows
ranges of values for case expressions, as in Ada and Ruby, the hash method is
not suitable. For these situations, a binary search table of case values and seg-
ment addresses is better.
If the range of the case values is relatively small and more than half of the
whole range of values is represented, an array whose indices are the case values
and whose values are the segment labels can be built. Array elements whose
indices are not among the represented case values are filled with the default
segment’s label. Then finding the correct segment label is found by array index-
ing, which is very fast.
Of course, choosing among these approaches is an additional burden on
the compiler. In many compilers, only two different methods are available.
As in other situations, determining and using the most efficient method costs
more compiler time.