純C語言的realloc，使用起來真是有夠危險

在純C底下，動態配置記憶體。估計大家都很熟練malloc()、free()。利用malloc配置記憶體，等用完後再用free刪除。非常單純。加入realloc來攪局後，事情就變得非常複雜了。

realloc原始目的是為了提昇效率。

我先用malloc挖了100的記憶體，然後我需要加大，變成101。那我先free釋放掉100，然後再重新配置101。太慢！原先的100記憶體，它的隔壁可能恰巧是空閒記憶體，只要後面多挖1就好了。這時候就可用realloc。

大概類似這樣

void* p;
p = malloc(100);
p = realloc(p,101);
free(p);

先要了100，覺得不夠，決定改要101。事後一樣用free刪除。似乎毫無問題？


問題出在realloc的行為非常複雜，沒有想像中的那麼美好。實際上完整的realloc行為如下：

1.先從舊位置找找，看看能不能原地加大。如果可以原地加大，就直接加大，然後傳回指標即可。當然多出來的1，函式庫不會幫你填值，所以內容不知。
2.舊位置不能加大。其他記憶體挖出101，舊記憶體100資料複製過去。然後舊記憶體會用free釋放掉。新的指標傳回去。當然多出來的1，函式庫不會幫你填值，所以內容不知。
3.舊位置不能加大。其他記憶體挖不出101。舊記憶體完全不動。直接回傳NULL。

所以下面這行會有什麼問題？

void* p = realloc(p,101);

等號左右兩邊的p可能記憶體位置根本不一樣。如果遇到情況3，新的p變成NULL。舊的p沒有人去呼叫free。

所以最正確方法是這樣：

void* p;
p = malloc(100);
if(p)
{
    void *p2 = realloc(p,101);
    if(p2==NULL)
    {
        // handle your error
    }
    else
        p = p2;
}
free(p);

還有一個更麻煩的小細節。如果呼叫這行。

void *p2 = realloc(p,0);

會變成怎樣？

答案是p2會變成NULL，然後函式realloc會自動幫你free(p)。
所以你不能自己再手動free(p)一次。所以每次呼叫realloc之前，最好自己手動檢查長度。

這跟malloc行為不一樣。因為
 p = malloc(0);
是合法的。而且事後要自己手動呼叫free(p)。

就一個很簡單的函式，隱藏的大量的陷阱。太容易寫錯。

fbstring與fbvector原始碼心得導讀

代碼已經使用C++11風格，編譯器需支援C++11。

fbstring

做的非常複雜，所有最佳化的方式都用上了，時間空間均壓榨到了極限。

有些函式庫對於記憶體配置使用三個指標，A指向記憶體開頭，B指向字串結尾，C指向記憶體結尾。fbstring採用一個指標 + 兩個size_t。不過大多數的機器size_t佔用空間跟指標一樣大。

根據字串長短分成三種處理模式，短/中/長。以下均假設機器64 bits。

挪用size_t的兩個bit來紀錄狀態，，size_t長度64 bits，挪用了兩個bits，所以理論支援的字串最長可以到2的62次方。也因為挪用了兩個bits，須考慮機器是Big Endian或是Little Endian。代碼中提供kIsLittleEndian定義，可根據自己的機器來改動。

短字串：

利用三個指標佔用的記憶體來存。三指標合計24 bytes，一般的函式庫需要一個byte紀錄長度。字串結尾又需要加\0，所以被吃掉2個bytes，故短字串最長22bytes。結果 fbstring採用絕頂聰明的方式。可以存到23bytes。

假設短字串23bytes存滿，結尾就是'\0'，所以是0x00。

挪用兩個bits紀錄，它把短字串訂成00，中字串訂成10，長字串訂成01。短字串結尾是0x00，當然不影響。

正常的情況需要挪用一個bytes紀錄長度，通常放在最後一個byte。fbstring在短字串底下，不紀錄長度，而是紀錄「最大短字串長度-現在長 度」

最大短字串長度當然就是23，如果現在字串長度也是23，那最後一個byte就是0，剛好也是'\0'。

