src/mtr/mtr.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  MtrNode

Defines

#define CONST
#define MTR_INLINE
#define MTR_UNUSED
#define MTR_DEFAULT   0x00000000
#define MTR_TERMINAL   0x00000001
#define MTR_SOFT   0x00000002
#define MTR_FIXED   0x00000004
#define MTR_NEWNODE   0x00000008
#define MTR_MAXHIGH   ((MtrHalfWord) ~0)
#define MTR_SET(node, flag)   (node->flags |= (flag))
#define MTR_RESET(node, flag)   (node->flags &= ~ (flag))
#define MTR_TEST(node, flag)   (node->flags & (flag))

Typedefs

typedef unsigned short MtrHalfWord

Functions

MtrNode * Mtr_AllocNode (void)
void Mtr_DeallocNode (MtrNode *node)
MtrNode * Mtr_InitTree (void)
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)
MtrNode * Mtr_InitGroupTree (int lower, int size)
MtrNode * Mtr_MakeGroup (MtrNode *root, unsigned int low, unsigned int high, unsigned int flags)
MtrNode * Mtr_DissolveGroup (MtrNode *group)
MtrNode * Mtr_FindGroup (MtrNode *root, unsigned int low, unsigned int high)
int Mtr_SwapGroups (MtrNode *first, MtrNode *second)
void Mtr_PrintGroups (MtrNode *root, int silent)
MtrNode * Mtr_ReadGroups (FILE *fp, int nleaves)

Define Documentation

#define CONST

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 [Copyright (c) 1995-2004, Regents of the University of Colorado

All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

Neither the name of the University of Colorado nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.]

Revision [

Id
mtr.h,v 1.14 2009/02/20 02:03:47 fabio Exp

]

Definition at line 85 of file mtr.h.

#define MTR_DEFAULT   0x00000000

Definition at line 101 of file mtr.h.

#define MTR_FIXED   0x00000004

Definition at line 104 of file mtr.h.

#define MTR_INLINE

Definition at line 96 of file mtr.h.

#define MTR_MAXHIGH   ((MtrHalfWord) ~0)

Definition at line 114 of file mtr.h.

#define MTR_NEWNODE   0x00000008

Definition at line 105 of file mtr.h.

#define MTR_RESET ( node,
flag   )     (node->flags &= ~ (flag))

Definition at line 156 of file mtr.h.

#define MTR_SET ( node,
flag   )     (node->flags |= (flag))

Definition at line 155 of file mtr.h.

#define MTR_SOFT   0x00000002

Definition at line 103 of file mtr.h.

#define MTR_TERMINAL   0x00000001

Definition at line 102 of file mtr.h.

#define MTR_TEST ( node,
flag   )     (node->flags & (flag))

Definition at line 157 of file mtr.h.

#define MTR_UNUSED

Definition at line 97 of file mtr.h.

Typedef Documentation

typedef unsigned short MtrHalfWord

Definition at line 130 of file mtr.h.

Function Documentation

MtrNode* Mtr_AllocNode ( void   ) 

AutomaticStart

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 117 of file mtrBasic.c.

