source: icGREP/icgrep-devel/cudd-2.5.1/mtr/mtrBasic.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: 12.6 KB
Line 
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-2012, 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
84static char rcsid[] MTR_UNUSED = "$Id: mtrBasic.c,v 1.16 2014/08/21 01:17:31 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******************************************************************************/
116MtrNode *
117Mtr_AllocNode(void)
118{
119    MtrNode *node;
120
121    node = ALLOC(MtrNode,1);
122    node->flags = node->low = node->size = node->index = 0;
123    return node;
124
125} /* Mtr_AllocNode */
126
127
128/**Function********************************************************************
129
130  Synopsis    [Deallocates tree node.]
131
132  Description []
133
134  SideEffects [None]
135
136  SeeAlso     [Mtr_AllocNode]
137
138******************************************************************************/
139void
140Mtr_DeallocNode(
141  MtrNode * node /* node to be deallocated */)
142{
143    FREE(node);
144    return;
145
146} /* end of Mtr_DeallocNode */
147
148
149/**Function********************************************************************
150
151  Synopsis    [Initializes tree with one node.]
152
153  Description [Initializes tree with one node. Returns pointer to node.]
154
155  SideEffects [None]
156
157  SeeAlso     [Mtr_FreeTree Mtr_InitGroupTree]
158
159******************************************************************************/
160MtrNode *
161Mtr_InitTree(void)
162{
163    MtrNode *node;
164
165    node = Mtr_AllocNode();
166    if (node == NULL) return(NULL);
167
168    node->parent = node->child = node->elder = node->younger = NULL;
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******************************************************************************/
186void
187Mtr_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******************************************************************************/
213MtrNode *
214Mtr_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******************************************************************************/
267void
268Mtr_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******************************************************************************/
298void
299Mtr_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******************************************************************************/
335MtrNode *
336Mtr_CreateFirstChild(
337  MtrNode * parent)
338{
339    MtrNode *child;
340
341    child = Mtr_AllocNode();
342    if (child == NULL) return(NULL);
343
344    child->child = NULL;
345    Mtr_MakeFirstChild(parent,child);
346    return(child);
347
348} /* end of Mtr_CreateFirstChild */
349
350
351/**Function********************************************************************
352
353  Synopsis    [Creates a new node and makes it the last child of parent.]
354
355  Description [Creates a new node and makes it the last child of parent.
356  Returns pointer to new child.]
357
358  SideEffects [None]
359
360  SeeAlso     [Mtr_MakeLastChild Mtr_CreateFirstChild]
361
362******************************************************************************/
363MtrNode *
364Mtr_CreateLastChild(
365  MtrNode * parent)
366{
367    MtrNode *child;
368
369    child = Mtr_AllocNode();
370    if (child == NULL) return(NULL);
371
372    child->child = NULL;
373    Mtr_MakeLastChild(parent,child);
374    return(child);
375
376} /* end of Mtr_CreateLastChild */
377
378
379/**Function********************************************************************
380
381  Synopsis    [Makes second the next sibling of first.]
382
383  Description [Makes second the next sibling of first. Second becomes a
384  child of the parent of first.]
385
386  SideEffects [None]
387
388  SeeAlso     []
389
390******************************************************************************/
391void
392Mtr_MakeNextSibling(
393  MtrNode * first,
394  MtrNode * second)
395{
396    second->parent = first->parent;
397    second->elder = first;
398    second->younger = first->younger;
399    if (first->younger != NULL) {
400        first->younger->elder = second;
401    }
402    first->younger = second;
403    return;
404
405} /* end of Mtr_MakeNextSibling */
406
407
408/**Function********************************************************************
409
410  Synopsis    [Prints a tree, one node per line.]
411
412  Description []
413
414  SideEffects [None]
415
416  SeeAlso     [Mtr_PrintGroups]
417
418******************************************************************************/
419void
420Mtr_PrintTree(
421  MtrNode * node)
422{
423    if (node == NULL) return;
424    (void) fprintf(stdout,
425#if SIZEOF_VOID_P == 8
426    "N=0x%-8lx C=0x%-8lx Y=0x%-8lx E=0x%-8lx P=0x%-8lx F=%x L=%u S=%u\n",
427    (unsigned long) node, (unsigned long) node->child,
428    (unsigned long) node->younger, (unsigned long) node->elder,
429    (unsigned long) node->parent, node->flags, node->low, node->size);
430#else
431    "N=0x%-8x C=0x%-8x Y=0x%-8x E=0x%-8x P=0x%-8x F=%x L=%hu S=%hu\n",
432    (unsigned) node, (unsigned) node->child,
433    (unsigned) node->younger, (unsigned) node->elder,
434    (unsigned) node->parent, node->flags, node->low, node->size);
435#endif
436    if (!MTR_TEST(node,MTR_TERMINAL)) Mtr_PrintTree(node->child);
437    Mtr_PrintTree(node->younger);
438    return;
439
440} /* end of Mtr_PrintTree */
441
442/*---------------------------------------------------------------------------*/
443/* Definition of internal functions                                          */
444/*---------------------------------------------------------------------------*/
445
446/*---------------------------------------------------------------------------*/
447/* Definition of static functions                                            */
448/*---------------------------------------------------------------------------*/
Note: See TracBrowser for help on using the repository browser.