source: vis_dev/glu-2.3/src/mtr/mtrBasic.c @ 91

Last change on this file since 91 was 13, checked in by cecile, 13 years ago

library glu 2.3
File size: 12.6 KB
RevLine 
[13]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
84static 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******************************************************************************/
116MtrNode *
117Mtr_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******************************************************************************/
138void
139Mtr_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******************************************************************************/
159MtrNode *
160Mtr_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******************************************************************************/
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 = 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******************************************************************************/
364MtrNode *
365Mtr_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******************************************************************************/
393void
394Mtr_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******************************************************************************/
421void
422Mtr_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/*---------------------------------------------------------------------------*/
Note: See TracBrowser for help on using the repository browser.