MYSQL INNODB中通用雙向鏈表怎么實現

156次閱讀

共計 6482 個字符，預計需要花費 17 分鐘才能閱讀完成。

這篇文章給大家分享的是有關 MYSQL INNODB 中通用雙向鏈表怎么實現的內容。丸趣 TV 小編覺得挺實用的，因此分享給大家做個參考，一起跟隨丸趣 TV 小編過來看看吧。

源碼在 Ut0lst.h 中
注意：這里我將鏈表中的實際的串聯的數據叫做數據類比如：lock_t、mem_block_t

鏈表作為一種的非常重要的數據結構，在任何地方都會用到，這里簡單解釋一下 innodb 雙向
鏈表的實現，讓我們來看看 innodb 鏈表設計的魅力：
經常在某些結構體中看到
UT_LIST_BASE_NODE_T(mem_block_t) base;
UT_LIST_NODE_T(mem_block_t) list;

作為最為基本的一種的數據結構 innodb 中實現得比較精妙涉及到重要的 4 個 C ++ 知識點：
1、仿函數
2、類成員指針
3、類模板
4、函數重載

簡單的說仿函數是調用的時候類似函數調用的形式的類，類成員指針并非一個真正意義上的
指針，而是指向特定類對象相對位置的一個偏移量。
比如如下就是一個仿函數類：

點擊 (此處) 折疊或打開

template typename T

class ShowElemt

{

public:

ShowElemt()

{

n = 0;

}

void operator()(T t)

{

n++;

cout t

}

void printCount()

{

cout n endl;

}

public:

int n;

};

下面是一個簡單的類成員指針使用, 他初始化分為 2 步在最后給出.：

點擊 (此處) 折疊或打開

#include iostream

using namespace std;

class T

{

public:

typedef int uint;

public:

int a;

int b;

};

int main21(void)

