Mercurial > cgi-bin > hgwebdir.cgi > VMS > C_Libraries > Queue_impl
view PrivateQueue.c @ 32:a74011c0b78b
fixed expansion of queue, and added numInPrivQ and freePrivQ
| author | Some Random Person <seanhalle@yahoo.com> |
|---|---|
| date | Wed, 14 Mar 2012 22:48:50 -0700 |
| parents | bd38feb38c80 |
| children | 501206566d16 |
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 <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 *) VMS_int__malloc( sizeof( PrivQueueStruc ) );
32 //This malloc is not safe to use in wrapper lib nor app code!
33 retQ->startOfData = VMS_WL__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 void
44 enlargePrivQ( PrivQueueStruc *Q )
45 { int32 oldSize, newSize;
46 int8 *insertPos, *extractPos;
47 int8 *oldStartOfData, *oldEndOfData, *newStartOfData, *newEndOfData;
48 int8 *insertOffsetBytes, *extractOffsetBytes;
50 oldStartOfData = (int8 *)Q->startOfData;
51 oldEndOfData = (int8 *)Q->endOfData;
52 insertPos = (int8 *)Q->insertPos;
53 extractPos = (int8 *)Q->extractPos;
55 //TODO: verify these get number of bytes correct
56 insertOffsetBytes = insertPos - oldStartOfData;
57 extractOffsetBytes = extractPos - oldStartOfData);
59 oldSize = endOfData - startOfData + 1; //in bytes
60 newSize = 2 * oldSize;
62 //This malloc is not safe to use in wrapper lib nor app code!
63 Q->startOfData = (void **)VMS_int__malloc( newSize );
64 newStartOfData = (int8 *)Q->startOfData;
65 newEndOfData = newStartOfData + newSize; //all calcs in Bytes
66 Q->endOfData = (void **)newEndOfData;
68 //TODO: test all of this, for both cases
70 //Moving the data and pointers to the new array is
71 //a little trickier than at first it seems.. the top part
72 // of old queue must be moved to the top part of new queue, while
73 // bottom part of old to bottom part of new, then the new insert
74 // and extract positions calculated by offset from top and bottom
75 //UNLESS the one case where old extract was at bottom and insert
76 // was at top.
77 //TODO: check that this is correct!
78 if( extractPos == startOfData && insertPos == endOfData )
79 {
80 memcpy( newStartOfData, oldStartOfData, oldSize ); //oldSize is bytes
81 Q->extractPos = Q->startOfData; //start of valid data
82 Q->insertPos = Q->startOfData + oldSize - 1; //end of valid data
83 }
84 else //have to copy two parts separately, then calc positions
85 { //TODO: check end-addr, sizes, and new positions carefully
87 //copy top part, starting at extract up until end of data,
88 // into top of new array
89 topPartSize = oldEndOfData - extractPos + 1; //+1 includes extractPos
90 copyStartAddr = newEndOfData - topPartSize + 1;//+1 cancels other
91 memcpy( copyStartAddr, Q->extractPos, topPartSize );
92 Q->extractPos = (void **)copyStartAddr; //extract just-copied data
94 //copy bottom part, from old start up to old insert,
95 // into bottom of new array
96 bottPartSize = oldSize - topPartSize - 1; //-1 for empty insertPos
97 memcpy( newStartOfData, oldStartOfData, bottPartSize );
98 Q->insertPos = (void **)(newStartOfData + bottPartSize);
99 }
100 //This free is not safe to use in wrapper lib nor app code!
101 VMS_int__free(oldStartOfData);
102 }
105 /*Returns NULL when queue is empty
106 */
107 void* readPrivQ( PrivQueueStruc* Q )
108 { void *out = 0;
109 void **startOfData = Q->startOfData;
110 void **endOfData = Q->endOfData;
112 void **insertPos = Q->insertPos;
113 void **extractPos = Q->extractPos;
115 //if not empty -- (extract is just below insert when empty)
116 if( insertPos - extractPos != 1 &&
117 !(extractPos == endOfData && insertPos == startOfData))
118 { //move before read
119 if( extractPos == endOfData ) //write new pos exactly once, correctly
120 { Q->extractPos = startOfData; //can't overrun then fix it 'cause
121 } // other thread might read bad pos
122 else
123 { Q->extractPos++;
124 }
125 out = *(Q->extractPos);
126 return out;
127 }
128 //Q is empty
129 return NULL;
130 }
133 /*Expands the queue size automatically when it's full
134 */
135 void
136 writePrivQ( void * in, PrivQueueStruc* Q )
137 {
138 void **startOfData = Q->startOfData;
139 void **endOfData = Q->endOfData;
141 void **insertPos = Q->insertPos;
142 void **extractPos = Q->extractPos;
144 tryAgain:
145 //Full? (insert is just below extract when full)
146 if( extractPos - insertPos != 1 &&
147 !(insertPos == endOfData && extractPos == startOfData))
148 { *(Q->insertPos) = in; //insert before move
149 if( insertPos == endOfData ) //write new pos exactly once, correctly
150 { Q->insertPos = startOfData;
151 }
152 else
153 { Q->insertPos++;
154 }
155 return;
156 }
157 //Q is full
158 enlargePrivQ( Q );
159 goto tryAgain;
160 }
163 /*Returns false when the queue was full.
164 * have option of calling make_larger_PrivQ to make more room, then try again
165 */
166 int writeIfSpacePrivQ( void * in, PrivQueueStruc* Q )
167 {
168 void **startOfData = Q->startOfData;
169 void **endOfData = Q->endOfData;
171 void **insertPos = Q->insertPos;
172 void **extractPos = Q->extractPos;
174 if( extractPos - insertPos != 1 &&
175 !(insertPos == endOfData && extractPos == startOfData))
176 { *(Q->insertPos) = in; //insert before move
177 if( insertPos == endOfData ) //write new pos exactly once, correctly
178 { Q->insertPos = startOfData;
179 }
180 else
181 { Q->insertPos++;
182 }
183 return TRUE;
184 }
185 //Q is full
186 return FALSE;
187 }
189 int32
190 numInPrivQ( PrivQueueStruc *Q )
191 { int32 size, numIn;
193 if( Q->insertPos < Q->extractPos )
194 { //insert has wrapped around so numIn is:
195 // insertPos + size - extractPos -- Consider, is empty when
196 // extractPos = endOfData and insert = start -- correctly get zero
197 size = Q->endOfData - Q->startOfData;
198 numIn = Q->insertPos + size - Q->extractPos;
199 }
200 else
201 {
202 numIn = Q->insertPos - Q->extractPos -1;//-1 bec empty @ side-by-side
203 }
204 return numIn;
205 }
208 int
209 numInPrivQ( PrivQueueStruc *Q )
210 {
211 void **insertPos = Q->insertPos;
212 void **extractPos = Q->extractPos;
214 int numInQ;
216 if( (numInQ = insertPos - extractPos) >= 0 ) return numInQ;
217 else
218 { int size = Q->endOfData - Q->startOfData;
219 int numEmpty = extractPos - insertPos; //not efficient, but easier to read
220 return size - numEmpty;
221 }
222 }
224 /*Treats queue as a stack -- no matter contents, if read done right after
225 * a push, then the pushed item is what comes out.
226 * Expands the queue size automatically when it's full.
227 */
228 void
229 pushPrivQ( void * in, PrivQueueStruc* Q )
230 {
231 while(1){
232 void **startOfData = Q->startOfData;
233 void **endOfData = Q->endOfData;
235 void **insertPos = Q->insertPos;
236 void **extractPos = Q->extractPos;
238 //Full? (insert is just below extract when full)
239 if( extractPos - insertPos != 1 &&
240 !(insertPos == endOfData && extractPos == startOfData))
241 { //insert -- but go backwards, inserting at read position then
242 // move read pos backwards
243 *(Q->extractPos) = in;
244 if( extractPos == startOfData ) //write new pos exactly once, correctly
245 { Q->extractPos = endOfData; //can't overrun then fix it 'cause
246 } // other thread might read bad pos
247 else
248 { Q->extractPos--;
249 }
250 return;
251 }
252 //Q is full
253 enlargePrivQ( Q );
254 }
255 }
258 void
259 freePrivQ( PrivQueueStruc *Q )
260 {
261 //This free is not safe to use in wrapper lib nor app code!
262 VMS_int__free( Q->startOfData );
263 VMS_int__free( Q );
264 }