MySQL InnoDB 中通用双向链表的实现

192次阅读

共计 6625 个字符，预计需要花费 17 分钟才能阅读完成。

源码在 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;
不解释了。