В заключение темы рассмотрим последний компилятор - WATCOM C. Как и следует ожидать, здесь подстерегают свои тонкости. Итак, откомпилированный им код предыдущего примера должен выглядеть так: main_ proc near ; CODE XREF: CMain+40 ppush 8call CHK; Проверка стека на переполнение cmp eax, 1; Сравнение регистровой переменной EAX, содержащей в себе переменную a; со значением 1 jb short loc_41002F; Если EAX == 0, то переход к ветви с дополнительными проверками jbe short loc_41003A; Если EAX == 1 (т.е. условие bellow уже обработано выше), то переход; к ветке вызова printf("a == 1"); cmp eax, 2; Сравнение EAX со значением 2 jbe short loc_410041; Если EAX == 2 (условие EAX <2 уже было обработано выше), то переход; к ветке вызова printf("a == 2"); cmp eax, 666h; Сравнение EAX со значением 0x666 jz short loc_410048; Если EAX == 0x666, то переход к ветке вызова printf("a == 666h"); jmp short loc_41004F; Ни одно из условий не подошло - переход к ветке "Default" loc_41002F: ; CODE XREF: main_+D j; // printf("a == 0");test eax, eaxjnz short loc_41004F; Совершенно непонятно - зачем здесь дополнительная проверка?!; Это ляп компилятора - она ни к чему! push offset aA0 ; "A == 0"; Здесь WATCOM сумел обойтись всего одним вызовом printf!; Обработчики case всего лишь передают ей нужный аргумент!; Вот это действительно - оптимизация!jmp short loc_410054 loc_41003A: ; CODE XREF: main_+F j; // printf("a == 1");push offset aA1 ; "A == 1"jmp short loc_410054 loc_410041: ; CODE XREF: main_+14 j; // printf("a == 2");push offset aA2 ; "A == 2"jmp short loc_410054 loc_410048: ; CODE XREF: main_+1B j; // printf("a == 666h");push offset aA666h ; "A == 666h"jmp short loc_410054 loc_41004F: ; CODE XREF: main_+1D j main_+21 j; // printf("Default");push offset aDefault ; "Default" loc_410054: ; CODE XREF: main_+28 j main_+2F j .call printf_; Это printf, получающий аргументы из case-обработчиков! add esp, 4; Закрытие кадра стека retnmain_ endp

В общем, WATCOM генерирует более хитрый, но, как ни странно, весьма наглядный и читабельный код.

2.1 Отличия switch от оператора case языка Pascal

Оператор CASE языка Pascal практически идентичен своему Си собрату - оператору switch, хотя и близнецами их не назовешь: оператор CASE выгодно отличается поддержкой наборов и диапазонов значений. Ну, если обработку наборов можно реализовать и посредством switch, правда не так элегантно как на Pascal, то проверка вхождения значения в диапазон на Си организуется исключительно с помощью конструкции "IF-THEN-ELSE". Зато в Паскале каждый case-обработчик принудительно завершается неявным break, а Си-программист волен ставить (или не ставить) его по своему усмотрению.

