最近看了看書，看了看博客，聽了聽高人們的談?wù)?，心里有些體會，記錄下來，算是最近寫的一個關(guān)于堆代碼的總結(jié)吧，雖然是很簡單的應(yīng)用，但是自己從中學(xué)到了知識，也算收貨不少。某位偉人說的，人生每天進(jìn)步一點(diǎn)點(diǎn)，（后面是啥，忘記了。。。）。好了，不扯淡了，開始話題。
首先，我來說下怎么用單鏈表去模擬一個堆（準(zhǔn)確說是一個內(nèi)存池）。
用單鏈表去記錄一些可用的memory，主要是用單鏈表把這些可用的內(nèi)存記錄起來。
用自己的malloc去從單鏈表中返回一個可用內(nèi)存，并把這片可用內(nèi)存從鏈表中刪除。
用自己的free把用完的內(nèi)存再添加到可用內(nèi)存鏈表中。
有個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
return true;
}
ptNew = (check_t *)(pchTemp+wi);
free_check_str_t((check_str_t*)ptNew);
}
return true;
}
這樣就是實(shí)現(xiàn)了一個簡單的專用堆，準(zhǔn)確說是棧結(jié)構(gòu)的。這樣做比用static的變量去實(shí)現(xiàn)有什么好處呢？
先說缺點(diǎn)：
1、相同的變量比原來要多一個指針空間（不是鏈表自身，而是存儲申請的HEAP地址）；
2、這個缺點(diǎn)很重要，一不小心就內(nèi)存泄漏；
既然有缺點(diǎn)，為什么人們還熱此不彼的去用專用堆呢？
我開始沒理解，后來還是沒理解。原來這么做是為了以時間換空間（引出了今天的話題）。什么意思呢？
比方說，上面是一個可重入的模塊，它提供某項(xiàng)服務(wù)（需要消耗一個struct 空間）。
有三個任務(wù)A/B/C都要需要調(diào)用這個服務(wù)。假如RAM寬裕，可以為每個任務(wù)都單獨(dú)提供一個struct（為了重入），
那么這個時候這三個任務(wù)不需要等待，就可以同時運(yùn)行，也就是通過犧牲RAM（空間），換取三個任務(wù)同時運(yùn)行時間。
假如RAM不夠大，那么只能用一個struct，大家輪流去申請，誰申請到誰用，用完釋放掉，這樣本來三個可以并行運(yùn)行的任務(wù)，
由于RAM限制，不得不順序執(zhí)行，這就是以時間換空間。也就是說用提供模塊的專用堆，我們可以很方便的根據(jù)實(shí)際RAM大小去選擇
運(yùn)行方案，而不需要更要上層調(diào)用邏輯。這就是專用HEAP作用。
其實(shí)說來這么多廢話，主要是想引出下面這邊博客（不要罵我無恥，其實(shí)我就是菜鳥，才剛學(xué)）：
出處：http://www.amobbs.com/thread-5642364-1-1.html
雖然不是Linux提出的概念，但流（Stream）和塊（Block）處理的深入人心絕對離不開流文件和
塊文件的功勞。然而，流和塊其實(shí)是更為通用的概念，它們分別代表了數(shù)據(jù)處理中 “以時間換空間”
和 “以空間換時間” 的兩種截然不同的偏重策略。
1、以空間換時間的塊處理
說到塊處理，其最顯著的特征就是，將所要處理的數(shù)據(jù)用一段連續(xù)的存儲器保存下來，我們可以
隨機(jī)對對這些數(shù)據(jù)進(jìn)行訪問和處理——簡單說就是以保存數(shù)據(jù)所占用的存儲器空間換取了訪問的便利
性，降低了訪問和處理的時間成本——因此我們可以說，塊處理是一個典型的用存儲器空間換取處理
時間的策略。
舉例來說，假設(shè)我們需要從一段文字中中處理其中某幾個單詞，我們可以先簡單的將整段文字連
續(xù)的保存在RAM中，然后使用基于塊的字符串處理函數(shù)對其進(jìn)行操作。由于訪問方式簡單直接（隨機(jī)
訪問），因此字符串處理的效率主要由處理的算法決定，字符串訪問并不是瓶頸——簡單說，就是算
法能多快快，整個操作就有多快，對字符串的訪問并不存在額外的時延。
實(shí)際上，這個例子看似存在問題，因?yàn)樽址幚淼幕締挝蝗匀皇亲址m然目標(biāo)數(shù)據(jù)被完整
地保存在數(shù)據(jù)塊中，但常見的字符串操作仍然和流一樣需要“一個字符一個字符”的順次進(jìn)行（例如比
較字符串，或者是查找字符串位置）。但我不得不舉這個例子，因?yàn)樗粌H僅是最常見的流操作和塊
操作的目標(biāo)，更重要的是，這種 “一個字符一個字符處理” 的特性讓人們對流處理和塊處理的特點(diǎn)在認(rèn)
識上造成了模糊。因此，這里我想通過這個例子特別指出：
> 塊處理中，字符串處理效率的瓶頸是由算法本身決定的，與之相比，數(shù)據(jù)訪問的成本幾乎可以忽略
不計(jì)（隨機(jī)訪問）。塊處理的優(yōu)勢體現(xiàn)在，當(dāng)我們以任意順序訪問塊中的任意數(shù)據(jù)時，這里的訪問成
本是最低的。塊處理往往可以理解為：批量的處理，是效率的代名詞；
> 流處理中，字符串處理效率的瓶頸是數(shù)據(jù)的訪問，與之相對，算法的效率問題幾乎可以忽略（順序
訪問）——要么是程序處理好當(dāng)前字符后，喝完茶、打了個瞌睡，下一個字符還沒有就緒；要么是處
理器處理一個字符所消耗的時間遠(yuǎn)沒有從流中讀取下一個字符來得長（考慮多任務(wù)間的隊(duì)列通信）。
實(shí)際應(yīng)用中，這兩種情形往往是結(jié)合在一起的——當(dāng)某個任務(wù)“焦急”的從串口緩沖區(qū)中嘗試讀取下一
個字符以便進(jìn)行數(shù)據(jù)幀解析時，隊(duì)列操作的時間、等待字符接收完成的時間通常比單獨(dú)一個字符的處
理時間高出好幾個數(shù)量級。
說了那么多廢話，讓我們來做一個小結(jié)：塊（Block）處理就是消耗存儲器空間將目標(biāo)數(shù)據(jù)都存儲
下來，以方便數(shù)據(jù)處理算法隨機(jī)的對其進(jìn)行訪問，從而至少節(jié)省訪問時間的一種處理方式（由于訪問
是隨機(jī)的，可選用的算法就變得多樣起來，選擇最優(yōu)的算法也會帶來額外的好處）。這是一個以存儲
器空間換取訪問時間的策略。
塊的表現(xiàn)形式，是一段可隨機(jī)訪問的存儲器空間?！翱呻S機(jī)訪問”是其時間上的本質(zhì)，而塊并不要
求數(shù)據(jù)在空間上是連續(xù)的（雖然字面上感覺應(yīng)該要連續(xù)，但這種連續(xù)性并不是強(qiáng)制的）。
2、以時間換空間的流處理
流處理最顯著的特點(diǎn)就是，大的數(shù)據(jù)塊被人為拆分成小的數(shù)據(jù)單元，數(shù)據(jù)的處理方一次只能接收
或者處理一個數(shù)據(jù)單元。流處理最大的限制是數(shù)據(jù)訪問順序的限制——所有的數(shù)據(jù)單元必須按照流發(fā)
送方提供的順序進(jìn)行訪問。正是由于這種訪問順序的限制，讓流的處理方常常覺得“誰用誰知道”的別
扭?！芏鄷r候，為了數(shù)據(jù)訪問的方便，會將一部分流先緩沖成小的數(shù)據(jù)塊，再以塊的方式進(jìn)行處
理——典型的例子就是串行數(shù)據(jù)通信中常見的數(shù)據(jù)幀（Frame）。
流處理的好處也是顯而易見的，由于不需要大塊的存儲器空間用于數(shù)據(jù)的暫存，因而在小資源的
處理器，尤其是小SRAM的MCU中尤其流行。缺點(diǎn)是，受制于訪問順序，流處理的算法往往較為復(fù)雜，
有些功能甚至是無法實(shí)現(xiàn)的（單憑流處理本身無法實(shí)現(xiàn)，需要局部應(yīng)用快處理）；同時流處理的數(shù)據(jù)
存取時間造成的浪費(fèi)也非?？捎^。人常說，流處理的本質(zhì)就是零庫存的手工作坊，一切都得按步就班
的來，提高流處理效率的方法就是把數(shù)據(jù)傳輸所需的等待時間以流水線的方式利用起來。
小結(jié)一下，流（Stream）處理是以消耗更多處理器時間，并增加訪問順序的限制（順序限制仍然
是時間軸上的一種限制）的方法，節(jié)省存儲器空間的一種處理方式。這是一個以時間換空間的策略。
3、流和塊的互換
在常見的嵌入式系統(tǒng)數(shù)據(jù)流中，每一個數(shù)據(jù)處理環(huán)節(jié)（簡稱數(shù)據(jù)處理Process）對時間和空間的偏
好是不同的。這里的數(shù)據(jù)流可能包含多個分工不同的子系統(tǒng)（處理器），甚至包含遠(yuǎn)端的服務(wù)器系統(tǒng)。
有的Process對性能（時間）敏感并擁有寬裕的RAM，顯然應(yīng)該利用塊處理“以空間換時間”的特性，將
RAM富余的優(yōu)勢更多的轉(zhuǎn)化為性能優(yōu)勢；有的Process對空間敏感（往往是成本敏感導(dǎo)致的），對性能
則要求不高（比如UART，9600，甚至是2400波特率傳輸信息，比如紅外遙控器傳輸遙控信息），這
種情況下，以流處理換取更多的成本優(yōu)勢幾乎是不二的選擇。
那么，當(dāng)一個數(shù)據(jù)流中，相鄰的Process存在不同的偏好時怎么協(xié)調(diào)呢？
> 生產(chǎn)者Process使用“流”處理；消費(fèi)者Process使用“塊”處理
１、由消費(fèi)者提供一個隊(duì)列Q，該隊(duì)列將用于保存數(shù)據(jù)的塊MEM提供給Q作為緩沖區(qū)初始化為空隊(duì)列；
２、永久封堵Ｑ的出隊(duì)接口
３、將Ｑ的入隊(duì)接口提供給生產(chǎn)者
４、當(dāng)隊(duì)列滿時，將MEM取出，交給消費(fèi)者處理；
５、如果MEM是堆分配的，則嘗試從堆中獲取一個新的MEM，重復(fù)1的步驟；當(dāng)消費(fèi)者完成對數(shù)據(jù)MEM
的處理后，應(yīng)當(dāng)在隨后適當(dāng)?shù)奈恢脤EM釋放回堆中
> 生產(chǎn)者Process使用“塊”處理；消費(fèi)者Process使用“流”處理
１、由生產(chǎn)者提供一個隊(duì)列Q，并將保存數(shù)據(jù)的塊MEM提供給Q作為緩沖區(qū)初始化為滿隊(duì)列；
２、永久封堵Q的入隊(duì)接口
３、將Ｑ的出隊(duì)接口提供給消費(fèi)者
４、當(dāng)隊(duì)列為空時，１）如果MEM是堆分配的，則將MEM釋放回堆，并等待生產(chǎn)者提供可用的數(shù)據(jù)塊，
進(jìn)而回到步驟1；2）如果MEM是靜態(tài)分配的，唯一的，則在此時還給生產(chǎn)者做下一次的數(shù)據(jù)生產(chǎn)；
通過上面的描述，我們發(fā)現(xiàn)，隊(duì)列（Queue）在流塊互轉(zhuǎn)間扮演了關(guān)鍵的橋梁作用。這里不僅有傳
統(tǒng)意義上“將隊(duì)列初始化為空”的操作，還引入了“將隊(duì)列初始化為滿”的概念。
為什么隊(duì)列如此神奇呢？因?yàn)槠浔举|(zhì)是：用存儲器空間為“出隊(duì)”、“入隊(duì)”之間偶爾的瞬間速度差爭
取時間。（相信大家都知道小學(xué)時候變態(tài)的泳池放水模型）隊(duì)列是一個典型的用空間換時間的數(shù)據(jù)結(jié)
構(gòu)。它能爭取的是“出隊(duì)”、“入隊(duì)”之間由于速度差導(dǎo)致的時間差異，能換多少時間，完全由緩沖區(qū)大小
決定。
我們有很多“同志”總是把隊(duì)列當(dāng)成萬能藥，只要覺得數(shù)據(jù)傳輸“可能出現(xiàn)速度不一致的問題”，就吃
一粒，也不管這種速度差異是不是恒定的（如果入隊(duì)比出隊(duì)恒定大，則隊(duì)列必溢出，時間早晚由隊(duì)列
緩沖大小決定）；就好像用了隊(duì)列就可以當(dāng)自己為鴕鳥——把腦袋扎進(jìn)沙子里——而所有通信的問題就
不存在了一樣：
恩！存在也不是速度差異的問題——“我用隊(duì)列了阿？為什么還有問題？”——呵呵噠！
其實(shí)，整篇文章鋪墊那么多，就是為了最后一處吐槽作鋪墊，吐完收工！暢快！舒服～哈哈哈哈。
下載文檔
