1 /*------------------------------------------------------------------------- 2 * 3 * shmqueue.c 4 * shared memory linked lists 5 * 6 * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group 7 * Portions Copyright (c) 1994, Regents of the University of California 8 * 9 * 10 * IDENTIFICATION 11 * src/backend/storage/ipc/shmqueue.c 12 * 13 * NOTES 14 * 15 * Package for managing doubly-linked lists in shared memory. 16 * The only tricky thing is that SHM_QUEUE will usually be a field 17 * in a larger record. SHMQueueNext has to return a pointer 18 * to the record itself instead of a pointer to the SHMQueue field 19 * of the record. It takes an extra parameter and does some extra 20 * pointer arithmetic to do this correctly. 21 * 22 * NOTE: These are set up so they can be turned into macros some day. 23 * 24 *------------------------------------------------------------------------- 25 */ 26 #include "postgres.h" 27 28 #include "storage/shmem.h" 29 30 31 /* 32 * ShmemQueueInit -- make the head of a new queue point 33 * to itself 34 */ 35 void 36 SHMQueueInit(SHM_QUEUE *queue) 37 { 38 Assert(ShmemAddrIsValid(queue)); 39 queue->prev = queue->next = queue; 40 } 41 42 /* 43 * SHMQueueIsDetached -- true if element is not currently 44 * in a queue. 45 */ 46 bool 47 SHMQueueIsDetached(const SHM_QUEUE *queue) 48 { 49 Assert(ShmemAddrIsValid(queue)); 50 return (queue->prev == NULL); 51 } 52 53 /* 54 * SHMQueueElemInit -- clear an element's links 55 */ 56 void 57 SHMQueueElemInit(SHM_QUEUE *queue) 58 { 59 Assert(ShmemAddrIsValid(queue)); 60 queue->prev = queue->next = NULL; 61 } 62 63 /* 64 * SHMQueueDelete -- remove an element from the queue and 65 * close the links 66 */ 67 void 68 SHMQueueDelete(SHM_QUEUE *queue) 69 { 70 SHM_QUEUE *nextElem = queue->next; 71 SHM_QUEUE *prevElem = queue->prev; 72 73 Assert(ShmemAddrIsValid(queue)); 74 Assert(ShmemAddrIsValid(nextElem)); 75 Assert(ShmemAddrIsValid(prevElem)); 76 77 prevElem->next = queue->next; 78 nextElem->prev = queue->prev; 79 80 queue->prev = queue->next = NULL; 81 } 82 83 /* 84 * SHMQueueInsertBefore -- put elem in queue before the given queue 85 * element. Inserting "before" the queue head puts the elem 86 * at the tail of the queue. 87 */ 88 void 89 SHMQueueInsertBefore(SHM_QUEUE *queue, SHM_QUEUE *elem) 90 { 91 SHM_QUEUE *prevPtr = queue->prev; 92 93 Assert(ShmemAddrIsValid(queue)); 94 Assert(ShmemAddrIsValid(elem)); 95 96 elem->next = prevPtr->next; 97 elem->prev = queue->prev; 98 queue->prev = elem; 99 prevPtr->next = elem; 100 } 101 102 /* 103 * SHMQueueInsertAfter -- put elem in queue after the given queue 104 * element. Inserting "after" the queue head puts the elem 105 * at the head of the queue. 106 */ 107 void 108 SHMQueueInsertAfter(SHM_QUEUE *queue, SHM_QUEUE *elem) 109 { 110 SHM_QUEUE *nextPtr = queue->next; 111 112 Assert(ShmemAddrIsValid(queue)); 113 Assert(ShmemAddrIsValid(elem)); 114 115 elem->prev = nextPtr->prev; 116 elem->next = queue->next; 117 queue->next = elem; 118 nextPtr->prev = elem; 119 } 120 121 /*-------------------- 122 * SHMQueueNext -- Get the next element from a queue 123 * 124 * To start the iteration, pass the queue head as both queue and curElem. 125 * Returns NULL if no more elements. 126 * 127 * Next element is at curElem->next. If SHMQueue is part of 128 * a larger structure, we want to return a pointer to the 129 * whole structure rather than a pointer to its SHMQueue field. 130 * For example, 131 * struct { 132 * int stuff; 133 * SHMQueue elem; 134 * } ELEMType; 135 * When this element is in a queue, prevElem->next points at struct.elem. 136 * We subtract linkOffset to get the correct start address of the structure. 137 * 138 * calls to SHMQueueNext should take these parameters: 139 * &(queueHead), &(queueHead), offsetof(ELEMType, elem) 140 * or 141 * &(queueHead), &(curElem->elem), offsetof(ELEMType, elem) 142 *-------------------- 143 */ 144 Pointer 145 SHMQueueNext(const SHM_QUEUE *queue, const SHM_QUEUE *curElem, Size linkOffset) 146 { 147 SHM_QUEUE *elemPtr = curElem->next; 148 r_mark_regions(struct SN_env * z)149 Assert(ShmemAddrIsValid(curElem)); 150 151 if (elemPtr == queue) /* back to the queue head? */ 152 return NULL; 153 154 return (Pointer) (((char *) elemPtr) - linkOffset); 155 } 156 157 /*-------------------- 158 * SHMQueuePrev -- Get the previous element from a queue 159 * 160 * Same as SHMQueueNext, just starting at tail and moving towards head. 161 * All other comments and usage applies. 162 */ 163 Pointer 164 SHMQueuePrev(const SHM_QUEUE *queue, const SHM_QUEUE *curElem, Size linkOffset) 165 { 166 SHM_QUEUE *elemPtr = curElem->prev; 167 168 Assert(ShmemAddrIsValid(curElem)); 169 170 if (elemPtr == queue) /* back to the queue head? */ 171 return NULL; 172 r_main_suffix(struct SN_env * z)173 return (Pointer) (((char *) elemPtr) - linkOffset); 174 } 175 176 /* 177 * SHMQueueEmpty -- true if queue head is only element, false otherwise 178 */ 179 bool 180 SHMQueueEmpty(const SHM_QUEUE *queue) 181 { 182 Assert(ShmemAddrIsValid(queue)); 183 184 if (queue->prev == queue) 185 { 186 Assert(queue->next == queue); 187 return true; 188 } 189 return false; 190 } 191