{

T t;

int T::* t1 = T::b;//1、成員函數指針初始化為指向類 T 成員 b 的一個指針(成員函數指針指向的是偏移量)

T* t2 = //t2 一個指向類變量 t 的指針

t.*t1 = 10;//2、初始化 t 的 t1 類成員指針指向的內存空間值為 10，實際上就是 t.b=10

cout t.*t1 t2- *t1 endl;// 相同輸出一個采用對象一個采用對象指針

{

T t3;

t3.a=300;

t.*t1 = t3.a; // 他就是擁有實際內存空間的變量了

}

模板和函數重載就沒有什么好說的了。

接下來我們看看 UT_LIST_BASE_NODE_T、UT_LIST_NODE_T 分別代表了什么
實際上他們都是宏定義：
#define UT_LIST_BASE_NODE_T(t) ut_list_base t, ut_list_node t::*
#define UT_LIST_NODE_T(t) ut_list_node
那么他們的類型出來了實際上就是：
ut_list_base 和 ut_list_node，我們知道在設計鏈表的時候，通常有一個鏈表頭數據結構，用來存儲
比如鏈表中總共多少元素，鏈表頭，鏈表尾等等特征，但是之前還是想來看看 ut_list_node 鏈表結構體:

點擊 (此處) 折疊或打開

template typename Type

struct ut_list_node {

Type* prev; /*! pointer to the previous

node, NULL if start of list */

Type* next; /*! pointer to next node,

NULL if end of list */

void reverse()

{

Type* tmp = prev;

prev = next;

next = tmp;

}

};

非常簡單沒有包含任何固定的數據信息，只是包含了鏈表的前后指針，同時包含了一個成員函數 reverse，作為
實現鏈表反轉的基礎，這里也注意到由于沒有包含任何數據信息成員，做到了鏈表和具體數據類之間的剝離。
在鏈表設計的時候通常有 2 種方式：
1、鏈表結構包含數據類
2、數據類包含鏈表結構
這里 INNODB 使用了后者，讓鏈表的通用更加方便

再來看看 ut_list_base 鏈表頭結構體:

點擊 (此處) 折疊或打開

template typename Type, typename NodePtr

struct ut_list_base {

typedef Type elem_type;

typedef NodePtr node_ptr;

typedef ut_list_node Type node_type;

ulint count; /*! count of nodes in list */

elem_type* start; /*! pointer to list start,

NULL if empty */

elem_type* end; /*! pointer to list end,

NULL if empty */

node_ptr node; /*! Pointer to member field

that is used as a link node */

#ifdef UNIV_DEBUG

ulint init; /*! UT_LIST_INITIALISED if

the list was initialised with

UT_LIST_INIT() */

#endif /* UNIV_DEBUG */

void reverse()

{

Type* tmp = start;

start = end;

end = tmp;

}

};

這里再來解釋一下：
在類的內部進行了 3 種類型的 typedef，分別是：
typedef Type elem_type;: 具體的類型比如 lock_t、mem_block_t。
typedef NodePtr node_ptr; : 和模板聲明中的 ut_list_node t::* 聯合起來看，實際上他是一個
類成員指針，他指向的會是特定數據類比如 lock_t、mem_block_t 中特定的一個成員，這個成員一定是
ut_list_node 類型的也就是 UT_LIST_NODE_T(t) 類型的，其中 t 當然也就是數據類本身，這也是整個
設計中的精髓。
typedef ut_list_node node_type; : 和前面的 ut_list_node 聯合起來看，就能知道
它是一個特定類型的節點類型比如 lock_t、mem_block_t。
剩下的就是類成員了：
ulint count;: 鏈表中的有多少元素
elem_type* start;: 具體數據類元素的起始位置指針
elem_type* end;: 具體數據類元素的最后位置指針
node_ptr node;: 這里使用了剛才說的 typedef NodePtr node_ptr 來定義成員 node，那么我們可以猜測他是指向
特定數據類對象中鏈表結構元素的成員指針，其實的確如此：
如 lock_t

點擊 (此處) 折疊或打開

/** Lock struct; protected by lock_sys- mutex */

struct lock_t {

trx_t* trx; /*! transaction owning the

lock */

UT_LIST_NODE_T(lock_t)

trx_locks; /*! list of the locks of the

transaction */

……….

剩下還有一個關鍵的仿函數：

點擊 (此處) 折疊或打開

template typename Type // 一元謂詞仿函數

struct GenericGetNode {

typedef ut_list_node Type node_type;

GenericGetNode(node_type Type::* node) : m_node(node) {}

node_type operator() (Type elem)

{

return(elem.*m_node);

}

node_type Type::*m_node;

};

這里解釋一下這個仿函數類：
typedef ut_list_node node_type; 和前面的 ut_list_node 聯合起來看，就能知道
它是一個特定類型的節點類型比如 lock_t、mem_block_t。
GenericGetNode(node_type Type::* node) : m_node(node) {} : 有參構造函數，通過輸入一個指向特定數據節點的
ut_list_node(UT_LIST_NODE_T(t)) 成員的值 node 進行初始化元素 m_node。但是這里只是指向了類成員有了偏移量，但是并沒有初始化內存空間，具體的初始化
內存空間在實現函數中。
node_type operator() (Type elem) : 這里就是仿函數，重載了 () 運算符，接受一個特定節點類型比如 lock_t、mem_block_t
的一個引用輸入，然后返回一個類成員指針的引用，如果是 lock_t 那么返回的將是 trx_locks，那么我們就能夠使用它
trx_locks.prev
在鏈表實現中中包含很多方法大概如下：
UT_LIST_INIT: 初始化一個鏈表、是一個宏定義
ut_list_prepend: 頭插法插入鏈表
ut_list_append: 尾插法插入鏈表
ut_list_insert: 將某個元素插入到某個元素之后
ut_list_remove: 刪除某個節點
ut_list_reverse: 鏈表反向
ut_list_move_to_front: 將指定的元素放到頭部
好了到這里我們解釋了關鍵鏈表數據結構下面我們通過一段 innodb 代碼來分析一下，這里我們
我們只是關注鏈表操作所以如下，這里涉及到初始化和尾插法加入鏈表
UT_LIST_BASE_NODE_T(lock_t) old_locks;
UT_LIST_INIT(old_locks, lock_t::trx_locks);
lock_t* old_lock = lock_rec_copy(lock, heap);
UT_LIST_ADD_LAST(old_locks, old_lock);

我們來具體解釋一下步驟：
1、UT_LIST_BASE_NODE_T(lock_t) old_locks; 定義 old_locks 為一個鏈表頭對象。
2、UT_LIST_INIT(old_locks, lock_t::trx_locks); 進行初始化，這里 UT_LIST_INIT 是一個宏

點擊 (此處) 折疊或打開

#define UT_LIST_INIT(b, pmf) \

{ \

(b).count = 0; \

(b).start = 0; \

(b).end = 0; \

(b).node = pmf; \

UT_LIST_INITIALISE(b); \

}

非常簡單設置全部指針都是 NULL，并且初始化 node 類成員指針指向 lock_t::trx_locks。
3、lock_t* old_lock = lock_rec_copy(lock, heap); 我們先不深究這里面，但是他肯定是一種拷貝，完成后他返回一個 lock_t* 的指針
old_lock
4、接下來就是加入節點，這是一個重頭戲，會應用到前面全部的知識。
UT_LIST_ADD_LAST(old_locks, old_lock);
實際上他是一共宏定義
#define UT_LIST_ADD_LAST(LIST, ELEM) ut_list_append(LIST, ELEM)
在經過函數重載調用后實際上他會調用

點擊 (此處) 折疊或打開

template typename List

void

ut_list_append(

List list,

typename List::elem_type* elem)

{

ut_list_append(

list, elem,

GenericGetNode typename List::elem_type (list.node));

}

然后調用：

點擊 (此處) 折疊或打開

template typename List, typename Functor

void

ut_list_append(

List list,

typename List::elem_type* elem,

Functor get_node)

{

typename List::node_type node = get_node(*elem);

UT_LIST_IS_INITIALISED(list);

node.next = 0;

node.prev = list.end;

if (list.end != 0) {

typename List::node_type base_node = get_node(*list.end);

ut_ad(list.end != elem);

base_node.next = elem;

}

list.end = elem;

if (list.start == 0) {

list.start = elem;

}

++list.count;

}

詳細描述一下：
首先看一下：
template
void
ut_list_append(
List list,
typename List::elem_type* elem)
{
ut_list_append(
list, elem,
GenericGetNode(list.node));
}
這里 list 就是我們初始化的 old_locks 類型為 UT_LIST_BASE_NODE_T(lock_t)，elem 就是我們 copy 出來的一個
指向 lock_t* 的指針 old_lock 其類型當然也就是 UT_LIST_BASE_NODE_T(lock_t)::elem_type* 類型實際上就是
lock_t* 類型繞了一大圈。
而 GenericGetNode(list.node)雖然很長但是我們可以清楚的明白他是
調用的構造函數，生成一個匿名對象，typename List::elem_type 是用到了 ut_list_base 定義的類型
elem_type 就是一個 UT_LIST_BASE_NODE_T(lock_t)::elem_type 類型其實就是 lock_t 類型，而 list.node
實際上就是 node_ptr 類型，初始化已經被定義為 lock_t::trx_locks

接下來由于函數重載的函數調用了
ut_list_append(
List list,
typename List::elem_type* elem,
Functor get_node)
我們來看看。
typename List::node_type node = get_node(*elem);
將 List(old_locks)中的 node 成員函數指針進行初始化他指向了 old_lock 這是結構實際鏈表結構的位置。
接下來 node.next nodex.prev 將是可用的了
node.next = 0;
node.prev = list.end;
將節點的后指針設置為 NULL，前指針當然設置為 list.end 的位置
這里也看到他確實放到末尾
if (list.end != 0) {
typename List::node_type base_node = get_node(*list.end);
ut_ad(list.end != elem);
base_node.next = elem;
}
如果鏈表不為空，這里再次獲得 end 節點的位置存放到 base_node 中，
當然也就要將 base_node.next 設置為我們新加入的節點的指針。
list.end = elem;
將鏈表頭結構的 end 指針放到我們新插入的 elem 中。
if (list.start == 0) {
list.start = elem;
}
如果 list 的 start 指針為空代表鏈表為空，那么還需要將 start 指針指向 elem
最后
++list.count;
不解釋了。