TLA Line data Source code
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-2023, 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 : */
28 : static inline void
29 CBC 44292678 : proclist_init(proclist_head *list)
30 : {
31 44292678 : list->head = list->tail = INVALID_PGPROCNO;
32 44292678 : }
33 :
34 : /*
35 : * Is the list empty?
36 : */
37 : static inline bool
38 GNC 2694323 : proclist_is_empty(const proclist_head *list)
39 : {
40 CBC 2694323 : 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 : */
47 : static inline proclist_node *
48 2778860 : proclist_node_get(int procno, size_t node_offset)
49 : {
50 2778860 : char *entry = (char *) GetPGProcByNumber(procno);
51 :
52 2778860 : return (proclist_node *) (entry + node_offset);
53 : }
54 :
55 : /*
56 : * Insert a process at the beginning of a list.
57 : */
58 : static inline void
59 3924 : proclist_push_head_offset(proclist_head *list, int procno, size_t node_offset)
60 : {
61 3924 : proclist_node *node = proclist_node_get(procno, node_offset);
62 :
63 3924 : Assert(node->next == 0 && node->prev == 0);
64 :
65 3924 : if (list->head == INVALID_PGPROCNO)
66 : {
67 2508 : Assert(list->tail == INVALID_PGPROCNO);
68 2508 : node->next = node->prev = INVALID_PGPROCNO;
69 2508 : list->head = list->tail = procno;
70 : }
71 : else
72 : {
73 1416 : Assert(list->tail != INVALID_PGPROCNO);
74 1416 : Assert(list->head != procno);
75 1416 : Assert(list->tail != procno);
76 1416 : node->next = list->head;
77 1416 : proclist_node_get(node->next, node_offset)->prev = procno;
78 1416 : node->prev = INVALID_PGPROCNO;
79 1416 : list->head = procno;
80 : }
81 3924 : }
82 :
83 : /*
84 : * Insert a process at the end of a list.
85 : */
86 : static inline void
87 51747 : proclist_push_tail_offset(proclist_head *list, int procno, size_t node_offset)
88 : {
89 51747 : proclist_node *node = proclist_node_get(procno, node_offset);
90 :
91 51747 : Assert(node->next == 0 && node->prev == 0);
92 :
93 51747 : if (list->tail == INVALID_PGPROCNO)
94 : {
95 48252 : Assert(list->head == INVALID_PGPROCNO);
96 48252 : node->next = node->prev = INVALID_PGPROCNO;
97 48252 : list->head = list->tail = procno;
98 : }
99 : else
100 : {
101 3495 : Assert(list->head != INVALID_PGPROCNO);
102 3495 : Assert(list->head != procno);
103 3495 : Assert(list->tail != procno);
104 3495 : node->prev = list->tail;
105 3495 : proclist_node_get(node->prev, node_offset)->next = procno;
106 3495 : node->next = INVALID_PGPROCNO;
107 3495 : list->tail = procno;
108 : }
109 51747 : }
110 :
111 : /*
112 : * Delete a process from a list --- it must be in the list!
113 : */
114 : static inline void
115 55468 : proclist_delete_offset(proclist_head *list, int procno, size_t node_offset)
116 : {
117 55468 : proclist_node *node = proclist_node_get(procno, node_offset);
118 :
119 55468 : Assert(node->next != 0 || node->prev != 0);
120 :
121 55468 : if (node->prev == INVALID_PGPROCNO)
122 : {
123 55335 : Assert(list->head == procno);
124 55335 : list->head = node->next;
125 : }
126 : else
127 133 : proclist_node_get(node->prev, node_offset)->next = node->next;
128 :
129 55468 : if (node->next == INVALID_PGPROCNO)
130 : {
131 50677 : Assert(list->tail == procno);
132 50677 : list->tail = node->prev;
133 : }
134 : else
135 4791 : proclist_node_get(node->next, node_offset)->prev = node->prev;
136 :
137 55468 : node->next = node->prev = 0;
138 55468 : }
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 : */
145 : static inline bool
146 GNC 2623148 : proclist_contains_offset(const proclist_head *list, int procno,
147 : size_t node_offset)
148 : {
149 2623148 : const 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 CBC 2623148 : if (node->prev == 0 && node->next == 0)
153 2618009 : 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 5139 : Assert(node->prev != INVALID_PGPROCNO || list->head == procno);
164 5139 : Assert(node->next != INVALID_PGPROCNO || list->tail == procno);
165 :
166 5139 : return true;
167 : }
168 :
169 : /*
170 : * Remove and return the first process from a list (there must be one).
171 : */
172 : static inline PGPROC *
173 2456 : proclist_pop_head_node_offset(proclist_head *list, size_t node_offset)
174 : {
175 : PGPROC *proc;
176 :
177 2456 : Assert(!proclist_is_empty(list));
178 2456 : proc = GetPGProcByNumber(list->head);
179 2456 : proclist_delete_offset(list, list->head, node_offset);
180 2456 : 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 */
|
