granicus.if.org Git - postgresql/blob - src/backend/storage/ipc/shmqueue.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * shmqueue.c--
   4  *    shared memory linked lists
   5  *
   6  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  *
   9  * IDENTIFICATION
  10  *    $Header: /cvsroot/pgsql/src/backend/storage/ipc/shmqueue.c,v 1.2 1996/11/03 05:06:58 scrappy Exp $
  11  *
  12  * NOTES
  13  *
  14  * Package for managing doubly-linked lists in shared memory.
  15  * The only tricky thing is that SHM_QUEUE will usually be a field
  16  * in a larger record.  SHMQueueGetFirst has to return a pointer
  17  * to the record itself instead of a pointer to the SHMQueue field
  18  * of the record.  It takes an extra pointer and does some extra
  19  * pointer arithmetic to do this correctly.
  20  *
  21  * NOTE: These are set up so they can be turned into macros some day.
  22  *
  23  *-------------------------------------------------------------------------
  24  */
  25 #include <stdio.h>              /* for sprintf() */
  26 #include "postgres.h"
  27 #include "storage/shmem.h"      /* where the declarations go */
  28
  29 /*#define SHMQUEUE_DEBUG*/
  30 #ifdef SHMQUEUE_DEBUG
  31 #define SHMQUEUE_DEBUG_DEL      /* deletions */
  32 #define SHMQUEUE_DEBUG_HD       /* head inserts */
  33 #define SHMQUEUE_DEBUG_TL       /* tail inserts */
  34 #define SHMQUEUE_DEBUG_ELOG NOTICE
  35 #endif /* SHMQUEUE_DEBUG */
  36
  37 /*
  38  * ShmemQueueInit -- make the head of a new queue point
  39  *      to itself
  40  */
  41 void
  42 SHMQueueInit(SHM_QUEUE *queue)
  43 {
  44     Assert(SHM_PTR_VALID(queue));
  45     (queue)->prev = (queue)->next = MAKE_OFFSET(queue);
  46 }
  47
  48 /*
  49  * SHMQueueIsDetached -- TRUE if element is not currently
  50  *      in a queue.
  51  */
  52 bool
  53 SHMQueueIsDetached(SHM_QUEUE *queue)
  54 {
  55     Assert(SHM_PTR_VALID(queue));
  56     return ((queue)->prev == INVALID_OFFSET);
  57 }
  58
  59 /*
  60  * SHMQueueElemInit -- clear an element's links
  61  */
  62 void
  63 SHMQueueElemInit(SHM_QUEUE *queue)
  64 {
  65     Assert(SHM_PTR_VALID(queue));
  66     (queue)->prev = (queue)->next = INVALID_OFFSET;
  67 }
  68
  69 /*
  70  * SHMQueueDelete -- remove an element from the queue and
  71  *      close the links
  72  */
  73 void
  74 SHMQueueDelete(SHM_QUEUE *queue)
  75 {
  76     SHM_QUEUE *nextElem = (SHM_QUEUE *) MAKE_PTR((queue)->next);
  77     SHM_QUEUE *prevElem = (SHM_QUEUE *) MAKE_PTR((queue)->prev);
  78
  79     Assert(SHM_PTR_VALID(queue));
  80     Assert(SHM_PTR_VALID(nextElem));
  81     Assert(SHM_PTR_VALID(prevElem));
  82
  83 #ifdef SHMQUEUE_DEBUG_DEL
  84     dumpQ(queue, "in SHMQueueDelete: begin");
  85 #endif /* SHMQUEUE_DEBUG_DEL */
  86
  87     prevElem->next =  (queue)->next;
  88     nextElem->prev =  (queue)->prev;
  89
  90 #ifdef SHMQUEUE_DEBUG_DEL
  91     dumpQ((SHM_QUEUE *)MAKE_PTR(queue->prev), "in SHMQueueDelete: end");
  92 #endif /* SHMQUEUE_DEBUG_DEL */
  93 }
  94
  95 #ifdef SHMQUEUE_DEBUG
  96 void
  97 dumpQ(SHM_QUEUE *q, char *s)
  98 {
  99     char elem[16];
 100     char buf[1024];
 101     SHM_QUEUE   *start = q;
 102     int count = 0;
 103
 104     sprintf(buf, "q prevs: %x", MAKE_OFFSET(q));
 105     q = (SHM_QUEUE *)MAKE_PTR(q->prev);
 106     while (q != start)
 107         {
 108             sprintf(elem, "--->%x", MAKE_OFFSET(q));
 109             strcat(buf, elem);
 110             q = (SHM_QUEUE *)MAKE_PTR(q->prev);
 111             if (q->prev == MAKE_OFFSET(q))
 112                 break;
 113             if (count++ > 40)
 114                 {
 115                     strcat(buf, "BAD PREV QUEUE!!");
 116                     break;
 117                 }
 118         }
 119     sprintf(elem, "--->%x", MAKE_OFFSET(q));
 120     strcat(buf, elem);
 121     elog(SHMQUEUE_DEBUG_ELOG, "%s: %s", s, buf);
 122
 123     sprintf(buf, "q nexts: %x", MAKE_OFFSET(q));
 124     count = 0;
 125     q = (SHM_QUEUE *)MAKE_PTR(q->next);
 126     while (q != start)
 127         {
 128             sprintf(elem, "--->%x", MAKE_OFFSET(q));
 129             strcat(buf, elem);
 130             q = (SHM_QUEUE *)MAKE_PTR(q->next);
 131             if (q->next == MAKE_OFFSET(q))
 132                 break;
 133             if (count++ > 10)
 134                 {
 135                     strcat(buf, "BAD NEXT QUEUE!!");
 136                     break;
 137                 }
 138         }
 139     sprintf(elem, "--->%x", MAKE_OFFSET(q));
 140     strcat(buf, elem);
 141     elog(SHMQUEUE_DEBUG_ELOG, "%s: %s", s, buf);
 142 }
 143 #endif /* SHMQUEUE_DEBUG */
 144
 145 /*
 146  * SHMQueueInsertHD -- put elem in queue between the queue head
 147  *      and its "prev" element.
 148  */
 149 void
 150 SHMQueueInsertHD(SHM_QUEUE *queue, SHM_QUEUE *elem)
 151 {
 152     SHM_QUEUE *prevPtr = (SHM_QUEUE *) MAKE_PTR((queue)->prev);
 153     SHMEM_OFFSET        elemOffset = MAKE_OFFSET(elem);
 154
 155     Assert(SHM_PTR_VALID(queue));
 156     Assert(SHM_PTR_VALID(elem));
 157
 158 #ifdef SHMQUEUE_DEBUG_HD
 159     dumpQ(queue, "in SHMQueueInsertHD: begin");
 160 #endif /* SHMQUEUE_DEBUG_HD */
 161
 162     (elem)->next = prevPtr->next;
 163     (elem)->prev = queue->prev;
 164     (queue)->prev = elemOffset;
 165     prevPtr->next = elemOffset;
 166
 167 #ifdef SHMQUEUE_DEBUG_HD
 168     dumpQ(queue, "in SHMQueueInsertHD: end");
 169 #endif /* SHMQUEUE_DEBUG_HD */
 170 }
 171
 172 void
 173 SHMQueueInsertTL(SHM_QUEUE *queue, SHM_QUEUE *elem)
 174 {
 175     SHM_QUEUE *nextPtr = (SHM_QUEUE *) MAKE_PTR((queue)->next);
 176     SHMEM_OFFSET        elemOffset = MAKE_OFFSET(elem);
 177
 178     Assert(SHM_PTR_VALID(queue));
 179     Assert(SHM_PTR_VALID(elem));
 180
 181 #ifdef SHMQUEUE_DEBUG_TL
 182     dumpQ(queue, "in SHMQueueInsertTL: begin");
 183 #endif /* SHMQUEUE_DEBUG_TL */
 184
 185     (elem)->prev = nextPtr->prev;
 186     (elem)->next = queue->next;
 187     (queue)->next = elemOffset;
 188     nextPtr->prev = elemOffset;
 189
 190 #ifdef SHMQUEUE_DEBUG_TL
 191     dumpQ(queue, "in SHMQueueInsertTL: end");
 192 #endif /* SHMQUEUE_DEBUG_TL */
 193 }
 194
 195 /*
 196  * SHMQueueFirst -- Get the first element from a queue
 197  *
 198  * First element is queue->next.  If SHMQueue is part of
 199  * a larger structure, we want to return a pointer to the
 200  * whole structure rather than a pointer to its SHMQueue field.
 201  * I.E. struct {
 202  *      int             stuff;
 203  *      SHMQueue        elem;
 204  * } ELEMType;
 205  * when this element is in a queue (queue->next) is struct.elem.
 206  * nextQueue allows us to calculate the offset of the SHMQueue
 207  * field in the structure.
 208  *
 209  * call to SHMQueueFirst should take these parameters:
 210  *
 211  *   &(queueHead),&firstElem,&(firstElem->next)
 212  *
 213  * Note that firstElem may well be uninitialized.  if firstElem
 214  * is initially K, &(firstElem->next) will be K+ the offset to
 215  * next.
 216  */
 217 void
 218 SHMQueueFirst(SHM_QUEUE *queue, Pointer *nextPtrPtr, SHM_QUEUE *nextQueue)
 219 {
 220     SHM_QUEUE *elemPtr = (SHM_QUEUE *) MAKE_PTR((queue)->next);
 221
 222     Assert(SHM_PTR_VALID(queue));
 223     *nextPtrPtr = (Pointer) (((unsigned long) *nextPtrPtr) +
 224                           ((unsigned long) elemPtr) - ((unsigned long) nextQueue));
 225
 226     /*
 227       nextPtrPtr a ptr to a structure linked in the queue
 228       nextQueue is the SHMQueue field of the structure
 229       *nextPtrPtr - nextQueue is 0 minus the offset of the queue
 230       field n the record
 231       elemPtr + (*nextPtrPtr - nexQueue) is the start of the
 232       structure containing elemPtr.
 233       */
 234 }
 235
 236 /*
 237  * SHMQueueEmpty -- TRUE if queue head is only element, FALSE otherwise
 238  */
 239 bool
 240 SHMQueueEmpty(SHM_QUEUE *queue)
 241 {
 242     Assert(SHM_PTR_VALID(queue));
 243
 244     if (queue->prev == MAKE_OFFSET(queue))
 245         {
 246             Assert(queue->next = MAKE_OFFSET(queue));
 247             return(TRUE);
 248         }
 249     return(FALSE);
 250 }