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.h **/
35 /** **/
36 /** AUTHOR : Francois PELLEGRINI **/
37 /** **/
38 /** FUNCTION : This module contains the definitions of **/
39 /** the generic Fibonacci trees. **/
40 /** **/
41 /** DATES : # Version 1.0 : from : 01 may 2010 **/
42 /** to 12 may 2010 **/
43 /** **/
44 /** NOTES : # Since this module has originally been **/
45 /** designed as a gain keeping data **/
46 /** structure for local optimization **/
47 /** algorithms, the computation of the **/
48 /** best node is only done when actually **/
49 /** searching for it. **/
50 /** This is most useful when many **/
51 /** insertions and deletions can take **/
52 /** place in the mean time. This is why **/
53 /** this data structure does not keep **/
54 /** track of the best node, unlike most **/
55 /** implementations do. **/
56 /** **/
57 /************************************************************/
58
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 +*/
68 } FiboLink;
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 +*/
83 } FiboNode;
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 +*/
94 } FiboTree;
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);
190 FiboNode * fiboTreeConsolidate (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