如何用C/C++实现仅在内存中保留一页的栈结构？

完全可以基于C/C++指针结合mmap实现这种单页驻留的栈结构——核心思路是只在内存中维护当前活跃的栈页，其余数据持久化在磁盘文件中，通过页切换时的内存映射操作完成磁盘与内存的同步，避免频繁全栈IO。

关键设计要点 #

1. 页对齐的栈布局 #

• 先通过sysconf(_SC_PAGESIZE)获取系统页大小，栈的每个逻辑页对应磁盘文件中一块页大小对齐的区域，每个页可存储PAGE_SIZE / sizeof(ElementType)个栈元素（比如int类型的话，每页能存PAGE_SIZE/4个元素）。
• 磁盘文件作为栈的持久化载体，初始大小设为一页，后续扩展时每次追加一页。

2. 核心状态变量 #

需要维护几个关键状态来管理页与栈：

• void* current_page_ptr：指向当前驻留在内存中的栈页的指针（mmap返回的地址）。
• size_t current_page_num：当前驻留页的页号（从0开始计数）。
• size_t global_top_idx：整个栈（含磁盘部分）的栈顶元素索引（从0开始，栈空时为0）。
• int fd：磁盘栈文件的文件描述符。
• size_t page_size：系统页大小。
• bool is_dirty：标记当前页是否被修改，用于避免不必要的磁盘同步。

3. 页切换逻辑 #

当PUSH/POP操作需要访问的页不是当前驻留页时，执行以下步骤：

1. 若当前页被修改（is_dirty为true），调用msync(current_page_ptr, page_size, MS_SYNC)将内存数据同步回磁盘。
2. 调用munmap(current_page_ptr, page_size)释放当前页的内存映射。
3. 计算目标页在磁盘文件中的偏移：off_t target_offset = current_page_num * page_size。若目标页超出当前文件大小，用ftruncate(fd, target_offset + page_size)扩展文件。
4. 重新映射目标页到内存：current_page_ptr = mmap(NULL, page_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, target_offset)，更新current_page_num和is_dirty为false。

C语言代码实现示例 #

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdbool.h>

typedef int ElementType;

typedef struct {
    int fd;
    void* current_page_ptr;
    size_t current_page_num;
    size_t global_top_idx;
    size_t page_size;
    bool is_dirty;
} DiskStack;

// 初始化磁盘栈，创建或打开指定的磁盘文件
DiskStack* disk_stack_init(const char* filename) {
    DiskStack* stack = malloc(sizeof(DiskStack));
    if (!stack) return NULL;

    // 获取系统页大小
    stack->page_size = sysconf(_SC_PAGESIZE);
    if (stack->page_size == -1) {
        free(stack);
        return NULL;
    }

    // 打开或创建磁盘文件
    stack->fd = open(filename, O_RDWR | O_CREAT, S_IRUSR | S_IWUSR);
    if (stack->fd == -1) {
        free(stack);
        return NULL;
    }

    // 确保文件至少有一页大小
    struct stat st;
    if (fstat(stack->fd, &st) == -1 || st.st_size < stack->page_size) {
        if (ftruncate(stack->fd, stack->page_size) == -1) {
            close(stack->fd);
            free(stack);
            return NULL;
        }
    }

    // 映射初始页（第0页）到内存
    stack->current_page_ptr = mmap(NULL, stack->page_size, PROT_READ | PROT_WRITE, MAP_SHARED, stack->fd, 0);
    if (stack->current_page_ptr == MAP_FAILED) {
        close(stack->fd);
        free(stack);
        return NULL;
    }

    stack->current_page_num = 0;
    stack->global_top_idx = 0;
    stack->is_dirty = false;

    return stack;
}