如果字串長度22bytes。倒數第二byte是'\0'，最後byte是1，存放1這個bytes，最前2 bits是用來紀錄短中長資訊。短字串本來就是00兩個bits，還是不影響。

中字串：

採用動態配置記憶體。不使用new，而是用函式庫jemalloc，這應該是目前最強的記憶體函式庫。中型字串最大254 bytes。不知道為什麼採用254，一般記憶體配置合適大小256 bytes，預留字串結尾\0，那也應該用255。函式庫卻把中型字串訂成254，原因不明。函式庫有考慮到字元大小未必是一byte。如果單字元超過 1byte，實際上字串會更短。

長字串：

超過254 bytes一律使用長字串，也是採用動態配置記憶體。但有使用Copy on write技術，多字串共用同一筆資料，有修改字串才複製。當然大家都知道多執行序使用Copy on write會出錯，所以操作字串一定要加鎖。當然C++11有導入atomic，直接使用標準函式庫即可。

不論是短中長字串，在配置記憶體的時候，能用jemalloc函式庫就用，如不能用也會視情況採用malloc/calloc/realloc三個標準函 式庫。

如資料量低於50%使用malloc。
如字串40，總空間100，這時候要串接一個200字串。就直接malloc配置新記憶體。舊字串40複製過去，再串接200字串。

如資料量高於50%使用realloc
如字串60，總空間100，這時候使用realloc配置記憶體。希望函式庫可以加大同一塊記憶體。就不用搬移60字串。

fbvector

最小會使用64 bytes，即便是空的vector，還是配置64 bytes。加大vector的策略是用1.5倍，不是2倍。

配置記憶體還是使用jemalloc函式庫。但不採用malloc/calloc/realloc。

會根據資料型態，以及當時狀況，優先使用std::memcpy，再使用std::memmove，都不行才會使用std::copy複製。當然也因為是 C++11，能用move語意就優先使用。

C++實作無序容器的方法，且可接受重複的元素

此文翻譯自
http://bannalia.blogspot.tw/2013/10/implementation-of-c-unordered_25.html

上次我們介紹了Hash Table各種流行的方法，現在我們來考慮如果元素有重複，要怎麼辦？
(unordered_multiset  , unordered_multimap)

Hash Table跟重複元素，這是兩個不同玩意，不要混在一起。兩個基本問題要解決。

• Hash的負載係數(load factor)是[所有元素]除以[所有桶子]，但因為重複元素會放在同一個桶子。必須要重新設計負載係數，不然陣列會拼命長大，結果大多數桶子都是空 的。
• 演算法複雜度跟負載係數無關，而是跟桶子裡面塞了多少東西有關。

補救負載係數(load factor)非常困難，因為規範對於負載係數定得太死。沒有多少空間可以作弊。一個細心的工程師會同時考慮最大桶子塞了多少東西以及平均每個桶子有多少 東西。我的選擇是在節點上動手腳，遍歷桶子的時候，可以快速的跳過重複的地方(規範要求相同的元素必須放在一起)。跟不重複版本比較，我們希望時間效率一 樣好！

• Dinkumware libc++ , libstdec++ -V3函式庫

對於重複元素，根本沒做任何處理。

• Boost.Unordered

有做一些設計，請看圖

桶子b2裡面有五個相同的元素。往前指的指標改成指向重複元素最後一個。利用這個反向指標，可以把五個元素視為一個大節點。插入或刪除的時候，先找到第一 個元素，利用反向指標直接跳到第五個元素。省去了掃描的麻煩。

• Boost.MultiIndex

與之前文章的設計類似，第一個節點要指回桶子，所以是特殊處理。其餘節點如果是一樣的資料，就把反向指標串好。

定一個節點叫做X，下一個節點叫做Xn，前一個節點叫做Xp。
假設有多個元素重複，全部串在一起。
第一個叫做F
第二個叫做S
倒數第二個叫做P
倒數第一個叫做L

• Sp=L
• Pn=F

第二個元素，[往前指標]會指向最後節點。
倒數第二個元素，[往後指標]會指向最初節點。

推導一些特性

