1 /* Copyright 2010 IPB, INRIA & CNRS
2 **
3 ** This file originally comes from the Scotch software package for
4 ** static mapping, graph partitioning and sparse matrix ordering.
5 **
6 ** This software is governed by the CeCILL-B license under French law
7 ** and abiding by the rules of distribution of free software. You can
8 ** use, modify and/or redistribute the software under the terms of the
9 ** CeCILL-B license as circulated by CEA, CNRS and INRIA at the following
10 ** URL: "http://www.cecill.info".
11 **
12 ** As a counterpart to the access to the source code and rights to copy,
13 ** modify and redistribute granted by the license, users are provided
14 ** only with a limited warranty and the software's author, the holder of
15 ** the economic rights, and the successive licensors have only limited
16 ** liability.
17 **
18 ** In this respect, the user's attention is drawn to the risks associated
19 ** with loading, using, modifying and/or developing or reproducing the
20 ** software by the user in light of its specific status of free software,
21 ** that may mean that it is complicated to manipulate, and that also
22 ** therefore means that it is reserved for developers and experienced
23 ** professionals having in-depth computer knowledge. Users are therefore
24 ** encouraged to load and test the software's suitability as regards
25 ** their requirements in conditions enabling the security of their
26 ** systems and/or data to be ensured and, more generally, to use and
27 ** operate it in the same conditions as regards security.
28 **
29 ** The fact that you are presently reading this means that you have had
30 ** knowledge of the CeCILL-B license and that you accept its terms.
31 */
32 /************************************************************/
33 /** **/
34 /** NAME : fibo.c **/
35 /** **/
36 /** AUTHOR : Francois PELLEGRINI **/
37 /** **/
38 /** FUNCTION : This module handles Fibonacci trees. **/
39 /** **/
40 /** DATES : # Version 1.0 : from : 01 may 2010 **/
41 /** to 12 may 2010 **/
42 /** **/
43 /************************************************************/
44
45 /*
46 ** The defines and includes.
47 */
48
49 #define FIBO
50
51 #include <stdlib.h>
52 #include <memory.h>
53 #include <stdio.h>
54 #include "fibo.h"
55
56 /* Helper macros which can be redefined at compile time. */
57
58 #ifndef INT
59 #define INT int /* "long long" can be used on 64-bit systems */
60 #endif /* INT */
61
62 #ifndef errorPrint
63 #define errorPrint(s) fprintf (stderr, s)
64 #endif /* errorPrint */
65
66 #ifndef memAlloc
67 #define memAlloc malloc
68 #define memSet memset
69 #define memFree free
70 #endif /* memAlloc */
71
72 /*********************************************/
73 /* */
74 /* These routines deal with Fibonacci trees. */
75 /* */
76 /*********************************************/
77
78 /* This routine initializes a Fibonacci
79 ** tree structure.
80 ** It returns:
81 ** - 0 : in case of success.
82 ** - !0 : on error.
83 */
84
85 int
86 fiboTreeInit (
87 FiboTree * const treeptr,
88 int (* cmpfptr) (const FiboNode * const, const FiboNode * const))
89 {
90 if ((treeptr->degrtab = (FiboNode **) memAlloc ((sizeof (INT) << 3) * sizeof (FiboNode *))) == NULL) /* As many cells as there are bits in an INT */
91 return (1);
92
93 memSet (treeptr->degrtab, 0, (sizeof (INT) << 3) * sizeof (FiboNode *)); /* Make degree array ready for consolidation: all cells set to NULL */
94
95 treeptr->rootdat.linkdat.prevptr = /* Link root node to itself */
96 treeptr->rootdat.linkdat.nextptr = &treeptr->rootdat;
97 treeptr->cmpfptr = cmpfptr;
98
99 return (0);
100 }
101
102 /* This routine flushes the contents of
103 ** the given Fibonacci tree.
104 ** It returns:
105 ** - VOID : in all cases.
106 */
107
108 void
109 fiboTreeExit (
110 FiboTree * const treeptr)
111 {
112 if (treeptr->degrtab != NULL)
113 memFree (treeptr->degrtab);
114 }
115
116 /* This routine flushes the contents of
117 ** the given Fibonacci tree. It does not
118 ** free any of its contents, but instead
119 ** makes the tree structure look empty again.
120 ** It returns:
121 ** - VOID : in all cases.
122 */
123
124 void
125 fiboTreeFree (
126 FiboTree * const treeptr)
127 {
128 treeptr->rootdat.linkdat.prevptr = /* Link root node to itself */
129 treeptr->rootdat.linkdat.nextptr = &treeptr->rootdat;
130 }
131
132 /* This routine perform the consolidation
133 ** of roots per degree. It returns the best
134 ** element found because this element is not
135 ** recorded in the data structure itself.
136 ** It returns:
137 ** - !NULL : pointer to best element found.
138 ** - NULL : Fibonacci tree is empty.
139 */
140
141 FiboNode *
142 fiboTreeConsolidate (
143 FiboTree * const treeptr)
144 {
145 FiboNode ** restrict degrtab;
146 int degrmax;
147 int degrval;
148 FiboNode * rootptr;
149 FiboNode * nextptr;
150 FiboNode * bestptr;
151
152 degrtab = treeptr->degrtab;
153
154 for (rootptr = treeptr->rootdat.linkdat.nextptr, nextptr = rootptr->linkdat.nextptr, degrmax = 0; /* For all roots in root list */
155 rootptr != &treeptr->rootdat; ) {
156 degrval = rootptr->deflval >> 1; /* Get degree, getting rid of flag part */
157 #ifdef FIBO_DEBUG
158 if (degrval >= (sizeof (INT) << 3))
159 errorPrint ("fiboTreeConsolidate: invalid node degree");
160 #endif /* FIBO_DEBUG */
161 if (degrtab[degrval] == NULL) { /* If no tree with same degree already found */
162 if (degrval > degrmax) /* Record highest degree found */
163 degrmax = degrval;
164
165 degrtab[degrval] = rootptr; /* Record tree as first tree with this degree */
166 rootptr = nextptr; /* Process next root in list during next iteration */
167 nextptr = rootptr->linkdat.nextptr;
168 }
169 else {
170 FiboNode * oldrptr; /* Root which will no longer be a root */
171 FiboNode * chldptr;
172
173 oldrptr = degrtab[degrval]; /* Assume old root is worse */
174 if (treeptr->cmpfptr (oldrptr, rootptr) <= 0) { /* If old root is still better */
175 oldrptr = rootptr; /* This root will be be linked to it */
176 rootptr = degrtab[degrval]; /* We will go on processing this root */
177 }
178
179 degrtab[degrval] = NULL; /* Remaining root changes degree so leaves this cell */
180 fiboTreeUnlink (oldrptr); /* Old root is no longer a root */
181 oldrptr->deflval &= ~1; /* Whatever old root flag was, it is reset to 0 */
182 oldrptr->pareptr = rootptr; /* Remaining root is now father of old root */
183
184 chldptr = rootptr->chldptr; /* Get first child of remaining root */
185 if (chldptr != NULL) { /* If remaining root had already some children, link old root with them */
186 rootptr->deflval += 2; /* Increase degree by 1, that is, by 2 with left shift in deflval */
187 fiboTreeLinkAfter (chldptr, oldrptr);
188 }
189 else { /* Old root becomes first child of remaining root */
190 rootptr->deflval = 2; /* Real degree set to 1, and flag set to 0 */
191 rootptr->chldptr = oldrptr;
192 oldrptr->linkdat.prevptr = /* Chain old root to oneself as only child */
193 oldrptr->linkdat.nextptr = oldrptr;
194 }
195 } /* Process again remaining root as its degree has changed */
196 }
197
198 bestptr = NULL;
199 for (degrval = 0; degrval <= degrmax; degrval ++) {
200 if (degrtab[degrval] != NULL) { /* If some tree is found */
201 bestptr = degrtab[degrval]; /* Record it as potential best */
202 degrtab[degrval] = NULL; /* Clean-up used part of array */
203 degrval ++; /* Go on at next cell in next loop */
204 break;
205 }
206 }
207 for ( ; degrval <= degrmax; degrval ++) { /* For remaining roots once a potential best root has been found */
208 if (degrtab[degrval] != NULL) {
209 if (treeptr->cmpfptr (degrtab[degrval], bestptr) < 0) /* If new root is better */
210 bestptr = degrtab[degrval]; /* Record new root as best root */
211 degrtab[degrval] = NULL; /* Clean-up used part of array */
212 }
213 }
214
215 return (bestptr);
216 }
217
218 /* This routine returns the node of minimum
219 ** key in the given tree. The node is searched
220 ** for each time this routine is called, so this
221 ** information should be recorded if needed.
222 ** This is the non-macro version, for testing
223 ** and setting up breakpoints.
224 ** It returns:
225 ** - !NULL : pointer to best element found.
226 ** - NULL : Fibonacci tree is empty.
227 */
228
229 #ifndef fiboTreeMin
230
231 FiboNode *
232 fiboTreeMin (
233 FiboTree * const treeptr)
234 {
235 FiboNode * bestptr;
236
237 bestptr = fiboTreeMinMacro (treeptr);
238
239 #ifdef FIBO_DEBUG
240 fiboTreeCheck (treeptr);
241 #endif /* FIBO_DEBUG */
242
243 return (bestptr);
244 }
245
246 #endif /* fiboTreeMin */
247
248 /* This routine adds the given node to the
249 ** given tree. This is the non-macro version,
250 ** for testing and setting up breakpoints.
251 ** It returns:
252 ** - void : in all cases.
253 */
254
255 #ifndef fiboTreeAdd
256
257 void
258 fiboTreeAdd (
259 FiboTree * const treeptr,
260 FiboNode * const nodeptr)
261 {
262 fiboTreeAddMacro (treeptr, nodeptr);
263
264 #ifdef FIBO_DEBUG
265 fiboTreeCheck (treeptr);
266 #endif /* FIBO_DEBUG */
267 }
268
269 #endif /* fiboTreeAdd */
270
271 /* This routine deletes the given node from
272 ** the given tree, whatever ths node is (root
273 ** or non root). This is the non-macro version,
274 ** for testing and setting up breakpoints.
275 ** It returns:
276 ** - void : in all cases.
277 */
278
279 #ifndef fiboTreeDel
280
281 void
282 fiboTreeDel (
283 FiboTree * const treeptr,
284 FiboNode * const nodeptr)
285 {
286 fiboTreeDelMacro (treeptr, nodeptr);
287
288 #ifdef FIBO_DEBUG
289 nodeptr->pareptr =
290 nodeptr->chldptr =
291 nodeptr->linkdat.prevptr =
292 nodeptr->linkdat.nextptr = NULL;
293
294 fiboTreeCheck (treeptr);
295 #endif /* FIBO_DEBUG */
296 }
297
298 #endif /* fiboTreeDel */
299
300 /* This routine checks the consistency of the
301 ** given linked list.
302 ** It returns:
303 ** - !NULL : pointer to the vertex.
304 ** - NULL : if no such vertex available.
305 */
306
307 #ifdef FIBO_DEBUG
308
309 static
310 int
311 fiboTreeCheck2 (
312 const FiboNode * const nodeptr)
313 {
314 FiboNode * chldptr;
315 int degrval;
316
317 degrval = 0;
318 chldptr = nodeptr->chldptr;
319 if (chldptr != NULL) {
320 do {
321 if (chldptr->linkdat.nextptr->linkdat.prevptr != chldptr) {
322 errorPrint ("fiboTreeCheck: bad child linked list");
323 return (1);
324 }
325
326 if (chldptr->pareptr != nodeptr) {
327 errorPrint ("fiboTreeCheck: bad child parent");
328 return (1);
329 }
330
331 if (fiboTreeCheck2 (chldptr) != 0)
332 return (1);
333
334 degrval ++;
335 chldptr = chldptr->linkdat.nextptr;
336 } while (chldptr != nodeptr->chldptr);
337 }
338
339 if (degrval != (nodeptr->deflval >> 1)) { /* Real node degree is obtained by discarding lowest bit */
340 errorPrint ("fiboTreeCheck2: invalid child information");
341 return (1);
342 }
343
344 return (0);
345 }
346
347 int
348 fiboTreeCheck (
349 const FiboTree * const treeptr)
350 {
351 FiboNode * nodeptr;
352
353 for (nodeptr = treeptr->rootdat.linkdat.nextptr;
354 nodeptr != &treeptr->rootdat; nodeptr = nodeptr->linkdat.nextptr) {
355 if (nodeptr->linkdat.nextptr->linkdat.prevptr != nodeptr) {
356 errorPrint ("fiboTreeCheck: bad root linked list");
357 return (1);
358 }
359
360 if (nodeptr->pareptr != NULL) {
361 errorPrint ("fiboTreeCheck: bad root parent");
362 return (1);
363 }
364
365 if (fiboTreeCheck2 (nodeptr) != 0)
366 return (1);
367 }
368
369 return (0);
370 }
371
372 #endif /* FIBO_DEBUG */