Включение наследования в C с использованием структурной композиции

Автор оригинала: Arpit Bhayani.

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

Композиция структуры – это когда мы помещаем одну структуру в другую не через ее указатель, а как собственный член-что-то вроде этого

// this structure defines a node of a linked list and
// it only holds the pointers to the next and the previous
// nodes in the linked list.
struct list_head {
  struct list_head *next; // pointer to the node next to the current one
  struct list_head *prev; // pointer to the node previous to the current one
};

// list_int holds an list_head and an integer data member
struct list_int {
  struct list_head list;  // common next and prev pointers
  int value;              // specific member as per implementation
};

// list_int holds an list_head and an char * data member
struct list_str {
  struct list_head list;  // common next and prev pointers
  char * str;             // specific member as per implementation
};

В приведенном выше примере мы определяем узел связанного списка с помощью структурной композиции. Обычно узел связанного списка имеет 3 элемента – два указателя на соседние узлы (следующий и предыдущий), а третий может быть либо данными, либо указателем на них. Определяющим фактором связанного списка являются два указателя, которые логически образуют цепочку узлов. Чтобы сохранить абстракцию, мы создаем структуру с именем list_head , которая содержит эти два указателя next и prev и опускает специфику, т. е. данные.

Используя структуру list_head , если бы мы определили узел связанного списка, содержащий целочисленное значение, мы могли бы создать другую структуру с именем list_int , которая содержит член типа list_head и целочисленное значение value . Следующий и предыдущий указатели вводятся в эту структуру через list_head list и могут называться list.next и list.prev .

Существует вполне реальная причина для выбора таких странных имен для узла связанного списка и членов структур; причина для этого будет прояснена в последующих разделах этого эссе.

Из-за вышеприведенного определения структуры построение узла связанного списка, содержащего любой тип, становится легким делом. Например, строка, содержащая узел, может быть быстро определена как структура list_str имеющая list_head и chair * . Эта способность расширять list_head и создавать узел, содержащий данные любого типа и любой специфики, делает низкоуровневый код простым, единообразным и расширяемым.

Представление памяти list_int

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

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

void print_addrs() {
    // creating a node of the list_int holding value 41434
    struct list_int *ll = new_list_int(41434);

    // printing the address of individual members
    printf("%p: head\n",             head);
    printf("%p: head->list.next\n",  &((head->list).next));
    printf("%p: head->list.prev\n",  &((head->list).prev));
    printf("%p: head->value\n",      &(head->value));
}

~ $ make && ./a.out
0x4058f0: head
0x4058f0: head->list.next
0x4058f4: head->list.prev
0x4058f8: head->value

Мы ясно видим все 3 члена, занимающие 12 байт смежных сегментов памяти в порядке их определения внутри структуры.

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

Приведение указателей, указывающих на структуру

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

Когда мы приводим list_int * в list_head * , движок отображает пространство, требуемое целевым типом, т. е. list_head на пространство, занимаемое list_int . Это означает, что он сопоставляет 8 байтов, необходимых для list_head , с первыми 8 байтами, занятыми экземпляром list_int . Переходя к описанному выше представлению памяти, мы обнаруживаем , что первые 8 байтов list_int на самом деле являются list_head , и, следовательно, приведение list_int * к list_head * фактически просто ссылается на list_head член list_int через новую переменную.

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

Здесь важно отметить, что отношение родитель-потомок устанавливается только потому, что первый член list_int имеет тип list_head . это не сработало бы, если бы мы изменили порядок членов в list_int .

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

Из контекста, который мы создали, скажем, мы хотим написать функцию, которая добавляет узел между ними в связанный список. Основная логика для выполнения этой операции на самом деле не нуждается в какой-либо конкретике, все, что требуется, – это несколько манипуляций указателем next и prev . Следовательно, мы могли бы просто определить функцию, принимающую аргументы типа list_head* , и записать ее как

/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static void __list_add(struct list_head *new,
                       struct list_head *prev,
                       struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

Поскольку мы можем безопасно ввести case list_int * и list_str * в list_head* , мы можем передать любую из конкретных реализаций функции __list_add , и она все равно добавит узел между двумя другими без проблем.

Поскольку основные операции над связанными списками требуют только манипуляций с указателями, мы можем определить эти операции как функции, принимающие list_head * вместо конкретных типов, таких как list_int * . Таким образом, нам не нужно писать подобные функции для специфики. Функция удаления узла может быть записана следующим образом

/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
    next->prev = prev;
    prev->next = next;
}

Другие утилиты связанного списка, такие как добавление узла в хвост , замена узлов , сращивание списка , поворот списка и т. Д., Требуют только манипуляций указателями next и prev . Следовательно, они также могут быть написаны очень похожим образом, то есть принимая list_head * и таким образом устраняя необходимость переопределения логики функций для каждой отдельной дочерней реализации.

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

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

Ядро Linux

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

Иерархия типов и объектов Python

Python, один из самых важных языков в современном мире, использует структурную композицию для построения иерархии типов. Python определяет корневую структуру с именем PyObject , которая содержит счетчик ссылок, определяющий количество мест, из которых ссылается объект, и тип объекта , определяющий тип объекта, т. е. int , str , list , dict и т. Д.

typedef struct _object {
    Py_ssize_t     ob_refcnt;  // holds reference count of the object
    PyTypeObject   *ob_type;   // holds the type of the object
} PyObject;

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

#define PyObject_HEAD PyObject ob_base;

typedef struct {
    PyObject_HEAD
    double ob_fval;    // holds the actual float value
} PyFloatObject;

Теперь написание служебных функций, которые увеличивают и уменьшают количество ссылок при каждом доступе к любому объекту, может быть записано как только одна функция, принимающая PyObject* , как показано ниже

static inline void _Py_INCREF(PyObject *op) {
    op->ob_refcnt++;
}

Таким образом, мы избавляемся от необходимости переписывать INCREF для каждого отдельного типа объекта и просто пишем его один раз для PyObject , и он будет работать для каждого отдельного типа объекта Python, который расширяется через PyObject .

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

Вы всегда можете найти меня в твиттере @arpit_bhayani .