0%

链表结构

## 链表结构 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();
}