最近看了看書(shū)，看了看博客，聽(tīng)了聽(tīng)高人們的談?wù)?，心里有些體會(huì)，記錄下來(lái)，算是最近寫的一個(gè)關(guān)于堆代碼的總結(jié)吧，雖然是很簡(jiǎn)單的應(yīng)用，但是自己從中學(xué)到了知識(shí)，也算收貨不少。某位偉人說(shuō)的，人生每天進(jìn)步一點(diǎn)點(diǎn)，（后面是啥，忘記了。。。）。好了，不扯淡了，開(kāi)始話題。

首先，我來(lái)說(shuō)下怎么用單鏈表去模擬一個(gè)堆（準(zhǔn)確說(shuō)是一個(gè)內(nèi)存池）。

用單鏈表去記錄一些可用的memory，主要是用單鏈表把這些可用的內(nèi)存記錄起來(lái)。

用自己的malloc去從單鏈表中返回一個(gè)可用內(nèi)存，并把這片可用內(nèi)存從鏈表中刪除。

用自己的free把用完的內(nèi)存再添加到可用內(nèi)存鏈表中。

有個(gè)memory_add函數(shù)，把一片可用內(nèi)存初始化為可用的內(nèi)存鏈表。

具體實(shí)現(xiàn)：

void free_check_str_t(check_str_t *ptItem)
{
check_t* ptThis = (check_t*)ptItem;
check_t* ptTempList = s_ptFreeList;
if(NULL == ptThis){
return;
}

s_ptFreeList = &this;
this.ptNext = ptTempList;
}

check_str_t *malloc_check_str_t(void)
{
check_t *ptThis = s_ptFreeList;
if(NULL == ptThis){
return NULL;
}


s_ptFreeList = this.ptNext;
this.ptNext = NULL;
return (check_str_t*)(&this.tItem);
}

bool add_memory_block_to_check_str_t_heap(void *pBlock, uint32_t wBlockSize)
{
check_t *ptNew = NULL;
uint8_t *pchTemp = pBlock;
uint32_t wi = 0;
if(NULL == pBlock){
return false;
}
if(CHECK_LIST_ITEM_SIZE > wBlockSize){
return false;
}
//添加新的節(jié)點(diǎn)
for(wi=0;wi if((wi + CHECK_LIST_ITEM_SIZE) > wBlockSize){//剩余不夠，不再分配
return true;
}
ptNew = (check_t *)(pchTemp+wi);
free_check_str_t((check_str_t*)ptNew);
}
return true;
}

這樣就是實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的專用堆，準(zhǔn)確說(shuō)是棧結(jié)構(gòu)的。這樣做比用static的變量去實(shí)現(xiàn)有什么好處呢？

先說(shuō)缺點(diǎn)：

1、相同的變量比原來(lái)要多一個(gè)指針空間（不是鏈表自身，而是存儲(chǔ)申請(qǐng)的HEAP地址）；

2、這個(gè)缺點(diǎn)很重要，一不小心就內(nèi)存泄漏；

既然有缺點(diǎn)，為什么人們還熱此不彼的去用專用堆呢？

我開(kāi)始沒(méi)理解，后來(lái)還是沒(méi)理解。原來(lái)這么做是為了以時(shí)間換空間（引出了今天的話題）。什么意思呢？

比方說(shuō)，上面是一個(gè)可重入的模塊，它提供某項(xiàng)服務(wù)（需要消耗一個(gè)struct 空間）。

有三個(gè)任務(wù)A/B/C都要需要調(diào)用這個(gè)服務(wù)。假如RAM寬裕，可以為每個(gè)任務(wù)都單獨(dú)提供一個(gè)struct（為了重入），

那么這個(gè)時(shí)候這三個(gè)任務(wù)不需要等待，就可以同時(shí)運(yùn)行，也就是通過(guò)犧牲RAM（空間），換取三個(gè)任務(wù)同時(shí)運(yùn)行時(shí)間。

假如RAM不夠大，那么只能用一個(gè)struct，大家輪流去申請(qǐng)，誰(shuí)申請(qǐng)到誰(shuí)用，用完釋放掉，這樣本來(lái)三個(gè)可以并行運(yùn)行的任務(wù)，

由于RAM限制，不得不順序執(zhí)行，這就是以時(shí)間換空間。也就是說(shuō)用提供模塊的專用堆，我們可以很方便的根據(jù)實(shí)際RAM大小去選擇

