distr/mtr/mtrGroup.c

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