我正在尋找實現一個堆分配算法在C爲一個內存受限的微控制器。我已將搜索範圍縮小到了我所知道的兩個選項，但我非常樂於接受建議，並且正在尋找來自具有此經驗的任何人的建議或意見。抗碎片微控制器堆算法
我的要求：
- 速度絕對計數，但它是一個次要問題。
-timing決定並不重要 - 要求確定性最壞情況時序代碼的任何部分都有其自己的分配方法。
- 主要要求是破碎免疫力。該設備正在運行一個lua腳本引擎，這將需要一定範圍的分配大小（在32字節塊上很重）。主要要求是該設備可以長時間運行，而不會使其堆成無法使用的狀態。
另外注意：
（僅供參考）中，我們談論的Cortex-M和PIC32部位，用存儲器範圍從128K和16MB或存儲器（重點是下端）。
- 我不想使用編譯器的堆，因爲1）我想對所有的編譯器一致的性能和2）它們的實現一般都非常簡單，是相同的或碎裂更糟。
-double間接的選項，因爲我不想fundamtnetally變化和重新驗證巨大的Lua代碼基地出來。
我的青睞途徑迄今：
1）具有二進制好友分配器，和犧牲存儲器的使用效率（四捨五入至2大小的功率）。 - 這將（根據我的理解）需要一個二叉樹的每個訂單/斌來存儲空閒節點按內存地址排序快速夥伴塊查找重新鏈接。
2）有兩個空閒塊的二叉樹，一個按大小排序，另一個按內存地址排序。 （所有的二叉樹鏈接存儲在塊本身） -分配將是最適合的，使用在表中按大小查找，然後通過地址 從其他樹中刪除該塊 - 分配將通過地址查找相鄰塊rechaining
導向軸算法也將需要所分配的塊的開始之前存儲的分配尺寸，並具有塊出去作爲2減去4的功率（或8取決於對準）。 （除非它們存儲二叉樹其他地方來跟蹤內存地址進行排序分配，我不認爲一個好的選擇）
導向軸算法需要高度平衡二叉樹的代碼。
- 算法2沒有通過舍入到2的冪來浪費內存的要求。
-In任一情況下，我將可能有由嵌套比特字段來卸載塊這個尺寸或更小，這將是不受外部碎片分配32字節的塊的固定銀行。
我的問題：
-Is有什麼理由方法1會比方法2個免疫不成？
-Are那裏，我很想念這可能符合要求的替代品？
夥伴系統沒有使用二叉樹釋放，當它找到一個塊的可能夥伴。您可以根據原始塊的地址計算好友的地址。然後你檢查一下，看看這個夥伴是免費還是使用。您可以將該位置放在該區域的起始位置 - 因此您實際上不會獲得32個字節，但可能有31個可用字節。您可以通過使用免費/使用的單獨位圖來更改此設置。 Knuth描述了一個免費使用標籤位的版本 – mcdowella
Yah，我只是想到了這一點。我認爲2GB的塊大小可能足夠了:)我也認爲擺脫二叉樹免費節點的作用是將每個bin/order的空閒節點存儲在一個雙鏈接的循環列表中，然後使用好友的指向鏈接下一個和前一個節點的指針（並且如果節點指向正被移除的節點，則將頭部ptr提前一個節點）。通過這種方式，根本不需要搜索來查找和刪除免費好友。因此，沒有二叉樹實現。思考？ –
你真的需要分配嗎？像這些嵌入式系統通常不分配，但使用固定大小的結構（當然堆棧除外，你必須小心）。給被認爲是堅如磐石的東西增加了太多的風險。 –