technical-requirement.md

Техническое задание

Общие требования. Данное техническое задание формулирует следующие требования к вашему ПО:

1. Модуль, реализующий стек, должен быть выполнен как статическая библиотека. Это требование выполняется автоматически (CMakeLists.txt) - весь код из cstack.c попадет в библиотеку.
2. Библиотека должна собираться, т.е. в ней не должно быть ошибок компиляции и линковки (за исключением ситуации отсутствия на машине сборки стандартной библиотеки C).
3. Библиотека не должна иметь зависимостей иных, чем стандартная библиотека C. Не сомневаюсь, что при должном упорстве можно найти готовые реализации стека на С, удовлетворяющие нашим требованиям. Это не наш случай 🥲.
4. Функции библиотеки должны удовлетворять требованиям, описанным ниже.
5. Библиотека должна корректно освобождать ресурсы памяти при должном использовании.
6. Библиотека должна быть отказоустойчива (в разумных пределах) к входным данным функций, т.е. должны быть введены разумные проверки на нулевой указатель, нулевой размер и т.д. Понятно, что проверить валидность переданного указателя (например, что он не указывает в начало адресного пространства) невозможно или очень трудно, но полноценная проверка и не является ответственностью библиотеки.
7. В ходе нормального выполнения и использования кода библиотеки не должны возникать ошибки сегментации, переполнения стека, обращения к памяти и др.
8. Библиотека не гарантирует: освобождение ресурсов памяти при некорректном использовании функций библиотеки; отсутствие недекларированного поведения в случае передачи невалидного указателя (за исключением нулевого указателя).

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

Особенности нашей реализации стека.

1. Библиотека может одновременно обслуживать несколько стеков.
2. Количество одновременно обслуживаемых стеков не должно быть меньше 10.
3. Данные, хранимые в стеке, не типизированны.

Требования к функциям библиотеки. Одним из аргументов большинства функций библиотеки является хэндлер стека с типом t_hstack. Этот тип является псевдонимом типа int и к реализации стека в памяти отношения не имеет. Скорее это абстрактный идентификатор, который нужен, чтобы отличить один стек от другого. Отмечу, что в C использование хэндлера, (дескриптора), является стандартной практикой. Примеры: hInstance в WinAPI, возвращаемое значение функции open в POSIX. Объявление этого типа находится в заголовочном файле cstack.h.

• hstack_t stack_new(void)
  Brief: Создать новый стек.
  Returns: -1 в случае ошибки выполнения, хэндлер нового стека с неотрицательным значением в случае успеха.

• void stack_free(const hstack_t stack)
  Brief: Удалить стек, если соответствующий хэндлеру стек существует.
  Parameters: stack - хэндлер стека.

• int stack_valid_handler(const hstack_t stack)
  Brief: Проверить хэндлер.
  Parameters: stack - хэндлер стека.
  Returns: 0 - соответствующий хэндлеру стек существует, 1 - нет.

• unsigned int stack_size(const hstack_t stack)
  Brief: Получить количество элементов в стеке, если соответствующий хэндлеру стек существует.
  Parameters: stack - хэндлер стека.
  Returns: количество элементов в стеке, если соответствующий хэндлеру стек существует, или 0 в противном случае.

• void stack_push(const hstack_t stack, const void* data_in, const unsigned int size)
  Brief: Добавить элемент данных из буфера в стек, если соответствующий хэндлеру стек существует.
  Parameters: stack - хэндлер стека; data_in - указатель на буфер с данными; size - размер буфера с данными.

• unsigned int stack_pop(const hstack_t stack, void* data_out, const unsigned int size)
  Brief: Извлечь элемент из стека и записать данные этого элемента в буфер, если соответствующий хэндлеру стек существует.
  Parameters: stack - хэндлер стека; data_out - указатель на буфер для записи данных; size - размер буфера.
  Returns: размер записанных данных в байтах, если соответствующий хэндлеру стек существует, или 0 в противном случае.

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

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

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

struct node
{
    const struct node* prev;
    unsigned int size;
    char data[0];
};

typedef struct node* stack_t;

Такой подход напоминает другую структуру данных односвязный список. Из общего у них наличие указателя на предыдущий элемент. При добавлении нового элемента в стек удобно в рантайме посчитать количество данных элемента стека (размер указателя на предыдущий элемент prev + размер поля size + размер самих данных), аллоцировать эти данные и заполнить их. Это не единственно верный вариант, возможны альтернативы.

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

struct stack_entry
{
    int reserved;
    stack_t stack;
};

typedef struct stack_entry stack_entry_t;

struct stack_entries_table
{
    unsigned int size;
    stack_entry_t* entries;
};

struct stack_entries_table g_table = {0u, NULL};

Пошаговая инструкция

1. Если вы незнакомы с системой контроля версий Git, познакомьтесь с её основами. Во всех дальнейших домашних работах вам эти знания всё равно понадобятся. Для начала достаточно изучить самые базовые команды (add, commit, pull, push и несколько других). Начать знакомство рекомендую здесь.
2. Заведите профиль на https://github.com/.
3. Сделайте форк репозитория. После этого в вашем аккаунте среди ваших репозиториев появится копия данного репозитория с веткой master. Включите GitHub Actions для вашего форка.
4. Склонируйте репозиторий на ваш компьютер. Создайте ветку в вашем репозитории с названием, отличным от master. В командной строке Linux или GitBash на Windows это можно сделать следующим образом:

   git clone <ссылка из буфера обмена>
   cd prosoft-c-stack/
   git checkout -b development
   git push --set-upstream origin development

5. Выполните вашу первую реализацию задания, закоммитьте и запушьте изменения.

   git add cstack.c
   git commit -m "my first commit"
   git push

6. Создайте пулл-реквест в вашем репозитории из вашей ветки в ветку master. Обратите внимание, что в качестве base ветки нужно выбрать ветку из вашего репозитория.
7. В названии пулл-реквеста укажите фамилию и имя.
8. Добавьте меня (czertyaka) в качестве коллаборатора в ваш проект.
9. После этого я появлюсь в списке коллабораторов в статусе Pending Invite. На мою почту придет письмо, в котором меня попросят присоединиться к вашему проекту. После моего присоединения:
10. Добавьте меня в качестве рецензента в ваш пулл-реквест.
11. Дальше начинается процесс ревью. Если у меня есть замечания, я их делаю, вы правите код.

Вот тут подробнее про совместную работу над проектами, форки, пулл-реквесты и т.д.