src/bdd/mtr/mtrBasic.c File Reference

#include "util_hack.h"
#include "mtrInt.h"
Include dependency graph for mtrBasic.c:

Go to the source code of this file.

Functions

MtrNode * Mtr_AllocNode ()
void Mtr_DeallocNode (MtrNode *node)
MtrNode * Mtr_InitTree ()
void Mtr_FreeTree (MtrNode *node)
MtrNode * Mtr_CopyTree (MtrNode *node, int expansion)
void Mtr_MakeFirstChild (MtrNode *parent, MtrNode *child)
void Mtr_MakeLastChild (MtrNode *parent, MtrNode *child)
MtrNode * Mtr_CreateFirstChild (MtrNode *parent)
MtrNode * Mtr_CreateLastChild (MtrNode *parent)
void Mtr_MakeNextSibling (MtrNode *first, MtrNode *second)
void Mtr_PrintTree (MtrNode *node)

Variables

static char rcsid[] MTR_UNUSED = "$Id: mtrBasic.c,v 1.1.1.1 2003/02/24 22:24:02 wjiang Exp $"

Function Documentation

MtrNode* Mtr_AllocNode (  ) 

AutomaticStart AutomaticEnd Function********************************************************************

Synopsis [Allocates new tree node.]

Description [Allocates new tree node. Returns pointer to node.]

SideEffects [None]

SeeAlso [Mtr_DeallocNode]

Definition at line 90 of file mtrBasic.c.

00092 {
00093     MtrNode *node;
00094 
00095     node = ALLOC(MtrNode,1);
00096     return node;
00097 
00098 } /* Mtr_AllocNode */

MtrNode* Mtr_CopyTree ( MtrNode *  node,
int  expansion 
)

Function********************************************************************

Synopsis [Makes a copy of tree.]

Description [Makes a copy of tree. If parameter expansion is greater than 1, it will expand the tree by that factor. It is an error for expansion to be less than 1. Returns a pointer to the copy if successful; NULL otherwise.]

SideEffects [None]

SeeAlso [Mtr_InitTree]

Definition at line 189 of file mtrBasic.c.

00192 {
00193     MtrNode *copy;
00194 
00195     if (node == NULL) return(NULL);
00196     if (expansion < 1) return(NULL);
00197     copy = Mtr_AllocNode();
00198     if (copy == NULL) return(NULL);
00199     copy->parent = copy->elder = copy->child = copy->younger = NULL;
00200     if (node->child != NULL) {
00201         copy->child = Mtr_CopyTree(node->child, expansion);
00202         if (copy->child == NULL) {
00203             Mtr_DeallocNode(copy);
00204             return(NULL);
00205         }
00206     }
00207     if (node->younger != NULL) {
00208         copy->younger = Mtr_CopyTree(node->younger, expansion);
00209         if (copy->younger == NULL) {
00210             Mtr_FreeTree(copy);
00211             return(NULL);
00212         }
00213     }
00214     copy->flags = node->flags;
00215     copy->low = node->low * expansion;
00216     copy->size = node->size * expansion;
00217     copy->index = node->index * expansion;
00218     if (copy->younger) copy->younger->elder = copy;
00219     if (copy->child) {
00220         MtrNode *auxnode = copy->child;
00221         while (auxnode != NULL) {
00222             auxnode->parent = copy;
00223             auxnode = auxnode->younger;
00224         }
00225     }
00226     return(copy);
00227     
00228 } /* end of Mtr_CopyTree */

MtrNode* Mtr_CreateFirstChild ( MtrNode *  parent  ) 

Function********************************************************************

Synopsis [Creates a new node and makes it the first child of parent.]

Description [Creates a new node and makes it the first child of parent. Returns pointer to new child.]

SideEffects [None]

SeeAlso [Mtr_MakeFirstChild Mtr_CreateLastChild]

Definition at line 311 of file mtrBasic.c.

00313 {
00314     MtrNode *child;
00315 
00316     child = Mtr_AllocNode();
00317     if (child == NULL) return(NULL);
00318 
00319     child->child = child->younger = child-> elder = NULL;
00320     child->flags = 0;
00321     Mtr_MakeFirstChild(parent,child);
00322     return(child);
00323 
00324 } /* end of Mtr_CreateFirstChild */

MtrNode* Mtr_CreateLastChild ( MtrNode *  parent  ) 

Function********************************************************************

Synopsis [Creates a new node and makes it the last child of parent.]

Description [Creates a new node and makes it the last child of parent. Returns pointer to new child.]

SideEffects [None]

SeeAlso [Mtr_MakeLastChild Mtr_CreateFirstChild]

Definition at line 340 of file mtrBasic.c.

00342 {
00343     MtrNode *child;
00344 
00345     child = Mtr_AllocNode();
00346     if (child == NULL) return(NULL);
00347 
00348     child->child = child->younger = child->elder = NULL;
00349     child->flags = 0;
00350     Mtr_MakeLastChild(parent,child);
00351     return(child);
00352 
00353 } /* end of Mtr_CreateLastChild */

void Mtr_DeallocNode ( MtrNode *  node  ) 

Function********************************************************************

Synopsis [Deallocates tree node.]

Description []

SideEffects [None]

SeeAlso [Mtr_AllocNode]

Definition at line 113 of file mtrBasic.c.

00115 {
00116     FREE(node);
00117     return;
00118 
00119 } /* end of Mtr_DeallocNode */

