当前位置：网站首页>IList of PostgreSQL

IList of PostgreSQL

2022-06-24 14:20:00 【happytree001】

One 、 brief introduction

postgresql In its own library, it implements one-way linked list and two-way linked list , Involving documents src/include/lib/ilist.h and src/backend/lib/ilist.c, Most functions are in ilist.h To realize .

Two 、 Structure definition

2.1 Double linked list

2.1.1 Structure definition

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 iterator

/* * 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 One way linked list

2.2.1 Structure definition

/* * 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 iterator

/* * 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;

3、 ... and 、 API

3.1 Double linked list

/* * 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 One way linked list

/* * 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);

Four 、 summary

Are short, compact inline functions , Embedded in the caller , No function call consumption

Well designed , Considerate , Avoid accidents

/* * 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);
}

The insertion of this two-way linked list , first if Judge , Without this judgment , Callers are prone to errors .

For example, the caller uses the following code , Use memest Instead of dlist_init.

dlist_head head;

memset(&head, 0, sizeof(head));
// dlist_init(&head);

dlist_node *node = malloc(sizeof(node));

dlist_push_head(&head, node);

without if Judge , This will cause the linked list to be destroyed , Not a two-way linked list , Subsequent operations on this linked list will cause unexpected problems , For example, collapse , It may be that other places use this linked list , So the scope is expanded , It is even harder to troubleshoot problems

The function is basic and powerful , You can build a new model by stacking wood

such as The following two functions can be combined to build a chained stack model .

static inline void dlist_push_head(dlist_head *head, dlist_node *node); // Push 
static inline dlist_node *dlist_pop_head_node(dlist_head *head); // Out of the stack 
static inline dlist_node * dlist_head_node(dlist_head *head); // Look at the top of the stack elements

such as The following two functions can be combined to build a chained queue model .

static inline void dlist_push_tail(dlist_head *head, dlist_node *node); // The team 
static inline dlist_node *dlist_pop_head_node(dlist_head *head); // Out of the team

such as The following combination can build a LRU Queues

static inline void dlist_push_head(dlist_head *head, dlist_node *node); // The team 

// Iteration queue , Find the node to access 
#define dlist_foreach(iter, lhead) ...

static inline void dlist_move_head(dlist_head *head, dlist_node *node); // Move the currently accessed node to the queue head 

// When the queue length reaches a certain threshold , Delete the last element 
static inline dlist_node * dlist_tail_node(dlist_head *head);
static inline void dlist_delete(dlist_node *node);

Code comments are detailed , There are also some precautions for use

/* * 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;
}

such as dlist_pop_head_node Comments on functions , Just make it clear list There must be an element in the , It can also be seen from the implementation , call Assert Assertion judgement list Is it empty , If it is blank, it will 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)])])
    
...