Типобезопасные общие структуры данных в C

Ян Фишер – 7 июня история

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

Или следуйте мой RSS-канал .

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

Разминка: и int стек

Общая структура данных мы будем реализовывать это стек. В качестве разминки мы напишем обычный, не общий стек, который работает только для int значения. Наш минималистичный стек будет поддерживать только две операции, push и pop – не самая полезная структура данных, но достаточная, чтобы покрыть фундаментальные проблемы реализации структуры данных.

Внутреннее состояние нашего стека состоит из длины, емкости и указателя на данные, размещенные в куче. Длина – это количество элементов в стеке, а емкость – это максимальное количество элементов, которое может вместить выделенная память (а не размер выделенной памяти в байтах, который равен capability sizeof (int) ).

  
 typedef   struct  { size_t  лен, вместимость;   int данные;  } IntStack;  

Кроме того: Вы можете найти полный код этого сообщения здесь.

Начнем с операции push. Во-первых, размер стека изменяется, если не хватает емкости для дополнительного элемента. Затем длина стека увеличивается, и значение записывается в конец массива данных: 2

  пустота IntStack_push (IntStack stck, 
 int  значение) {  if  (! stck) { возвращаться;  } если (stck-> len +  1 > шток-> емкость) { 
 /  ДЕЛАТЬ: Обработка арифметического переполнения.  /   size_t  new_capacity = stck-> capability  2 ;   int  new_data = realloc (stck-> information, new_capacity 
размер( int ));  если (! новые_данные) {
 /  ДЕЛАТЬ : обработка ошибки памяти.  /  возвращаться;  } stck-> capability = new_capacity;  stck-> information = new_data;  } stck-> len ++;  stck-> данные  = значение;  }  

Обратите внимание, что realloc может возвращать нулевой указатель, если не может повторно выделить память, поэтому назначать возвращаемое значение

stck-> information , не проверяя сначала, является ли он нулевым. Также обратите внимание, что использование realloc предполагает, что stck-> данные были ранее выделены с помощью malloc , предположение, что будет поддерживаться конструктором, который мы напишем позже.

Операция pop уменьшает поле длины и возвращает предыдущий последний элемент. Возвращаемое значение заключено в IntResult структура данных, поскольку в случае, что stck имеет значение NULL или пусто, нет всплывающего значения для возврата. 3

IntResult IntStack_pop (IntStack stck) {

 if  (! stck || stck-> len ==  0 ) { return  IntResult_error ();  } stck-> len--;  возвращаться IntResult_of (stck-> information [stck->len]);  }  

IntResult и его конструкторы определены следующим образом:

 

typedef struct {логическая ошибка;
 int  результат;  } IntResult;  IntResult IntResult_of (
 int  v) {IntResult r = {.error = false, .consequence = v};  возвращаться р;  } IntResult IntResult_error () {IntResult r = {.error = true};  возвращаться р;  }  

Мы также предоставим конструктор для удобного создания Объекты IntStack . Он инициализирует стек длиной 0 и небольшой начальной емкостью памяти, выделенной кучей.

IntStack IntStack_new () {

 size_t  емкость = 
 8 ;   int  данные = malloc (емкость размер(
 int ));  если (!данные) {  /  ДЕЛАТЬ : обработка ошибки памяти.  / } IntStack stck = {.len = 
 0 , .capability = емкость, .information = information};  возвращаться наклеить;  }  

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

 

void IntStack_free (IntStack stck) {
 если  (stck) {бесплатно (stck-> information);  }}  

И с этим у нас есть минимальный, но полный класс стека:

  IntStack int_stack = IntStack_new ();  IntStack_push (& int_stack, 
 1 );  IntStack_push (& int_stack, 
 2 );  IntResult r = IntStack_pop (& int_stack);  assert (! r.error);  assert (r.consequence ==  2 );  IntStack_free (& int_stack);  

Небезопасный общий стек

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

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

В C двоичные данные могут храниться в массиве char s. В качестве примера предположим, что мы определяем

Точку тип:

   typedef   struct  {
 int  x, y;  } Точка;

Мы можем сохранить Точку объект в массив char , используя memcpy , чтобы скопировать байты в массив:

   // Инициализируем массив с более чем достаточной емкостью.  
 символ  данные[100];  
 // Инициализировать объект Point.  Точка p = {.x =  42 ,. y =  100 };  
 // Копируем объект Point в массив.  memcpy (данные, & p, размер(Точка));  
 // Распечатать байты массива.  для (
 size_t  i =  0 ; i <размер (Точка); i ++) {printf ( "данные [%ld] =% d    n   ", i, данные [i]);  }  

В моей системе цикл for печатает

  данные [0] = 42 данные [1] = 0 данные [2] = 0 данные [3] = 0 данные [4] = 43 данные [5] = 0 данные [6] = 0 данные [7] = 0  

Но отдельные элементы массива должны рассматриваться как непрозрачные, поскольку структура памяти Point зависит от компилятора.

Этот метод является основой нашего общего типа стека UnsafeStack .

4 UnsafeStack имеет char information вместо поля int information и дополнительный objsize поле для отслеживания, сколько байтов занимает каждый объект:

  
 typedef   struct  { 
 size_t  лен, вместимость;  
 size_t  objsize;   символ данные;  } UnsafeStack;  

Логика изменения размера массива в UnsafeStack_push аналогичен IntStack_push . Как мы видели в Level , мы должны использовать memcpy , чтобы скопировать значение в конец стека, а не назначать его напрямую индексу массива, потому что значение может быть сколь угодно большим.