void Mtr_FreeTree ( MtrNode *  node  ) 

Function********************************************************************

Synopsis [Disposes of tree rooted at node.]

Description []

SideEffects [None]

SeeAlso [Mtr_InitTree]

Definition at line 162 of file mtrBasic.c.

00164 {
00165     if (node == NULL) return;
00166     if (! MTR_TEST(node,MTR_TERMINAL)) Mtr_FreeTree(node->child);
00167     Mtr_FreeTree(node->younger);
00168     Mtr_DeallocNode(node);
00169     return;
00170 
00171 } /* end of Mtr_FreeTree */

MtrNode* Mtr_InitTree (  ) 

Function********************************************************************

Synopsis [Initializes tree with one node.]

Description [Initializes tree with one node. Returns pointer to node.]

SideEffects [None]

SeeAlso [Mtr_FreeTree Mtr_InitGroupTree]

Definition at line 134 of file mtrBasic.c.

00136 {
00137     MtrNode *node;
00138 
00139     node = Mtr_AllocNode();
00140     if (node == NULL) return(NULL);
00141 
00142     node->parent = node->child = node->elder = node->younger = NULL;
00143     node->flags = 0;
00144 
00145     return(node);
00146 
00147 } /* end of Mtr_InitTree */

void Mtr_MakeFirstChild ( MtrNode *  parent,
MtrNode *  child 
)

Function********************************************************************

Synopsis [Makes child the first child of parent.]

Description []

SideEffects [None]

SeeAlso [Mtr_MakeLastChild Mtr_CreateFirstChild]

Definition at line 243 of file mtrBasic.c.

00246 {
00247     child->parent = parent;
00248     child->younger = parent->child;
00249     child->elder = NULL;
00250     if (parent->child != NULL) {
00251 #ifdef MTR_DEBUG
00252         assert(parent->child->elder == NULL);
00253 #endif
00254         parent->child->elder = child;
00255     }
00256     parent->child = child;
00257     return;
00258 
00259 } /* end of Mtr_MakeFirstChild */

void Mtr_MakeLastChild ( MtrNode *  parent,
MtrNode *  child 
)

Function********************************************************************

Synopsis [Makes child the last child of parent.]

Description []

SideEffects [None]

SeeAlso [Mtr_MakeFirstChild Mtr_CreateLastChild]

Definition at line 274 of file mtrBasic.c.

00277 {
00278     MtrNode *node;
00279 
00280     child->younger = NULL;
00281 
00282     if (parent->child == NULL) {
00283         parent->child = child;
00284         child->elder = NULL;
00285     } else {
00286         for (node = parent->child;
00287              node->younger != NULL;
00288              node = node->younger);
00289         node->younger = child;
00290         child->elder = node;
00291     }
00292     child->parent = parent;
00293     return;
00294 
00295 } /* end of Mtr_MakeLastChild */

void Mtr_MakeNextSibling ( MtrNode *  first,
MtrNode *  second 
)

Function********************************************************************

Synopsis [Makes second the next sibling of first.]

Description [Makes second the next sibling of first. Second becomes a child of the parent of first.]

SideEffects [None]

SeeAlso []

Definition at line 369 of file mtrBasic.c.

00372 {
00373     second->younger = first->younger;
00374     if (first->younger != NULL) {
00375         first->younger->elder = second;
00376     }
00377     second->parent = first->parent;
00378     first->younger = second;
00379     second->elder = first;
00380     return;
00381 
00382 } /* end of Mtr_MakeNextSibling */

void Mtr_PrintTree ( MtrNode *  node  ) 

Function********************************************************************

Synopsis [Prints a tree, one node per line.]

Description []

SideEffects [None]

SeeAlso [Mtr_PrintGroups]

Definition at line 397 of file mtrBasic.c.

00399 {
00400     if (node == NULL) return;
00401     (void) fprintf(stdout,
00402 #if SIZEOF_VOID_P == 8
00403     "N=0x%-8lx C=0x%-8lx Y=0x%-8lx E=0x%-8lx P=0x%-8lx F=%x L=%d S=%d\n",
00404     (unsigned long) node, (unsigned long) node->child,
00405     (unsigned long) node->younger, (unsigned long) node->elder,
00406     (unsigned long) node->parent, node->flags, node->low, node->size);
00407 #else
00408     "N=0x%-8x C=0x%-8x Y=0x%-8x E=0x%-8x P=0x%-8x F=%x L=%d S=%d\n",
00409     (unsigned) node, (unsigned) node->child,
00410     (unsigned) node->younger, (unsigned) node->elder,
00411     (unsigned) node->parent, node->flags, node->low, node->size);
00412 #endif
00413     if (!MTR_TEST(node,MTR_TERMINAL)) Mtr_PrintTree(node->child);
00414     Mtr_PrintTree(node->younger);
00415     return;
00416 
00417 } /* end of Mtr_PrintTree */

Variable Documentation

char rcsid [] MTR_UNUSED = "$Id: mtrBasic.c,v 1.1.1.1 2003/02/24 22:24:02 wjiang Exp $" [static]

CFile***********************************************************************

FileName [mtrBasic.c]

PackageName [mtr]

Synopsis [Basic manipulation of multiway branching trees.]

Description [External procedures included in this module:

]

SeeAlso [cudd package]

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.]

Definition at line 57 of file mtrBasic.c.

Generated on Tue Jan 5 12:19:00 2010 for abc70930 by  doxygen 1.6.1