summaryrefslogtreecommitdiffstats
path: root/src/bdd/mtr/mtrGroup.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/bdd/mtr/mtrGroup.c')
-rw-r--r--src/bdd/mtr/mtrGroup.c690
1 files changed, 690 insertions, 0 deletions
diff --git a/src/bdd/mtr/mtrGroup.c b/src/bdd/mtr/mtrGroup.c
new file mode 100644
index 00000000..ae9c5c2f
--- /dev/null
+++ b/src/bdd/mtr/mtrGroup.c
@@ -0,0 +1,690 @@
+/**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.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 */
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-02 19:21:46 +0000