/[dtapublic]/projs/trunk/shared_source/c_datd/cvxzone.c
ViewVC logotype

Diff of /projs/trunk/shared_source/c_datd/cvxzone.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

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

Legend:
Removed from v.70  
changed lines
  Added in v.71

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25