Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log

mtrGroup.c @ 84

Last change on this file since 84 was 13, checked in by cecile, 13 years ago
library glu 2.3
File size: 22.1 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_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 */

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: vis_dev/glu-2.3/src/mtr/mtrGroup.c @ 84

Download in other formats: