MYSQLINNODB中通用雙向鏈表怎么實(shí)現(xiàn)

這篇文章給大家分享的是有關(guān)MySQL INNODB中通用雙向鏈表怎么實(shí)現(xiàn)的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。

從策劃到設(shè)計(jì)制作，每一步都追求做到細(xì)膩，制作可持續(xù)發(fā)展的企業(yè)網(wǎng)站。為客戶提供成都做網(wǎng)站、網(wǎng)站制作、網(wǎng)站策劃、網(wǎng)頁(yè)設(shè)計(jì)、域名與空間、網(wǎng)站空間、網(wǎng)絡(luò)營(yíng)銷、VI設(shè)計(jì)、 網(wǎng)站改版、漏洞修補(bǔ)等服務(wù)。為客戶提供更好的一站式互聯(lián)網(wǎng)解決方案,以客戶的口碑塑造優(yōu)易品牌,攜手廣大客戶,共同發(fā)展進(jìn)步。


源碼在Ut0lst.h中
注意：這里我將鏈表中的實(shí)際的串聯(lián)的數(shù)據(jù)叫做數(shù)據(jù)類比如：lock_t、mem_block_t

鏈表作為一種的非常重要的數(shù)據(jù)結(jié)構(gòu)，在任何地方都會(huì)用到，這里簡(jiǎn)單解釋一下innodb雙向
鏈表的實(shí)現(xiàn)，讓我們來(lái)看看innodb鏈表設(shè)計(jì)的魅力：
經(jīng)常在某些結(jié)構(gòu)體中看到
UT_LIST_BASE_NODE_T(mem_block_t) base;
UT_LIST_NODE_T(mem_block_t) list; 

作為最為基本的一種的數(shù)據(jù)結(jié)構(gòu)innodb中實(shí)現(xiàn)得比較精妙涉及到重要的4個(gè)C++知識(shí)點(diǎn)：
1、仿函數(shù)
2、類成員指針
3、類模板
4、函數(shù)重載

簡(jiǎn)單的說(shuō)仿函數(shù)是調(diào)用的時(shí)候類似函數(shù)調(diào)用的形式的類，類成員指針并非一個(gè)真正意義上的
指針，而是指向特定類對(duì)象相對(duì)位置的一個(gè)偏移量。
比如如下就是一個(gè)仿函數(shù)類：

點(diǎn)擊(此處)折疊或打開(kāi)

  1. template <typename T>

  2. class ShowElemt

  3. {

  4. public:

  5.     ShowElemt()

  6.     {

  7.         n = 0;

  8.     }

  9.     void operator()(T &t)

  10.     {

  11.         n++;

  12.         cout << t << " ";

  13.     }

  14.     void printCount()

  15.     {

  16.         cout << n << endl;

  17.     }

  18. public:

  19.     int n;

  20. };

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

點(diǎn)擊(此處)折疊或打開(kāi)

  1. #include<iostream>

  2. using namespace std;

  4. class T

  5. {

  6.   public:

  7.   typedef int uint;

  8.   public:

  9.           int a;

  10.           int b;

  11. };

  13. int main21(void)

  14. {

  15.         T t;

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

  17.         T* t2 = &t;//t2一個(gè)指向類變量t的指針

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

  19.         cout<<t.*t1<<" "<<t2->*t1<<endl;//相同輸出一個(gè)采用對(duì)象一個(gè)采用對(duì)象指針

  20.         {

  21.                 T t3;

  22.                 t3.a=300;

  23.                 t.*t1 = t3.a; //他就是擁有實(shí)際內(nèi)存空間的變量了

  24.         }

  25. }

模板和函數(shù)重載就沒(méi)有什么好說(shuō)的了。

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

點(diǎn)擊(此處)折疊或打開(kāi)

  1. template <typename Type>

  2. struct ut_list_node {

  3.     Type*        prev;            /*!< pointer to the previous

  4.                         node, NULL if start of list */

  5.     Type*        next;            /*!< pointer to next node,

  6.                         NULL if end of list */

  8.     void reverse()

  9.     {

  10.         Type*    tmp = prev;

  11.         prev = next;

  12.         next = tmp;

  13.     }

  14. };

非常簡(jiǎn)單沒(méi)有包含任何固定的數(shù)據(jù)信息，只是包含了鏈表的前后指針，同時(shí)包含了一個(gè)成員函數(shù)reverse，作為
實(shí)現(xiàn)鏈表反轉(zhuǎn)的基礎(chǔ)，這里也注意到由于沒(méi)有包含任何數(shù)據(jù)信息成員，做到了鏈表和具體數(shù)據(jù)類之間的剝離。
在鏈表設(shè)計(jì)的時(shí)候通常有2種方式：
1、鏈表結(jié)構(gòu)包含數(shù)據(jù)類
2、數(shù)據(jù)類包含鏈表結(jié)構(gòu)
這里INNODB使用了后者，讓鏈表的通用更加方便

再來(lái)看看ut_list_base 鏈表頭結(jié)構(gòu)體:

點(diǎn)擊(此處)折疊或打開(kāi)

  1. template <typename Type, typename NodePtr>

  2. struct ut_list_base {

  3.     typedef Type elem_type;

  4.     typedef NodePtr node_ptr;

  5.     typedef ut_list_node<Type> node_type;

  7.     ulint        count;            /*!< count of nodes in list */

  8.     elem_type*    start;            /*!< pointer to list start,

  9.                         NULL if empty */

  10.     elem_type*    end;            /*!< pointer to list end,

  11.                         NULL if empty */

  12.     node_ptr    node;            /*!< Pointer to member field

  13.                         that is used as a link node */

  14. #ifdef UNIV_DEBUG

  15.     ulint        init;            /*!< UT_LIST_INITIALISED if

  16.                         the list was initialised with

  17.                         UT_LIST_INIT() */

  18. #endif /* UNIV_DEBUG */

  20.     void reverse()

  21.     {

  22.         Type*    tmp = start;

  23.         start = end;

  24.         end = tmp;

  25.     }

  26. };

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