• 如果Xpnn == X，那就是桶子第一個節點
• 如果Xnpn == X，那就是桶子最後節點
• 如果相同元素>=3，串成一個集團，集團第一個節點條件是Xnp != X && Xnppn == X
• 如果相同元素>=3，串成一個集團，集團第二個節點條件是Xpn != X && Xppnn == X
• 如果相同元素>=3，串成一個集團，集團倒數第二個節點條件是Xnp != X && Xnnpp == X
• 如果相同元素>=3，串成一個集團，集團倒數第一個節點條件是Xpn != X && Xpnnp == X

所有特殊位置節點都可以偵測到。整個雙向鏈結還是可以視為一個環狀。插入刪除節點都可以在O(1)。遇到資料相同的集團，可以直接跳到頭或是跳到尾，大幅 度加速。

插入元素的方法：

1. 使用Hash先找到桶子。(常數時間)
2. 檢查桶子裡面的每個元素，遇到集團的時候，只要檢查集團第一個節點即可。(桶子大小線性時間)
3. 如果元素等於某個集團，把元素加入集團內。如果整個桶子沒有相同元素，直接插入在桶子的頭端。
4. 調整桶子的指標。

遇到重複元素集團的時候，直接用Xnp就可跳到集團最尾端。若重複元素的集團長度低於3。則加速方法不適用。

刪除元素的方法：

1. 刪除鏈結裡面的元素，調整前後指標。
2. 調整桶子的指標。

事實上實作非常複雜，因為在插入刪除的時候，雙向鏈結調整指標，必須要偵測到特殊狀態的指標。但是最後效能提升，遍歷桶子不依賴桶子裡面塞了多少元素，而 是看桶子裡面有多少集團。與不重複版本比較(set/map)，可以達到同樣的效能。如果Hash演算法良好，插入就是O(1)。刪除動作不用管考慮 Hash演算法，一定是O(1)。

C++實作無序容器的方法

本文翻譯自 http://bannalia.blogspot.tw/2013/10/implementation-of-c-unordered.html
C++不叫Hash Table，而是取了一個華麗名字叫無序容器(unordered  associative  container)。從2011開始c++提供了四種無序容器。

• unordered_set  ,   unordered_map              (不可接受重複的元素)
• unordered_multiset  , unordered_multimap (可接受重複的元素)

一個常用的方法是採用單向連結。

在這種狀況下，每個桶子內部都是一個指標，指向一個單向序列。如果Hash演算法設計的好，每個鏈結都很短，插入跟刪除效率會接近O(1)。如圖所示， b1,b3只有一個元素，b2有兩個元素。簡單方便，但是在C++不合用，因為規範要求容器必須可以遍歷，必須提供一個iterator，可以讓 iterator從頭到尾掃過一遍。那要如何從b1跳到b2？最明顯的方法是繼續掃描陣列，直到下一個有裝東西的桶子。但這不可用，因為陣列愈大，掃描愈 慢。偏偏規範明定++i;效率要保持O(1)。為了符合規範，只好把所有元素都串在一起。

我們來看一些Hash Table常用的結構。加上一個模仿Boost.MutiIndex的設計。先假設所有元素都不一樣。
(unordered_multiset  , unordered_multimap以後再討論)

假設有N筆資料，陣列有B個桶子。

• Dinkumware函式庫

這是微軟Visual C++的實現方法。請看圖。

(請注意，桶子的順序不一定要跟元素順序一樣。圖片只是為了繪圖方便)

就跟你想的一樣，所有元素都串在一起。使用雙向連結。現在可以用iterator雙向訪問，代價是要多一個指標。好處是刪除元素非常容易。陣列裡面每個桶 子都有兩個指標，指向鏈結的頭跟尾。

插入元素的方法：

1. 使用Hash先找到桶子。(常數時間)
2. 元素如果重複要放棄插入，所以要掃描桶子裡面所有元素。(桶子大小線性時間)
3. 新元素插入在鏈結的頭。(常數時間)
4. 調整桶子裡面的兩個指標。(常數時間)

刪除元素的方法：

1. 使用Hash先找到桶子。(常數時間)
2. 刪除鏈結一個元素，調整前後指標。(常數時間)
3. 調整桶子裡面的兩個指標。(常數時間)

