Языков программирования существует великое множество. И часто новые языки создаются потому, что в старых чего-то нехватало. Однако C – язык исключение, несмотря на появление Go и Rust он всё ещё твёрдо держит свои позиции.
Часто C упрекают ввиду его компактности, и поэтому многие вещи приходится писать самому, руками. Однако с другой стороны, такое положение дел, вынуждает разработчиков глубже вникать в устройство типов данных, функций и т. д.
В этой статье я предлагаю читателю рассмотреть, устройство такого популярного типа данных как стек и его реализацию в C. Начнём с определения: — тип данных, представляющий собой список элементов, организованных по принципу LIFO. У неподготовленного, сразу возникнет вопрос, а что же такое LIFO? LIFO – с англ. «last in — first out», «последним пришёл — первым вышел». Для наглядности, представьте себе тарелку в которую складывают блины. Первый положенный блин, в последствии будет последним. А последний положенный, будет съеден первым.
В любой современной машине есть свой аппаратный стек. Для манипулирования им существуют специальные команды языка ассемблера push и pop. Первая добавляет новый элемент в стек, а вторая выталкивает самый верхний элемент, а его значение сохраняет куда-либо (обычно в регистр). Ввиду этого, можно было бы просто использовать аппаратный стек, однако, во первых, он только один, а во вторых, мы не ищем лёгких путей.
Обычно при реализации стека используют 2 указателя: SP – stack pointer (указатель стека) указывает на вершину стека и BS – bottom stack (дно стека), указывает на дно стека. Ситуация когда SP == BS, есть не что иное, как пустой стек. Если стек может быть пустым, то он соответственно может быть и полным.
Однако нередко можно встретить и реализацию стека через связный список, например здесь или на Википедии.
Однако перейдём от слов к делу. Начнём с функции создания стека:
char *stack_new(size_t size) {
return malloc(size);
}В нашем примере, создаётся стек символов размером size, однако ничто не мешает Вам заменить char на int или что-либо другое.
После того как мы создали стек, не плохо было бы удалить его. И так как при создании мы воспользовались функцией malloc, то при удалении нам надо использовать комплиментарную ей free:
void stack_del(char *stack) {
free(stack);
}Перейдём к помещению символов в стек:
static int offset = 0;
void push(char *stack, char val) {
*(stack+offset) = val;
offset++;
}Внимательный читатель заметит присутствие переменной offset, она в данном случае заменяет SP, являясь смещением относительно дна стека (аргумента stack). Так же обращаю внимание на то, что переменная offset объявлена со спецификатором static вне функций, а это значит, она будет видна только в файле в котором объявлена.
Положив символ в стек, его надо вытолкнуть, и для этого есть ещё одна функция:
char pop(char *stack) {
return *stack+(--offset);
}Здесь так же используется offset. И внимательный читатель, заметит, что если стек пуст, то функция отработает, и даже не заметит ошибки, поэтому исправим:
char pop(char *stack) {
if (offset)
return *stack+(--offset);
else
return -1;
}Теперь, в случае пустого стека, будет возвращено -1. Однако стек может и переполниться, поэтому перепишем остальные функции так:
char *stack_new(int len) {
stack_len = len;
return (char*)malloc(sizeof(char) * len);
}
int push(char *stack, char val) {
if (offset == stack_len)
return -1;
*(stack+offset) = val;
offset++;
return 1;
}Теперь, при создании стека, помимо выделения памяти, происходит инициализация переменной stack_len, а если offset == stack_len, значит стек переполнился, и функция push возвратит -1.
Таким образом мы получаем полный исходный файл:
#include <stdlib.h>
static int offset = 0;
static int stack_len = 0;
char *stack_new(int len) {
stack_len = len;
return (char*)malloc(sizeof(char) * len);
}
void stack_del(char *stack) {
free(stack);
}
int push(char *stack, char val) {
if (offset == stack_len)
return -1;
*(stack+offset) = val;
offset++;
return 1;
}
char pop(char *stack) {
if (offset)
return *stack+(--offset);
else
return -1;
}К нему можно добавить дополнительный заголовочный файл и получить библиотеку. А если требуется несколько стеков, то переменные offset, stack_len и указатель *stack можно оформить в структуру.
У меня, всё. Надеюсь для тебя, Читатель, эта статья была полезна.
Комментарии (41)
selrorener
12.01.2020 20:24Это не C, а C/C++.
то переменные offset, stack_len и указатель *stack можно оформить в структуру.
Это нужно сделать по умолчанию, плюс заменить offset/len на нормальные указатели. Плюс взять нормальные типы из stdint.
Ну и для защиты от инквизиции следует падать на malloc() == NULL сразу, а не позже.
Centrix2132 Автор
12.01.2020 20:25-2Я хотел дать базовое представление, чтобы желающий в будущем смогли доработать это как им заблагорассудится.
Centrix2132 Автор
13.01.2020 07:30Ну и для защиты от инквизиции следует падать на malloc() == NULL сразу, а не позже.
Это не имеет смысла. Ну пусть я введу ветвление, обнаружу что malloc() == NULL, и что дальше? Возвращая -1 я делаю тоже что и возвратить NULL. В любом случае при вызове функции нужна проверка, а на что она будет направлена, на -1 или NULL безразлично.
Я хотел сделать всё на указателях (не на их арифметике), но подумал, что использовать сдвиг немного логичнее.
fougasse
13.01.2020 08:34Надо вызывать exit и всё, если malloc не нашел память — в рамках туториала дёргаться уже поздно.
selrorener
14.01.2020 01:11Это не имеет смысла. Ну пусть я введу ветвление, обнаружу что malloc() == NULL, и что дальше?
А дальше падать. Тут дело в том, что нормальной конфигурации и на нормальной ОС — маллок в принципе не может вернуть null, но во могу набежать адепты святой проверки маллока.
Поэтому для решения этой проблемы — можно просто поставить assert/упасть. Сразу в маллоке. Это не работало для адептов, да и не работает сейчас. Они будут кричать "всё неправильно".
Но это решается очень просто. Растом. Раст падает, поэтому если адепты святой проверки не согласны с падением — они пойдут войной на раст. А они не пойдут. Причин много — как минимум половина из них, если не более — адепты и того и другого. Правда непонятно как это у них в одном сознание уживается, но пропаганда имеет непостижимую силу.
Я хотел сделать всё на указателях (не на их арифметике), но подумал, что использовать сдвиг немного логичнее.
Какой сдвиг? На указателях — это просто — (++ptr) и ptr--. Но это не точно — точно там в зависимости от того, что у вас и в какую сторону растёт.
ncr
14.01.2020 01:50Тут дело в том, что нормальной конфигурации и на нормальной ОС — маллок в принципе не может вернуть null, но во могу набежать адепты святой проверки маллока.
О, адепт оверкоммита уже здесь.
Не может, ага. До первой фрагментации.
selrorener
14.01.2020 01:58О, адепт оверкоммита уже здесь.
О, адепт "я ничего не знаю и повторяю услышанные где-то базворды" уже здесь.
Ошибка номер номер раз — никакого оверкоммита нет. Адепта обманули. Пусть он больше читает кода, а меньше желтушной чуши.
Не может, ага. До первой фрагментации.
Так же и здесь. Адепт где-то слышал про какую-то фрагментацию, но опять же — всё те же проблемы. Это полная чушь.
На уровне vm фрагментации не существует. Опять же, больше нужно читать кода и матчасти, а не повторять чушь из интернета.
ncr
14.01.2020 02:44никакого оверкоммита нет
А что же есть?
Слово «чушь» встречается в вашем комментарии как минимум трижды — похоже, вы глубоко в теме. Не томите же, поведайте, как работают волшебные конфигурации и ОС с бесконечным маллоком (а заодно, видимо, и бесконечным адресным пространством)?
selrorener
14.01.2020 03:44А что же есть?
Ничего нет. Нету той глупости, что адепты вычитывают в желтушных методичках. Меня до сих пор не перестаёт удивлять то, сколько же невежество породила попытка адаптировать информацию в мане под слабое понимание обывателя.
Я уже устал открывать эту тайну, но открою её ещё раз. На самом деле оверкоммит не позволяет выделять "памяти больше", как это написано в мусорной методички. Оверкоммист это костыль, который как раз таки и подавляет базовую семантику.
В рамках базовой семантики адресспейс никакого отношения к памяти не имеет и не может закончиться. Конечно, в реальности существуют ограничения, но об этом ниже.
Слово «чушь» встречается в вашем комментарии как минимум трижды — похоже, вы глубоко в теме.
Слово "чушь" встречается в моём комментарии ровно столько раз, сколько чушь появлялась в комментарии того, кому я отвечаю.
Не томите же, поведайте, как работают волшебные конфигурации и ОС с бесконечным маллоком (а заодно, видимо, и бесконечным адресным пространством)?
Во-первых я рад, что адепт погуглил. Только я не понял, почему адепт съехал с темы и забыл все свои предыдущие тезисы. Куда же делся оверкоммит и фрагментация?
Во-вторых, заход так же не работает. Этому есть несколько причин.
Даже если аллокатор никак не будет трогать адресспейс — он имеет оверхед на каждую аллокацию. Нужно где-то и как-то сохранить факт наличия аллокации и её конфигурацию.
Если мы говорим о дефолтном маллоке, то оверхед в данном случае будет минимум 4к на аллокацию, таким образом ни о какой бесконечности речи идти не может. Это не учитывая оверхеда на pte и обеспечение иерархии.
Так же, базовая семантика всех языков не предполагает наличия vm, таким образом никаких "бесконечных" аллокаций не предполагает. Таким образом аллокации большей чем 2-3 объёма памяти в принципе быть не может. Это не имеет смысла. А 2-3 — это семантика всяких векторов.
Поэтому в конфигурации фейкового овереркоммита по умолчанию и существует данный костыль. Который обеспечивает данную данную семантику — т.е. отвал mmap по аллокации большей относительно объёма памяти.
Без этого костыля получить null в рамках базовой семантики языков от маллока в принципе нельзя. Именно поэтому на это можно забить, а для успокоения можно добавить assert.
Но формально получить null можно, аллоцируя сотни терабайт "памяти". Но даже это уже не особо актуально, потому как дефолтный 48 битный адресспейс — мусор. Поэтому там, где аллокаций и памяти много, где 48 бит действительно может теоретически кончится — уже не 48бит.
Получить можно null только одним способом — создавая множество огромных аллокаций. Очевидно, что этого в реальности не бывает. Программа с базовой семантикой не может в принципе выделить сотню терабайт памяти, что-бы исчерпать адресспейс.
А там, где памяти терабайты — там совершенно другие правила и другой адресспейс.
Ах да, прокомментирую ещё несколько очевидных заходов. Заход типа "у меня заммапировано 100 терабайт файлов — мне не хватит". Заход крайне наивный. Во-первых это крайне сомнительно, а во-вторых — этого мало. Повторюсь, что базовая семантика не предполагает аллокаций в несколько раз больших, нежели объём памяти. К тому же там, где будут обрабатывать десятки/сотни терабайт данных — маллок явно использовать не будут, а даже если будут — как минимум будут знать что и когда произойдёт. Это явно не обычный обывательский случай.
А вообще адепты любят ссылаться на ситуации за рамками контекста. "а вот там, а вот адрессанитайзер". Базовые ситуации рассматривают только те случаи, где возникает вопрос "проверять или нет". Там, где находятся все эти граничные случаи — таких вопросов попросту не бывает. Там люди знают что нужно, а что ненужно проверять и так. И подобные вопросы не задаются.
Ещё один из популярных заходов — это всякие "а как же надругих платформах". Там, где есть нормальная ОС с нормальной конфигурацией — там нету проблемы вида "может не хватить адресспейса".
Поэтому я как минимум не рассматриваю всякие мобилки/ембедед формально на линуксе. Хотя даже там 32битный мусор уже легаси, да и от линукса одно название. Полноценной ОС там нет, как и нормальной конфигурации.
Да и во всех этих мобилках вендоры глушал нативные языки типа С/С++.
qrdl
12.01.2020 20:31+3Результат malloc'а не надо кастить. sizeof(char) тоже не нужен, поскольку он по стандарту языка равен 1. В чем смысл таскать указатель на стэк по всем функциям, если при этом offset и stack_len глобальные (в пределах TU, но все равно)? Тогда уж надо упаковать это все в одну структуру и таскать это все вместе, иначе никакого смысла. Или все далать глобальным и упрощать API.
Не думаю, что такой код может научить чему-то полезному.Centrix2132 Автор
12.01.2020 20:33-2Результат malloc'а не надо кастить.
Почему?
sizeof(char) тоже не нужен, поскольку он по стандарту языка равен 1.
Не на всех машинах.qrdl
12.01.2020 20:36+2Почему?
Ну, например: stackoverflow.com/a/605858/28494
Не на всех машинах
По стандарту языка, везде. Байт не обязательно равен 8 битам, это да, но char это всегда один байт.
myxo
12.01.2020 21:26Кастить или не кастить маллок — вкусовщина. На мой взгляд явное преобразование всегда лучше неявного. А вот sizeof(char) я бы лучше не убирал. Появляется какой-то специальный случай, когда выделяем память под тип размера 1. Читаемость сильно ухудшается.
Но это мелочи. Вот про offset и stack_len все верно, разделять их не нужно. Также непонятно почему вместо привычного синтаксиса обращения к массиву, идет арифметика указателей.
Centrix2132 Автор
12.01.2020 20:49-7У меня даже что бы исправить статью кармы не хватает, ужас.
justhabrauser
13.01.2020 02:21Потому что детский сад и манна каша.
В следующий раз читать вслух туториалы лучше соседней кошке.
Для кармы безопаснее.
oam2oam
12.01.2020 22:23Давно не видел настолько странной и бездарной статьи… Стек, конечно, можно реализовать на базе массива, но что-то так редко получается делать. Да что там говорить, сейчас же все программы многозадачные — что-то тут не видно ни семафоров ни фьютексов. В общем — чрезвычайно низкий уровень статьи.
Centrix2132 Автор
13.01.2020 07:10Семафоров и (*мьютексов?) нет потому, что они реализованы в therads.h
Fregl
12.01.2020 23:36Человек хотел написать статью для самых маленьких. Но увы, не совсем все очевидно. Во первых не написано практического применения стека, а это и стек вызовов, и передача параметров в функцию и возврат результатов, различные алгоритмы сортировок, рекурсии, да много чего. Я бы сначала это написал, а потом уже реализацию…
FDA
13.01.2020 00:08Ну подход к написанию у всех разный может быть. Конечно, почему-то не показан вариант реализации стека без динамического выделения памяти на основе обычного массива. Такой подход часто используется во встраиваемых системах. По идее можно было бы сделать цикл статей, но автору уже зачем-то нагадили в карму, сильно уменьшив желание писать тут дальше.
Fregl
13.01.2020 11:26Ну зря вы автору накидали минусов, указали бы просто на ошибки и дали бы время на исправление. А то видать у многих корону задело, сразу в минуса запихивать… Да, статья ни о чем, но это же проба пера, дайте автору шанс.
GCU
13.01.2020 13:13Поскольку char знаковый, как после pop отличить настоящее значение -1 от ошибки?
COKPOWEHEU
13.01.2020 14:03-1Обычно-то char беззнаковый (это же символ, а не целочисленная переменная). Стандартом оговорено, что в принципе он может быть даже знаковым, и в компиляторах есть соответствующий флажок.
Но вот значение 255 ничуть не хуже любого другого, так что несмотря на ошибочность формулировки, с сутью вопроса (как отличить корректное значение от ошибки) согласен.
Известные решения:
getchar() возвращает int, то есть корректные символы как обычно кодируются диапазоном char (0 — 255), а ошибки — отрицательными числами (обычно -1)
errno и т.п. — глобальная переменная кода ошибки
В С++ можно еще генерировать исключение.GCU
13.01.2020 19:06Я подумал что char знаковый, поскольку в приведённом в статье коде функция объявлена как возвращающая char, и при этом явно возвращает -1.
Еще непонятно как это работает:
*stack+(--offset);
По логике уменьшается offset и прибавляется к самому первому значению в «стеке»!?
Это открывает мощнейшие возможности для оптимизации и рефакторинга, так как все элементы после 1го можно не хранить, они всё равно не используются :)
Вызовы malloc и free тоже можно выкинуть, причём вместе с инклюдом, и функциями, и… с аргументом stack, вот.
static int offset = 0; static char stack = 0; int push(char val) {return offset++ ? 1 : (stack=val,1);} char pop() {return offset ? stack+(--offset) : -1;}
В результате:
— упростился API;
— меньше зависимостей;
— меньше требования к памяти для работы;
P.S. И тут Остапа понесло
Wesha
У, а я надеялся, что тут будет обсуждаться системный стек и анальные кары для того, кто придумал пихать в него и адреса возврата, и данные, что открыло безграничные возможности для атак через переполнение стека.
picul
Wesha
Конечно, есть.
Давайте внимательно подумаем: а в чём проблема? В том, что при доступе за пределы выделенной на стеке временной области для даннных затираются адреса возврата. Следовательно — что? Правильно, пусть будут
мухи отдельно, котлеты — отдельнодва совершенно независимых стека: один для адресов, другой для данных.Взбалтывать, но не смешивать.Тогда можно выходить за пределы выделенной области данных хоть до посинения — будут испорчены только другие данные.(Конечно, это не панацея — в таком случае хакеру надо уже придумывать способ "испортить другие данные" так, чтобы выполнение программы пошло в нужном ему направлении, а это задача гораздо менее тривиальная).
Kudesnick33
Си — язык довольно примитивный, ближе к макроассемблеру. Часто применяется вообще на голом железе. А далеко не все процы имеют два раздельный аппаратных стека — для данных и адресов возврата. Когда язык создавался, не уверен, что процы с несколькими аппаратными стеками вообще существовали. Си — это не про безопасность, а про близость к железу.
COKPOWEHEU
Некоторые компиляторы так и делают. IAR вроде, но не уверен.
Вот только с системным стеком положено работать только компилятору, а его пишут умные люди, не допускающие переполнений. Если же разработчик влез в него грязными руками или допустил бесконечную рекурсию, то падение программы (быстрая и явная ошибка) куда лучше незаметной порчи данных.
Кроме того, два раздельных стека хуже расходуют память: между ними остается область, недоступная для использования, причем неизвестного размера.
Wesha
Kudesnick33: > Когда язык создавался, не уверен, что процы с несколькими аппаратными стеками вообще существовали.
Я и не говорю про время, когда язык создавался — тогда компы выполняли тысячи операций в секунду, а не сотни миллионов, и не были объединены в планетарную сеть. С той поры много нулей утекло, пора бы уже и безопасность начать приотизировать.
COKPOWEHEU: > Кроме того, два раздельных стека хуже расходуют память: между ними остается область, недоступная для использования, причем неизвестного размера.
Во-первых, сейчас, когда всё виртулизовано по самое не балуй, это не принципиально; а во-вторых — хорошо, пусть один растёт вниз от конца той самой виртуализованной памяти, а второй — вверх от начала. Если они внезапно пересекаются — процессор вполне может это осознать и упасть.
Kudesnick33
Ну так для современных задач, требующих виртуализации, защиты областей памяти и пр. существуют современные языки. Всякие джавы, шарпы и пр. А си остался в своей нише: ядра, загрузчики, низкоуровневые драйвера, микроконтроллеры. И там ему нет равных именно из за простоты и предсказуемости кодогенерации. Там где важна не суперзащищенность, а нужно быть уверенным в том, что ячейка памяти будет прочитана/записана именно столько раз, сколько хочет программист и за определённое количество тактов, ибо это может оказаться вовсе не ячейка памяти, а что угодно другое. Например, тот же указатель стека (аппаратный). Усовершенствование си — это как Усовершенствование лопаты: можно, но это будет уже не лопата.
Wesha
После появления оптимизирующих компиляторов — четыре раза ха-ха. Вы вставляете пустой цикл для создания задержки — а "умный" компилятор его — того...
Kudesnick33
Потому что "глупый" программист не знает про volatile.
Wesha
Вспомнился анекдот.
bentall
Самое простое — в языке Forth (за малым — не ровесник C) есть отдельный стек данных, а на стеке возвратов лежат только адреса возврата.
pvl_1
ЕМНИП в стандарте C смешивание в одном стеке адресов возврата и данных не оговорено, так что это остаётся на совести разработчиков процессоров, ОС и компиляторов под них. То есть данная проблема больше зависит не от языка, а от машины, на которой исполняется код. И если на x86 именно так, как Вы указали, то на некоторых более поздних архитектурах под адреса возврата выделено место не в стеке данных, а где-то ещё. Я, например, могу вспомнить вариант (правда, на какой именно архитектуре, не помню), где под адреса возврата выделен отдельный стек.