Longda's Interesting World

Longda's Interesting World

MySQL 源码解读 -- 链表

MySQL 源码解读 -- 链表

链表结构

链表结构

innodb 的链表结构设计的比较巧妙，而且灵活， 一个基本的类型elem_type 可以是多个list的一个成员, 只要这个elem_type里面对应的node 对象

结构

list node 节点, 一个指向 前node， 一个指向 后node

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
  }
};

list 节点
一个指向list的头元素， 一个指向list的尾元素

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

  void reverse() {
    Type *tmp = start;
    start = end;
    end = tmp;
  }
};

一般使用方式是

使用

获取对象

举个例子， 以buffer_pool 中的LRU 为例
一个基本的类型elem_type 可以是多个list的一个成员, 只要这个elem_type里面对应的node 对象

1
2
3
4
5
6
7
8
9
10
#define UT_LIST_BASE_NODE_T(t) ut_list_base<t, ut_list_node<t> t::*>
#define UT_LIST_NODE_T(t) ut_list_node<t>
#define UT_LIST_INIT(b, pmf) \
  {                          \
    (b).count = 0;           \
    (b).start = 0;           \
    (b).end = 0;             \
    (b).node = pmf;          \
    UT_LIST_INITIALISE(b);   \
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
struct buf_pool_t {
...
UT_LIST_BASE_NODE_T(buf_page_t) LRU;
...
}

class buf_page_t {
...
UT_LIST_NODE_T(buf_page_t) LRU; 
// 注意， 这个里面有一个要求，就是elem_type 里面得有ut_list_node， 
// 这样后续可以通过elem_type得到node 对象， 比如elem->*list.node
...
}

这个里面需要注意的就是如何从elem得到node的操作， 比如elem->*list.node
或者类似如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/** Functor for accessing the embedded node within a list element. This is
required because some lists can have the node emebedded inside a nested
struct/union. See lock0priv.h (table locks) for an example. It provides a
specialised functor to grant access to the list node. */
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;
};

使用上

1
2
Functor get_node = GenericGetNode<typename List::elem_type>(list.node)
typename List::node_type &node = get_node(*elem);

初始化

1
2
3
UT_LIST_INIT(buf_pool->LRU, &buf_page_t::LRU);
UT_LIST_INIT(buf_pool->free, &buf_page_t::list);
UT_LIST_INIT(buf_pool->withdraw, &buf_page_t::list);

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
}

删除一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template <typename List, typename Functor>
void ut_list_remove(List &list, typename List::node_type &node,
                    Functor get_node) {
  ut_a(list.count > 0);
  UT_LIST_IS_INITIALISED(list);

  if (node.next != NULL) {
    typename List::node_type &next_node = get_node(*node.next);

    next_node.prev = node.prev;
  } else {
    list.end = node.prev;
  }

  if (node.prev != NULL) {
    typename List::node_type &prev_node = get_node(*node.prev);

    prev_node.next = node.next;
  } else {
    list.start = node.next;
  }

  node.next = 0;
  node.prev = 0;

  --list.count;
}

遍历list

1
2
3
4
5
6
7
8
9
10
11
template <typename List>
void ut_list_reverse(List &list) {
  UT_LIST_IS_INITIALISED(list);

  for (typename List::elem_type *elem = list.start; elem != 0;
       elem = (elem->*list.node).prev) {
    (elem->*list.node).reverse();
  }

  list.reverse();
}