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 */ 28 static inline void 29 proclist_init(proclist_head *list) 30 { 31 list->head = list->tail = INVALID_PGPROCNO; 32 } 33 34 /* 35 * Is the list empty? 36 */ 37 static inline bool 38 proclist_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 */ 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 146 proclist_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 */ 172 static inline PGPROC * 173 proclist_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