1 |
//$Header$ |
2 |
//------------------------------------------------------------------------------------------------- |
3 |
//This file is part of "David T. Ashley's Shared Source Code", a set of shared components |
4 |
//integrated into many of David T. Ashley's projects. |
5 |
//------------------------------------------------------------------------------------------------- |
6 |
//This source code and any program in which it is compiled/used is provided under the MIT License, |
7 |
//reproduced below. |
8 |
//------------------------------------------------------------------------------------------------- |
9 |
//Permission is hereby granted, free of charge, to any person obtaining a copy of |
10 |
//this software and associated documentation files(the "Software"), to deal in the |
11 |
//Software without restriction, including without limitation the rights to use, |
12 |
//copy, modify, merge, publish, distribute, sublicense, and / or sell copies of the |
13 |
//Software, and to permit persons to whom the Software is furnished to do so, |
14 |
//subject to the following conditions : |
15 |
// |
16 |
//The above copyright notice and this permission notice shall be included in all |
17 |
//copies or substantial portions of the Software. |
18 |
// |
19 |
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
20 |
//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
21 |
//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE |
22 |
//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
23 |
//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
24 |
//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE |
25 |
//SOFTWARE. |
26 |
//------------------------------------------------------------------------------------------------- |
27 |
/* Convex zones for timed automata verification. |
28 |
*/ |
29 |
//------------------------------------------------------------------------------------------------- |
30 |
#define MODULE_CVXZONE |
31 |
|
32 |
#include <assert.h> |
33 |
#include <malloc.h> |
34 |
#include <stdio.h> |
35 |
#include <string.h> |
36 |
|
37 |
#include "ccmalloc.h" |
38 |
#include "cvxzone.h" |
39 |
|
40 |
|
41 |
/**************************************************************************/ |
42 |
/***** ALLOCATION, DEALLOCATION, AND COPY FUNCTIONS |
43 |
/**************************************************************************/ |
44 |
/* Returns the number of constraint slots in memory that should be |
45 |
** allocated as a function of those required. |
46 |
*/ |
47 |
static int CVXZONE_cr_num_to_alloc(int crs_reqd_num) |
48 |
{ |
49 |
int rv; |
50 |
|
51 |
assert(crs_reqd_num >= 0); |
52 |
|
53 |
rv = crs_reqd_num + CVXZONE_ZONE_CONST_ALLOC_INC - 1; |
54 |
|
55 |
rv = rv - (rv % CVXZONE_ZONE_CONST_ALLOC_INC); |
56 |
|
57 |
assert(rv >= crs_reqd_num); |
58 |
|
59 |
return(rv); |
60 |
} |
61 |
|
62 |
|
63 |
void CVXZONE_new(CVXZONE_zone_ptr *arg) |
64 |
{ |
65 |
/* Eyeball the inputs. */ |
66 |
assert(arg != NULL); |
67 |
assert(*arg == NULL); |
68 |
|
69 |
/* Allocate the space for the zone itself. |
70 |
*/ |
71 |
*arg = CCMALLOC_malloc(sizeof(CVXZONE_zone)); |
72 |
|
73 |
/* Zero the space. */ |
74 |
memset(*arg, 0, sizeof(CVXZONE_zone)); |
75 |
|
76 |
/* Set any fields that take on non-zero initial values. |
77 |
*/ |
78 |
(*arg)->is_canonical = 1; |
79 |
} |
80 |
|
81 |
|
82 |
void CVXZONE_delete(CVXZONE_zone_ptr *arg) |
83 |
{ |
84 |
/* Check the input parameters. */ |
85 |
assert(arg != NULL); |
86 |
assert(*arg != NULL); |
87 |
|
88 |
/* Free any allocated constraint block. |
89 |
*/ |
90 |
if ((*arg)->constraints) |
91 |
CCMALLOC_free((*arg)->constraints); |
92 |
|
93 |
/* Free the record itself. |
94 |
*/ |
95 |
CCMALLOC_free(*arg); |
96 |
|
97 |
/* Set the caller's pointer to NULL. |
98 |
*/ |
99 |
*arg = NULL; |
100 |
} |
101 |
|
102 |
|
103 |
void CVXZONE_copy(CVXZONE_zone_ptr *dst, CVXZONE_zone_ptr *src) |
104 |
{ |
105 |
CVXZONE_constraint_ptr constraints; |
106 |
int n_allocd; |
107 |
|
108 |
/* Check the input parameters. */ |
109 |
assert(dst != NULL); |
110 |
assert(src != NULL); |
111 |
assert(*dst != NULL); |
112 |
assert(*src != NULL); |
113 |
|
114 |
/* Save the victim's pointer to constraints and also the amount of |
115 |
** space allocated. These will be written over by the memory |
116 |
** copy. |
117 |
*/ |
118 |
constraints = (*dst)->constraints; |
119 |
n_allocd = (*dst)->n_allocd; |
120 |
|
121 |
/* Do a block copy from source to destination. This catches |
122 |
** everything except the constraints. |
123 |
*/ |
124 |
memcpy(*dst, *src, sizeof(CVXZONE_zone)); |
125 |
|
126 |
/* Write the memory pointer and the amount allocd back. |
127 |
*/ |
128 |
(*dst)->constraints = constraints; |
129 |
(*dst)->n_allocd = n_allocd; |
130 |
|
131 |
/* Reallocate the destination constraint block if there is not |
132 |
** enough space to hold the constraints. |
133 |
*/ |
134 |
if ((*dst)->n_used > (*dst)->n_allocd) |
135 |
{ |
136 |
if ((*dst)->constraints) |
137 |
{ |
138 |
/* There was already a memory area involved, but not large |
139 |
** enough. |
140 |
*/ |
141 |
CCMALLOC_realloc((*dst)->constraints, CVXZONE_cr_num_to_alloc((*dst)->n_used) * sizeof(CVXZONE_constraint)); |
142 |
} |
143 |
else |
144 |
{ |
145 |
/* No memory area had been allocated. Need to allocate it for |
146 |
** the first time. |
147 |
*/ |
148 |
CCMALLOC_malloc(CVXZONE_cr_num_to_alloc((*dst)->n_used) * sizeof(CVXZONE_constraint)); |
149 |
} |
150 |
} |
151 |
|
152 |
/* Copy over the constraint block. |
153 |
*/ |
154 |
if ((*dst)->n_used) |
155 |
{ |
156 |
memcpy((*dst)->constraints, (*src)->constraints, (*dst)->n_used * sizeof(CVXZONE_constraint)); |
157 |
} |
158 |
} |
159 |
|
160 |
|
161 |
void CVXZONE_clone(CVXZONE_zone_ptr *clone, CVXZONE_zone_ptr *orig) |
162 |
{ |
163 |
/* Check the inputs. */ |
164 |
assert(clone != NULL); |
165 |
assert(orig != NULL); |
166 |
assert(*clone == NULL); |
167 |
assert(*orig != NULL); |
168 |
|
169 |
/* Allocate the clone. |
170 |
*/ |
171 |
CVXZONE_new(clone); |
172 |
|
173 |
/* Copy to the clone. |
174 |
*/ |
175 |
CVXZONE_copy(clone, orig); |
176 |
} |
177 |
|
178 |
|
179 |
/**************************************************************************/ |
180 |
/***** MAINTENANCE FUNCTIONS |
181 |
/**************************************************************************/ |
182 |
/* Removes (i.e. compresses out) all the unused constraints, i.e. those with |
183 |
** the valid flag not set. This simply makes the existing constraints contiguous. |
184 |
** This function does this unconditionally, i.e. the is_canonical flag is not |
185 |
** considered. |
186 |
*/ |
187 |
static void CVXZONE_compress_constraints(CVXZONE_zone_ptr *arg) |
188 |
{ |
189 |
int src_idx, dst_idx; |
190 |
|
191 |
assert(arg != NULL); |
192 |
assert(*arg != NULL); |
193 |
|
194 |
dst_idx = 0; |
195 |
|
196 |
for (src_idx = 0; src_idx < (int)((*arg)->n_used); src_idx++) |
197 |
{ |
198 |
if ((*arg)->constraints[src_idx].valid) |
199 |
{ |
200 |
if (src_idx != dst_idx) /* No sense copying something onto itself. */ |
201 |
{ |
202 |
memcpy((*arg)->constraints + dst_idx, |
203 |
(*arg)->constraints + src_idx, |
204 |
sizeof(CVXZONE_constraint)); |
205 |
} |
206 |
dst_idx++; |
207 |
} |
208 |
} |
209 |
|
210 |
/* The copy cycle is complete. We can infer how many slots were *actually* used. |
211 |
*/ |
212 |
(*arg)->n_used = dst_idx; |
213 |
} |
214 |
|
215 |
|
216 |
void CVXZONE_maintain_memory_trim(CVXZONE_zone_ptr *arg) |
217 |
{ |
218 |
assert(arg != NULL); |
219 |
assert(*arg != NULL); |
220 |
|
221 |
/* First, compact the array of constraints. |
222 |
*/ |
223 |
CVXZONE_compress_constraints(arg); |
224 |
|
225 |
/* Now, realloc the array to be the exact right size. |
226 |
*/ |
227 |
if ((*arg)->n_used) |
228 |
{ |
229 |
assert((*arg)->constraints != NULL); |
230 |
|
231 |
CCMALLOC_realloc((*arg)->constraints, |
232 |
(*arg)->n_used * sizeof(CVXZONE_constraint)); |
233 |
} |
234 |
else |
235 |
{ |
236 |
if ((*arg)->constraints) |
237 |
{ |
238 |
CCMALLOC_free((*arg)->constraints); |
239 |
(*arg)->constraints = NULL; |
240 |
} |
241 |
} |
242 |
} |
243 |
|
244 |
|
245 |
DECMOD_CVXZONE void CVXZONE_maintain_canonize(CVXZONE_zone_ptr *arg) |
246 |
{ |
247 |
assert(arg != NULL); |
248 |
assert(*arg != NULL); |
249 |
|
250 |
|
251 |
} |
252 |
|
253 |
//End of cvxzone.c. |