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空間配置器等提供了更高效的實現。