00118 {
00119     MtrNode *node;
00120 
00121     node = ALLOC(MtrNode,1);
00122     return node;
00123 
00124 } /* 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 214 of file mtrBasic.c.

00217 {
00218     MtrNode *copy;
00219 
00220     if (node == NULL) return(NULL);
00221     if (expansion < 1) return(NULL);
00222     copy = Mtr_AllocNode();
00223     if (copy == NULL) return(NULL);
00224     copy->parent = copy->elder = copy->child = copy->younger = NULL;
00225     if (node->child != NULL) {
00226         copy->child = Mtr_CopyTree(node->child, expansion);
00227         if (copy->child == NULL) {
00228             Mtr_DeallocNode(copy);
00229             return(NULL);
00230         }
00231     }
00232     if (node->younger != NULL) {
00233         copy->younger = Mtr_CopyTree(node->younger, expansion);
00234         if (copy->younger == NULL) {
00235             Mtr_FreeTree(copy);
00236             return(NULL);
00237         }
00238     }
00239     copy->flags = node->flags;
00240     copy->low = node->low * expansion;
00241     copy->size = node->size * expansion;
00242     copy->index = node->index * expansion;
00243     if (copy->younger) copy->younger->elder = copy;
00244     if (copy->child) {
00245         MtrNode *auxnode = copy->child;
00246         while (auxnode != NULL) {
00247             auxnode->parent = copy;
00248             auxnode = auxnode->younger;
00249         }
00250     }
00251     return(copy);
00252 
00253 } /* 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 336 of file mtrBasic.c.

00338 {
00339     MtrNode *child;
00340 
00341     child = Mtr_AllocNode();
00342     if (child == NULL) return(NULL);
00343 
00344     child->child = child->younger = child-> elder = NULL;
00345     child->flags = 0;
00346     Mtr_MakeFirstChild(parent,child);
00347     return(child);
00348 
00349 } /* 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 365 of file mtrBasic.c.

00367 {
00368     MtrNode *child;
00369 
00370     child = Mtr_AllocNode();
00371     if (child == NULL) return(NULL);
00372 
00373     child->child = child->younger = child->elder = NULL;
00374     child->flags = 0;
00375     Mtr_MakeLastChild(parent,child);
00376     return(child);
00377 
00378 } /* end of Mtr_CreateLastChild */

void Mtr_DeallocNode ( MtrNode *  node  ) 

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

Synopsis [Deallocates tree node.]

Description []

SideEffects [None]

SeeAlso [Mtr_AllocNode]

Definition at line 139 of file mtrBasic.c.

00141 {
00142     FREE(node);
00143     return;
00144 
00145 } /* end of Mtr_DeallocNode */

MtrNode* Mtr_DissolveGroup ( MtrNode *  group  ) 

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

Synopsis [Merges the children of `group' with the children of its parent.]

Description [Merges the children of `group' with the children of its parent. Disposes of the node pointed by group. If group is the root of the group tree, this procedure leaves the tree unchanged. Returns the pointer to the parent of `group' upon successful termination; NULL otherwise.]

SideEffects [None]

SeeAlso [Mtr_MakeGroup]

Definition at line 355 of file mtrGroup.c.

00357 {
00358     MtrNode *parent;
00359     MtrNode *last;
00360 
00361     parent = group->parent;
00362 
00363     if (parent == NULL) return(NULL);
00364     if (MTR_TEST(group,MTR_TERMINAL) || group->child == NULL) return(NULL);
00365 
00366     /* Make all children of group children of its parent, and make
00367     ** last point to the last child of group. */
00368     for (last = group->child; last->younger != NULL; last = last->younger) {
00369         last->parent = parent;
00370     }
00371     last->parent = parent;
00372 
00373     last->younger = group->younger;
00374     if (group->younger != NULL) {
00375         group->younger->elder = last;
00376     }
00377 
00378     group->child->elder = group->elder;
00379     if (group == parent->child) {
00380         parent->child = group->child;
00381     } else {
00382         group->elder->younger = group->child;
00383     }
00384 
00385     Mtr_DeallocNode(group);
00386     return(parent);
00387 
00388 } /* end of Mtr_DissolveGroup */

MtrNode* Mtr_FindGroup ( MtrNode *  root,
unsigned int  low,
unsigned int  size 
)

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

Synopsis [Finds a group with size leaves starting at low, if it exists.]

Description [Finds a group with size leaves starting at low, if it exists. This procedure relies on the low and size fields of each node. It also assumes that the children of each node are sorted in order of increasing low. Returns the pointer to the root of the group upon successful termination; NULL otherwise.]

SideEffects [None]

SeeAlso []

Definition at line 407 of file mtrGroup.c.

