我正在我的一台计算机上运行 Arch Linux,64 位最新更新。我目前是一名计算机科学专业的学生,昨天我们进行了一次测试,我们将使用链表实现动态堆栈。我现在有兴趣了解我的计算机中的堆栈是如何构建的,但是我无法在我的 Arch Linux 计算机上找到任何带有注释的“stack.c”。堆栈编程位于哪里?我了解堆栈如何创建内存,但我想实际查看代码,也许自己也可以尝试一下。
答案1
“堆栈”这个词用得太多了。一些可能的解释包括:
- “堆栈”是一个抽象一组数据结构,提供对其包含的元素的后进先出 (LIFO) 访问。
- 有实现“堆栈”抽象。您在课堂上开发的基于链表的堆栈就是这样的实现之一。这并不是唯一的认识。例如,也可以使用数组构建堆栈。
- 运行时激活堆栈——程序中线程执行期间用于管理函数调用和返回的堆栈——是“堆栈”抽象的另一种实现。它的行为类似于基于数组的堆栈。
根据(3),内存“块”被分配给程序中的每个正在运行的线程。当函数在这些线程中被调用并返回时,它们会从与线程关联的堆栈中推送和弹出“堆栈帧”(运行时激活堆栈上的“元素”)。堆栈帧中包含的内容的细节因硬件架构而异。一般来说,堆栈帧包含:
- 调用者的返回地址
- 函数的部分或全部参数(取决于硬件架构、参数数量及其大小)
- 函数内定义的局部变量。
- 函数使用的寄存器的状态,但其值需要在函数返回之前恢复。
由于参数的数量、函数内局部变量的数量和大小以及需要保存的寄存器因函数而异,因此堆栈帧没有恒定的大小。
无需stack.c
检查,因为管理激活记录堆栈的代码是由逐个函数构建程序的编译器生成的。编译器生成触发函数调用的指令。当编译器生成程序指令时,它知道:
- 使用什么硬件指令来触发函数调用,以及该指令对堆栈有何影响(例如,它是否自动存储返回地址,是否调整跟踪堆栈“顶部”的寄存器)。
- 如果调用中的任何参数存储在堆栈中,则这些参数将位于堆栈的“顶部”。
- 函数内局部变量的大小,以及这些变量相对于堆栈“顶部”的位置(编译器使用它来调整跟踪堆栈“顶部”的寄存器)。
- 函数正在使用的寄存器以及何时需要保存/恢复它们
- 使用哪些硬件指令来触发函数调用的返回,以及该指令对堆栈有何影响。
编译器遵循硬件架构的一套完善的规则(调用约定),以便由不同编译器构建的不同部分组成的程序可以互操作。
请注意,尽管运行时激活堆栈 (3) 是“堆栈”抽象 (1) 的实现,但除了推送/弹出记录的概念之外,它与基于链接的实现几乎没有相似之处。
答案2
如前所述,堆栈是一种通用数据类型,在任何给定的通用操作系统上可能有多种堆栈实现。不存在单一堆栈这堆栈,除非您是系统级程序员,在这种情况下,硬件调用堆栈可能就是它。或许。
OpenSSL 有一个stack.h
,该库实现了堆栈数据结构。也许这就是你找到的那个。C++也有标准容器std::stack
。 (该文件可能被称为stack
,在我的 Linux 上指的是stl_stack.h
。)通常您不会安装库的源代码文件,因为它们对于不负责修改该库的人来说没有用处。即使是头文件也只需要编译使用该库的东西。