Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * shmqueue.c
4 : * shared memory linked lists
5 : *
6 : * Portions Copyright (c) 1996-2017, 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 182241 : SHMQueueInit(SHM_QUEUE *queue)
37 : {
38 182241 : Assert(ShmemAddrIsValid(queue));
39 182241 : queue->prev = queue->next = queue;
40 182241 : }
41 :
42 : /*
43 : * SHMQueueIsDetached -- TRUE if element is not currently
44 : * in a queue.
45 : */
46 : bool
47 362 : SHMQueueIsDetached(const SHM_QUEUE *queue)
48 : {
49 362 : Assert(ShmemAddrIsValid(queue));
50 362 : return (queue->prev == NULL);
51 : }
52 :
53 : /*
54 : * SHMQueueElemInit -- clear an element's links
55 : */
56 : void
57 698 : SHMQueueElemInit(SHM_QUEUE *queue)
58 : {
59 698 : Assert(ShmemAddrIsValid(queue));
60 698 : queue->prev = queue->next = NULL;
61 698 : }
62 :
63 : /*
64 : * SHMQueueDelete -- remove an element from the queue and
65 : * close the links
66 : */
67 : void
68 174654 : SHMQueueDelete(SHM_QUEUE *queue)
69 : {
70 174654 : SHM_QUEUE *nextElem = queue->next;
71 174654 : SHM_QUEUE *prevElem = queue->prev;
72 :
73 174654 : Assert(ShmemAddrIsValid(queue));
74 174654 : Assert(ShmemAddrIsValid(nextElem));
75 174654 : Assert(ShmemAddrIsValid(prevElem));
76 :
77 174654 : prevElem->next = queue->next;
78 174654 : nextElem->prev = queue->prev;
79 :
80 174654 : queue->prev = queue->next = NULL;
81 174654 : }
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 208382 : SHMQueueInsertBefore(SHM_QUEUE *queue, SHM_QUEUE *elem)
90 : {
91 208382 : SHM_QUEUE *prevPtr = queue->prev;
92 :
93 208382 : Assert(ShmemAddrIsValid(queue));
94 208382 : Assert(ShmemAddrIsValid(elem));
95 :
96 208382 : elem->next = prevPtr->next;
97 208382 : elem->prev = queue->prev;
98 208382 : queue->prev = elem;
99 208382 : prevPtr->next = elem;
100 208382 : }
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 0 : SHMQueueInsertAfter(SHM_QUEUE *queue, SHM_QUEUE *elem)
109 : {
110 0 : SHM_QUEUE *nextPtr = queue->next;
111 :
112 0 : Assert(ShmemAddrIsValid(queue));
113 0 : Assert(ShmemAddrIsValid(elem));
114 :
115 0 : elem->prev = nextPtr->prev;
116 0 : elem->next = queue->next;
117 0 : queue->next = elem;
118 0 : nextPtr->prev = elem;
119 0 : }
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 907534 : SHMQueueNext(const SHM_QUEUE *queue, const SHM_QUEUE *curElem, Size linkOffset)
146 : {
147 907534 : SHM_QUEUE *elemPtr = curElem->next;
148 :
149 907534 : Assert(ShmemAddrIsValid(curElem));
150 :
151 907534 : if (elemPtr == queue) /* back to the queue head? */
152 843032 : return NULL;
153 :
154 64502 : 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 0 : SHMQueuePrev(const SHM_QUEUE *queue, const SHM_QUEUE *curElem, Size linkOffset)
165 : {
166 0 : SHM_QUEUE *elemPtr = curElem->prev;
167 :
168 0 : Assert(ShmemAddrIsValid(curElem));
169 :
170 0 : if (elemPtr == queue) /* back to the queue head? */
171 0 : return NULL;
172 :
173 0 : return (Pointer) (((char *) elemPtr) - linkOffset);
174 : }
175 :
176 : /*
177 : * SHMQueueEmpty -- TRUE if queue head is only element, FALSE otherwise
178 : */
179 : bool
180 97250 : SHMQueueEmpty(const SHM_QUEUE *queue)
181 : {
182 97250 : Assert(ShmemAddrIsValid(queue));
183 :
184 97250 : if (queue->prev == queue)
185 : {
186 97247 : Assert(queue->next == queue);
187 97247 : return TRUE;
188 : }
189 3 : return FALSE;
190 : }
|
