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