操作效率是O(1)，記憶體消耗，每個元素要兩個指標，每個桶子也要兩個指標。

• 2N+2B

看起來很好，但其實Dinkumware的方法對於刪除元素，有一個嚴重的瑕疵。

1. 使用Hash先找到桶子。(常數時間)

如果Hash函式會丟出例外，今天刪除動作就失敗了。偏偏規範又講明刪除保證要成功，而且不可以丟出任何例外。所以Dinkumware方法其實不符合規 範。

• Boost.Unordered, libc++ , libstdec++ -V3函式庫

Boost.Unordered, libc++函式庫使用類似的資料結構。但設計成單向鏈結。

1. 所有元素用單向鏈結串在一起。
2. 因為刪除動作不可以拋出異常。刪除的時候不可以呼叫Hash函式，所以只好把Hash後的數字也存起來。
3. 因為是單向鏈結，為了刪除方便。桶子裡面的指標不是指向第一筆元素，而是第一筆的前一個。所以圖片中的b2指標指向前一個的b1。

刪除元素的方法：

1. 因為節點裡面已經有Hash值，可直接定位到桶子。(常數時間，不會丟出異常)
2. 鏈結掃過一遍。(桶子大小線性時間)
3. 刪除鏈結一個元素，調整前後指標。(常數時間)
4. 調整桶子裡面的指標。(常數時間)

插入刪除都是O(1)。滿足規範。記憶消耗如下

• 2N+1B

(我們假設Hash的數字，占用大小跟一個指標一樣)

libstdec++ -V3提供了一個最佳化設計。如果Hash函式確定不會丟出異常。(有使用nonexcpt)。函式庫會標記成fast模式。節點裡面不會儲存Hash數 字。我覺得這設計有點危險。代碼裡面使用__is_fast_hash type來標記，基本型態通通設定為true。使用者自訂Hash函式預設是false，除非函式有用nonexcept，才會變成true。

不考慮最佳化的特殊機制，2N+1B似乎已經是好的設計了。但事實上還有更好的方法，不需要再增加任何記憶體。

• 簿記式的資料結構

Boost 1.56 Boost.MutiIndex裡面使用了一種全新的方式。雙向鏈結改用環狀的方式。

定一個節點叫做X，下一個節點叫做Xn，前一個節點叫做Xp。環形鏈結代表

• X = Xnp = Xpn

這個條件永遠成立。
連結往前再往後一定會回到自己。
連結往後再往前一定會回到自己。

我們現在看一下完整的示意圖


把陣列桶子也加進來，做一個小改動。

如果元素是桶子的第一個元素，Xp改成指向桶子自己。

可以導出一些規則。

• 如果Xpn != X，代表X是這個桶子的第一個元素
• 如果Xnp != X，代表X是這個桶子的最後一個元素
• 下一個元素一定可以用Xn取得。
• 前一個元素比較麻煩，如果是桶子的第一個元素，前一個元素就是Xpn，其他元素直接用Xp存取即可。

所有動作都是常數時間，我們可以把它還是當作環形鏈結。只是往前移動需要特殊處理。

刪除元素的方法：

1. 從雙向連結刪除元素，調整前後指標。(常數時間)
2. 調整桶子裡面的指標。(常數時間)

刪除元素不需要把一個桶子都翻遍，就算遇到差勁的Hash演算法也沒差。記憶體不用增加。還是2N+1B。

NAT traversal

所謂NAT traversal，又叫做NAT穿透。指的是虛擬IP如何直接連線到另一個虛擬IP。在此必須要先了解何謂NAT/虛擬IP/實體IP。

最原始的網路只有實體IP的設計，只要知道對方的IP即可傳送資料給對方。當然對方電腦有無開機，對方電腦收到之後會不會回應，我這邊無法控制。後來上網 人口增多，IP數量不夠用，IP價格也變貴。到最後NAT技術就因應而生。


NAT目的就是讓多台電腦共用一個實體IP。如圖所示，兩台電腦192開頭的IP都是虛擬IP。
在這裡的NAT設備是一台無線AP，有實體IP  114.25.8.46。對外連到伺服器202.43.195.521。

