algorithm - ジャンプテーブルのサイズを最適化するには?

Question

次のような C ライクな言語の典型的な列挙型を考えてみましょう。

enum foo {
    FOO_A,
    FOO_B,
    FOO_C,
    /* ... */
    FOO_N
};

type の値に対する switch ステートメントがありenum foo、特定の列挙値を処理しない可能性があります。

enum foo bar;
/* ... */
switch (bar) {
case FOO_A: /* ... */
case FOO_B: /* ... */
case FOO_D: /* ... */
case FOO_L: /* ... */
default: /* ... */
}

ここで、処理される列挙値の量が十分に多い場合、コンパイラは、サイズが(<処理される最大値> - <処理される最小値> + 1) * sizeof(void*)のジャンプ テーブルを使用して、switch ステートメントを実装します。

ジャンプ テーブルを使用することが知られているこのような switch ステートメントが複数あるとします。それぞれのステートメントで、どの値が処理され、どの値が処理されないかがわかっているからです。enum foo生成されたすべてのジャンプ テーブルの合計サイズが最小になるように値を並べ替えるにはどうすればよいですか?

例

以下は、コンパイラがすべての switch ステートメントに対してジャンプ テーブルを生成することを前提とした、少し単純化された例です。これは列挙です：

enum example {
    EX_A,
    EX_B,
    EX_C,
    EX_D
};

そして、これらは2つのスイッチステートメントです:

enum example a, b;

switch (a) {
case EX_A: /* ... */
case EX_C: /* ... */
default: /* ... */
}

switch (b) {
case EX_B: /* ... */
case EX_D: /* ... */
default: /* ... */
}

この例では、コンパイラはそれぞれ 3 つのエントリを持つ 2 つのジャンプ テーブルを生成し (最初のケースではEX_Ato からEX_C、2 番目のケースではEX_Bto からEX_D)、合計で 6 つのマシン ワードがジャンプ テーブルに使用されます。次のように列挙を並べ替えた場合:

enum example {
    EX_A,
    EX_C,
    EX_B,
    EX_D
};

ジャンプ テーブルに必要なデータ ワードは 4 つだけです。