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.h
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 
57 
59 /*
60 ** The type and structure definitions.
61 */
62 
63 /* The doubly linked list structure. */
64 
65 typedef struct FiboLink_ {
66  struct FiboNode_ * prevptr; /*+ Pointer to previous sibling element +*/
67  struct FiboNode_ * nextptr; /*+ Pointer to next sibling element +*/
69 
70 /* The tree node data structure. The deflval
71  variable merges degree and flag variables.
72  The degree of a node is smaller than
73  "bitsizeof (INT)", so it can hold on an
74  "int". The flag value is stored in the
75  lowest bit of the value. */
76 
77 
78 typedef struct FiboNode_ {
79  struct FiboNode_ * pareptr; /*+ Pointer to parent element, if any +*/
80  struct FiboNode_ * chldptr; /*+ Pointer to first child element, if any +*/
81  FiboLink linkdat; /*+ Pointers to sibling elements +*/
82  int deflval; /*+ Lowest bit: flag value; other bits: degree value +*/
84 
85 /* The tree data structure. The fake dummy node aims
86  at handling root node insertion without any test.
87  This is important as many insertions have to be
88  performed. */
89 
90 typedef struct FiboTree_ {
91  FiboNode rootdat; /*+ Dummy node for fast root insertion +*/
92  FiboNode ** restrict degrtab; /*+ Consolidation array of size "bitsizeof (INT)" +*/
93  int (* cmpfptr) (const FiboNode * const, const FiboNode * const); /*+ Comparison routine +*/
95 
96 /*
97 ** The marco definitions.
98 */
99 
100 /* This is the core of the module. All of
101  the algorithms have been de-recursived
102  and written as macros. */
103 
104 #define fiboTreeLinkAfter(o,n) do { \
105  FiboNode * nextptr; \
106  nextptr = (o)->linkdat.nextptr; \
107  (n)->linkdat.nextptr = nextptr; \
108  (n)->linkdat.prevptr = (o); \
109  nextptr->linkdat.prevptr = (n); \
110  (o)->linkdat.nextptr = (n); \
111  } while (0)
112 
113 #define fiboTreeUnlink(n) do { \
114  (n)->linkdat.prevptr->linkdat.nextptr = (n)->linkdat.nextptr; \
115  (n)->linkdat.nextptr->linkdat.prevptr = (n)->linkdat.prevptr; \
116  } while (0)
117 
118 #define fiboTreeAddMacro(t,n) do { \
119  (n)->pareptr = NULL; \
120  (n)->chldptr = NULL; \
121  (n)->deflval = 0; \
122  fiboTreeLinkAfter (&((t)->rootdat), (n)); \
123  } while (0)
124 
125 #define fiboTreeMinMacro(t) (fiboTreeConsolidate (t))
126 
127 #define fiboTreeCutChildren(t,n) do { \
128  FiboNode * chldptr; \
129  chldptr = (n)->chldptr; \
130  if (chldptr != NULL) { \
131  FiboNode * cendptr; \
132  cendptr = chldptr; \
133  do { \
134  FiboNode * nextptr; \
135  nextptr = chldptr->linkdat.nextptr; \
136  chldptr->pareptr = NULL; \
137  fiboTreeLinkAfter (&((t)->rootdat), chldptr); \
138  chldptr = nextptr; \
139  } while (chldptr != cendptr); \
140  } \
141  } while (0)
142 
143 #define fiboTreeDelMacro(t,n) do { \
144  FiboNode * pareptr; \
145  FiboNode * rghtptr; \
146  pareptr = (n)->pareptr; \
147  fiboTreeUnlink (n); \
148  fiboTreeCutChildren ((t), (n)); \
149  if (pareptr == NULL) \
150  break; \
151  rghtptr = (n)->linkdat.nextptr; \
152  while (1) { \
153  FiboNode * gdpaptr; \
154  int deflval; \
155  deflval = pareptr->deflval - 2; \
156  pareptr->deflval = deflval | 1; \
157  gdpaptr = pareptr->pareptr; \
158  pareptr->chldptr = (deflval <= 1) ? NULL : rghtptr; \
159  if (((deflval & 1) == 0) || (gdpaptr == NULL)) \
160  break; \
161  rghtptr = pareptr->linkdat.nextptr; \
162  fiboTreeUnlink (pareptr); \
163  pareptr->pareptr = NULL; \
164  fiboTreeLinkAfter (&((t)->rootdat), pareptr); \
165  pareptr = gdpaptr; \
166  } \
167  } while (0)
168 
169 /*
170 ** The function prototypes.
171 */
172 
173 /* This set of definitions allows the user
174  to specify whether he prefers to use
175  the fibonacci routines as macros or as
176  regular functions, for instance for
177  debugging. */
178 
179 #define fiboTreeAdd fiboTreeAddMacro
180 /* #define fiboTreeDel fiboTreeDelMacro */
181 /* #define fiboTreeMin fiboTreeMinMacro */
182 
183 #ifndef FIBO
184 #define static
185 #endif
186 
187 int fiboTreeInit (FiboTree * const, int (*) (const FiboNode * const, const FiboNode * const));
188 void fiboTreeExit (FiboTree * const);
189 void fiboTreeFree (FiboTree * const);
191 #ifndef fiboTreeAdd
192 void fiboTreeAdd (FiboTree * const, FiboNode * const);
193 #endif /* fiboTreeAdd */
194 #ifndef fiboTreeDel
195 void fiboTreeDel (FiboTree * const, FiboNode * const);
196 #endif /* fiboTreeDel */
197 #ifndef fiboTreeMin
198 FiboNode * fiboTreeMin (FiboTree * const);
199 #endif /* fiboTreeMin */
200 #ifdef FIBO_DEBUG
201 int fiboTreeCheck (const FiboTree * const);
202 static int fiboTreeCheck2 (const FiboNode * const);
203 #endif /* FIBO_DEBUG */
204 
205 #undef static
FiboTree_::cmpfptr
int(* cmpfptr)(const FiboNode *const, const FiboNode *const)
Definition: fibo.h:93
fiboTreeExit
void fiboTreeExit(FiboTree *const)
Definition: fibo.c:109
FiboTree_::rootdat
FiboNode rootdat
Definition: fibo.h:91
FiboTree_::degrtab
FiboNode **restrict degrtab
Definition: fibo.h:92
FiboTree
struct FiboTree_ FiboTree
fiboTreeAdd
#define fiboTreeAdd
Definition: fibo.h:179
FiboLink
struct FiboLink_ FiboLink
NAME : fibo.h
FiboTree_
Definition: fibo.h:90
FiboNode_::pareptr
struct FiboNode_ * pareptr
Definition: fibo.h:79
FiboNode_
Definition: fibo.h:78
FiboNode_::linkdat
FiboLink linkdat
Definition: fibo.h:81
fiboTreeMin
FiboNode * fiboTreeMin(FiboTree *const)
Definition: fibo.c:232
fiboTreeInit
int fiboTreeInit(FiboTree *const, int(*)(const FiboNode *const, const FiboNode *const))
Definition: fibo.c:86
fiboTreeDel
void fiboTreeDel(FiboTree *const, FiboNode *const)
Definition: fibo.c:282
FiboNode_::deflval
int deflval
Definition: fibo.h:82
FiboNode
struct FiboNode_ FiboNode
fiboTreeFree
void fiboTreeFree(FiboTree *const)
Definition: fibo.c:125
FiboNode_::chldptr
struct FiboNode_ * chldptr
Definition: fibo.h:80
fiboTreeConsolidate
FiboNode * fiboTreeConsolidate(FiboTree *const)
Definition: fibo.c:142