mtrgroup.c

主要进行大规模的电路综合

    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 */