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 206