PostgreSQL Source Code  git master
shmqueue.c
Go to the documentation of this file.
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
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
48 {
49  Assert(ShmemAddrIsValid(queue));
50  return (queue->prev == NULL);
51 }
52 
53 /*
54  * SHMQueueElemInit -- clear an element's links
55  */
56 void
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
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
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
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 
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 
173  return (Pointer) (((char *) elemPtr) - linkOffset);
174 }
175 
176 /*
177  * SHMQueueEmpty -- true if queue head is only element, false otherwise
178  */
179 bool
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 }
Pointer SHMQueuePrev(const SHM_QUEUE *queue, const SHM_QUEUE *curElem, Size linkOffset)
Definition: shmqueue.c:164
struct SHM_QUEUE * next
Definition: shmem.h:31
void SHMQueueInsertBefore(SHM_QUEUE *queue, SHM_QUEUE *elem)
Definition: shmqueue.c:89
char * Pointer
Definition: c.h:273
void SHMQueueInsertAfter(SHM_QUEUE *queue, SHM_QUEUE *elem)
Definition: shmqueue.c:108
bool SHMQueueEmpty(const SHM_QUEUE *queue)
Definition: shmqueue.c:180
Pointer SHMQueueNext(const SHM_QUEUE *queue, const SHM_QUEUE *curElem, Size linkOffset)
Definition: shmqueue.c:145
bool ShmemAddrIsValid(const void *addr)
Definition: shmem.c:263
struct SHM_QUEUE * prev
Definition: shmem.h:30
#define Assert(condition)
Definition: c.h:670
bool SHMQueueIsDetached(const SHM_QUEUE *queue)
Definition: shmqueue.c:47
size_t Size
Definition: c.h:404
void SHMQueueElemInit(SHM_QUEUE *queue)
Definition: shmqueue.c:57
void SHMQueueInit(SHM_QUEUE *queue)
Definition: shmqueue.c:36
void SHMQueueDelete(SHM_QUEUE *queue)
Definition: shmqueue.c:68