distr/mtr/mtr.h

   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
  67 extern "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
 128 typedef unsigned int   MtrHalfWord;
 129 #else
 130 typedef unsigned short MtrHalfWord;
 131 #endif
 132
 133 typedef 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
 166 extern MtrNode * Mtr_AllocNode (void);
 167 extern void Mtr_DeallocNode (MtrNode *node);
 168 extern MtrNode * Mtr_InitTree (void);
 169 extern void Mtr_FreeTree (MtrNode *node);
 170 extern MtrNode * Mtr_CopyTree (MtrNode *node, int expansion);
 171 extern void Mtr_MakeFirstChild (MtrNode *parent, MtrNode *child);
 172 extern void Mtr_MakeLastChild (MtrNode *parent, MtrNode *child);
 173 extern MtrNode * Mtr_CreateFirstChild (MtrNode *parent);
 174 extern MtrNode * Mtr_CreateLastChild (MtrNode *parent);
 175 extern void Mtr_MakeNextSibling (MtrNode *first, MtrNode *second);
 176 extern void Mtr_PrintTree (MtrNode *node);
 177 extern MtrNode * Mtr_InitGroupTree (int lower, int size);
 178 extern MtrNode * Mtr_MakeGroup (MtrNode *root, unsigned int low, unsigned int high, unsigned int flags);
 179 extern MtrNode * Mtr_DissolveGroup (MtrNode *group);
 180 extern MtrNode * Mtr_FindGroup (MtrNode *root, unsigned int low, unsigned int high);
 181 extern int Mtr_SwapGroups (MtrNode *first, MtrNode *second);
 182 extern void Mtr_PrintGroups (MtrNode *root, int silent);
 183 extern MtrNode * Mtr_ReadGroups (FILE *fp, int nleaves);
 184
 185 /**AutomaticEnd***************************************************************/
 186
 187 #ifdef __cplusplus
 188 }
 189 #endif
 190
 191 #endif /* __MTR */