shared_source/c_datd/cvxzone.c

//$Header$
//-------------------------------------------------------------------------------------------------
//This file is part of "David T. Ashley's Shared Source Code", a set of shared components
//integrated into many of David T. Ashley's projects.
//-------------------------------------------------------------------------------------------------
//This source code and any program in which it is compiled/used is provided under the MIT License,
//reproduced below.
//-------------------------------------------------------------------------------------------------
//Permission is hereby granted, free of charge, to any person obtaining a copy of
//this software and associated documentation files(the "Software"), to deal in the
//Software without restriction, including without limitation the rights to use,
//copy, modify, merge, publish, distribute, sublicense, and / or sell copies of the
//Software, and to permit persons to whom the Software is furnished to do so,
//subject to the following conditions :
//
//The above copyright notice and this permission notice shall be included in all
//copies or substantial portions of the Software.
//
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
//SOFTWARE.
//-------------------------------------------------------------------------------------------------
/* Convex zones for timed automata verification.
*/
//-------------------------------------------------------------------------------------------------
#define MODULE_CVXZONE

#include <assert.h>
#include <malloc.h>
#include <stdio.h>
#include <string.h>

#include "ccmalloc.h"
#include "cvxzone.h"


/**************************************************************************/
/***** ALLOCATION, DEALLOCATION, AND COPY FUNCTIONS
/**************************************************************************/
/* Returns the number of constraint slots in memory that should be 
** allocated as a function of those required.
*/
static int CVXZONE_cr_num_to_alloc(int crs_reqd_num)
   {
   int rv;

   assert(crs_reqd_num >= 0);

   rv = crs_reqd_num + CVXZONE_ZONE_CONST_ALLOC_INC - 1;

   rv = rv - (rv % CVXZONE_ZONE_CONST_ALLOC_INC);

   assert(rv >= crs_reqd_num);

   return(rv);
   }


void CVXZONE_new(CVXZONE_zone_ptr *arg)
   {
   /* Eyeball the inputs. */
   assert(arg  != NULL);
   assert(*arg == NULL);

   /* Allocate the space for the zone itself.
   */
   *arg = CCMALLOC_malloc(sizeof(CVXZONE_zone));

   /* Zero the space. */
   memset(*arg, 0, sizeof(CVXZONE_zone));

   /* Set any fields that take on non-zero initial values.
   */
   (*arg)->is_canonical = 1;
   }


void CVXZONE_delete(CVXZONE_zone_ptr *arg)
   {
   /* Check the input parameters. */
   assert(arg  != NULL);
   assert(*arg != NULL);

   /* Free any allocated constraint block.
   */
   if ((*arg)->constraints)
      CCMALLOC_free((*arg)->constraints);

   /* Free the record itself.
   */
   CCMALLOC_free(*arg);

   /* Set the caller's pointer to NULL.
   */
   *arg = NULL;
   }


void CVXZONE_copy(CVXZONE_zone_ptr *dst, CVXZONE_zone_ptr *src)
   {
   CVXZONE_constraint_ptr constraints;
   int n_allocd;

   /* Check the input parameters. */
   assert(dst  != NULL);
   assert(src  != NULL);
   assert(*dst != NULL);
   assert(*src != NULL);

   /* Save the victim's pointer to constraints and also the amount of
   ** space allocated.  These will be written over by the memory
   ** copy.
   */
   constraints = (*dst)->constraints;
   n_allocd    = (*dst)->n_allocd;

   /* Do a block copy from source to destination.  This catches
   ** everything except the constraints.
   */
   memcpy(*dst, *src, sizeof(CVXZONE_zone));

   /* Write the memory pointer and the amount allocd back.
   */
   (*dst)->constraints = constraints;
   (*dst)->n_allocd    = n_allocd;

   /* Reallocate the destination constraint block if there is not
   ** enough space to hold the constraints.
   */
   if ((*dst)->n_used > (*dst)->n_allocd)
      {
      if ((*dst)->constraints)
         {
         /* There was already a memory area involved, but not large
         ** enough.
         */
         CCMALLOC_realloc((*dst)->constraints, CVXZONE_cr_num_to_alloc((*dst)->n_used) * sizeof(CVXZONE_constraint));
         }
      else
         {
         /* No memory area had been allocated.  Need to allocate it for
         ** the first time.
         */
         CCMALLOC_malloc(CVXZONE_cr_num_to_alloc((*dst)->n_used) * sizeof(CVXZONE_constraint));
         }
      }

   /* Copy over the constraint block.
   */
   if ((*dst)->n_used)
      {
      memcpy((*dst)->constraints, (*src)->constraints, (*dst)->n_used * sizeof(CVXZONE_constraint));
      }
   }


