1 /*-----------------------------------------------------------------------
2
3 File : clb_pstacks.c
4
5 Author: Stephan Schulz
6
7 Contents
8
9 Stacks for (long) integers and pointers.
10
11 Copyright 1998, 1999 by the author.
12 This code is released under the GNU General Public Licence and
13 the GNU Lesser General Public License.
14 See the file COPYING in the main E directory for details..
15 Run "eprover -h" for contact information.
16
17 Changes
18
19 <1> Wed Dec 3 17:43:15 MET 1997
20
21 -----------------------------------------------------------------------*/
22
23 #include <clb_pstacks.h>
24
25
26 /*---------------------------------------------------------------------*/
27 /* Global Variables */
28 /*---------------------------------------------------------------------*/
29
30
31 /*---------------------------------------------------------------------*/
32 /* Forward Declarations */
33 /*---------------------------------------------------------------------*/
34
35
36 /*---------------------------------------------------------------------*/
37 /* Internal Functions */
38 /*---------------------------------------------------------------------*/
39
40 /*---------------------------------------------------------------------*/
41 /* Exported Functions */
42 /*---------------------------------------------------------------------*/
43
44 /* Most things are now defined as inline stuff.... */
45
46 /*-----------------------------------------------------------------------
47 //
48 // Function: PStackGrow()
49 //
50 // Grow the stack area. Realloc is emulated in terms of
51 // SizeMalloc()/SizeFree(). This is because stacks are allocated and
52 // deallocated a lot, and usually in the same sizes, so it pays off
53 // to optimize this behaviour.
54 //
55 // Global Variables: -
56 //
57 // Side Effects : Memory operations
58 //
59 /----------------------------------------------------------------------*/
60
PStackGrow(PStack_p stack)61 void __attribute__ ((noinline)) PStackGrow(PStack_p stack)
62 {
63 IntOrP *tmp;
64 long old_size;
65
66 /* Emulate Realloc-Functionality for use of SizeMalloc() */
67 old_size = stack->size;
68 stack->size = stack->size*2;
69 tmp = SizeMalloc(stack->size * sizeof(IntOrP));
70 memcpy(tmp, stack->stack, old_size*sizeof(IntOrP));
71 SizeFree(stack->stack, old_size * sizeof(IntOrP));
72 stack->stack = tmp;
73 }
74
75
76 /*-----------------------------------------------------------------------
77 //
78 // Function: PStackDiscardElement()
79 //
80 // Remove element number i from the stack. If it is not the top
81 // element, the top element gets swapped in.
82 //0
83 // Global Variables:
84 //
85 // Side Effects :
86 //
87 /----------------------------------------------------------------------*/
88
PStackDiscardElement(PStack_p stack,PStackPointer i)89 void PStackDiscardElement(PStack_p stack, PStackPointer i)
90 {
91 assert(stack);
92 assert(i < PStackGetSP(stack));
93 assert(i >= 0);
94
95 stack->current--;
96 if(stack->current != i)
97 {
98 stack->stack[i] = stack->stack[stack->current];
99 }
100 }
101
102
103
104 /*-----------------------------------------------------------------------
105 //
106 // Function: PStackTopAddr()
107 //
108 // Return address of top element on the stack.
109 //
110 // Global Variables: -
111 //
112 // Side Effects : -
113 //
114 /----------------------------------------------------------------------*/
115
PStackTopAddr(PStack_p stack)116 IntOrP* PStackTopAddr(PStack_p stack)
117 {
118 assert(stack->current);
119
120 return &(stack->stack[stack->current-1]);
121 }
122
123
124
125 /*-----------------------------------------------------------------------
126 //
127 // Function: PStackComputeAverage()
128 //
129 // Given a stack of integers, compute the arithmetic mean (returned)
130 // and the standard deviation (stored in *deviation) of the
131 // integers.
132 //
133 // Global Variables: -
134 //
135 // Side Effects : -
136 //
137 /----------------------------------------------------------------------*/
138
PStackComputeAverage(PStack_p stack,double * deviation)139 double PStackComputeAverage(PStack_p stack, double *deviation)
140 {
141 PStackPointer i;
142 long count = 0;
143 double sum = 0, average = 0, variance = 0;
144
145 for(i=0; i<PStackGetSP(stack); i++)
146 {
147 sum+=PStackElementInt(stack,i);
148 count++;
149 }
150 if(count)
151 {
152 average = sum / (double)count;
153 }
154 else
155 {
156 average = 0;
157 }
158
159 if(count)
160 {
161 for(i=0; i<PStackGetSP(stack); i++)
162 {
163 variance+= (PStackElementInt(stack,i)-average)
164 *(PStackElementInt(stack,i)-average);
165 }
166 variance = variance / (double)count;
167 }
168 else
169 {
170 variance = 0;
171 }
172 *deviation = sqrt(variance);
173
174 return average;
175 }
176
177
178
179 /*-----------------------------------------------------------------------
180 //
181 // Function: PStackSort()
182 //
183 // Sort the elements of the PStack using qsort.
184 //
185 // Global Variables: -
186 //
187 // Side Effects : -
188 //
189 /----------------------------------------------------------------------*/
190
PStackSort(PStack_p stack,ComparisonFunctionType cmpfun)191 void PStackSort(PStack_p stack, ComparisonFunctionType cmpfun)
192 {
193 qsort(stack->stack, stack->current, sizeof(IntOrP), cmpfun);
194 }
195
196 /*-----------------------------------------------------------------------
197 //
198 // Function: PStackMerge()
199 //
200 // Merge two sorted stacks onto a third. Discards duplicates.
201 //
202 // Global Variables:
203 //
204 // Side Effects :
205 //
206 /----------------------------------------------------------------------*/
207
PStackMerge(PStack_p st1,PStack_p st2,PStack_p res,ComparisonFunctionType cmpfun)208 void PStackMerge(PStack_p st1, PStack_p st2, PStack_p res,
209 ComparisonFunctionType cmpfun)
210 {
211 IntOrP tmp;
212 int cmpres;
213
214 while(!PStackEmpty(st1) || !PStackEmpty(st2))
215 {
216 if(PStackEmpty(st1))
217 {
218 tmp = PStackPop(st2);
219 }
220 else if(PStackEmpty(st2))
221 {
222 tmp = PStackPop(st1);
223 }
224 else
225 {
226 cmpres = cmpfun(PStackTopAddr(st1), PStackTopAddr(st2));
227 if(cmpres < 0)
228 {
229 tmp = PStackPop(st1);
230 }
231 else
232 {
233 tmp = PStackPop(st2);
234 }
235 }
236 if(PStackEmpty(res) || (cmpfun(PStackTopAddr(res), &tmp)!=0))
237 {
238 push(res, tmp);
239 }
240 }
241 }
242
243
244 /*-----------------------------------------------------------------------
245 //
246 // Function: PStackPushStack()
247 //
248 // Push all elements from source onto target.
249 //
250 // Global Variables: -
251 //
252 // Side Effects : -
253 //
254 /----------------------------------------------------------------------*/
255
PStackPushStack(PStack_p target,PStack_p source)256 void PStackPushStack(PStack_p target, PStack_p source)
257 {
258 PStackPointer i;
259
260 for(i=0; i<PStackGetSP(source); i++)
261 {
262 push(target, PStackElement(source,i));
263 }
264 }
265
266
267 /*-----------------------------------------------------------------------
268 //
269 // Function: PStackPrintInt()
270 //
271 // Print a stack (interpreted as (long) integers) using the format
272 // given.
273 //
274 // Global Variables: -
275 //
276 // Side Effects : Output
277 //
278 /----------------------------------------------------------------------*/
279
PStackPrintInt(FILE * out,char * format,PStack_p stack)280 void PStackPrintInt(FILE* out, char* format, PStack_p stack)
281 {
282 PStackPointer i;
283
284 for(i=0; i<PStackGetSP(stack); i++)
285 {
286 fprintf(out, format, PStackElementInt(stack, i));
287 }
288 }
289
290
291
292 /*---------------------------------------------------------------------*/
293 /* End of File */
294 /*---------------------------------------------------------------------*/
295
296
297