src/include/storage/proclist.h

   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-2024, 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_PROC_NUMBER;
  32 }
  33
  34 /*
  35  * Is the list empty?
  36  */
  37 static inline bool
  38 proclist_is_empty(const proclist_head *list)
  39 {
  40         return list->head == INVALID_PROC_NUMBER;
  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_PROC_NUMBER)
  66         {
  67                 Assert(list->tail == INVALID_PROC_NUMBER);
  68                 node->next = node->prev = INVALID_PROC_NUMBER;
  69                 list->head = list->tail = procno;
  70         }
  71         else
  72         {
  73                 Assert(list->tail != INVALID_PROC_NUMBER);
  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_PROC_NUMBER;
  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_PROC_NUMBER)
  94         {
  95                 Assert(list->head == INVALID_PROC_NUMBER);
  96                 node->next = node->prev = INVALID_PROC_NUMBER;
  97                 list->head = list->tail = procno;
  98         }
  99         else
 100         {
 101                 Assert(list->head != INVALID_PROC_NUMBER);
 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_PROC_NUMBER;
 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_PROC_NUMBER)
 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_PROC_NUMBER)
 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(const proclist_head *list, int procno,
 147                                                  size_t node_offset)
 148 {
 149         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         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_PROC_NUMBER || list->head == procno);
 164         Assert(node->next != INVALID_PROC_NUMBER || 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_PROC_NUMBER ? INVALID_PROC_NUMBER :        \
 211                          proclist_node_get((iter).cur,                                                                  \
 212                                                            offsetof(PGPROC, link_member))->next;                \
 213                  (iter).cur != INVALID_PROC_NUMBER;                                                                     \
 214                  (iter).cur = (iter).next,                                                                                      \
 215                  (iter).next = (iter).cur == INVALID_PROC_NUMBER ? INVALID_PROC_NUMBER :        \
 216                          proclist_node_get((iter).cur,                                                                  \
 217                                                            offsetof(PGPROC, link_member))->next)
 218
 219 #endif                                                  /* PROCLIST_H */