тивен даже в языке Pascal. Поскольку размер каждого компонента Е известен уже при трансляции, то, если значение индекса также известно при трансляции (например, А[2]), вся формула доступа может быть вычислена во время компиляции. Обратите внимание на то, что в массивах типа char языка С Е = 1; поскольку всегда выполняется равенство LB = 0, эквивалентная формула доступа в С становится чрезвычайно простой:
/-значение(А[1]) - а + I
Рис. 6.3. Представление вектора А с полным дескриптором
Виртуальный начальный адрес. Теперь вычислим адрес элемента с индексом О нашего вектора. Формула доступа дает следующий результат:
;-значение(А[0]) = (а - LB х Е) + (0 х Е) = (а - LB х Е) = К
Таким образом, К представляет собой адрес блока памяти, который занимает элемент вектора с индексом 0, если он существует. Поскольку элемент с нулевым индексом может и не существовать (потому что нижняя граница диапазона индексов может быть больше нуля), то этот адрес называется виртуальным начальным адресом (virtual origin, VO). Таким образом, мы получаем следующий алгоритм для построения векторов и генерации формулы доступа.
1. При выделении памяти для представления вектора отводится место в памяти для N компонентов вектора, каждый размером Е, и для дескриптора размером D, то есть всего D + N х Е ячеек памяти. Пусть а обозначает адрес расположения первого компонента вектора.
250
Глава 6. Инкапсуляция
2. Вычисляем виртуальный начальный адрес VO = а - LB х Е.
3. При доступе к компоненту вектора /-значение любого компонента А[1] вы числяется как
7-значение(А[1]) = VO + I х Е
Предполагается, что значение индекса I в формуле заведомо является допустимым для данного массива А. Для проверки возможных ошибок, связанных с выходом значения индекса за пределы допустимого диапазона, следует до вычисления формулы доступа проверить выполнение двойного неравенства LB < I < UB (где LB и UB — соответственно нижняя и верхняя границы диапазона), а значения LB и UB должны присутствовать в дескрипторе во время выполнения программы. Вообще говоря, чтобы точно указать наиболее эффективный способ вычисления формулы доступа и проверки диапазона, нужно учесть конкретную конфигурацию аппаратной части компьютера и те операции, которые в нее встроены. Проверка диапазона именно этими средствами гарантирует, что даже если индекс I не находится внутри диапазона LB < I < UB, соответствующая область памяти никогда не может быть доступна как /-значение, которое не представляет правильный индекс.
Заметим, что в приведенной формуле доступа используется виртуальный начальный адрес для определения местоположения данного элемента массива. Если виртуальный начальный адрес хранится в дескрипторе массива, то сам массив не обязательно должен занимать область памяти, смежную с его дескриптором (рис. 6.4). Это обычный случай, когда дескрипторы для параметров-массивов могут быть переданы в какую-либо подпрограмму, а сам массив может фактически храниться где-то в другом месте. (Заметим, что типы данных для дескриптора и компонентов вектора на рис. 6.4 опущены. Для таких языков, как С или Pascal, эта информация получается во время трансляции, поэтому нет необходимости сохранять ее в дескрипторе времени выполнения.)
Упакованное и неупакованное представления в памяти. Предполагается, что размер каждого компонента в приведенной выше формуле доступа равен Е и является целым числом адресуемых единиц памяти (слов или байтов). Например, если базовая адресуемая единица памяти — это слово, то предполагается, что каждый компонент занимает одно слово, или два, или более в зависимости от указанного в объявлении типа. Если тип компонента логический или символьный, то для представления этого компонента может потребоваться только небольшая часть слова. В таком случае в одно слово могут уместиться несколько компонентов. Упакованное представление — это такое представление, при котором компоненты вектора (или другой структуры) располагаются в памяти подряд, при этом каждый очередной компонент вовсе не должен оказываться в начале адресуемого слова (или байта). Упакованное представление позволяет сэкономить значительное количество ресурсов памяти. К сожалению, доступ к компонентам упакованного вектора обычно обходится гораздо дороже, поскольку в таком случае обычная формула доступа непригодна. Вместо нее приходится использовать ряд более сложных вычислений для доступа к тому слову или байту, в котором содержится искомый компонент.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.