source: vis_dev/glu-2.3/src/mtr/mtr.h @ 76

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

library glu 2.3

File size: 6.9 KB
Line 
1/**CHeaderFile*****************************************************************
2
3  FileName    [mtr.h]
4
5  PackageName [mtr]
6
7  Synopsis    [Multiway-branch tree manipulation]
8
9  Description [This package provides two layers of functions. Functions
10  of the lower level manipulate multiway-branch trees, implemented
11  according to the classical scheme whereby each node points to its
12  first child and its previous and next siblings. These functions are
13  collected in mtrBasic.c.<p>
14  Functions of the upper layer deal with group trees, that is the trees
15  used by group sifting to represent the grouping of variables. These
16  functions are collected in mtrGroup.c.]
17
18  SeeAlso     [The CUDD package documentation; specifically on group
19  sifting.]
20
21  Author      [Fabio Somenzi]
22
23  Copyright   [Copyright (c) 1995-2004, Regents of the University of Colorado
24
25  All rights reserved.
26
27  Redistribution and use in source and binary forms, with or without
28  modification, are permitted provided that the following conditions
29  are met:
30
31  Redistributions of source code must retain the above copyright
32  notice, this list of conditions and the following disclaimer.
33
34  Redistributions in binary form must reproduce the above copyright
35  notice, this list of conditions and the following disclaimer in the
36  documentation and/or other materials provided with the distribution.
37
38  Neither the name of the University of Colorado nor the names of its
39  contributors may be used to endorse or promote products derived from
40  this software without specific prior written permission.
41
42  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
43  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
44  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
45  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
46  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
47  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
48  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
49  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
50  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
51  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
52  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
53  POSSIBILITY OF SUCH DAMAGE.]
54
55  Revision    [$Id: mtr.h,v 1.14 2009/02/20 02:03:47 fabio Exp $]
56
57******************************************************************************/
58
59#ifndef __MTR
60#define __MTR
61
62/*---------------------------------------------------------------------------*/
63/* Nested includes                                                           */
64/*---------------------------------------------------------------------------*/
65
66#ifdef __cplusplus
67extern "C" {
68#endif
69
70/*---------------------------------------------------------------------------*/
71/* Constant declarations                                                     */
72/*---------------------------------------------------------------------------*/
73
74#ifndef SIZEOF_VOID_P
75#define SIZEOF_VOID_P 4
76#endif
77#ifndef SIZEOF_INT
78#define SIZEOF_INT 4
79#endif
80
81#undef CONST
82#if defined(__STDC__) || defined(__cplusplus)
83#define CONST           const
84#else /* !(__STDC__ || __cplusplus) */
85#define CONST
86#endif /* !(__STDC__ || __cplusplus) */
87
88#if defined(__GNUC__)
89#define MTR_INLINE __inline__
90# if (__GNUC__ >2 || __GNUC_MINOR__ >=7)
91#   define MTR_UNUSED __attribute__ ((unused))
92# else
93#   define MTR_UNUSED
94# endif
95#else
96#define MTR_INLINE
97#define MTR_UNUSED
98#endif
99
100/* Flag definitions */
101#define MTR_DEFAULT     0x00000000
102#define MTR_TERMINAL    0x00000001
103#define MTR_SOFT        0x00000002
104#define MTR_FIXED       0x00000004
105#define MTR_NEWNODE     0x00000008
106
107/* MTR_MAXHIGH is defined in such a way that on 32-bit and 64-bit
108** machines one can cast a value to (int) without generating a negative
109** number.
110*/
111#if SIZEOF_VOID_P == 8 && SIZEOF_INT == 4
112#define MTR_MAXHIGH     (((MtrHalfWord) ~0) >> 1)
113#else
114#define MTR_MAXHIGH     ((MtrHalfWord) ~0)
115#endif
116
117
118/*---------------------------------------------------------------------------*/
119/* Stucture declarations                                                     */
120/*---------------------------------------------------------------------------*/
121
122
123/*---------------------------------------------------------------------------*/
124/* Type declarations                                                         */
125/*---------------------------------------------------------------------------*/
126
127#if SIZEOF_VOID_P == 8 && SIZEOF_INT == 4
128typedef unsigned int   MtrHalfWord;
129#else
130typedef unsigned short MtrHalfWord;
131#endif
132
133typedef struct MtrNode {
134    MtrHalfWord flags;
135    MtrHalfWord low;
136    MtrHalfWord size;
137    MtrHalfWord index;
138    struct MtrNode *parent;
139    struct MtrNode *child;
140    struct MtrNode *elder;
141    struct MtrNode *younger;
142} MtrNode;
143
144
145/*---------------------------------------------------------------------------*/
146/* Variable declarations                                                     */
147/*---------------------------------------------------------------------------*/
148
149
150/*---------------------------------------------------------------------------*/
151/* Macro declarations                                                        */
152/*---------------------------------------------------------------------------*/
153
154/* Flag manipulation macros */
155#define MTR_SET(node, flag)             (node->flags |= (flag))
156#define MTR_RESET(node, flag)   (node->flags &= ~ (flag))
157#define MTR_TEST(node, flag)    (node->flags & (flag))
158
159
160/**AutomaticStart*************************************************************/
161
162/*---------------------------------------------------------------------------*/
163/* Function prototypes                                                       */
164/*---------------------------------------------------------------------------*/
165
166extern MtrNode * Mtr_AllocNode (void);
167extern void Mtr_DeallocNode (MtrNode *node);
168extern MtrNode * Mtr_InitTree (void);
169extern void Mtr_FreeTree (MtrNode *node);
170extern MtrNode * Mtr_CopyTree (MtrNode *node, int expansion);
171extern void Mtr_MakeFirstChild (MtrNode *parent, MtrNode *child);
172extern void Mtr_MakeLastChild (MtrNode *parent, MtrNode *child);
173extern MtrNode * Mtr_CreateFirstChild (MtrNode *parent);
174extern MtrNode * Mtr_CreateLastChild (MtrNode *parent);
175extern void Mtr_MakeNextSibling (MtrNode *first, MtrNode *second);
176extern void Mtr_PrintTree (MtrNode *node);
177extern MtrNode * Mtr_InitGroupTree (int lower, int size);
178extern MtrNode * Mtr_MakeGroup (MtrNode *root, unsigned int low, unsigned int high, unsigned int flags);
179extern MtrNode * Mtr_DissolveGroup (MtrNode *group);
180extern MtrNode * Mtr_FindGroup (MtrNode *root, unsigned int low, unsigned int high);
181extern int Mtr_SwapGroups (MtrNode *first, MtrNode *second);
182extern void Mtr_PrintGroups (MtrNode *root, int silent);
183extern MtrNode * Mtr_ReadGroups (FILE *fp, int nleaves);
184
185/**AutomaticEnd***************************************************************/
186
187#ifdef __cplusplus
188}
189#endif
190
191#endif /* __MTR */
Note: See TracBrowser for help on using the repository browser.