source: icGREP/icgrep-devel/cudd-2.5.1/mtr/mtrGroup.c @ 5815

Last change on this file since 5815 was 4597, checked in by nmedfort, 4 years ago

Upload of the CUDD library.

File size: 26.8 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [mtrGroup.c]
4
5  PackageName [mtr]
6
7  Synopsis    [Functions to support group specification for reordering.]
8
9  Description [External procedures included in this module:
10            <ul>
11            <li> Mtr_InitGroupTree()
12            <li> Mtr_MakeGroup()
13            <li> Mtr_DissolveGroup()
14            <li> Mtr_FindGroup()
15            <li> Mtr_SwapGroups()
16            <li> Mtr_ReorderGroups()
17            <li> Mtr_PrintGroups()
18            <li> Mtr_ReadGroups()
19            </ul>
20        Static procedures included in this module:
21            <ul>
22            <li> mtrShiftHL
23            </ul>
24            ]
25
26  SeeAlso     [cudd package]
27
28  Author      [Fabio Somenzi]
29
30  Copyright   [Copyright (c) 1995-2012, Regents of the University of Colorado
31
32  All rights reserved.
33
34  Redistribution and use in source and binary forms, with or without
35  modification, are permitted provided that the following conditions
36  are met:
37
38  Redistributions of source code must retain the above copyright
39  notice, this list of conditions and the following disclaimer.
40
41  Redistributions in binary form must reproduce the above copyright
42  notice, this list of conditions and the following disclaimer in the
43  documentation and/or other materials provided with the distribution.
44
45  Neither the name of the University of Colorado nor the names of its
46  contributors may be used to endorse or promote products derived from
47  this software without specific prior written permission.
48
49  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
50  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
51  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
52  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
53  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
54  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
55  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
56  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
57  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
58  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
59  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
60  POSSIBILITY OF SUCH DAMAGE.]
61
62******************************************************************************/
63
64#include "util.h"
65#include "mtrInt.h"
66
67/*---------------------------------------------------------------------------*/
68/* Constant declarations                                                     */
69/*---------------------------------------------------------------------------*/
70
71/*---------------------------------------------------------------------------*/
72/* Stucture declarations                                                     */
73/*---------------------------------------------------------------------------*/
74
75/*---------------------------------------------------------------------------*/
76/* Type declarations                                                         */
77/*---------------------------------------------------------------------------*/
78
79/*---------------------------------------------------------------------------*/
80/* Variable declarations                                                     */
81/*---------------------------------------------------------------------------*/
82
83#ifndef lint
84static char rcsid[] MTR_UNUSED = "$Id: mtrGroup.c,v 1.23 2015/01/04 23:26:36 fabio Exp $";
85#endif
86
87/*---------------------------------------------------------------------------*/
88/* Macro declarations                                                        */
89/*---------------------------------------------------------------------------*/
90
91/**AutomaticStart*************************************************************/
92
93/*---------------------------------------------------------------------------*/
94/* Static function prototypes                                                */
95/*---------------------------------------------------------------------------*/
96
97static int mtrShiftHL (MtrNode *node, int shift);
98
99/**AutomaticEnd***************************************************************/
100
101/*---------------------------------------------------------------------------*/
102/* Definition of exported functions                                          */
103/*---------------------------------------------------------------------------*/
104
105
106/**Function********************************************************************
107
108  Synopsis    [Allocate new tree.]
109
110  Description [Allocate new tree with one node, whose low and size
111  fields are specified by the lower and size parameters.
112  Returns pointer to tree root.]
113
114  SideEffects [None]
115
116  SeeAlso     [Mtr_InitTree Mtr_FreeTree]
117
118******************************************************************************/
119MtrNode *
120Mtr_InitGroupTree(
121  int  lower,
122  int  size)
123{
124    MtrNode *root;
125
126    root = Mtr_InitTree();
127    if (root == NULL) return(NULL);
128    root->flags = MTR_DEFAULT;
129    root->low = lower;
130    root->size = size;
131    return(root);
132
133} /* end of Mtr_InitGroupTree */
134
135
136/**Function********************************************************************
137
138  Synopsis    [Makes a new group with size leaves starting at low.]
139
140  Description [Makes a new group with size leaves starting at low.
141  If the new group intersects an existing group, it must
142  either contain it or be contained by it.  This procedure relies on
143  the low and size fields of each node. It also assumes that the
144  children of each node are sorted in order of increasing low.  In
145  case of a valid request, the flags of the new group are set to the
146  value passed in `flags.'  Returns the pointer to the root of the new
147  group upon successful termination; NULL otherwise. If the group
148  already exists, the pointer to its root is returned.]
149
150  SideEffects [None]
151
152  SeeAlso     [Mtr_DissolveGroup Mtr_ReadGroups Mtr_FindGroup]
153
154******************************************************************************/
155MtrNode *
156Mtr_MakeGroup(
157  MtrNode * root /* root of the group tree */,
158  unsigned int  low /* lower bound of the group */,
159  unsigned int  size /* size of the group */,
160  unsigned int  flags /* flags for the new group */)
161{
162    MtrNode *node,
163            *first,
164            *last,
165            *previous,
166            *newn;
167
168    /* Sanity check. */
169    if (size == 0)
170        return(NULL);
171
172    /* Check whether current group includes new group.  This check is
173    ** necessary at the top-level call.  In the subsequent calls it is
174    ** redundant. */
175    if (low < (unsigned int) root->low ||
176        low + size > (unsigned int) (root->low + root->size))
177        return(NULL);
178
179    /* At this point we know that the new group is contained
180    ** in the group of root. We have two possible cases here:
181    **  - root is a terminal node;
182    **  - root has children.       */
183
184    /* Root has no children: create a new group. */
185    if (root->child == NULL) {
186        newn = Mtr_AllocNode();
187        if (newn == NULL) return(NULL); /* out of memory */
188        newn->low = low;
189        newn->size = size;
190        newn->flags = flags;
191        newn->parent = root;
192        newn->elder = newn->younger = newn->child = NULL;
193        root->child = newn;
194        return(newn);
195    }
196
197    /* Root has children: Find all children of root that are included
198    ** in the new group.  If the group of any child entirely contains
199    ** the new group, call Mtr_MakeGroup recursively. */
200    previous = NULL;
201    first = root->child; /* guaranteed to be non-NULL */
202    while (first != NULL && low >= (unsigned int) (first->low + first->size)) {
203        previous = first;
204        first = first->younger;
205    }
206    if (first == NULL) {
207        /* We have scanned the entire list and we need to append a new
208        ** child at the end of it.  Previous points to the last child
209        ** of root. */
210        newn = Mtr_AllocNode();
211        if (newn == NULL) return(NULL); /* out of memory */
212        newn->low = low;
213        newn->size = size;
214        newn->flags = flags;
215        newn->parent = root;
216        newn->elder = previous;
217        previous->younger = newn;
218        newn->younger = newn->child = NULL;
219        return(newn);
220    }
221    /* Here first is non-NULL and low < first->low + first->size. */
222    if (low >= (unsigned int) first->low &&
223        low + size <= (unsigned int) (first->low + first->size)) {
224        /* The new group is contained in the group of first. */
225        newn = Mtr_MakeGroup(first, low, size, flags);
226        return(newn);
227    } else if (low + size <= first->low) {
228        /* The new group is entirely contained in the gap between
229        ** previous and first. */
230        newn = Mtr_AllocNode();
231        if (newn == NULL) return(NULL); /* out of memory */
232        newn->low = low;
233        newn->size = size;
234        newn->flags = flags;
235        newn->child = NULL;
236        newn->parent = root;
237        newn->elder = previous;
238        newn->younger = first;
239        first->elder = newn;
240        if (previous != NULL) {
241            previous->younger = newn;
242        } else {
243            root->child = newn;
244        }
245        return(newn);
246    } else if (low < (unsigned int) first->low &&
247               low + size < (unsigned int) (first->low + first->size)) {
248        /* Trying to cut an existing group: not allowed. */
249        return(NULL);
250    } else if (low > first->low) {
251        /* The new group neither is contained in the group of first
252        ** (this was tested above) nor contains it. It is therefore
253        ** trying to cut an existing group: not allowed. */
254        return(NULL);
255    }
256
257    /* First holds the pointer to the first child contained in the new
258    ** group. Here low <= first->low and low + size >= first->low +
259    ** first->size.  One of the two inequalities is strict. */
260    last = first->younger;
261    while (last != NULL &&
262           (unsigned int) (last->low + last->size) < low + size) {
263        last = last->younger;
264    }
265    if (last == NULL) {
266        /* All the chilren of root from first onward become children
267        ** of the new group. */
268        newn = Mtr_AllocNode();
269        if (newn == NULL) return(NULL); /* out of memory */
270        newn->low = low;
271        newn->size = size;
272        newn->flags = flags;
273        newn->child = first;
274        newn->parent = root;
275        newn->elder = previous;
276        newn->younger = NULL;
277        first->elder = NULL;
278        if (previous != NULL) {
279            previous->younger = newn;
280        } else {
281            root->child = newn;
282        }
283        last = first;
284        while (last != NULL) {
285            last->parent = newn;
286            last = last->younger;
287        }
288        return(newn);
289    }
290
291    /* Here last != NULL and low + size <= last->low + last->size. */
292    if (low + size - 1 >= (unsigned int) last->low &&
293        low + size < (unsigned int) (last->low + last->size)) {
294        /* Trying to cut an existing group: not allowed. */
295        return(NULL);
296    }
297
298    /* First and last point to the first and last of the children of
299    ** root that are included in the new group. Allocate a new node
300    ** and make all children of root between first and last chidren of
301    ** the new node.  Previous points to the child of root immediately
302    ** preceeding first. If it is NULL, then first is the first child
303    ** of root. */
304    newn = Mtr_AllocNode();
305    if (newn == NULL) return(NULL);     /* out of memory */
306    newn->low = low;
307    newn->size = size;
308    newn->flags = flags;
309    newn->child = first;
310    newn->parent = root;
311    if (previous == NULL) {
312        root->child = newn;
313    } else {
314        previous->younger = newn;
315    }
316    newn->elder = previous;
317    newn->younger = last->younger;
318    if (last->younger != NULL) {
319        last->younger->elder = newn;
320    }
321    last->younger = NULL;
322    first->elder = NULL;
323    for (node = first; node != NULL; node = node->younger) {
324        node->parent = newn;
325    }
326
327    return(newn);
328
329} /* end of Mtr_MakeGroup */
330
331
332/**Function********************************************************************
333
334  Synopsis    [Merges the children of `group' with the children of its
335  parent.]
336
337  Description [Merges the children of `group' with the children of its
338  parent. Disposes of the node pointed by group. If group is the
339  root of the group tree, this procedure leaves the tree unchanged.
340  Returns the pointer to the parent of `group' upon successful
341  termination; NULL otherwise.]
342
343  SideEffects [None]
344
345  SeeAlso     [Mtr_MakeGroup]
346
347******************************************************************************/
348MtrNode *
349Mtr_DissolveGroup(
350  MtrNode * group /* group to be dissolved */)
351{
352    MtrNode *parent;
353    MtrNode *last;
354
355    parent = group->parent;
356
357    if (parent == NULL) return(NULL);
358    if (MTR_TEST(group,MTR_TERMINAL) || group->child == NULL) return(NULL);
359
360    /* Make all children of group children of its parent, and make
361    ** last point to the last child of group. */
362    for (last = group->child; last->younger != NULL; last = last->younger) {
363        last->parent = parent;
364    }
365    last->parent = parent;
366
367    last->younger = group->younger;
368    if (group->younger != NULL) {
369        group->younger->elder = last;
370    }
371
372    group->child->elder = group->elder;
373    if (group == parent->child) {
374        parent->child = group->child;
375    } else {
376        group->elder->younger = group->child;
377    }
378
379    Mtr_DeallocNode(group);
380    return(parent);
381
382} /* end of Mtr_DissolveGroup */
383
384
385/**Function********************************************************************
386
387  Synopsis [Finds a group with size leaves starting at low, if it exists.]
388
389  Description [Finds a group with size leaves starting at low, if it
390  exists.  This procedure relies on the low and size fields of each
391  node. It also assumes that the children of each node are sorted in
392  order of increasing low.  Returns the pointer to the root of the
393  group upon successful termination; NULL otherwise.]
394
395  SideEffects [None]
396
397  SeeAlso     []
398
399******************************************************************************/
400MtrNode *
401Mtr_FindGroup(
402  MtrNode * root /* root of the group tree */,
403  unsigned int  low /* lower bound of the group */,
404  unsigned int  size /* upper bound of the group */)
405{
406    MtrNode *node;
407
408#ifdef MTR_DEBUG
409    /* We cannot have a non-empty proper subgroup of a singleton set. */
410    assert(!MTR_TEST(root,MTR_TERMINAL));
411#endif
412
413    /* Sanity check. */
414    if (size < 1) return(NULL);
415
416    /* Check whether current group includes the group sought.  This
417    ** check is necessary at the top-level call.  In the subsequent
418    ** calls it is redundant. */
419    if (low < (unsigned int) root->low ||
420        low + size > (unsigned int) (root->low + root->size))
421        return(NULL);
422
423    if (root->size == size && root->low == low)
424        return(root);
425
426    if (root->child == NULL)
427        return(NULL);
428
429    /* Find all chidren of root that are included in the new group. If
430    ** the group of any child entirely contains the new group, call
431    ** Mtr_MakeGroup recursively.  */
432    node = root->child;
433    while (low >= (unsigned int) (node->low + node->size)) {
434        node = node->younger;
435    }
436    if (low + size <= (unsigned int) (node->low + node->size)) {
437        /* The group is contained in the group of node. */
438        node = Mtr_FindGroup(node, low, size);
439        return(node);
440    } else {
441        return(NULL);
442    }
443
444} /* end of Mtr_FindGroup */
445
446
447/**Function********************************************************************
448
449  Synopsis    [Swaps two children of a tree node.]
450
451  Description [Swaps two children of a tree node. Adjusts the high and
452  low fields of the two nodes and their descendants.  The two children
453  must be adjacent. However, first may be the younger sibling of second.
454  Returns 1 in case of success; 0 otherwise.]
455
456  SideEffects [None]
457
458  SeeAlso     []
459
460******************************************************************************/
461int
462Mtr_SwapGroups(
463  MtrNode * first /* first node to be swapped */,
464  MtrNode * second /* second node to be swapped */)
465{
466    MtrNode *node;
467    MtrNode *parent;
468    int sizeFirst;
469    int sizeSecond;
470
471    if (second->younger == first) { /* make first first */
472        node = first;
473        first = second;
474        second = node;
475    } else if (first->younger != second) { /* non-adjacent */
476        return(0);
477    }
478
479    sizeFirst = first->size;
480    sizeSecond = second->size;
481
482    /* Swap the two nodes. */
483    parent = first->parent;
484    if (parent == NULL || second->parent != parent) return(0);
485    if (parent->child == first) {
486        parent->child = second;
487    } else { /* first->elder != NULL */
488        first->elder->younger = second;
489    }
490    if (second->younger != NULL) {
491        second->younger->elder = first;
492    }
493    first->younger = second->younger;
494    second->elder = first->elder;
495    first->elder = second;
496    second->younger = first;
497
498    /* Adjust the high and low fields. */
499    if (!mtrShiftHL(first,sizeSecond)) return(0);
500    if (!mtrShiftHL(second,-sizeFirst)) return(0);
501
502    return(1);
503
504} /* end of Mtr_SwapGroups */
505
506
507/**Function********************************************************************
508
509  Synopsis    [Fix variable tree at the end of tree sifting.]
510
511  Description [Fix the levels in the variable tree sorting siblings
512  according to them.  It should be called on a non-NULL tree.  It then
513  maintains this invariant.  It applies insertion sorting to the list of
514  siblings  The order is determined by permutation, which is used to find
515  the new level of the node index.  Index must refer to the first variable
516  in the group.]
517
518  SideEffects [The tree is modified.]
519
520  SeeAlso     []
521
522******************************************************************************/
523void
524Mtr_ReorderGroups(
525  MtrNode *treenode,
526  int *permutation)
527{
528    MtrNode *auxnode;
529    /* Initialize sorted list to first element. */
530    MtrNode *sorted = treenode;
531    sorted->low = permutation[sorted->index];
532    if (sorted->child != NULL)
533      Mtr_ReorderGroups(sorted->child, permutation);
534
535    auxnode = treenode->younger;
536    while (auxnode != NULL) {
537        MtrNode *rightplace;
538        MtrNode *moving = auxnode;
539        auxnode->low = permutation[auxnode->index];
540        if (auxnode->child != NULL)
541          Mtr_ReorderGroups(auxnode->child, permutation);
542        rightplace = auxnode->elder;
543        /* Find insertion point. */
544        while (rightplace != NULL && auxnode->low < rightplace->low)
545            rightplace = rightplace->elder;
546        auxnode = auxnode->younger;
547        if (auxnode != NULL) {
548            auxnode->elder = moving->elder;
549            auxnode->elder->younger = auxnode;
550        } else {
551            moving->elder->younger = NULL;
552        }
553        if (rightplace == NULL) { /* Move to head of sorted list. */
554            sorted->elder = moving;
555            moving->elder = NULL;
556            moving->younger = sorted;
557            sorted = moving;
558        } else { /* Splice. */
559            moving->elder = rightplace;
560            moving->younger = rightplace->younger;
561            if (rightplace->younger != NULL)
562                rightplace->younger->elder = moving;
563            rightplace->younger = moving;
564        }
565    }
566    /* Fix parent. */
567    if (sorted->parent != NULL)
568        sorted->parent->child = sorted;
569
570} /* end of Mtr_ReorderGroups */
571
572
573/**Function********************************************************************
574
575  Synopsis    [Prints the groups as a parenthesized list.]
576
577  Description [Prints the groups as a parenthesized list. After each
578  group, the group's flag are printed, preceded by a `|'.  For each
579  flag (except MTR_TERMINAL) a character is printed.
580  <ul>
581  <li>F: MTR_FIXED
582  <li>N: MTR_NEWNODE
583  <li>S: MTR_SOFT
584  </ul>
585  The second argument, silent, if different from 0, causes
586  Mtr_PrintGroups to only check the syntax of the group tree.
587  ]
588
589  SideEffects [None]
590
591  SeeAlso     [Mtr_PrintTree]
592
593******************************************************************************/
594void
595Mtr_PrintGroups(
596  MtrNode * root /* root of the group tree */,
597  int  silent /* flag to check tree syntax only */)
598{
599    MtrNode *node;
600
601    assert(root != NULL);
602    assert(root->younger == NULL || root->younger->elder == root);
603    assert(root->elder == NULL || root->elder->younger == root);
604#if SIZEOF_VOID_P == 8
605    if (!silent) (void) printf("(%u",root->low);
606#else
607    if (!silent) (void) printf("(%hu",root->low);
608#endif
609    if (MTR_TEST(root,MTR_TERMINAL) || root->child == NULL) {
610        if (!silent) (void) printf(",");
611    } else {
612        node = root->child;
613        while (node != NULL) {
614            assert(node->low >= root->low && (int) (node->low + node->size) <= (int) (root->low + root->size));
615            assert(node->parent == root);
616            Mtr_PrintGroups(node,silent);
617            node = node->younger;
618        }
619    }
620    if (!silent) {
621#if SIZEOF_VOID_P == 8
622        (void) printf("%u", (MtrHalfWord) (root->low + root->size - 1));
623#else
624        (void) printf("%hu", (MtrHalfWord) (root->low + root->size - 1));
625#endif
626        if (root->flags != MTR_DEFAULT) {
627            (void) printf("|");
628            if (MTR_TEST(root,MTR_FIXED)) (void) printf("F");
629            if (MTR_TEST(root,MTR_NEWNODE)) (void) printf("N");
630            if (MTR_TEST(root,MTR_SOFT)) (void) printf("S");
631        }
632        (void) printf(")");
633        if (root->parent == NULL) (void) printf("\n");
634    }
635    assert((root->flags &~(MTR_TERMINAL | MTR_SOFT | MTR_FIXED | MTR_NEWNODE)) == 0);
636    return;
637
638} /* end of Mtr_PrintGroups */
639
640
641/**Function********************************************************************
642
643  Synopsis    [Prints the variable order  as a parenthesized list.]
644
645  Description [Prints the variable order as a parenthesized list. After each
646  group, the group's flag are printed, preceded by a `|'.  For each
647  flag (except MTR_TERMINAL) a character is printed.
648  <ul>
649  <li>F: MTR_FIXED
650  <li>N: MTR_NEWNODE
651  <li>S: MTR_SOFT
652  </ul>
653  The second argument, gives the map from levels to variable indices.
654  ]
655
656  SideEffects [None]
657
658  SeeAlso     [Mtr_PrintGroups]
659
660******************************************************************************/
661int
662Mtr_PrintGroupedOrder(
663  MtrNode * root /* root of the group tree */,
664  int *invperm /* map from levels to indices */,
665  FILE *fp /* output file */)
666{
667    MtrNode *child;
668    MtrHalfWord level;
669    int retval;
670
671    assert(root != NULL);
672    assert(root->younger == NULL || root->younger->elder == root);
673    assert(root->elder == NULL || root->elder->younger == root);
674    retval = fprintf(fp,"(");
675    if (retval == EOF) return(0);
676    level = root->low;
677    child = root->child;
678    while (child != NULL) {
679        assert(child->low >= root->low && (child->low + child->size) <= (root->low + root->size));
680        assert(child->parent == root);
681        while (level < child->low) {
682            retval = fprintf(fp,"%d%s", invperm[level], (level < root->low + root->size - 1) ? "," : "");
683            if (retval == EOF) return(0);
684            level++;
685        }
686        retval = Mtr_PrintGroupedOrder(child,invperm,fp);
687        if (retval == 0) return(0);
688        level += child->size;
689        if (level < root->low + root->size - 1) {
690            retval = fprintf(fp,",");
691            if (retval == EOF) return(0);
692        }
693        child = child->younger;
694    }
695    while (level < root->low + root->size) {
696        retval = fprintf(fp,"%d%s", invperm[level], (level < root->low + root->size - 1) ? "," : "");
697        if (retval == EOF) return(0);
698        level++;
699    }
700    if (root->flags != MTR_DEFAULT) {
701      retval = fprintf(fp,"|");
702      if (retval == EOF) return(0);
703      if (MTR_TEST(root,MTR_FIXED)) {
704          retval = fprintf(fp,"F");
705          if (retval == EOF) return(0);
706      }
707      if (MTR_TEST(root,MTR_NEWNODE)) {
708          retval = fprintf(fp,"N");
709          if (retval == EOF) return(0);
710      }
711      if (MTR_TEST(root,MTR_SOFT)) {
712          retval = fprintf(fp,"S");
713          if (retval == EOF) return(0);
714      }
715    }
716    retval = fprintf(fp,")");
717    if (retval == EOF) return(0);
718    if (root->parent == NULL) {
719        retval = fprintf(fp,"\n");
720        if (retval == EOF) return(0);
721    }
722    assert((root->flags &~(MTR_SOFT | MTR_FIXED | MTR_NEWNODE)) == 0);
723    return(1);
724
725} /* end of Mtr_PrintGroupedOrder */
726
727
728/**Function********************************************************************
729
730  Synopsis    [Reads groups from a file and creates a group tree.]
731
732  Description [Reads groups from a file and creates a group tree.
733  Each group is specified by three fields:
734  <xmp>
735       low size flags.
736  </xmp>
737  Low and size are (short) integers. Flags is a string composed of the
738  following characters (with associated translation):
739  <ul>
740  <li>D: MTR_DEFAULT
741  <li>F: MTR_FIXED
742  <li>N: MTR_NEWNODE
743  <li>S: MTR_SOFT
744  <li>T: MTR_TERMINAL
745  </ul>
746  Normally, the only flags that are needed are D and F.  Groups and
747  fields are separated by white space (spaces, tabs, and newlines).
748  Returns a pointer to the group tree if successful; NULL otherwise.]
749
750  SideEffects [None]
751
752  SeeAlso     [Mtr_InitGroupTree Mtr_MakeGroup]
753
754******************************************************************************/
755MtrNode *
756Mtr_ReadGroups(
757  FILE * fp /* file pointer */,
758  int  nleaves /* number of leaves of the new tree */)
759{
760    int low;
761    int size;
762    int err;
763    unsigned int flags;
764    MtrNode *root;
765    MtrNode *node;
766    char attrib[8*sizeof(unsigned int)+1];
767    char *c;
768
769    root = Mtr_InitGroupTree(0,nleaves);
770    if (root == NULL) return NULL;
771
772    while (! feof(fp)) {
773        /* Read a triple and check for consistency. */
774        err = fscanf(fp, "%d %d %s", &low, &size, attrib);
775        if (err == EOF) {
776            break;
777        } else if (err != 3) {
778            Mtr_FreeTree(root);
779            return(NULL);
780        } else if (low < 0 || low+size > nleaves || size < 1) {
781            Mtr_FreeTree(root);
782            return(NULL);
783        } else if (strlen(attrib) > 8 * sizeof(MtrHalfWord)) {
784            /* Not enough bits in the flags word to store these many
785            ** attributes. */
786            Mtr_FreeTree(root);
787            return(NULL);
788        }
789
790        /* Parse the flag string. Currently all flags are permitted,
791        ** to make debugging easier. Normally, specifying NEWNODE
792        ** wouldn't be allowed. */
793        flags = MTR_DEFAULT;
794        for (c=attrib; *c != 0; c++) {
795            switch (*c) {
796            case 'D':
797                break;
798            case 'F':
799                flags |= MTR_FIXED;
800                break;
801            case 'N':
802                flags |= MTR_NEWNODE;
803                break;
804            case 'S':
805                flags |= MTR_SOFT;
806                break;
807            case 'T':
808                flags |= MTR_TERMINAL;
809                break;
810            default:
811                return NULL;
812            }
813        }
814        node = Mtr_MakeGroup(root, (MtrHalfWord) low, (MtrHalfWord) size,
815                             flags);
816        if (node == NULL) {
817            Mtr_FreeTree(root);
818            return(NULL);
819        }
820    }
821
822    return(root);
823
824} /* end of Mtr_ReadGroups */
825
826
827/*---------------------------------------------------------------------------*/
828/* Definition of internal functions                                          */
829/*---------------------------------------------------------------------------*/
830
831/*---------------------------------------------------------------------------*/
832/* Definition of static functions                                            */
833/*---------------------------------------------------------------------------*/
834
835
836/**Function********************************************************************
837
838  Synopsis    [Adjusts the low fields of a node and its descendants.]
839
840  Description [Adjusts the low fields of a node and its
841  descendants. Adds shift to low of each node. Checks that no
842  out-of-bounds values result.  Returns 1 in case of success; 0
843  otherwise.]
844
845  SideEffects [None]
846
847  SeeAlso     []
848
849******************************************************************************/
850static int
851mtrShiftHL(
852  MtrNode * node /* group tree node */,
853  int  shift /* amount by which low should be changed */)
854{
855    MtrNode *auxnode;
856    int low;
857
858    low = (int) node->low;
859
860
861    low += shift;
862
863    if (low < 0 || low + (int) (node->size - 1) > (int) MTR_MAXHIGH) return(0);
864
865    node->low = (MtrHalfWord) low;
866
867    if (!MTR_TEST(node,MTR_TERMINAL) && node->child != NULL) {
868        auxnode = node->child;
869        do {
870            if (!mtrShiftHL(auxnode,shift)) return(0);
871            auxnode = auxnode->younger;
872        } while (auxnode != NULL);
873    }
874
875    return(1);
876
877} /* end of mtrShiftHL */
Note: See TracBrowser for help on using the repository browser.