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

annotate PrivateQueue.c @ 34:c5d2f2a94133

find changesets by author, revision, files, or words in the commit message
updated to fixed versions from MC_shared brch, then removed VMS_ from malloc
author Some Random Person <seanhalle@yahoo.com>
date Wed, 14 Mar 2012 23:02:28 -0700
parents 1ed562d601d9
children d6da470bbd38
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
Me@19 11 #include <stdio.h>
Me@19 12 #include <string.h>
Me@19 13 #include <errno.h>
Me@19 14 #include <stdlib.h>
Me@19 15
Me@19 16 #include "PrivateQueue.h"
Me@19 17
Me@19 18
Me@19 19
Me@19 20 //===========================================================================
Me@19 21
Me@19 22 /*This kind of queue is private to a single core at a time -- has no
Me@19 23 * synchronizations
Me@19 24 */
Me@19 25
Me@19 26 PrivQueueStruc* makePrivQ()
Me@19 27 {
Me@19 28 PrivQueueStruc* retQ;
seanhalle@34 29 //This malloc is not safe to use inside VMS-language!
Me@19 30 retQ = (PrivQueueStruc *) malloc( sizeof( PrivQueueStruc ) );
Me@19 31
seanhalle@34 32 //This malloc is not safe to use inside VMS-language!
Me@19 33 retQ->startOfData = malloc( 1024 * sizeof(void *) );
Me@19 34 memset( retQ->startOfData, 0, 1024 * sizeof(void *) );
Me@19 35 retQ->extractPos = &(retQ->startOfData[0]); //side by side == empty
Me@19 36 retQ->insertPos = &(retQ->startOfData[1]); // so start pos's have to be
Me@19 37 retQ->endOfData = &(retQ->startOfData[1023]);
Me@19 38
Me@19 39 return retQ;
Me@19 40 }
Me@19 41
Me@19 42
Me@19 43 void
Me@19 44 enlargePrivQ( PrivQueueStruc *Q )
seanhalle@34 45 { int32 oldSize, newSize;
seanhalle@34 46 int8 *insertPos, *extractPos;
seanhalle@34 47 int8 *oldStartOfData, *oldEndOfData, *newStartOfData, *newEndOfData;
seanhalle@34 48 int8 *insertOffsetBytes, *extractOffsetBytes;
Me@19 49
seanhalle@34 50 oldStartOfData = (int8 *)Q->startOfData;
seanhalle@34 51 oldEndOfData = (int8 *)Q->endOfData;
seanhalle@34 52 insertPos = (int8 *)Q->insertPos;
seanhalle@34 53 extractPos = (int8 *)Q->extractPos;
Me@19 54
seanhalle@34 55 //TODO: verify these get number of bytes correct
seanhalle@34 56 insertOffsetBytes = insertPos - oldStartOfData;
seanhalle@34 57 extractOffsetBytes = extractPos - oldStartOfData);
seanhalle@34 58
seanhalle@34 59 oldSize = endOfData - startOfData + 1; //in bytes
seanhalle@34 60 newSize = 2 * oldSize;
seanhalle@34 61
seanhalle@34 62 //This malloc is not safe to use inside VMS-language!
seanhalle@34 63 Q->startOfData = (void **)malloc( newSize );
seanhalle@34 64 newStartOfData = (int8 *)Q->startOfData;
seanhalle@34 65 newEndOfData = newStartOfData + newSize; //all calcs in Bytes
seanhalle@34 66 Q->endOfData = (void **)newEndOfData;
seanhalle@34 67
seanhalle@34 68 //TODO: test all of this, for both cases
seanhalle@34 69
seanhalle@34 70 //Moving the data and pointers to the new array is
seanhalle@34 71 //a little trickier than at first it seems.. the top part
seanhalle@34 72 // of old queue must be moved to the top part of new queue, while
seanhalle@34 73 // bottom part of old to bottom part of new, then the new insert
seanhalle@34 74 // and extract positions calculated by offset from top and bottom
seanhalle@34 75 //UNLESS the one case where old extract was at bottom and insert
seanhalle@34 76 // was at top.
seanhalle@34 77 //TODO: check that this is correct!
seanhalle@34 78 if( extractPos == startOfData && insertPos == endOfData )
seanhalle@34 79 {
seanhalle@34 80 memcpy( newStartOfData, oldStartOfData, oldSize ); //oldSize is bytes
seanhalle@34 81 Q->extractPos = Q->startOfData; //start of valid data
seanhalle@34 82 Q->insertPos = Q->startOfData + oldSize - 1; //end of valid data
seanhalle@34 83 }
seanhalle@34 84 else //have to copy two parts separately, then calc positions
seanhalle@34 85 { //TODO: check end-addr, sizes, and new positions carefully
seanhalle@34 86
seanhalle@34 87 //copy top part, starting at extract up until end of data,
seanhalle@34 88 // into top of new array
seanhalle@34 89 topPartSize = oldEndOfData - extractPos + 1; //+1 includes extractPos
seanhalle@34 90 copyStartAddr = newEndOfData - topPartSize + 1;//+1 cancels other
seanhalle@34 91 memcpy( copyStartAddr, Q->extractPos, topPartSize );
seanhalle@34 92 Q->extractPos = (void **)copyStartAddr; //extract just-copied data
seanhalle@34 93
seanhalle@34 94 //copy bottom part, from old start up to old insert,
seanhalle@34 95 // into bottom of new array
seanhalle@34 96 bottPartSize = oldSize - topPartSize - 1; //-1 for empty insertPos
seanhalle@34 97 memcpy( newStartOfData, oldStartOfData, bottPartSize );
seanhalle@34 98 Q->insertPos = (void **)(newStartOfData + bottPartSize);
seanhalle@34 99 }
seanhalle@34 100 //This free is not safe to use inside VMS-language!
seanhalle@34 101 free(oldStartOfData);
Me@19 102 }
Me@19 103
Me@19 104
Me@19 105 /*Returns NULL when queue is empty
Me@19 106 */
Me@19 107 void* readPrivQ( PrivQueueStruc* Q )
Me@19 108 { void *out = 0;
Me@19 109 void **startOfData = Q->startOfData;
Me@19 110 void **endOfData = Q->endOfData;
Me@19 111
Me@19 112 void **insertPos = Q->insertPos;
Me@19 113 void **extractPos = Q->extractPos;
Me@19 114
Me@19 115 //if not empty -- (extract is just below insert when empty)
Me@19 116 if( insertPos - extractPos != 1 &&
Me@19 117 !(extractPos == endOfData && insertPos == startOfData))
Me@19 118 { //move before read
Me@19 119 if( extractPos == endOfData ) //write new pos exactly once, correctly
Me@19 120 { Q->extractPos = startOfData; //can't overrun then fix it 'cause
Me@19 121 } // other thread might read bad pos
Me@19 122 else
Me@19 123 { Q->extractPos++;
Me@19 124 }
Me@19 125 out = *(Q->extractPos);
Me@19 126 return out;
Me@19 127 }
Me@19 128 //Q is empty
Me@19 129 return NULL;
Me@19 130 }
Me@19 131
Me@19 132
Me@19 133 /*Expands the queue size automatically when it's full
Me@19 134 */
Me@19 135 void
Me@19 136 writePrivQ( void * in, PrivQueueStruc* Q )
Me@19 137 {
Me@19 138 void **startOfData = Q->startOfData;
Me@19 139 void **endOfData = Q->endOfData;
Me@19 140
Me@19 141 void **insertPos = Q->insertPos;
Me@19 142 void **extractPos = Q->extractPos;
Me@19 143
Me@19 144 tryAgain:
Me@19 145 //Full? (insert is just below extract when full)
Me@19 146 if( extractPos - insertPos != 1 &&
Me@19 147 !(insertPos == endOfData && extractPos == startOfData))
Me@19 148 { *(Q->insertPos) = in; //insert before move
Me@19 149 if( insertPos == endOfData ) //write new pos exactly once, correctly
Me@19 150 { Q->insertPos = startOfData;
Me@19 151 }
Me@19 152 else
Me@19 153 { Q->insertPos++;
Me@19 154 }
Me@19 155 return;
Me@19 156 }
Me@19 157 //Q is full
Me@19 158 enlargePrivQ( Q );
Me@19 159 goto tryAgain;
Me@19 160 }
Me@19 161
Me@19 162
Me@19 163 /*Returns false when the queue was full.
Me@19 164 * have option of calling make_larger_PrivQ to make more room, then try again
Me@19 165 */
Me@19 166 int writeIfSpacePrivQ( void * in, PrivQueueStruc* Q )
Me@19 167 {
Me@19 168 void **startOfData = Q->startOfData;
Me@19 169 void **endOfData = Q->endOfData;
Me@19 170
Me@19 171 void **insertPos = Q->insertPos;
Me@19 172 void **extractPos = Q->extractPos;
Me@19 173
Me@19 174 if( extractPos - insertPos != 1 &&
Me@19 175 !(insertPos == endOfData && extractPos == startOfData))
Me@19 176 { *(Q->insertPos) = in; //insert before move
Me@19 177 if( insertPos == endOfData ) //write new pos exactly once, correctly
Me@19 178 { Q->insertPos = startOfData;
Me@19 179 }
Me@19 180 else
Me@19 181 { Q->insertPos++;
Me@19 182 }
Me@19 183 return TRUE;
Me@19 184 }
Me@19 185 //Q is full
Me@19 186 return FALSE;
Me@19 187 }
seanhalle@34 188
seanhalle@34 189 int32
seanhalle@34 190 numInPrivQ( PrivQueueStruc *Q )
seanhalle@34 191 { int32 size, numIn;
seanhalle@34 192
seanhalle@34 193 if( Q->insertPos < Q->extractPos )
seanhalle@34 194 { //insert has wrapped around so numIn is:
seanhalle@34 195 // insertPos + size - extractPos -- Consider, is empty when
seanhalle@34 196 // extractPos = endOfData and insert = start -- correctly get zero
seanhalle@34 197 size = Q->endOfData - Q->startOfData + 1; //sz of 10 is 0..9
seanhalle@34 198 numIn = Q->insertPos - Q->extractPos + size - 1; //-1 bec insrt empty
seanhalle@34 199 }
seanhalle@34 200 else
seanhalle@34 201 {
seanhalle@34 202 numIn = Q->insertPos - Q->extractPos -1;//-1 bec insertPos empty
seanhalle@34 203 }
seanhalle@34 204 return numIn;
seanhalle@34 205 }
seanhalle@34 206
seanhalle@34 207
seanhalle@34 208 /*Treats queue as a stack -- no matter contents, if read done right after
seanhalle@34 209 * a push, then the pushed item is what comes out.
seanhalle@34 210 * Expands the queue size automatically when it's full.
seanhalle@34 211 */
seanhalle@34 212 void
seanhalle@34 213 pushPrivQ( void * in, PrivQueueStruc* Q )
seanhalle@34 214 {
seanhalle@34 215 while(1){
seanhalle@34 216 void **startOfData = Q->startOfData;
seanhalle@34 217 void **endOfData = Q->endOfData;
seanhalle@34 218
seanhalle@34 219 void **insertPos = Q->insertPos;
seanhalle@34 220 void **extractPos = Q->extractPos;
seanhalle@34 221
seanhalle@34 222 //Full? (insert is just below extract when full)
seanhalle@34 223 if( extractPos - insertPos != 1 &&
seanhalle@34 224 !(insertPos == endOfData && extractPos == startOfData))
seanhalle@34 225 { //insert -- but go backwards, inserting at read position then
seanhalle@34 226 // move read pos backwards
seanhalle@34 227 *(Q->extractPos) = in;
seanhalle@34 228 if( extractPos == startOfData ) //write new pos exactly once, correctly
seanhalle@34 229 { Q->extractPos = endOfData; //can't overrun then fix it 'cause
seanhalle@34 230 } // other thread might read bad pos
seanhalle@34 231 else
seanhalle@34 232 { Q->extractPos--;
seanhalle@34 233 }
seanhalle@34 234 return;
seanhalle@34 235 }
seanhalle@34 236 //Q is full
seanhalle@34 237 enlargePrivQ( Q );
seanhalle@34 238 }
seanhalle@34 239 }
seanhalle@34 240
seanhalle@34 241
seanhalle@34 242 void
seanhalle@34 243 freePrivQ( PrivQueueStruc *Q )
seanhalle@34 244 {
seanhalle@34 245 //This free is not safe to use inside VMS-language!
seanhalle@34 246 free( Q->startOfData );
seanhalle@34 247 free( Q );
seanhalle@34 248 }