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

annotate PrivateQueue.c @ 42:c54f7e0a9d11

find changesets by author, revision, files, or words in the commit message
fix peek + debug code
author Nina Engelhardt <nengel@mailbox.tu-berlin.de>
date Wed, 06 Mar 2013 14:33:55 +0100
parents 8fcbe46de60a
children 0b3e087a6d37
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)
nengel@42 152 if (insertPos - extractPos != 1 &&
nengel@42 153 !(extractPos == endOfData && insertPos == startOfData)) { //move before read
nengel@42 154 if (extractPos == endOfData) //write new pos exactly once, correctly
nengel@42 155 {
nengel@42 156 out = *(startOfData); //can't overrun then fix it 'cause
nengel@42 157 }// other thread might read bad pos
nengel@42 158 else {
nengel@42 159 out = *(Q->extractPos + 1);
nengel@42 160 }
nengel@42 161
nengel@42 162 return out;
seanhalle@37 163 }
seanhalle@37 164 //Q is empty
seanhalle@37 165 return NULL;
seanhalle@37 166 }
seanhalle@37 167
Me@19 168 /*Returns NULL when queue is empty
Me@19 169 */
nengel@41 170 void* readPrivQ(PrivQueueStruc* Q) {
nengel@41 171
nengel@41 172 void *out = 0;
nengel@41 173 void **startOfData = Q->startOfData;
nengel@41 174 void **endOfData = Q->endOfData;
Me@19 175
nengel@41 176 void **insertPos = Q->insertPos;
nengel@41 177 void **extractPos = Q->extractPos;
Me@19 178
nengel@41 179 //if not empty -- (extract is just below insert when empty)
nengel@41 180 if (insertPos - extractPos != 1 &&
nengel@41 181 !(extractPos == endOfData && insertPos == startOfData)) { //move before read
nengel@41 182 if (extractPos == endOfData) //write new pos exactly once, correctly
nengel@41 183 {
nengel@41 184 Q->extractPos = startOfData; //can't overrun then fix it 'cause
nengel@41 185 }// other thread might read bad pos
nengel@41 186 else {
nengel@41 187 Q->extractPos++;
nengel@41 188 }
nengel@41 189 out = *(Q->extractPos);
nengel@42 190 //*(Q->extractPos) = NULL;
nengel@42 191 #ifdef DEBUG_PRIVATE_Q
nengel@42 192 Q->numReads++;
nengel@42 193 #endif
nengel@41 194 return out;
Me@19 195 }
nengel@41 196 //Q is empty
nengel@41 197 return NULL;
nengel@41 198 }
Me@19 199 /*Expands the queue size automatically when it's full
Me@19 200 */
Me@19 201 void
nengel@41 202 writePrivQ(void * in, PrivQueueStruc* Q) {
Me@19 203
nengel@41 204 #ifdef DEBUG_PRIVATE_Q
nengel@41 205 Q->numWrites++;
nengel@41 206 #endif
nengel@41 207
nengel@41 208 //tryAgain:
nengel@41 209 //Full? (insert is just below extract when full)
nengel@41 210 if ((Q->extractPos - Q->insertPos) == 1 ||
nengel@41 211 (Q->insertPos == Q->endOfData && Q->extractPos == Q->startOfData)) {
nengel@41 212 enlargePrivQ(Q);
Me@19 213 }
nengel@41 214
nengel@41 215 *(Q->insertPos) = in; //insert before move
nengel@41 216 if (Q->insertPos == Q->endOfData) //write new pos exactly once, correctly
nengel@41 217 {
nengel@41 218 Q->insertPos = Q->startOfData;
nengel@41 219 } else {
nengel@41 220 Q->insertPos++;
nengel@41 221 }
nengel@41 222 return;
nengel@41 223
nengel@41 224 //Q is full
nengel@41 225
nengel@41 226 //goto tryAgain;
nengel@41 227 }
Me@19 228
Me@19 229
Me@19 230 /*Returns false when the queue was full.
Me@19 231 * have option of calling make_larger_PrivQ to make more room, then try again
Me@19 232 */
seanhalle@35 233 bool32
seanhalle@35 234 writeIfSpacePrivQ( void * in, PrivQueueStruc* Q )
Me@19 235 {
Me@19 236 void **startOfData = Q->startOfData;
Me@19 237 void **endOfData = Q->endOfData;
Me@19 238
Me@19 239 void **insertPos = Q->insertPos;
Me@19 240 void **extractPos = Q->extractPos;
Me@19 241
Me@19 242 if( extractPos - insertPos != 1 &&
Me@19 243 !(insertPos == endOfData && extractPos == startOfData))
Me@19 244 { *(Q->insertPos) = in; //insert before move
Me@19 245 if( insertPos == endOfData ) //write new pos exactly once, correctly
Me@19 246 { Q->insertPos = startOfData;
Me@19 247 }
Me@19 248 else
Me@19 249 { Q->insertPos++;
Me@19 250 }
nengel@41 251 #ifdef DEBUG_PRIVATE_Q
nengel@41 252 Q->numWrites++;
nengel@41 253 #endif
Me@19 254 return TRUE;
Me@19 255 }
Me@19 256 //Q is full
Me@19 257 return FALSE;
Me@19 258 }
seanhalle@27 259
seanhalle@32 260 int32
seanhalle@32 261 numInPrivQ( PrivQueueStruc *Q )
seanhalle@32 262 { int32 size, numIn;
seanhalle@32 263
seanhalle@32 264 if( Q->insertPos < Q->extractPos )
seanhalle@32 265 { //insert has wrapped around so numIn is:
seanhalle@32 266 // insertPos + size - extractPos -- Consider, is empty when
seanhalle@32 267 // extractPos = endOfData and insert = start -- correctly get zero
seanhalle@33 268 size = Q->endOfData - Q->startOfData + 1; //sz of 10 is 0..9
seanhalle@33 269 numIn = Q->insertPos - Q->extractPos + size - 1; //-1 bec insrt empty
seanhalle@32 270 }
seanhalle@32 271 else
seanhalle@32 272 {
seanhalle@33 273 numIn = Q->insertPos - Q->extractPos -1;//-1 bec insertPos empty
seanhalle@32 274 }
seanhalle@32 275 return numIn;
seanhalle@32 276 }
seanhalle@32 277
seanhalle@32 278
seanhalle@32 279 /*Treats queue as a stack -- no matter contents, if read done right after
seanhalle@32 280 * a push, then the pushed item is what comes out.
seanhalle@32 281 * Expands the queue size automatically when it's full.
seanhalle@32 282 */
seanhalle@32 283 void
seanhalle@32 284 pushPrivQ( void * in, PrivQueueStruc* Q )
seanhalle@32 285 {
nengel@41 286 #ifdef DEBUG_PRIVATE_Q
nengel@41 287 Q->numWrites++;
nengel@41 288 #endif
seanhalle@32 289 while(1){
seanhalle@32 290 void **startOfData = Q->startOfData;
seanhalle@32 291 void **endOfData = Q->endOfData;
seanhalle@32 292
seanhalle@32 293 void **insertPos = Q->insertPos;
seanhalle@32 294 void **extractPos = Q->extractPos;
seanhalle@32 295
seanhalle@32 296 //Full? (insert is just below extract when full)
seanhalle@32 297 if( extractPos - insertPos != 1 &&
seanhalle@32 298 !(insertPos == endOfData && extractPos == startOfData))
seanhalle@32 299 { //insert -- but go backwards, inserting at read position then
seanhalle@32 300 // move read pos backwards
seanhalle@32 301 *(Q->extractPos) = in;
seanhalle@32 302 if( extractPos == startOfData ) //write new pos exactly once, correctly
seanhalle@32 303 { Q->extractPos = endOfData; //can't overrun then fix it 'cause
seanhalle@32 304 } // other thread might read bad pos
seanhalle@32 305 else
seanhalle@32 306 { Q->extractPos--;
seanhalle@32 307 }
seanhalle@32 308 return;
seanhalle@32 309 }
seanhalle@32 310 //Q is full
seanhalle@32 311 enlargePrivQ( Q );
seanhalle@32 312 }
seanhalle@32 313 }
seanhalle@32 314
seanhalle@32 315
seanhalle@32 316 void
seanhalle@32 317 freePrivQ( PrivQueueStruc *Q )
seanhalle@32 318 {
seanhalle@32 319 //This free is not safe to use in wrapper lib nor app code!
seanhalle@32 320 VMS_int__free( Q->startOfData );
seanhalle@32 321 VMS_int__free( Q );
seanhalle@32 322 }