Адресная арифметика

Если p является указателем, то каков бы ни был сорт объекта, на который он указывает, операция p++ увеличивает p так, что он указывает на следующий элемент набора этих объектов, а операция p +=i увеличивает p так, чтобы он указывал на элемент, отстоящий на i элементов от текущего элемента. Эти и аналогичные конструкции представляют собой самые простые и самые распространенные формы арифметики указателей или адресной арифметики.

Язык "C" последователен и постоянен в своем подходе к адресной арифметике; объединение в одно целое указателей, массивов и адресной арифметики является одной из наиболее сильных сторон языка. Давайте проиллюстрируем некоторые из соответствующих возможностей языка на примере элементарной (но полезной, несмотря на свою простоту) программы распределения памяти. Имеются две функции: функция alloc(n) возвращает в качестве своего значения указатель p, который указывает на первую из n последовательных символьных позиций, которые могут быть использованы вызывающей функцию alloc программой для хранения символов; функция free(p) освобождает приобретенную таким образом память, так что ее в дальнейшем можно снова использовать. программа является "элементарной", потому что обращения к free должны производиться в порядке, обратном тому, в котором производились обращения к alloc. Таким образом, управляемая функциями alloc и free память является стеком или списком, в котором последний вводимый элемент извлекается первым. Стандартная библиотека языка "C" содержит аналогичные функции, не имеющие таких ограничений, и, кроме того, в лекции №8 мы приведем улучшенные варианты. Между тем, однако, для многих приложений нужна только тривиальная функция alloc для распределения небольших участков памяти неизвестных заранее размеров в непредсказуемые моменты времени.

Простейшая реализация состоит в том, чтобы функция раздавала отрезки большого символьного массива, которому мы присвоили имя allocbuf. Этот массив является собственностью функций alloc и free. Так как они работают с указателями, а не с индексами массива, никакой другой функции не нужно знать имя этого массива. Он может быть описан как внешний статический, т.е. он будет локальным по отношению к исходному файлу, содержащему alloc и free, и невидимым за его пределами. При практической реализации этот массив может даже не иметь имени; вместо этого он может быть получен в результате запроса к операционной системе на указатель некоторого неименованного блока памяти.

Другой необходимой информацией является то, какая часть массива allocbuf уже использована. Мы пользуемся указателем первого свободного элемента, названным allocp. Когда к функции alloc обращаются за выделением n символов, то она проверяет, достаточно ли осталось для этого места в allocbuf. Если достаточно, то alloc возвращает текущее значение allocp (т.е. начало свободного блока), затем увеличивает его на n, с тем чтобы он указывал на следующую свободную область. функция free(p) просто полагает allocp равным p при условии, что p указывает на позицию внутри allocbuf.

define null 0 /* pointer value for error report */ define allocsize 1000 /* size of available space */

static char allocbuf[allocsize];/* storage for alloc */ static char *allocp = allocbuf; /* next free position */

char *alloc(n) /* return pointer to n characters */ int n; ( if (allocp + n <= allocbuf + allocsize) { allocp += n; return(allocp - n); /* old p */ } else /* not enough room */ return(null); )

free(p) /* free storage pointed by p */ char *p; ( if (p >= allocbuf && p < allocbuf + allocsize) allocp = p; )

Дадим некоторые пояснения. Вообще говоря, указатель может быть инициализирован точно так же, как и любая другая переменная, хотя обычно единственными осмысленными значениями являются null (это обсуждается ниже) или выражение, включающее адреса ранее определеных данных соответствующего типа.

описание

static char *allocp = allocbuf;

определяет allocp как указатель на символы и инициализирует его так, чтобы он указывал на allocbuf, т.е. на первую свободную позицию при начале работы программы. Так как имя массива является адресом его нулевого элемента, то это можно было бы записать в виде

static char *allocp = &allocbuf[0];

используйте ту запись, которая вам кажется более естественной. С помощью проверки

if (allocp + n <= allocbuf + allocsize)

выясняется, осталось ли достаточно места, чтобы удовлетворить запрос на n символов. Если достаточно, то новое значение allocp не будет указывать дальше, чем на последнюю позицию allocbuf. Если запрос может быть удовлетворен, то alloc возвращает обычный указатель (обратите внимание на описание самой функции). Если же нет, то alloc должна вернуть некоторый признак, говорящий о том, что больше места не осталось. В языке "C" гарантируется, что ни один правильный указатель данных не может иметь значение нуль, так что возвращение нуля может служить в качестве сигнала о ненормальном событии, в данном случае об отсутствии места. Мы, однако, вместо нуля пишем null, с тем чтобы более ясно показать, что это специальное значение указателя. Вообще говоря, целые не могут осмысленно присваиваться указателям, а нуль - это особый случай.

Проверки вида



if (allocp + n <= allocbuf + aloocsize) и if (p >= allocbuf && p < allocbuf + allocsize)

демонстрируют несколько важных аспектов арифметики указателей. Во-первых , при определеных условиях указатели можно сравнивать. Если p и q указывают на элементы одного и того же массива, то такие отношения, как <, >= и т.д., работают надлежащим образом. Например,

p < q

истинно, если p указывает на более ранний элемент массива, чем q. Отношения == и != тоже работают. Любой указатель можно осмысленным образом сравнить на равенство или неравенство с null. Но ни за что нельзя ручаться, если вы используете сравнения при работе с указателями, указывающими на разные массивы. Если вам повезет, то на всех машинах вы получите очевидную бессмыслицу. Если же нет, то ваша программа будет правильно работать на одной машине и давать непостижимые результаты на другой.

Во-вторых, как мы уже видели, указатель и целое можно складывать и вычитать. конструкция

p + n

подразумевает n-ый объект за тем, на который p указывает в настоящий момент. Это справедливо независимо от того, на какой вид объектов p должен указывать; компилятор сам масштабирует n в соответствии с определяемым из описания p размером объектов, указываемых с помощью p. Например, на PDP-11 масштабирующий множитель равен 1 для char, 2 для int и short, 4 для long и float и 8 для double.

Вычитание указателей тоже возможно: если p и q указывают на элементы одного и того же массива, то p-q - количество элементов между p и q. Этот факт можно использовать для написания еще одного варианта функции



strlen: strlen(s) /* return length of string s */ char *s; { char *p = s;

while (*p != '\0') p++; return(p-s); }

При описании указатель p в этой функции инициализирован посредством строки s, в результате чего он указывает на первый символ строки. В цикле while по очереди проверяется каждый символ до тех пор, пока не появится символ конца строки \0. Так как значение \0 равно нулю, а while только выясняет, имеет ли выражение в нем значение 0, то в данном случае явную проверку можно опустить. Такие циклы часто записывают в виде

Инициализация массивов указателей

Рассмотрим задачу написания функции month_name(n), которая возвращает указатель на символьную строку, содержащую имя n-го месяца. Это идеальная задача для применения внутреннего статического массива. функция month_name содержит локальный массив символьных строк и при обращении к ней возвращает указатель нужной строки. Тема настоящего раздела - как инициализировать этот массив имен.

char *month_name(n) /* return name of n-th month */ int n; { static char *name[] = { "illegal month", "january", "february", "march", "april", "may", "jun", "july", "august", "september", "october", "november", "december" }; return ((n < 1 || n > 12) ? name[0] : name[n]); }

описание массива указателей на символы name точно такое же, как аналогичное описание lineptr в примере с сортировкой. Инициализатором является просто список символьных строк; каждая строка присваивается соответствующей позиции в массиве. Более точно, символы i-ой строки помещаются в какое-то иное место, а ее указатель хранится в name[i]. Поскольку размер массива name не указан, компилятор сам подсчитывает количество инициализаторов и соответственно устанавливает правильное число.

Командная строка аргументов

Системные средства, на которые опирается реализация языка "с", позволяют передавать командную строку аргументов или параметров начинающей выполняться программе. Когда функция main вызывается к исполнению, она вызывается с двумя аргументами. Первый аргумент (условно называемый argc) указывает число аргументов в командной строке, с которыми происходит обращение к программе; второй аргумент (argv) является указателем на массив символьных строк, содержащих эти аргументы, по одному в строке. Работа с такими строками - это обычное использование многоуровневых указателей.

Самую простую иллюстрацию этой возможности и необходимых при этом описаний дает программа echo, которая просто печатает в одну строку аргументы командной строки, разделяя их пробелами. Таким образом, если дана команда

echo hello, world

то выходом будет

hello, world

по соглашению argv[0] является именем, по которому вызывается программа, так что argc по меньшей мере равен 1. В приведенном выше примере argc равен 3, а argv[0], argv[1] и argv[2] равны соответственно "echo", "hello," и "world". Первым фактическим аргументом является argv[1], а последним - argv[argc-1]. Если argc равен 1, то за именем программы не следует никакой командной строки аргументов. Все это показано в echo:

main(argc, argv) /* echo arguments; 1st version */ int argc; char *argv[]; { int i;

for (i = 1; i < argc; i++) printf("%s%c", argv[i], (i<argc-1) ? ' ' : '\n'); }

Поскольку argv является указателем на массив указателей, то существует несколько способов написания этой программы, использующих работу с указателем, а не с индексацией массива. Мы продемонстрируем два варианта.

main(argc, argv) /* echo arguments; 2nd version */ int argc; char *argv[]; { while (--argc > 0) printf("%s%c",*++argv, (argc > 1) ? ' ' : '\n'); }

Так как argv является указателем на начало массива строк- аргументов, то, увеличив его на 1 (++argv), мы вынуждаем его указывать на подлинный аргумент argv[1], а не на argv[0]. Каждое последующее увеличение передвигает его на следующий аргумент; при этом *argv становится указателем на этот аргумент. Одновременно величина argc уменьшается; когда она обратится в нуль, все аргументы будут уже напечатаны.

Другой вариант:

main(argc, argv) /* echo arguments; 3rd version */ int argc; char *argv[]; { while (--argc > 0) printf((argc > 1) ? "%s" : "%s\n", *++argv); }

Эта версия показывает, что аргумент формата функции printf может быть выражением, точно так же, как и любой другой. Такое использование встречается не очень часто, но его все же стоит запомнить.

Как второй пример, давайте внесем некоторые усовершенствования в программу отыскания заданной комбинации символов из лекции №4. Если вы помните, мы поместили искомую комбинацию глубоко внутрь программы, что очевидно является совершенно неудовлетворительным. Следуя утилите grep системы UNIX, давайте изменим программу так, чтобы эта комбинация указывалась в качестве первого аргумента строки.

#define maxline 1000

main(argc, argv) /* find pattern from first argument */ int argc; char *argv[]; { char line[maxline];

if (argc != 2) printf ("usage: find pattern\n"); else while (getline(line, maxline) > 0) if (index(line, argv[1] >= 0) printf("%s", line); }

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

Общепринятым соглашением в "с"-программах является то, что аргумент, начинающийся со знака минус, вводит необязательный признак или параметр. Если мы, для того, чтобы сообщить об инверсии, выберем -x, а для указания о нумерации нужных строк выберем -n("номер"), то команда

find -x -n the

при входных данных

now is the time for all good men to come to the aid of their party.

Должна выдать

2:for all good men

Нужно, чтобы необязательные аргументы могли располагаться в произвольном порядке, и чтобы остальная часть программы не зависела от количества фактически присутствующих аргументов. В частности, вызов функции index не должен содержать ссылку на argv[2], когда присутствует один необязательный аргумент, и на argv[1], когда его нет. Более того, для пользователей удобно, чтобы необязательные аргументы можно было объединить в виде:



find -nx the

вот сама программа:

#define maxline 1000

main(argc, argv) /* find pattern from first argument */ int argc; char *argv[]; { char line[maxline], *s; long lineno = 0; int except = 0, number = 0; while (--argc > 0 && (*++argv)[0] == '-') for (s = argv[0]+1; *s != '\0'; s++) switch (*s) { case 'x': except = 1; break;

case 'n': number = 1; break; default: printf("find: illegal option %c\n", *s); argc = 0; break; } if (argc != 1) printf("usage: find -x -n pattern\n"); else while (getlinе(line, maxline) > 0) { lineno++; if ((index(line, *argv) >= 0) != except) \ if (number) printf("%ld: ", lineno); printf("%s", line); } } }

аргумент argv увеличивается перед каждым необязательным аргументом, в то время как аргумент argc уменьшается. Если нет ошибок, то в конце цикла величина argc должна равняться 1, а *argv должно указывать на заданную комбинацию. Обратите внимание на то, что *++argv является указателем аргументной строки; (*++argv)[0] - ее первый символ. Круглые скобки здесь необходимы, потому что без них выражение бы приняло совершенно отличный (и неправильный) вид *++(argv[0]). Другой правильной формой была бы **++argv.

Упражнение 5-7

Напишите программу add, вычисляющую обратное польское выражение из командной строки. Например,

add 2 3 4 + * вычисляет 2*(3+4).

Упражнение 5-8

Модифицируйте программы entab и detab (указанные в качестве упражнений в лекции №1) так, чтобы они получали список табуляционных остановок в качестве аргументов. Если аргументы отсутствуют, используйте стандартную установку табуляций.

Упражнение 5-9

Расширьте entab и detab таким образом, чтобы они воспринимали сокращенную нотацию

entab m +n

означающую табуляционные остановки через каждые n столбцов, начиная со столбца m. Выберите удобное (для пользователя) поведение функции по умолчанию.

Упражнение 5-10

Напишите программу для функции tail, печатающей последние n строк из своего файла ввода. Пусть по умолчанию n равно 10, но это число может быть изменено с помощью необязательного аргумента, так что

Массивы указателей; указатели указателей

Так как указатели сами являются переменными, то вы вполне могли бы ожидать использования массива указателей. Это действительно так. Мы проиллюстрируем это написанием программы сортировки в алфавитном порядке набора текстовых строк, предельно упрощенного варианта утилиты sort операционной систем UNIX.

В лекции №3 мы привели функцию сортировки по Шеллу, которая упорядочивала массив целых. Этот же алгоритм будет работать и здесь, хотя теперь мы будем иметь дело со строчками текста различной длины, которые, в отличие от целых, нельзя сравнивать или перемещать с помощью одной операции. Мы нуждаемся в таком представлении данных, которое бы позволяло удобно и эффективно обрабатывать строки текста переменной длины.

Здесь и возникают массивы указателей. Если подлежащие сортировке сроки хранятся одна за другой в длинном символьном массиве (управляемом, например, функцией alloc ), то к каждой строке можно обратиться с помощью указателя на ее первый символ. Сами указатели можно хранить в массиве. Две строки можно сравнить, передав их указатели функции strcmp.

Если две расположенные в неправильном порядке строки должны быть переставлены, то фактически переставляются указатели в массиве указателей, а не сами тексты строк. Этим исключаются сразу две связанные проблемы: сложного управления памятью и больших дополнительных затрат на фактическую перестановку строк.

Процесс сортировки включает три шага:

чтение всех строк ввода их сортировка вывод их в правильном порядке

