Зона кода

А давайте немного попрограммируем...

Кастомизация стека

C99Контейнеры

На этом сайте были опубликованы 4 статьи, посвящённые разработке стека на языке C99. Вот ссылки на эти статьи: первая, вторая, третья, четвёртая. Напомню, что элементами нашего стека являлись значения типа void *, т. е. нетипизированные адреса.

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

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

Новый стек мы будем разрабатывать на основе старого, т. е. будем кастомизировать старый стек, тем самым "превращая" его в новый.

Основная идея

В дальнейшем я буду предполагать, что читатель уже знаком с упомянутыми мной 4-мя статьями, в которых описывалась разработка предыдущего варианта стека. В четвёртой статье приведена ссылка, по которой можно скачать исходный код библиотеки для работы со стеком, состоящей из заголовочного файла stack.h и файла с исполняемым кодом stack.c. Мы переименуем эти файлы в custom_stack.h и custom_stack.c соответственно, после чего будем их переделывать.

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

#define el_type int

В данном случае в качестве базового типа стека выбран тип int. Это определение должно являться частью библиотеки. Поскольку эта часть является изменяемой пользователем стека, с моей точки зрения, разумно поместить её в отдельный файл, называемый, например, el_type.h. Данный файл директивой препроцессора #include необходимо включить в заголовочный файл custom_stack.h.

Заметим, что если базовый тип стека является пользовательским, то его описание тоже должно быть включено в файл el_type.h.

Теперь основные изменения, которые мы должны произвести в файлах custom_stack.h и custom_stack.c, заключаются в замене типа void * макросом el_type. Но перед тем, как внести изменения в код, обсудим достоинства и недостатки конструируемого нами стека.

Достоинства и недостатки кастомизированного стека

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

Начнём с достоинств. Главное — это то, что при использовании стека можно вообще отказаться от работы с адресами и не вспоминать о них. А теперь по порядку.

  1. Чтобы получить фактический элемент, адрес которого вытолкнут из старого стека, нам нужно результат, возвращённый функцией pop(), привести к типу "указатель на тип фактического элемента", после чего полученное значение разыменовать. Поясним на примере, в котором типом фактического элемента является int:

    int a = *(int *) pop(&stack);

    В случае нового стека функция pop() будет возвращать уже "готовое" значение, которое преобразовывать не нужно:

    int a = pop(&stack);
  2. Предположим, что мы хотим поместить в стек в качестве фактического элемента константу встроенного типа, например, 5. Функции push() мы не сможем передать в качестве аргумента константу 5, поскольку push() принимает только адреса. Поэтому придётся сначала создать переменную, присвоить ей значение 5, и только после этого адрес переменной передать функции push():

    int a = 5;
    stack = push(stack, &a);

    А в случае нового стека создавать новую переменную не нужно. Просто передаём константу функции push() и всё:

    stack = push(stack, 5);
  3. Может случиться так, что по адресу, помещённому в старый стек, память была выделена динамически, причём, кроме как в стеке, этот адрес больше нигде не хранится. Именно такой подход заполнения стека был нами использован при построении анализатора, являющегося частью текстового калькулятора. Тогда после выталкивания этого адреса из стека нужно не забыть освободить память.

    Вернёмся к примеру из пункта 1, в котором элемент выталкивается из старого стека:

    int a = *(int *) pop(&stack);

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

    int *p = pop(&stack), a = *p;
    free(p);

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

    Если же мы работаем с новым стеком, то таких проблем не возникает в принципе. Фактические элементы нового стека создаются посредством копирования, производимого в функции push(), причём память динамически выделяется для контейнера (т. е. переменной типа node), в котором хранится копия. А при вызове pop() верхний элемент стека уничтожается вместе с контейнером, а функция возвращает его копию, память для которой динамически не выделялась.

