Неоднородные типы данных.
Структуры, записи, объединения.
1999, 2007, 29.11.2017
Массивы хороши, когда надо сгруппировать данные одного типа. А что делать, если требуется логически (или семантически) сгруппировать данные разных типов? В большинстве современных языков программирования (даже уровня Assembler) есть структурные типы данных. Вот сейчас мы и посмотрим, как же такие структуры реализуются физически.
Предположим, что нужно написать программу для отдела кадров. Эта программа должна обрабатывать информацию о сотрудниках, такую как домашний адрес, домашний телефон, дата рождения, дата поступления на работу и прочее. С помощью простых типов данных и массивов написать такую программу не так просто (хотя и возможно). Например, описание данных сотрудника может выглядеть примерно так:
char home_address[150]; // Домашний адрес
char home_phone[10]; // Домашний телефон
int birth_day; // День рождения
int birth_month; // Месяц рождения
int birth_year; // Год рождения
int work_day; // День поступления на работу
int work_month; // Месяц поступления на работу
int work_year; // Год поступления на работу
. . .
Если нужно обрабатывать сразу всех сотрудников, то нужно объявить не просто переменные, а массивы переменных. Конечно, этот способ работает. Более того, именно так (только на Fortran) были написаны многочисленные программы "Кадры" и "Зарплата" для ЕС ЭВМ. Но этот подход выглядит не эстетично, да и чреват большим количеством ошибок. Целостные понятия, такие как дата или человек представлены набором не связанных между собой переменных. Отсутствует логическая и семантическая целостность.
Впервые это заметили и решили исправить разработчики языка Cobol. Этот язык был ориентирован на обработку экономической информации и задачи, подобные вышеописанной, рассматривались еще на этапе разработки языка.
В современных языках программирования логическое объединение целостных понятий называется записью (Pascal) или структурой (С/С++). Например в языке С можно так переписать приведенный выше фрагмент:
struct date {
int day; // День
int month; // Месяц
int year; // Год
};
struct person {
struct date birth; // Дата рождения
struct date work; // Дата приема на работу
char home_addr[150]; // Домашний адрес
char home_phone[10]; // Домашний телефон
};
struct person worker;
struct person workers[100];
Как видно, структуры помогают добиться более понятного для человека кода. Транслятору структуры не нужны, но он поддерживает их для программиста. Последняя строка в примере показывает, как легко можно объявить массив структур. Работа со структурными переменными так же проста:
worker.birth.day=1; worker.birth.month=10; worker.birth.year=1970;
workers[10].work.year=1999;
write(file,&worker,sizeof(worker));
Язык С++ ввел понятие класса, являющегося, по сути, расширением понятия структуры. Но оставим в стороне синтаксические и семантические тонкости языков С и С++. Нас интересуют данные и их физическая реализация. Поэтому снова посмотрите на описание структуры date. В этой структуре day, month и year называются полями. В структуре person полями являются birth, work, home_addr и home_phone. То, что поля структур сами могут быть структурами, позволяет целостным образом описывать достаточно сложные понятия реального мира. Так как структуры, в отличии от массивов, хранят данные различных типов, они и относятся к неоднородным типам данных.
Однако понятие структуры, в том виде, как это описано выше, позволяет описать не все. Например, представим, что структура person должна для мужчин содержать название воинской специальности, а для женщин количество детей. Решение в лоб может выглядеть так:
struct person {
struct date birth; // Дата рождения
char sex; // Пол (м/ж)
char wars[20]; // Воинская специальность
int kids; // Количество детей
};
Синтаксически все правильно. Однако семантически появляется возможность описать мужчину рожавшего детей (про женщин военнослужащих пока забудем). Избежать подобного положения мы можем объявив, что поля wars и kids не могут быть представлены одновременно. Другими словами мы объединим эти поля в одно целое. Это и есть объединение (С) или запись с вариантами (Pascal).
struct person {
struct date birth;
char sex;
union {
char wars[20];
int kids;
};
};
Объединения позволяют решить поставленную задачу. Одновременно решается и задача экономии памяти. Как это происходит мы увидим, когда будем рассматривать физическую реализацию структур. Но не будем забывать, что вся наша семантика не нужна компилятору, поэтому он не отслеживает, какое из двух полей, wars или kids, должно существовать в данный момент. Для компилятора, и компьютера, одновременно существуют оба поля. Это приводит к тому, что если мы представим мать-героиню имеющую 30 детей, то увидим, что ее воинская специальность '0'. Почему? Сейчас узнаете.
Необходимоо отметить, что для Pascal записи с вариантами реализуются несколько по иному (да и с точки зрения самого языка работа с ними идет по другому). В частности, там можно описать только одну вариантную часть и хранится и само поле обеспечивающее выбор одного из вариантов, так что даже с точки зрения компилятора в каждом экземпляре записи присутствует лишь одно поле. Но для нас сейчас это не важно, поэтому дальнейшее описание будет использовать реализацию для языка C.
Физическая реализация структур
Вспомним реализацию массивов. Массив адресуется с помощью базового адреса и индексов, которые в сущности определяют смещение от базового адреса до искомого элемента. Со структурами ситуация похожая.
Как видно из рисунка, структурная переменная определяет базовый адрес, а каждое поле определяет смещение от базового адреса соответствующей структуры. Предположим, что целые числа занимают 2 байта. Тогда размер структуры date будет 6 байт. Далее, предположим, что базовый адрес переменной worker равен 100. Тогда базовый адрес поля birth будет так же равен 100, а базовый адрес поля work будет равен 106. Поле month имеет смещение 2 относительно базового адреса структуры date. Следовательно поле birth.month будет иметь адрес 102 (базовый адрес worker плюс базовый адрес bith плюс смещение до month), а поле work.month будет имеет адрес 108. Поле addr будет имеет адрес 112 (базовый адрес worker плюс двойной размер структуры date). Поле phone будет иметь адрес 132. Все эти вычисления очень просты и их без труда выполняет компилятор во время трансляции Вашей программы.
Ситуация несколько усложняется, если компилятор обеспечивает выравнивание данных. Этого может требовать процессор. Например слово, состоящее из двух байт, может обязательно требоваться разместить начиная с четного байта. В этом случае компилятор вставляет неиспользуемые байты между полями структуры.
Слева на этом рисунке представлено размещение структуры без выравнивания, или с выравниванием на границу байта, что одно и тоже. Справа, размещение той же структуры с выравниванием на границу слова (двух байт). Видно, что в области памяти, занимаемой структурой, появилось две дыры. Это компилятор вставил неиспользуемые байты, что бы длина всех полей была кратна двум байтам. Иногда компиляторы поступают более умно, вставляя неиспользуемые байты не после полей, длина которых не кратна заданному значению, а перед полями, для которых действительно требуется выравнивание.
Объединения размещаются в памяти принципиально отлично от структур. Все поля объединения располагаются начиная с одного и того же адреса, равному базовому адресу объединения. Из рисунка видно, что поля b, c и d размещаются по одному и тому же адресу и занимают одну и ту же область памяти. Размер области памяти, занимаемой объединением, равен не сумме длин полей, как у структуры, а полю максимальной длины. В нашем случае это поле d, которое занимает 4 байта. Это и объясняет уже упомянутую выше экономию памяти при использовании объединений.
Размещение полей объединения в одной области памяти позволяет записав одно поле прочитать другое. Например в нашем примере можно занести в поле c символ '0' и прочитать из поля b его код 0x30. Занесение в поле b числа 53 (0x35) вызовет изменение и поля c, там будет символ '5'. Это позволяет использовать объединения для преобразования типов данных. Например можно объединить двухсимвольный массив и целое, при этом появится возможность работать как с целым числом, так и с составляющими его младшим и старшим байтом. Но в большинстве обычных применений такая особенность может привести к ошибкам. Поэтому компилятор, или среда времени выполнения, могут контролировать значение ключевого поля (в Pascal, для записей с вариантами, или в ADA) и не допускать обращения к недействительному, на данный момент, полю объединения.
В языке С существует еще один тип структур - битовые поля. Так как в других языках такой тип отсутствует, коснусь его лишь вкратце. Размещение структуры с битовыми полями отличается от размещения обычной структуры лишь тем, что поля размещаются не на границе байт или слов, а на границе битов. Это позволяет, например, разместить в одном байте два числа, каждое по 4 бита (тетрада). Кажущаяся экономия памяти обманчива. Работа с битовыми полями медленнее, а код, генерируемый компилятором, длиннее. Поэтому данная возможность, чаще всего, используется в программах работающих с регистрами оборудования и прочих системных штучках. Кстати, для битового поля операция взятия адреса неприменима, так как минимально адресуемой единицей памяти является байт, а не бит. Однако, использование битовых полей при программировании микроконтроллеров имеет свои тонкости. Например, семейство MCS51 позволяет получать адрес отдельного бита. Кроме того, в микроконтроллерах память программ и данных бывает разделена (семейство base и midrange PIC Microchip), что может привести к необходимости экономии памяти данных даже в ущерб экономии памяти программ.
Вы можете обсудить данную статью или задать вопросы автору на форуме