Как обычно, лучше разделить программу на несколько функций в соответствии с естественным делением задачи и выделить ведущую функцию, управляющую работой всей программы. Давайте отложим на некоторое время рассмотрение шага сортировки и сосредоточимся на структуре данных и вводе-выводе. функция, осуществляющая ввод, должна извлечь символы каждой строки, запомнить их и построить массив указателей строк. Она должна также подсчитать число строк во вводе, так как эта информация необходима при сортировке и выводе. Так как функция ввода в состоянии справиться только с конечным числом вводимых строк, в случае слишком большого их числа она может возвращать некоторое число, отличное от возможного числа строк, например -1. функция осуществляющая вывод, должна печатать строки в том порядке, в каком они появляются в массиве указателей.

#define null 0 #define lines 100 /* max lines to be sorted */

main() /* sort input lines */ { char *lineptr[lines]; /*pointers to text lines */ int nlines; /* number of input lines read */

if ((nlines = readlines(lineptr, lines)) >= 0) { sort(lineptr, nlines); writelines(lineptr, nlines); } else printf("input too big to sort\n"); }

#define maxlen 1000

readlines(lineptr, maxlines) /* read input lines */ char *lineptr[]; /* for sorting */ int maxlines; { int len, nlines; char *p, *alloc(), line[maxlen];

nlines = 0; while ((len = getline(line, maxlen)) > 0) if (nlines >= maxlines) return(-1); else if ((p = alloc(len)) == null) return (-1); else { line[len-1] = '\0'; /* zap newline */ strcpy(p,line); lineptr[nlines++] = p; } return(nlines); }

Символ новой строки в конце каждой строки удаляется, так что он никак не будет влиять на порядок, в котором сортируются строки.

writelines(lineptr, nlines) /* write output lines */ char *lineptr[]; int nlines; { int i;

for (i = 0; i < nlines; i++) printf("%s\n", lineptr[i]); }

Существенно новым в этой программе является описание

char *lineptr[lines];

которое сообщает, что lineptr является массивом из lines элементов, каждый из которых - указатель на переменные типа char. Это означает, что lineptr[i] - указатель на символы, а *lineptr[i] извлекает символ.

Так как сам lineptr является массивом, который передается функции writelines, с ним можно обращаться как с указателем точно таким же образом, как в наших более ранних примерах. Тогда последнюю функцию можно переписать в виде:

writelines(lineptr, nlines) /* write output lines */ char *lineptr[]; int nlines; { int i;

while (--nlines >= 0) printf("%s\n", *lineptr++); }

здесь *lineptr сначала указывает на первую строку; каждое увеличение передвигает указатель на следующую строку, в то время как nlines убывает до нуля.

Справившись с вводом и выводом, мы можем перейти к сортировке. Программа сортировки по Шеллу из лекции №3 требует очень небольших изменений: должны быть модифицированы описания, а операция сравнения выделена в отдельную функцию. Основной алгоритм остается тем же самым, и это дает нам определенную уверенность, что он по-прежнему будет работать.


sort(v, n) /* sort strings v[0] ... v[n-1] */ char *v[]; /* into increasing order */ int n; { int gap, i, j; char *temp;

for (gap = n/2; gap > 0; gap /= 2) for (i = gap; i < n; i++) for (j = i - gap; j >= 0; j -= gap) { if (strcmp(v[j], v[j+gap]) <= 0) break; temp = v[j]; v[j] = v[j+gap]; v[j+gap] = temp; } }

Так как каждый отдельный элемент массива v (имя формального параметра, соответствующего lineptr) является указателем на символы, то и temp должен быть указателем на символы, чтобы их было можно копировать друг в друга.

Мы написали эту программу по возможности более просто с тем, чтобы побыстрее получить работающую программу. Она могла бы работать быстрее, если, например, вводить строки непосредственно в массив, управляемый функцией readlines, а не копировать их в line, а затем в скрытое место с помощью функции alloc. Но мы считаем, что будет разумнее первоначальный вариант сделать более простым для понимания, а об "эффективности" позаботиться позднее. Все же, по-видимому, способ, позволяющий добиться заметного ускорения работы программы состоит не в исключении лишнего копирования вводимых строк. Более вероятно, что существенной разницы можно достичь за счет замены сортировки по шеллу на нечто лучшее, например, на метод быстрой сортировки.

В лекции №1 мы отмечали, что поскольку в циклах while и for проверка осуществляется до того, как тело цикла выполнится хотя бы один раз, эти циклы оказываются удобными для обеспечения правильной работы программы при граничных значениях, в частности, когда ввода вообще нет. Очень полезно просмотреть все функции программы сортировки, разбираясь, что происходит, если вводимый текст отсутствует.

Упражнение 5-5

Перепишите функцию readlines таким образом, чтобы она помещала строки в массив, предоставляемый функцией main, а не в память, управляемую обращениями к функции alloc. Насколько быстрее стала программа?

Многомерные массивы

В языке "C" предусмотрены прямоугольные многомерные массивы, хотя на практике существует тенденция к их значительно более редкому использованию по сравнению с массивами указателей. В этом разделе мы рассмотрим некоторые их свойства.

Рассмотрим задачу преобразования дня месяца в день года и наоборот. Например, 1-ое марта является 60-м днем не високосного года и 61-м днем високосного года. Давайте введем две функции для выполнения этих преобразований: day_of_year преобразует месяц и день в день года, а month_day преобразует день года в месяц и день. Так как эта последняя функция возвращает два значения, то аргументы месяца и дня должны быть указателями:

month_day(1977, 60, &m, &d)

Полагает m равным 3 и d равным 1 (1-ое марта).

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

static int day_tab[2][13] = { (0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31), (0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31) };

day_of_year(year, month, day) /* set day of year */ int year, month, day; /* from month & day */ { int i, leap; leap = year%4 == 0 && year%100 != 0 || year%400 == 0; for (i = 1; i < month; i++) day += day_tab[leap][i]; return(day); {

month_day(year, yearday, pmonth, pday) /*set month,day */ int year, yearday, *pmonth, *pday; /* from day of year */ { leap = year%4 == 0 && year%100 != 0 || year%400 == 0; for (i = 1; yearday > day_tab[leap][i]; i++) yearday -= day_tab[leap][i]; *pmonth = i; *pday = yearday; }

Массив day_tab должен быть внешним как для day_of_year, так и для month_day, поскольку он используется обеими этими функциями.

Массив day_tab является первым двумерным массивом, с которым мы имеем дело. По определению в "C" двумерный массив по существу является одномерным массивом, каждый элемент которого является массивом. Поэтому индексы записываются как

Указатели и адреса

Так как указатель содержит адрес объекта, это дает возможность "косвенного" доступа к этому объекту через указатель. Предположим, что х - переменная, например, типа int, а рх - указатель, созданный неким еще не указанным способом. Унарная операция & выдает адрес объекта, так что оператор

рх = &х;

присваивает адрес х переменной рх; говорят, что рх "указывает" на х. Операция & применима только к переменным и элементам массива, конструкции вида &(х-1) и &3 являются незаконными. Нельзя также получить адрес регистровой переменной.

Унарная операция * рассматривает свой операнд как адрес конечной цели и обращается по этому адресу, чтобы извлечь содержимое. Следовательно, если y тоже имеет тип int, то

y = *рх;

присваивает y содержимое того, на что указывает рх. Так последовательность

рх = &х; y = *рх;

присваивает y то же самое значение, что и оператор

y = x;

переменные, участвующие во всем этом необходимо описать:

int x, y; int *px;

с описанием для x и y мы уже неоднократно встречались. описание указателя

int *px;

является новым и должно рассматриваться как мнемоническое; оно говорит, что комбинация *px имеет тип int. Это означает, что если px появляется в контексте *px, то это эквивалентно переменной типа int. Фактически синтаксис описания переменной имитирует синтаксис выражений, в которых эта переменная может появляться. Это замечание полезно во всех случаях, связанных со сложными описаниями. Например,

double atof(), *dp;

говорит, что atof() и *dp имеют в выражениях значения типа double.

Вы должны также заметить, что из этого описания следует, что указатель может указывать только на определенный вид объектов.

указатели могут входить в выражения. Например, если px указывает на целое x, то *px может появляться в любом контексте, где может встретиться x. Так оператор

y = *px + 1

присваивает y значение, на 1 большее значения x;

printf("%d\n", *px)

печатает текущее значение x;

d = sqrt((double) *px)

получает в d квадратный корень из x, причем до передачи функции sqrt значение x преобразуется к типу double. (Смотри лекцию №2).

В выражениях вида

Указатели и аргументы функций

Так как в "с" передача аргументов функциям осуществляется "по значению", вызванная процедура не имеет непосредственной возможности изменить переменную из вызывающей программы. Что же делать, если вам действительно надо изменить аргумент? Например, программа сортировки захотела бы поменять два нарушающих порядок элемента с помощью функции с именем swap. Для этого недостаточно написать

swap(a, b);

определив функцию swap при этом следующим образом:

swap(x, y) /* wrong */ int x, y; { int temp;

temp = x; x = y; y = temp; }

из-за вызова по значению swap не может воздействовать на аргументы a и b в вызывающей функции.

К счастью, все же имеется возможность получить желаемый эффект. Вызывающая программа передает указатели подлежащих изменению значений: swap(&a, &b); так как операция & выдает адрес переменной, то &a является указателем на a. В самой swap аргументы описываются как указатели и доступ к фактическим операндам осуществляется через них.

swap(px, py) /* interchange *px and *py */ int *px, *py; { int temp;

temp = *px; *px = *py; *py = temp; }

Указатели в качестве аргументов обычно используются в функциях, которые должны возвращать более одного значения. (Можно сказать, что swap возвращает два значения, новые значения ее аргументов). В качестве примера рассмотрим функцию getint, которая осуществляет преобразование поступающих в свободном формате данных, разделяя поток символов на целые значения, по одному целому за одно обращение. функция getint должна возвращать либо найденное значение, либо признак конца файла, если входные данные полностью исчерпаны. Эти значения должны возвращаться как отдельные объекты, какое бы значение ни использовалось для EOF, даже если это значение вводимого целого.

Одно из решений, основывающееся на описываемой в лекции №7

функции ввода scanf, состоит в том, чтобы при выходе на конец файла getint возвращала EOF в качестве значения функции; любое другое возвращенное значение говорит о нахождении нормального целого. Численное же значение найденного целого возвращается через аргумент, который должен быть указателем целого. Эта организация разделяет статус конца файла и численные значения.

Следующий цикл заполняет массив целыми с помощью обращений к функции

Указатели и массивы

Указатель - это переменная, содержащая адрес другой переменной. указатели очень широко используются в языке "C". Это происходит отчасти потому, что иногда они дают единственную возможность выразить нужное действие, а отчасти потому, что они обычно ведут к более компактным и эффективным программам, чем те, которые могут быть получены другими способами.

указатели обычно смешивают в одну кучу с операторами goto, характеризуя их как чудесный способ написания программ, которые невозможно понять. Это безусловно справедливо, если указатели используются беззаботно; очень просто ввести указатели, которые указывают на что-то совершенно неожиданное. Однако, при определенной дисциплине, использование указателей помогает достичь ясности и простоты. Именно этот аспект мы попытаемся здесь проиллюстрировать.

pa = a

Еще более удивительным, по крайней мере на первый взгляд, кажется тот факт, что ссылку на a[i] можно записать в виде *(a+i). При анализировании выражения a[i] в языке "C" оно немедленно преобразуется к виду *(a+i); эти две формы совершенно эквивалентны. Если применить операцию & к обеим частям такого соотношения эквивалентности, то мы получим, что &a[i] и a+i тоже идентичны: a+i - адрес i-го элемента от начала a. С другой стороны, если pa является указателем, то в выражениях его можно использовать с индексом: pa[i] идентично *(pa+i). Короче, любое выражение, включающее массивы и индексы, может быть записано через указатели и смещения и наоборот, причем даже в одном и том же утверждении.

Имеется одно различие между именем массива и указателем, которое необходимо иметь в виду. указатель является переменной, так что операции pa=a и pa++ имеют смысл. Но имя массива является константой, а не переменной: конструкции типа a=pa или a++,или p=&a будут незаконными.

Когда имя массива передается функции, то на самом деле ей передается местоположение начала этого массива. Внутри вызванной функции такой аргумент является точно такой же переменной, как и любая другая, так что имя массива в качестве аргумента действительно является указателем, т.е. переменной, содержащей адрес. МЫ можем использовать это обстоятельство для написания нового варианта функции strlen, вычисляющей длину строки.

strlen(s) /* return length of string s */ char *s; { int n;

for (n = 0; *s != '\0'; s++) n++; return(n); }

Операция увеличения s совершенно законна, поскольку эта переменная является указателем; s++ никак не влияет на символьную строку в обратившейся к strlen функции, а только увеличивает локальную для функции strlen копию адреса. описания формальных параметров в определении функции в виде

char s[]; char *s;

совершенно эквивалентны; какой вид описания следует предпочесть, определяется в значительной степени тем, какие выражения будут использованы при написании функции. Если функции передается имя массива, то в зависимости от того, что удобнее, можно полагать, что функция оперирует либо с массивом, либо с указателем, и действовать далее соответствующим образом. Можно даже использовать оба вида операций, если это кажется уместным и ясным.

Можно передать функции часть массива, если задать в качестве аргумента указатель начала подмассива. Например, если a - массив, то как

Указатели на функции

В языке "с" сами функции не являются переменными, но имеется возможность определить указатель на функцию, который можно обрабатывать, передавать другим функциям, помещать в массивы и т.д. Мы проиллюстрируем это, проведя модификацию написанной ранее программы сортировки так, чтобы при задании необязательного аргумента -n она бы сортировала строки ввода численно, а не лексикографически.

Сортировка часто состоит из трех частей - сравнения, которое определяет упорядочивание любой пары объектов, перестановки, изменяющей их порядок, и алгоритма сортировки, осуществляющего сравнения и перестановки до тех пор, пока объекты не расположатся в нужном порядке. Алгоритм сортировки не зависит от операций сравнения и перестановки, так что, передавая в него различные функции сравнения и перестановки, мы можем организовать сортировку по различным критериям. Именно такой подход используется в нашей новой программе сортировки.

Как и прежде, лексикографическое сравнение двух строк осуществляется функцией strcmp, а перестановка функцией swap; нам нужна еще функция numcmp, сравнивающая две строки на основе численного значения и возвращающая условное указание того же вида, что и strcmp. Эти три функции описываются в main и указатели на них передаются в sort. В свою очередь функция sort обращается к этим функциям через их указатели. мы урезали обработку ошибок в аргументах с тем, чтобы сосредоточиться на главных вопросах.

#define lines 100 /* max number of lines to be sorted */

main(argc, argv) /* sort input lines */ int argc; char *argv[]; { char *lineptr[lines]; /* pointers to text lines */ int nlines; /* number of input lines read */ int strcmp(), numcmp(); /* comparsion functions */ int swap(); /* exchange function */ int numeric = 0; /* 1 if numeric sort */

if(argc>1 && argv[1][0] == '-' && argv[1][1]=='n') numeric = 1; if(nlines = readlines(lineptr, lines)) >= 0) { if (numeric) sort(lineptr, nlines, numcmp, swap); else sort(lineptr, nlines, strcmp, swap); writelines(lineptr, nlines); } else printf("input too big to sort\n"); }

Здесь strcmp, nimcmp и swap - адреса функций; так как известно, что это функции, операция & здесь не нужна совершенно аналогично тому, как она не нужна и перед именем массива. Передача адресов функций организуется компилятором.

Второй шаг состоит в модификации sort:

sort(v, n, comp, exch) /* sort strings v[0] ... v[n-1] */ char *v[]; /* into increasing order */ int n; int (*comp)(), (*exch)(); { int gap, i, j;

for(gap = n/2; gap > 0; gap /= 2) for(i = gap; i < n; i++) for(j = i-gap; j >= 0; j -= gap) { if((*comp)(v[j], v[j+gap]) <= 0) break; (*exch)(&v[j], &v[j+gap]); } }

Здесь следует обратить определенное внимание на описания. описание

int (*comp)()

говорит, что comp является указателем на функцию, которая возвращает значение типа int. Первые круглые скобки здесь необходимы; без них описание

int *comp()

говорило бы, что comp является функцией, возвращающей указатель на целые, что, конечно, совершенно другая вещь.

Использование comp в строке

if (*comp)(v[j], v[j+gap]) <= 0)

