MYSQL INNODB中通用双向链表怎么达成
发布时间：2022-01-12 11:33:53 所属栏目：MySql教程 来源：互联网
导读：这篇文章给大家分享的是有关MYSQL INNODB中通用双向链表怎么实现的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。 源码在Ut0lst.h中 注意：这里我将链表中的实际的串联的数据叫做数据类比如：lock_t、mem_block_t 链表作为一
|
这篇文章给大家分享的是有关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中通用双向链表怎么实现”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！ （编辑：应用网_镇江站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