PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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-2017, 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  * an offset.
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 node 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  if (list->head == INVALID_PGPROCNO)
64  {
65  Assert(list->tail == INVALID_PGPROCNO);
66  node->next = node->prev = INVALID_PGPROCNO;
67  list->head = list->tail = procno;
68  }
69  else
70  {
71  Assert(list->tail != INVALID_PGPROCNO);
72  Assert(list->head != procno);
73  Assert(list->tail != procno);
74  node->next = list->head;
75  proclist_node_get(node->next, node_offset)->prev = procno;
76  node->prev = INVALID_PGPROCNO;
77  list->head = procno;
78  }
79 }
80 
81 /*
82  * Insert a node at the end of a list.
83  */
84 static inline void
85 proclist_push_tail_offset(proclist_head *list, int procno, size_t node_offset)
86 {
87  proclist_node *node = proclist_node_get(procno, node_offset);
88 
89  if (list->tail == INVALID_PGPROCNO)
90  {
91  Assert(list->head == INVALID_PGPROCNO);
92  node->next = node->prev = INVALID_PGPROCNO;
93  list->head = list->tail = procno;
94  }
95  else
96  {
97  Assert(list->head != INVALID_PGPROCNO);
98  Assert(list->head != procno);
99  Assert(list->tail != procno);
100  node->prev = list->tail;
101  proclist_node_get(node->prev, node_offset)->next = procno;
102  node->next = INVALID_PGPROCNO;
103  list->tail = procno;
104  }
105 }
106 
107 /*
108  * Delete a node. The node must be in the list.
109  */
110 static inline void
111 proclist_delete_offset(proclist_head *list, int procno, size_t node_offset)
112 {
113  proclist_node *node = proclist_node_get(procno, node_offset);
114 
115  if (node->prev == INVALID_PGPROCNO)
116  list->head = node->next;
117  else
118  proclist_node_get(node->prev, node_offset)->next = node->next;
119 
120  if (node->next == INVALID_PGPROCNO)
121  list->tail = node->prev;
122  else
123  proclist_node_get(node->next, node_offset)->prev = node->prev;
124 
125  node->next = node->prev = INVALID_PGPROCNO;
126 }
127 
128 /*
129  * Check if a node is currently in a list. It must be known that the node is
130  * not in any _other_ proclist that uses the same proclist_node, so that the
131  * only possibilities are that it is in this list or none.
132  */
133 static inline bool
135  size_t node_offset)
136 {
137  proclist_node *node = proclist_node_get(procno, node_offset);
138 
139  /*
140  * If this is not a member of a proclist, then the next and prev pointers
141  * should be 0. Circular lists are not allowed so this condition is not
142  * confusable with a real pgprocno 0.
143  */
144  if (node->prev == 0 && node->next == 0)
145  return false;
146 
147  /* If there is a previous node, then this node must be in the list. */
148  if (node->prev != INVALID_PGPROCNO)
149  return true;
150 
151  /*
152  * There is no previous node, so the only way this node can be in the list
153  * is if it's the head node.
154  */
155  return list->head == procno;
156 }
157 
158 /*
159  * Remove and return the first node from a list (there must be one).
160  */
161 static inline PGPROC *
163 {
164  PGPROC *proc;
165 
166  Assert(!proclist_is_empty(list));
167  proc = GetPGProcByNumber(list->head);
168  proclist_delete_offset(list, list->head, node_offset);
169  return proc;
170 }
171 
172 /*
173  * Helper macros to avoid repetition of offsetof(PGPROC, <member>).
174  * 'link_member' is the name of a proclist_node member in PGPROC.
175  */
176 #define proclist_delete(list, procno, link_member) \
177  proclist_delete_offset((list), (procno), offsetof(PGPROC, link_member))
178 #define proclist_push_head(list, procno, link_member) \
179  proclist_push_head_offset((list), (procno), offsetof(PGPROC, link_member))
180 #define proclist_push_tail(list, procno, link_member) \
181  proclist_push_tail_offset((list), (procno), offsetof(PGPROC, link_member))
182 #define proclist_pop_head_node(list, link_member) \
183  proclist_pop_head_node_offset((list), offsetof(PGPROC, link_member))
184 #define proclist_contains(list, procno, link_member) \
185  proclist_contains_offset((list), (procno), offsetof(PGPROC, link_member))
186 
187 /*
188  * Iterate through the list pointed at by 'lhead', storing the current
189  * position in 'iter'. 'link_member' is the name of a proclist_node member in
190  * PGPROC. Access the current position with iter.cur.
191  *
192  * The only list modification allowed while iterating is deleting the current
193  * node with proclist_delete(list, iter.cur, node_offset).
194  */
195 #define proclist_foreach_modify(iter, lhead, link_member) \
196  for (AssertVariableIsOfTypeMacro(iter, proclist_mutable_iter), \
197  AssertVariableIsOfTypeMacro(lhead, proclist_head *), \
198  (iter).cur = (lhead)->head, \
199  (iter).next = (iter).cur == INVALID_PGPROCNO ? INVALID_PGPROCNO : \
200  proclist_node_get((iter).cur, \
201  offsetof(PGPROC, link_member))->next; \
202  (iter).cur != INVALID_PGPROCNO; \
203  (iter).cur = (iter).next, \
204  (iter).next = (iter).cur == INVALID_PGPROCNO ? INVALID_PGPROCNO : \
205  proclist_node_get((iter).cur, \
206  offsetof(PGPROC, link_member))->next)
207 
208 #endif
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:162
#define GetPGProcByNumber(n)
Definition: proc.h:263
static void proclist_delete_offset(proclist_head *list, int procno, size_t node_offset)
Definition: proclist.h:111
static proclist_node * proclist_node_get(int procno, size_t node_offset)
Definition: proclist.h:48
#define INVALID_PGPROCNO
Definition: proc.h:76
static void proclist_push_tail_offset(proclist_head *list, int procno, size_t node_offset)
Definition: proclist.h:85
#define Assert(condition)
Definition: c.h:675
static bool proclist_is_empty(proclist_head *list)
Definition: proclist.h:38
tuple list
Definition: sort-test.py:11
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:134
Definition: proc.h:94