Cтраница 4
Оператор вызова значений по 14-разрядному адресу, формируемому из двух слогов, производит обращение к слову, указанному в этом адресе. Данное слово может оказаться значением. В этом случае оно помещается в верхушку стека. Но выбранное слово может оказаться, в свою очередь, косвенной ссылкой или дескриптором. В этом случае аппаратура продолжает поиск нужного значения, последовательно вызывая косвенные ссылки или выполняя извлечение операнда, согласно той управляющей информации, которая указана в дескрипторе. [46]
Аппарат дескрипторов является очень интересной особенностью машин фирмы Барроуз, и далее мы подробнее рассмотрим их назначение и функции. Косвенная ссылка может быть обращена к слову, которое, в свою очередь, само есть косвенная ссылка. Таким путем достигается многоуровневая косвенная адресация, причем длина цепочки косвенных ссылок ничем не ограничена. Следует подчеркнуть еще раз, что команда вызова имени завершает свою работу размещением косвенной ссылки в стеке, в отличие от оператора вызова значения, для выполнения которого может потребоваться аппаратный анализ цепочки косвенных ссылок, многократные обращения в память, в результате чего в верхушке стека должен оказаться операнд. [47]
Этот оператор может выполняться только в том случае, когда в верхушке стека расположен либо дескриптор данных, либо дескриптор косвенной ссылки. В том случае, если исходный дескриптор или косвенная ссылка указывают на следующий дескриптор или следующую косвенную ссылку, этот оператор, разворачивая всю цепочку ссылок, добирается, Наконец, до дескриптора или косвенной ссылки, указывающих на операнд. Эти последние в цепочке ссылок замещают исходный дескриптор в стеке. В том случае, если в верхушке магазина находится информация, отличная от дескриптора данных или косвенной ссылки, производится прерывание по запрещенной команде. Этот оператор доставляет средства, позволяющие добраться до конца косвенных ссылок и в дальнейшем пользоваться доступом к данным, минуя многоступенчатый поиск по памяти, отнимающий много времени. [48]
Аппарат дескрипторов является очень интересной особенностью машин фирмы Барроуз, и далее мы подробнее рассмотрим их назначение и функции. Косвенная ссылка может быть обращена к слову, которое, в свою очередь, само есть косвенная ссылка. Таким путем достигается многоуровневая косвенная адресация, причем длина цепочки косвенных ссылок ничем не ограничена. Следует подчеркнуть еще раз, что команда вызова имени завершает свою работу размещением косвенной ссылки в стеке, в отличие от оператора вызова значения, для выполнения которого может потребоваться аппаратный анализ цепочки косвенных ссылок, многократные обращения в память, в результате чего в верхушке стека должен оказаться операнд. [49]
Затем мы подробно рассмотрим реализацию трех элементарных методов: сортировки выбором, сортировки вставками и пузырьковой сортировки. После этого будут подробно анализироваться рабочие характеристики упомянутых алгоритмов. Далее мы рассмотрим сортировку методом Шелла, которой не очень-то подходит характеристика элементарная, однако она достаточно просто реализуется и имеет много общего с сортировкой методом вставки. Углубляясь в математические свойства сортировки методом Шелла, мы займемся изучением проблемы разработки интерфейсов типов данных, наряду с программами, которые рассматривались в главах 3 и 4 и которые предназначены для распространения изучаемых алгоритмов на сортировку различных видов файлов данных, какие встречаются на практике. Затем мы рассмотрим методы сортировки по косвенным ссылкам на данные, а также методы сортировки связных списков. Данная глава завершается обсуждением специализированного метода, который целесообразно использовать, когда известно, что ключи принимают значения в ограниченном диапазоне. [50]