Стек на C99. 1-я часть. Основные функции
Настоящая статья — первая из цикла, состоящего из четырёх статей, посвящённых разработке стека — достаточно известной и простой структуры данных. Несмотря на её простоту, можно придумать немалое количество разнообразных функций, предназначенных для обработки стека, а некоторые из них могут быть реализованы различными способами. Разработка этих функций — отличный способ попрактиковаться в программировании.
Цикл статей может оказаться полезным тем, кто уже достаточно неплохо разбирается в языке C99 и кого не пугают такие понятия, как указатель, адрес переменной и динамическое распределение памяти. К слову сказать, указателей в нашем коде будет предостаточно, так что возможность поупражняться в построении не самых простых программных конструкций у нас будет.
Стеком называется контейнер, предназначенный для хранения элементов произвольного типа. Особенностью стека является то, что элементы добавляются в него последовательно, а извлекаются в порядке, обратном тому, в котором были добавлены.
Отличной иллюстрацией стека является стопка тарелок, символизирующих элементы стека. В любой момент времени нам доступна только одна тарелка — та, которая поставлена на стопку последней, т. е. верхняя. Для того, чтобы получить доступ к произвольной тарелке внутри стопки, необходимо сначала последовательно снять все тарелки, находящиеся над ней.
По аналогии со стопкой тарелок применительно к стеку говорят о верхнем элементе (том, который добавлен последним) и нижнем элементе (добавленном первым). Отметим ещё, что принцип работы стека кратко описывается аббревиатурой LIFO — last in — first out (первым вошёл — последним вышел, англ.).
Для хранения стеков в памяти компьютера наиболее часто используются массивы и односвязные списки. Преимущество первых перед последними заключается в том, что операции помещения элемента на вершину стека (т. н. проталкивание) и получения верхнего элемента одновременно с его удалением (выталкивание) в случае массивов выполняются быстрее, чем в случае с односвязными списками, т. к. не требуют динамического выделения и освобождения памяти. Эти же операции, реализованные для односвязных списков, как правило, основаны на динамическом распределении памяти.
С другой стороны, при использовании массивов необходимо знать заранее, хотя бы приблизительно, количество элементов, которые будут храниться в стеке, поскольку размер массива всегда фиксирован. В отсутствии такой информации, размер массива приходится выбирать «с запасом», что может привести к неиспользованию существенного объёма зарезервированной памяти. Односвязные списки в этом отношении являются более гибкими: в ходе операций проталкивания и выталкивания они динамически меняют свой размер. Наш стек будет построен на основе односвязного списка.
Непустой односвязный список представляет собой упорядоченный набор узлов — переменных определённого типа, хранящихся в памяти компьютера. Каждый узел, кроме последнего, содержит указатель на следующий за ним узел. Последний же узел в качестве указателя на последующий содержит ноль. Помимо этого, каждый из узлов является контейнером для хранения некоторой информации. Заметим, что односвязный список может быть пустым, т. е. может не содержать ни одного узла.
Наш стек будет универсальным, т. е. он будет поддерживать данные любых типов. Поэтому его элементами будут являться адреса переменных произвольного типа, для хранения которых будут использованы нетипизированные указатели (т. е. указатели типа void * ).
Каждый узел списка будет являться контейнером для указателя, содержащего элемент стека, а также для указателя на следующий узел. В первом узле списка будет храниться верхний элемент стека, во втором — второй сверху и т. д. Наконец, в последнем узле будет содержаться нижний элемент стека. Для представления узлов создадим следующую структуру:
Таким образом, каждый узел списка будет являться переменной типа node .
Что касается самого стека, то отдельный тип данных для его представления мы создавать не будем. Для того, чтобы получить доступ к стеку, достаточно иметь указатель на первый узел списка, т. е. тот, в котором содержится верхний элемент стека. Такой указатель будем в дальнейшем называть, для определённости, стековой переменной. Для создания пустого стека достаточно объявить стековую переменную, например, под именем stack , и присвоить ей нулевое значение:
Теперь мы можем наполнять созданный стек элементами с помощью функции push() . Стоп! Но ведь эту функцию мы ещё не создали! Ну так давайте создадим!
Функция push()
Но перед созданием функции push() напишем вспомогательную функцию pmalloc() , которая будет вызываться из push() .
Проталкивание элемента в стек влечёт за собой необходимость создания нового узла списка, в котором будет храниться этот элемент. Память для данного узла будет выделяться динамически с помощью функции malloc() из стандартной библиотеки <stdlib.h>. Эта функция возвращает адрес выделенного участка памяти, если выделение прошло удачно или нулевой адрес в противном случае. Таким образом, перед использованием этого адреса необходимо убедиться в том, что он отличен от нуля.
Именно такую проверку на равенство нулю полученного адреса и будет производить функция pmalloc() . По сути, она будет являться «посредником» между вызывающей её функцией и функцией malloc() . Функция pmalloc() примет размер памяти, которую нужно выделить, и «передаст» его функции malloc() . В случае успеха pmalloc() возвратит адрес выделенного участка, а в случае неудачи выведет соответствующее сообщение и завершит работу программы с помощью функции exit() (из той же стандартной библиотеки <stdlib.h> ).
Ниже размещён код функции pmalloc() (префикс p в названии функции происходит от слова «protected»):
Ну а теперь можно перейти к созданию функции p u s h ( ) .
Функция push() будет принимать в качестве аргументов значение стековой переменной ( stack ) и элемент, который требуется протолкнуть в стек ( element ). В результате выполнения функции будет динамически выделяться память для нового узла списка, в него будут помещаться новый элемент стека и адрес следующего узла. Последний будет браться из формального параметра stack , который теперь уже будет указывать не на первый узел списка, а на второй. Функция возвращает новое значение стековой переменной, которым теперь будет являться адрес только что созданного узла. Вот код функции:
Поместить новый элемент в стек можно, например, следующим образом:
Следующая функция будет выталкивать из стека верхний элемент.
Функция pop()
Функция pop() возвращает верхний элемент стека и удаляет узел списка, содержащий этот элемент. Разумеется, стековая переменная, связанная с обрабатываемым стеком, должна после выполнения функции указывать на узел, следующий за удалённым. Однако функция возвратить новое значение стековой переменной уже не может. Поэтому мы предоставим функции возможность самой изменить значение стековой переменной, передав в функцию её адрес. Если к моменту вызова стек уже пустой, то функция возвращает ноль. Ниже приведён код функции pop() .
Получить вытолкнутый элемент стека можно, например, так:
Заметим, что функции push() и pop() «берут на себя» динамическое выделение памяти для узлов списка и её освобождение. Что касается переменных, адреса которых содержатся в стеке, то «забота» о памяти, в которой хранятся эти переменные, полностью ложится на плечи пользователя стека. Впрочем, заботиться о своевременной очистке памяти нужно лишь в случае её динамического распределения. Если же память выделяется автоматически, то, разумеется, думать о её «ручном» освобождении не приходится.
Мы реализовали функции, осуществляющие основные операции со стеком: проталкивание и выталкивание элементов. Однако, к основным операциям часто относят также просмотр верхнего элемента без его удаления из стека. Давайте реализуем соответствующую функцию.
Функция peek()
Функция peek() принимает в качестве аргумента значение стековой переменной и возвращает верхний элемент стека, не удаляя его. Если стек пуст, то возвращается ноль. Реализация весьма проста:
Не менее прост и пример использования функции:
На этом с основными функциями мы закончили. Во второй части будут реализованы некоторые дополнительные функции для работы со стеком. Там же будет размещена ссылка на скачивание исходного кода, опубликованного в обеих статьях.
Что такое push в языке С: правила использования и примеры
Стек является структурой данных, которая задействована во многих алгоритмах, не всегда связанных с программированием. А в программировании стек вообще очень распространен. Поэтому понимание работы функций push(), pop() и peek() в стеке С — это базовая вещь , без которой в программировании будет трудно .
Функция push() в С
Пример реализации функции push() в С:
node *push( node *stack, void *pushElement )
<
node *new_node = pmalloc(sizeof(node)); //выделяется память для нового узла
new_node — > pushElement = pushElement; //присваивается значение полям узла
new_node — > next = stack;
return new_node; //возвращается адрес узла, который мы создали
Чтобы поместит ь с озданный элемент в stack, можно воспользоваться следующим способом:
stack = push(stack, new_pushElement)
Коротко объясним, что мы сделали. Мы использовали вспомогательную функцию «pmalloc()» из стандартной библиотеки «<stdlib.h>». Эта функция помогает создавать новый узел в стеке, где будет хранится новый элемент. Функция «push()» принимает в качестве аргумента «pushElement», который нужно протолкнуть в стек, и значение узла из «stack». Когда функция будет исполняться, тогда в динамическом режиме будет выделятся память для нового узла, куда поместится значение нового элемента «pushElement».
Функция pop()
Как мы уже писали, данная функция необходима, чтобы «вытолкнуть» верхний элемент из стека. При выталкивании элемента она полностью удаляет узел из списка стека. Стековая переменна я п осле работы этой функции принимает значение следующего элемента после удаленного.
Пример реализации функции pop() в С:
void *pop(node *mystack) // «mystack» является формальным параметром,
< //указывающим на адрес стековой переменной
if (*mystack)
<
node *first_node = mystack; //происходит извлечение первого узла из списка
*mystack = first_node — > next; // переменной присваивается адрес 2-го узла
void *element = first_node — > element; //извлекается верхний элемент
free(first_node); //удаляется узел
return element; //возвращается верхний элемент
>
return 0; // когда стек будет пустым, тогда вернется 0
>
Функция peek()
Когда нужно просто просмотреть верхний элемент стека без его удаления, тогда в С применяется функция peek(). Она достаточно просто реализуется:
void *peek(node *stack)
<
return sta ck ? Stack — > myElement : 0;
>
Заключение
-
push() отвечает за добавление элемента в стек;
-
pop() отвечает за удаление элемента из стека;
-
peek() отвечает за просмотр элемента без его удаления.
Мы будем очень благодарны
если под понравившемся материалом Вы нажмёте одну из кнопок социальных сетей и поделитесь с друзьями.
Push c что это
Stacks are a type of container adaptors that follow LIFO(Last In First Out) property, where a new element is added at one end and an element(at the top) is removed from that end only. Basically, the insertion and deletion happen on the top of the stack itself.
stack::push()
push() function is used to insert or ‘push’ an element at the top of the stack. This is an inbuilt function from C++ Standard Template Library(STL). This function belongs to the <stack> header file. The element is added to the stack container and the size of the stack is increased by 1.
Syntax:
Parameters: The value of the element to be inserted is passed as the parameter.
Result: Adds an element of value the same as that of the parameter passed at the top of the stack.
Устройство Стека для Intel386
Стек (от англ. Stack) — специально отведённое место в памяти для хранения временных данных. Он подчиняется следующим правилам:
LIFO (Last In First Out), который подразумевает, что элемент, который был помещён на стек последним, будет первым оттуда удалён.
Стек растёт в сторону начала адресного пространства (ещё говорят, что стек растёт вниз).
Минимальная единица, которая может быть удалена\помещена со\на стек(а) — 16 бит (2 байта).
Максимальная единица, которая может быть удалена\помещена со\на стек(а) — 32 бита (4 байта).
Устройство Стека
Рисунок 1. Устройство стека на Intel386
Как видно из Рисунка 1, при помещении чего-либо на стек он увеличивается вниз. Указатель стека (ESP — Stack Pointer) содержит адрес последнего элемента стека, следующий за последним элементом. Эту часть стека также называют вершиной стека (от англ. TOS — Top Of Stack).
Когда что-то помещается на стеке, процессор декрементирует значение в регистре ESP и записывает помещаемое значение на вершину стека. В случае, когда необходимо что-то удалить со стека, процессор сначала копирует удаляемое значение с вершины стека, а затем уже инкрементирует значение в регистре ESP.
Чтобы процессор смог понять, что ему нужно сохранить на стек, используется инструкция push в ассемблерном коде, в случае удаления «вытаскивания» значения со стека — pop.
Инструкция push
Её синтаксис может разниться от одного языка ассемблера к другому, однако суть её остаётся неизменной — помещение какого-либо значения на стек.
Префикс r/m (от англ. register/memory) означает, что значение, которое необходимо поместить на стек находится в памяти, которая в свою очередь находится в регистре, например, в регистре лежит значение 0x87654321 — адрес памяти, по которому хранится значение 0x11223344 , соответственно на стек будет помещено значение 0x11223344.
Префикс r (от англ. register) означает, что значение, которое необходимо поместить на стек, находится в регистре.
Префикс imm (от англ. immediate), т.е. значение, которое непосредственно передаётся инструкции в качестве параметра.
Постфиксы 8, 16, 32 означают сколько бит содержит, передаваемое инструкции, значение, которое в свою очередь, обычно называют операндом.
На данный момент может возникнуть вопрос от том, что, как писалось выше, минимальная единица, которая может быть помещена на стек — 16 бит, но в синтаксисе инструкции push есть imm8 , говорящее о том, что операндом инструкции может быть 8-битное значение. На самом деле, 8-битные значения дополняются до 16-битных, т.к. стек выровнен по 16 бит, однако это имеет значение и для знаковых типов, которые используют 2-ое дополнение дополнение до двух.
Инструкция pop
Синтаксис инструкции pop аналогичен тому, который используется в инструкции push , за исключением того, что значение удаляется со стека и помещается в операнд инструкции.
А также, по очевидным причинам, операндом инструкции pop не может быть immediate value, т.к. мы не можем сохранить что-либо туда.
Регистры для управления стеком
Уже был упомянут один из регистров, который позволяет управлять стеком — ESP (Stack Pointer), пожалуй, это самый важный регистр, который хранит указатель на вершину стека, однако есть ещё несколько регистров, связанных со стеком:
SS (Stack Segment) — регистр, указывающий на определённый сегмент памяти, в котором и находится сам стек, только одним сегментом стека можно манипулировать в конкретный момент времени, этот регистр задействуется процессором для всех операций, связанных со стеком.
EBP (Base Pointer) — регистр, указывающий на текущий фрейм, т.е. на начало стека для конкретной процедуры\функции, обычно используется для адресации локальных переменных и аргументов процедуры\функции.
Соглашение о вызовах функций в System V Intel386
В System V Intel386 (далее System V) существует несколько правил для вызова функций и соответственно передачи им аргументов, эти правила распространяются исключительно на глобальные функции, локальные функции могут не следовать этим правилам (однако это считается не лучшим выбором):
Аргументы вызываемой функции помещаются на стек в обратном порядке по отношению к вызывающей функции, т.е. вызывающая функция (от англ. caller) сначала должна поместить на стек последний аргумент, затем предпоследний и т.д. до первого, затем вызываемая функция (от англ. callee) может забрать со стека аргументы в привычном для неё порядке.
Регистры EBP, EBX, EDI, ESI и ESP могут изменяться вызываемой функцией, соответственно, если вызывающая функция хранит какое-либо значение в одном из этих регистров — она сначала должна поместить значения этих регистров на стеке, а после восстановить их. Исключение составляет регистр EBP, который не изменяется при вызове функции и продолжает указывать на предыдущий фрейм (на фрейм вызывающей функции), поэтому он помещается на стек вызываемой функцией в начале её выполнения и восстанавливается по завершении, то же касается и регистра ESP.
При осуществлении вызова функции используется инструкция call в ассемблере, которая сохраняет на стеке адрес следующей за ней [call] инструкции, который обычно называют return address.
Если функция возвращает какое-либо значение — она должна поместить его в регистр EAX, в ином случае она не должна ничего сохранять в какой-либо регистр.
Следовательно, после вызова функции (после выполнения инструкции call ), стек будет выглядеть следующим образом:
Рисунок 2. Стек после вызова функции
Как показано на Рисунке 2, первое, что есть на текущем фрейме — адрес следующей после call инструкции, далее идёт сохранённое значение регистра EBP, указывающее на предыдущий фрейм, а затем идут локальные переменные, относящиеся к конкретной функции.
Всё, что выше return address, относится к предыдущему фрейму, включая аргументы, переданные вызываемой функции. Таким образом, первый аргумент будет в EBP + 8, второй в EBP + 12, и т.д., за исключением случаев, когда аргументом является 16-битное значение.
Пример работы со стеком на GNU Assembler x86
В качестве примера работы со стеком будет рассматриваться вывод аргументов командной строки, которые будут индексироваться с помощью локальной переменной, а также вывод переменных окружения.
В примере будет использоваться GNU Assembler (GAS), который использует синтаксис AT&T, для сборки используется GCC.
Начнём с того, как будет выглядеть стек для функции main :
В качестве аргументов были переданы argc, argv и envp и находятся они, соответственно, в EBP + 8, EBP + 12 и EBP + 16, return address — как уже упоминалось — адрес, следующий за инструкцией call , local argv index — локальная переменная для красивого вывода (ну почти) массива argv.
Для начала в секции .rodata (Read-Only Data) создадим 3 переменные, которые будут форматированными строками, для вывода argc, argv и envp:
Затем объявим в секции .text функцию main, где собственно, и будет код программы, и пометим её, как глобальную:
В самом начале функции помещаем регистр EBP на стек и делаем его локальным указателем на текущий фрейм:
Помещаем argc и указатель на массив argv в EDI и ESI соответственно, а также аллоцируем на стеке 4 байта для локальной переменной и инициализируем её значением ноль:
Теперь можно заняться выводом argc, для этого необходимо в обратном порядке поместить все аргументы функции (в данном случае используется printf ), а после вызова очистить стек, т.к. в System V очисткой стека занимается вызывающая сторона.
Аргументами функции будут форматированная строка и значение argc, которое хранится в регистре EDI:
Стоит заметить, что на стек мы помещаем не значение, которое хранится в argc_str , а её адрес, т.к. printf ожидает именно указатель на форматированную строку.
Следующим шагом будет вывод массива argv, который будет осуществляться в цикле, однако перед этим необходимо понимать, что argv содержит адрес памяти, по которому лежит массив символов (необходимая нам строка), поэтому первым аргументом будет адрес, лежащий в argv, вторым аргументом будет адрес, лежащий в argv + 4, и т.д., здесь мы прибавляем по 4 байта, т.к. адрес — это 32-битное (4-байтовое) число:
Первым делом, в цикле проверяется значение индекса и argc, в случае если они равны (напоминаю, что индексация массива в данном случае идёт с нуля, поэтому последний элемент в массиве argv будет argv + (argc — 1) ), то мы просто выходим из цикла, иначе же вызываем функцию printf (регистр ESI содержит адрес argv), чистим стек, увеличиваем индекс на единицу, перемещаем указатель на следующий элемент в массиве argv и возвращаемся в начало цикла.
После чего, чтобы отделить масив argv от массива envp, сделаем перенос строки (символ переноса строки — \n , который в десятичном представлении имеет значение 10, а в шестнадцатеричном, соответственно, 0xA), для этого используем функцию putchar:
Далее мы будем импользовать тот же регистр ESI для хранения указателей на переменные окружения в массиве envp, как и в случае с argv:
Теперь, т.к. у нас нет индекса для массива envp, а также мы не знаем заранее, сколько там будет элементов, необходимо вспомнить, что массив envp — это нуль-терминированный массив, поэтому, чтобы узнать, что больше элементов нет — достаточно проверить равен ли нулю элемент (он будет следовать за последним):
Цикл вывода переменных окружения не сильно отличается от того, что использовался для вывода массива аргументов командной строки, за исключением проверки выхода из цикла и отсутствием индекса.
Ну и в самом конце необходимо установить возвращаемое значение функции в ноль, а также произвести очистку стека:
Очистка стека производится путём восстановления регистра EBP и ESP в их исходные значения, следовательно всё, что было в этой функции может быть перезаписано и использовано другими функциями\процедурами, инструкция ret устанавливает в EIP (Instruction Pointer) значение return address, таким образом управление возрвращается вызывающей стороне.
Важно упомянуть, что существует более удобная инструкция для очистки стека — leave , она выполняет именно эти две вещи — восстановление регистров EBP и ESP, соответственно последняя часть кода может быть переписана следующим образом:
Однако у этой инструкции есть менее привлекательный компаньон — инструкция enter , у неё два операнда, первый отвечает за количество байт, которое необходимо аллоцировать на стеке, а второй за уровень вложенности, из-за чего реализация подобной инструкции достаточно сложна и не ограничивается этими тремя инструкциями:
Поэтому выполняется в разы медленнее, из-за чего большинство компиляторов стараются её избегать, однако, для демонстрации, те три строчки можно заменить одной:
Теперь подошло время проверить работу программы, для этого используем gcc , чтобы скомпилировать и слинковать ассемблерный код:
Или, в случае, если хостом является x64:
И, наконец, можно запустить программу:
Заключение
Работа со стеком — важная часть для любого языка программирования, особенно низкоуровнего, однако полезно знать, как она устроена и для высокоуровневых языков, хотя для них она может значительно отличаться из-за самих концепций языка.