source: vis_dev/vis-2.3/src/abs/absCatalog.c @ 50

Last change on this file since 50 was 14, checked in by cecile, 13 years ago

vis2.3
File size: 18.6 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [absCatalog.c]
4
5  PackageName [abs]
6
7  Synopsis [Functions to handle a catalog of sub-formulas to detect
8  common sub-expressions]
9
10  Author      [Abelardo Pardo <abel@vlsi.colorado.edu>]
11
12  Copyright   [This file was created at the University of Colorado at
13  Boulder.  The University of Colorado at Boulder makes no warranty
14  about the suitability of this software for any purpose.  It is
15  presented on an AS IS basis.]
16
17******************************************************************************/
18
19#include "absInt.h"
20
21static char rcsid[] UNUSED = "$Id: absCatalog.c,v 1.8 2005/04/16 04:22:21 fabio Exp $";
22
23
24/*---------------------------------------------------------------------------*/
25/* Structure declarations                                                    */
26/*---------------------------------------------------------------------------*/
27
28/**Struct**********************************************************************
29
30  Synopsis [A struct to keep list of subformulas to detect common
31  subexpressions]
32
33  SeeAlso     [AbsVerificationInfo]
34
35******************************************************************************/
36
37struct AbsVertexCatalog {
38  lsList fixedPoints;
39  lsList booleanOps;
40  lsList negations;
41  lsList preImages;
42  lsList identifiers;
43  lsList variables;
44};
45
46/*---------------------------------------------------------------------------*/
47/* Macro declarations                                                        */
48/*---------------------------------------------------------------------------*/
49
50/**Macro***********************************************************************
51
52  Synopsis [Macro to read the fixedPoints field from a AbsVertexCatalog_t
53  structure]
54
55  SideEffects  []
56
57  SeeAlso      [AbsVertexCatalog]
58
59******************************************************************************/
60#define AbsVertexCatalogReadFixedPoints(\
61  /* AbsVertexCatalog_t * */ cPtr      \
62)                                      \
63    (cPtr->fixedPoints)
64
65/**Macro***********************************************************************
66
67  Synopsis [Macro to read the booleanOps field from a AbsVertexCatalog_t
68  structure]
69
70  SideEffects  []
71
72  SeeAlso      [AbsVertexCatalog]
73
74******************************************************************************/
75#define AbsVertexCatalogReadBooleanOps(\
76  /* AbsVertexCatalog_t * */ cPtr      \
77)                                      \
78    (cPtr->booleanOps)
79
80/**Macro***********************************************************************
81
82  Synopsis [Macro to read the negations field from a AbsVertexCatalog_t
83  structure]
84
85  SideEffects  []
86
87  SeeAlso      [AbsVertexCatalog]
88
89******************************************************************************/
90#define AbsVertexCatalogReadNegations(\
91  /* AbsVertexCatalog_t * */ cPtr      \
92)                                      \
93    (cPtr->negations)
94
95/**Macro***********************************************************************
96
97  Synopsis [Macro to read the preImages field from a AbsVertexCatalog_t
98  structure]
99
100  SideEffects  []
101
102  SeeAlso      [AbsVertexCatalog]
103
104******************************************************************************/
105#define AbsVertexCatalogReadPreImages(\
106  /* AbsVertexCatalog_t * */ cPtr      \
107)                                      \
108    (cPtr->preImages)
109
110/**Macro***********************************************************************
111
112  Synopsis [Macro to read the identifiers field from a AbsVertexCatalog_t
113  structure]
114
115  SideEffects  []
116
117  SeeAlso      [AbsVertexCatalog]
118
119******************************************************************************/
120#define AbsVertexCatalogReadIdentifiers(\
121  /* AbsVertexCatalog_t * */ cPtr      \
122)                                      \
123    (cPtr->identifiers)
124
125/**Macro***********************************************************************
126
127  Synopsis [Macro to read the variables field from a AbsVertexCatalog_t
128  structure]
129
130  SideEffects  []
131
132  SeeAlso      [AbsVertexCatalog]
133
134******************************************************************************/
135#define AbsVertexCatalogReadVariables(\
136  /* AbsVertexCatalog_t * */ cPtr     \
137)                                     \
138    (cPtr->variables)
139
140/**Macro***********************************************************************
141
142  Synopsis [Macro to set the fixedPoints field from a AbsVertexCatalog_t
143  structure]
144
145  SideEffects  []
146
147  SeeAlso      [AbsVertexCatalog]
148
149******************************************************************************/
150#define AbsVertexCatalogSetFixedPoints(\
151  /* AbsVertexCatalog_t * */ cPtr,    \
152  /* lsList */ data                   \
153)                                     \
154    (cPtr->fixedPoints) = (data)
155
156/**Macro***********************************************************************
157
158  Synopsis [Macro to set the booleanOps field from a AbsVertexCatalog_t
159  structure]
160
161  SideEffects  []
162
163  SeeAlso      [AbsVertexCatalog]
164
165******************************************************************************/
166#define AbsVertexCatalogSetBooleanOps(\
167  /* AbsVertexCatalog_t * */ cPtr,    \
168  /* lsList */ data                   \
169)                                     \
170    (cPtr->booleanOps) = (data)
171
172/**Macro***********************************************************************
173
174  Synopsis [Macro to set the negations field from a AbsVertexCatalog_t
175  structure]
176
177  SideEffects  [AbsVertexCatalog]
178
179  SeeAlso      []
180
181******************************************************************************/
182#define AbsVertexCatalogSetNegations(\
183  /* AbsVertexCatalog_t * */ cPtr,   \
184  /* lsList */ data                  \
185)                                    \
186    (cPtr->negations) = (data)
187
188/**Macro***********************************************************************
189
190  Synopsis [Macro to set the preImages field from a AbsVertexCatalog_t
191  structure]
192
193  SideEffects  []
194
195  SeeAlso      [AbsVertexCatalog]
196
197******************************************************************************/
198#define AbsVertexCatalogSetPreImages(\
199  /* AbsVertexCatalog_t * */ cPtr,  \
200  /* lsList */ data                 \
201)                                   \
202    (cPtr->preImages) = (data)
203
204/**Macro***********************************************************************
205
206  Synopsis [Macro to set the identifiers field from a AbsVertexCatalog_t
207  structure]
208
209  SideEffects  []
210
211  SeeAlso      [AbsVertexCatalog]
212
213******************************************************************************/
214#define AbsVertexCatalogSetIdentifiers(\
215  /* AbsVertexCatalog_t * */ cPtr,     \
216  /* lsList */ data                    \
217)                                      \
218    (cPtr->identifiers) = (data)
219
220/**Macro***********************************************************************
221
222  Synopsis [Macro to set the variables field from a AbsVertexCatalog_t
223  structure]
224
225  SideEffects  []
226
227  SeeAlso      [AbsVertexCatalog]
228
229******************************************************************************/
230#define AbsVertexCatalogSetVariables(\
231  /* AbsVertexCatalog_t * */ cPtr,   \
232  /* lsList */ data                  \
233)                                    \
234    (cPtr->variables) = (data)
235
236/**AutomaticStart*************************************************************/
237
238/*---------------------------------------------------------------------------*/
239/* Static function prototypes                                                */
240/*---------------------------------------------------------------------------*/
241
242static AbsVertexInfo_t * LookUpBooleanOp(lsList vertexList, AbsVertex_t type, boolean polarity, AbsVertexInfo_t *leftKid, AbsVertexInfo_t *rightKid);
243static AbsVertexInfo_t * LookUpFixedPoint(lsList vertexList, boolean polarity, AbsVertexInfo_t *leftKid, int localId);
244static AbsVertexInfo_t * LookUpIdentifier(lsList vertexList, boolean polarity, char *name, char *value);
245static AbsVertexInfo_t * LookUpPreImage(lsList vertexList, boolean polarity, AbsVertexInfo_t *leftKid);
246static AbsVertexInfo_t * LookUpVariable(lsList vertexList, boolean polarity, int localId);
247
248/**AutomaticEnd***************************************************************/
249
250
251/*---------------------------------------------------------------------------*/
252/* Definition of exported functions                                          */
253/*---------------------------------------------------------------------------*/
254
255/*---------------------------------------------------------------------------*/
256/* Definition of internal functions                                          */
257/*---------------------------------------------------------------------------*/
258
259/**Function********************************************************************
260
261  Synopsis [Allocate the structure to store the catalog of vertices]
262
263  SideEffects        []
264
265  SeeAlso            [AbsVertexCatalog]
266
267******************************************************************************/
268AbsVertexCatalog_t *
269AbsVertexCatalogInitialize(void)
270{
271  AbsVertexCatalog_t *result;
272
273  result = ALLOC(AbsVertexCatalog_t, 1);
274
275  AbsVertexCatalogSetFixedPoints(result, lsCreate());
276  AbsVertexCatalogSetBooleanOps(result, lsCreate());
277  AbsVertexCatalogSetNegations(result, lsCreate());
278  AbsVertexCatalogSetPreImages(result, lsCreate());
279  AbsVertexCatalogSetIdentifiers(result, lsCreate());
280  AbsVertexCatalogSetVariables(result, lsCreate());
281
282  return result;
283} /* End of AbsVertexCatalogInitialize */
284
285/**Function********************************************************************
286
287  Synopsis [Deallocate the structure storing the catalog vertices]
288
289  SideEffects        []
290
291  SeeAlso            [AbsVertexCatalog]
292
293******************************************************************************/
294void
295AbsVertexCatalogFree(
296  AbsVertexCatalog_t *c)
297{
298  lsDestroy(AbsVertexCatalogReadFixedPoints(c), (void (*)(lsGeneric))0);
299  lsDestroy(AbsVertexCatalogReadBooleanOps(c), (void (*)(lsGeneric))0);
300  lsDestroy(AbsVertexCatalogReadNegations(c), (void (*)(lsGeneric))0);
301  lsDestroy(AbsVertexCatalogReadPreImages(c), (void (*)(lsGeneric))0);
302  lsDestroy(AbsVertexCatalogReadIdentifiers(c), (void (*)(lsGeneric))0);
303  lsDestroy(AbsVertexCatalogReadVariables(c), (void (*)(lsGeneric))0);
304
305  FREE(c);
306
307  return;
308} /* End of AbsVertexCatalogFree */
309
310/**Function********************************************************************
311
312  Synopsis [Find or create the vertex with the given sub-formula in the vertex
313  catalog]
314
315  SideEffects []
316
317  SeeAlso [AbsVertexCatalog]
318
319******************************************************************************/
320AbsVertexInfo_t *
321AbsVertexCatalogFindOrAdd(
322  AbsVertexCatalog_t *catalog,
323  AbsVertex_t type,
324  boolean polarity,
325  AbsVertexInfo_t *leftKid,
326  AbsVertexInfo_t *rightKid,
327  int localId,
328  char *idName,
329  char *idValue
330)
331{
332  if (type == fixedPoint_c) {
333    return LookUpFixedPoint(AbsVertexCatalogReadFixedPoints(catalog),
334                            polarity, leftKid, localId);
335  }
336
337  if (type == and_c || type == xor_c || type == xnor_c) {
338    return LookUpBooleanOp(AbsVertexCatalogReadBooleanOps(catalog),
339                           type, polarity, leftKid, rightKid);
340  }
341
342  if (type == not_c) {
343    return LookUpPreImage(AbsVertexCatalogReadNegations(catalog),
344                          polarity, leftKid);
345  }
346
347  if (type == preImage_c) {
348    return LookUpPreImage(AbsVertexCatalogReadPreImages(catalog),
349                          polarity, leftKid);
350  }
351
352  if (type == identifier_c) {
353    return LookUpIdentifier(AbsVertexCatalogReadIdentifiers(catalog),
354                            polarity, idName, idValue);
355  }
356
357  if (type == variable_c) {
358    return LookUpVariable(AbsVertexCatalogReadVariables(catalog),
359                          polarity, localId);
360  }
361
362  (void) fprintf(vis_stderr, "** abs error: Unknown vertex type in function ");
363  (void) fprintf(vis_stderr, "AbsVertexCatalogFindOrAdd.\n");
364
365  return NIL(AbsVertexInfo_t);
366
367} /* End of AbsVertexCatalogFindOrAdd */
368
369/**Function********************************************************************
370
371  Synopsis           [Delete a vertex from the catalog]
372
373  SideEffects        []
374
375  SeeAlso            [AbsVertexFree]
376
377******************************************************************************/
378void
379AbsCatalogDelete(
380  AbsVertexCatalog_t *catalog,
381  AbsVertexInfo_t *vertex)
382{
383  AbsVertex_t type;
384  AbsVertexInfo_t *result;
385  lsList vertexList;
386  lsGen listGen;
387  lsHandle item;
388  lsGeneric userData;
389
390  vertexList = 0;
391  type = AbsVertexReadType(vertex);
392
393  /* Select the proper list from the catalog */
394  if (type == fixedPoint_c) {
395    vertexList = AbsVertexCatalogReadFixedPoints(catalog);
396  }
397
398  if (type == and_c || type == xor_c || type == xnor_c) {
399    vertexList = AbsVertexCatalogReadBooleanOps(catalog);
400  }
401
402  if (type == not_c) {
403    vertexList = AbsVertexCatalogReadNegations(catalog);
404  }
405
406  if (type == preImage_c) {
407    vertexList = AbsVertexCatalogReadPreImages(catalog);
408  }
409
410  if (type == identifier_c) {
411    vertexList = AbsVertexCatalogReadIdentifiers(catalog);
412  }
413
414  if (type == variable_c) {
415    vertexList = AbsVertexCatalogReadVariables(catalog);
416  }
417 
418  listGen = lsStart(vertexList);
419  while(lsNext(listGen, &result, &item) == LS_OK) {
420    if (result == vertex) {
421      lsRemoveItem(item, &userData);
422      assert(vertex == (AbsVertexInfo_t *)userData);
423      lsFinish(listGen);
424      return;
425    }
426  }
427
428  (void) fprintf(vis_stderr, "** abs error: Removing non-existent vertex from");
429  (void) fprintf(vis_stderr, " catalog\n");
430
431  return;
432} /* End of AbsCatalogDelete */
433
434/*---------------------------------------------------------------------------*/
435/* Definition of static functions                                            */
436/*---------------------------------------------------------------------------*/
437
438/**Function********************************************************************
439
440  Synopsis           [Find or add a vertex to the list of boolean ops]
441
442  SideEffects        []
443
444  SeeAlso            [AbsVertexCatalogFindOrAdd]
445
446******************************************************************************/
447static AbsVertexInfo_t *
448LookUpBooleanOp(
449  lsList vertexList,
450  AbsVertex_t type,
451  boolean polarity,
452  AbsVertexInfo_t *leftKid,
453  AbsVertexInfo_t *rightKid)
454{
455  lsGen listGen;
456  AbsVertexInfo_t *result;
457
458  /* Start the generator and traverse the list */
459  listGen = lsStart(vertexList);
460  while(lsNext(listGen, &result, NIL(lsHandle)) == LS_OK) {
461    if (AbsVertexReadType(result) == type &&
462        AbsVertexReadLeftKid(result) == leftKid &&
463        AbsVertexReadRightKid(result) == rightKid &&
464        AbsVertexReadPolarity(result) == polarity) {
465      AbsVertexReadRefs(result)++;
466      lsFinish(listGen);
467      return result;
468    }
469  }
470
471  /* Item has not been found */
472  lsFinish(listGen);
473  result = AbsVertexInitialize();
474  lsNewBegin(vertexList, (lsGeneric)result, NIL(lsHandle));
475
476  return result;
477} /* End of LookUpBooleanOp */
478
479/**Function********************************************************************
480
481  Synopsis           [Find or add a vertex to the list of fixedpoints]
482
483  SideEffects        []
484
485  SeeAlso            [AbsVertexCatalogFindOrAdd]
486
487******************************************************************************/
488static AbsVertexInfo_t *
489LookUpFixedPoint(
490  lsList vertexList,
491  boolean polarity,
492  AbsVertexInfo_t *leftKid,
493  int localId)
494{
495  lsGen listGen;
496  AbsVertexInfo_t *result;
497
498  /* Start the generator and traverse the list */
499  listGen = lsStart(vertexList);
500  while(lsNext(listGen, &result, NIL(lsHandle)) == LS_OK) {
501    if (AbsVertexReadLeftKid(result) == leftKid &&
502        AbsVertexReadPolarity(result) == polarity &&
503        AbsVertexReadVarId(AbsVertexReadFpVar(result)) == localId) {
504      AbsVertexReadRefs(result)++;
505      lsFinish(listGen);
506      return result;
507    }
508  }
509
510  /* Item has not been found */
511  lsFinish(listGen);
512  result = AbsVertexInitialize();
513  lsNewBegin(vertexList, (lsGeneric)result, NIL(lsHandle));
514
515  return result;
516} /* End of LookUpFixedPoint */
517
518/**Function********************************************************************
519
520  Synopsis           [Find or add a vertex to the list of identifiers]
521
522  SideEffects        []
523
524  SeeAlso            [AbsVertexCatalogFindOrAdd]
525
526******************************************************************************/
527static AbsVertexInfo_t *
528LookUpIdentifier(
529  lsList vertexList,
530  boolean polarity,
531  char *name,
532  char *value)
533{
534  lsGen listGen;
535  AbsVertexInfo_t *result;
536
537  /* Start the generator and traverse the list */
538  listGen = lsStart(vertexList);
539  while(lsNext(listGen, &result, NIL(lsHandle)) == LS_OK) {
540    if (AbsVertexReadPolarity(result) == polarity &&
541        strcmp(AbsVertexReadName(result), name) == 0 && 
542        strcmp(AbsVertexReadValue(result), value) == 0) {
543      AbsVertexReadRefs(result)++;
544      lsFinish(listGen);
545      return result;
546    }
547  }
548
549  /* Item has not been found */
550  lsFinish(listGen);
551  result = AbsVertexInitialize();
552  lsNewBegin(vertexList, (lsGeneric)result, NIL(lsHandle));
553
554  return result;
555} /* End of LookUpIdentifier */
556
557/**Function********************************************************************
558
559  Synopsis           [Find or add a vertex to the list of preimages]
560
561  SideEffects        []
562
563  SeeAlso            [AbsVertexCatalogFindOrAdd]
564
565******************************************************************************/
566static AbsVertexInfo_t *
567LookUpPreImage(
568  lsList vertexList,
569  boolean polarity,
570  AbsVertexInfo_t *leftKid)
571{
572  lsGen listGen;
573  AbsVertexInfo_t *result;
574
575  /* Start the generator and traverse the list */
576  listGen = lsStart(vertexList);
577  while(lsNext(listGen, &result, NIL(lsHandle)) == LS_OK) {
578    if (AbsVertexReadLeftKid(result) == leftKid &&
579        AbsVertexReadPolarity(result) == polarity) {
580      AbsVertexReadRefs(result)++;
581      lsFinish(listGen);
582      return result;
583    }
584  }
585
586  /* Item has not been found */
587  lsFinish(listGen);
588  result = AbsVertexInitialize();
589  lsNewBegin(vertexList, (lsGeneric)result, NIL(lsHandle));
590
591  return result;
592} /* End of LookUpPreImage */
593
594/**Function********************************************************************
595
596  Synopsis           [Find or add a vertex to the list of variables]
597
598  SideEffects        []
599
600  SeeAlso            [AbsVertexCatalogFindOrAdd]
601
602******************************************************************************/
603static AbsVertexInfo_t *
604LookUpVariable(
605  lsList vertexList,
606  boolean polarity,
607  int localId)
608{
609  lsGen listGen;
610  AbsVertexInfo_t *result;
611
612  /* Start the generator and traverse the list */
613  listGen = lsStart(vertexList);
614  while(lsNext(listGen, &result, NIL(lsHandle)) == LS_OK) {
615    if (AbsVertexReadPolarity(result) == polarity &&
616        AbsVertexReadVarId(result) == localId) {
617      AbsVertexReadRefs(result)++;
618      lsFinish(listGen);
619      return result;
620    }
621  }
622
623  /* Item has not been found */
624  lsFinish(listGen);
625  result = AbsVertexInitialize();
626  lsNewBegin(vertexList, (lsGeneric)result, NIL(lsHandle));
627
628  return result;
629} /* End of LookUpVariable */
630
Note: See TracBrowser for help on using the repository browser.