運(yùn)行方案，而不需要更要上層調(diào)用邏輯。這就是專用HEAP作用。

其實(shí)說(shuō)來(lái)這么多廢話，主要是想引出下面這邊博客（不要罵我無(wú)恥，其實(shí)我就是菜鳥(niǎo)，才剛學(xué)）：

出處：http://www.amobbs.com/thread-5642364-1-1.html

雖然不是Linux提出的概念，但流（Stream）和塊（Block）處理的深入人心絕對(duì)離不開(kāi)流文件和
塊文件的功勞。然而，流和塊其實(shí)是更為通用的概念，它們分別代表了數(shù)據(jù)處理中 “以時(shí)間換空間”
和 “以空間換時(shí)間” 的兩種截然不同的偏重策略。

1、以空間換時(shí)間的塊處理
　　說(shuō)到塊處理，其最顯著的特征就是，將所要處理的數(shù)據(jù)用一段連續(xù)的存儲(chǔ)器保存下來(lái)，我們可以
隨機(jī)對(duì)對(duì)這些數(shù)據(jù)進(jìn)行訪問(wèn)和處理——簡(jiǎn)單說(shuō)就是以保存數(shù)據(jù)所占用的存儲(chǔ)器空間換取了訪問(wèn)的便利
性，降低了訪問(wèn)和處理的時(shí)間成本——因此我們可以說(shuō)，塊處理是一個(gè)典型的用存儲(chǔ)器空間換取處理
時(shí)間的策略。
　　舉例來(lái)說(shuō)，假設(shè)我們需要從一段文字中中處理其中某幾個(gè)單詞，我們可以先簡(jiǎn)單的將整段文字連
續(xù)的保存在RAM中，然后使用基于塊的字符串處理函數(shù)對(duì)其進(jìn)行操作。由于訪問(wèn)方式簡(jiǎn)單直接（隨機(jī)
訪問(wèn)），因此字符串處理的效率主要由處理的算法決定，字符串訪問(wèn)并不是瓶頸——簡(jiǎn)單說(shuō)，就是算
法能多快快，整個(gè)操作就有多快，對(duì)字符串的訪問(wèn)并不存在額外的時(shí)延。

　　實(shí)際上，這個(gè)例子看似存在問(wèn)題，因?yàn)樽址幚淼幕締挝蝗匀皇亲址?，雖然目標(biāo)數(shù)據(jù)被完整
地保存在數(shù)據(jù)塊中，但常見(jiàn)的字符串操作仍然和流一樣需要“一個(gè)字符一個(gè)字符”的順次進(jìn)行（例如比
較字符串，或者是查找字符串位置）。但我不得不舉這個(gè)例子，因?yàn)樗粌H僅是最常見(jiàn)的流操作和塊
操作的目標(biāo)，更重要的是，這種 “一個(gè)字符一個(gè)字符處理” 的特性讓人們對(duì)流處理和塊處理的特點(diǎn)在認(rèn)
識(shí)上造成了模糊。因此，這里我想通過(guò)這個(gè)例子特別指出：

> 塊處理中，字符串處理效率的瓶頸是由算法本身決定的，與之相比，數(shù)據(jù)訪問(wèn)的成本幾乎可以忽略
不計(jì)（隨機(jī)訪問(wèn)）。塊處理的優(yōu)勢(shì)體現(xiàn)在，當(dāng)我們以任意順序訪問(wèn)塊中的任意數(shù)據(jù)時(shí)，這里的訪問(wèn)成
本是最低的。塊處理往往可以理解為：批量的處理，是效率的代名詞；

> 流處理中，字符串處理效率的瓶頸是數(shù)據(jù)的訪問(wèn)，與之相對(duì)，算法的效率問(wèn)題幾乎可以忽略（順序
訪問(wèn)）——要么是程序處理好當(dāng)前字符后，喝完茶、打了個(gè)瞌睡，下一個(gè)字符還沒(méi)有就緒；要么是處
理器處理一個(gè)字符所消耗的時(shí)間遠(yuǎn)沒(méi)有從流中讀取下一個(gè)字符來(lái)得長(zhǎng)（考慮多任務(wù)間的隊(duì)列通信）。
實(shí)際應(yīng)用中，這兩種情形往往是結(jié)合在一起的——當(dāng)某個(gè)任務(wù)“焦急”的從串口緩沖區(qū)中嘗試讀取下一
個(gè)字符以便進(jìn)行數(shù)據(jù)幀解析時(shí)，隊(duì)列操作的時(shí)間、等待字符接收完成的時(shí)間通常比單獨(dú)一個(gè)字符的處
理時(shí)間高出好幾個(gè)數(shù)量級(jí)。