NAT設備所要做的事便是記住內部IP與外部如何對應。
192.168.0.100想要用port 2000傳訊給伺服器202.43.195.521:6000。
會先傳給無線AP，然後無線AP打開port4000對伺服器202.43.195.521:6000通訊。
伺服器回傳給無線AP的實體IP 114.25.8.46:4000。然後無線AP再把資料轉給192.168.0.100 : 2000。

對於NAT設備來講，都會要求內部電腦先對外通訊，NAT設備會開啟一個port，然後外部伺服器的訊息才可以轉發進來。

如果一台電腦，從頭到尾沒有發出任何訊息，外面的人是無法主動通訊的。

對於內部兩台電腦，無線AP會打開兩個不同的port，在此例是4000,5000。

在NAT設備底下，內部電腦無法直接得知NAT的對外IP，對外port。
外部的伺服器也無法知道NAT背後藏了幾台電腦，也無法直接得知每台電腦的虛擬IP。

NAT技術可以節省大量的實體IP，同時NAT可兼做防火牆設備，比較安全。2015目前NAT技術已經到處都在用。
在家裡架設Wifi，手機連上Wifi，會配虛擬IP。
手機4G跟基地台連線，基地台還是配虛擬IP。

但是NAT技術嚴重妨礙到一般電腦的直接通訊。對於p2p影響超大。emule/BT很難用，通常可以連線的點會非常少。
也妨礙到網路電話VOIP使用，兩支手機不能直接連線，很麻煩。

分析一下各種狀況
1.雙方均是實體IP，只要知道對方IP即可通訊。
2.一方實體，一方虛擬。由虛擬IP先發起通訊即可。
3.兩台電腦都是虛擬IP，連到同一台NAT設備。可直接使用虛擬IP通訊。
4.兩台電腦都是虛擬IP，連到不同NAT設備。無法單純直接連線。

本文要探討的便是最麻煩的情況4。此技術就是所謂的NAT traversal。

當然可以用一種最簡單的方法，就是中間利用一台伺服器轉發資料。但是伺服器網路頻寬要錢。更何況網路電話/p2p軟體傳輸資料量大。伺服器錢誰要出？

由於NAT設備的轉發資料規則，並沒有國際規範。完全由廠商自由心證。故這世界上沒有完美的NAT traversal。兩個虛擬IP未必能成功建立連線。

NAT設備的行為大致分成四種。

1.Full cone NAT
NAT設備對於同一台內部電腦，永遠打開同一個port。例如說port 5000。
port打開之後，任何外部的人傳訊到port 5000，都會轉發給同一台內部電腦。

2.Address-Restricted cone NAT
NAT設備對於同一台內部電腦，永遠打開同一個port。例如說port 5000。
內部電腦傳訊給伺服器202.43.195.521:6000。
伺服器202.43.195.521可以用任何port傳訊到NAT設備的port 5000，都會轉發給同一台內部電腦。

3.Port-Restricted cone NAT
NAT設備對於同一台內部電腦，永遠打開同一個port。例如說port 5000。
內部電腦傳訊給伺服器202.43.195.521:6000。
伺服器202.43.195.521只能用自己的port 6000傳訊到NAT設備port 5000，才會轉發給同一台內部電腦。

4.Symmetric NAT
內部電腦對外連線，根據不同伺服器IP，NAT設備會打開不同的port。
例如說：

內部電腦傳訊給伺服器202.43.195.521:6000。
NAT打開port 4000。伺服器回傳資料必須用port 6000回傳給NAT的port 4000，才可正確送達NAT背後的電腦。
內部電腦傳訊給伺服器202.43.195.522:7000。
NAT打開port 5000。伺服器回傳資料必須用port 7000回傳給NAT的port 5000，才可正確送達NAT背後的電腦。

此種情況是最困難的NAT。

電腦連上網路之後，無法直接判斷自己是否在NAT底下。也無法知道NAT的對外IP對外port。必須要跟伺服器通訊，由伺服器告知。而且需要兩台伺服器 幫忙。兩台伺服器需要有不同的IP。

