溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章給大家分享的是有關MYSQL INNODB中通用雙向鏈表怎么實現的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。
源碼在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 = &t;//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;
不解釋了。
從整個鏈表的實現來看仿函數是其中的一個重點，他是一個橋梁其主要分為兩步：
1、初始化指向一個類的成員函數，這是指定他的類型，獲得他的偏移量
2、初始化指向某一個元素，這是獲得他的內存空間地址基地址
有了基地址+偏移量就能夠找到實際的元素了。
感謝各位的閱讀！關于“MYSQL INNODB中通用雙向鏈表怎么實現”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
