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

annotate PrivateQueue.c @ 41:8fcbe46de60a

find changesets by author, revision, files, or words in the commit message
bugfixes - peek and enlarge now working properly
author Nina Engelhardt <nengel@mailbox.tu-berlin.de>
date Wed, 19 Dec 2012 15:38:08 +0100
parents b9cb01d8ce56
children c54f7e0a9d11
rev   line source
Me@19 1 /*
Me@19 2 * Copyright 2009 OpenSourceStewardshipFoundation.org
Me@19 3 * Licensed under GNU General Public License version 2
Me@19 4 *
Me@19 5 * NOTE: this version of SRSW correct as of April 25, 2010
Me@19 6 *
Me@19 7 * Author: seanhalle@yahoo.com
Me@19 8 */
Me@19 9
Me@19 10
nengel@41 11 #include <string.h>
nengel@41 12 #include <stdlib.h>
Me@19 13 #include <stdio.h>
Me@19 14
Me@19 15 #include "PrivateQueue.h"
Me@19 16
Me@19 17
Me@19 18
Me@19 19 //===========================================================================
Me@19 20
Me@19 21 /*This kind of queue is private to a single core at a time -- has no
Me@19 22 * synchronizations
Me@19 23 */
Me@19 24
Me@19 25 PrivQueueStruc* makePrivQ()
Me@19 26 {
Me@19 27 PrivQueueStruc* retQ;
seanhalle@32 28 //This malloc is not safe to use in wrapper lib nor app code!
seanhalle@32 29 retQ = (PrivQueueStruc *) VMS_int__malloc( sizeof( PrivQueueStruc ) );
Me@19 30
seanhalle@32 31 //This malloc is not safe to use in wrapper lib nor app code!
seanhalle@37 32 retQ->startOfData = VMS_int__malloc( 1024 * sizeof(void *) );
Me@19 33 memset( retQ->startOfData, 0, 1024 * sizeof(void *) );
Me@19 34 retQ->extractPos = &(retQ->startOfData[0]); //side by side == empty
Me@19 35 retQ->insertPos = &(retQ->startOfData[1]); // so start pos's have to be
Me@19 36 retQ->endOfData = &(retQ->startOfData[1023]);
Me@19 37
nengel@41 38 #ifdef DEBUG_PRIVATE_Q
nengel@41 39 retQ->numReads = 0;
nengel@41 40 retQ->numWrites =0;
nengel@41 41 #endif
nengel@41 42
Me@19 43 return retQ;
Me@19 44 }
Me@19 45
Me@19 46
Me@19 47 void
Me@19 48 enlargePrivQ( PrivQueueStruc *Q )
nengel@41 49 { size_t oldSize, newSize, topPartSize, bottPartSize;
nengel@41 50 char *insertPos, *extractPos;
nengel@41 51 char *oldStartOfData, *oldEndOfData, *newStartOfData, *newEndOfData;
nengel@41 52 size_t insertOffsetBytes, extractOffsetBytes;
nengel@41 53 char* copyStartAddr;
Me@19 54
nengel@41 55 #ifdef DEBUG_PRIVATE_Q
nengel@41 56 printf("Enlarging queue Q = %p\nnumReads = %d; numWrites = %d\n",Q,Q->numReads,Q->numWrites);
nengel@41 57 #endif
nengel@41 58
nengel@41 59 oldStartOfData = (char*)Q->startOfData;
nengel@41 60 oldEndOfData = (char*)(Q->endOfData + 1);
nengel@41 61 insertPos = (char*)Q->insertPos;
nengel@41 62 extractPos = (char*)Q->extractPos;
Me@19 63
seanhalle@32 64 //TODO: verify these get number of bytes correct
nengel@41 65 insertOffsetBytes = (insertPos - oldStartOfData);
nengel@41 66 extractOffsetBytes = (extractPos - oldStartOfData);
seanhalle@32 67
nengel@41 68 oldSize = oldEndOfData - oldStartOfData; //in bytes
seanhalle@32 69 newSize = 2 * oldSize;
seanhalle@32 70
nengel@41 71 #ifdef DEBUG_PRIVATE_Q
nengel@41 72 printf("Old size = %d, new size = %d\n",(int)oldSize,(int)newSize);
nengel@41 73 #endif
nengel@41 74
seanhalle@32 75 //This malloc is not safe to use in wrapper lib nor app code!
nengel@41 76 newStartOfData = (char *) VMS_int__malloc( newSize );
nengel@41 77 if(newStartOfData == NULL){
nengel@41 78 perror("malloc"); exit(1);
nengel@41 79 }
seanhalle@32 80 newEndOfData = newStartOfData + newSize; //all calcs in Bytes
nengel@41 81
nengel@41 82 //TODO: test all of this, for both cases
nengel@41 83 Q->startOfData = newStartOfData;
nengel@41 84 Q->endOfData = ((void **)newEndOfData) - 1;
seanhalle@32 85
seanhalle@32 86 //Moving the data and pointers to the new array is
seanhalle@32 87 //a little trickier than at first it seems.. the top part
seanhalle@32 88 // of old queue must be moved to the top part of new queue, while
seanhalle@32 89 // bottom part of old to bottom part of new, then the new insert
seanhalle@32 90 // and extract positions calculated by offset from top and bottom
seanhalle@32 91 //UNLESS the one case where old extract was at bottom and insert
seanhalle@32 92 // was at top.
seanhalle@32 93 //TODO: check that this is correct!
nengel@41 94 if( extractPos == oldStartOfData )
seanhalle@32 95 {
seanhalle@32 96 memcpy( newStartOfData, oldStartOfData, oldSize ); //oldSize is bytes
seanhalle@32 97 Q->extractPos = Q->startOfData; //start of valid data
nengel@41 98 Q->insertPos = (void**)(newStartOfData + insertOffsetBytes); //end of valid data
seanhalle@32 99 }
seanhalle@32 100 else //have to copy two parts separately, then calc positions
seanhalle@32 101 { //TODO: check end-addr, sizes, and new positions carefully
nengel@41 102
seanhalle@32 103 //copy top part, starting at extract up until end of data,
seanhalle@35 104 // into top of new array
nengel@41 105 topPartSize = oldEndOfData - extractPos;
nengel@41 106 copyStartAddr = newEndOfData - topPartSize;
nengel@41 107 memcpy( copyStartAddr, extractPos, topPartSize );
seanhalle@35 108 Q->extractPos = (void **)copyStartAddr; //extract just-copied data
seanhalle@35 109
seanhalle@32 110 //copy bottom part, from old start up to old insert,
seanhalle@35 111 // into bottom of new array
nengel@41 112 bottPartSize = insertPos - oldStartOfData; //-1 for empty insertPos
seanhalle@32 113 memcpy( newStartOfData, oldStartOfData, bottPartSize );
seanhalle@32 114 Q->insertPos = (void **)(newStartOfData + bottPartSize);
seanhalle@32 115 }
seanhalle@32 116 //This free is not safe to use in wrapper lib nor app code!
seanhalle@32 117 VMS_int__free(oldStartOfData);
Me@19 118 }
Me@19 119
Me@19 120
seanhalle@37 121 /*Returns TRUE when queue is empty
seanhalle@37 122 */
seanhalle@37 123 bool32 isEmptyPrivQ( PrivQueueStruc* Q )
seanhalle@37 124 { void *out = 0;
seanhalle@37 125 void **startOfData = Q->startOfData;
seanhalle@37 126 void **endOfData = Q->endOfData;
seanhalle@37 127
seanhalle@37 128 void **insertPos = Q->insertPos;
seanhalle@37 129 void **extractPos = Q->extractPos;
seanhalle@37 130
seanhalle@37 131 //if not empty -- (extract is just below insert when empty)
seanhalle@37 132 if( insertPos - extractPos != 1 &&
seanhalle@37 133 !(extractPos == endOfData && insertPos == startOfData))
seanhalle@37 134 {
seanhalle@37 135 return FALSE;
seanhalle@37 136 }
seanhalle@37 137 //Q is empty
seanhalle@37 138 return TRUE;
seanhalle@37 139 }
seanhalle@37 140
seanhalle@37 141 /*Returns NULL when queue is empty
seanhalle@37 142 */
seanhalle@37 143 void* peekPrivQ( PrivQueueStruc* Q )
seanhalle@37 144 { void *out = 0;
seanhalle@37 145 void **startOfData = Q->startOfData;
seanhalle@37 146 void **endOfData = Q->endOfData;
seanhalle@37 147
seanhalle@37 148 void **insertPos = Q->insertPos;
seanhalle@37 149 void **extractPos = Q->extractPos;
seanhalle@37 150
seanhalle@37 151 //if not empty -- (extract is just below insert when empty)
seanhalle@37 152 if( insertPos - extractPos != 1 &&
seanhalle@37 153 !(extractPos == endOfData && insertPos == startOfData))
seanhalle@37 154 {
nengel@41 155 out = *(Q->extractPos + 1);
seanhalle@37 156 return out;
seanhalle@37 157 }
seanhalle@37 158 //Q is empty
seanhalle@37 159 return NULL;
seanhalle@37 160 }
seanhalle@37 161
Me@19 162 /*Returns NULL when queue is empty
Me@19 163 */
nengel@41 164 void* readPrivQ(PrivQueueStruc* Q) {
nengel@41 165 #ifdef DEBUG_PRIVATE_Q
nengel@41 166 Q->numReads++;
nengel@41 167 #endif
nengel@41 168
nengel@41 169 void *out = 0;
nengel@41 170 void **startOfData = Q->startOfData;
nengel@41 171 void **endOfData = Q->endOfData;
Me@19 172
nengel@41 173 void **insertPos = Q->insertPos;
nengel@41 174 void **extractPos = Q->extractPos;
Me@19 175
nengel@41 176 //if not empty -- (extract is just below insert when empty)
nengel@41 177 if (insertPos - extractPos != 1 &&
nengel@41 178 !(extractPos == endOfData && insertPos == startOfData)) { //move before read
nengel@41 179 if (extractPos == endOfData) //write new pos exactly once, correctly
nengel@41 180 {
nengel@41 181 Q->extractPos = startOfData; //can't overrun then fix it 'cause
nengel@41 182 }// other thread might read bad pos
nengel@41 183 else {
nengel@41 184 Q->extractPos++;
nengel@41 185 }
nengel@41 186 out = *(Q->extractPos);
nengel@41 187 return out;
Me@19 188 }
nengel@41 189 //Q is empty
nengel@41 190 return NULL;
nengel@41 191 }
Me@19 192 /*Expands the queue size automatically when it's full
Me@19 193 */
Me@19 194 void
nengel@41 195 writePrivQ(void * in, PrivQueueStruc* Q) {
Me@19 196
nengel@41 197 #ifdef DEBUG_PRIVATE_Q
nengel@41 198 Q->numWrites++;
nengel@41 199 #endif
nengel@41 200
nengel@41 201 //tryAgain:
nengel@41 202 //Full? (insert is just below extract when full)
nengel@41 203 if ((Q->extractPos - Q->insertPos) == 1 ||
nengel@41 204 (Q->insertPos == Q->endOfData && Q->extractPos == Q->startOfData)) {
nengel@41 205 enlargePrivQ(Q);
Me@19 206 }
nengel@41 207
nengel@41 208 *(Q->insertPos) = in; //insert before move
nengel@41 209 if (Q->insertPos == Q->endOfData) //write new pos exactly once, correctly
nengel@41 210 {
nengel@41 211 Q->insertPos = Q->startOfData;
nengel@41 212 } else {
nengel@41 213 Q->insertPos++;
nengel@41 214 }
nengel@41 215 return;
nengel@41 216
nengel@41 217 //Q is full
nengel@41 218
nengel@41 219 //goto tryAgain;
nengel@41 220 }
Me@19 221
Me@19 222
Me@19 223 /*Returns false when the queue was full.
Me@19 224 * have option of calling make_larger_PrivQ to make more room, then try again
Me@19 225 */
seanhalle@35 226 bool32
seanhalle@35 227 writeIfSpacePrivQ( void * in, PrivQueueStruc* Q )
Me@19 228 {
Me@19 229 void **startOfData = Q->startOfData;
Me@19 230 void **endOfData = Q->endOfData;
Me@19 231
Me@19 232 void **insertPos = Q->insertPos;
Me@19 233 void **extractPos = Q->extractPos;
Me@19 234
Me@19 235 if( extractPos - insertPos != 1 &&
Me@19 236 !(insertPos == endOfData && extractPos == startOfData))
Me@19 237 { *(Q->insertPos) = in; //insert before move
Me@19 238 if( insertPos == endOfData ) //write new pos exactly once, correctly
Me@19 239 { Q->insertPos = startOfData;
Me@19 240 }
Me@19 241 else
Me@19 242 { Q->insertPos++;
Me@19 243 }
nengel@41 244 #ifdef DEBUG_PRIVATE_Q
nengel@41 245 Q->numWrites++;
nengel@41 246 #endif
Me@19 247 return TRUE;
Me@19 248 }
Me@19 249 //Q is full
Me@19 250 return FALSE;
Me@19 251 }
seanhalle@27 252
seanhalle@32 253 int32
seanhalle@32 254 numInPrivQ( PrivQueueStruc *Q )
seanhalle@32 255 { int32 size, numIn;
seanhalle@32 256
seanhalle@32 257 if( Q->insertPos < Q->extractPos )
seanhalle@32 258 { //insert has wrapped around so numIn is:
seanhalle@32 259 // insertPos + size - extractPos -- Consider, is empty when
seanhalle@32 260 // extractPos = endOfData and insert = start -- correctly get zero
seanhalle@33 261 size = Q->endOfData - Q->startOfData + 1; //sz of 10 is 0..9
seanhalle@33 262 numIn = Q->insertPos - Q->extractPos + size - 1; //-1 bec insrt empty
seanhalle@32 263 }
seanhalle@32 264 else
seanhalle@32 265 {
seanhalle@33 266 numIn = Q->insertPos - Q->extractPos -1;//-1 bec insertPos empty
seanhalle@32 267 }
seanhalle@32 268 return numIn;
seanhalle@32 269 }
seanhalle@32 270
seanhalle@32 271
seanhalle@32 272 /*Treats queue as a stack -- no matter contents, if read done right after
seanhalle@32 273 * a push, then the pushed item is what comes out.
seanhalle@32 274 * Expands the queue size automatically when it's full.
seanhalle@32 275 */
seanhalle@32 276 void
seanhalle@32 277 pushPrivQ( void * in, PrivQueueStruc* Q )
seanhalle@32 278 {
nengel@41 279 #ifdef DEBUG_PRIVATE_Q
nengel@41 280 Q->numWrites++;
nengel@41 281 #endif
seanhalle@32 282 while(1){
seanhalle@32 283 void **startOfData = Q->startOfData;
seanhalle@32 284 void **endOfData = Q->endOfData;
seanhalle@32 285
seanhalle@32 286 void **insertPos = Q->insertPos;
seanhalle@32 287 void **extractPos = Q->extractPos;
seanhalle@32 288
seanhalle@32 289 //Full? (insert is just below extract when full)
seanhalle@32 290 if( extractPos - insertPos != 1 &&
seanhalle@32 291 !(insertPos == endOfData && extractPos == startOfData))
seanhalle@32 292 { //insert -- but go backwards, inserting at read position then
seanhalle@32 293 // move read pos backwards
seanhalle@32 294 *(Q->extractPos) = in;
seanhalle@32 295 if( extractPos == startOfData ) //write new pos exactly once, correctly
seanhalle@32 296 { Q->extractPos = endOfData; //can't overrun then fix it 'cause
seanhalle@32 297 } // other thread might read bad pos
seanhalle@32 298 else
seanhalle@32 299 { Q->extractPos--;
seanhalle@32 300 }
seanhalle@32 301 return;
seanhalle@32 302 }
seanhalle@32 303 //Q is full
seanhalle@32 304 enlargePrivQ( Q );
seanhalle@32 305 }
seanhalle@32 306 }
seanhalle@32 307
seanhalle@32 308
seanhalle@32 309 void
seanhalle@32 310 freePrivQ( PrivQueueStruc *Q )
seanhalle@32 311 {
seanhalle@32 312 //This free is not safe to use in wrapper lib nor app code!
seanhalle@32 313 VMS_int__free( Q->startOfData );
seanhalle@32 314 VMS_int__free( Q );
seanhalle@32 315 }