00411 {
00412     MtrNode *node;
00413 
00414 #ifdef MTR_DEBUG
00415     /* We cannot have a non-empty proper subgroup of a singleton set. */
00416     assert(!MTR_TEST(root,MTR_TERMINAL));
00417 #endif
00418 
00419     /* Sanity check. */
00420     if (size < 1) return(NULL);
00421 
00422     /* Check whether current group includes the group sought.  This
00423     ** check is necessary at the top-level call.  In the subsequent
00424     ** calls it is redundant. */
00425     if (low < (unsigned int) root->low ||
00426         low + size > (unsigned int) (root->low + root->size))
00427         return(NULL);
00428 
00429     if (root->size == size && root->low == low)
00430         return(root);
00431 
00432     if (root->child == NULL)
00433         return(NULL);
00434 
00435     /* Find all chidren of root that are included in the new group. If
00436     ** the group of any child entirely contains the new group, call
00437     ** Mtr_MakeGroup recursively.  */
00438     node = root->child;
00439     while (low >= (unsigned int) (node->low + node->size)) {
00440         node = node->younger;
00441     }
00442     if (low + size <= (unsigned int) (node->low + node->size)) {
00443         /* The group is contained in the group of node. */
00444         node = Mtr_FindGroup(node, low, size);
00445         return(node);
00446     } else {
00447         return(NULL);
00448     }
00449 
00450 } /* end of Mtr_FindGroup */

void Mtr_FreeTree ( MtrNode *  node  ) 

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

Synopsis [Disposes of tree rooted at node.]

Description []

SideEffects [None]

SeeAlso [Mtr_InitTree]

Definition at line 187 of file mtrBasic.c.

00189 {
00190     if (node == NULL) return;
00191     if (! MTR_TEST(node,MTR_TERMINAL)) Mtr_FreeTree(node->child);
00192     Mtr_FreeTree(node->younger);
00193     Mtr_DeallocNode(node);
00194     return;
00195 
00196 } /* end of Mtr_FreeTree */

MtrNode* Mtr_InitGroupTree ( int  lower,
int  size 
)

AutomaticEnd Function********************************************************************

Synopsis [Allocate new tree.]

Description [Allocate new tree with one node, whose low and size fields are specified by the lower and size parameters. Returns pointer to tree root.]

SideEffects [None]

SeeAlso [Mtr_InitTree Mtr_FreeTree]

Definition at line 119 of file mtrGroup.c.

00122 {
00123     MtrNode *root;
00124 
00125     root = Mtr_InitTree();
00126     if (root == NULL) return(NULL);
00127     root->flags = MTR_DEFAULT;
00128     root->low = lower;
00129     root->size = size;
00130     return(root);
00131 
00132 } /* end of Mtr_InitGroupTree */

MtrNode* Mtr_InitTree ( void   ) 

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 160 of file mtrBasic.c.

00161 {
00162     MtrNode *node;
00163 
00164     node = Mtr_AllocNode();
00165     if (node == NULL) return(NULL);
00166 
00167     node->parent = node->child = node->elder = node->younger = NULL;
00168     node->flags = 0;
00169 
00170     return(node);
00171 
00172 } /* 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 268 of file mtrBasic.c.

00271 {
00272     child->parent = parent;
00273     child->younger = parent->child;
00274     child->elder = NULL;
00275     if (parent->child != NULL) {
00276 #ifdef MTR_DEBUG
00277         assert(parent->child->elder == NULL);
00278 #endif
00279         parent->child->elder = child;
00280     }
00281     parent->child = child;
00282     return;
00283 
00284 } /* end of Mtr_MakeFirstChild */

MtrNode* Mtr_MakeGroup ( MtrNode *  root,
unsigned int  low,
unsigned int  size,
unsigned int  flags 
)

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

Synopsis [Makes a new group with size leaves starting at low.]

