1/*-------------------------------------------------------------------------
2 *
3 * proclist.h
4 * operations on doubly-linked lists of pgprocnos
5 *
6 * The interface is similar to dlist from ilist.h, but uses pgprocno instead
7 * of pointers. This allows proclist_head to be mapped at different addresses
8 * in different backends.
9 *
10 * See proclist_types.h for the structs that these functions operate on. They
11 * are separated to break a header dependency cycle with proc.h.
12 *
13 * Portions Copyright (c) 2016-2019, PostgreSQL Global Development Group
14 *
15 * IDENTIFICATION
16 * src/include/storage/proclist.h
17 *-------------------------------------------------------------------------
18 */
19#ifndef PROCLIST_H
20#define PROCLIST_H
21
22#include "storage/proc.h"
23#include "storage/proclist_types.h"
24
25/*
26 * Initialize a proclist.
27 */
28static inline void
29proclist_init(proclist_head *list)
30{
31 list->head = list->tail = INVALID_PGPROCNO;
32}
33
34/*
35 * Is the list empty?
36 */
37static inline bool
38proclist_is_empty(proclist_head *list)
39{
40 return list->head == INVALID_PGPROCNO;
41}
42
43/*
44 * Get a pointer to a proclist_node inside a given PGPROC, given a procno and
45 * the proclist_node field's offset within struct PGPROC.
46 */
47static inline proclist_node *
48proclist_node_get(int procno, size_t node_offset)
49{
50 char *entry = (char *) GetPGProcByNumber(procno);
51
52 return (proclist_node *) (entry + node_offset);
53}
54
55/*
56 * Insert a process at the beginning of a list.
57 */
58static inline void
59proclist_push_head_offset(proclist_head *list, int procno, size_t node_offset)
60{
61 proclist_node *node = proclist_node_get(procno, node_offset);
62
63 Assert(node->next == 0 && node->prev == 0);
64
65 if (list->head == INVALID_PGPROCNO)
66 {
67 Assert(list->tail == INVALID_PGPROCNO);
68 node->next = node->prev = INVALID_PGPROCNO;
69 list->head = list->tail = procno;
70 }
71 else
72 {
73 Assert(list->tail != INVALID_PGPROCNO);
74 Assert(list->head != procno);
75 Assert(list->tail != procno);
76 node->next = list->head;
77 proclist_node_get(node->next, node_offset)->prev = procno;
78 node->prev = INVALID_PGPROCNO;
79 list->head = procno;
80 }
81}
82
83/*
84 * Insert a process at the end of a list.
85 */
86static inline void
87proclist_push_tail_offset(proclist_head *list, int procno, size_t node_offset)
88{
89 proclist_node *node = proclist_node_get(procno, node_offset);
90
91 Assert(node->next == 0 && node->prev == 0);
92
93 if (list->tail == INVALID_PGPROCNO)
94 {
95 Assert(list->head == INVALID_PGPROCNO);
96 node->next = node->prev = INVALID_PGPROCNO;
97 list->head = list->tail = procno;
98 }
99 else
100 {
101 Assert(list->head != INVALID_PGPROCNO);
102 Assert(list->head != procno);
103 Assert(list->tail != procno);
104 node->prev = list->tail;
105 proclist_node_get(node->prev, node_offset)->next = procno;
106 node->next = INVALID_PGPROCNO;
107 list->tail = procno;
108 }
109}
110
111/*
112 * Delete a process from a list --- it must be in the list!
113 */
114static inline void
115proclist_delete_offset(proclist_head *list, int procno, size_t node_offset)
116{
117 proclist_node *node = proclist_node_get(procno, node_offset);
118
119 Assert(node->next != 0 || node->prev != 0);
120
121 if (node->prev == INVALID_PGPROCNO)
122 {
123 Assert(list->head == procno);
124 list->head = node->next;
125 }
126 else
127 proclist_node_get(node->prev, node_offset)->next = node->next;
128
129 if (node->next == INVALID_PGPROCNO)
130 {
131 Assert(list->tail == procno);
132 list->tail = node->prev;
133 }
134 else
135 proclist_node_get(node->next, node_offset)->prev = node->prev;
136
137 node->next = node->prev = 0;
138}
139
140/*
141 * Check if a process is currently in a list. It must be known that the
142 * process is not in any _other_ proclist that uses the same proclist_node,
143 * so that the only possibilities are that it is in this list or none.
144 */
145static inline bool
146proclist_contains_offset(proclist_head *list, int procno,
147 size_t node_offset)
148{
149 proclist_node *node = proclist_node_get(procno, node_offset);
150
151 /* If it's not in any list, it's definitely not in this one. */
152 if (node->prev == 0 && node->next == 0)
153 return false;
154
155 /*
156 * It must, in fact, be in this list. Ideally, in assert-enabled builds,
157 * we'd verify that. But since this function is typically used while
158 * holding a spinlock, crawling the whole list is unacceptable. However,
159 * we can verify matters in O(1) time when the node is a list head or
160 * tail, and that seems worth doing, since in practice that should often
161 * be enough to catch mistakes.
162 */
163 Assert(node->prev != INVALID_PGPROCNO || list->head == procno);
164 Assert(node->next != INVALID_PGPROCNO || list->tail == procno);
165
166 return true;
167}
168
169/*
170 * Remove and return the first process from a list (there must be one).
171 */
172static inline PGPROC *
173proclist_pop_head_node_offset(proclist_head *list, size_t node_offset)
174{
175 PGPROC *proc;
176
177 Assert(!proclist_is_empty(list));
178 proc = GetPGProcByNumber(list->head);
179 proclist_delete_offset(list, list->head, node_offset);
180 return proc;
181}
182
183/*
184 * Helper macros to avoid repetition of offsetof(PGPROC, <member>).
185 * 'link_member' is the name of a proclist_node member in PGPROC.
186 */
187#define proclist_delete(list, procno, link_member) \
188 proclist_delete_offset((list), (procno), offsetof(PGPROC, link_member))
189#define proclist_push_head(list, procno, link_member) \
190 proclist_push_head_offset((list), (procno), offsetof(PGPROC, link_member))
191#define proclist_push_tail(list, procno, link_member) \
192 proclist_push_tail_offset((list), (procno), offsetof(PGPROC, link_member))
193#define proclist_pop_head_node(list, link_member) \
194 proclist_pop_head_node_offset((list), offsetof(PGPROC, link_member))
195#define proclist_contains(list, procno, link_member) \
196 proclist_contains_offset((list), (procno), offsetof(PGPROC, link_member))
197
198/*
199 * Iterate through the list pointed at by 'lhead', storing the current
200 * position in 'iter'. 'link_member' is the name of a proclist_node member in
201 * PGPROC. Access the current position with iter.cur.
202 *
203 * The only list modification allowed while iterating is deleting the current
204 * node with proclist_delete(list, iter.cur, node_offset).
205 */
206#define proclist_foreach_modify(iter, lhead, link_member) \
207 for (AssertVariableIsOfTypeMacro(iter, proclist_mutable_iter), \
208 AssertVariableIsOfTypeMacro(lhead, proclist_head *), \
209 (iter).cur = (lhead)->head, \
210 (iter).next = (iter).cur == INVALID_PGPROCNO ? INVALID_PGPROCNO : \
211 proclist_node_get((iter).cur, \
212 offsetof(PGPROC, link_member))->next; \
213 (iter).cur != INVALID_PGPROCNO; \
214 (iter).cur = (iter).next, \
215 (iter).next = (iter).cur == INVALID_PGPROCNO ? INVALID_PGPROCNO : \
216 proclist_node_get((iter).cur, \
217 offsetof(PGPROC, link_member))->next)
218
219#endif /* PROCLIST_H */
220