Header And Logo

PostgreSQL
| The world's most advanced open source database.

shmqueue.c

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * shmqueue.c
00004  *    shared memory linked lists
00005  *
00006  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00007  * Portions Copyright (c) 1994, Regents of the University of California
00008  *
00009  *
00010  * IDENTIFICATION
00011  *    src/backend/storage/ipc/shmqueue.c
00012  *
00013  * NOTES
00014  *
00015  * Package for managing doubly-linked lists in shared memory.
00016  * The only tricky thing is that SHM_QUEUE will usually be a field
00017  * in a larger record.  SHMQueueNext has to return a pointer
00018  * to the record itself instead of a pointer to the SHMQueue field
00019  * of the record.  It takes an extra parameter and does some extra
00020  * pointer arithmetic to do this correctly.
00021  *
00022  * NOTE: These are set up so they can be turned into macros some day.
00023  *
00024  *-------------------------------------------------------------------------
00025  */
00026 #include "postgres.h"
00027 
00028 #include "storage/shmem.h"
00029 
00030 
00031 /*
00032  * ShmemQueueInit -- make the head of a new queue point
00033  *      to itself
00034  */
00035 void
00036 SHMQueueInit(SHM_QUEUE *queue)
00037 {
00038     Assert(ShmemAddrIsValid(queue));
00039     queue->prev = queue->next = queue;
00040 }
00041 
00042 /*
00043  * SHMQueueIsDetached -- TRUE if element is not currently
00044  *      in a queue.
00045  */
00046 bool
00047 SHMQueueIsDetached(const SHM_QUEUE *queue)
00048 {
00049     Assert(ShmemAddrIsValid(queue));
00050     return (queue->prev == NULL);
00051 }
00052 
00053 /*
00054  * SHMQueueElemInit -- clear an element's links
00055  */
00056 void
00057 SHMQueueElemInit(SHM_QUEUE *queue)
00058 {
00059     Assert(ShmemAddrIsValid(queue));
00060     queue->prev = queue->next = NULL;
00061 }
00062 
00063 /*
00064  * SHMQueueDelete -- remove an element from the queue and
00065  *      close the links
00066  */
00067 void
00068 SHMQueueDelete(SHM_QUEUE *queue)
00069 {
00070     SHM_QUEUE  *nextElem = queue->next;
00071     SHM_QUEUE  *prevElem = queue->prev;
00072 
00073     Assert(ShmemAddrIsValid(queue));
00074     Assert(ShmemAddrIsValid(nextElem));
00075     Assert(ShmemAddrIsValid(prevElem));
00076 
00077     prevElem->next = queue->next;
00078     nextElem->prev = queue->prev;
00079 
00080     queue->prev = queue->next = NULL;
00081 }
00082 
00083 /*
00084  * SHMQueueInsertBefore -- put elem in queue before the given queue
00085  *      element.  Inserting "before" the queue head puts the elem
00086  *      at the tail of the queue.
00087  */
00088 void
00089 SHMQueueInsertBefore(SHM_QUEUE *queue, SHM_QUEUE *elem)
00090 {
00091     SHM_QUEUE  *prevPtr = queue->prev;
00092 
00093     Assert(ShmemAddrIsValid(queue));
00094     Assert(ShmemAddrIsValid(elem));
00095 
00096     elem->next = prevPtr->next;
00097     elem->prev = queue->prev;
00098     queue->prev = elem;
00099     prevPtr->next = elem;
00100 }
00101 
00102 /*
00103  * SHMQueueInsertAfter -- put elem in queue after the given queue
00104  *      element.  Inserting "after" the queue head puts the elem
00105  *      at the head of the queue.
00106  */
00107 void
00108 SHMQueueInsertAfter(SHM_QUEUE *queue, SHM_QUEUE *elem)
00109 {
00110     SHM_QUEUE  *nextPtr = queue->next;
00111 
00112     Assert(ShmemAddrIsValid(queue));
00113     Assert(ShmemAddrIsValid(elem));
00114 
00115     elem->prev = nextPtr->prev;
00116     elem->next = queue->next;
00117     queue->next = elem;
00118     nextPtr->prev = elem;
00119 }
00120 
00121 /*--------------------
00122  * SHMQueueNext -- Get the next element from a queue
00123  *
00124  * To start the iteration, pass the queue head as both queue and curElem.
00125  * Returns NULL if no more elements.
00126  *
00127  * Next element is at curElem->next.  If SHMQueue is part of
00128  * a larger structure, we want to return a pointer to the
00129  * whole structure rather than a pointer to its SHMQueue field.
00130  * For example,
00131  * struct {
00132  *      int             stuff;
00133  *      SHMQueue        elem;
00134  * } ELEMType;
00135  * When this element is in a queue, prevElem->next points at struct.elem.
00136  * We subtract linkOffset to get the correct start address of the structure.
00137  *
00138  * calls to SHMQueueNext should take these parameters:
00139  *   &(queueHead), &(queueHead), offsetof(ELEMType, elem)
00140  * or
00141  *   &(queueHead), &(curElem->elem), offsetof(ELEMType, elem)
00142  *--------------------
00143  */
00144 Pointer
00145 SHMQueueNext(const SHM_QUEUE *queue, const SHM_QUEUE *curElem, Size linkOffset)
00146 {
00147     SHM_QUEUE  *elemPtr = curElem->next;
00148 
00149     Assert(ShmemAddrIsValid(curElem));
00150 
00151     if (elemPtr == queue)       /* back to the queue head? */
00152         return NULL;
00153 
00154     return (Pointer) (((char *) elemPtr) - linkOffset);
00155 }
00156 
00157 /*--------------------
00158  * SHMQueuePrev -- Get the previous element from a queue
00159  *
00160  * Same as SHMQueueNext, just starting at tail and moving towards head.
00161  * All other comments and usage applies.
00162  */
00163 Pointer
00164 SHMQueuePrev(const SHM_QUEUE *queue, const SHM_QUEUE *curElem, Size linkOffset)
00165 {
00166     SHM_QUEUE  *elemPtr = curElem->prev;
00167 
00168     Assert(ShmemAddrIsValid(curElem));
00169 
00170     if (elemPtr == queue)       /* back to the queue head? */
00171         return NULL;
00172 
00173     return (Pointer) (((char *) elemPtr) - linkOffset);
00174 }
00175 
00176 /*
00177  * SHMQueueEmpty -- TRUE if queue head is only element, FALSE otherwise
00178  */
00179 bool
00180 SHMQueueEmpty(const SHM_QUEUE *queue)
00181 {
00182     Assert(ShmemAddrIsValid(queue));
00183 
00184     if (queue->prev == queue)
00185     {
00186         Assert(queue->next == queue);
00187         return TRUE;
00188     }
00189     return FALSE;
00190 }