Description [Makes a new group with size leaves starting at low. If the new group intersects an existing group, it must either contain it or be contained by it. This procedure relies on the low and size fields of each node. It also assumes that the children of each node are sorted in order of increasing low. In case of a valid request, the flags of the new group are set to the value passed in `flags.' This can also be used to change the flags of an existing group. Returns the pointer to the root of the new group upon successful termination; NULL otherwise. If the group already exists, the pointer to its root is returned.]

SideEffects [None]

SeeAlso [Mtr_DissolveGroup Mtr_ReadGroups Mtr_FindGroup]

Definition at line 156 of file mtrGroup.c.

00161 {
00162     MtrNode *node,
00163             *first,
00164             *last,
00165             *previous,
00166             *newn;
00167 
00168     /* Sanity check. */
00169     if (size == 0)
00170         return(NULL);
00171 
00172     /* Check whether current group includes new group.  This check is
00173     ** necessary at the top-level call.  In the subsequent calls it is
00174     ** redundant. */
00175     if (low < (unsigned int) root->low ||
00176         low + size > (unsigned int) (root->low + root->size))
00177         return(NULL);
00178 
00179     /* Trying to create an existing group has the effect of updating
00180     ** the flags. */
00181     if (root->size == size && root->low == low) {
00182         root->flags = flags;
00183         return(root);
00184     }
00185 
00186     /* At this point we know that the new group is properly contained
00187     ** in the group of root. We have two possible cases here: - root
00188     ** is a terminal node; - root has children. */
00189 
00190     /* Root has no children: create a new group. */
00191     if (root->child == NULL) {
00192         newn = Mtr_AllocNode();
00193         if (newn == NULL) return(NULL); /* out of memory */
00194         newn->low = low;
00195         newn->size = size;
00196         newn->flags = flags;
00197         newn->parent = root;
00198         newn->elder = newn->younger = newn->child = NULL;
00199         root->child = newn;
00200         return(newn);
00201     }
00202 
00203     /* Root has children: Find all chidren of root that are included
00204     ** in the new group. If the group of any child entirely contains
00205     ** the new group, call Mtr_MakeGroup recursively. */
00206     previous = NULL;
00207     first = root->child; /* guaranteed to be non-NULL */
00208     while (first != NULL && low >= (unsigned int) (first->low + first->size)) {
00209         previous = first;
00210         first = first->younger;
00211     }
00212     if (first == NULL) {
00213         /* We have scanned the entire list and we need to append a new
00214         ** child at the end of it.  Previous points to the last child
00215         ** of root. */
00216         newn = Mtr_AllocNode();
00217         if (newn == NULL) return(NULL); /* out of memory */
00218         newn->low = low;
00219         newn->size = size;
00220         newn->flags = flags;
00221         newn->parent = root;
00222         newn->elder = previous;
00223         previous->younger = newn;
00224         newn->younger = newn->child = NULL;
00225         return(newn);
00226     }
00227     /* Here first is non-NULL and low < first->low + first->size. */
00228     if (low >= (unsigned int) first->low &&
00229         low + size <= (unsigned int) (first->low + first->size)) {
00230         /* The new group is contained in the group of first. */
00231         newn = Mtr_MakeGroup(first, low, size, flags);
00232         return(newn);
00233     } else if (low + size <= first->low) {
00234         /* The new group is entirely contained in the gap between
00235         ** previous and first. */
00236         newn = Mtr_AllocNode();
00237         if (newn == NULL) return(NULL); /* out of memory */
00238         newn->low = low;
00239         newn->size = size;
00240         newn->flags = flags;
00241         newn->child = NULL;
00242         newn->parent = root;
00243         newn->elder = previous;
00244         newn->younger = first;
00245         first->elder = newn;
00246         if (previous != NULL) {
00247             previous->younger = newn;
00248         } else {
00249             root->child = newn;
00250         }
00251         return(newn);
00252     } else if (low < (unsigned int) first->low &&
00253                low + size < (unsigned int) (first->low + first->size)) {
00254         /* Trying to cut an existing group: not allowed. */
00255         return(NULL);
00256     } else if (low > first->low) {
00257         /* The new group neither is contained in the group of first
00258         ** (this was tested above) nor contains it. It is therefore
00259         ** trying to cut an existing group: not allowed. */
00260         return(NULL);
00261     }
00262 
00263     /* First holds the pointer to the first child contained in the new
00264     ** group. Here low <= first->low and low + size >= first->low +
00265     ** first->size.  One of the two inequalities is strict. */
00266     last = first->younger;
00267     while (last != NULL &&
00268            (unsigned int) (last->low + last->size) < low + size) {
00269         last = last->younger;
00270     }
00271     if (last == NULL) {
00272         /* All the chilren of root from first onward become children
00273         ** of the new group. */
00274         newn = Mtr_AllocNode();
00275         if (newn == NULL) return(NULL); /* out of memory */
00276         newn->low = low;
00277         newn->size = size;
00278         newn->flags = flags;
00279         newn->child = first;
00280         newn->parent = root;
00281         newn->elder = previous;
00282         newn->younger = NULL;
00283         first->elder = NULL;
00284         if (previous != NULL) {
00285             previous->younger = newn;
00286         } else {
00287             root->child = newn;
00288         }
00289         last = first;
00290         while (last != NULL) {
00291             last->parent = newn;
00292             last = last->younger;
00293         }
00294         return(newn);
00295     }
00296 
00297     /* Here last != NULL and low + size <= last->low + last->size. */
00298     if (low + size - 1 >= (unsigned int) last->low &&
00299         low + size < (unsigned int) (last->low + last->size)) {
00300         /* Trying to cut an existing group: not allowed. */
00301         return(NULL);
00302     }
00303 
00304     /* First and last point to the first and last of the children of
00305     ** root that are included in the new group. Allocate a new node
00306     ** and make all children of root between first and last chidren of
00307     ** the new node.  Previous points to the child of root immediately
00308     ** preceeding first. If it is NULL, then first is the first child
00309     ** of root. */
00310     newn = Mtr_AllocNode();
00311     if (newn == NULL) return(NULL);     /* out of memory */
00312     newn->low = low;
00313     newn->size = size;
00314     newn->flags = flags;
00315     newn->child = first;
00316     newn->parent = root;
00317     if (previous == NULL) {
00318         root->child = newn;
00319     } else {
00320         previous->younger = newn;
00321     }
00322     newn->elder = previous;
00323     newn->younger = last->younger;
00324     if (last->younger != NULL) {
00325         last->younger->elder = newn;
00326     }
00327     last->younger = NULL;
00328     first->elder = NULL;
00329     for (node = first; node != NULL; node = node->younger) {
00330         node->parent = newn;
00331     }
00332 
00333     return(newn);
00334 
00335 } /* end of Mtr_MakeGroup */

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 299 of file mtrBasic.c.

00302 {
00303     MtrNode *node;
00304 
00305     child->younger = NULL;
00306 
00307     if (parent->child == NULL) {
00308         parent->child = child;
00309         child->elder = NULL;
00310     } else {
00311         for (node = parent->child;
00312              node->younger != NULL;
00313              node = node->younger);
00314         node->younger = child;
00315         child->elder = node;
00316     }
00317     child->parent = parent;
00318     return;
00319 
00320 } /* 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 394 of file mtrBasic.c.

00397 {
00398     second->younger = first->younger;
00399     if (first->younger != NULL) {
00400         first->younger->elder = second;
00401     }
00402     second->parent = first->parent;
00403     first->younger = second;
00404     second->elder = first;
00405     return;
00406 
00407 } /* end of Mtr_MakeNextSibling */

void Mtr_PrintGroups ( MtrNode *  root,
int  silent 
)

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

Synopsis [Prints the groups as a parenthesized list.]

Description [Prints the groups as a parenthesized list. After each group, the group's flag are printed, preceded by a `|'. For each flag (except MTR_TERMINAL) a character is printed.

  • F: MTR_FIXED
  • N: MTR_NEWNODE
  • S: MTR_SOFT

The second argument, silent, if different from 0, causes Mtr_PrintGroups to only check the syntax of the group tree. ]