полностью согласуется с описанием: comp - указатель на функцию, *comp - сама функция, а

(*comp)(v[j], v[j+gap])

- обращение к ней. круглые скобки необходимы для правильного объединения компонентов.

Мы уже приводили функцию strcmp, сравнивающую две строки по первому численному значению:

numcmp(s1, s2) /* compare s1 and s2 numerically */ char *s1, *s2; { double atof(), v1, v2;

v1 = atof(s1); v2 = atof(s2); if(v1 < v2) return(-1); else if(v1 > v2) return(1); else return (0); }

Заключительный шаг состоит в добавлении функции swap, переставляющей два указателя. Это легко сделать, непосредственно используя то, что мы изложили ранее в этой лекции.

swap(px, py) /* interchange *px and *py */ char *px[], *py[]; { char *temp;

temp = *px; *px = *py; *py = temp; }

Имеется множество других необязательных аргументов, которые могут быть включены в программу сортировки: некоторые из них составляют интересные упражнения.

Упражнение 5-11

Модифицируйте sort таким образом, чтобы она работала с меткой -r, указывающей на сортировку в обратном (убывающем) порядке. Конечно, -r должна работать с -n.

Упражнение 5-12

Добавьте необязательный аргумент -f, объединяющий вместе прописные и строчные буквы, так чтобы различие регистров не учитывалось во время сортировки: данные из верхнего и нижнего регистров сортируются вместе, так что буква 'а' прописное и 'а' строчное оказываются соседними , а не разделенными целым алфавитом.

Упражнение 5-13

Добавьте необязательный аргумент -d ("словарное упорядочивание"), при наличии которого сравниваются только буквы, числа и пробелы. Позаботьтесь о том, чтобы эта функция работала и вместе с -f.

Упражнение 5-14

Добавьте возможность обработки полей, так чтобы можно было сортировать поля внутри строк. Каждое поле должно сортироваться в соответствии с независимым набором необязательных аргументов. (предметный указатель этой книги сортировался с помощью аргументов -df для категории указателя и с -n для номеров страниц).

Указатели - не целые

Вы, возможно, обратили внимание в предыдущих "с"-программах на довольно непринужденное отношение к копированию указателей. В общем это верно, что на большинстве машин указатель можно присвоить целому и передать его обратно, не изменив его; при этом не происходит никакого масштабирования или преобразования и ни один бит не теряется. к сожалению, это ведет к вольному обращению с функциями, возвращающими указатели, которые затем просто передаются другим функциям, - необходимые описания указателей часто опускаются. Рассмотрим, например, функцию strsave(s), которая копирует строку s в некоторое место для хранения, выделяемое посредством обращения к функции alloc, и возвращает указатель на это место. Правильно она должна быть записана так:

char *strsave(s) /* save string s somewhere */ char *s; { char *p, *alloc(); if ((p = alloc(strlen(s)+1)) != null) strcpy(p, s); return(p); }

на практике существует сильное стремление опускать описания:

*strsave(s) /* save string s somewhere */ { char *p;

if ((p = alloc(strlen(s)+1)) != null) strcpy(p, s); return(p); }

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

Указатели символов и функции

Строчная константа, как, например,

"i am a string"

является массивом символов. Компилятор завершает внутреннее представление такого массива символом \0, так что программы могут находить его конец. Таким образом, длина массива в памяти оказывается на единицу больше числа символов между двойными кавычками.

По-видимому чаще всего строчные константы появляются в качестве аргументов функций, как, например, в

printf ("hello, world\n");

когда символьная строка, подобная этой, появляется в программе, то доступ к ней осуществляется с помощью указателя символов; функция printf фактически получает указатель символьного массива.

Конечно, символьные массивы не обязаны быть только аргументами функций. Если описать message как

char *message;

то в результате оператора

message = "now is the time";

переменная message станет указателем на фактический массив символов. Это не копирование строки; здесь участвуют только указатели. В языке "C" не предусмотрены какие-либо операции для обработки всей строки символов как целого.

Мы проиллюстрируем другие аспекты указателей и массивов, разбирая две полезные функции из стандартной библиотеки ввода-вывода, которая будет рассмотрена в лекции №7.

Первая функция - это strcpy(s,t), которая копирует строку t в строку s. аргументы написаны именно в этом порядке по аналогии с операцией присваивания, когда для того, чтобы присвоить t к s обычно пишут

s = t

сначала приведем версию с массивами:

strcpy(s, t) /* copy t to s */ char s[], t[]; { int i; i = 0; while ((s[i] = t[i]) != '\0') i++; }

Для сопоставления ниже дается вариант strcpy с указателями.

strcpy(s, t) /* copy t to s; pointer version 1 */ char *s, *t; { while ((*s = *t) != '\0') { s++; t++; } }

Так как аргументы передаются по значению, функция strcpy может использовать s и t так, как она пожелает. Здесь они с удобством полагаются указателями, которые передвигаются вдоль массивов, по одному символу за шаг, пока не будет скопирован в s завершающий в t символ \0.

На практике функция strcpy была бы записана не так, как мы показали выше. Вот вторая возможность:

strcpy(s, t) /* copy t to s; pointer version 2 */ char *s, *t; { while ((*s++ = *t++) != '\0') ; }

Здесь увеличение s и t внесено в проверочную часть. Значением *t++ является символ, на который указывал t до увеличения; постфиксная операция ++ не изменяет t, пока этот символ не будет извлечен. Точно так же этот символ помещается в старую позицию s, до того как s будет увеличено. Конечный результат заключается в том, что все символы, включая завершающий \0, копируются из t в s.

И как последнее сокращение мы опять отметим, что сравнение с \0 является излишним, так что функцию можно записать в виде

strcpy(s, t) /* copy t to s; pointer version 3 */ char *s, *t; { while (*s++ = *t++) ; }

хотя с первого взгляда эта запись может показаться загадочной, она дает значительное удобство. Этой идиомой следует овладеть уже хотя бы потому, что вы с ней будете часто встречаться в "C"-программах.

Вторая функция - strcmp(s, t), которая сравнивает символьные строки s и t, возвращая отрицательное, нулевое или положительное значение в соответствии с тем, меньше, равно или больше лексикографически s, чем t. Возвращаемое значение получается в результате вычитания символов из первой позиции, в которой s и t не совпадают.

strcmp(s, t) /* return <0 if s<t, 0 if s==t, >0 if s>t */ char s[], t[]; { int i;

i = 0; while (s[i] == t[i]) if (s[i++] == '\0') return(0); return(s[i]-t[i]); }

Вот версия strcmp с указателями:

strcmp(s, t) /* return <0 if s<t, 0 if s==t, >0 if s>t */ char *s, *t; { for ( ; *s == *t; s++, t++) if (*s == '\0') return(0); return(*s-*t); }

так как ++ и -- могут быть как постфиксными, так и префиксными операциями, встречаются другие комбинации * и ++ и --, хотя и менее часто.

Например

*++p

увеличивает p до извлечения символа, на который указывает p, а

*--p

сначала уменьшает p.

Упражнение 5-2

Напишите вариант с указателями функции strcat из лекции №2: strcat(s, t) копирует строку t в конец s.

Упражнение 5-3

Напишите макрос для strcpy.

Упражнение 5-4

Перепишите подходящие программы из предыдущих лекций и упражнений, используя указатели вместо индексации массивов. Хорошие возможности для этого предоставляют функции getline /лекции 1 и №4/, atoi, itoa и их варианты /лекция №2, №3 и №4/, reverse /лекция №3/, index и getop /лекция №4/.

Массивы структур

структуры особенно подходят для управления массивами связанных переменных. Рассмотрим, например, программу подсчета числа вхождений каждого ключевого слова языка "C". Нам нужен массив символьных строк для хранения имен и массив целых для подсчета. одна из возможностей состоит в использовании двух параллельных массивов keyword и keycount:

char *keyword [nkeys]; int keycount [nkeys];

Но сам факт, что массивы параллельны, указывает на возможность другой организации. Каждое ключевое слово здесь по существу является парой:

char *keyword; int keycount;

и, следовательно, имеется массив пар. описание структуры

struct key { char *keyword; int keycount; } keytab [nkeys];

определяет массив keytab структур такого типа и отводит для них память. Каждый элемент массива является структурой. Это можно было бы записать и так:

struct key { char *keyword; int keycount; }; struct key keytab [nkeys];

Так как структура keytab фактически содержит постоянный набор имен, то легче всего инициализировать ее один раз и для всех членов при определении. Инициализация структур вполне аналогична предыдущим инициализациям - за определением следует заключенный в фигурные скобки список инициализаторов:

struct key { char *keyword; int keycount; } keytab[] = { "break", 0, "case", 0, "char", 0, "continue", 0, "default", 0, /* ... */ "unsigned", 0, "while", 0 };

Инициализаторы перечисляются парами соответственно членам структуры. Было бы более точно заключать в фигурные скобки инициализаторы для каждой "строки" или структуры следующим образом:

{ "break", 0 }, { "case", 0 }, . . .

Но когда инициализаторы являются простыми переменными или символьными строками и все они присутствуют, то во внутренних фигурных скобках нет необходимости. Как обычно, компилятор сам вычислит число элементов массива keytab, если инициализаторы присутствуют, а скобки [] оставлены пустыми.

Программа подсчета ключевых слов начинается с определения массива keytab. Ведущая программа читает свой файл ввода, последовательно обращаясь к функции getword, которая извлекает из ввода по одному слову за обращение. Каждое слово ищется в массиве keytab с помощью варианта функции бинарного поиска, написанной нами в лекции №3. (Конечно, чтобы эта функция работала, список ключевых слов должен быть расположен в порядке возрастания).

#define maxword 20

main() /* count "c" keywords */ { int n, t; char word[maxword];

while ((t = getword(word,maxword)) != EOF) if (t == letter) if((n = binary(word,keytab,nkeys)) >= 0) keytab[n].keycount++; for (n =0; n < nkeys; n++) if (keytab[n].keycount > 0) printf("%4d %s\n", keytab[n].keycount, keytab[n].keyword); } binary(word, tab, n) /* find word in tab[0]...tab[n-1] */ char *word; struct key tab[]; int n; { int low, high, mid, cond;

low = 0; high = n - 1; while (low <= high) { mid = (low+high) / 2; if((cond = strcmp(word, tab[mid].keyword)) < 0) high = mid - 1; else if (cond > 0) low = mid + 1; else return (mid); } return(-1); }

Мы вскоре приведем функцию getword; пока достаточно сказать, что она возвращает letter каждый раз, как она находит слово, и копирует это слово в свой первый аргумент.

Величина nkeys - это количество ключевых слов в массиве keytab. Хотя мы можем сосчитать это число вручную, гораздо легче и надежнее поручить это машине, особенно в том случае, если список ключевых слов подвержен изменениям. Одной из возможностей было бы закончить список инициализаторов указанием на нуль и затем пройти в цикле сквозь массив keytab, пока не найдется конец.

Но, поскольку размер этого массива полностью определен к моменту компиляции, здесь имеется более простая возможность. Число элементов просто есть

size of keytab / size of struct key

дело в том, что в языке "C" предусмотрена унарная операция sizeof, выполняемая во время компиляции, которая позволяет вычислить размер любого объекта.

Выражение

sizeof(object)

выдает целое, равное размеру указанного объекта. (Размер определяется в неспецифицированных единицах, называемых "байтами", которые имеют тот же размер, что и переменные типа char). Объект может быть фактической переменной, массивом и структурой, или именем основного типа, как int или double, или именем производного типа, как структура. В нашем случае число ключевых слов равно размеру массива, деленному на размер одного элемента массива. Это вычисление используется в утверждении #define для установления значения nkeys:



#define nkeys (sizeof(keytab) / sizeof(struct key))

Теперь перейдем к функции getword. Мы фактически написали более общий вариант функции getword, чем необходимо для этой программы, но он не на много более сложен. функция getword возвращает следующее "слово" из ввода, где словом считается либо строка букв и цифр, начинающихся с буквы, либо отдельный символ. тип объекта возвращается в качестве значения функции; это - letter, если найдено слово, EOF для конца файла и сам символ, если он не буквенный.

getword(w, lim) /* get next word from input */ char *w; int lim; { int c, t; if (type(c=*w++=getch()) !=letter) { *w='\0'; return(c); }

while (--lim > 0) { t = type(c = *w++ = getch()); if (t ! = letter && t ! = digit) { ungetch(c); break; } } *(w-1) - '\0'; return(letter); }

функция getword использует функции getch и ungetch, которые мы написали в лекции №4: когда набор алфавитных символов прерывается, функция getword получает один лишний символ. В результате вызова ungetch этот символ помещается назад во ввод для следующего обращения.

функция getword обращается к функции type для определения типа каждого отдельного символа из файла ввода. Вот вариант, справедливый только для алфавита ASCII.

type(c) /* return type of ascii character */ int c; { if (c>= 'a' && c<= 'z' || c>= 'a' && c<= 'z') return(letter); else if (c>= '0' && c<= '9') return(digit); else return(c); }

Символические константы letter и digit могут иметь любые значения, лишь бы они не вступали в конфликт с символами, отличными от буквенно-цифровых, и с EOF; очевидно возможен следующий выбор

#define letter 'a' #define digit '0'

функция getword могла бы работать быстрее, если бы обращения к функции type были заменены обращениями к соответствующему массиву type[ ]. В стандартной библиотеке языка "C" предусмотрены макросы isalpha и isdigit, действующие необходимым образом.

Упражнение 6-1

Сделайте такую модификацию функции getword и оцените, как изменится скорость работы программы.

Упражнение 6-2

Напишите вариант функции type, не зависящий от конкретного набора символов.

Упражнение 6-3

Напишите вариант программы подсчета ключевых слов, который бы не учитывал появления этих слов в заключенных в кавычки строках.

Объединения

