PostgreSQL Source Code  git master
proclist.h
Go to the documentation of this file.
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-2018, 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
30 {
31  list->head = list->tail = INVALID_PGPROCNO;
32 }
33 
34 /*
35  * Is the list empty?
36  */
37 static inline bool
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  */
47 static inline proclist_node *
48 proclist_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  */
58 static inline void
59 proclist_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  */
86 static inline void
87 proclist_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  */
114 static inline void
115 proclist_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  */
145 static inline bool
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  */
172 static inline PGPROC *
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 */
static void proclist_push_head_offset(proclist_head *list, int procno, size_t node_offset)
Definition: proclist.h:59
static PGPROC * proclist_pop_head_node_offset(proclist_head *list, size_t node_offset)
Definition: proclist.h:173
#define GetPGProcByNumber(n)
Definition: proc.h:277
static void proclist_delete_offset(proclist_head *list, int procno, size_t node_offset)
Definition: proclist.h:115
static proclist_node * proclist_node_get(int procno, size_t node_offset)
Definition: proclist.h:48
#define INVALID_PGPROCNO
Definition: proc.h:77
static void proclist_push_tail_offset(proclist_head *list, int procno, size_t node_offset)
Definition: proclist.h:87
#define Assert(condition)
Definition: c.h:688
static bool proclist_is_empty(proclist_head *list)
Definition: proclist.h:38
static void proclist_init(proclist_head *list)
Definition: proclist.h:29
static bool proclist_contains_offset(proclist_head *list, int procno, size_t node_offset)
Definition: proclist.h:146
Definition: proc.h:95