openmpi  3.1.6
About: Open MPI is a high performance Message Passing Interface (MPI) library project combining technologies and resources from several other projects (FT-MPI, LA-MPI, LAM/MPI, and PACX-MPI) in order to build the best MPI library available. 3.x series.
  Fossies Dox: openmpi-3.1.6.tar.bz2  ("unofficial" and yet experimental doxygen-generated source code documentation)  

fibo.c
Go to the documentation of this file.
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 
43 
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 
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
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
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
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 *
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 *
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
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 */
FiboTree_::cmpfptr
int(* cmpfptr)(const FiboNode *const, const FiboNode *const)
Definition: fibo.h:93
fiboTreeAddMacro
#define fiboTreeAddMacro(t, n)
Definition: fibo.h:118
fiboTreeDelMacro
#define fiboTreeDelMacro(t, n)
Definition: fibo.h:143
fiboTreeMin
FiboNode * fiboTreeMin(FiboTree *const treeptr)
Definition: fibo.c:232
memSet
#define memSet
Definition: fibo.c:68
FiboTree_::rootdat
FiboNode rootdat
Definition: fibo.h:91
memory.h
errorPrint
#define errorPrint(s)
Definition: fibo.c:63
FiboTree_::degrtab
FiboNode **restrict degrtab
Definition: fibo.h:92
memAlloc
#define memAlloc
Definition: fibo.c:67
INT
#define INT
Definition: fibo.c:59
fiboTreeAdd
#define fiboTreeAdd
Definition: fibo.h:179
FiboTree_
Definition: fibo.h:90
fiboTreeInit
int fiboTreeInit(FiboTree *const treeptr, int(*cmpfptr)(const FiboNode *const, const FiboNode *const))
Definition: fibo.c:86
fiboTreeLinkAfter
#define fiboTreeLinkAfter(o, n)
Definition: fibo.h:104
FiboNode_::pareptr
struct FiboNode_ * pareptr
Definition: fibo.h:79
FiboNode_
Definition: fibo.h:78
FiboNode_::linkdat
FiboLink linkdat
Definition: fibo.h:81
fiboTreeFree
void fiboTreeFree(FiboTree *const treeptr)
Definition: fibo.c:125
fiboTreeDel
void fiboTreeDel(FiboTree *const treeptr, FiboNode *const nodeptr)
Definition: fibo.c:282
fiboTreeUnlink
#define fiboTreeUnlink(n)
Definition: fibo.h:113
fiboTreeExit
void fiboTreeExit(FiboTree *const treeptr)
Definition: fibo.c:109
fibo.h
memFree
#define memFree
Definition: fibo.c:69
FiboNode_::deflval
int deflval
Definition: fibo.h:82
fiboTreeMinMacro
#define fiboTreeMinMacro(t)
Definition: fibo.h:125
FiboNode_::chldptr
struct FiboNode_ * chldptr
Definition: fibo.h:80
NULL
#define NULL
Copyright (C) 2000-2004 by Etnus, LLC.
Definition: ompi_msgq_dll.c:136
fiboTreeConsolidate
FiboNode * fiboTreeConsolidate(FiboTree *const treeptr)
Definition: fibo.c:142