SideEffects [None]

SeeAlso [Mtr_PrintTree]

Definition at line 535 of file mtrGroup.c.

00538 {
00539     MtrNode *node;
00540 
00541     assert(root != NULL);
00542     assert(root->younger == NULL || root->younger->elder == root);
00543     assert(root->elder == NULL || root->elder->younger == root);
00544 #if SIZEOF_VOID_P == 8
00545     if (!silent) (void) printf("(%u",root->low);
00546 #else
00547     if (!silent) (void) printf("(%hu",root->low);
00548 #endif
00549     if (MTR_TEST(root,MTR_TERMINAL) || root->child == NULL) {
00550         if (!silent) (void) printf(",");
00551     } else {
00552         node = root->child;
00553         while (node != NULL) {
00554             assert(node->low >= root->low && (int) (node->low + node->size) <= (int) (root->low + root->size));
00555             assert(node->parent == root);
00556             Mtr_PrintGroups(node,silent);
00557             node = node->younger;
00558         }
00559     }
00560     if (!silent) {
00561 #if SIZEOF_VOID_P == 8
00562         (void) printf("%u", root->low + root->size - 1);
00563 #else
00564         (void) printf("%hu", root->low + root->size - 1);
00565 #endif
00566         if (root->flags != MTR_DEFAULT) {
00567             (void) printf("|");
00568             if (MTR_TEST(root,MTR_FIXED)) (void) printf("F");
00569             if (MTR_TEST(root,MTR_NEWNODE)) (void) printf("N");
00570             if (MTR_TEST(root,MTR_SOFT)) (void) printf("S");
00571         }
00572         (void) printf(")");
00573         if (root->parent == NULL) (void) printf("\n");
00574     }
00575     assert((root->flags &~(MTR_TERMINAL | MTR_SOFT | MTR_FIXED | MTR_NEWNODE)) == 0);
00576     return;
00577 
00578 } /* end of Mtr_PrintGroups */

