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

annotate PrivateQueue.c @ 48:1ea30ca7093c

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