Mercurial > cgi-bin > hgwebdir.cgi > VMS > C_Libraries > Queue_impl
view PrivateQueue.c @ 36:d6da470bbd38
fixed bug in pure c queue -- enlarges correctly now
| author | Some Random Person <seanhalle@yahoo.com> |
|---|---|
| date | Thu, 24 May 2012 07:53:13 -0700 |
| parents | c5d2f2a94133 |
| children |
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, topPartSize, bottPartSize;
46 int8 *insertPos, *extractPos;
47 int8 *oldStartOfData, *oldEndOfData, *newStartOfData, *newEndOfData;
48 int32 insertOffsetBytes, extractOffsetBytes;
49 int8 *copyStartAddr;
51 oldStartOfData = (int8 *)Q->startOfData;
52 oldEndOfData = (int8 *)Q->endOfData;
53 insertPos = (int8 *)Q->insertPos;
54 extractPos = (int8 *)Q->extractPos;
56 //TODO: verify these get number of bytes correct
57 insertOffsetBytes = (int32)(insertPos - oldStartOfData);
58 extractOffsetBytes = (int32)(extractPos - oldStartOfData);
60 oldSize = oldEndOfData - oldStartOfData + 1; //in bytes
61 newSize = 2 * oldSize;
63 //This malloc is not safe to use in wrapper lib nor app code!
64 Q->startOfData = (void **)VMS_int__malloc( newSize );
65 newStartOfData = (int8 *)Q->startOfData;
66 newEndOfData = newStartOfData + newSize; //all calcs in Bytes
67 Q->endOfData = (void **)newEndOfData;
69 //TODO: test all of this, for both cases
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
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
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 VMS_int__free(oldStartOfData);
103 }
106 /*Returns NULL when queue is empty
107 */
108 void* readPrivQ( PrivQueueStruc* Q )
109 { void *out = 0;
110 void **startOfData = Q->startOfData;
111 void **endOfData = Q->endOfData;
113 void **insertPos = Q->insertPos;
114 void **extractPos = Q->extractPos;
116 //if not empty -- (extract is just below insert when empty)
117 if( insertPos - extractPos != 1 &&
118 !(extractPos == endOfData && insertPos == startOfData))
119 { //move before read
120 if( extractPos == endOfData ) //write new pos exactly once, correctly
121 { Q->extractPos = startOfData; //can't overrun then fix it 'cause
122 } // other thread might read bad pos
123 else
124 { Q->extractPos++;
125 }
126 out = *(Q->extractPos);
127 return out;
128 }
129 //Q is empty
130 return NULL;
131 }
134 /*Expands the queue size automatically when it's full
135 */
136 void
137 writePrivQ( void * in, PrivQueueStruc* Q )
138 {
139 void **startOfData = Q->startOfData;
140 void **endOfData = Q->endOfData;
142 void **insertPos = Q->insertPos;
143 void **extractPos = Q->extractPos;
145 tryAgain:
146 //Full? (insert is just below extract when full)
147 if( extractPos - insertPos != 1 &&
148 !(insertPos == endOfData && extractPos == startOfData))
149 { *(Q->insertPos) = in; //insert before move
150 if( insertPos == endOfData ) //write new pos exactly once, correctly
151 { Q->insertPos = startOfData;
152 }
153 else
154 { Q->insertPos++;
155 }
156 return;
157 }
158 //Q is full
159 enlargePrivQ( Q );
160 goto tryAgain;
161 }
164 /*Returns false when the queue was full.
165 * have option of calling make_larger_PrivQ to make more room, then try again
166 */
167 bool32
168 writeIfSpacePrivQ( void * in, PrivQueueStruc* Q )
169 {
170 void **startOfData = Q->startOfData;
171 void **endOfData = Q->endOfData;
173 void **insertPos = Q->insertPos;
174 void **extractPos = Q->extractPos;
176 if( extractPos - insertPos != 1 &&
177 !(insertPos == endOfData && extractPos == startOfData))
178 { *(Q->insertPos) = in; //insert before move
179 if( insertPos == endOfData ) //write new pos exactly once, correctly
180 { Q->insertPos = startOfData;
181 }
182 else
183 { Q->insertPos++;
184 }
185 return TRUE;
186 }
187 //Q is full
188 return FALSE;
189 }
191 int32
192 numInPrivQ( PrivQueueStruc *Q )
193 { int32 size, numIn;
195 if( Q->insertPos < Q->extractPos )
196 { //insert has wrapped around so numIn is:
197 // insertPos + size - extractPos -- Consider, is empty when
198 // extractPos = endOfData and insert = start -- correctly get zero
199 size = Q->endOfData - Q->startOfData + 1; //sz of 10 is 0..9
200 numIn = Q->insertPos - Q->extractPos + size - 1; //-1 bec insrt empty
201 }
202 else
203 {
204 numIn = Q->insertPos - Q->extractPos -1;//-1 bec insertPos empty
205 }
206 return numIn;
207 }
210 /*Treats queue as a stack -- no matter contents, if read done right after
211 * a push, then the pushed item is what comes out.
212 * Expands the queue size automatically when it's full.
213 */
214 void
215 pushPrivQ( void * in, PrivQueueStruc* Q )
216 {
217 while(1){
218 void **startOfData = Q->startOfData;
219 void **endOfData = Q->endOfData;
221 void **insertPos = Q->insertPos;
222 void **extractPos = Q->extractPos;
224 //Full? (insert is just below extract when full)
225 if( extractPos - insertPos != 1 &&
226 !(insertPos == endOfData && extractPos == startOfData))
227 { //insert -- but go backwards, inserting at read position then
228 // move read pos backwards
229 *(Q->extractPos) = in;
230 if( extractPos == startOfData ) //write new pos exactly once, correctly
231 { Q->extractPos = endOfData; //can't overrun then fix it 'cause
232 } // other thread might read bad pos
233 else
234 { Q->extractPos--;
235 }
236 return;
237 }
238 //Q is full
239 enlargePrivQ( Q );
240 }
241 }
244 void
245 freePrivQ( PrivQueueStruc *Q )
246 {
247 //This free is not safe to use in wrapper lib nor app code!
248 VMS_int__free( Q->startOfData );
249 VMS_int__free( Q );
250 }