你在閱讀源代碼或設計文檔時，看到哪些驚艷的技巧？

你在閱讀源代碼或設計文檔時，看到哪些驚艷的技巧？

一些代碼，或者是高明的設計思想，或者是別的。

讓你拍案叫絕那種。

似乎看到了另外一片天地，讓你感嘆作者的層次之高。

---

提兩個C語言里實現列表用到的技巧。會用的人可能會覺得很平常，但是第一次看到的時候還是覺得很厲害的：

1. 兩級指針：兩級指針要怎麼用呢？我們先來看一下大部分正常人實現列表的方法：

   //定義鏈表節點struct
struct node {
data_type data;
struct node *next, *prev;
}*head = NULL;
//然後插入一個節點就要這樣：
void insert(struct node *new) {
new-&>next = head;
if (head)
head-&>prev = new;
new-&>prev = NULL;
head = new;
}
//刪除就要這樣
void remove(struct node *delete) {
if (delete == head) {
head = head-&>next;
head-&>prev = NULL;
} else {
delete-&>prev-&>next = delete-&>next;
if (delete-&>next)
delete-&>next-&>prev = delete-&>prev;
}
free(delete);
}


   有沒有覺得remove里這個if很麻煩？有沒有辦法不用條件語句就處理所有情況？請看：

   //這一次，我們把節點定義成這樣
struct node {
data_type data;
struct node *next, **prev;
}*head;

   //然後insert就變成了這樣
   void insert(struct node *new) {
   new-&>prev = head;
   new-&>next = head;
   if(head)
   head-&>prev = new-&>next;
   head = new;
   }

   //刪除就成了這樣
void remove(struct node *delete) {
*delete-&>prev = delete-&>next;
if (delete-&>next)
delete-&>next-&>prev = delete-&>prev;
free(delete);
}


   這裡給的例子不是很全，事實上這種做法可以在多種鏈表操作里簡化對head的判斷。至於這個方法是怎麼工作的，可以自己想想，並不難理解。

   //同樣的技巧還能用在單鏈表的刪除節點上
//Before
struct node *now, *prev;
for(now = head; now != NULL; now = now-&>next){
if(now是要刪的節點){
if(now == head)
head = now-&>next;
else
prev-&>next = now-&>next;
break;
}
prev = now;
}
//After
struct list **nowp;
for(nowp = head; *nowp != NULL; nowp = (*nowp)-&>next){
if((*nowp)是要刪的節點){
*nowp = (*nowp)-&>next;
break;
}
}


   Source: &

2. container_of：正常人都知道，C不是面向對象語言，沒有模板之類的東西。那麼我們還有辦法實現一套「通用」的鏈表API嗎？答案當然是能——不要小看了C語言的黑魔法。
   注意到，操作鏈表的函數做的只不過是擺弄next，prev兩個指針而已，那麼我們只要把這部分數據結構獨立出來就好了。

   struct list_head {
struct list_head *next, **prev;
};
//然後要用到鏈表的地方：
struct some_node {
data_type data;
struct list_head list;
};
//如果你要把一個struct some_node插入鏈表，你給鏈表API傳的參數長這樣：
int some_function() {
struct some_node n;
...
insert(n-&>list);
}


   但是有一個明顯的問題，這樣你從鏈表中拿出來的東西只可能是struct list_head *類型的，怎麼把它還原到struct some_node呢？

   //舉個例子
struct list_head *list_ptr = first(head);


   注意到其實這個struct list_head *的指針指向的是struct some_node中間的一個位置，只要能知道偏移量，我們就能得到struct some_node的指針。當然，手算這個偏移量是要死人的，於是就有了這個：

   #define container_of(ptr, type, member) ({
const typeof( ((type *)0)-&>member ) *__mptr = (ptr);
(type *)( (char *)__mptr - offsetof(type,member) );})


   這個宏的意思是說，給定ptr是指向type中間一個member的指針，獲取type本身的指針。其中的核心是offsetof這個宏，功能是取得type中member的offset，定義是這樣的：

   #define offsetof(st, m) ((size_t)(((st *)0)-&>m))


   有了這一組宏，你就可以這麼寫：

   struct some_node *n = container_of(list_ptr, struct some_node, list);


   來獲取原本的指針了。

   Source: Linux/include/linux/list.h

現在你們知道C是一個充滿閃(hei)光(mo)點(fa)的語言了吧……

---

1. 環形隊列的長度 在 java.util.concurrent 中 所有基於數組實現的環形隊列默認的長度都是8192 擴展後也是2的冪次方 這樣的話Round Robin 就不需要用 "%" 直接 ""即可 另外替換內容永遠都是基於Unsafe實現保證線程安全 計算偏移量的步驟都讓我很頭暈 而對開發者都是習以為常的..
2. 節約空間的存儲設計 最近在寫一個RDB(Redis的dump文件)逆序列化的東西 看到一些作者節約存儲空間的方式 比如 大多數情況下 key或value的長度都能維持在60左右 所以作者用來存儲內容長度的位元組默認只用6bit 另外2bit做標記 如果超出6bit能表達的長度 則用14bit表達 如果14bit表達不了 則索性用32bit表達 佔用位元組分別是 1、2、5(第一個位元組用來標記接下來4個位元組是實際長度) 根據內容的不同 存儲的方式也不一樣 比如普通的String類型 如果裡面的字元全部都是數字 他會轉換成整型去存 內容有一定長度後 進行lzf壓縮 Redis的rdb還是相對簡單的 沒辦法想像寫mysql dump文件的逆序列化的人有多蛋疼