void Mtr_PrintTree ( MtrNode *  node  ) 

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

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

Description []

SideEffects [None]

SeeAlso [Mtr_PrintGroups]

Definition at line 422 of file mtrBasic.c.

00424 {
00425     if (node == NULL) return;
00426     (void) fprintf(stdout,
00427 #if SIZEOF_VOID_P == 8
00428     "N=0x%-8lx C=0x%-8lx Y=0x%-8lx E=0x%-8lx P=0x%-8lx F=%x L=%u S=%u\n",
00429     (unsigned long) node, (unsigned long) node->child,
00430     (unsigned long) node->younger, (unsigned long) node->elder,
00431     (unsigned long) node->parent, node->flags, node->low, node->size);
00432 #else
00433     "N=0x%-8x C=0x%-8x Y=0x%-8x E=0x%-8x P=0x%-8x F=%x L=%hu S=%hu\n",
00434     (unsigned) node, (unsigned) node->child,
00435     (unsigned) node->younger, (unsigned) node->elder,
00436     (unsigned) node->parent, node->flags, node->low, node->size);
00437 #endif
00438     if (!MTR_TEST(node,MTR_TERMINAL)) Mtr_PrintTree(node->child);
00439     Mtr_PrintTree(node->younger);
00440     return;
00441 
00442 } /* end of Mtr_PrintTree */

MtrNode* Mtr_ReadGroups ( FILE *  fp,
int  nleaves 
)

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

Synopsis [Reads groups from a file and creates a group tree.]

Description [Reads groups from a file and creates a group tree. Each group is specified by three fields: <xmp> low size flags. </xmp> Low and size are (short) integers. Flags is a string composed of the following characters (with associated translation):

  • D: MTR_DEFAULT
  • F: MTR_FIXED
  • N: MTR_NEWNODE
  • S: MTR_SOFT
  • T: MTR_TERMINAL

Normally, the only flags that are needed are D and F. Groups and fields are separated by white space (spaces, tabs, and newlines). Returns a pointer to the group tree if successful; NULL otherwise.]

SideEffects [None]

SeeAlso [Mtr_InitGroupTree Mtr_MakeGroup]

Definition at line 609 of file mtrGroup.c.