А теперь — к недостаткам.

  1. Первый недостаток является следствием ключевой особенности кастомизированного стека — "заточенности" под конкретный тип. Заключается он в отсутствии универсальности, т. е. возможности хранить в одном стеке элементы различных типов. А старый стек, благодаря тому, что хранит адреса, позволяет манипулировать с фактическими элементами произвольных типов.
  2. Для каждого значения, хранящегося как в старом, так и в новом стеках, по крайней мере дважды выполняется операция копирования: в функции push() и в функции pop(). Кроме того, на каждое такое значение приходится одна операция динамического выделения памяти, и одна — её освобождения.

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

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

  3. После того, как мы определяем нужным нам образом макрос el_type, мы можем создавать стеки только с базовым типом el_type, и больше ни с каким, т. е. 2 стека с разными базовыми типами создать не получится.

    Действительно, мы не можем заставить библиотеку скомпилироваться с двумя разными значениями el_type. Для решения проблемы нужно создавать копии файлов custom_stack.h, custom_stack.c и el_type.h, переименовывать их и определять два разных макроса, задающих базовые типы стеков.

  4. Само по себе наличие изменяемой части библиотеки, подразумевающее, что пользователь вынужден редактировать исходный код библиотеки перед её использованием, уже является её недостатком. В частности, он приводит к тому, что библиотека должна компилироваться вместе с другими файлами проекта. Не получится заранее скомпилировать её "раз и навсегда", после чего подключать к совершенно разным проектам.

Исходный код

Переходим к построению самой библиотеки. Как уже было сказано, начинаем мы с переименования файлов. Далее приступаем к редактированию файла custom_stack.h. Добавляем в него директиву #include, подключающую файл el_type.h, и в некоторых прототипах функций меняем void * на el_type. Изменения нужно внести в 5 прототипов. Вот итоговое содержимое файла custom_stack.h:

#include <stdlib.h>
#define _GNU_SOURCE
#include <stdio.h>
#include <string.h>
#include "el_type.h"

struct node
{
    el_type element;         //Указатель, содержащий элемент стека
    struct node *next;       //Указатель на следующий узел
};
     
typedef struct node node;    //Для удобства введём короткое обозначение для struct node

node *push(node *stack, el_type element);
el_type pop(node **pstack);
el_type peek(node *stack);
int count(node *stack);
node *invert(node *stack);
char *print_down(node *stack, char *string, int max_size,
                 char *(*print_element) (el_type element));
char *print_up(node *stack, char *(*print_element) (el_type element));

Теперь переходим к файлу custom_stack.c. Перед тем, как мы приступим к редактированию содержащихся в нём функций, сделаем одно замечание.

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

while (pop(&stack));

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

Если, всё-таки, одна из этих функций будет вызвана для пустого стека, то будет выведено сообщение об ошибке и выполнение программы будет прервано. За эти действия будет отвечать функция void_stack(), которую мы внесём в файл custom_stack.c. Вот её код:

//Функция, прекращающая работу программы в случае попытки
//прочитать элемент пустого стека или вытолкнуть элемент
//из пустого стека
void void_stack()
{
    printf("Попытка обращения к верхнему элементу несуществующего стека\n");
    printf("Работа программы прекращена\n");
    exit(1);
}

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

while (stack)
    pop(&stack);

Теперь переходим к редактированию функций, уже имеющихся в файле custom_stack.c.

Функция pmalloc() остаётся без изменений:

//Функция, динамически выделяющая память размера size
//и возвращающая адрес выделенного участка в случае успеха,
//или завершающая работу программы в случае неудачи
void *pmalloc(size_t size)
{
    void *p = malloc(size);
    if (p)
        return p;
    printf("Недостаточно памяти. Работа программы прекращена\n");
    exit(1);
}

В функции push() заменяем тип void * макросом el_type в списке аргументов:

