Mercurial > cgi-bin > hgwebdir.cgi > VMS > C_Libraries > Queue_impl

view PrivateQueue.c @ 43:d01d48b023ca

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