栗子還有很多 他們的代碼默認不是我看到的樣子 而是經過反覆推敲後 得出來的東西 能感覺到作者在為了某些事情做取捨 比如讀多寫少用COW 棄用Bucket鎖 再比如尋找一個字元究竟從前向後遍歷好 還是從後向前遍歷好 再比如要不要背棄規範做一些違規的事情(看Java集合類庫里一堆針對RandomAccess做的判斷 在方法內部根據具體類型走分支我個人覺得是不美麗的...)

持續的調整自己的代碼 讓其作用更加明確 這大概就是開發過程令人著迷的地方吧

---

Facebook的C++基礎庫folly folly/Conv.md at master · facebook/folly · GitHub

出自Andrei Alexandrescu手的Conv組件，一個to&<&>函數hold住所有基本類型包括string的轉換：

auto s = to&(1024);
auto n = to&("1024");
auto f = to&("3.14");


還能完成字元串拼接:

auto text = to&(12, "12", 12.0);


廢話少說，放碼來：

folly/Conv.h at master · facebook/folly · GitHub

---

nginx在判斷http method的時候用的不是字元串比較，而是整數比較。

比如「POST」，一般的寫法是用strcmp，就會牽扯到4次char的比較。

而nginx把接受到的method轉化為一個int，那麼4次比較就可以轉化為1次比較。

具體代碼如下：

#define ngx_str3Ocmp(m, c0, c1, c2, c3)
*(uint32_t *) m == ((c3 &<&< 24) | (c2 &<&< 16) | (c1 &<&< 8) | c0)

update ----

如果大家對nginx里的各種奇技淫巧感興趣的話，我可以繼續補充下去。

---

之前一直苦於lua沒有自帶的四捨五入函數，每次都要math.modf()一下判斷是否&>0.5，覺得寫的很臃腫。直到看到了這一段代碼……

num = math.floor(num+0.5)

瞬間覺得智商被爆……

---

Hacking Strings Redis 字元串的實現， 這篇講述這種技巧： Struct hack 也談C語言的Struct Hack

---

泛型技巧系列：類型字典和Type Traits

話說，這個不是看源碼看到的，是看博客。

---

More C++ Idioms/Copy-and-swap。優雅的 exception safety。核心思想就是造好一個新的，然後引用到這個新的。稍微進一步就是 MVCC 了。

---

看lua的源碼的時候有這段代碼：

union luai_Cast { double l_d; long l_l; };

#define lua_number2int(i,d)

{ volatile union luai_Cast u; u.l_d = (d) + 6755399441055744.0; (i) = u.l_l; }

也就是double轉int.

---

SICP中的定義car, cdr方法

1.

(define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "Argument error")))))

(define (car z) (z 0))
(define (cdr z) (z 1))


2.

(define (cons x y)
(lambda (m) (m x y)))

(define (car z)
(z (lambda (p q) p)))

(define (cdr z)
(z (lambda (p q) q)))


反正開始看的時候是被驚艷了.

還有set的定義. 用函數定義, 而不是使用數據結構.

SICP上當然還有很多好玩的..

---

C++判斷當兩個int變數有且僅有一個為真時執行某操作的寫法就很驚艷

---

doug lea 在 juc 中用 lock free 實現的 aqs

---

難道沒人提這個炸彈？

:(){ :|: };:

---

再加一條，私有純虛函數，誰用誰知道。但是真不是一般的c++碼農會考慮的……

作為一個平時寫java 寫C++，被OOP浸到骨子裡的人，看到別人寫的C代碼，真的超級佩服。

不管是用函數指針來作為struct的參數來仿OOP，還是純過程化，卻寫成所有函數都可以重入，都互相不會影響，每一次看到都被震撼。

忽然看到別人有人都說異或來交換兩個數的方法，這個……沒感覺多神啊……不是很明顯么。

那麼大家會覺得並查集很神么？神一樣的數據結構。

---

以前自己讀完python文檔幫別人寫作業時，寫得跟c++一樣，格式很工整，注釋很詳細。

後來去stackoverflow，以及刷leetcode看別人的代碼時，卧槽，卧槽卧槽卧槽卧槽卧槽，你們寫得怎麼都這麼狂拽酷炫吊炸天！！！可惜我怎麼也寫不出來，現在寫得依然跟C++一樣啰嗦冗長。

我到現在依然覺得，每個寫Python的代碼都很驚艷！！！你們到底是有多懶打字呀！！！

---

1、獲取struct的entry

#define list_entry(ptr, type, member) /

((type *)((char *)(ptr)-(unsigned long)(((type *)0)-&>member)))


已知結構體的某成員地址，可獲取這個結構體的起始地址。

比如定義下面的結構體：

struct student
{
int name;
vector&* grade;
}


比如我知道s.grade,帶入到宏，得到：

((student *)((char *)(s.grade)-(unsigned long)(((student *)0)-&>grade)))


2、多級指針

忘了在哪看到的了。

定義如下結構體：

typedef struct node{
struct node * next;
int a;
int b;
} Node;

Node a;
Node ** phead = a.next;
...（創建一系列節點）


*phead就是第一個節點

**phead就是第二個節點

***phead就是第三個節點。。。

看起來還是比較有意思的。。

---

Redis的assert，fail時強行造segment fault

*((char*)-1) = "x";


---

define private public

測試私有介面時有這句很方便...

---

STL rotate：

template &
void rotate (ForwardIterator first, ForwardIterator middle,
ForwardIterator last)
{


ForwardIterator next = middle;


while (first!=next)
{


swap (*first++,*next++);


if (next==last) next=middle;


else if (first==middle) middle=next;


}


}


---

Protobuffer源碼中uint32轉float的實現：

inline float WireFormatLite::DecodeFload(uint32 value) {
union {float f; uint32 i;};
i = value;
return f;
}


---

推薦閱讀：