//Функция, проталкивающая в стек stack элемент element
//и возвращающая новое значение стековой переменной
node *push(node *stack, el_type element) 
{
    node *new_node = pmalloc(sizeof(node));       //Выделяем память на новый узел
    new_node->element = element;                  //Присваиваем значения
    new_node->next = stack;                       //его полям
    return new_node;                              //Возвращаем адрес созданного узла
}

В функции pop() помимо замены типа void * макросом el_type изменяем действие, выполняющееся в случае отсутствия элементов в стеке: вместо возврата нуля вызываем функцию void_stack():

//Функция, выталкивающая из стека верхний элемент
el_type pop(node **pstack)                     //Формальный параметр назовём pstack, чтобы
{                                              //подчеркнуть, что это адрес стековой переменной
    if (*pstack)                               //Если стек непустой
    {
        node *first_node = *pstack;            //Извлекаем 1-й узел списка
        *pstack = first_node->next;            //Помещаем в стековую переменную адрес 2-го узла
        el_type element = first_node->element; //Извлекаем из 1-го узла верхний элемент стека
        free(first_node);                      //Удаляем узел
        return element;                        //Возвращаем верхний элемент стека
    }
    void_stack();                              //Если стек пуст, то прекращаем работу программы
}

Замены в функции peek() аналогичны предыдущим:

//Функция, возвращающая верхний элемент без удаления его из стека
el_type peek(node *stack)
{
    if (stack)
        return stack->element;
    void_stack();                             //Если стек пуст, то прекращаем работу программы
}

Функция count() изменению не подлежит:

//Функция, возвращающая количество элементов, хранящихся в стеке
int count(node *stack)
{
    int i = 0;
    for(; stack; i++)
        stack = stack->next;
    return i;
}

Не требуется изменять и функцию invert():

//Функция, инвертирующая стек
node *invert(node *stack)
{
    if (!stack)
        return 0;
    node *stack2 = stack->next, *temp;
    stack->next = 0;
    while (stack2)
    {
        temp = stack2->next;
        stack2->next = stack;
        stack = stack2;
        stack2 = temp;
    }
    return stack;
}

А вот функцию print_down() изменить придётся. Правда, изменения коснутся только списка аргументов: тип void * заменим макросом el_type:

//Функция, распечатывающая стек в направлении сверху вниз
char *print_down(node *stack, char *string, int max_size,
                 char *(*print_element) (el_type element))
{
    if (!stack)
    {
        snprintf(string, max_size, "{}");
        return string;
    }
    char *str = string, *str2;
    int c;
    snprintf(string++, max_size--, "{");
    while (stack)
    {
        c = snprintf(string, max_size, "%s, ", str2 = (*print_element) (stack->element));
        free(str2);
        string += c;
        max_size -= c;
        stack = stack->next;
    }
    snprintf(string - 2, max_size + 2, "}");
    return str;
}

Изменения, которые нужно внести в функцию print_up(), — самые большие по объёму. В старой версии функции использовался стек для хранения адресов строк, из которых впоследствии формировалась результирующая строка. Соответствующая стековая переменная называлась stack2. Для этого стека вызывались функции push() и pop() (их старые версии, разумеется). Но старые версии этих функций уже заменены новыми, которые не годятся.

Поэтому я решил для хранения адресов строк использовать массив. Для этого небольшой фрагмент кода функции пришлось переписать заново. Помимо этого изменения, тип void * в заголовке функции заменён макросом el_type. Ниже приведён код функции print_up().

//Функция, распечатывающая стек в направлении снизу вверх
char *print_up(node *stack, char *(*print_element) (el_type element))
{
    if (!stack)
    {
        char *string = pmalloc(3);
        sprintf(string, "{}");
        return string;
    }
    int i = 0, j = 0;
    char *strings[count(stack)];
    char *string, *str;
    while (stack)
    {
        strings[i++] = str = (*print_element) (stack->element);//printf("\ni=%d ", i);
        j += strlen(str);
        stack = stack->next;
    }
    str = string = pmalloc(j + 2 * i + 1);
    sprintf(string++, "{");
    while (--i)
    {
        string += sprintf(string, "%s, ", strings[i]);
        free(strings[i]);
    }
    sprintf(string, "%s}", strings[0]);
    free(strings[0]);
    return str;
}

