Mercurial > cgi-bin > hgwebdir.cgi > VMS > C_Libraries > Queue_impl
view PrivateQueue.c @ 41:8fcbe46de60a
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 |
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))
154 {
155 out = *(Q->extractPos + 1);
156 return out;
157 }
158 //Q is empty
159 return NULL;
160 }
162 /*Returns NULL when queue is empty
163 */
164 void* readPrivQ(PrivQueueStruc* Q) {
165 #ifdef DEBUG_PRIVATE_Q
166 Q->numReads++;
167 #endif
169 void *out = 0;
170 void **startOfData = Q->startOfData;
171 void **endOfData = Q->endOfData;
173 void **insertPos = Q->insertPos;
174 void **extractPos = Q->extractPos;
176 //if not empty -- (extract is just below insert when empty)
177 if (insertPos - extractPos != 1 &&
178 !(extractPos == endOfData && insertPos == startOfData)) { //move before read
179 if (extractPos == endOfData) //write new pos exactly once, correctly
180 {
181 Q->extractPos = startOfData; //can't overrun then fix it 'cause
182 }// other thread might read bad pos
183 else {
184 Q->extractPos++;
185 }
186 out = *(Q->extractPos);
187 return out;
188 }
189 //Q is empty
190 return NULL;
191 }
192 /*Expands the queue size automatically when it's full
193 */
194 void
195 writePrivQ(void * in, PrivQueueStruc* Q) {
197 #ifdef DEBUG_PRIVATE_Q
198 Q->numWrites++;
199 #endif
201 //tryAgain:
202 //Full? (insert is just below extract when full)
203 if ((Q->extractPos - Q->insertPos) == 1 ||
204 (Q->insertPos == Q->endOfData && Q->extractPos == Q->startOfData)) {
205 enlargePrivQ(Q);
206 }
208 *(Q->insertPos) = in; //insert before move
209 if (Q->insertPos == Q->endOfData) //write new pos exactly once, correctly
210 {
211 Q->insertPos = Q->startOfData;
212 } else {
213 Q->insertPos++;
214 }
215 return;
217 //Q is full
219 //goto tryAgain;
220 }
223 /*Returns false when the queue was full.
224 * have option of calling make_larger_PrivQ to make more room, then try again
225 */
226 bool32
227 writeIfSpacePrivQ( void * in, PrivQueueStruc* Q )
228 {
229 void **startOfData = Q->startOfData;
230 void **endOfData = Q->endOfData;
232 void **insertPos = Q->insertPos;
233 void **extractPos = Q->extractPos;
235 if( extractPos - insertPos != 1 &&
236 !(insertPos == endOfData && extractPos == startOfData))
237 { *(Q->insertPos) = in; //insert before move
238 if( insertPos == endOfData ) //write new pos exactly once, correctly
239 { Q->insertPos = startOfData;
240 }
241 else
242 { Q->insertPos++;
243 }
244 #ifdef DEBUG_PRIVATE_Q
245 Q->numWrites++;
246 #endif
247 return TRUE;
248 }
249 //Q is full
250 return FALSE;
251 }
253 int32
254 numInPrivQ( PrivQueueStruc *Q )
255 { int32 size, numIn;
257 if( Q->insertPos < Q->extractPos )
258 { //insert has wrapped around so numIn is:
259 // insertPos + size - extractPos -- Consider, is empty when
260 // extractPos = endOfData and insert = start -- correctly get zero
261 size = Q->endOfData - Q->startOfData + 1; //sz of 10 is 0..9
262 numIn = Q->insertPos - Q->extractPos + size - 1; //-1 bec insrt empty
263 }
264 else
265 {
266 numIn = Q->insertPos - Q->extractPos -1;//-1 bec insertPos empty
267 }
268 return numIn;
269 }
272 /*Treats queue as a stack -- no matter contents, if read done right after
273 * a push, then the pushed item is what comes out.
274 * Expands the queue size automatically when it's full.
275 */
276 void
277 pushPrivQ( void * in, PrivQueueStruc* Q )
278 {
279 #ifdef DEBUG_PRIVATE_Q
280 Q->numWrites++;
281 #endif
282 while(1){
283 void **startOfData = Q->startOfData;
284 void **endOfData = Q->endOfData;
286 void **insertPos = Q->insertPos;
287 void **extractPos = Q->extractPos;
289 //Full? (insert is just below extract when full)
290 if( extractPos - insertPos != 1 &&
291 !(insertPos == endOfData && extractPos == startOfData))
292 { //insert -- but go backwards, inserting at read position then
293 // move read pos backwards
294 *(Q->extractPos) = in;
295 if( extractPos == startOfData ) //write new pos exactly once, correctly
296 { Q->extractPos = endOfData; //can't overrun then fix it 'cause
297 } // other thread might read bad pos
298 else
299 { Q->extractPos--;
300 }
301 return;
302 }
303 //Q is full
304 enlargePrivQ( Q );
305 }
306 }
309 void
310 freePrivQ( PrivQueueStruc *Q )
311 {
312 //This free is not safe to use in wrapper lib nor app code!
313 VMS_int__free( Q->startOfData );
314 VMS_int__free( Q );
315 }