当前位置：网站首页>postgresql 之 ilist

postgresql 之 ilist

2022-06-24 13:03:00 【happytree001】

一、简介

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)])])
    
...