　　說(shuō)了那么多廢話，讓我們來(lái)做一個(gè)小結(jié)：塊（Block）處理就是消耗存儲(chǔ)器空間將目標(biāo)數(shù)據(jù)都存儲(chǔ)
下來(lái)，以方便數(shù)據(jù)處理算法隨機(jī)的對(duì)其進(jìn)行訪問(wèn)，從而至少節(jié)省訪問(wèn)時(shí)間的一種處理方式（由于訪問(wèn)
是隨機(jī)的，可選用的算法就變得多樣起來(lái)，選擇最優(yōu)的算法也會(huì)帶來(lái)額外的好處）。這是一個(gè)以存儲(chǔ)
器空間換取訪問(wèn)時(shí)間的策略。

　　塊的表現(xiàn)形式，是一段可隨機(jī)訪問(wèn)的存儲(chǔ)器空間?！翱呻S機(jī)訪問(wèn)”是其時(shí)間上的本質(zhì)，而塊并不要
求數(shù)據(jù)在空間上是連續(xù)的（雖然字面上感覺(jué)應(yīng)該要連續(xù)，但這種連續(xù)性并不是強(qiáng)制的）。

2、以時(shí)間換空間的流處理
　　流處理最顯著的特點(diǎn)就是，大的數(shù)據(jù)塊被人為拆分成小的數(shù)據(jù)單元，數(shù)據(jù)的處理方一次只能接收
或者處理一個(gè)數(shù)據(jù)單元。流處理最大的限制是數(shù)據(jù)訪問(wèn)順序的限制——所有的數(shù)據(jù)單元必須按照流發(fā)
送方提供的順序進(jìn)行訪問(wèn)。正是由于這種訪問(wèn)順序的限制，讓流的處理方常常覺(jué)得“誰(shuí)用誰(shuí)知道”的別
扭?！芏鄷r(shí)候，為了數(shù)據(jù)訪問(wèn)的方便，會(huì)將一部分流先緩沖成小的數(shù)據(jù)塊，再以塊的方式進(jìn)行處
理——典型的例子就是串行數(shù)據(jù)通信中常見(jiàn)的數(shù)據(jù)幀（Frame）。
　　流處理的好處也是顯而易見(jiàn)的，由于不需要大塊的存儲(chǔ)器空間用于數(shù)據(jù)的暫存，因而在小資源的
處理器，尤其是小SRAM的MCU中尤其流行。缺點(diǎn)是，受制于訪問(wèn)順序，流處理的算法往往較為復(fù)雜，
有些功能甚至是無(wú)法實(shí)現(xiàn)的（單憑流處理本身無(wú)法實(shí)現(xiàn)，需要局部應(yīng)用快處理）；同時(shí)流處理的數(shù)據(jù)
存取時(shí)間造成的浪費(fèi)也非?？捎^。人常說(shuō)，流處理的本質(zhì)就是零庫(kù)存的手工作坊，一切都得按步就班
的來(lái)，提高流處理效率的方法就是把數(shù)據(jù)傳輸所需的等待時(shí)間以流水線的方式利用起來(lái)。

　　小結(jié)一下，流（Stream）處理是以消耗更多處理器時(shí)間，并增加訪問(wèn)順序的限制（順序限制仍然
是時(shí)間軸上的一種限制）的方法，節(jié)省存儲(chǔ)器空間的一種處理方式。這是一個(gè)以時(shí)間換空間的策略。

3、流和塊的互換
　　在常見(jiàn)的嵌入式系統(tǒng)數(shù)據(jù)流中，每一個(gè)數(shù)據(jù)處理環(huán)節(jié)（簡(jiǎn)稱數(shù)據(jù)處理Process）對(duì)時(shí)間和空間的偏
好是不同的。這里的數(shù)據(jù)流可能包含多個(gè)分工不同的子系統(tǒng)（處理器），甚至包含遠(yuǎn)端的服務(wù)器系統(tǒng)。
有的Process對(duì)性能（時(shí)間）敏感并擁有寬裕的RAM，顯然應(yīng)該利用塊處理“以空間換時(shí)間”的特性，將
RAM富余的優(yōu)勢(shì)更多的轉(zhuǎn)化為性能優(yōu)勢(shì)；有的Process對(duì)空間敏感（往往是成本敏感導(dǎo)致的），對(duì)性能
則要求不高（比如UART，9600，甚至是2400波特率傳輸信息，比如紅外遙控器傳輸遙控信息），這
種情況下，以流處理?yè)Q取更多的成本優(yōu)勢(shì)幾乎是不二的選擇。
　　那么，當(dāng)一個(gè)數(shù)據(jù)流中，相鄰的Process存在不同的偏好時(shí)怎么協(xié)調(diào)呢？

