Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Прочее

Размещение объектов переменной длины с использованием двух стеков

Работу с двумя стеками можно организовать так: функции первого, третьего, пятого и т.д. уровня вложенности пользуются первым стеком, а второго, четвёртого и т.д. уровня – вторым стеком. Результат свой работы функции нечётного уровня вложенности пишут во второй стек, чётного уровня – в первый. Схематически это будет так:
Размещение объектов переменной длины с использованием двух стеков
            Функции f1 и f3 записывают параметры для вызова f2 и f4 не в свой стек, а во второй стек. Функции f2 и f4 сохраняет результат не в свой стек, а первый и т.д. В свою очередь f2 и f4 записывают параметры для вызова f3 и f5 в первый стек, возвращаемый результат сохраняют во второй стек.

            Позволяет ли такая схема возвращать из функции результат переменной длины? Несомненно. Возьмём функцию f2 из приведённого примера. Она может запросто, безо всяких последствий сдвигать указатель первого стека в сторону незанятой памяти (в архитектуре Intel x86 – это вниз, в сторону уменьшения адресов). В первом стеке, если вызывались функции f3, f5 и т.д., остались следы их локальных данных. Но они уже не нужны, ибо владельцы этих данных (функции f3, f5 и т.д.) уже отработали, ведь сейчас выполняется функция f2. Всё то же можно сказать о функции f3: она тоже может возвратить значение в стек функции f2. Меняются лишь стеки: они используются по очереди.

            Следующий вопрос – как пользоваться памятью, которая зарезервирована в стеке подобным образом. Область стека, которая отведена под локальные объекты, имеет размеры, известные компилятору. Поэтому компилятору известно смещение, необходимое для обращения к объекту переменной длины: адресом этого объекта будет содержимое базового регистра за вычетом смещения:

[EBP - <смещение>]
            Таким образом, можно обратиться к объекту переменной длины, который был помещён в стек первым. А если в каком-либо фрагменте стека выделяется не единожды, то каким образом узнать адрес второго и далее объекта? Ведь размер первого объекта не известен во время компиляции, значит смещение второго объекта тоже неизвестно. Выход таков: в стеке должны быть указатели, в которые записывается адрес выделенного участка памяти. Например:
Объект* функция (<список параметров>) {
   Объект* указатель= Выделить память в другом стеке (требуемый размер);
   return  указатель;
}
            Внешне это выглядит так же, как выделение памяти в «куче»:
указатель = Выделить память в куче (требуемый размер);
ptr = malloc (size_of_object);
Размещение объектов переменной длины с использованием двух стеков
            Само по себе выделение памяти под объект переменной длины – это ещё не возвращение из функции собственно объекта. Эта память после выделения должна обрести содержимое, в неё должно быть что-то записано. В терминологии C++ функции, возвращающие объект (в нашем случае – переменной длины), можно назвать конструкторами объектов. Размер памяти, необходимый под объект, может вычисляться конструктором на основании переданных ему параметров:
Объект* Конструктор (<список параметров>) {
   требуемый размер = Вычислить размер (<параметры>);
   Объект* указатель = Выделить память в другом стеке (требуемый размер);
   указатель -> Заполнить объект содержимым (<список параметров>);
   return  указатель;
}
            Эти конструкторы можно использовать примерно так:
Таблица БД* поставщики = Конструктор таблицы БД (список поставщиков);
Таблица БД* покупатели = Конструктор таблицы БД (список покупателей);
Таблица БД* контрагенты = Объединить (поставщики, покупатели);
Заметьте, что всё это делается в стеке.

            Читаем далее следующую статью: Реализация двухстековой модели размещения данных.

Почитайте ещё:

Последняя правка: 2016-03-18    09:44

ОценитеОценки посетителей
   ██████████████████████████████████████████ 4 (100%)
   ▌ 0
   ▌ 0
   ▌ 0

Отзывы

     2016/06/03 15:09, Андрей

А как быть если нужно вернуть объект переменной длины через одну ф-ю. Пример:
char* f() { return str; }
char* g() { return f(); }
void main() {
char* str = g();
}
Результат возвращаемый f непосредственно в ф-ии g не используется, а тут же возвращается. Т.е., f использует 1-й стек, а ее результат используется в main, которая также использует первый стэк. В этом случае не получится сохранить результат в 1-м стеке. Если сохранять во 2-м стеке, то потом его придется копировать в 1-й, чего мы хотели избежать.

Описываемая ситуация встречается довольно часто - это всякие декораторы и рекурсивные ф-ии (особенно если рекурсия косвенная). Например, построение дерева.

     2016/06/03 17:44, Автор сайта

Подобный вопрос возникал и я на него отвечал:

Задают вопрос: А что если есть цепочка вызовов foo(bar(file2str()))?

Отвечаю: Тоже об этом думал – достаточно ли двух стеков или же надо иметь множество стеков. И пришёл к такому выводу. Зачем file2str() вызывается из bar(), а не из foo()?

1) Если результат, возвращаемый file2str(), требуется функции foo() в неизменном виде, то его надо вызывать из foo():

foo () {
x = file2str();
bar (x);}

В этом случае двух стеков достаточно.

2) Если функции foo () требуется не результат file2str() в чистом виде, а нужен результат, преобразованный функцией bar(file2str()), то двух стеков тоже достаточно. Ибо в foo () результат file2str() помещён не будет. Там будет что-то другое.

Здесь примерно так же. Функцию main можно переписать так:
 char* str = f();
