Linux內(nèi)核中的紅黑樹

hk2305621

struct rb_root只是struct rb_node*的一個(gè)包裝，這樣做的好處是看起來(lái)不用傳遞二級(jí)指針了。不錯(cuò)，很簡(jiǎn)單。再看一下下面幾個(gè)重要的宏，細(xì)心的你一定會(huì)發(fā)現(xiàn)，rb_parent_color其實(shí)沒(méi)那么簡(jiǎn)單，Andrea Arcangeli在這里使用了一個(gè)小的技巧，不過(guò)非常棒。正如名字所暗示，這個(gè)成員其實(shí)包含指向parent的指針和此結(jié)點(diǎn)的顏色！它是怎么做到的呢？很簡(jiǎn)單，對(duì)齊起了作用。既然是sizeof(long)大小的對(duì)齊，那么在IA-32上，任何rb_node結(jié)構(gòu)體的地址的低兩位肯定都是零，與其空著不用，還不如用它們表示顏色，反正顏色就兩種，其實(shí)一位就已經(jīng)夠了。

重點(diǎn)看到了這里.  之前不知道的.

sizeof(long)  使指針的低兩位在 IA-32 上為0. 那么其他的體系結(jié)構(gòu)上是否也符合呢？ 大端與小端都OK？ 還請(qǐng)解惑. 謝謝！

ps：
在那里都可以看到 LZ(GodBach) 的帖子和回帖. 強(qiáng)大的存在.

Godbach

回復(fù) 71# hk2305621

sizeof(long)  使指針的低兩位在 IA-32 上為0. 那么其他的體系結(jié)構(gòu)上是否也符合呢？ 大端與小端都OK？ 還請(qǐng)解惑. 謝謝！

這個(gè)地方感覺(jué)應(yīng)該和體系結(jié)構(gòu)無(wú)關(guān)的吧，作者代碼實(shí)現(xiàn)就完全沒(méi)有涉及到 ARCH，而且這些接口在內(nèi)存管理等地方都直接調(diào)用了。
   

hk2305621

回復(fù) 72# Godbach

不過(guò)想想也是, 大小端是在內(nèi)存中的存儲(chǔ)形式, 對(duì)于 long 在程序中的表現(xiàn)而言, 最低位還是 long & 0x01. 和大小端無(wú)關(guān)了.

斑竹分享下你的 Linux 進(jìn)階道路吧, 我最近比較迷茫. 先謝謝了！呵呵