Oбъединения - это переменная, которая в различные моменты времени может содержать объекты разных типов и размеров, причем компилятор берет на себя отслеживание размера и требований выравнивания. Объединения представляют возможность работать с различными видами данных в одной области памяти, не вводя в программу никакой машинно-зависимой информации.

В качестве примера, снова из символьной таблицы компилятора, предположим, что константы могут быть типа int, float или быть указателями на символы. значение каждой конкретной константы должно храниться в переменной соответствующего типа, но все же для управления таблицей самым удобным было бы, если это значение занимало бы один и тот же объем памяти и хранилось в том же самом месте независимо от его типа. это и является назначением объединения - выделить отдельную переменную, в которой можно законно хранить любую одну из переменных нескольких типов. Как и в случае полей, синтаксис основывается на структурах.

union u_tag { int ival; float fval; char *pval; } uval;

переменная uval будет иметь достаточно большой размер, чтобы хранить наибольший из трех типов, независимо от машины, на которой осуществляется компиляция, - программа не будет зависить от характеристик аппаратных средств. Любой из этих трех типов может быть присвоен uvar и затем использован в выражениях, пока такое использование совместимо: извлекаемый тип должен совпадать с последним помещенным типом. Дело программиста - следить за тем, какой тип хранится в объединении в данный момент; если что-либо хранится как один тип, а извлекается как другой, то результаты будут зависеть от используемой машины.

Синтаксически доступ к членам объединения осуществляется следующим образом:

имя объединения.член --------------------

или

указатель объединения ->член ----------------------------

то есть точно так же, как и в случае структур. если для отслеживания типа, хранимого в данный момент в uval, используется переменная utype, то можно встретить такой участок программы:

Определение типа

В языке "C" предусмотрена возможность, называемая typedef для введения новых имен для типов данных. Например, описание

typedef int length;

делает имя length синонимом для int. "Тип" length может быть использован в описаниях, переводов типов и т.д. Точно таким же образом, как и тип int:

length len, maxlen; length *lengths[];

Аналогично описанию

typedef char *string;

делает string синонимом для char*, то есть для указателя на символы, что затем можно использовать в описаниях вида

string p, lineptr[lines], alloc();

Обратите внимание, что объявляемый в конструкции typedef тип появляется в позиции имени переменной, а не сразу за словом typedef. Синтаксически конструкция typedef подобна описаниям класса памяти extern, static и т. д. Мы также использовали прописные буквы, чтобы яснее выделить имена.

В качестве более сложного примера мы используем конструкцию typedef для описания узлов дерева, рассмотренных ранее в этой лекции:

typedef struct tnode { /* the basic node */ char *word; /* points to the text */ int count; /* number of occurrences */ struct tnode *left; /* left child */ struct tnode *right; /* right child */ } treenode, *treeptr;

В результате получаем два новых ключевых слова: treenode (структура) и treeptr (указатель на структуру). Тогда функцию talloc можно записать в виде

treeptr talloc() { char *alloc(); return((treeptr) alloc(sizeof(treenode))); }

Необходимо подчеркнуть, что описание typedef не приводит к созданию нового в каком-либо смысле типа; оно только добавляет новое имя для некоторого существующего типа. При этом не возникает и никакой новой семантики: описанные таким способом переменные обладают точно теми же свойствами, что и переменные, описанные явным образом. По существу конструкция typedef сходна с #define за исключением того, что она интерпретируется компилятором и потому может осуществлять подстановки текста, которые выходят за пределы возможностей макропроцессора языка "C". Например,

typedef int (*pfi) ();

Поиск в таблице

Для иллюстрации дальнейших аспектов использования структур в этом разделе мы напишем программу, представляющую собой содержимое пакета поиска в таблице. Эта программа является типичным представителем подпрограмм управления символьными таблицами макропроцессора или компилятора. Рассмотрим, например, оператор #define языка "C". Когда встречается строка вида

#define yes 1

то имя yes и заменяющий текст 1 помещаются в таблицу. Позднее, когда имя yes появляется в операторе вида

inword = yes;

Oно должно быть замещено на 1.

Имеются две основные процедуры, которые управляют именами и заменяющими их текстами. функция install(s,t) записывает имя s и заменяющий текст t в таблицу; здесь s и t просто символьные строки. функция lookup(s) ищет имя s в таблице и возвращает либо указатель того места, где это имя найдено, либо null, если этого имени в таблице не оказалось.

При этом используется поиск по алгоритму хеширования - поступающее имя преобразуется в маленькое положительное число, которое затем используется для индексации массива указателей. Элемент массива указывает на начало цепочных блоков, описывающих имена, которые имеют это значение хеширования. Если никакие имена при хешировании не получают этого значения, то элементом массива будет null.

Блоком цепи является структура, содержащая указатели на соответствующее имя, на заменяющий текст и на следующий блок в цепи. Нулевой указатель следующего блока служит признаком конца данной цепи.

struct nlist { /* basic table entry */ char *name; char *def; struct nlist *next; /* next entry in chain */ };

Массив указателей это просто

define hashsize 100 tatic struct nlist *hashtab[hashsize] /* pointer table */

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

hash(s) /* form hash value for string */ char *s; { int hashval;

for (hashval = 0; *s != '\0'; ) hashval += *s++; return(hashval % hashsize); }

В результате процесса хеширования выдается начальный индекс в массиве hashtab; если данная строка может быть где-то найдена, то именно в цепи блоков, начало которой указано там. Поиск осуществляется функцией lookup. Если функция lookup находит, что данный элемент уже присутствует, то она возвращает указатель на него; если нет, то она возвращает null.

struct nlist *lookup(s) /* look for s in hashtab */ char *s; { struct nlist *np; } for (np = hashtab[hash(s)]; np != null;np=np->next) if (strcmp(s, np->name) == 0) return(np); /* found it */ return(null); /* not found */

функция install использует функцию lookup для определения, не присутствует ли уже вводимое в данный момент имя; если это так, то новое определение должно вытеснить старое. В противном случае создается совершенно новый элемент. Если по какой-либо причине для нового элемента больше нет места, то функция install возвращает null.

struct nlist *install(name, def) /* put (name, def) */ char *name, *def; { struct nlist *np, *lookup(); char *strsave(), *alloc(); int hashval;

if((np = lookup(name)) == null) \( /* not found */ np = (struct nlist *) alloc(sizeof(*np)); if (np == null) return(null); if ((np->name = strsave(name)) == null) return(null); hashval = hash(np->name); np->next = hashtab[hashval]; hashtab[hashval] = np; } else /* already there */ free((np->def);/* free previous definition */ if ((np->def = strsave(def)) == null) return (null); return(np); }

функция strsave просто копирует строку, указанную в качестве аргумента, в место хранения, полученное в результате обращения к функции alloc. Мы уже привели эту функцию в лекции №5. Так как обращение к функции alloc и free могут происходить в любом порядке и в связи с проблемой выравнивания, простой вариант функции alloc из лекции №5 нам больше не подходит; смотрите лекции №7 и лекции №8.

Упражнение 6-7

Напишите процедуру, которая будет удалять имя и определение из таблицы, управляемой функциями lookup и install.

Упражнение 6-8

Разработайте простую, основанную на функциях этого раздела, версию процессора для обработки конструкций #define, пригодную для использования с "C"-программами. Вам могут также оказаться полезными функции getchar и ungetch.

Поля

Когда вопрос экономии памяти становится очень существенным, то может оказаться необходимым помещать в одно машинное слово несколько различных объектов; одно из особенно распространенных употреблений - набор однобитовых признаков в применениях, подобных символьным таблицам компилятора. Внешне обусловленные форматы данных, такие как интерфейсы аппаратных средств также зачастую предполагают возможность получения слова по частям.

Представьте себе фрагмент компилятора, который работает с символьной таблицей. С каждым идентификатором программы связана определенная информация, например, является он или нет ключевым словом, является ли он или нет внешним и/или статическим и т.д. Самый компактный способ закодировать такую информацию - поместить набор однобитовых признаков в отдельную переменную типа char или int.

Обычный способ, которым это делается, состоит в определении набора "масок", отвечающих соответствующим битовым позициям, как в

#define keyword 01 #define external 02 #define static 04

(числа должны быть степенями двойки). Тогда обработка битов сведется к "жонглированию битами" с помощью операций сдвига, маскирования и дополнения, описанных нами в лекции №2.

Некоторые часто встречающиеся идиомы:

flags |= external | static;

включает биты external и static в flags, в то время как

flags &= \^(еxternal | static);

их выключает, а

if ((flags & (external | static)) == 0) ...

истинно, если оба бита выключены.

Хотя этими идиомами легко овладеть, язык "C" в качестве альтернативы предлагает возможность определения и обработки полей внутри слова непосредственно, а не посредством побитовых логических операций. Поле - это набор смежных битов внутри одной переменной типа int. Синтаксис определения и обработки полей основывается на структурах. Например, символьную таблицу конструкций #define, приведенную выше, можно бы было заменить определением трех полей:

struct { unsigned is_keyword : 1; unsigned is_extern : 1; unsigned is_static : 1; } flags;

Здесь определяется переменная с именем flags, которая содержит три 1-битовых поля. Следующее за двоеточием число задает ширину поля в битах. Поля описаны как unsigned, чтобы подчеркнуть, что они действительно будут величинами без знака.

На отдельные поля можно ссылаться, как flags.is_static, flags. is_extern, flags.is_keyword И т.д., то есть точно так же, как на другие члены структуры. Поля ведут себя подобно небольшим целым без знака и могут участвовать в арифметических выражениях точно так же, как и другие целые. Таким образом, предыдущие примеры более естественно переписать так:

flags.is_extern = flags.is_static = 1;

для включения битов;

flags.is_extern = flags.is_static = 0;

для выключения битов;

if (flags.is_extern == 0 &&flags.is_static == 0)...

для их проверки.

Поле не может перекрывать границу int; если указанная ширина такова, что это должно случиться, то поле выравнивается по границе следующего int. Полям можно не присваивать имена; неименованные поля (только двоеточие и ширина) используются для заполнения свободного места. Чтобы вынудить выравнивание на границу следующего int, можно использовать специальную ширину 0.

При работе с полями имеется ряд моментов, на которые следует обратить внимание. По-видимому наиболее существенным является то, что отражая природу различных аппаратных средств, распределение полей на некоторых машинах осуществляется слева направо, а на некоторых справа налево. Это означает, что хотя поля очень полезны для работы с внутренне определеными структурами данных, при разделении внешне определяемых данных следует тщательно рассматривать вопрос о том, какой конец поступает первым.

Другие ограничения, которые следует иметь в виду: поля не имеют знака; они могут храниться только в переменных типа int (или, что эквивалентно, типа unsigned); они не являются массивами; они не имеют адресов, так что к ним не применима операция &.

on_load_lecture()



Дальше »