g(str);
Подобные вопросы закономерны, поэтому хочется проверять теорию жизнью и практикой. Когда появится более-менее наработанная практика, то обязательно поделюсь опытом использования.

     2016/08/09 06:31, rst256

Зачем file2str() вызывается из bar(), а не из foo()?
1) Если результат, возвращаемый file2str(), требуется функции foo() в неизменном виде, то его надо вызывать из foo():
foo () { x = file2str(); bar (x);}

Затем, что бы было. Уж извините, какой вопрос – такой и ответ. А теперь вопрос. Eсли:
foo () { x = file2str(); bar (x);} // для foo(bar(file2str()))
foo () { x = file3str(); bar (x);} // для foo(bar(file3str()))
foo () { x = file4str(); bar (x);} // для foo(bar(file4str()))
То зачем вообще делать функцию, если она не будет работать как функция?

2) Если функции foo () требуется не результат file2str() в чистом виде, а нужен результат, преобразованный функцией bar(file2str()), то двух стеков тоже достаточно. Ибо в foo () результат file2str() помещён не будет. Там будет что-то другое.

Как же так, а если надо что бы было вот так?
bar(a) { if(... a ...) return a; else return some; }

Здесь примерно так же. Функцию main можно переписать так:
char* str = f();
g(str);

А заодно переписать и функцию g? Ведь она работала так:
char* g() { return f(); }
И все остальные вызовы для функции g, разумеется, тоже переписать надо.

Может привести примеры функций посложнее, дабы абсурдность ответа: "Вставляйте код функции напрямую вместо ее вызова", стала более очевидной? И ведь это еще из той серии примеров, которые можно решить при помощи немного иной 2-х стековой модели (точнее 3-х стековой: аппаратный стек, стек приема и стек передачи).

     2016/08/09 07:23, rst256

Может быть, всё же именно вам переписать код ВАШЕЙ ф-и:
Объект* Конструктор (функция аллокатор, <список параметров>) {
требуемый размер = Вычислить размер (<параметры>);
Объект* указатель = аллокатор (требуемый размер);
указатель -> Заполнить объект содержимым (<список параметров>);
return указатель;
}
И перегрузочку полезную:
размер Конструктор (Объект* указатель, Объект* указатель_макс,<список параметров>);
Именно тот случай, когда в стек надо положить, ибо, как известно в стеке предварительно выделять не надо, в стек можно сразу класть и уже по итогу "выделять". Что, согласитесь, иногда выходит быстрее. Например конкатенация сишных строк не потребует предварительного получения их длины.

Вот тут да, тут двухстековая модель уже смахивает на полезную штуку, тем более что теперь уже НАМ не надо ничего переписывать. Вместо этого компилятор просто должен правильно выбрать одну из двух перегрузок, либо передать указатель на стек и потом увеличить указатель стека на возвращаемое конструктором значение, либо передать malloc (или иной alloc) и получить указатель на объект.

Написать отзыв

Написать автору можно на электронную почту mail(аt)compiler.su

Авторизация

Регистрация

Выслать пароль

Карта сайта


Каким должен быть язык программирования?

Анализ и критика

Устарел ли текст как форма представления программы

Русский язык и программирование

Многоязыковое программирование

Синтаксис языков программирования

Синтаксический сахар

Некоторые «вкусности» Алгол-68

«Двухмерный» синтаксис Python

Почему языки с синтаксисом Си популярнее языков с синтаксисом Паскаля?

Должна ли программа быть удобочитаемой?

Стиль языка программирования

Тексто-графическое представление программы

●  Разделители

●  Строки программы

●  Слева направо или справа налево?

Комментарии

●  Длинные комментарии

●  Короткие комментарии

●  Комментарии автоматической генерации документации

●  Нерабочий код

Нужны ли беззнаковые целые?

Шестнадцатиричные и двоичные константы

Условные операторы

Переключатель

Циклы

●  Продолжение цикла и выход из него

Некошерный «goto»

Операции присвоения и проверки на равенство. Возможно ли однаковое обозначение?

Так ли нужны операции «&&», «||» и «^^»?

Постфиксные инкремент и декремент

Почему в PHP для конкатенации строк используется «.»?

Указатели и ссылки в C++

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

Почему динамическое распределение памяти – это плохо

Как обеспечить возврат функциями объектов переменной длины?

●  Типы переменного размера (dynamically sized types, DST) в языке Rust

●  Массивы переменной длины в C/C++

●  Размещение объектов в стеке, традиционный подход

●  Размещение объектов переменной длины с использованием множества стеков

●  Размещение объектов переменной длины с использованием двух стеков

●  Реализация двухстековой модели размещения данных

●  Двухстековая модель: тесты на скорость

●  Размещение объектов переменной длины с использованием одного стека

Можно ли забыть о «куче», если объекты переменной длины хранить в стеке

Безопасность и размещение объектов переменной длины в стеке

Массивы, структуры, типы, классы переменной длины

О хранении данных в стеке, вместо заключения

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

Компьютерный юмор

Прочее

Последние комментарии

2018/04/16 15:09, Олег
Русский язык и программирование

2018/04/02 22:42, rst256
Программирование без программистов — это медицина без врачей

2018/03/25 21:14, Денис Будяк
Энтузиасты-разработчики компиляторов и их проекты

2018/03/21 23:37, Marat
Почему обречён язык Форт

2018/03/10 20:05, Comdiv
«Двухмерный» синтаксис Python

2018/02/24 14:51, Эникейщик
Русской операционной системой должна стать ReactOS

2017/12/12 13:32, Comdiv
Отечественные разработки

2017/11/05 17:26, rst256
Электроника без электронщиков