A switch clause is just an integer or anything that can be widened to an int
(such as char, short). The GNU compiler (as an example) recognized three
different ways to compile a switch statement, depending on the case values:
1) perfect
2) dense
3) normal
A perfect switch statement has consecutive case values (in no particular order):
-
switch (value) {
-
case 3: do3(); break;
-
case 5: do5(); break;
-
case 4: do4(); break;
-
}
Code generated for this switch statement involves a simple jump table:
0: address of do3();
1: address of do4();
2: address of do5();
the address to be jumped to is table[value-3].
A dense switch statement is like a perfect switch table where all the case
clauses are almost consecutive and the resulting jump table would be dense.
The empty entries point to the address where the (optional or empty) default
case selector is located.
A normal switch statement also uses a jump table and a case value table which
again is sorted. The value table is consulted using a binary search for the case
selector value. If the entry is found, the jump table destination is used,
otherwise the default case clause address will be used.
The first to variants are O(1) while the third variant is O(log(n)) where n is the
number of case clauses in the switch statement. The AIX xlc compiler suite
attempts to find a perfect hash function for a normal switch statement which
can result in O(1) behaviour even for normal (sparse) switch statements. This
attempt can fail and code similar to GNU's compiler generated code for the
normal switch statement is generated.
kind regards,
Jos