c语言数据结构的数据存储

Ⅰ C语言内存管理机制--malloc/calloc/free原理与实现

一、C程序的存储空间布局

在C程序中，存储空间布局通常分为栈和堆两种类型。栈用于函数调用时的局部变量存储，其大小由编译器自动管理，遵循后进先出（LIFO）原则。堆用于动态内存分配，可以由程序在运行时动态地请求和释放内存。

二、Heap内存模型

在堆内存中，malloc所申请的内存主要从堆区域分配。Linux内核通过维护一个break指针来管理堆空间。这个指针指向堆空间的某个地址，从堆起始地址（Heap’s Start）到break之间的地址空间为映射好的（虚拟地址与物理地址的映射，通过MMU实现），可以供进程访问。从break向上，是未映射的地址空间，访问这些空间会导致程序报错。

三、调整break：brk()和sbrk()

break指针最初位于bss段的末尾之后，当break指针升高时，程序可以访问新分配区域内的任何内存地址，而此时物理内存页尚未分配，内存会在进程首次试图访问这些虚拟内存地址时自动分配新的物理内存页。

Linux通过brk和sbrk系统调用操作break指针。brk()将break指针设置为指定位置，地址四舍五入到下一个内存页的边界处。sbrk()将break指针在原有地址基础上增加指定的大小。sbrk(0)返回当前break指针的位置。系统对进程所分配的资源有限，包括映射的内存空间。

四、malloc

malloc函数用于在系统中动态分配连续的可用内存。它要求内存大小至少为指定的字节数，返回指向内存块起始地址的指针，多次调用不重叠分配地址，实现内存分配和释放。malloc函数的返回值总是字节对齐，适合高效访问C语言数据结构。

五、初探实现malloc

一个简单实现的malloc函数直接从未映射区域划出内存，但忽略了记录分配的内存块信息，导致内存释放时无法确定释放的大小，需要额外数据结构记录块信息。

六、正式实现malloc

实现一个完整的malloc需要一个数据结构组织堆内存，每个内存块包含元信息（大小、空闲状态、指针）和实际数据区域。查找合适的内存块、分配新的块、分裂块等操作需实现相应函数。

七、calloc的实现

calloc函数用于给一组相同对象分配内存，并初始化它们。实现只需两次调用malloc，一次分配内存，另一次初始化。

八、free的实现

free函数需要验证地址的有效性，并解决碎片问题。实现策略包括合并相邻空闲内存块，确保释放的地址与未映射区域之间是空闲的。

九、realloc的实现

realloc函数调整已分配内存的大小。实现包括复制现有内存、调整大小、释放旧内存等操作。

十、总结

通过上述机制，C语言提供内存管理功能，允许程序动态分配和释放内存。优化空间和实际应用的内存管理策略如Linux内核伙伴算法、STL空间配置器等提供了更高效的实现。