  Если Вы заметили ошибку - сообщите нам.  

Структуры

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

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

структуры оказываются полезными при организации сложных данных особенно в больших программах, поскольку во многих ситуациях они позволяют сгруппировать связанные данные таким образом, что с ними можно обращаться, как с одним целым, а не как с отдельными объектами. В этой лекции мы постараемся продемонстрировать то, как используются структуры. программы, которые мы для этого будем использовать, больше, чем многие другие в этой книге, но все же достаточно умеренных размеров.

Структуры и функции

В языке "C" существует ряд ограничений на использование структур. Обязательные правила заключаются в том, что единственные операции, которые вы можете проводить со структурами, состоят в определении ее адреса с помощью операции & и доступе к одному из ее членов. Это влечет за собой то, что структуры нельзя присваивать или копировать как целое, и что они не могут быть переданы функциям или возвращены ими. (В последующих версиях эти ограничения будут сняты). На указатели структур эти ограничения однако не накладываются, так что структуры и функции все же могут с удобством работать совместно. И наконец, автоматические структуры, как и автоматические массивы, не могут быть инициализированы; инициализация возможна только в случае внешних или статических структур.

Давайте разберем некоторые из этих вопросов, переписав с этой целью функции преобразования даты из предыдущей лекции так, чтобы они использовали структуры. Так как правила запрещают непосредственную передачу структуры функции, то мы должны либо передавать отдельно компоненты, либо передать указатель всей структуры. Первая возможность демонстрируется на примере функции day_of_year, как мы ее написали в лекции №5:

d.yearday = day_of_year(d.year, d.month, d.day);

другой способ состоит в передаче указателя. если мы опишем hiredate как

struct date hiredate;

и перепишем day_of_year нужным образом, мы сможем тогда написать

hiredate yearday = day_of_year(&hiredate);

передавая указатель на hiredate функции day_of_year. функция должна быть модифицирована, потому что ее аргумент теперь является указателем, а не списком переменных.

day_of_year(pd) /* set day of year from month, day */ struct date *pd; { int i, day, leap;

day = pd->day; leap = pd->year % 4 == 0 && pd->year % 100 != 0 || pd->year % 400 == 0; for (i =1; i < pd->month; i++) day += day_tab[leap][i]; return(day); }

описание

struct date *pd;

говорит, что pd является указателем структуры типа date. Запись, показанная на примере

pd->year

является новой. Если p - указатель на структуру, то

p-> член структуры ------------------

обращается к конкретному члену. (Операция -> - это знак минус, за которым следует знак ">".)

Так как pd указывает на структуру, то к члену year можно обратиться и следующим образом

(*pd).year

но указатели структур используются настолько часто, что запись -> оказывается удобным сокращением. круглые скобки в (*pd).year необходимы, потому что операция указания члена структуры старше , чем *. Обе операции, "->" и ".", ассоциируются слева направо, так что конструкции слева и справа эквивалентны

p->q->memb (p->q)->memb emp.birthdate.month (emp.birthdate).month

Для полноты ниже приводится другая функция, month_day, переписанная с использованием структур.

month_day(pd) /* set month and day from day of year */ struct date *pd; { int i, leap;

leap = pd->year % 4 == 0 && pd->year % 100 != 0 || pd->year % 400 == 0; pd->day = pd->yearday; for (i = 1; pd->day > day_tab[leap][i]; i++) pd->day -= day_tab[leap][i]; pd->month = i; }

Операции работы со структурами "->" и "." наряду со () для списка аргументов и [] для индексов находятся на самом верху иерархии старшинства операций и, следовательно, связываются очень крепко. Если, например, имеется описание

struct { int x; int *y; } *p;

то выражение

++p->x

увеличивает x, а не p, так как оно эквивалентно выражению ++(p->х). Для изменения порядка выполнения операций можно использовать круглые скобки: (++p)->x увеличивает p до доступа к x, а (p++)->x увеличивает p после. (Круглые скобки в последнем случае необязательны. Почему?)

Совершенно аналогично *p->y извлекает то, на что указывает y; *p->y++ увеличивает y после обработки того, на что он указывает (точно так же, как и *s++); (*p->y)++ увеличивает то, на что указывает y; *p++->y увеличивает p после выборки того, на что указывает y.

on_load_lecture()

Структуры, ссылающиеся на себя

Предположим, что нам надо справиться с более общей задачей, состоящей в подсчете числа появлений всех слов в некотором файле ввода. Так как список слов заранее не известен, мы не можем их упорядочить удобным образом и использовать бинарный поиск. Мы даже не можем осуществлять последовательный просмотр при поступлении каждого слова, с тем чтобы установить, не встречалось ли оно ранее; такая программа будет работать вечно. (Более точно, ожидаемое время работы растет как квадрат числа вводимых слов). Как же нам организовать программу, чтобы справиться со списком произвольных слов?

Одно из решений состоит в том, чтобы все время хранить массив поступающих до сих пор слов в упорядоченном виде, помещая каждое слово в нужное место по мере их поступления. Oднако это не следует делать, перемещая слова в линейном массиве, - это также потребует слишком много времени. Вместо этого мы используем структуру данных, называемую двоичным деревом.

Каждому новому слову соответствует один "узел" дерева; каждый узел содержит:

указатель текста слова ---------------------- счетчик числа появлений ----------------------- указатель узла левого потомка ----------------------------- указатель узла правого потомка ------------------------------

Никакой узел не может иметь более двух детей; возможно отсутствие детей или наличие только одного потомка.

Узлы создаются таким образом, что левое поддерево каждого узла содержит только те слова, которые меньше слова в этом узле, а правое поддерево только те слова, которые больше. Чтобы определить, находится ли новое слово уже в дереве, начинают с корня и сравнивают новое слово со словом, хранящимся в этом узле. Если слова совпадают, то вопрос решается утвердительно. Если новое слово меньше слова в дереве, то переходят к рассмотрению левого потомка; в противном случае исследуется правый потомок. Если в нужном направлении потомок отсутствует, то значит новое слово не находится в дереве и место этого недостающего потомка как раз и является местом, куда следует поместить новое слово. Поскольку поиск из любого узла приводит к поиску одного из его потомков, то сам процесс поиска по существу является рекурсивным. В соответствии с этим наиболее естественно использовать рекурсивные процедуры ввода и вывода.

Возвращаясь назад к описанию узла, ясно, что это будет структура с четырьмя компонентами:

struct tnode { /* the basic node */ char *word; /* points to the text */ int count; /* number of occurrences */ struct tnode *left; /* left child */ struct tnode *right; /* right child */ };

Это "рекурсивное" описание узла может показаться рискованным, но на самом деле оно вполне корректно. структура не имеет права содержать ссылку на саму себя, но

struct tnode *left;

описывает left как указатель на узел, а не как сам узел.

Текст самой программы оказывается удивительно маленьким, если, конечно, иметь в распоряжении набор написанных нами ранее процедур, обеспечивающих нужные действия. Мы имеем в виду функцию getword для извлечения каждого слова из файла ввода и функцию alloc для выделения места для хранения слов.

Ведущая программа просто считывает слова с помощью функции getword и помещает их в дерево, используя функцию tree.

#define maxword 20 main() /* word freguency count */ { struct tnode *root, *tree(); char word[maxword]; int t; root = null; while ((t = getword(word, maxword)) |= EOF) if (t == letter) root = tree(root, word); treeprint(root); }

функция tree сама по себе проста. Слово передается функцией main к верхнему уровню (корню) дерева. На каждом этапе это слово сравнивается со словом, уже хранящимся в этом узле, и с помощью рекурсивного обращения к tree просачивается вниз либо к левому, либо к правому поддереву. В конце концов это слово либо совпадает с каким-то словом, уже находящимся в дереве (в этом случае счетчик увеличивается на единицу), либо программа натолкнется на нулевой указатель, свидетельствующий о необходимости создания и добавления к дереву нового узла. В случае создания нового узла функция tree возвращает указатель этого узла, который помещается в родительский узел.

struct tnode *tree(p, w) /* install w at or below p */ struct tnode *p; char *w; { struct tnode *talloc(); char *strsave(); int cond; if (p == null) { /* a new word has arrived */ p == talloc(); /* make a new node */ p->word = strsave(w); p->count = 1; p->left = p->right = null; } else if ((cond = strcmp(w, p->word)) == 0) p->count++; /* repeated word */ else if (cond < 0)/* lower goes into left subtree */ p->left = tree(p->left, w); else /* greater into right subtree */ p->right = tree(p->right, w); return(p); }



Память для нового узла выделяется функцией talloc, являющейся адаптацией для данного случая функции alloc, написанной нами ранее. Она возвращает указатель свободного пространства, пригодного для хранения нового узла дерева. (Мы вскоре обсудим это подробнее). Новое слово копируется функцией strsave в скрытое место, счетчик инициализируется единицей, и указатели обоих потомков полагаются равными нулю. Эта часть программы выполняется только при добавлении нового узла к ребру дерева. Мы здесь опустили проверку на ошибки возвращаемых функций strsave и talloc значений (что неразумно для практически работающей программы).

функция treeprint печатает дерево, начиная с левого поддерева; в каждом узле сначала печатается левое поддерево (все слова, которые младше этого слова), затем само слово, а затем правое поддерево (все слова, которые старше). Если вы неуверенно оперируете с рекурсией, нарисуйте дерево сами и напечатайте его с помощью функции treeprint; это одна из наиболее ясных рекурсивных процедур, которую можно найти.

treeprint (p) /* print tree p recursively */ struct tnode *p; { if (p != null) { treeprint (p->left); printf("%4d %s\n", p->count, p->word); treeprint (p->right); } }

Практическое замечание: если дерево становится "несбалансированным" из-за того, что слова поступают не в случайном порядке, то время работы программы может расти слишком быстро. В худшем случае, когда поступающие слова уже упорядочены, настоящая программа осуществляет дорогостоящую имитацию линейного поиска. Существуют различные обобщения двоичного дерева, особенно 2-3 деревья и avl деревья, которые не ведут себя так "в худших случаях", но мы не будем здесь на них останавливаться.

Прежде чем расстаться с этим примером, уместно сделать небольшое отступление в связи с вопросом о распределении памяти. Ясно, что в программе желательно иметь только один распределитель памяти, даже если ему приходится размещать различные виды объектов. Но если мы хотим использовать один распределитель памяти для обработки запросов на выделение памяти для указателей на переменные типа char и для указателей на struct tnode, то при этом возникают два вопроса. Первый: как выполнить то существующее на большинстве реальных машин ограничение, что объекты определеных типов должны удовлетворять требованиям выравнивания (например, часто целые должны размещаться в четных адресах)? Второй: как организовать описания, чтобы справиться с тем, что функция alloc должна возвращать различные виды указателей ?

Вообще говоря, требования выравнивания легко выполнить за счет выделения некоторого лишнего пространства, просто обеспечив то, чтобы распределитель памяти всегда возвращал указатель, удовлетворяющий всем ограничениям выравнивания. Например, на PDP-11 достаточно, чтобы функция alloc всегда возвращала четный указатель, поскольку в четный адрес можно поместить любой тип объекта. Единственный расход при этом - лишний символ при запросе на нечетную длину. Аналогичные действия предпринимаются на других машинах. Таким образом, реализация alloc может не оказаться переносимой, но ее использование будет переносимым. функция alloc из лекции №5

Указатели на структуры

Чтобы проиллюстрировать некоторые соображения, связанные с использованием указателей и массивов структур, давайте снова составим программу подсчета ключевых строк, используя на этот раз указатели, а не индексы массивов.

Внешнее описание массива keytab не нужно изменять, но функции main и binary требуют модификации.

main() /* count c keyword; pointer version */ { int t; char word[maxword]; struct key *binary(), *p; while ((t = getword(word, maxword;) !=EOF) if (t==letter) if ((p=binary(word,keytab,nkeys)) !=null) p->keycount++; for (p=keytab; p>keytab + nkeys; p++) if (p->keycount > 0) printf("%4d %s/n", p->keycount, p->keyword); } struct key *binary(word, tab, n) /* find word */ char *word /* in tab[0]...tab[n-1] */ struct key tab []; int n; { int cond; struct key *low = &tab[0]; struct key *high = &tab[n-1]; struct key *mid; while (low <= high) { mid = low + (high-low) / 2; if ((cond = strcmp(word, mid->keyword)) < 0) high = mid - 1; else if (cond > 0) low = mid + 1; else return(mid); } return(null); }

Здесь имеется несколько моментов, которые стоит отметить. Во-первых, описание функции binary должно указывать, что она возвращает указатель на структуру типа key, а не на целое; это объявляется как в функции main, так и в binary. Если функция binary находит слово, то она возвращает указатель на него; если же нет, она возвращает null.

Во-вторых, все обращения к элементам массива keytab осуществляются через указатели. Это влечет за собой одно существенное изменение в функции binary: средний элемент больше нельзя вычислять просто по формуле

mid = (low + high) / 2

потому что сложение двух указателей не дает какого-нибудь полезного результата (даже после деления на 2) и в действительности является незаконным. Эту формулу надо заменить на

mid = low + (high-low) / 2

в результате которой mid становится указателем на элемент, расположенный посередине между low и high.

Вам также следует разобраться в инициализации low и high. указатель можно инициализировать адресом ранее определенного объекта; именно как мы здесь и поступили.

В функции main мы написали

Доступ к файлам

Все до сих пор написанные программы читали из стандартного ввода и писали в стандартный вывод, относительно которых мы предполагали, что они магическим образом предоставлены программе местной операционной системой.

Следующим шагом в вопросе ввода-вывода является написание программы, работающей с файлом, который не связан заранее с программой. Одной из программ, которая явно демонстрирует потребность в таких операциях, является cat, которая объединяет набор из нескольких именованных файлов в стандартный вывод. Программа cat используется для вывода файлов на терминал и в качестве универсального сборщика ввода для программ, которые не имеют возможности обращаться к файлам по имени. Например, команда

cat x.c,y.c

печатает содержимое файлов x.c и y.c в стандартный вывод.

Вопрос состоит в том, как организовать чтение из именованных файлов, т.е., как связать внешние имена, которыми мыслит пользователь, с фактически читающими данные операторами.

Эти правила просты. Прежде чем можно считывать из некоторого файла или записывать в него, этот файл должен быть открыт с помощью функции fopen из стандартной библиотеки. функция fopen берет внешнее имя (подобное x.c или y.c), проводит некоторые обслуживающие действия и переговоры с операционной системой (детали которых не должны нас касаться) и возвращает внутреннее имя, которое должно использоваться при последующих чтениях из файла или записях в него.

Это внутреннее имя, называемое "указателем файла", фактически является указателем структуры, которая содержит информацию о файле, такую как место размещения буфера, текущая позиция символа в буфере, происходит ли чтение из файла или запись в него и тому подобное. Пользователи не обязаны знать эти детали, потому что среди определений для стандартного ввода-вывода, получаемых из файла stdio.h, содержится определение структуры с именем file. Единственное необходимое для указателя файла описание демонстрируется примером:

file *fopen(), *fp;

Здесь говорится, что fp является указателем на file и fopen возвращает указатель на file. Oбратите внимание, что file является именем типа, подобным int, а не ярлыку структуры; это реализовано как typedef. (Подробности того, как все это работает на системе UNIX, приведены в лекции №8).

Фактическое обращение к функции fopen в программе имеет вид:

fp=fopen(name,mode);

Первым аргументом функции fopen является "имя" файла, которое задается в виде символьной строки. Второй аргумент mode("режим") также является символьной строкой, которая указывает, как этот файл будет использоваться. Допустимыми режимами являются: чтение ("r"), запись ("w") и добавление ("a").

Если вы откроете файл, который еще не существует, для записи или добавления, то такой файл будет создан (если это возможно).

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

Другой необходимой вещью является способ чтения или записи, если файл уже открыт. Здесь имеется несколько возможностей, из которых getc и putc являются простейшими. функция getc возвращает следующий символ из файла; ей необходим указатель файла, чтобы знать, из какого файла читать. Таким образом,

c=getc(fp)

помещает в "C" следующий символ из файла, указанного посредством fp, и EOF, если достигнут конец файла.

функция putc, являющаяся обращением к функции getc,

putc(c,fp)

помещает символ "c" в файл fp и возвращает "c". Подобно функциям getchar и putchar, getc и putc могут быть макросами, а не функциями.

При запуске программы автоматически открываются три файла, которые снабжены определеными указателями файлов. Этими файлами являются стандартный ввод, стандартный вывод и стандартный вывод ошибок; соответствующие указатели файлов называются stdin, stdout и stderr. Обычно все эти указатели связаны с терминалом, но stdin и stdout могут быть перенаправлены на файлы или в поток (pipe), как описывалось в разделе 7.2. лекции №7.

функции getchar и putchar могут быть определены в терминалах getc, putc, stdin и stdout следующим образом: #define getchar() getc(stdin) #define putchar(c) putc(c, stdout). При работе с файлами для форматного ввода и вывода можно использовать функции fscanf и fprintf. Они идентичны функциям scanf и printf, за исключением того, что первым аргументом является указатель файла, определяющий тот файл, который будет читаться или куда будет вестись запись; управляющая строка будет вторым аргументом.

Покончив с предварительными замечаниями, мы теперь в состоянии написать программу cat для конкатенации файлов. Используемая здесь основная схема оказывается удобной во многих программах: если имеются аргументы в командной строке, то они обрабатываются последовательно. Если такие аргументы отсутствуют, то обрабатывается стандартный ввод. Это позволяет использовать программу как самостоятельно, так и как часть большей задачи.

Форматное преобразование в памяти

От функции scanf и printf происходят функции sscanf и sprintf, которые осуществляют аналогичные преобразования, но оперируют со строкой, а не с файлом. Обращения к этим функциям имеют вид:

sprintf(string, control, arg1, arg2, ...) sscanf(string, control, arg1, arg2, ...)

Как и раньше , функция sprintf преобразует свои аргументы arg1, arg2 и т.д. В соответствии с форматом, указанным в control, но помещает результаты в string, а не в стандартный вывод. Kонечно, строка string должна быть достаточно велика, чтобы принять результат. Например, если name - это символьный массив, а n - целое, то

sprintf(name, "temp%d", n);

создает в name строку вида tempnnn, где nnn - значение n.

функция sscanf выполняет обратные преобразования - она просматривает строку string в соответствии с форматом в аргументе control и помещает результирующие значения в аргументы arg1, arg2 и т.д. Эти аргументы должны быть указателями. В результате обращения

sscanf(name, "temp%d", &n);

переменная n получает значение строки цифр, следующих за temp в name.

Упражнение 7-2

Перепишите настольный калькулятор из лекции №4, используя для ввода и преобразования чисел scanf и/или sscanf.

Форматный ввод - функция SCANF

Осуществляющая ввод функция scanf является аналогом printf и позволяет проводить в обратном направлении многие из тех же самых преобразований. функция

scanf(control, arg1, arg2, ...)

читает символы из стандартного ввода, интерпретирует их в соответствии с форматом, указанном в аргументе control, и помещает результаты в остальные аргументы. Управляющий аргумент описывается ниже; другие аргументы, каждый из которых должен быть указателем, определяют, куда следует поместить соответствующим образом преобразованный ввод.

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

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

Спецификация преобразования управляет преобразованием следующего поля ввода. Нормально результат помещается в переменную, которая указывается соответствующим аргументом. Если, однако , с помощью символа * указано подавление присваивания, то это поле ввода просто пропускается и никакого присваивания не производится. Поле ввода определяется как строка символов, которые отличны от символов простых промежутков; оно продолжается либо до следующего символа пустого промежутка, либо пока не будет исчерпана ширина поля, если она указана. Отсюда следует, что при поиске нужного ей ввода, функция scanf будет пересекать границы строк, поскольку символ новой строки входит в число пустых промежутков.

Символ преобразования определяет интерпретацию поля ввода; согласно требованиям основанной на вызове по значению семантики языка "с" соответствующий аргумент должен быть указателем. Допускаются следующие символы преобразования:

d - на вводе ожидается десятичное целое; соответствующий аргумент должен быть указателем на целое. o - На вводе ожидается восьмеричное целое (с лидирующим нулем или без него); соответствующий аргумент должен быть указателем на целое. x - На вводе ожидается шестнадцатеричное целое (с лидирующими 0x или без них); соответствующий аргумент должен быть указателем на целое. h - На вводе ожидается целое типа short; соответствующий аргумент должен быть указателем на целое типа short. c - Ожидается отдельный символ; соответствующий аргумент должен быть указателем на символы; следующий вводимый символ помещается в указанное место. Обычный пропуск сим- волов пустых промежутков в этом случае подавляется; для чтения следующего символа, который не является символом пустого промежутка, пользуйтесь спецификацией преобразования %1s. s - Ожидается символьная строка; соответствующий аргумент должен быть указателем символов, который указывает на массив символов, который достаточно велик для принятия строки и добавляемого в конце символа \0. f - Ожидается число с плавающей точкой; соответствующий аргумент должен быть указателем на переменную типа float. Е - символ преобразования e является синонимом для f. Формат ввода переменной типа float включает необязательный знак, строку цифр, возможно содержащую десятичную точку и необязательное поле экспоненты, состоящее из буквы e, за которой следует целое, возможно имеющее знак.

Перед символами преобразования d, o и x может стоять l, которая означает , что в списке аргументов должен находиться указатель на переменную типа long, а не типа int. Аналогично, буква l может стоять перед символами преобразования e или f, говоря о том, что в списке аргументов должен находиться указатель на переменную типа double, а не типа float.

Например, обращение

int i; float x; char name[50]; scanf("%d %f %s", &i, &x, name);

со строкой на вводе

25 54.32e-1 thompson

приводит к присваиванию i значения 25, x - значения 5.432 и name - строки "thompson", надлежащим образом законченной символом \0. эти три поля ввода можно разделить столькими пробелами, табуляциями и символами новых строк, сколько вы пожелаете. Обращение

int i; float x; char name[50]; scanf("%2d %f %*d %2s", &i, &x, name);

с вводом

56789 0123 45a72

присвоит i значение 56, x - 789.0, пропустит 0123 и поместит в name строку "45". При следующем обращении к любой процедуре ввода рассмотрение начнется с буквы a. В этих двух примерах name является указателем и, следовательно, перед ним не нужно помещать знак &.

В качестве другого примера перепишем теперь элементарный калькулятор из лекции №4, используя для преобразования ввода функцию scanf:

#include <stdio.h> main() /* rudimentary desk calculator */ { double sum, v; sum =0; while (scanf("%lf", &v) !=EOF) printf("\t%.2f\n", sum += v); }

выполнение функции scanf заканчивается либо тогда, когда она исчерпывает свою управляющую строку, либо когда некоторый элемент ввода не совпадает с управляющей спецификацией. В качестве своего значения она возвращает число правильно совпадающих и присвоенных элементов ввода. Это число может быть использовано для определения количества найденных элементов ввода. При выходе на конец файла возвращается EOF; подчеркнем, что это значение отлично от 0, что следующий вводимый символ не удовлетворяет первой спецификации в управляющей строке. При следующем обращении к scanf поиск возобновляется непосредственно за последним введенным символом.

Заключительное предостережение: аргументы функции scanf должны быть указателями. Несомненно наиболее распространенная ошибка состоит в написании

Форматный вывод - функция printf

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

printf(control, arg1, arg2, ...)

преобразует, определяет формат и печатает свои аргументы в стандартный вывод под управлением строки control. Управляющая строка содержит два типа объектов: обычные символы, которые просто копируются в выходной поток, и спецификации преобразований , каждая из которых вызывает преобразование и печать очередного аргумента printf.

Каждая Спецификация преобразования начинается с символа % и заканчивается символом преобразования. Между % и символом преобразования могут находиться:

знак минус, который указывает о выравнивании преобразованного аргумента по левому краю его поля. Строка цифр, задающая минимальную ширину поля. Преобразованное число будет напечатано в поле по крайней мере этой ширины, а если необходимо, то и в более широком. Если преобразованный аргумент имеет меньше символов, чем указанная ширина поля, то он будет дополнен слева (или справа, если было указано выравнивание по левому краю)заполняющими символами до этой ширины. Заполняющим символом обычно является пробел, а если ширина поля указывается с лидирующим нулем, то этим символом будет нуль (лидирующий нуль в данном случае не означает восьмеричной ширины поля). Точка, которая отделяет ширину поля от следующей строки цифр. Строка цифр (точность), которая указывает максимальное число символов строки, которые должны быть напечатаны, или число печатаемых справа от десятичной точки цифр для переменных типа float или double. Модификатор длины l, который указывает, что соответствующий элемент данных имеет тип long, а не int.

Ниже приводятся символы преобразования и их смысл:

d - аргумент преобразуется к десятичному виду. o - аргумент преобразуется в беззнаковую восьмеричную форму (без лидирующего нуля). x - аргумент преобразуется в беззнаковую шестнадцатеричную форму (без лидирующих 0x). u - аргумент преобразуется в беззнаковую десятичную форму. c - аргумент рассматривается как отдельный символ. s - аргумент является строкой: символы строки печатаются до тех пор, пока не будет достигнут нулевой символ или не будет напечатано количество символов, указанное в спецификации точности. e - аргумент, рассматриваемый как переменная типа float или double, преобразуется в десятичную форму в виде [-]m.nnnnnne[+-]xx, где длина строки из n определяется указанной точностью. Точность по умолчанию равна 6. f - аргумент, рассматриваемый как переменная типа float или double, преобразуется в десятичную форму в виде [-]mmm.nnnnn, где длина строки из n определяется указанной точностью. Точность по умолчанию равна 6. Отметим, что эта точность не определяет количество печатаемых в формате f значащих цифр. g - Используется или формат %e или %f, какой короче; незначащие нули не печатаются. Если идущий за % символ не является символом преобразования, то печатается сам этот символ; следовательно, символ % можно напечатать, указав %%.

Функция UNGETC

Стандартная библиотека содержит довольно ограниченную версию функции ungetch, написанной нами в лекции №4; она называется ungetc. В результате обращения

ungetc(c,fp)

символ "C" возвращается в файл fp. Позволяется возвращать в каждый файл только один символ. функция ungetc может быть использована в любой из функций ввода и с макросами типа scanf, getc или getchar.

Несколько разнообразных функций

Стандартная библиотека предоставляет множество разнообразных функций, некоторые из которых оказываются особенно полезными. Мы уже упоминали функции для работы со строками: strlen, strcpy, strcat и strcmp. Вот некоторые другие.

Обработка ошибок - STDERR и EXIT

Обработка ошибок в cat неидеальна. Неудобство заключается в том, что если один из файлов по некоторой причине оказывается недоступным, диагностическое сообщение об этом печатается в конце объединенного вывода. Это приемлемо, если вывод поступает на терминал, но не годится, если вывод поступает в некоторый файл или через поточный (pipeline) механизм в другую программу.

Чтобы лучше обрабатывать такую ситуацию, к программе точно таким же образом, как stdin и stdout, присоединяется второй выходной файл, называемый stderr. Если это вообще возможно, вывод, записанный в файле stderr, появляется на терминале пользователя, даже если стандартный вывод направляется в другое место.

Давайте переделаем программу cat таким образом, чтобы сообщения об ошибках писались в стандартный файл ошибок.

"include <stdio.h> main(argc,argv) /*cat: concatenate files*/ int argc; char *argv[]; { file *fp, *fopen(); if(argc==1) /*no args; copy standard input*/ filecopy(stdin); else while (--argc > 0) if((fp=fopen(*++argv,"r#))==null) { fprintf(stderr, "cat: can't open,%s\n", argv); exit(1); } else { filecopy(fp); } exit(0); }

Программа сообщает об ошибках двумя способами. диагностическое сообщение, выдаваемое функцией printf, поступает в stderr и, таким образом, оказывается на терминале пользователя, а не исчезает в потоке (pipeline) или в выходном файле.

Программа также использует функцию exit из стандартной библиотеки, обращение к которой вызывает завершение выполнения программы. Аргумент функции exit доступен любой программе, обращающейся к данной функции, так что успешное или неудачное завершение данной программы может быть проверено другой программой, использующей эту в качестве подзадачи. По соглашению величина 0 в качестве возвращаемого значения свидетельствует о том, что все в порядке, а различные ненулевые значения являются признаками нормальных ситуаций.

функция exit вызывает функцию fclose для каждого открытого выходного файла, с тем чтобы вывести всю помещенную в буферы выходную информацию, а затем вызывает функцию _exit. функция _exit приводит к немедленному завершению без очистки каких-либо буферов; конечно, при желании к этой функции можно обратиться непосредственно.

Обращение к системе

функция system(s) выполняет команду, содержащуюся в символьной строке s, и затем возобновляет выполнение текущей программы. Содержимое s сильно зависит от используемой операционной системы. В качестве тривиального примера, укажем, что на системе UNIX строка

system("date");

приводит к выполнению программы date, которая печатает дату и время дня.

Обращение к стандартной библиотеке

Каждый исходный файл, который обращается к функции из стандартной библиотеки, должен вблизи начала содержать строку

#include <stdio.h>

в файле stdio.h определяются некоторые макросы и переменные, используемые библиотекой ввода/вывода. Использование угловых скобок вместо обычных двойных кавычек - указание компилятору искать этот файл в справочнике, содержащем заголовки стандартной информации (на системе UNIX обычно lusrlinelude).

Кроме того, при загрузке программы может оказаться необходимым указать библиотеку явно; на системе PDP-11 UNIX, например, команда компиляции программы имела бы вид:

cc исходные файлы и т.д. -ls

где -ls указывает на загрузку из стандартной библиотеки.

Проверка вида символов и преобразования

Некоторые макросы выполняют проверку символов и преобразования:

salpha(c) не 0, если "c" алфавитный символ, 0 - если нет. supper(c) Не 0, если "c" буква верхнего регистра, 0 - если нет. slower(c) Не 0, если "c" буква нижнего регистра, 0 - если нет. sdigit(c) Не 0, если "c" цифра, 0 - если нет. sspacl(c) Не 0, если "c" пробел, табуляция или новая строка, 0 - если нет. oupper(c) Преобразует "c" в букву верхнего регистра. olower(c) Преобразует "c" в букву нижнего регистра.

Стандартный ввод и вывод - функции GETCHAR и PUTCHAR

Самый простой механизм ввода заключается в чтении по одному символу за раз из "стандартного ввода", обычно с терминала пользователя, с помощью функции getchar. функция getchar() при каждом к ней обращении возвращает следующий вводимый символ. В большинстве сред, которые поддерживают язык "с", терминал может быть заменен некоторым файлом с помощью обозначения <: если некоторая программа prog использует функцию getchar то командная строка

prog<infile

приведет к тому, что prog будет читать из файла infile, а не с терминала. Переключение ввода делается таким образом, что сама программа prog не замечает изменения; в частности строка"<infile" не включается в командную строку аргументов в argv. Переключение ввода оказывается незаметным и в том случае, когда вывод поступает из другой программы посредством поточного (pipe) механизма; командная строка

otherprog | prog

прогоняет две программы, otherprog и prog, и организует так, что стандартным вводом для prog служит стандартный вывод otherprog.

функция getchar возвращает значение EOF, когда она попадает на конец файла, какой бы ввод она при этом не считывала. Стандартная библиотека полагает символическую константу EOF равной -1 (посредством #define в файле stdio.h), но проверки следует писать в терминах EOF, а не -1, чтобы избежать зависимости от конкретного значения.

Вывод можно осуществлять с помощью функции putchar(c), помещающей символ 'с' в "стандартный ввод", который по умолчанию является терминалом. Вывод можно направить в некоторый файл с помощью обозначения > если prog использует putchar, то командная строка

prog>outfile

приведет к записи стандартного вывода в файл outfile, а не на терминал. На системе UNIX можно также использовать поточный механизм. Строка

prog | anotherprog

помещает стандартный вывод prog в стандартный ввод anotherprog. И опять prog не будет осведомлена об изменении направления.

Вывод, осуществляемый функцией printf, также поступает в стандартный вывод, и обращения к putchar и printf могут перемежаться.

Поразительное количество программ читает только из одного входного потока и пишет только в один выходной поток; для таких программ ввод и вывод с помощью функций getchar, putchar и printf может оказаться вполне адекватным и для начала определенно достаточным. Это особенно справедливо тогда, когда имеется возможность указания файлов для ввода и вывода и поточный механизм для связи вывода одной программы с вводом другой. Рассмотрим, например, программу lower, которая преобразует прописные буквы из своего ввода в строчные:

Ввод и вывод

Средства ввода/вывода не являются составной частью языка "с", так что мы не выделяли их в нашем предыдущем изложении. Однако реальные программы взаимодействуют со своей окружающей средой гораздо более сложным образом, чем мы видели до сих пор. В этой лекции будет описана "стандартная библиотека ввода/вывода", то есть набор функций, разработанных для обеспечения стандартной системы ввода/вывода для "с"- программ. Эти функции предназначены для удобства программного интерфейса, и все же отражают только те операции, которые могут быть обеспечены на большинстве современных операционных систем. процедуры достаточно эффективны для того, чтобы пользователи редко чувствовали

необходимость обойти их "ради эффективности", как бы ни была важна конкретная задача. И, наконец, эти процедуры задуманы быть "переносимыми" в том смысле, что они должны существовать в совместимом виде на любой системе, где имеется язык "с", и что программы, которые ограничивают свои взаимодействия с системой возможностями, предоставляемыми стандартной библиотекой, можно будет переносить с одной системы на другую по существу без изменений.

Мы здесь не будем пытаться описать всю библиотеку ввода/вывода; мы более заинтересованы в том, чтобы продемонстрировать сущность написания "с"-программ, которые взаимодействуют со своей операционной средой.

Ввод и вывод строк

Стандартная библиотека содержит функцию fgets, совершенно аналогичную функции getline, которую мы использовали на всем протяжении книги. В результате обращения

fgets(line, maxline, fp)

следующая строка ввода (включая символ новой строки) считывается из файла fp в символьный массив line; самое большое maxline_1 символ будет прочитан. Результирующая строка заканчивается символом \0. Нормально функция fgets возвращает line; в конце файла она возвращает null. (Наша функция getline возвращает длину строки, а при выходе на конец файла - нуль).

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

fputs(line, fp)

Чтобы показать, что в функциях типа fgets и fputs нет ничего таинственного, мы приводим их ниже, скопированными непосредственно из стандартной библиотеки ввода-вывода:

#include <stdio.h> char *fgets(s,n,iop) /*get at most n chars from iop*/ char *s; int n; register file *iop; { register int c; register char *cs; cs = s; while(--n>0&&(c=getc(iop)) !=EOF) if ((*cs++ = c)=='\n') break; *cs = '\0'; return((c==EOF && cs==s) 7 null : s); } fputs(s,iop) /*put string s on fils iop*/ register char *s; register file *iop; { register int c; while (c = *s++) putc(c,iop); }

Упражнение 7-3

Напишите программу сравнения двух файлов, которая будет печатать первую строку и позицию символа, где они различаются.

Упражнение 7-4

Переделайте программу поиска заданной комбинации символов из лекции №5

таким образом, чтобы в качестве ввода использовался набор именованных файлов или, если никакие файлы не указаны как аргументы, стандартный ввод. Следует ли печатать имя файла при нахождении подходящей строки?

Упражнение 7-5

Напишите программу печати набора файлов, которая начинает каждый новый файл с новой страницы и печатает для каждого файла заголовок и счетчик текущих страниц.

Дескрипторы файлов

В операционной системе UNIX весь ввод и вывод осуществляется посредством чтения файлов или их записи, потому что все периферийные устройства, включая даже терминал пользователя, являются файлами определенной файловой системы. Это означает, что один однородный интерфейс управляет всеми связями между программой и периферийными устройствами.

В наиболее общем случае перед чтением из файла или записью в файл необходимо сообщить системе о вашем намерении; этот процесс называется "открытием" файла. Система выясняет, имеете ли вы право поступать таким образом (существует ли этот файл? имеется ли у вас разрешение на обращение к нему?), и если все в порядке, возвращает в программу небольшое положительное целое число, называемое дескриптором файла. Всякий раз, когда этот файл используется для ввода или вывода, для идентификации файла употребляется дескриптор файла, а не его имя. (Здесь существует примерная аналогия с использованием read (5,...) и write (6,...) в фортране). Вся информация об открытом файле содержится в системе; программа пользователя обращается к файлу только через дескриптор файла.

Для удобства выполнения обычных операций ввода и вывода с помощью терминала пользователя существуют специальные соглашения. Когда интерпретатор команд ("shell") прогоняет программу, он открывает три файла, называемые стандартным вводом, стандартным выводом и стандартным выводом ошибок, которые имеют соответственно числа 0, 1 и 2 в качестве дескрипторов этих файлов. В нормальном состоянии все они связаны с терминалом, так что если программа читает с дескриптором файла 0 и пишет с дескрипторами файлов 1 и 2, то она может осуществлять ввод и вывод с помощью терминала, не заботясь об открытии соответствующих файлов.

Пользователь программы может перенаправлять ввод и вывод на файлы, используя операции командного интерпретатора shell "<" и ">":

prog <infile>outfile

В этом случае интерпретатор команд shell изменит присваивание по умолчанию дескрипторов файлов 0 и 1 с терминала на указанные файлы. Нормально дескриптор файла 2 остается связанным с терминалом, так что сообщения об ошибках могут поступать туда. Подобные замечания справедливы и тогда, когда ввод и вывод связан с каналом. Следует отметить, что во всех случаях прикрепления файлов изменяются интерпретатором shell, а не программой. Сама программа, пока она использует файл 0 для ввода и файлы 1 и 2 для вывода, не знает ни откуда приходит ее ввод, ни куда поступает ее выдача.

Интерфейс системы UNIX

Переменная base используется для начала работы. Если allocp имеет значение null, как в случае первого обращения к alloc, то создается вырожденный свободный список: он состоит из свободного блока размера нуль и указателя на самого себя. В любом случае затем исследуется свободный список. Поиск свободного блока подходящего размера начинается с того места (allocp ), где был найден последний блок; такая стратегия помогает сохранить однородность диска. Если найден слишком большой блок, то пользователю предлагается его хвостовая часть; это приводит к тому, что в заголовке исходного блока нужно изменить только его размер. Во всех случаях возвращаемый пользователю указатель указывает на действительно свободную область, лежащую на единицу дальше заголовка. Обратите внимание на то, что функция alloc перед возвращением "p" преобразует его в указатель на символы.

Функция morecore получает память от операционной системы. Детали того, как это осуществляется, меняются, конечно, от системы к системе. На системе UNIX точка входа sbrk(n) возвращает указатель на "n" дополнительных байтов памяти.(указатель удовлетворяет всем ограничениям на выравнивание). Так как запрос к системе на выделение памяти является сравнительно дорогой операцией, мы не хотим делать это при каждом обращении к функции alloc. Поэтому функция morecore округляет затребованное число единиц до большего значения; этот больший блок будет затем разделен так, как необходимо. Масштабирующая величина является параметром, который может быть подобран в соответствии с необходимостью.

#define nalloc 128 /*#units to allocate at once*/ static header *morecore(nu) /*ask system for memory*/ unsigned nu; { char *sbrk(); register char *cp; register header *up; register int rnu; rnu=nalloc*((nu+nalloc-1)/nalloc); cp=sbrk(rnu*sizeof(header)); if ((int)cp==-1) /*no space at all*/ return(null); up=(header *)cp; up->s.size=rnu; free((char *)(up+1)); return(allocp); }

Если больше не осталось свободного пространства, то функция sbrk возвращает "-1", хотя null был бы лучшим выбором. Для надежности сравнения "-1" должна быть преобразована к типу int. Снова приходится многократно использовать явные преобразования (перевод) типов, чтобы обеспечить определенную независимость функций от деталей представления указателей на различных машинах.

И последнее - сама функция free. Начиная с allocp, она просто просматривает свободный список в поиске места для введения свободного блока. Это место находится либо между двумя существующими блоками, либо в одном из концов списка. В любом случае, если освободившийся блок примыкает к одному из соседних, смежные блоки объединяются. Следить нужно только затем, чтобы указатели указывали на то, что нужно, и чтобы размеры были установлены правильно.

free(ap) /* put blocke ap in free list*/ char *ap; { register header *p, *g; p=(header*)ap-1; /*point to header*/ for (g=allocp; !(p>g && p>g->s.ptr);g=g->s.ptr) if (g>=g->s.ptr && (p>g || p<g->s.ptr)) break; /*at one end or other*/ if (p+p->s.size==g->s.ptr) { /*join to upper nbr*/ p->s.size += g->s.ptr->s.size; p->s.ptr = g->s.ptr->s.ptr; } else p->s.ptr = g->s.ptr; if (g+g->s.size==p) { /*join to lower nbr*/ g->s.size+=p->s.size; g->s.ptr=p->s.ptr; } else g->s.ptr=p; allocp = g; }

Хотя распределение памяти по своей сути зависит от используемой машины, приведенная выше программа показывает, как эту зависимость можно регулировать и ограничить весьма небольшой частью программы. Использование typedef и union позволяет справиться с выравниванием (при условии, что функция sbrk обеспечивает подходящий указатель). Переводы типов организуют выполнение явного преобразования типов и даже справляются с неудачно разработанным системным интерфейсом. И хотя рассмотренные здесь подробности связаны с распределением памяти, общий подход равным образом применим и к другим ситуациям.

Упражнение 8-6

функция из стандартной библиотеки calloc(n,size) возвращает указатель на "n" объектов размера size, причем соответствующая память инициализируется на нуль. Напишите программу для calloc, используя функцию alloc либо в качестве образца, либо как функцию, к которой происходит обращение.

Упражнение 8-7

функция alloc принимает затребованный размер, не проверяя его правдоподобности; функция free полагает, что тот блок, который она должна освободить, содержит правильное значение в поле размера. Усовершенствуйте эти процедуры, затратив больше усилий на проверку ошибок.

Упражнение 8-8

Напишите функцию bfree(p,n), которая включает произвольный блок "p" из "n" символов в список свободных блоков, управляемый функциями alloc и free. С помощью функции bfree пользователь может в любое время добавлять в свободный список статический или внешний массив.

Низкоуровневый ввод/вывод - операторы READ и WRITE

Самый низкий уровень ввода/вывода в системе UNIX не предусматривает ни какой-либо буферизации, ни какого-либо другого сервиса; он по существу является непосредственным входом в операционную систему. Весь ввод и вывод осуществляется двумя функциями: read и write. Первым аргументом обеих функций является дескриптор файла. Вторым аргументом является буфер в вашей программе, откуда или куда должны поступать данные. Третий аргумент - это число подлежащих пересылке байтов. Обращения к этим функциям имеют вид:

n_read=read(fd,buf,n); n_written=write(fd,buf,n);

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

Количество байтов, подлежащих чтению или записи, может быть совершенно произвольным. Двумя самыми распространенными величинами являются "1", которая означает передачу одного символа за обращение (т.е. без использования буфера), и "512", которая соответствует физическому размеру блока на многих периферийных устройствах. Этот последний размер будет наиболее эффективным, но даже ввод или вывод по одному символу за обращение не будет необыкновенно дорогим.

Объединив все эти факты, мы написали простую программу для копирования ввода на вывод, эквивалентную программе копировки файлов, написанной в лекции №1. На системе UNIX эта программа будет копировать что угодно куда угодно, потому что ввод и вывод могут быть перенаправлены на любой файл или устройство.

#define bufsize 512 /*best size for pdp-11 unix*/ main() /*copy input to output*/ { char buf[bufsize]; int n; while((n=read(0,buf,bufsize))>0) write(1,buf,n); }

Если размер файла не будет кратен bufsize, то при некотором обращении к read будет возвращено меньшее число байтов, которые затем записываются с помощью write; при следующем после этого обращении к read будет возвращен нуль.

Поучительно разобраться, как можно использовать функции read и write для построения процедур более высокого уровня, таких как getchar, putchar и т.д. Вот, например, вариант функции getchar, осуществляющий ввод без использования буфера.

Открытие, создание, закрытие и расцепление (UNLINK)

Кроме случая, когда по умолчанию определены стандартные файлы ввода, вывода и ошибок, вы должны явно открывать файлы, чтобы затем читать из них или писать в них. Для этой цели существуют две точки входа: open и creat.

функция open весьма сходна с функцией fopen, рассмотренной в лекции №7, за исключением того, что вместо возвращения указателя файла она возвращает дескриптор файла, который является просто целым типа int.

int fd; fd=open(name,rwmode);

Как и в случае fopen, аргумент name является символьной строкой, соответствующей внешнему имени файла. Однако аргумент, определяющий режим доступа, отличен: rwmode равно: 0 - для чтения, 1 - для записи, 2 - для чтения и записи. Если происходит какая-то ошибка, функция open возвращает "-1"; в противном случае она возвращает действительный дескриптор файла.

Попытка открыть файл, который не существует, является ошибкой. Точка входа creat предоставляет возможность создания новых файлов или перезаписи старых. В результате обращения

fd=creat(name,pmode);

возвращает дескриптор файла, если оказалось возможным создать файл с именем name, и "-1" в противном случае. Если файл с таким именем уже существует, creat усечет его до нулевой длины; создание файла, который уже существует, не является ошибкой.

Если файл является совершенно новым, то creat создает его с определеным режимом защиты, специфицируемым аргументом pmode. В системе файлов на UNIX с файлом связываются девять битов защиты информации, которые управляют разрешением на чтение, запись и выполнение для владельца файла, для группы владельцев и для всех остальных пользователей. Таким образом, трехзначное восьмеричное число наиболее удобно для спецификации разрешений. Например, число 0755 свидетельствует о разрешении на чтение, запись и выполнение для владельца и о разрешении на чтение и выполнение для группы и всех остальных.

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

Пример - распечатка справочников

Иногда требуется другой вид взаимодействия с системой файлов - определение информации о файле, а не того, что в нем содержится. Примером может служить команда ls ("список справочника") системы UNIX. По этой команде распечатываются имена файлов из справочника и, необязательно, другая информация, такая как размеры, разрешения и т.д.

Поскольку, по крайней мере, на системе UNIX справочник является просто файлом, то в такой команде, как ls нет ничего особенного; она читает файл и выделяет нужные части из находящейся там информации. Однако формат информации определяется системой, так что ls должна знать, в каком виде все представляется в системе.

Мы это частично проиллюстрируем при написании программы fsize. Программа fsize представляет собой специальную форму ls, которая печатает размеры всех файлов, указанных в списке ее аргументов. Если один из файлов является справочником, то для обработки этого справочника программа fsize обращается сама к себе рекурсивно. если же аргументы вообще отсутствуют, то обрабатывается текущий справочник.

Для начала дадим краткий обзор структуры системы файлов. Справочник - это файл, который содержит список имен файлов и некоторое указание о том, где они размещаются. Фактически это указание является индексом для другой таблицы, которую называют "I - узловой таблицей". Для файла I-узел - это то, где содержится вся информация о файле, за исключением его имени. Запись в справочнике состоит только из двух элементов: номера I-узла и имени файла. Точная спецификация поступает при включении файла sys/dir.h, который содержит

#define dirsiz 14 /*max length of file name*/ struct direct /*structure of directory entry*/ { ino_t& _ino; /*inode number*/ char & _name[dirsiz]; /*file name*/ };

"Тип" ino_t - это определяемый посредством typedef тип, который описывает индекс I-узловой таблицы. На PDP-11 UNIX этим типом оказывается unsigned, но это не тот сорт информации, который помещают внутрь программы: на разных системах этот тип может быть различным. Поэтому и следует использовать typedef. Полный набор "системных" типов находится в файле sys/tupes.h.

функция stat берет имя файла и возвращает всю содержащуюся в I-ом узле информацию об этом файле (или -1, если имеется ошибка). Таким образом, в результате

struct stat stbuf; char *name; stat(name,&stbuf);

структура stbuf наполняется информацией из I-го узла о файле с именем name. структура, описывающая возвращаемую функцией stat информацию, находится в файле sys/stat.h и выглядит следующим образом:

struct stat /*structure returned by stat*/ { dev_t st_dev; /* device of inode */ ino_t st_ino; /* inode number */ short st_mode /* mode bits */ short st_nlink; / *number of links to file */ short st_uid; /* owner's user id */ short st_gid; /* owner's group id */ dev_t st_rdev; /* for special files */ off_t st_size; /* file size in characters */ time_t st_atime; /* time last accessed */ time_t st_mtime; /* time last modified */ time_t st_ctime; /* time originally created */ }

Большая часть этой информации объясняется в комментариях. Элемент st.mode содержит набор флагов, описывающих файл; для удобства определения флагов также находятся в файле sys/stat.h.

#define s_ifmt 0160000 /* type of file */ #define s_ifdir 0040000 /* directory */ #define s_ifchr 0020000 /* character special */ #define s_ifblk 0060000 /* block special */ #define s_ifreg 0100000 /* regular */ #define s_isuid 04000 /* set user id on execution */ #define s_isgid 02000 /* set group id on execution */ #define s_isvtx 01000 /*save swapped text after use*/ #define s_iread 0400 /* read permission */ #define s_iwrite 0200 /* write permission */ #define s_iexec 0100 /* execute permission */

Теперь мы в состоянии написать программу fsize. Если полученный от функции stat режим указывает, что файл не является справочником, то его размер уже под рукой и может быть напечатан непосредственно. Если же он оказывается справочником, то мы должны обрабатывать этот справочник отдельно для каждого файла; так как справочник может в свою очередь содержать подсправочники, этот процесс обработки является рекурсивным.

Как обычно, ведущая программа главным образом имеет дело с командной строкой аргументов; она передает каждый аргумент функции fsize в большой буфер.

#include <stdio.h> #include <sys/types.h>> /*typedefs*/ #include <sys/dir.h>> /*directory entry structure*/ #include <sys/stat.h>> /*structure returned by stat*/ #define bufsize 256 main(argc,argv) /*fsize:print file sizes*/ char *argv[]; { char buf[bufsize]; if(argc==1) { /*default:current directory*/ atrcpy(buf,"."); fsize(buf); } else while(--argc>0) { strcpy(buf,*++argv); fsize(buf); } }



Функция fsize печатает размер файла. Если однако файл оказывается справочником, то fsize сначала вызывает функцию directory для обработки всех указанных в нем файлов. Обратите внимание на использование имен флагов s_ifmt и _ifdir из файла stat.h.

fsize(name) /*print size for name*/ char *name; { struct stat stbuf; if(stat(name,&stbuf)== -1) { fprintf(stderr,"fsize:can't find %s\n",name); return; } if((stbuf.st_mode & s_ifmt)==s_ifdir) directory(name); printf("%8ld %s\n",stbuf.st_size,name); }

Функция directory является самой сложной. Однако значительная ее часть связана с созданием для обрабатываемого в данный момент файла его полного имени, по которому можно восстановить путь в дереве.

directory(name) /*fsize for all files in name*/ char *name; { struct direct dirbuf; char *nbp, *nep; int i, fd; nbp=name+strlen(name); *nbp++='/'; /*add slash to directory name*/ if(nbp+dirsiz+2>=name+bufsize) /*name too long*/ return; if((fd=open(name,0))== -1) return; while(read(fd,(char *)&dirbuf,sizeof(dirbuf))>0) \( if(dirbuf.d_ino==0) /*slot not in use*/ continue; if(strcmp (dirbuf.d_name,".")==0 || strcmp(dirbuf.d_name,"..")==0 continue; /*skip self and parent*/ for (i=0,nep=nbp;i<dirsiz;i++) *nep++=dirbuf.d_name[i]; *nep++='\0'; fsize(name); } close(fd); *--nbp='\0'; /*restore name*/ }

Если некоторая дыра в справочнике в настоящее время не используется (потому что файл был удален), то в соответствующее I-узловое число равно нулю, и эта позиция пропускается. Каждый справочник также содержит запись в самом себе, называемую ".", и о своем родителе, ".."; они, очевидно, также должны быть пропущены, а то программа будет работать весьма и весьма долго.

Хотя программа fsize довольно специализированна, она все же демонстрирует пару важных идей. во-первых, многие программы не являются "системными программами"; они только используют информацию, форма или содержание которой определяется операционной системой. Во-вторых, для таких программ существенно, что представление этой информации входит только в стандартные "заголовочные файлы", такие как stat.h и dir.h, и что программы включают эти файлы, а не помещают фактические описания внутрь самих программ.

Пример - распределитель памяти

В лекции №5 мы написали бесхитростный вариант функции alloc. Вариант, который мы напишем теперь, не содержит ограничений: обращения к функциям alloc и free могут перемежаться в любом порядке; когда это необходимо, функция alloc обращается к операционной системе за дополнительной памятью. Кроме того, что эти процедуры полезны сами по себе, они также иллюстрируют некоторые соображения, связанные с написанием машинно-зависимых программ относительно машинно-независимым образом, и показывают практическое применение структур, объединений и конструкций typedef.

Вместо того, чтобы выделять память из скомпилированного внутри массива фиксированного размера, функция alloc будет по мере необходимости обращаться за памятью к операционной системе. Поскольку различные события в программе могут требовать асинхронного выделения памяти, то память, управляемая alloc, не может быть непрерывной. В силу этого свободная память хранится в виде цепочки свободных блоков. Каждый блок включает размер, указатель следующего блока и саму свободную память. Блоки упорядочиваются в порядке возрастания адресов памяти, причем последний блок (с наибольшим адресом) указывает на первый, так что цепочка фактически оказывается кольцом.

При поступлении запроса список свободных блоков просматривается до тех пор, пока не будет найден достаточно большой блок. Если этот блок имеет в точности требуемый размер, то он отцепляется от списка и передается пользователю. Если же этот блок слишком велик, то он разделяется, нужное количество передается пользователю, а остаток возвращается в свободный список. Если достаточно большого блока найти не удается, то операционной системой выделяется новый блок, который включается в список свободных блоков; затем поиск возобновляется.

Освобождение памяти также влечет за собой просмотр свободного списка в поиске подходящего места для введения освобожденного блока. Если этот освободившийся блок с какой-либо стороны примыкает к блоку из списка свободных блоков, то они объединяются в один блок большего размера, так что память не становится слишком раздробленной. Обнаружить смежные блоки просто, потому что свободный список содержится в порядке возрастания адресов.

Одна из проблем, о которой мы упоминали в лекции №5, заключается в обеспечении того, чтобы возвращаемая функцией alloc память была выровнена подходящим образом для тех объектов, которые будут в ней храниться. Хотя машины и различаются, для каждой машины существует тип, требующий наибольших ограничений по размещению памяти, если данные самого ограничительного типа можно поместить в некоторый определенный адрес, то это же возможно и для всех остальных типов. Например, на IBM 360/370,HONEYWELL 6000 и многих других машинах любой объект может храниться в границах, соответствующим переменным типа double; на PDP-11 будут достаточны переменные типа int.

Свободный блок содержит указатель следующего блока в цепочке, запись о размере блока и само свободное пространство; управляющая информация в начале называется заголовком. Для упрощения выравнивания все блоки кратны размеру заголовка, а сам заголовок выровнен надлежащим образом. Это достигается с помощью объединения, которое содержит желаемую структуру заголовка и образец наиболее ограничительного по выравниванию типа:

Пример - реализация функций FOPEN и GETC

Давайте теперь на примере реализации функций fopen и getc из стандартной библиотеки подпрограмм продемонстрируем, как некоторые из описанных элементов объединяются вместе.

Напомним, что в стандартной библиотеке файлы описываются посредством указателей файлов, а не дескрипторов. указатель файла является указателем на структуру, которая содержит несколько элементов информации о файле: указатель буфера, чтобы файл мог читаться большими порциями; счетчик числа символов, оставшихся в буфере; указатель следующей позиции символа в буфере; некоторые признаки, указывающие режим чтения или записи и т.д.; дескриптор файла.

Описывающая файл структура данных содержится в файле stdio.h, который должен включаться (посредством #include) в любой исходный файл, в котором используются функции из стандартной библиотеки. Он также включается функциями этой библиотеки. В приводимой ниже выдержке из файла stdio.h имена, предназначаемые только для использования функциями библиотеки, начинаются с подчеркивания, с тем чтобы уменьшить вероятность совпадения с именами в программе пользователя.

define _bufsize 512 define _nfile 20 /*files that can be handled*/ typedef struct _iobuf { char *_ptr; /*next character position*/ int _cnt; /*number of characters left*/ char *_base; /*location of buffer*/ int _flag; /*mode of file access*/ int _fd; /*file descriptor*/ } file; xtern file _iob[_nfile];

define stdin (&_iob[0]) define stdout (&_iob[1]) define stderr (&_iob[2])

define _READ 01 /* file open for reading */ define _WRITE 02 /* file open for writing */ define _UNBUF 04 /* file is unbuffered */ define _BIGBUF 010 /* big buffer allocated */ define _EOF 020 /* EOF has occurred on this file */ define _ERR 040 /* error has occurred on this file */ define NULL 0 define EOF (-1)

define getc(p) (--(p)->_cnt >= 0 \ ? *(p)->_ptr++ & 0377 : _filebuf(p)) define getchar() getc(stdin)

define putc(x,p) (--(p)->_cnt >= 0 \ ? *(p)->_ptr++ = (x) : _flushbuf((x),p)) define putchar(x) putc(x,stdout)

В нормальном состоянии макрос getc просто уменьшает счетчик, передвигает указатель и возвращает символ. (Если определение #define слишком длинное, то оно продолжается с помощью обратной косой черты). Если однако счетчик становится отрицательным, то getc вызывает функцию _filebuf, которая снова заполняет буфер, реинициализирует содержимое структуры и возвращает символ. функция может предоставлять переносимый интерфейс и в то же время содержать непереносимые конструкции: getc маскирует символ числом 0377, которое подавляет знаковое расширение, осуществляемое на PDP-11, и тем самым гарантирует положительность всех символов.

Хотя мы не собираемся обсуждать какие-либо детали, мы все же включили сюда определение макроса putc, для того чтобы показать, что она работает в основном точно также, как и getc, обращаясь при заполнении буфера к функции _flushbuf.

Теперь может быть написана функция fopen. Большая часть программы функции fopen связана с открыванием файла и расположением его в нужном месте, а также с установлением битов признаков таким образом, чтобы они указывали нужное состояние. функция fopen не выделяет какой-либо буферной памяти; это делается функцией _filebuf при первом чтении из файла.

#include <stdio.h> #define pmode 0644 /*r/w for owner;r for others*/ file *fopen(name,mode) /*open file,return file ptr*/ register char *name, *mode; { register int fd; register file *fp; if(*mode !='r'&&*mode !='w'&&*mode !='a') { fprintf(stderr,"illegal mode %s opening %s\n", mode,name); exit(1); } for (fp=_iob;fp<_iob+_nfile;fp++) if((fp->_flag & (_read | _write))==0) break; /*found free slot*/ if(fp>=_iob+_nfile) /*no free slots*/ return(null); if(*mode=='w') /*access file*/ fd=creat(name,pmode); else if(*mode=='a') { if((fd=open(name,1))==-1) fd=creat(name,pmode); lseek(fd,ol,2); } else fd=open(name,0); if(fd==-1) /*couldn't access name*/ return(null); fp->_fd=fd; fp->_cnt=0; fp->_base=null; fp->_flag &=(_read | _write); fp->_flag |=(*mode=='r') ? _read : _write; return(fp); }



функция _filebuf несколько более сложная. Основная трудность заключается в том, что _filebuf стремится разрешить доступ к файлу и в том случае, когда может не оказаться достаточно места в памяти для буферизации ввода или вывода. если пространство для нового буфера может быть получено обращением к функции calloc, то все отлично; если же нет, то _filebuf осуществляет небуферизованный ввод/вывод, используя отдельный символ, помещенный в локальном массиве.

#include <stdio.h> _fillbuf(fp) /*allocate and fill input buffer*/ register file *fp; ( static char smallbuf(nfile);/*for unbuffered 1/0*/ char *calloc(); if((fr->_flag& _read)==0 || (fp->_flag&(EOF|_err)) |=0 return(EOF); while(fp->_base==null) /*find buffer space*/ if(fp->_flag & _unbuf) /*unbuffered*/ fp->_base=&smallbuf[fp->_fd]; else if((fp->_base=calloc(_bufsize,1))==null) fp->_flag |=_unbuf; /*can't get big buf*/ else fp->_flag |=_bigbuf; /*got big one*/ fp->_ptr=fp->_base; fp->_cnt=read(fp->_fd, fp->_ptr, fp->_flag & _unbuf ? 1 : _bufsize); ff(--fp->_cnt<0) { if(fp->_cnt== -1) fp->_flag | = _EOF; else fp->_flag |= _ err; fp->_cnt = 0; return(EOF); } return(*fp->_ptr++ & 0377); /*make char positive*/ }

При первом обращении к getc для конкретного файла счетчик оказывается равным нулю, что приводит к обращению к _filebuf. Если функция _filebuf найдет, что этот файл не открыт для чтения, она немедленно возвращает EOF. В противном случае она пытается выделить большой буфер, а если ей это не удается, то буфер из одного символа. При этом она заносит в _flag соответствующую информацию о буферизации.

Раз буфер уже создан, функция _filebuf просто вызывает функцию read для его заполнения, устанавливает счетчик и указатели и возвращает символ из начала буфера.

Единственный оставшийся невыясненным вопрос состоит в том, как все начинается. Массив _iob должен быть определен и инициализирован для stdin, stdout и stderr:

file _iob[nfile] = { (null,0,_read,0), /*stdin*/ (null,0,null,1), /*stdout*/ (null,0,null,_write | _unbuf,2) /*stderr*/ };

Произвольный доступ - SEEK и LSEEK

Нормально при работе с файлами ввод и вывод осуществляется последовательно: при каждом обращении к функциям read и write чтение или запись начинаются с позиции, непосредственно следующей за предыдущей обработанной. Но при необходимости файл может читаться или записываться в любом произвольном порядке. Обращение к системе с помощью функции lseek позволяет передвигаться по файлу, не производя фактического чтения или записи. В результате обращения

lseek(fd,offset,origin);

текущая позиция в файле с дескриптором fd передвигается на позицию offset (смещение), которая отсчитывается от места, указываемого аргументом origin (начало отсчета). Последующее чтение или запись будут теперь начинаться с этой позиции. Аргумент offset имеет тип long; fd и origin имеют тип int. аргумент origin может принимать значения 0,1 или 2, указывая на то, что величина offset должна отсчитываться соответственно от начала файла, от текущей позиции или от конца файла. Например, чтобы дополнить файл, следует перед записью найти его конец:

lseek(fd,0l,2);

чтобы вернуться к началу ("перемотать обратно"), можно написать:

lseek(fd,0l,0);

обратите внимание на аргумент 0l; его можно было бы записать и в виде (long) 0.

функция lseek позволяет обращаться с файлами примерно так же, как с большими массивами, правда ценой более медленного доступа. следующая простая функция, например, считывает любое количество байтов, начиная с произвольного места в файле.

get(fd,pos,buf,n) /*read n bytes from position pos*/ int fd, n; long pos; char *buf; { lseek(fd,pos,0); /*get to pos*/ return(read(fd,buf,n)); }

В более ранних редакциях, чем редакция 7 системы UNIX, основная точка входа в систему ввода-вывода называется seek. функция seek идентична функции lseek, за исключением того, что аргумент offset имеет тип int, а не long. В соответствии с этим, поскольку на PDP-11 целые имеют только 16 битов, аргумент offset, указываемый функции seek, ограничен величиной 65535; по этой причине аргумент origin может иметь значения 3, 4, 5, которые заставляют функцию seek умножить заданное значение offset на 512 (количество байтов в одном физическом блоке) и затем интерпретировать origin, как если это 0, 1 или 2 соответственно. Следовательно, чтобы достичь произвольного места в большом файле, нужно два обращения к seek: сначала одно, которое выделяет нужный блок, а затем второе, где origin имеет значение 1 и которое осуществляет передвижение на желаемый байт внутри блока.

Упражнение 8-2

Очевидно, что seek может быть написана в терминалах lseek и наоборот. напишите каждую функцию через другую.

---

---