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、函数重载

简单的说仿函数是调用的时候类似函数调用的形式的类,类成员指针并非一个真正意义上的
指针,而是指向特定类对象相对位置的一个偏移量。
比如如下就是一个仿函数类:

点击(此处)折叠或打开

  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. };

下面是一个简单的类成员指针使用,他初始化分为2步在最后给出.:

点击(此处)折叠或打开

  1. #include<iostream>
  2. using namespace std;
  3. class T
  4. {
  5.   public:
  6.   typedef int uint;
  7.   public:
  8.           int a;
  9.           int b;
  10. };
  11. int main21(void)
  12. {
  13.         T t;
  14.         int T::* t1 = &T::b;//1、成员函数指针 初始化为指向类T成员b的一个指针(成员函数指针指向的是偏移量)
  15.         T* t2 = &t;//t2一个指向类变量t的指针
  16.         t.*t1 = 10;//2、初始化t的t1类成员指针指向的内存空间值为10,实际上就是t.b=10
  17.         cout<<t.*t1<<” “<<t2->*t1<<endl;//相同输出一个采用对象一个采用对象指针
  18.         {
  19.                 T t3;
  20.                 t3.a=300;
  21.                 t.*t1 = t3.a; //他就是拥有实际内存空间的变量了
  22.         }
  23. }

模板和函数重载就没有什么好说的了。

接下来我们看看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链表结构体:

点击(此处)折叠或打开

  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 */
  7.     void reverse()
  8.     {
  9.         Type*    tmp = prev;
  10.         prev = next;
  11.         next = tmp;
  12.     }
  13. };

非常简单没有包含任何固定的数据信息,只是包含了链表的前后指针,同时包含了一个成员函数reverse,作为
实现链表反转的基础,这里也注意到由于没有包含任何数据信息成员,做到了链表和具体数据类之间的剥离。
在链表设计的时候通常有2种方式:
1、链表结构包含数据类
2、数据类包含链表结构
这里INNODB使用了后者,让链表的通用更加方便

再来看看ut_list_base 链表头结构体:

点击(此处)折叠或打开

  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;
  6.     ulint        count;            /*!< count of nodes in list */
  7.     elem_type*    start;            /*!< pointer to list start,
  8.                         NULL if empty */
  9.     elem_type*    end;            /*!< pointer to list end,
  10.                         NULL if empty */
  11.     node_ptr    node;            /*!< Pointer to member field
  12.                         that is used as a link node */
  13. #ifdef UNIV_DEBUG
  14.     ulint        init;            /*!< UT_LIST_INITIALISED if
  15.                         the list was initialised with
  16.                         UT_LIST_INIT() */
  17. #endif /* UNIV_DEBUG */
  18.     void reverse()
  19.     {
  20.         Type*    tmp = start;
  21.         start = end;
  22.         end = tmp;
  23.     }
  24. };

这里再来解释一下:
在类的内部进行了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

点击(此处)折叠或打开

  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. ..........

剩下还有一个关键的仿函数:

点击(此处)折叠或打开

  1. template <typename Type> //一元谓词仿函数
  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. };

这里解释一下这个仿函数类:
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是一个宏

点击(此处)折叠或打开

  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. }

非常简单设置全部指针都是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)
在经过函数重载调用后实际上他会调用

点击(此处)折叠或打开

  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. }

然后调用:

点击(此处)折叠或打开

  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);
  9. UT_LIST_IS_INITIALISED(list);
  10. node.next = 0;
  11. node.prev = list.end;
  12. if (list.end != 0) {
  13. typename List::node_type&    base_node = get_node(*list.end);
  14. ut_ad(list.end != elem);
  15. base_node.next = elem;
  16. }
  17. list.end = elem;
  18. if (list.start == 0) {
  19. list.start = elem;
  20. }
  21. ++list.count;
  22. }

详细描述一下:
首先看一下:
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 中通用双向链表的实现
PS:如果您想和业内技术大牛交流的话,请加qq群(527933790)或者关注微信公众 号(AskHarries),谢谢!

转载请注明原文出处:Harries Blog™ » MYSQL INNODB 中通用双向链表的实现

赞 (0)

分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址