點(diǎn)擊(此處)折疊或打開(kāi)

  1. /** Lock struct; protected by lock_sys->mutex */

  2. struct lock_t {

  3.     trx_t*        trx;        /*!< transaction owning the

  4.                     lock */

  5.     UT_LIST_NODE_T(lock_t)

  6.             trx_locks;    /*!< list of the locks of the

  7.                     transaction */

  8. ..........


剩下還有一個(gè)關(guān)鍵的仿函數(shù)：

點(diǎn)擊(此處)折疊或打開(kāi)

  1. template <typename Type> //一元謂詞仿函數(shù)

  2. struct GenericGetNode {

  3.     typedef ut_list_node<Type> node_type;

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

  5.     node_type& operator() (Type& elem)

  6.     {

  7.         return(elem.*m_node);

  8.     }

  9.     node_type    Type::*m_node;

  10. };

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

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

點(diǎn)擊(此處)折疊或打開(kāi)

  1. #define UT_LIST_INIT(b, pmf)    \

  2. {    \

  3. (b).count = 0;    \

  4. (b).start = 0;    \

  5. (b).end = 0;    \

  6. (b).node = pmf;    \

  7. UT_LIST_INITIALISE(b);    \

  8. }



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

點(diǎn)擊(此處)折疊或打開(kāi)

  1. template <typename List>

  2. void

  3. ut_list_append(

  4. List&    list,

  5. typename List::elem_type*    elem)

  6. {

  7. ut_list_append(

  8. list, elem,

  9. GenericGetNode<typename List::elem_type>(list.node));

  10. }



然后調(diào)用：

點(diǎn)擊(此處)折疊或打開(kāi)

  1. template <typename List, typename Functor>

  2. void

  3. ut_list_append(

  4. List&    list,

  5. typename List::elem_type*    elem,

  6. Functor    get_node)

  7. {

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

  11. UT_LIST_IS_INITIALISED(list);

  14. node.next = 0;

  15. node.prev = list.end;

  18. if (list.end != 0) {

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

  22. ut_ad(list.end != elem);

  25. base_node.next = elem;

  26. }

  29. list.end = elem;

  32. if (list.start == 0) {

  33. list.start = elem;

  34. }

  35. ++list.count;

  36. }

詳細(xì)描述一下：
首先看一下：
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出來(lái)的一個(gè)
指向lock_t*的指針old_lock其類型當(dāng)然也就是UT_LIST_BASE_NODE_T(lock_t)::elem_type*類型實(shí)際上就是
lock_t*類型繞了一大圈。
而GenericGetNode(list.node)雖然很長(zhǎng)但是我們可以清楚的明白他是
調(diào)用的構(gòu)造函數(shù)，生成一個(gè)匿名對(duì)象，typename List::elem_type是用到了ut_list_base定義的類型
elem_type就是一個(gè)UT_LIST_BASE_NODE_T(lock_t)::elem_type類型其實(shí)就是lock_t類型，而list.node
實(shí)際上就是node_ptr類型，初始化已經(jīng)被定義為&lock_t::trx_locks

接下來(lái)由于函數(shù)重載的函數(shù)調(diào)用了
ut_list_append(
List& list,
typename List::elem_type* elem,
Functor get_node)
我們來(lái)看看。
typename List::node_type& node = get_node(*elem);
將List(old_locks)中的node成員函數(shù)指針進(jìn)行初始化他指向了old_lock這是結(jié)構(gòu)實(shí)際鏈表結(jié)構(gòu)的位置。
接下來(lái)node.next nodex.prev將是可用的了
node.next = 0;
node.prev = list.end;
將節(jié)點(diǎn)的后指針設(shè)置為NULL，前指針當(dāng)然設(shè)置為list.end的位置
這里也看到他確實(shí)放到末尾
if (list.end != 0) {
typename List::node_type& base_node = get_node(*list.end);
ut_ad(list.end != elem);
base_node.next = elem;
}
如果鏈表不為空，這里再次獲得end節(jié)點(diǎn)的位置存放到base_node中，
當(dāng)然也就要將base_node.next設(shè)置為我們新加入的節(jié)點(diǎn)的指針。
list.end = elem;
將鏈表頭結(jié)構(gòu)的end指針?lè)诺轿覀冃虏迦氲膃lem中。
if (list.start == 0) {
list.start = elem;
}
如果list的start指針為空代表鏈表為空，那么還需要將start指針指向elem
最后
++list.count;
不解釋了。

從整個(gè)鏈表的實(shí)現(xiàn)來(lái)看仿函數(shù)是其中的一個(gè)重點(diǎn)，他是一個(gè)橋梁其主要分為兩步：
1、初始化指向一個(gè)類的成員函數(shù)，這是指定他的類型，獲得他的偏移量
2、初始化指向某一個(gè)元素，這是獲得他的內(nèi)存空間地址基地址
有了基地址+偏移量就能夠找到實(shí)際的元素了。

感謝各位的閱讀！關(guān)于“MYSQL INNODB中通用雙向鏈表怎么實(shí)現(xiàn)”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！

標(biāo)題名稱：MYSQLINNODB中通用雙向鏈表怎么實(shí)現(xiàn)
文章來(lái)源：http://muchs.cn/article26/pdhscg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站排名、品牌網(wǎng)站設(shè)計(jì)、面包屑導(dǎo)航、定制開(kāi)發(fā)、網(wǎng)站設(shè)計(jì)、品牌網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

手機(jī)網(wǎng)站建設(shè)