Version abc70930

1 files changed, 0 insertions, 690 deletions

diff --git a/src/bdd/mtr/mtrGroup.c b/src/bdd/mtr/mtrGroup.c
deleted file mode 100644
index 363b776b..00000000
--- a/src/bdd/mtr/mtrGroup.c
+++ /dev/null
@@ -1,690 +0,0 @@
-/**CFile***********************************************************************
-
-  FileName    [mtrGroup.c]
-
-  PackageName [mtr]
-
-  Synopsis    [Functions to support group specification for reordering.]
-
-  Description [External procedures included in this module:
-        <ul>
-        <li> Mtr_InitGroupTree()
-        <li> Mtr_MakeGroup()
-        <li> Mtr_DissolveGroup()
-        <li> Mtr_FindGroup()
-        <li> Mtr_SwapGroups()
-        <li> Mtr_PrintGroups()
-        <li> Mtr_ReadGroups()
-        </ul>
-    Static procedures included in this module:
-        <ul>
-        <li> mtrShiftHL
-        </ul>
-        ]
-
-  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.]
-
-******************************************************************************/
-
-#include "util_hack.h"
-#include "mtrInt.h"
-
-/*---------------------------------------------------------------------------*/
-/* Constant declarations                                                     */
-/*---------------------------------------------------------------------------*/
-
-/*---------------------------------------------------------------------------*/
-/* Stucture declarations                                                     */
-/*---------------------------------------------------------------------------*/
-
-/*---------------------------------------------------------------------------*/
-/* Type declarations                                                         */
-/*---------------------------------------------------------------------------*/
-
-/*---------------------------------------------------------------------------*/
-/* Variable declarations                                                     */
-/*---------------------------------------------------------------------------*/
-
-#ifndef lint
-static char rcsid[] MTR_UNUSED = "$Id: mtrGroup.c,v 1.1.1.1 2003/02/24 22:24:02 wjiang Exp $";
-#endif
-
-/*---------------------------------------------------------------------------*/
-/* Macro declarations                                                        */
-/*---------------------------------------------------------------------------*/
-
-/**AutomaticStart*************************************************************/
-
-/*---------------------------------------------------------------------------*/
-/* Static function prototypes                                                */
-/*---------------------------------------------------------------------------*/
-
-static int mtrShiftHL ARGS((MtrNode *node, int shift));
-
-/**AutomaticEnd***************************************************************/
-
-/*---------------------------------------------------------------------------*/
-/* Definition of exported functions                                          */
-/*---------------------------------------------------------------------------*/
-
-
-/**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]
-
-******************************************************************************/
-MtrNode *
-Mtr_InitGroupTree(
-  int  lower,
-  int  size)
-{
-    MtrNode *root;
-
-    root = Mtr_InitTree();
-    if (root == NULL) return(NULL);
-    root->flags = MTR_DEFAULT;
-    root->low = lower;
-    root->size = size;
-    return(root);
-
-} /* end of Mtr_InitGroupTree */
-
-
-/**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]
-
-******************************************************************************/
-MtrNode *
-Mtr_MakeGroup(
-  MtrNode * root /* root of the group tree */,
-  unsigned int  low /* lower bound of the group */,
-  unsigned int  size /* upper bound of the group */,
-  unsigned int  flags /* flags for the new group */)
-{
-    MtrNode *node,
-        *first,
-        *last,
-        *previous,
-        *newn;
-
-    /* Sanity check. */
-    if (size == 0)
-    return(NULL);
-
-    /* Check whether current group includes new group.  This check is
-    ** necessary at the top-level call.  In the subsequent calls it is
-    ** redundant. */
-    if (low < (unsigned int) root->low ||
-    low + size > (unsigned int) (root->low + root->size))
-    return(NULL);
-
-    /* Trying to create an existing group has the effect of updating
-    ** the flags. */
-    if (root->size == size && root->low == low) {
-    root->flags = flags;
-    return(root);
-    }
-
-    /* At this point we know that the new group is properly contained
-    ** in the group of root. We have two possible cases here: - root
-    ** is a terminal node; - root has children. */
-
-    /* Root has no children: create a new group. */
-    if (root->child == NULL) {
-    newn = Mtr_AllocNode();
-    if (newn == NULL) return(NULL);    /* out of memory */
-    newn->low = low;
-    newn->size = size;
-    newn->flags = flags;
-    newn->parent = root;
-    newn->elder = newn->younger = newn->child = NULL;
-    root->child = newn;
-    return(newn);
-    }
-
-    /* Root has children: Find all chidren of root that are included
-    ** in the new group. If the group of any child entirely contains
-    ** the new group, call Mtr_MakeGroup recursively. */
-    previous = NULL;
-    first = root->child; /* guaranteed to be non-NULL */
-    while (first != NULL && low >= (unsigned int) (first->low + first->size)) {
-    previous = first;
-    first = first->younger;
-    }
-    if (first == NULL) {
-    /* We have scanned the entire list and we need to append a new
-    ** child at the end of it.  Previous points to the last child
-    ** of root. */
-    newn = Mtr_AllocNode();
-    if (newn == NULL) return(NULL);    /* out of memory */
-    newn->low = low;
-    newn->size = size;
-    newn->flags = flags;
-    newn->parent = root;
-    newn->elder = previous;
-    previous->younger = newn;
-    newn->younger = newn->child = NULL;
-    return(newn);
-    }
-    /* Here first is non-NULL and low < first->low + first->size. */
-    if (low >= (unsigned int) first->low &&
-    low + size <= (unsigned int) (first->low + first->size)) {
-    /* The new group is contained in the group of first. */
-    newn = Mtr_MakeGroup(first, low, size, flags);
-    return(newn);
-    } else if (low + size <= first->low) {
-    /* The new group is entirely contained in the gap between
-    ** previous and first. */
-    newn = Mtr_AllocNode();
-    if (newn == NULL) return(NULL);    /* out of memory */
-    newn->low = low;
-    newn->size = size;
-    newn->flags = flags;
-    newn->child = NULL;
-    newn->parent = root;
-    newn->elder = previous;
-    newn->younger = first;
-    first->elder = newn;
-    if (previous != NULL) {
-        previous->younger = newn;
-    } else {
-        root->child = newn;
-    }
-    return(newn);
-    } else if (low < (unsigned int) first->low &&
-           low + size < (unsigned int) (first->low + first->size)) {
-    /* Trying to cut an existing group: not allowed. */
-    return(NULL);
-    } else if (low > first->low) {
-    /* The new group neither is contained in the group of first
-    ** (this was tested above) nor contains it. It is therefore
-    ** trying to cut an existing group: not allowed. */
-    return(NULL);
-    }
-
-    /* First holds the pointer to the first child contained in the new
-    ** group. Here low <= first->low and low + size >= first->low +
-    ** first->size.  One of the two inequalities is strict. */
-    last = first->younger;
-    while (last != NULL &&
-       (unsigned int) (last->low + last->size) < low + size) {
-    last = last->younger;
-    }
-    if (last == NULL) {
-    /* All the chilren of root from first onward become children
-    ** of the new group. */
-    newn = Mtr_AllocNode();
-    if (newn == NULL) return(NULL);    /* out of memory */
-    newn->low = low;
-    newn->size = size;
-    newn->flags = flags;
-    newn->child = first;
-    newn->parent = root;
-    newn->elder = previous;
-    newn->younger = NULL;
-    first->elder = NULL;
-    if (previous != NULL) {
-        previous->younger = newn;
-    } else {
-        root->child = newn;
-    }
-    last = first;
-    while (last != NULL) {
-        last->parent = newn;
-        last = last->younger;
-    }
-    return(newn);
-    }
-
-    /* Here last != NULL and low + size <= last->low + last->size. */
-    if (low + size - 1 >= (unsigned int) last->low &&
-    low + size < (unsigned int) (last->low + last->size)) {
-    /* Trying to cut an existing group: not allowed. */
-    return(NULL);
-    }
-
-    /* First and last point to the first and last of the children of
-    ** root that are included in the new group. Allocate a new node
-    ** and make all children of root between first and last chidren of
-    ** the new node.  Previous points to the child of root immediately
-    ** preceeding first. If it is NULL, then first is the first child
-    ** of root. */
-    newn = Mtr_AllocNode();
-    if (newn == NULL) return(NULL);    /* out of memory */
-    newn->low = low;
-    newn->size = size;
-    newn->flags = flags;
-    newn->child = first;
-    newn->parent = root;
-    if (previous == NULL) {
-    root->child = newn;
-    } else {
-    previous->younger = newn;
-    }
-    newn->elder = previous;
-    newn->younger = last->younger;
-    if (last->younger != NULL) {
-    last->younger->elder = newn;
-    }
-    last->younger = NULL;
-    first->elder = NULL;
-    for (node = first; node != NULL; node = node->younger) {
-    node->parent = newn;
-    }
-
-    return(newn);
-
-} /* end of Mtr_MakeGroup */
-
-
-/**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]
-
-******************************************************************************/
-MtrNode *
-Mtr_DissolveGroup(
-  MtrNode * group /* group to be dissolved */)
-{
-    MtrNode *parent;
-    MtrNode *last;
-
-    parent = group->parent;
-
-    if (parent == NULL) return(NULL);
-    if (MTR_TEST(group,MTR_TERMINAL) || group->child == NULL) return(NULL);
-
-    /* Make all children of group children of its parent, and make
-    ** last point to the last child of group. */
-    for (last = group->child; last->younger != NULL; last = last->younger) {
-    last->parent = parent;
-    }
-    last->parent = parent;
-
-    last->younger = group->younger;
-    if (group->younger != NULL) {
-    group->younger->elder = last;
-    }
-
-    group->child->elder = group->elder;
-    if (group == parent->child) {
-    parent->child = group->child;
-    } else {
-    group->elder->younger = group->child;
-    }
-
-    Mtr_DeallocNode(group);
-    return(parent);
-
-} /* end of Mtr_DissolveGroup */
-
-
-/**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     []
-
-******************************************************************************/
-MtrNode *
-Mtr_FindGroup(
-  MtrNode * root /* root of the group tree */,
-  unsigned int  low /* lower bound of the group */,
-  unsigned int  size /* upper bound of the group */)
-{
-    MtrNode *node;
-
-#ifdef MTR_DEBUG
-    /* We cannot have a non-empty proper subgroup of a singleton set. */
-    assert(!MTR_TEST(root,MTR_TERMINAL));
-#endif
-
-    /* Sanity check. */
-    if (size < 1) return(NULL);
-
-    /* Check whether current group includes the group sought.  This
-    ** check is necessary at the top-level call.  In the subsequent
-    ** calls it is redundant. */
-    if (low < (unsigned int) root->low ||
-    low + size > (unsigned int) (root->low + root->size))
-    return(NULL);
-
-    if (root->size == size && root->low == low)
-    return(root);
-
-    if (root->child == NULL)
-    return(NULL);
-
-    /* Find all chidren of root that are included in the new group. If
-    ** the group of any child entirely contains the new group, call
-    ** Mtr_MakeGroup recursively.  */
-    node = root->child;
-    while (low >= (unsigned int) (node->low + node->size)) {
-    node = node->younger;
-    }
-    if (low + size <= (unsigned int) (node->low + node->size)) {
-    /* The group is contained in the group of node. */
-    node = Mtr_FindGroup(node, low, size);
-    return(node);
-    } else {
-    return(NULL);
-    }
-
-} /* end of Mtr_FindGroup */
-
-
-/**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     []
-
-******************************************************************************/
-int
-Mtr_SwapGroups(
-  MtrNode * first /* first node to be swapped */,
-  MtrNode * second /* second node to be swapped */)
-{
-    MtrNode *node;
-    MtrNode *parent;
-    int sizeFirst;
-    int sizeSecond;
-
-    if (second->younger == first) { /* make first first */
-    node = first;
-    first = second;
-    second = node;
-    } else if (first->younger != second) { /* non-adjacent */
-    return(0);
-    }
-
-    sizeFirst = first->size;
-    sizeSecond = second->size;
-
-    /* Swap the two nodes. */
-    parent = first->parent;
-    if (parent == NULL || second->parent != parent) return(0);
-    if (parent->child == first) {
-    parent->child = second;
-    } else { /* first->elder != NULL */
-    first->elder->younger = second;
-    }
-    if (second->younger != NULL) {
-    second->younger->elder = first;
-    }
-    first->younger = second->younger;
-    second->elder = first->elder;
-    first->elder = second;
-    second->younger = first;
-
-    /* Adjust the high and low fields. */
-    if (!mtrShiftHL(first,sizeSecond)) return(0);
-    if (!mtrShiftHL(second,-sizeFirst)) return(0);
-
-    return(1);
-
-} /* end of Mtr_SwapGroups */
-
-
-/**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.
-  <ul>
-  <li>F: MTR_FIXED
-  <li>N: MTR_NEWNODE
-  <li>S: MTR_SOFT
-  </ul>
-  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]
-
-******************************************************************************/
-void
-Mtr_PrintGroups(
-  MtrNode * root /* root of the group tree */,
-  int  silent /* flag to check tree syntax only */)
-{
-    MtrNode *node;
-
-    assert(root != NULL);
-    assert(root->younger == NULL || root->younger->elder == root);
-    assert(root->elder == NULL || root->elder->younger == root);
-    if (!silent) (void) printf("(%d",root->low);
-    if (MTR_TEST(root,MTR_TERMINAL) || root->child == NULL) {
-    if (!silent) (void) printf(",");
-    } else {
-    node = root->child;
-    while (node != NULL) {
-        assert(node->low >= root->low && (int) (node->low + node->size) <= (int) (root->low + root->size));
-        assert(node->parent == root);
-        Mtr_PrintGroups(node,silent);
-        node = node->younger;
-    }
-    }
-    if (!silent) {
-    (void) printf("%d", root->low + root->size - 1);
-    if (root->flags != MTR_DEFAULT) {
-        (void) printf("|");
-        if (MTR_TEST(root,MTR_FIXED)) (void) printf("F");
-        if (MTR_TEST(root,MTR_NEWNODE)) (void) printf("N");
-        if (MTR_TEST(root,MTR_SOFT)) (void) printf("S");
-    }
-    (void) printf(")");
-    if (root->parent == NULL) (void) printf("\n");
-    }
-    assert((root->flags &~(MTR_TERMINAL | MTR_SOFT | MTR_FIXED | MTR_NEWNODE)) == 0);
-    return;
-
-} /* end of Mtr_PrintGroups */
-
-
-/**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):
-  <ul>
-  <li>D: MTR_DEFAULT
-  <li>F: MTR_FIXED
-  <li>N: MTR_NEWNODE
-  <li>S: MTR_SOFT
-  <li>T: MTR_TERMINAL
-  </ul>
-  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]
-
-******************************************************************************/
-MtrNode *
-Mtr_ReadGroups(
-  FILE * fp /* file pointer */,
-  int  nleaves /* number of leaves of the new tree */)
-{
-    int low;
-    int size;
-    int err;
-    unsigned int flags;
-    MtrNode *root;
-    MtrNode *node;
-    char attrib[8*sizeof(unsigned int)+1];
-    char *c;
-
-    root = Mtr_InitGroupTree(0,nleaves);
-    if (root == NULL) return NULL;
-
-    while (! feof(fp)) {
-    /* Read a triple and check for consistency. */
-    err = fscanf(fp, "%d %d %s", &low, &size, attrib);
-    if (err == EOF) {
-        break;
-    } else if (err != 3) {
-        return(NULL);
-    } else if (low < 0 || low+size > nleaves || size < 1) {
-        return(NULL);
-    } else if (strlen(attrib) > 8 * sizeof(MtrHalfWord)) {
-        /* Not enough bits in the flags word to store these many
-        ** attributes. */
-        return(NULL);
-    }
-
-    /* Parse the flag string. Currently all flags are permitted,
-    ** to make debugging easier. Normally, specifying NEWNODE
-    ** wouldn't be allowed. */
-    flags = MTR_DEFAULT;
-    for (c=attrib; *c != 0; c++) {
-        switch (*c) {
-        case 'D':
-        break;
-        case 'F':
-        flags |= MTR_FIXED;
-        break;
-        case 'N':
-        flags |= MTR_NEWNODE;
-        break;
-        case 'S':
-        flags |= MTR_SOFT;
-        break;
-        case 'T':
-        flags |= MTR_TERMINAL;
-        break;
-        default:
-        return NULL;
-        }
-    }
-    node = Mtr_MakeGroup(root, (MtrHalfWord) low, (MtrHalfWord) size,
-                 flags);
-    if (node == NULL) return(NULL);
-    }
-
-    return(root);
-
-} /* end of Mtr_ReadGroups */
-
-
-/*---------------------------------------------------------------------------*/
-/* Definition of internal functions                                          */
-/*---------------------------------------------------------------------------*/
-
-/*---------------------------------------------------------------------------*/
-/* Definition of static functions                                            */
-/*---------------------------------------------------------------------------*/
-
-
-/**Function********************************************************************
-
-  Synopsis    [Adjusts the low fields of a node and its descendants.]
-
-  Description [Adjusts the low fields of a node and its
-  descendants. Adds shift to low of each node. Checks that no
-  out-of-bounds values result.  Returns 1 in case of success; 0
-  otherwise.]
-
-  SideEffects [None]
-
-  SeeAlso     []
-
-******************************************************************************/
-static int
-mtrShiftHL(
-  MtrNode * node /* group tree node */,
-  int  shift /* amount by which low should be changed */)
-{
-    MtrNode *auxnode;
-    int low;
-
-    low = (int) node->low;
-
-
-    low += shift;
-
-    if (low < 0 || low + (int) (node->size - 1) > (int) MTR_MAXHIGH) return(0);
-
-    node->low = (MtrHalfWord) low;
-
-    if (!MTR_TEST(node,MTR_TERMINAL) && node->child != NULL) {
-    auxnode = node->child;
-    do {
-        if (!mtrShiftHL(auxnode,shift)) return(0);
-        auxnode = auxnode->younger;
-    } while (auxnode != NULL);
-    }
-
-    return(1);
-
-} /* end of mtrShiftHL */
-