內部電腦定為A，兩台伺服器分別是S1,S2

流程如下：

A傳訊給S1，S1回傳自己看到的IP,port。
A收到後若是IP,port均一致，代表A是實體IP。

A傳訊給S1，要求S1找另一台伺服器(S2)傳訊給A。且S2需用不同的port傳訊。
若A可以收到S2的訊息，代表A在Full cone NAT底下。

A傳訊給S2，S2回傳自己看到的IP,port。
若兩個伺服器回傳的port不一樣，代表A在Symmetric NAT底下。

A傳訊給S1，要求S1用不同的port回傳。
若A收到，代表A在Address-Restricted cone NAT底下。
若收不到，代表A在Port-Restricted cone NAT底下。

NAT traversal基本原理

兩台虛擬IP要直接連線，還是需要伺服器幫忙握手。兩台電腦都連到同一台伺服器。因為伺服器是實體IP，連線到伺服器不成問題。然後伺服器互相告知AB的 對外IP,port。這時候AB都知道對方的IP,port了。

1.使用UDP協定：A發訊息給114.25.8.47:3000。此訊息會在NAT設備B被擋掉。無所謂，此步驟目的是打開NAT A的通道。
2.使用TCP協定：A發訊息給伺服器，告知我已經打開通道。
3.使用TCP協定：伺服器發訊息給B，告知B可以開始傳輸。
4.使用TCP/UDP協定：B發訊息給114.25.8.46:2000

四個步驟全部做完，AB便可直接連線。AB互相連線的時候是傳訊給NAT的對外IP,port。不需要知道對方的虛擬IP。

TCP協定需要三次握手，UDP不用。
與伺服器本來就可以直接連線，可以通通用TCP沒問題。

步驟2因為連不到電腦B，所以一定要用UDP。
步驟4可成功建立連線，故TCP/UDP均可。

此方法對於這三種NAT通通都適用。不論AB分別是哪種NAT，都可用此方法。
Full cone NAT
Address-Restricted cone NAT
Port-Restricted cone NAT

當然聰明的你已經猜到，如果雙方都是Port-Restricted cone NAT這4個步驟才要全部都做。如果是比較寬鬆的兩種NAT。可以省略一些步驟。

再來是最麻煩的Symmetric NAT 。因為Symmetric NAT 的port會變化，必須要猜測下次打開port，猜中才可傳輸。實務上NAT por可能是規律變化，每次都+1而已。所以很好猜！

電腦要與兩台伺服器S1,S2通訊，利用兩台伺服器的回傳訊息，可以知道NAT兩次對外傳訊的對外port，利用這點來猜下次打開port。
服器互相告知AB的對外IP。也互相告知「對方下次打開的port」。

以圖片的範例來看

A傳訊給S1使用port 2000
A傳訊給S2使用port 2001
那A下次會打開2002

B傳訊給S1使用port 3000
B傳訊給S2使用port 3001
那B下次會打開3002

流程如下：
1.使用UDP協定：A發訊息給114.25.8.47:3002。此訊息會在NAT設備B被擋掉。無所謂，此步驟目的是打開NAT A的通道。
2.使用TCP協定：A發訊息給伺服器，告知我已經打開通道。
3.使用TCP協定：伺服器發訊息給B，告知B可以開始傳輸。
4.使用TCP/UDP協定：B發訊息給114.25.8.46:2002

四個步驟是一樣的，只是port有差異而已。

實務上有個變形方法，步驟1,4，沒人規定只能送一次訊息。
步驟1除了送出114.25.8.47:3002，也可以順便猜測一下其他的port，例如說把3002正負500的port都試過一遍。(使用UDP)
步驟4除了送出114.25.8.46:2002，也可以順便猜測一下其他的port，例如說把2002正負500的port都試過一遍。(使用UDP)

當然port只有65535個，如果你不在乎速度很慢，可以全部都試過一遍。

那如果Symmetric NAT的port變化是不規律的，port也猜不到，那就真的沒轍！只能回到最笨的方法，所有資料都利用伺服器轉送。