Никаких проблем в определении размера массива strings, использующегося вместо стека, не возникло. Он должен совпасть с количеством элементов  распечатываемого стека, которое можно найти с помощью функции count() (см. строку 11). Массив заполняется адресами строк в направлении от "начала к концу" (см. строки 13-18), а считываются адреса из массива в противоположном направлении (см. строки 21-26). Таким образом, можно сказать, что операции с массивом имитируют работу со стеком.

Как мы помним, файл stack.c содержал ещё закомментированные альтернативные варианты некоторых функций, играющие лишь учебную роль. Из файла custom_stack.c мы их просто удалим и рассматривать не будем.

Ну что ж, файл custom_stack.c готов к использованию. Но нельзя забывать, что библиотека должна ещё содержать файл el_type.h, формируемый пользователем стека.

Тестирование стека (1-й вариант)

Протестируем созданную библиотеку для базового типа int. Для начала создадим файл el_type.h, содержащий единственную строку:

#define el_type point

Весь тестирующий код поместим в файл stack_test.c. Ниже приведено его содержимое.

#include "custom_stack.h"    //Макрос el_type, тип node и функции для работы со стеком
 
char *print_element(int element)
{
    char *str;
    asprintf(&str, "%d", element);
    return str;
} 
     
int main()
{
    node *stack = 0;
    int a = 3, b = 5;
    stack = push(stack, a);
    stack = push(stack, b);
    stack = push(stack, 10);
    stack = push(stack, 2.7);
    stack = push(stack, a + b - 10);
    char string[20], *str;
    printf("Cтек сверху вниз: %s", print_down(stack, string, 20, print_element));
    printf("\nCтек снизу вверх: %s", str = print_up(stack, print_element));
    free(str);
    printf("\nВыталкиваем верхний элемент: %d", pop(&stack));
    printf("\nCтек сверху вниз: %s", print_down(stack, string, 20, print_element));
    printf("\nПросматриваем верхний элемент: %d", peek(stack));
    printf("\nЭлементов в стеке: %d", count(stack));
    printf("\nИнвертируем стек");
    stack = invert(stack);
    printf("\nCтек сверху вниз: %s", print_down(stack, string, 20, print_element));
    printf("\nЭлементов в стеке: %d", count(stack));
    printf("\nОчищаем стек");
    while (stack)
        pop(&stack);
    printf("\nCтек сверху вниз: %s", print_down(stack, string, 20, print_element));
    return 0;
}

Функция print_element() требуется для распечатки стека. Она преобразует в строку единственное значение типа, являющегося базовым для стека (int в нашем случае); для печати всего стека её адрес необходимо передать одной из функций print_up() или print_down().

Непосредственно тестирование осуществляется функцией main(). Из неё вызываются все функции, объявленные в файле custom_stack.h. Думаю, что код предельно понятен, тем более, что большинство операций комментируется внутри вызовов функции printf().

Обращу внимание читателей лишь на то, что в ходе вызова функции push() роль второго фактического аргумента играют то переменные (строки 14, 15), то константы, причём, разных типов (строки 16, 17), то выражение (строка 18). Разумеется, все эти вызовы корректны. В этой "всеядности" функции push() как раз проявляется достоинство кастомизированного стека, фигурирующего в нашем списке достоинств под номером 2.

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

Cтек сверху вниз: {-2, 2, 10, 5, 3}
Cтек снизу вверх: {3, 5, 10, 2, -2}
Выталкиваем верхний элемент: -2
Cтек сверху вниз: {2, 10, 5, 3}
Просматриваем верхний элемент: 2
Элементов в стеке: 4
Инвертируем стек
Cтек сверху вниз: {3, 5, 10, 2}
Элементов в стеке: 4
Очищаем стек
Cтек сверху вниз: {}