// 切换到目标页
static int disk_stack_switch_page(DiskStack* stack, size_t target_page_num) {
    if (target_page_num == stack->current_page_num) return 0;

    // 同步当前脏页到磁盘
    if (stack->is_dirty) {
        if (msync(stack->current_page_ptr, stack->page_size, MS_SYNC) == -1) {
            return -1;
        }
        stack->is_dirty = false;
    }

    // 释放当前页映射
    if (munmap(stack->current_page_ptr, stack->page_size) == -1) {
        return -1;
    }

    // 计算目标页偏移，若文件不足则扩展
    off_t target_offset = target_page_num * stack->page_size;
    struct stat st;
    if (fstat(stack->fd, &st) == -1 || st.st_size < target_offset + stack->page_size) {
        if (ftruncate(stack->fd, target_offset + stack->page_size) == -1) {
            return -1;
        }
    }

    // 映射目标页
    stack->current_page_ptr = mmap(NULL, stack->page_size, PROT_READ | PROT_WRITE, MAP_SHARED, stack->fd, target_offset);
    if (stack->current_page_ptr == MAP_FAILED) {
        return -1;
    }

    stack->current_page_num = target_page_num;
    return 0;
}

// PUSH操作
int disk_stack_push(DiskStack* stack, ElementType val) {
    // 计算栈顶要存入的页号和页内偏移
    size_t elements_per_page = stack->page_size / sizeof(ElementType);
    size_t target_page_num = stack->global_top_idx / elements_per_page;
    size_t offset_in_page = stack->global_top_idx % elements_per_page;

    // 切换到目标页
    if (disk_stack_switch_page(stack, target_page_num) == -1) {
        return -1;
    }

    // 写入元素到内存页
    ((ElementType*)stack->current_page_ptr)[offset_in_page] = val;
    stack->global_top_idx++;
    stack->is_dirty = true;

    return 0;
}

// POP操作
int disk_stack_pop(DiskStack* stack, ElementType* out_val) {
    if (stack->global_top_idx == 0) {
        // 栈空
        return -1;
    }

    stack->global_top_idx--;
    size_t elements_per_page = stack->page_size / sizeof(ElementType);
    size_t target_page_num = stack->global_top_idx / elements_per_page;
    size_t offset_in_page = stack->global_top_idx % elements_per_page;

    // 切换到目标页
    if (disk_stack_switch_page(stack, target_page_num) == -1) {
        stack->global_top_idx++; // 恢复栈顶，避免状态不一致
        return -1;
    }

    // 读取元素
    *out_val = ((ElementType*)stack->current_page_ptr)[offset_in_page];
    stack->is_dirty = true; // 栈顶位置变化，标记为脏页（后续若有新元素写入该页需要同步）

    return 0;
}

// 销毁磁盘栈，释放资源
void disk_stack_destroy(DiskStack* stack) {
    if (!stack) return;

    // 同步最后一页
    if (stack->is_dirty) {
        msync(stack->current_page_ptr, stack->page_size, MS_SYNC);
    }

    munmap(stack->current_page_ptr, stack->page_size);
    close(stack->fd);
    free(stack);
}

// 示例用法
int main() {
    DiskStack* stack = disk_stack_init("disk_stack.dat");
    if (!stack) {
        perror("Failed to init disk stack");
        return 1;
    }

    // 测试PUSH
    for (int i = 0; i < 10000; i++) {
        if (disk_stack_push(stack, i) == -1) {
            perror("Push failed");
            disk_stack_destroy(stack);
            return 1;
        }
    }

    // 测试POP
    ElementType val;
    for (int i = 9999; i >= 0; i--) {
        if (disk_stack_pop(stack, &val) == -1) {
            perror("Pop failed");
            disk_stack_destroy(stack);
            return 1;
        }
        if (val != i) {
            printf("Mismatch: expected %d, got %d\n", i, val);
            disk_stack_destroy(stack);
            return 1;
        }
    }

    printf("All operations succeeded\n");
    disk_stack_destroy(stack);
    return 0;
}

注意事项 #

• 脏页优化：通过is_dirty标记避免无修改页的同步，减少磁盘IO次数。
• 错误处理：代码中省略了部分错误处理的细节，实际使用时需完善所有系统调用的返回值检查。
• 线程安全：若多线程访问栈，需在页切换、PUSH/POP操作前后加互斥锁（如pthread_mutex_t）。
• C++封装：可以将上述结构封装成类，用RAII机制管理文件描述符和内存映射，提升代码安全性。

内容的提问来源于stack exchange，提问作者frozenca