> 生產(chǎn)者Process使用“流”處理；消費(fèi)者Process使用“塊”處理
１、由消費(fèi)者提供一個(gè)隊(duì)列Q，該隊(duì)列將用于保存數(shù)據(jù)的塊MEM提供給Q作為緩沖區(qū)初始化為空隊(duì)列；
２、永久封堵Ｑ的出隊(duì)接口
３、將Ｑ的入隊(duì)接口提供給生產(chǎn)者
４、當(dāng)隊(duì)列滿時(shí)，將MEM取出，交給消費(fèi)者處理；
５、如果MEM是堆分配的，則嘗試從堆中獲取一個(gè)新的MEM，重復(fù)1的步驟；當(dāng)消費(fèi)者完成對(duì)數(shù)據(jù)MEM
的處理后，應(yīng)當(dāng)在隨后適當(dāng)?shù)奈恢脤EM釋放回堆中

> 生產(chǎn)者Process使用“塊”處理；消費(fèi)者Process使用“流”處理
１、由生產(chǎn)者提供一個(gè)隊(duì)列Q，并將保存數(shù)據(jù)的塊MEM提供給Q作為緩沖區(qū)初始化為滿隊(duì)列；
２、永久封堵Q的入隊(duì)接口
３、將Ｑ的出隊(duì)接口提供給消費(fèi)者
４、當(dāng)隊(duì)列為空時(shí)，１）如果MEM是堆分配的，則將MEM釋放回堆，并等待生產(chǎn)者提供可用的數(shù)據(jù)塊，
進(jìn)而回到步驟1；2）如果MEM是靜態(tài)分配的，唯一的，則在此時(shí)還給生產(chǎn)者做下一次的數(shù)據(jù)生產(chǎn)；

　　通過(guò)上面的描述，我們發(fā)現(xiàn)，隊(duì)列（Queue）在流塊互轉(zhuǎn)間扮演了關(guān)鍵的橋梁作用。這里不僅有傳
統(tǒng)意義上“將隊(duì)列初始化為空”的操作，還引入了“將隊(duì)列初始化為滿”的概念。

　　為什么隊(duì)列如此神奇呢？因?yàn)槠浔举|(zhì)是：用存儲(chǔ)器空間為“出隊(duì)”、“入隊(duì)”之間偶爾的瞬間速度差爭(zhēng)
取時(shí)間。（相信大家都知道小學(xué)時(shí)候變態(tài)的泳池放水模型）隊(duì)列是一個(gè)典型的用空間換時(shí)間的數(shù)據(jù)結(jié)
構(gòu)。它能爭(zhēng)取的是“出隊(duì)”、“入隊(duì)”之間由于速度差導(dǎo)致的時(shí)間差異，能換多少時(shí)間，完全由緩沖區(qū)大小
決定。

　　我們有很多“同志”總是把隊(duì)列當(dāng)成萬(wàn)能藥，只要覺(jué)得數(shù)據(jù)傳輸“可能出現(xiàn)速度不一致的問(wèn)題”，就吃
一粒，也不管這種速度差異是不是恒定的（如果入隊(duì)比出隊(duì)恒定大，則隊(duì)列必溢出，時(shí)間早晚由隊(duì)列
緩沖大小決定）；就好像用了隊(duì)列就可以當(dāng)自己為鴕鳥(niǎo)——把腦袋扎進(jìn)沙子里——而所有通信的問(wèn)題就
不存在了一樣：

　　 恩！存在也不是速度差異的問(wèn)題——“我用隊(duì)列了阿？為什么還有問(wèn)題？”——呵呵噠！

　　其實(shí)，整篇文章鋪墊那么多，就是為了最后一處吐槽作鋪墊，吐完收工！暢快！舒服～哈哈哈哈。