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