diff options
Diffstat (limited to 'src/bdd/mtr/mtrGroup.c')
| -rw-r--r-- | src/bdd/mtr/mtrGroup.c | 396 |
1 files changed, 198 insertions, 198 deletions
diff --git a/src/bdd/mtr/mtrGroup.c b/src/bdd/mtr/mtrGroup.c index afc7bfdf..280108c9 100644 --- a/src/bdd/mtr/mtrGroup.c +++ b/src/bdd/mtr/mtrGroup.c @@ -7,20 +7,20 @@ 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> - ] + <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] @@ -60,7 +60,7 @@ ******************************************************************************/ -#include "util.h" +#include "util_hack.h" #include "mtrInt.h" ABC_NAMESPACE_IMPL_START @@ -162,27 +162,27 @@ Mtr_MakeGroup( unsigned int flags /* flags for the new group */) { MtrNode *node, - *first, - *last, - *previous, - *newn; + *first, + *last, + *previous, + *newn; /* Sanity check. */ if (size == 0) - return(NULL); + 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); + 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); + root->flags = flags; + return(root); } /* At this point we know that the new group is properly contained @@ -191,15 +191,15 @@ Mtr_MakeGroup( /* 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); + 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 @@ -208,58 +208,58 @@ Mtr_MakeGroup( 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; + 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); + /* 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); + 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); + /* 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); + 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); + /* 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 @@ -267,40 +267,40 @@ Mtr_MakeGroup( ** 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; + (unsigned int) (last->low + last->size) < low + size) { last = last->younger; } - return(newn); + 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); + 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 @@ -310,26 +310,26 @@ Mtr_MakeGroup( ** 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 */ + 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; + root->child = newn; } else { - previous->younger = newn; + previous->younger = newn; } newn->elder = previous; newn->younger = last->younger; if (last->younger != NULL) { - last->younger->elder = newn; + last->younger->elder = newn; } last->younger = NULL; first->elder = NULL; for (node = first; node != NULL; node = node->younger) { - node->parent = newn; + node->parent = newn; } return(newn); @@ -368,20 +368,20 @@ Mtr_DissolveGroup( /* 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->parent = parent; last->younger = group->younger; if (group->younger != NULL) { - group->younger->elder = last; + group->younger->elder = last; } group->child->elder = group->elder; if (group == parent->child) { - parent->child = group->child; + parent->child = group->child; } else { - group->elder->younger = group->child; + group->elder->younger = group->child; } Mtr_DeallocNode(group); @@ -425,28 +425,28 @@ Mtr_FindGroup( ** 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); + low + size > (unsigned int) (root->low + root->size)) + return(NULL); if (root->size == size && root->low == low) - return(root); + return(root); if (root->child == NULL) - return(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; + 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); + /* The group is contained in the group of node. */ + node = Mtr_FindGroup(node, low, size); + return(node); } else { - return(NULL); + return(NULL); } } /* end of Mtr_FindGroup */ @@ -477,11 +477,11 @@ Mtr_SwapGroups( int sizeSecond; if (second->younger == first) { /* make first first */ - node = first; - first = second; - second = node; + node = first; + first = second; + second = node; } else if (first->younger != second) { /* non-adjacent */ - return(0); + return(0); } sizeFirst = first->size; @@ -491,12 +491,12 @@ Mtr_SwapGroups( parent = first->parent; if (parent == NULL || second->parent != parent) return(0); if (parent->child == first) { - parent->child = second; + parent->child = second; } else { /* first->elder != NULL */ - first->elder->younger = second; + first->elder->younger = second; } if (second->younger != NULL) { - second->younger->elder = first; + second->younger->elder = first; } first->younger = second->younger; second->elder = first->elder; @@ -549,30 +549,30 @@ Mtr_PrintGroups( if (!silent) (void) printf("(%hu",root->low); #endif if (MTR_TEST(root,MTR_TERMINAL) || root->child == NULL) { - if (!silent) (void) printf(","); + 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; - } + 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) { #if SIZEOF_VOID_P == 8 - (void) printf("%u", root->low + root->size - 1); + (void) printf("%u", root->low + root->size - 1); #else - (void) printf("%hu", root->low + root->size - 1); + (void) printf("%hu", root->low + root->size - 1); #endif - 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"); + 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; @@ -625,53 +625,53 @@ Mtr_ReadGroups( 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) { - Mtr_FreeTree(root); - return(NULL); - } else if (low < 0 || low+size > nleaves || size < 1) { - Mtr_FreeTree(root); - return(NULL); - } else if (strlen(attrib) > 8 * sizeof(MtrHalfWord)) { - /* Not enough bits in the flags word to store these many - ** attributes. */ - Mtr_FreeTree(root); - return(NULL); - } + /* Read a triple and check for consistency. */ + err = fscanf(fp, "%d %d %s", &low, &size, attrib); + if (err == EOF) { + break; + } else if (err != 3) { + Mtr_FreeTree(root); + return(NULL); + } else if (low < 0 || low+size > nleaves || size < 1) { + Mtr_FreeTree(root); + return(NULL); + } else if (strlen(attrib) > 8 * sizeof(MtrHalfWord)) { + /* Not enough bits in the flags word to store these many + ** attributes. */ + Mtr_FreeTree(root); + 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; + /* 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) { + Mtr_FreeTree(root); + return(NULL); } - } - node = Mtr_MakeGroup(root, (MtrHalfWord) low, (MtrHalfWord) size, - flags); - if (node == NULL) { - Mtr_FreeTree(root); - return(NULL); - } } return(root); @@ -720,11 +720,11 @@ mtrShiftHL( 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); + auxnode = node->child; + do { + if (!mtrShiftHL(auxnode,shift)) return(0); + auxnode = auxnode->younger; + } while (auxnode != NULL); } return(1); |