Mercurial > cgi-bin > hgwebdir.cgi > VMS > C_Libraries > Queue_impl

annotate PrivateQueue.c @ 18:7c9e00ff1bf4

find changesets by author, revision, files, or words in the commit message
fixed queue enlarging function
author Merten Sach <msach@mailbox.tu-berlin.de>
date Wed, 22 Jun 2011 18:49:17 +0200
parents 1e93e5dbeda1
children 677afc259a58
rev   line source
Me@0 1 /*
Me@8 2 * Copyright 2009 OpenSourceStewardshipFoundation.org
Me@0 3 * Licensed under GNU General Public License version 2
Me@0 4 *
Me@0 5 * Author: seanhalle@yahoo.com
Me@0 6 */
Me@0 7
Me@0 8
Me@0 9 #include <stdio.h>
Me@0 10 #include <string.h>
Me@0 11 #include <errno.h>
Me@0 12 #include <stdlib.h>
Me@0 13
Me@0 14 #include "PrivateQueue.h"
msach@17 15 #include "../vmalloc.h"
Me@0 16
Me@0 17
Me@0 18
Me@0 19 //===========================================================================
Me@0 20
Me@0 21 /*This kind of queue is private to a single core at a time -- has no
Me@0 22 * synchronizations
Me@0 23 */
Me@0 24
Me@16 25 PrivQueueStruc* makeVMSPrivQ()
Me@0 26 {
msach@17 27 PrivQueueStruc *retQ;
msach@17 28 retQ = VMS__malloc( sizeof( PrivQueueStruc ) );
msach@17 29 retQ->startOfData = (void*)VMS__malloc( 1024 * sizeof(void *) );
Me@14 30 memset( retQ->startOfData, 0, 1024 );
Me@14 31
Me@0 32 retQ->extractPos = &(retQ->startOfData[0]); //side by side == empty
Me@0 33 retQ->insertPos = &(retQ->startOfData[1]); // so start pos's have to be
Me@0 34 retQ->endOfData = &(retQ->startOfData[1023]);
Me@0 35
Me@0 36 return retQ;
Me@0 37 }
Me@0 38
Me@2 39
Me@2 40 void
Me@2 41 enlargePrivQ( PrivQueueStruc *Q )
msach@18 42 { size_t oldSize, newSize;
Me@0 43 void **oldStartOfData;
Me@0 44
msach@18 45 oldSize = Q->endOfData - Q->startOfData + 1;
Me@0 46 newSize = 2 * oldSize;
Me@6 47 oldStartOfData = Q->startOfData;
msach@18 48 Q->startOfData = VMS__malloc( newSize * sizeof(void*));
msach@18 49 //copy second half
msach@18 50 size_t secondHalfSize = Q->endOfData - Q->extractPos + 1;
msach@18 51 memcpy(Q->startOfData,Q->extractPos, secondHalfSize * sizeof(void*));
msach@18 52 //copy first half
msach@18 53 memcpy(Q->startOfData + secondHalfSize, oldStartOfData,
msach@18 54 (oldSize-secondHalfSize) * sizeof(void*));
Me@9 55 VMS__free(oldStartOfData);
Me@0 56
msach@18 57 Q->extractPos = Q->startOfData;
msach@18 58 Q->insertPos = Q->startOfData + oldSize - 1;
Me@0 59 Q->endOfData = &(Q->startOfData[newSize - 1]);
Me@0 60 }
Me@0 61
Me@0 62
Me@0 63 /*Returns NULL when queue is empty
Me@0 64 */
Me@0 65 void* readPrivQ( PrivQueueStruc* Q )
Me@0 66 { void *out = 0;
Me@2 67 void **startOfData = Q->startOfData;
Me@2 68 void **endOfData = Q->endOfData;
Me@0 69
Me@2 70 void **insertPos = Q->insertPos;
Me@2 71 void **extractPos = Q->extractPos;
Me@0 72
Me@6 73 //if not empty -- (extract is just below insert when empty)
Me@0 74 if( insertPos - extractPos != 1 &&
Me@0 75 !(extractPos == endOfData && insertPos == startOfData))
Me@0 76 { //move before read
Me@0 77 if( extractPos == endOfData ) //write new pos exactly once, correctly
Me@0 78 { Q->extractPos = startOfData; //can't overrun then fix it 'cause
Me@0 79 } // other thread might read bad pos
Me@0 80 else
Me@0 81 { Q->extractPos++;
Me@0 82 }
Me@0 83 out = *(Q->extractPos);
Me@0 84 return out;
Me@0 85 }
Me@0 86 //Q is empty
Me@0 87 return NULL;
Me@0 88 }
Me@0 89
Me@11 90 int32
Me@11 91 numInPrivQ( PrivQueueStruc *Q )
Me@11 92 { int32 size, numIn;
Me@11 93
Me@11 94 if( Q->insertPos < Q->extractPos )
Me@11 95 { //insert has wrapped around so numIn is:
Me@11 96 // insertPos + size - extractPos -- Consider, is empty when
Me@11 97 // extractPos = endOfData and insert = start -- correctly get zero
Me@11 98 size = Q->endOfData - Q->startOfData;
Me@11 99 numIn = Q->insertPos + size - Q->extractPos;
Me@11 100 }
Me@11 101 else
Me@11 102 {
Me@11 103 numIn = Q->insertPos - Q->extractPos -1;//-1 bec empty @ side-by-side
Me@11 104 }
Me@11 105 return numIn;
Me@11 106 }
Me@11 107
Me@2 108
Me@2 109 /*Expands the queue size automatically when it's full
Me@2 110 */
Me@2 111 void
Me@6 112 writePrivQ( void * in, PrivQueueStruc* Q )
Me@2 113 {
msach@18 114 while(1){
msach@18 115 void **startOfData = Q->startOfData;
msach@18 116 void **endOfData = Q->endOfData;
Me@2 117
msach@18 118 void **insertPos = Q->insertPos;
msach@18 119 void **extractPos = Q->extractPos;
msach@18 120
msach@18 121 //Full? (insert is just below extract when full)
msach@18 122 if( extractPos - insertPos != 1 &&
msach@18 123 !(insertPos == endOfData && extractPos == startOfData))
msach@18 124 { *(Q->insertPos) = in; //insert before move
msach@18 125 if( insertPos == endOfData ) //write new pos exactly once, correctly
msach@18 126 { Q->insertPos = startOfData;
msach@18 127 }
msach@18 128 else
msach@18 129 { Q->insertPos++;
msach@18 130 }
msach@18 131 return;
msach@18 132 }
msach@18 133 //Q is full
msach@18 134 enlargePrivQ( Q );
msach@18 135 }
Me@2 136 }
Me@2 137
Me@2 138
Me@0 139 /*Returns false when the queue was full.
Me@0 140 * have option of calling make_larger_PrivQ to make more room, then try again
Me@0 141 */
Me@6 142 int writeIfSpacePrivQ( void * in, PrivQueueStruc* Q )
Me@0 143 {
Me@2 144 void **startOfData = Q->startOfData;
Me@2 145 void **endOfData = Q->endOfData;
Me@2 146
Me@2 147 void **insertPos = Q->insertPos;
Me@2 148 void **extractPos = Q->extractPos;
Me@0 149
Me@0 150 if( extractPos - insertPos != 1 &&
Me@0 151 !(insertPos == endOfData && extractPos == startOfData))
Me@2 152 { *(Q->insertPos) = in; //insert before move
Me@0 153 if( insertPos == endOfData ) //write new pos exactly once, correctly
Me@0 154 { Q->insertPos = startOfData;
Me@0 155 }
Me@0 156 else
Me@0 157 { Q->insertPos++;
Me@0 158 }
Me@0 159 return TRUE;
Me@0 160 }
Me@0 161 //Q is full
Me@0 162 return FALSE;
Me@0 163 }
Me@9 164
SeanHalle@12 165 /*Treats queue as a stack -- no matter contents, if read done right after
SeanHalle@12 166 * a push, then the pushed item is what comes out.
SeanHalle@12 167 * Expands the queue size automatically when it's full.
SeanHalle@12 168 */
SeanHalle@12 169 void
SeanHalle@12 170 pushPrivQ( void * in, PrivQueueStruc* Q )
SeanHalle@12 171 {
msach@18 172 while(1){
msach@18 173 void **startOfData = Q->startOfData;
msach@18 174 void **endOfData = Q->endOfData;
SeanHalle@12 175
msach@18 176 void **insertPos = Q->insertPos;
msach@18 177 void **extractPos = Q->extractPos;
SeanHalle@12 178
msach@18 179 //Full? (insert is just below extract when full)
msach@18 180 if( extractPos - insertPos != 1 &&
msach@18 181 !(insertPos == endOfData && extractPos == startOfData))
msach@18 182 { //insert -- but go backwards, inserting at read position then
msach@18 183 // move read pos backwards
msach@18 184 *(Q->extractPos) = in;
msach@18 185 if( extractPos == startOfData ) //write new pos exactly once, correctly
msach@18 186 { Q->extractPos = endOfData; //can't overrun then fix it 'cause
msach@18 187 } // other thread might read bad pos
msach@18 188 else
msach@18 189 { Q->extractPos--;
msach@18 190 }
msach@18 191 return;
msach@18 192 }
msach@18 193 //Q is full
msach@18 194 enlargePrivQ( Q );
msach@18 195 }
SeanHalle@12 196 }
SeanHalle@12 197
Me@9 198 void
Me@9 199 freePrivQ( PrivQueueStruc *Q )
Me@9 200 {
Me@9 201 VMS__free( Q->startOfData );
Me@9 202 VMS__free( Q );
Me@9 203 }