CASE a OF switch(a)begin {1 : WriteLn('a == 1'); case 1 : printf("a == 1"); break;2,4,7 : WriteLn('a == 2|4|7'); case 2 :case 4 :case 7 : printf("a == 2|4|7"); break;9 : WriteLn('a == 9'); case 9 : printf("a == 9"); break;end;

Однако оба языка накладывают жесткое ограничение на выбор сравниваемой переменной: она должна принадлежать к перечисленному типу, а все наборы (диапазоны) значений представлять собой константы или константные выражения, вычисляемые на стадии компиляции. Подстановка переменных или вызовов функций не допускается.

Представляет интерес посмотреть: как Pascal транслирует проверку диапазонов и сравнить его с компиляторами Си. Рассмотрим следующий пример: VARa : LongInt;BEGIN CASE a OF2 : WriteLn('a == 2');4, 6 : WriteLn('a == 4 | 6 ');10 100 : WriteLn('a == [10,100]');END;END.

Результат его компиляции компилятором Free Pascal должен выглядеть так (приведена лишь левая часть "косички"): mov eax, ds:_A; Загружаем в EAX значение сравниваемой переменной cmp eax, 2; Сравниваем EAX со значением 0х2 jl loc_CA ; Конец CASE; Если EAX < 2, то - конец CASE sub eax, 2; Вычитаем из EAX значение 0x2 jz loc_9E ; WriteLn('a == 2');; Переход на вызов WriteLn('a == 2') если EAX == 2 sub eax, 2; Вычитаем из EAX значение 0x2 jz short loc_72 ; WriteLn('a == 4 | 6');; Переход на вызов WriteLn(''a == 4 | 6') если EAX == 2 (соотв. a == 4) sub eax, 2; Вычитаем из EAX значение 0x2 jz short loc_72 ; WriteLn('a == 4 | 6');; Переход на вызов WriteLn(''a == 4 | 6') если EAX == 2 (соотв. a == 6) sub eax, 4; Вычитаем из EAX значение 0x4 jl loc_CA ; Конец CASE; Переход на конец CASE, если EAX < 4 (соотв. a < 10) sub eax, 90; Вычитаем из EAX значение 90 jle short loc_46 ; WriteLn('a = [10 100]');; Переход на вызов WriteLn('a = [10 100]') если EAX <= 90 (соотв. a <= 100); Поскольку, случай a > 10 уже был обработан выше, то данная ветка; срабатывает при условии a>=10 && a<=100. jmp loc_CA ; Конец CASE; Прыжок на конец CASE - ни одно из условий не подошло

Как видно, Free Pascal генерирует практически тот же самый код, что и компилятор Borland C++ 5.х, поэтому его анализ не должен вызвать никаких сложностей.

2.2 Обрезка (балансировка) длинных деревьев

В некоторых (хотя и редких) случаях, операторы множественного выбора содержат сотни (а то и тысячи) наборов значений, и если решать задачу сравнения "в лоб", то высота логического дерева окажется гигантской до неприличия, а его прохождение займет весьма длительное время, что не лучшим образом скажется на производительности программы.

Здесь возникает вопрос: чем собственно занимается оператор switch? Если отвлечься от устоявшейся идиомы "оператор SWITCH дает специальный способ выбора одного из многих вариантов, который заключается в проверке совпадения значения данного выражения с одной из заданных констант и соответствующем ветвлении", то можно сказать, что switch - оператор поиска соответствующего значения. В таком случае каноническое switch - дерево представляет собой тривиальный алгоритм последовательного поиска - самый неэффективный алгоритм из всех.

Пусть, например, исходный текст программы выглядел так: .switch (a){case 98 : …;case 4 : …;case 3 : …;case 9 : …;case 22 : …;case 0 : …;case 11 : …;case 666: …;case 096: …;case 777: …;case 7 : …;}

Тогда соответствующее ему не оптимизированное логическое дерево будет достигать в высоту одиннадцати гнезд (см. рис. 5 слева). Причем, на левой ветке корневого гнезда окажется аж десять других гнезд, а на правой - вообще ни одного (только соответствующий ему case - обработчик).

Исправить "перекос" можно разрезав одну ветку на две и привив образовавшиеся половинки к новому гнезду, содержащему условие, определяющее в какой из веток следует искать сравниваемую переменную. Например, левая ветка может содержать гнезда с четными значениями, а правая - с нечетными. Но это плохой критерий: четных и нечетных значений редко бывает поровну и вновь образуется перекос. Гораздо надежнее поступить так: берется наименьшее из всех значений и бросается в кучу А, затем берется наибольшее из всех значений и бросается в кучу B. Так повторяется до тех пор, пока не рассортируются все, имеющиеся значения.