distr/mtr/mtrBasic.c

   1 /**CFile***********************************************************************
   2
   3   FileName    [mtrBasic.c]
   4
   5   PackageName [mtr]
   6
   7   Synopsis    [Basic manipulation of multiway branching trees.]
   8
   9   Description [External procedures included in this module:
  10             <ul>
  11             <li> Mtr_AllocNode()
  12             <li> Mtr_DeallocNode()
  13             <li> Mtr_InitTree()
  14             <li> Mtr_FreeTree()
  15             <li> Mtr_CopyTree()
  16             <li> Mtr_MakeFirstChild()
  17             <li> Mtr_MakeLastChild()
  18             <li> Mtr_CreateFirstChild()
  19             <li> Mtr_CreateLastChild()
  20             <li> Mtr_MakeNextSibling()
  21             <li> Mtr_PrintTree()
  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 /*---------------------------------------------------------------------------*/
  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
  84 static char rcsid[] MTR_UNUSED = "$Id: mtrBasic.c,v 1.13 2009/02/20 02:03:47 fabio Exp $";
  85 #endif
  86
  87 /*---------------------------------------------------------------------------*/
  88 /* Macro declarations                                                        */
  89 /*---------------------------------------------------------------------------*/
  90
  91 /**AutomaticStart*************************************************************/
  92
  93 /*---------------------------------------------------------------------------*/
  94 /* Static function prototypes                                                */
  95 /*---------------------------------------------------------------------------*/
  96
  97
  98 /**AutomaticEnd***************************************************************/
  99
 100
 101 /*---------------------------------------------------------------------------*/
 102 /* Definition of exported functions                                          */
 103 /*---------------------------------------------------------------------------*/
 104
 105 /**Function********************************************************************
 106
 107   Synopsis    [Allocates new tree node.]
 108
 109   Description [Allocates new tree node. Returns pointer to node.]
 110
 111   SideEffects [None]
 112
 113   SeeAlso     [Mtr_DeallocNode]
 114
 115 ******************************************************************************/
 116 MtrNode *
 117 Mtr_AllocNode(void)
 118 {
 119     MtrNode *node;
 120
 121     node = ALLOC(MtrNode,1);
 122     return node;
 123
 124 } /* Mtr_AllocNode */
 125
 126
 127 /**Function********************************************************************
 128
 129   Synopsis    [Deallocates tree node.]
 130
 131   Description []
 132
 133   SideEffects [None]
 134
 135   SeeAlso     [Mtr_AllocNode]
 136
 137 ******************************************************************************/
 138 void
 139 Mtr_DeallocNode(
 140   MtrNode * node /* node to be deallocated */)
 141 {
 142     FREE(node);
 143     return;
 144
 145 } /* end of Mtr_DeallocNode */
 146
 147
 148 /**Function********************************************************************
 149
 150   Synopsis    [Initializes tree with one node.]
 151
 152   Description [Initializes tree with one node. Returns pointer to node.]
 153
 154   SideEffects [None]
 155
 156   SeeAlso     [Mtr_FreeTree Mtr_InitGroupTree]
 157
 158 ******************************************************************************/
 159 MtrNode *
 160 Mtr_InitTree(void)
 161 {
 162     MtrNode *node;
 163
 164     node = Mtr_AllocNode();
 165     if (node == NULL) return(NULL);
 166
 167     node->parent = node->child = node->elder = node->younger = NULL;
 168     node->flags = 0;
 169
 170     return(node);
 171
 172 } /* end of Mtr_InitTree */
 173
 174
 175 /**Function********************************************************************
 176
 177   Synopsis    [Disposes of tree rooted at node.]
 178
 179   Description []
 180
 181   SideEffects [None]
 182
 183   SeeAlso     [Mtr_InitTree]
 184
 185 ******************************************************************************/
 186 void
 187 Mtr_FreeTree(
 188   MtrNode * node)
 189 {
 190     if (node == NULL) return;
 191     if (! MTR_TEST(node,MTR_TERMINAL)) Mtr_FreeTree(node->child);
 192     Mtr_FreeTree(node->younger);
 193     Mtr_DeallocNode(node);
 194     return;
 195
 196 } /* end of Mtr_FreeTree */
 197
 198
 199 /**Function********************************************************************
 200
 201   Synopsis    [Makes a copy of tree.]
 202
 203   Description [Makes a copy of tree. If parameter expansion is greater
 204   than 1, it will expand the tree by that factor. It is an error for
 205   expansion to be less than 1. Returns a pointer to the copy if
 206   successful; NULL otherwise.]
 207
 208   SideEffects [None]
 209
 210   SeeAlso     [Mtr_InitTree]
 211
 212 ******************************************************************************/
 213 MtrNode *
 214 Mtr_CopyTree(
 215   MtrNode * node,
 216   int  expansion)
 217 {
 218     MtrNode *copy;
 219
 220     if (node == NULL) return(NULL);
 221     if (expansion < 1) return(NULL);
 222     copy = Mtr_AllocNode();
 223     if (copy == NULL) return(NULL);
 224     copy->parent = copy->elder = copy->child = copy->younger = NULL;
 225     if (node->child != NULL) {
 226         copy->child = Mtr_CopyTree(node->child, expansion);
 227         if (copy->child == NULL) {
 228             Mtr_DeallocNode(copy);
 229             return(NULL);
 230         }
 231     }
 232     if (node->younger != NULL) {
 233         copy->younger = Mtr_CopyTree(node->younger, expansion);
 234         if (copy->younger == NULL) {
 235             Mtr_FreeTree(copy);
 236             return(NULL);
 237         }
 238     }
 239     copy->flags = node->flags;
 240     copy->low = node->low * expansion;
 241     copy->size = node->size * expansion;
 242     copy->index = node->index * expansion;
 243     if (copy->younger) copy->younger->elder = copy;
 244     if (copy->child) {
 245         MtrNode *auxnode = copy->child;
 246         while (auxnode != NULL) {
 247             auxnode->parent = copy;
 248             auxnode = auxnode->younger;
 249         }
 250     }
 251     return(copy);
 252
 253 } /* end of Mtr_CopyTree */
 254
 255
 256 /**Function********************************************************************
 257
 258   Synopsis    [Makes child the first child of parent.]
 259
 260   Description []
 261
 262   SideEffects [None]
 263
 264   SeeAlso     [Mtr_MakeLastChild Mtr_CreateFirstChild]
 265
 266 ******************************************************************************/
 267 void
 268 Mtr_MakeFirstChild(
 269   MtrNode * parent,
 270   MtrNode * child)
 271 {
 272     child->parent = parent;
 273     child->younger = parent->child;
 274     child->elder = NULL;
 275     if (parent->child != NULL) {
 276 #ifdef MTR_DEBUG
 277         assert(parent->child->elder == NULL);
 278 #endif
 279         parent->child->elder = child;
 280     }
 281     parent->child = child;
 282     return;
 283
 284 } /* end of Mtr_MakeFirstChild */
 285
 286
 287 /**Function********************************************************************
 288
 289   Synopsis    [Makes child the last child of parent.]
 290
 291   Description []
 292
 293   SideEffects [None]
 294
 295   SeeAlso     [Mtr_MakeFirstChild Mtr_CreateLastChild]
 296
 297 ******************************************************************************/
 298 void
 299 Mtr_MakeLastChild(
 300   MtrNode * parent,
 301   MtrNode * child)
 302 {
 303     MtrNode *node;
 304
 305     child->younger = NULL;
 306
 307     if (parent->child == NULL) {
 308         parent->child = child;
 309         child->elder = NULL;
 310     } else {
 311         for (node = parent->child;
 312              node->younger != NULL;
 313              node = node->younger);
 314         node->younger = child;
 315         child->elder = node;
 316     }
 317     child->parent = parent;
 318     return;
 319
 320 } /* end of Mtr_MakeLastChild */
 321
 322
 323 /**Function********************************************************************
 324
 325   Synopsis    [Creates a new node and makes it the first child of parent.]
 326
 327   Description [Creates a new node and makes it the first child of
 328   parent. Returns pointer to new child.]
 329
 330   SideEffects [None]
 331
 332   SeeAlso     [Mtr_MakeFirstChild Mtr_CreateLastChild]
 333
 334 ******************************************************************************/
 335 MtrNode *
 336 Mtr_CreateFirstChild(
 337   MtrNode * parent)
 338 {
 339     MtrNode *child;
 340
 341     child = Mtr_AllocNode();
 342     if (child == NULL) return(NULL);
 343
 344     child->child = child->younger = child-> elder = NULL;
 345     child->flags = 0;
 346     Mtr_MakeFirstChild(parent,child);
 347     return(child);
 348
 349 } /* end of Mtr_CreateFirstChild */
 350
 351
 352 /**Function********************************************************************
 353
 354   Synopsis    [Creates a new node and makes it the last child of parent.]
 355
 356   Description [Creates a new node and makes it the last child of parent.
 357   Returns pointer to new child.]
 358
 359   SideEffects [None]
 360
 361   SeeAlso     [Mtr_MakeLastChild Mtr_CreateFirstChild]
 362
 363 ******************************************************************************/
 364 MtrNode *
 365 Mtr_CreateLastChild(
 366   MtrNode * parent)
 367 {
 368     MtrNode *child;
 369
 370     child = Mtr_AllocNode();
 371     if (child == NULL) return(NULL);
 372
 373     child->child = child->younger = child->elder = NULL;
 374     child->flags = 0;
 375     Mtr_MakeLastChild(parent,child);
 376     return(child);
 377
 378 } /* end of Mtr_CreateLastChild */
 379
 380
 381 /**Function********************************************************************
 382
 383   Synopsis    [Makes second the next sibling of first.]
 384
 385   Description [Makes second the next sibling of first. Second becomes a
 386   child of the parent of first.]
 387
 388   SideEffects [None]
 389
 390   SeeAlso     []
 391
 392 ******************************************************************************/
 393 void
 394 Mtr_MakeNextSibling(
 395   MtrNode * first,
 396   MtrNode * second)
 397 {
 398     second->younger = first->younger;
 399     if (first->younger != NULL) {
 400         first->younger->elder = second;
 401     }
 402     second->parent = first->parent;
 403     first->younger = second;
 404     second->elder = first;
 405     return;
 406
 407 } /* end of Mtr_MakeNextSibling */
 408
 409
 410 /**Function********************************************************************
 411
 412   Synopsis    [Prints a tree, one node per line.]
 413
 414   Description []
 415
 416   SideEffects [None]
 417
 418   SeeAlso     [Mtr_PrintGroups]
 419
 420 ******************************************************************************/
 421 void
 422 Mtr_PrintTree(
 423   MtrNode * node)
 424 {
 425     if (node == NULL) return;
 426     (void) fprintf(stdout,
 427 #if SIZEOF_VOID_P == 8
 428     "N=0x%-8lx C=0x%-8lx Y=0x%-8lx E=0x%-8lx P=0x%-8lx F=%x L=%u S=%u\n",
 429     (unsigned long) node, (unsigned long) node->child,
 430     (unsigned long) node->younger, (unsigned long) node->elder,
 431     (unsigned long) node->parent, node->flags, node->low, node->size);
 432 #else
 433     "N=0x%-8x C=0x%-8x Y=0x%-8x E=0x%-8x P=0x%-8x F=%x L=%hu S=%hu\n",
 434     (unsigned) node, (unsigned) node->child,
 435     (unsigned) node->younger, (unsigned) node->elder,
 436     (unsigned) node->parent, node->flags, node->low, node->size);
 437 #endif
 438     if (!MTR_TEST(node,MTR_TERMINAL)) Mtr_PrintTree(node->child);
 439     Mtr_PrintTree(node->younger);
 440     return;
 441
 442 } /* end of Mtr_PrintTree */
 443
 444 /*---------------------------------------------------------------------------*/
 445 /* Definition of internal functions                                          */
 446 /*---------------------------------------------------------------------------*/
 447
 448 /*---------------------------------------------------------------------------*/
 449 /* Definition of static functions                                            */
 450 /*---------------------------------------------------------------------------*/