1/*-------------------------------------------------------------------------
2 *
3 * shmqueue.c
4 * shared memory linked lists
5 *
6 * Portions Copyright (c) 1996-2019, 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 */
35void
36SHMQueueInit(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 */
46bool
47SHMQueueIsDetached(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 */
56void
57SHMQueueElemInit(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 */
67void
68SHMQueueDelete(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 */
88void
89SHMQueueInsertBefore(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 */
107void
108SHMQueueInsertAfter(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 */
144Pointer
145SHMQueueNext(const SHM_QUEUE *queue, const SHM_QUEUE *curElem, Size linkOffset)
146{
147 SHM_QUEUE *elemPtr = curElem->next;
148
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 */
163Pointer
164SHMQueuePrev(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
173 return (Pointer) (((char *) elemPtr) - linkOffset);
174}
175
176/*
177 * SHMQueueEmpty -- true if queue head is only element, false otherwise
178 */
179bool
180SHMQueueEmpty(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