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