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