summaryrefslogtreecommitdiffstats
path: root/src/bdd/mtr/mtr.h
blob: 189ac1be14c5ff5ad8b20d446fa413f8fa606bde (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
/**CHeaderFile*****************************************************************

  FileName    [mtr.h]

  PackageName [mtr]

  Synopsis    [Multiway-branch tree manipulation]

  Description [This package provides two layers of functions. Functions
  of the lower level manipulate multiway-branch trees, implemented
  according to the classical scheme whereby each node points to its
  first child and its previous and next siblings. These functions are
  collected in mtrBasic.c.<p>
  Functions of the upper layer deal with group trees, that is the trees
  used by group sifting to represent the grouping of variables. These
  functions are collected in mtrGroup.c.]

  SeeAlso     [The CUDD package documentation; specifically on group
  sifting.]

  Author      [Fabio Somenzi]

  Copyright   [This file was created at the University of Colorado at
  Boulder.  The University of Colorado at Boulder makes no warranty
  about the suitability of this software for any purpose.  It is
  presented on an AS IS basis.]

  Revision    [$Id: mtr.h,v 1.1.1.1 2003/02/24 22:24:02 wjiang Exp $]

******************************************************************************/

#ifndef __MTR
#define __MTR

/*---------------------------------------------------------------------------*/
/* Nested includes                                                           */
/*---------------------------------------------------------------------------*/

ABC_NAMESPACE_HEADER_START


/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/

#ifndef SIZEOF_VOID_P
#define SIZEOF_VOID_P 4
#endif
#ifndef SIZEOF_INT
#define SIZEOF_INT 4
#endif

#undef CONST
#if defined(__STDC__) || defined(__cplusplus)
#define CONST           const
#else /* !(__STDC__ || __cplusplus) */
#define CONST
#endif /* !(__STDC__ || __cplusplus) */

/* These are potential duplicates. */
#ifndef EXTERN
#   ifdef __cplusplus
#       ifdef ABC_NAMESPACE
#           define EXTERN extern
#       else
#           define EXTERN extern "C"
#       endif
#   else
#       define EXTERN extern
#   endif
#endif

#ifndef ARGS
#define ARGS(protos) protos
#endif

#if defined(__GNUC__)
#define MTR_INLINE __inline__
# if (__GNUC__ >2 || __GNUC_MINOR__ >=7)
#   define MTR_UNUSED __attribute__ ((unused))
# else
#   define MTR_UNUSED
# endif
#else
#define MTR_INLINE
#define MTR_UNUSED
#endif
 
/* Flag definitions */
#define MTR_DEFAULT    0x00000000
#define MTR_TERMINAL     0x00000001
#define MTR_SOFT    0x00000002
#define MTR_FIXED    0x00000004
#define MTR_NEWNODE    0x00000008

/* MTR_MAXHIGH is defined in such a way that on 32-bit and 64-bit
** machines one can cast a value to (int) without generating a negative
** number.
*/
#if SIZEOF_VOID_P == 8 && SIZEOF_INT == 4
#define MTR_MAXHIGH    (((MtrHalfWord) ~0) >> 1)
#else
#define MTR_MAXHIGH    ((MtrHalfWord) ~0)
#endif


/*---------------------------------------------------------------------------*/
/* Stucture declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/

#if SIZEOF_VOID_P == 8 && SIZEOF_INT == 4
typedef unsigned int   MtrHalfWord;
#else
typedef unsigned short MtrHalfWord;
#endif

typedef struct MtrNode {
    MtrHalfWord flags;
    MtrHalfWord low;
    MtrHalfWord size;
    MtrHalfWord index;
    struct MtrNode *parent;
    struct MtrNode *child;
    struct MtrNode *elder;
    struct MtrNode *younger;
} MtrNode;


/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/

/* Flag manipulation macros */
#define MTR_SET(node, flag)        (node->flags |= (flag))
#define MTR_RESET(node, flag)    (node->flags &= ~ (flag))
#define MTR_TEST(node, flag)    (node->flags & (flag))


/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Function prototypes                                                       */
/*---------------------------------------------------------------------------*/

EXTERN MtrNode * Mtr_AllocNode ARGS(());
EXTERN void Mtr_DeallocNode ARGS((MtrNode *node));
EXTERN MtrNode * Mtr_InitTree ARGS(());
EXTERN void Mtr_FreeTree ARGS((MtrNode *node));
EXTERN MtrNode * Mtr_CopyTree ARGS((MtrNode *node, int expansion));
EXTERN void Mtr_MakeFirstChild ARGS((MtrNode *parent, MtrNode *child));
EXTERN void Mtr_MakeLastChild ARGS((MtrNode *parent, MtrNode *child));
EXTERN MtrNode * Mtr_CreateFirstChild ARGS((MtrNode *parent));
EXTERN MtrNode * Mtr_CreateLastChild ARGS((MtrNode *parent));
EXTERN void Mtr_MakeNextSibling ARGS((MtrNode *first, MtrNode *second));
EXTERN void Mtr_PrintTree ARGS((MtrNode *node));
EXTERN MtrNode * Mtr_InitGroupTree ARGS((int lower, int size));
EXTERN MtrNode * Mtr_MakeGroup ARGS((MtrNode *root, unsigned int low, unsigned int high, unsigned int flags));
EXTERN MtrNode * Mtr_DissolveGroup ARGS((MtrNode *group));
EXTERN MtrNode * Mtr_FindGroup ARGS((MtrNode *root, unsigned int low, unsigned int high));
EXTERN int Mtr_SwapGroups ARGS((MtrNode *first, MtrNode *second));
EXTERN void Mtr_PrintGroups ARGS((MtrNode *root, int silent));
EXTERN MtrNode * Mtr_ReadGroups ARGS((FILE *fp, int nleaves));

/**AutomaticEnd***************************************************************/

ABC_NAMESPACE_HEADER_END

#endif /* __MTR */