00612 {
00613     int low;
00614     int size;
00615     int err;
00616     unsigned int flags;
00617     MtrNode *root;
00618     MtrNode *node;
00619     char attrib[8*sizeof(unsigned int)+1];
00620     char *c;
00621 
00622     root = Mtr_InitGroupTree(0,nleaves);
00623     if (root == NULL) return NULL;
00624 
00625     while (! feof(fp)) {
00626         /* Read a triple and check for consistency. */
00627         err = fscanf(fp, "%d %d %s", &low, &size, attrib);
00628         if (err == EOF) {
00629             break;
00630         } else if (err != 3) {
00631             Mtr_FreeTree(root);
00632             return(NULL);
00633         } else if (low < 0 || low+size > nleaves || size < 1) {
00634             Mtr_FreeTree(root);
00635             return(NULL);
00636         } else if (strlen(attrib) > 8 * sizeof(MtrHalfWord)) {
00637             /* Not enough bits in the flags word to store these many
00638             ** attributes. */
00639             Mtr_FreeTree(root);
00640             return(NULL);
00641         }
00642 
00643         /* Parse the flag string. Currently all flags are permitted,
00644         ** to make debugging easier. Normally, specifying NEWNODE
00645         ** wouldn't be allowed. */
00646         flags = MTR_DEFAULT;
00647         for (c=attrib; *c != 0; c++) {
00648             switch (*c) {
00649             case 'D':
00650                 break;
00651             case 'F':
00652                 flags |= MTR_FIXED;
00653                 break;
00654             case 'N':
00655                 flags |= MTR_NEWNODE;
00656                 break;
00657             case 'S':
00658                 flags |= MTR_SOFT;
00659                 break;
00660             case 'T':
00661                 flags |= MTR_TERMINAL;
00662                 break;
00663             default:
00664                 return NULL;
00665             }
00666         }
00667         node = Mtr_MakeGroup(root, (MtrHalfWord) low, (MtrHalfWord) size,
00668                              flags);
00669         if (node == NULL) {
00670             Mtr_FreeTree(root);
00671             return(NULL);
00672         }
00673     }
00674 
00675     return(root);
00676 
00677 } /* end of Mtr_ReadGroups */

int Mtr_SwapGroups ( MtrNode *  first,
MtrNode *  second 
)

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

Synopsis [Swaps two children of a tree node.]

Description [Swaps two children of a tree node. Adjusts the high and low fields of the two nodes and their descendants. The two children must be adjacent. However, first may be the younger sibling of second. Returns 1 in case of success; 0 otherwise.]

SideEffects [None]

SeeAlso []

Definition at line 468 of file mtrGroup.c.

00471 {
00472     MtrNode *node;
00473     MtrNode *parent;
00474     int sizeFirst;
00475     int sizeSecond;
00476 
00477     if (second->younger == first) { /* make first first */
00478         node = first;
00479         first = second;
00480         second = node;
00481     } else if (first->younger != second) { /* non-adjacent */
00482         return(0);
00483     }
00484 
00485     sizeFirst = first->size;
00486     sizeSecond = second->size;
00487 
00488     /* Swap the two nodes. */
00489     parent = first->parent;
00490     if (parent == NULL || second->parent != parent) return(0);
00491     if (parent->child == first) {
00492         parent->child = second;
00493     } else { /* first->elder != NULL */
00494         first->elder->younger = second;
00495     }
00496     if (second->younger != NULL) {
00497         second->younger->elder = first;
00498     }
00499     first->younger = second->younger;
00500     second->elder = first->elder;
00501     first->elder = second;
00502     second->younger = first;
00503 
00504     /* Adjust the high and low fields. */
00505     if (!mtrShiftHL(first,sizeSecond)) return(0);
00506     if (!mtrShiftHL(second,-sizeFirst)) return(0);
00507 
00508     return(1);
00509 
00510 } /* end of Mtr_SwapGroups */

Generated on Tue Jan 12 13:57:27 2010 for glu-2.2 by  doxygen 1.6.1