UnsafeStack_push принимает значение типа void , чтобы в него можно было передавать любые объекты любого типа

  пустота UnsafeStack_push (UnsafeStack stck, 
 void значение) { если (! stck) { возврат ;  } если (stck-> len +  1 > шток-> емкость) { 
 size_t  new_capacity = stck-> capability  2 ;   символ  new_data = realloc (stck-> information, new_capacity stck-> objsize);  если (! новые_данные) {
 /  ДЕЛАТЬ : обработка ошибки памяти.  /  возвращаться;  } stck-> capability = new_capacity;  stck-> information = new_data;  } memcpy (stck-> information + (stck-> len stck-> objsize), worth, stck-> objsize);  stck-> len ++;  }  

Аналогично UnsafeStack_pop возвращает указатель типа void , потому что тип объектов в данных структура неизвестна во время компиляции. Указатель представляет собой смещение в массиве, рассчитанное как

stck-> len stck-> objsize :

 

void UnsafeStack_pop (UnsafeStack stck) {
 если  (! stck || stck-> len ==  0 ) { возвращаться НОЛЬ;  } stck-> len--;  возвращаться stck-> information + (stck-> len stck-> objsize);  }  

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

UnsafeStack_new и UnsafeStack_free очень похожи на предыдущие:

  UnsafeStack UnsafeStack_new (
 size_t  objsize) {
 size_t  емкость = 
 8 ;   символ  данные = malloc (емкость размер);  если (! information) {} UnsafeStack stck = {.len =  0 , .capability = емкость, .objsize = objsize, .information = information};  возвращаться наклеить;  } пустота UnsafeStack_free (UnsafeStack stck) {
 если  (stck) {бесплатно ( stck-> information);  }}  

UnsafeStack API немного отличается от IntStack файлы. При помещении значения в стек мы предоставляем указатель на него, а не на сам элемент, а при извлечении значения мы приводим возвращаемое значение, а затем отменяем ссылку на него.

 

UnsafeStack_push (& unsafe_stack, & i);
 int  v = ( int   UnsafeStack_pop (& unsafe_stack);  

Поскольку UnsafeStack_push принимает аргумент-указатель, мы не можем передавать ему целочисленные литералы. Безопасный универсальный стек с использованием макросы

В отличие от приведений в Java и

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

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

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

IntStack замените все использования

int с тип , а затем оберните всю реализацию в макросе, параметризованном по типу

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

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

IntStack . Синтаксис typename ## _ new , typename ## _ free , и т. д., сообщает препроцессору, что нужно выполнить склейку имя типа , a параметр макроса для буквальных строк, например _ new или _ бесплатно , давая такие результаты, как FloatStack_new или StringStack_free . Параметр макроса тип заменяется везде, где у нас было

int в оригинале Код IntStack код.

   # определить DECL_STACK (typename, kind)   
 typedef struct {   size_t len, вместимость;     тип данные;    } typename;        typedef struct {   ошибка типа bool;     тип результат;    } typename ## Результат;       
 typename typename ## _ new () {   size_t вместимость = 8;     тип данные = malloc (емкость размер (тип));     if (! information) {}    typename stck = {.len = 0, .capability = емкость, .information = information};     return stck;    }   
    void typename ## _ free (typename stck) {  
 if (stck) {   бесплатно (stck-> information);    }   
}       size_t typename ## _ size (typename stck) {   вернуть stck?  stck-> len: 0;    }   
    void typename ## _ push (typename stck, kind worth) {  
 если (! stck) {   возвращаться;    }   
    if (stck-> len + 1> stck-> capability) {  
 size_t new_capacity = stck-> capability 2;     тип new_data = realloc (stck-> information, new_capacity sizeof (kind));       
 если (! новые_данные) {   возвращаться;    }   
    stck-> capability = new_capacity;     stck-> information = new_data;    }       stck-> len ++;     stck-> information [stck->len - 1] = значение;    }   
    typename ## End result typename ## _ pop (typename stck) {  
 если (! stck || stck-> len == 0 ) {   typename ## Результат errorval = {.error = true};     вернуть errorval;    }   
    тип значение = stck-> information [stck->len - 1];     stck-> len--;     typename ## End result r = {.error = false, .consequence = worth};     вернуть r;    }   

Затем мы вызываем DECL_STACK для объявления нового типа стека либо в файле заголовка, либо на верхнем уровне программы:

  DECL_STACK (SafeIntStack ,  int )   

Результирующий API обеспечивает безопасность и удобство IntStack и универсальность UnsafeStack :

SafeIntStack safe_int_stack = SafeIntStack_new (); SafeIntStack_push (& safe_int_stack, 1 ); SafeIntStack_push (& safe_int_stack, 2 ); SafeIntStackResult r = SafeIntStack_pop (& safe_int_stack); assert (! r.error); assert (r.consequence == 2 ); SafeIntStack_free (& safe_int_stack);

Обратите внимание, что

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

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

То, что можно писать типобезопасные универсальные структуры данных на языке, чья система типов изначально не поддерживает их, говорит о гибкости C. 5 Но используемые нами техники - неконтролируемое приведение указателей и антисанитарные лексические макросы - сами по себе весьма небезопасны при неправильном использовании. Гибкость, простота и безопасность: язык может достигать максимум двух из трех. Rust и Haskell выбирают гибкость и безопасность. Go выбирает безопасность и простоту. 6 C выбирает гибкость и простоту. Каждый выбор имеет свои компромиссы. Тенденция современных языков предпочитать безопасность является прямым следствием бесчисленных ошибок, обнаруженных в коде C, которые можно было бы предотвратить с помощью более надежных гарантий времени компиляции. Тем не менее, как показал этот пост, гибкость и простота - мощное сочетание.