From 888e5bed5d7f56a5d86d91a6e8e88f3e5a3454dc Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Fri, 29 Jul 2005 08:01:00 -0700 Subject: Version abc50729 --- src/bdd/mtr/mtr.h | 173 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 173 insertions(+) create mode 100644 src/bdd/mtr/mtr.h (limited to 'src/bdd/mtr/mtr.h') diff --git a/src/bdd/mtr/mtr.h b/src/bdd/mtr/mtr.h new file mode 100644 index 00000000..201329ae --- /dev/null +++ b/src/bdd/mtr/mtr.h @@ -0,0 +1,173 @@ +/**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.

+ 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 */ +/*---------------------------------------------------------------------------*/ + + +/*---------------------------------------------------------------------------*/ +/* 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 +# define EXTERN extern "C" +# else +# define EXTERN extern +# endif +#endif +#ifndef ARGS +# if defined(__STDC__) || defined(__cplusplus) +# define ARGS(protos) protos /* ANSI C */ +# else /* !(__STDC__ || __cplusplus) */ +# define ARGS(protos) () /* K&R C */ +# endif /* !(__STDC__ || __cplusplus) */ +#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***************************************************************/ + +#endif /* __MTR */ -- cgit v1.2.3