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

Работу с двумя стеками можно организовать так: функции первого, третьего, пятого и т.д. уровня вложенности пользуются первым стеком, а второго, четвёртого и т.д. уровня — вторым стеком. Результат свой работы функции нечётного уровня вложенности пишут во второй стек, чётного уровня — в первый. Схематически это будет так:             Функции 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);

Объект* Конструктор (<список параметров>) {
   требуемый размер = Вычислить размер (<параметры>);
   Объект* указатель = Выделить память в другом стеке (требуемый размер);
   указатель -> Заполнить объект содержимым (<список параметров>);
   return  указатель;
}

Таблица БД* поставщики = Конструктор таблицы БД (список поставщиков);
Таблица БД* покупатели = Конструктор таблицы БД (список покупателей);
Таблица БД* контрагенты = Объединить (поставщики, покупатели);

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

• Почему динамическое распределение памяти — это плохо
• Как обеспечить возврат функциями объектов переменной длины?
• Типы переменного размера (dynamically sized types, DST) в языке Rust
• Массивы переменной длины в C/C++
• Размещение объектов в стеке, традиционный подход
• Размещение объектов переменной длины с использованием множества стеков
• Реализация двухстековой модели размещения данных
• Двухстековая модель: тесты на скорость
• Размещение объектов переменной длины с использованием одного стека
• Можно ли забыть о «куче», если объекты переменной длины хранить в стеке
• Безопасность и размещение объектов переменной длины в стеке
• Массивы, структуры, типы, классы переменной длины
• О хранении данных в стеке — вместо заключения

Опубликовано: 2014.07.27, последняя правка: 2018.10.29    16:02

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

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

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

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

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

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

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

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

 char* str = f();
 g(str);

✅  2016/08/09 06:31, rst256          #2 

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

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);

char* g() { return f(); }

✅  2016/08/09 07:23, rst256          #3 

Объект* Конструктор (функция аллокатор, <список параметров>) {
   требуемый размер = Вычислить размер (<параметры>);
   Объект* указатель = аллокатор (требуемый размер);
   указатель -> Заполнить объект содержимым (<список параметров>);
   return  указатель;
}

размер Конструктор (Объект* указатель, Объект* указатель_макс,<список параметров>);

Добавить свой отзыв

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