Тестирование стека (2-й вариант)

Теперь протестируем стек, выбрав в качестве базового типа point — структуру с двумя полями типа int. Переменные типа point будут соответствовать точкам на плоскости с целочисленными координатами.

Напоминаю, что, поскольку point будет являться значением макроса el_type, данный тип должен быть описан в файле el_type.h. Данное описание, разумеется, должно предшествовать определению макроса el_type.

Ниже приведено содержимое файла el_type.h

typedef struct
{
    int x;
    int y;
} point;

#define el_type point

Переделаем функции print_element() и main() в файле stack_test.c. Теперь первая из них будет преобразовыввать в строку переменые типа point. Строка будет содержать координаты точки на плоскости, разделённые запятой и помещённые в круглые скобки. А во второй функции будут выполняться те же самые операции со стеком, что и в функции main() из 1-го варианта тестирующей программы, однако на этот раз элементами стека будут значения типа point.

Вот как выглядит изменённая версия файла stack_test.c:

#include "custom_stack.h"    //Макрос el_type, типы point и noode, 
                             //функции для работы со стеком
char *print_element(point element)
{
    char *str;
    asprintf(&str, "(%d, %d)", element.x, element.y);
    return str;
} 
     
int main()
{
    node *stack = 0;
    point a = {2, 3}, b = {-1, 6};
    stack = push(stack, a);
    stack = push(stack, b);
    stack = push(stack, (point) {-5, 9});
    stack = push(stack, (point) {10, -14});
    char string[40], *str;
    printf("Cтек сверху вниз: %s", print_down(stack, string, 40, print_element));
    printf("\nCтек снизу вверх: %s", str = print_up(stack, print_element));
    free(str);
    printf("\nВыталкиваем верхний элемент: %s", str = print_element(pop(&stack)));
    free(str);
    printf("\nCтек сверху вниз: %s", print_down(stack, string, 40, print_element));
    printf("\nПросматриваем верхний элемент: %s", str = print_element(peek(stack)));
    free(str);
    printf("\nЭлементов в стеке: %d", count(stack));
    printf("\nИнвертируем стек");
    stack = invert(stack);
    printf("\nCтек сверху вниз: %s", print_down(stack, string, 40, print_element));
    printf("\nЭлементов в стеке: %d", count(stack));
    printf("\nОчищаем стек");
    while (stack)
        pop(&stack);
    printf("\nCтек сверху вниз: %s", print_down(stack, string, 50, print_element));
    return 0;
}

На этот раз мы помещаем в стек первоначально 4 значения (см. строки 14-17). Как мы видим, первые 2 из них содержатся в переменных a и b, а 3-е и 4-е задаются литералами. Ниже приведён результат работы данной программы.

Cтек сверху вниз: {(10, -14), (-5, 9), (-1, 6), (2, 3)}
Cтек снизу вверх: {(2, 3), (-1, 6), (-5, 9), (10, -14)}
Выталкиваем верхний элемент: (10, -14)
Cтек сверху вниз: {(-5, 9), (-1, 6), (2, 3)}
Просматриваем верхний элемент: (-5, 9)
Элементов в стеке: 3
Инвертируем стек
Cтек сверху вниз: {(2, 3), (-1, 6), (-5, 9)}
Элементов в стеке: 3
Очищаем стек
Cтек сверху вниз: {}

Заключение

И старая, и новая версии стека имеют свои достоинтсва и недостатки. Выбор того или иного варианта стека определяется уже конкретной задачей, которая стоит перед пользователем. Заметим, что, несмотря на то, что кастомизированный стек "заточен" под конкретный базовый тип, сама библиотека "custom_stack.h" является более универсальной, чем "stack.h".

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

Скачать исходный код