void CVXZONE_clone(CVXZONE_zone_ptr *clone, CVXZONE_zone_ptr *orig)
   {
   /* Check the inputs. */
   assert(clone  != NULL);
   assert(orig   != NULL);
   assert(*clone == NULL);
   assert(*orig  != NULL);

   /* Allocate the clone.
   */
   CVXZONE_new(clone);

   /* Copy to the clone.
   */
   CVXZONE_copy(clone, orig);
   }


/**************************************************************************/
/***** MAINTENANCE FUNCTIONS                        
/**************************************************************************/
/* Removes (i.e. compresses out) all the unused constraints, i.e. those with
** the valid flag not set.  This simply makes the existing constraints contiguous.
** This function does this unconditionally, i.e. the is_canonical flag is not
** considered.
*/
static void CVXZONE_compress_constraints(CVXZONE_zone_ptr *arg)
   {
   int src_idx, dst_idx;

   assert(arg  != NULL);
   assert(*arg != NULL);

   dst_idx = 0;

   for (src_idx = 0; src_idx < (int)((*arg)->n_used); src_idx++)
      {
      if ((*arg)->constraints[src_idx].valid)
         {
         if (src_idx != dst_idx)  /* No sense copying something onto itself. */
            {
            memcpy((*arg)->constraints + dst_idx, 
                   (*arg)->constraints + src_idx,
                   sizeof(CVXZONE_constraint));
            }
         dst_idx++;
         }
      }

   /* The copy cycle is complete.  We can infer how many slots were *actually* used.
   */
   (*arg)->n_used = dst_idx;
   }


void CVXZONE_maintain_memory_trim(CVXZONE_zone_ptr *arg)
   {
   assert(arg  != NULL);
   assert(*arg != NULL);

   /* First, compact the array of constraints.
   */
   CVXZONE_compress_constraints(arg);

   /* Now, realloc the array to be the exact right size.
   */
   if ((*arg)->n_used)
      {
      assert((*arg)->constraints != NULL);

      CCMALLOC_realloc((*arg)->constraints,
                       (*arg)->n_used * sizeof(CVXZONE_constraint));
      }
   else
      {
      if ((*arg)->constraints)
         {
         CCMALLOC_free((*arg)->constraints);
         (*arg)->constraints = NULL;
         }
      }
   }


DECMOD_CVXZONE void CVXZONE_maintain_canonize(CVXZONE_zone_ptr *arg)
   {
   assert(arg  != NULL);
   assert(*arg != NULL);


   }

//End of cvxzone.c.
1	dashley	56	//$Header$
2	dashley	25	//-------------------------------------------------------------------------------------------------
3	dashley	56	//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	dashley	25	//-------------------------------------------------------------------------------------------------
6	dashley	56	//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	dashley	25	//
16	dashley	56	//The above copyright notice and this permission notice shall be included in all
17			//copies or substantial portions of the Software.
18	dashley	25	//
19	dashley	56	//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	dashley	25	//-------------------------------------------------------------------------------------------------
27	dashley	56	/* Convex zones for timed automata verification.
28			*/
29			//-------------------------------------------------------------------------------------------------
30	dashley	25	#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	dashley	56	//End of cvxzone.c.