一、简介
postgresql本身的库中实现了单向链表和双向链表，涉及文件src/include/lib/ilist.h和 src/backend/lib/ilist.c, 绝大部分功能都在ilist.h中实现。
二、结构定义
2.1 双向链表
2.1.1 结构定义
typedef struct dlist_node dlist_node;
struct dlist_node
{
dlist_node *prev;
dlist_node *next;
};
/*
* Head of a doubly linked list.
*
* Non-empty lists are internally circularly linked. Circular lists have the
* advantage of not needing any branches in the most common list manipulations.
* An empty list can also be represented as a pair of NULL pointers, making
* initialization easier.
*/
typedef struct dlist_head
{
/*
* head.next either points to the first element of the list; to &head if
* it's a circular empty list; or to NULL if empty and not circular.
*
* head.prev either points to the last element of the list; to &head if
* it's a circular empty list; or to NULL if empty and not circular.
*/
dlist_node head;
} dlist_head;
2.1.2 迭代器
/*
* Doubly linked list iterator.
*
* Used as state in dlist_foreach() and dlist_reverse_foreach(). To get the
* current element of the iteration use the 'cur' member.
*
* Iterations using this are *not* allowed to change the list while iterating!
*
* NB: We use an extra "end" field here to avoid multiple evaluations of
* arguments in the dlist_foreach() macro.
*/
typedef struct dlist_iter
{
dlist_node *cur; /* current element */
dlist_node *end; /* last node we'll iterate to */
} dlist_iter;
/*
* Doubly linked list iterator allowing some modifications while iterating.
*
* Used as state in dlist_foreach_modify(). To get the current element of the
* iteration use the 'cur' member.
*
* Iterations using this are only allowed to change the list at the current
* point of iteration. It is fine to delete the current node, but it is *not*
* fine to insert or delete adjacent nodes.
*
* NB: We need a separate type for mutable iterations so that we can store
* the 'next' node of the current node in case it gets deleted or modified.
*/
typedef struct dlist_mutable_iter
{
dlist_node *cur; /* current element */
dlist_node *next; /* next node we'll iterate to */
dlist_node *end; /* last node we'll iterate to */
} dlist_mutable_iter;
2.2 单向链表
2.2.1 结构定义
/*
* Node of a singly linked list.
*
* Embed this in structs that need to be part of a singly linked list.
*/
typedef struct slist_node slist_node;
struct slist_node
{
slist_node *next;
};
/*
* Head of a singly linked list.
*
* Singly linked lists are not circularly linked, in contrast to doubly linked
* lists; we just set head.next to NULL if empty. This doesn't incur any
* additional branches in the usual manipulations.
*/
typedef struct slist_head
{
slist_node head;
} slist_head;
2.2.2 迭代器
/*
* Singly linked list iterator.
*
* Used as state in slist_foreach(). To get the current element of the
* iteration use the 'cur' member.
*
* It's allowed to modify the list while iterating, with the exception of
* deleting the iterator's current node; deletion of that node requires
* care if the iteration is to be continued afterward. (Doing so and also
* deleting or inserting adjacent list elements might misbehave; also, if
* the user frees the current node's storage, continuing the iteration is
* not safe.)
*
* NB: this wouldn't really need to be an extra struct, we could use an
* slist_node * directly. We prefer a separate type for consistency.
*/
typedef struct slist_iter
{
slist_node *cur;
} slist_iter;
/*
* Singly linked list iterator allowing some modifications while iterating.
*
* Used as state in slist_foreach_modify(). To get the current element of the
* iteration use the 'cur' member.
*
* The only list modification allowed while iterating is to remove the current
* node via slist_delete_current() (*not* slist_delete()). Insertion or
* deletion of nodes adjacent to the current node would misbehave.
*/
typedef struct slist_mutable_iter
{
slist_node *cur; /* current element */
slist_node *next; /* next node we'll iterate to */
slist_node *prev; /* prev node, for deletions */
} slist_mutable_iter;
三、 API
3.1 双向链表
/*
* Initialize a doubly linked list.
* Previous state will be thrown away without any cleanup.
*/
static inline void dlist_init(dlist_head *head);
/*
* Is the list empty?
*
* An empty list has either its first 'next' pointer set to NULL, or to itself.
*/
static inline bool dlist_is_empty(dlist_head *head);
/*
* Insert a node at the beginning of the list.
*/
static inline void dlist_push_head(dlist_head *head, dlist_node *node);
/*
* Insert a node at the end of the list.
*/
static inline void dlist_push_tail(dlist_head *head, dlist_node *node);
/*
* Insert a node after another *in the same list*
*/
static inline void
dlist_insert_after(dlist_node *after, dlist_node *node);
/*
* Insert a node before another *in the same list*
*/
static inline void
dlist_insert_before(dlist_node *before, dlist_node *node);
/*
* Delete 'node' from its list (it must be in one).
*/
static inline void dlist_delete(dlist_node *node);
/*
* Remove and return the first node from a list (there must be one).
*/
static inline dlist_node *dlist_pop_head_node(dlist_head *head);
/*
* Move element from its current position in the list to the head position in
* the same list.
*
* Undefined behaviour if 'node' is not already part of the list.
*/
static inline void dlist_move_head(dlist_head *head, dlist_node *node);
/*
* Move element from its current position in the list to the tail position in
* the same list.
*
* Undefined behaviour if 'node' is not already part of the list.
*/
static inline void dlist_move_tail(dlist_head *head, dlist_node *node);
/*
* Check whether 'node' has a following node.
* Caution: unreliable if 'node' is not in the list.
*/
static inline bool dlist_has_next(dlist_head *head, dlist_node *node);
/*
* Check whether 'node' has a preceding node.
* Caution: unreliable if 'node' is not in the list.
*/
static inline bool dlist_has_prev(dlist_head *head, dlist_node *node);
/*
* Return the next node in the list (there must be one).
*/
static inline dlist_node * dlist_next_node(dlist_head *head, dlist_node *node);
/*
* Return previous node in the list (there must be one).
*/
static inline dlist_node * dlist_prev_node(dlist_head *head, dlist_node *node);
/* internal support function to get address of head element's struct */
static inline void * dlist_head_element_off(dlist_head *head, size_t off);
/*
* Return the first node in the list (there must be one).
*/
static inline dlist_node * dlist_head_node(dlist_head *head);
/* internal support function to get address of tail element's struct */
static inline void * dlist_tail_element_off(dlist_head *head, size_t off);
/*
* Return the last node in the list (there must be one).
*/
static inline dlist_node * dlist_tail_node(dlist_head *head);
3.2 单向链表
/*
* Initialize a singly linked list.
* Previous state will be thrown away without any cleanup.
*/
static inline void slist_init(slist_head *head);
/*
* Is the list empty?
*/
static inline bool slist_is_empty(slist_head *head);
/*
* Insert a node at the beginning of the list.
*/
static inline void slist_push_head(slist_head *head, slist_node *node);
/*
* Insert a node after another *in the same list*
*/
static inline void slist_insert_after(slist_node *after, slist_node *node);
/*
* Remove and return the first node from a list (there must be one).
*/
static inline slist_node * slist_pop_head_node(slist_head *head);
/*
* Check whether 'node' has a following node.
*/
static inline bool slist_has_next(slist_head *head, slist_node *node);
/*
* Return the next node in the list (there must be one).
*/
static inline slist_node * slist_next_node(slist_head *head, slist_node *node);
/* internal support function to get address of head element's struct */
static inline void * slist_head_element_off(slist_head *head, size_t off);
/*
* Return the first node in the list (there must be one).
*/
static inline slist_node * slist_head_node(slist_head *head);
/*
* Delete the list element the iterator currently points to.
*
* Caution: this modifies iter->cur, so don't use that again in the current
* loop iteration.
*/
static inline void slist_delete_current(slist_mutable_iter *iter);
四、总结
-
都是短小精干的内联函数，内嵌到调用方，没有函数调用的消耗
-
设计精妙，考虑周到，避免意外
/* * Insert a node at the beginning of the list. */ static inline void dlist_push_head(dlist_head *head, dlist_node *node) { if (head->head.next == NULL) /* convert NULL header to circular */ dlist_init(head); node->next = head->head.next; node->prev = &head->head; node->next->prev = node; head->head.next = node; dlist_check(head); }这个双向链表的插入，第一个if判断，如果没有这个判断，调用方很容易出现错误。
比如调用方使用如下代码,使用memest代替了dlist_init。
dlist_head head; memset(&head, 0, sizeof(head)); // dlist_init(&head); dlist_node *node = malloc(sizeof(node)); dlist_push_head(&head, node);如果没有if判断，将导致这个链表被破坏，不是双向链表，后续对这个链表的操作将出现意想不到的问题，比如崩溃，可能是其他地方使用这个链表，这样范围扩大，更不好排查问题 😦
-
函数功能基础且强大，可以搭积木构建新模型
比如 如下两个函数组合就可以构建一个链式的栈模型。
static inline void dlist_push_head(dlist_head *head, dlist_node *node); //入栈
static inline dlist_node *dlist_pop_head_node(dlist_head *head); //出栈
static inline dlist_node * dlist_head_node(dlist_head *head); //查看栈顶元素
比如 如下两个函数组合就可以构建一个链式的队列模型。
static inline void dlist_push_tail(dlist_head *head, dlist_node *node); //入队
static inline dlist_node *dlist_pop_head_node(dlist_head *head); //出队
比如 如下组合就可以构建一个LRU的队列
static inline void dlist_push_head(dlist_head *head, dlist_node *node); //入队
//迭代队列，找到需要访问的节点
#define dlist_foreach(iter, lhead) ...
static inline void dlist_move_head(dlist_head *head, dlist_node *node); //将当前访问的节点移动到队头
//当队列长度达到某个阈值时，删除最后一个元素
static inline dlist_node * dlist_tail_node(dlist_head *head);
static inline void dlist_delete(dlist_node *node);
- 代码注释详细，并且还带有一些使用的注意事项
/*
* Remove and return the first node from a list (there must be one).
*/
static inline dlist_node *
dlist_pop_head_node(dlist_head *head)
{
dlist_node *node;
Assert(!dlist_is_empty(head));
node = head->head.next;
dlist_delete(node);
return node;
}
比如dlist_pop_head_node函数的注释，就明确说明list中必须要有元素，从实现中也能看出，调用Assert断言判断list是否为空，如果为空则会abort。
include/c.h
#ifndef USE_ASSERT_CHECKING
#define Assert(condition) ((void)true)
...
#elif defined(FRONTEND)
#include <assert.h>
#define Assert(p) assert(p)
...
#else /* USE_ASSERT_CHECKING && !FRONTEND */
...
#define Assert(condition) \
do { \
if (!(condition)) \
ExceptionalCondition(#condition, "FailedAssertion", \
__FILE__, __LINE__); \
} while (0)
...
#endif /* USE_ASSERT_CHECKING && !FRONTEND */
configure.ac
...
#
# Enable assert checks
#
PGAC_ARG_BOOL(enable, cassert, no, [enable assertion checks (for debugging)],
[AC_DEFINE([USE_ASSERT_CHECKING], 1,
[Define to 1 to build with assertion checks. (--enable-cassert)])])
...
可以看到默认是定义了USE_ASSERT_CHECKING, 所以最终都会调用abort终止程序。
所以在调用dlist_pop_head_node之前需要调用dlist_is_empty进行判断，如果链表不为空才能调用dlist_pop_head_node。
- 分工明确
比如迭代器，分为了只读迭代器和可修改链表的迭代器。
