1 /* 2 * A Pairing Heap implementation. 3 * 4 * "The Pairing Heap: A New Form of Self-Adjusting Heap" 5 * https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf 6 * 7 * With auxiliary twopass list, described in a follow on paper. 8 * 9 * "Pairing Heaps: Experiments and Analysis" 10 * http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.2988&rep=rep1&type=pdf 11 * 12 ******************************************************************************* 13 */ 14 15 #ifndef PH_H_ 16 #define PH_H_ 17 18 /* Node structure. */ 19 #define phn(a_type) \ 20 struct { \ 21 a_type *phn_prev; \ 22 a_type *phn_next; \ 23 a_type *phn_lchild; \ 24 } 25 26 /* Root structure. */ 27 #define ph(a_type) \ 28 struct { \ 29 a_type *ph_root; \ 30 } 31 32 /* Internal utility macros. */ 33 #define phn_lchild_get(a_type, a_field, a_phn) \ 34 (a_phn->a_field.phn_lchild) 35 #define phn_lchild_set(a_type, a_field, a_phn, a_lchild) do { \ 36 a_phn->a_field.phn_lchild = a_lchild; \ 37 } while (0) 38 39 #define phn_next_get(a_type, a_field, a_phn) \ 40 (a_phn->a_field.phn_next) 41 #define phn_prev_set(a_type, a_field, a_phn, a_prev) do { \ 42 a_phn->a_field.phn_prev = a_prev; \ 43 } while (0) 44 45 #define phn_prev_get(a_type, a_field, a_phn) \ 46 (a_phn->a_field.phn_prev) 47 #define phn_next_set(a_type, a_field, a_phn, a_next) do { \ 48 a_phn->a_field.phn_next = a_next; \ 49 } while (0) 50 51 #define phn_merge_ordered(a_type, a_field, a_phn0, a_phn1, a_cmp) do { \ 52 a_type *phn0child; \ 53 \ 54 assert(a_phn0 != NULL); \ 55 assert(a_phn1 != NULL); \ 56 assert(a_cmp(a_phn0, a_phn1) <= 0); \ 57 \ 58 phn_prev_set(a_type, a_field, a_phn1, a_phn0); \ 59 phn0child = phn_lchild_get(a_type, a_field, a_phn0); \ 60 phn_next_set(a_type, a_field, a_phn1, phn0child); \ 61 if (phn0child != NULL) \ 62 phn_prev_set(a_type, a_field, phn0child, a_phn1); \ 63 phn_lchild_set(a_type, a_field, a_phn0, a_phn1); \ 64 } while (0) 65 66 #define phn_merge(a_type, a_field, a_phn0, a_phn1, a_cmp, r_phn) do { \ 67 if (a_phn0 == NULL) \ 68 r_phn = a_phn1; \ 69 else if (a_phn1 == NULL) \ 70 r_phn = a_phn0; \ 71 else if (a_cmp(a_phn0, a_phn1) < 0) { \ 72 phn_merge_ordered(a_type, a_field, a_phn0, a_phn1, \ 73 a_cmp); \ 74 r_phn = a_phn0; \ 75 } else { \ 76 phn_merge_ordered(a_type, a_field, a_phn1, a_phn0, \ 77 a_cmp); \ 78 r_phn = a_phn1; \ 79 } \ 80 } while (0) 81 82 #define ph_merge_siblings(a_type, a_field, a_phn, a_cmp, r_phn) do { \ 83 a_type *head = NULL; \ 84 a_type *tail = NULL; \ 85 a_type *phn0 = a_phn; \ 86 a_type *phn1 = phn_next_get(a_type, a_field, phn0); \ 87 \ 88 /* \ 89 * Multipass merge, wherein the first two elements of a FIFO \ 90 * are repeatedly merged, and each result is appended to the \ 91 * singly linked FIFO, until the FIFO contains only a single \ 92 * element. We start with a sibling list but no reference to \ 93 * its tail, so we do a single pass over the sibling list to \ 94 * populate the FIFO. \ 95 */ \ 96 if (phn1 != NULL) { \ 97 a_type *phnrest = phn_next_get(a_type, a_field, phn1); \ 98 if (phnrest != NULL) \ 99 phn_prev_set(a_type, a_field, phnrest, NULL); \ 100 phn_prev_set(a_type, a_field, phn0, NULL); \ 101 phn_next_set(a_type, a_field, phn0, NULL); \ 102 phn_prev_set(a_type, a_field, phn1, NULL); \ 103 phn_next_set(a_type, a_field, phn1, NULL); \ 104 phn_merge(a_type, a_field, phn0, phn1, a_cmp, phn0); \ 105 head = tail = phn0; \ 106 phn0 = phnrest; \ 107 while (phn0 != NULL) { \ 108 phn1 = phn_next_get(a_type, a_field, phn0); \ 109 if (phn1 != NULL) { \ 110 phnrest = phn_next_get(a_type, a_field, \ 111 phn1); \ 112 if (phnrest != NULL) { \ 113 phn_prev_set(a_type, a_field, \ 114 phnrest, NULL); \ 115 } \ 116 phn_prev_set(a_type, a_field, phn0, \ 117 NULL); \ 118 phn_next_set(a_type, a_field, phn0, \ 119 NULL); \ 120 phn_prev_set(a_type, a_field, phn1, \ 121 NULL); \ 122 phn_next_set(a_type, a_field, phn1, \ 123 NULL); \ 124 phn_merge(a_type, a_field, phn0, phn1, \ 125 a_cmp, phn0); \ 126 phn_next_set(a_type, a_field, tail, \ 127 phn0); \ 128 tail = phn0; \ 129 phn0 = phnrest; \ 130 } else { \ 131 phn_next_set(a_type, a_field, tail, \ 132 phn0); \ 133 tail = phn0; \ 134 phn0 = NULL; \ 135 } \ 136 } \ 137 phn0 = head; \ 138 phn1 = phn_next_get(a_type, a_field, phn0); \ 139 if (phn1 != NULL) { \ 140 while (true) { \ 141 head = phn_next_get(a_type, a_field, \ 142 phn1); \ 143 assert(phn_prev_get(a_type, a_field, \ 144 phn0) == NULL); \ 145 phn_next_set(a_type, a_field, phn0, \ 146 NULL); \ 147 assert(phn_prev_get(a_type, a_field, \ 148 phn1) == NULL); \ 149 phn_next_set(a_type, a_field, phn1, \ 150 NULL); \ 151 phn_merge(a_type, a_field, phn0, phn1, \ 152 a_cmp, phn0); \ 153 if (head == NULL) \ 154 break; \ 155 phn_next_set(a_type, a_field, tail, \ 156 phn0); \ 157 tail = phn0; \ 158 phn0 = head; \ 159 phn1 = phn_next_get(a_type, a_field, \ 160 phn0); \ 161 } \ 162 } \ 163 } \ 164 r_phn = phn0; \ 165 } while (0) 166 167 #define ph_merge_aux(a_type, a_field, a_ph, a_cmp) do { \ 168 a_type *phn = phn_next_get(a_type, a_field, a_ph->ph_root); \ 169 if (phn != NULL) { \ 170 phn_prev_set(a_type, a_field, a_ph->ph_root, NULL); \ 171 phn_next_set(a_type, a_field, a_ph->ph_root, NULL); \ 172 phn_prev_set(a_type, a_field, phn, NULL); \ 173 ph_merge_siblings(a_type, a_field, phn, a_cmp, phn); \ 174 assert(phn_next_get(a_type, a_field, phn) == NULL); \ 175 phn_merge(a_type, a_field, a_ph->ph_root, phn, a_cmp, \ 176 a_ph->ph_root); \ 177 } \ 178 } while (0) 179 180 #define ph_merge_children(a_type, a_field, a_phn, a_cmp, r_phn) do { \ 181 a_type *lchild = phn_lchild_get(a_type, a_field, a_phn); \ 182 if (lchild == NULL) \ 183 r_phn = NULL; \ 184 else { \ 185 ph_merge_siblings(a_type, a_field, lchild, a_cmp, \ 186 r_phn); \ 187 } \ 188 } while (0) 189 190 /* 191 * The ph_proto() macro generates function prototypes that correspond to the 192 * functions generated by an equivalently parameterized call to ph_gen(). 193 */ 194 #define ph_proto(a_attr, a_prefix, a_ph_type, a_type) \ 195 a_attr void a_prefix##new(a_ph_type *ph); \ 196 a_attr bool a_prefix##empty(a_ph_type *ph); \ 197 a_attr a_type *a_prefix##first(a_ph_type *ph); \ 198 a_attr void a_prefix##insert(a_ph_type *ph, a_type *phn); \ 199 a_attr a_type *a_prefix##remove_first(a_ph_type *ph); \ 200 a_attr void a_prefix##remove(a_ph_type *ph, a_type *phn); 201 202 /* 203 * The ph_gen() macro generates a type-specific pairing heap implementation, 204 * based on the above cpp macros. 205 */ 206 #define ph_gen(a_attr, a_prefix, a_ph_type, a_type, a_field, a_cmp) \ 207 a_attr void \ 208 a_prefix##new(a_ph_type *ph) \ 209 { \ 210 \ 211 memset(ph, 0, sizeof(ph(a_type))); \ 212 } \ 213 a_attr bool \ 214 a_prefix##empty(a_ph_type *ph) \ 215 { \ 216 \ 217 return (ph->ph_root == NULL); \ 218 } \ 219 a_attr a_type * \ 220 a_prefix##first(a_ph_type *ph) \ 221 { \ 222 \ 223 if (ph->ph_root == NULL) \ 224 return (NULL); \ 225 ph_merge_aux(a_type, a_field, ph, a_cmp); \ 226 return (ph->ph_root); \ 227 } \ 228 a_attr void \ 229 a_prefix##insert(a_ph_type *ph, a_type *phn) \ 230 { \ 231 \ 232 memset(&phn->a_field, 0, sizeof(phn(a_type))); \ 233 \ 234 /* \ 235 * Treat the root as an aux list during insertion, and lazily \ 236 * merge during a_prefix##remove_first(). For elements that \ 237 * are inserted, then removed via a_prefix##remove() before the \ 238 * aux list is ever processed, this makes insert/remove \ 239 * constant-time, whereas eager merging would make insert \ 240 * O(log n). \ 241 */ \ 242 if (ph->ph_root == NULL) \ 243 ph->ph_root = phn; \ 244 else { \ 245 phn_next_set(a_type, a_field, phn, phn_next_get(a_type, \ 246 a_field, ph->ph_root)); \ 247 if (phn_next_get(a_type, a_field, ph->ph_root) != \ 248 NULL) { \ 249 phn_prev_set(a_type, a_field, \ 250 phn_next_get(a_type, a_field, ph->ph_root), \ 251 phn); \ 252 } \ 253 phn_prev_set(a_type, a_field, phn, ph->ph_root); \ 254 phn_next_set(a_type, a_field, ph->ph_root, phn); \ 255 } \ 256 } \ 257 a_attr a_type * \ 258 a_prefix##remove_first(a_ph_type *ph) \ 259 { \ 260 a_type *ret; \ 261 \ 262 if (ph->ph_root == NULL) \ 263 return (NULL); \ 264 ph_merge_aux(a_type, a_field, ph, a_cmp); \ 265 \ 266 ret = ph->ph_root; \ 267 \ 268 ph_merge_children(a_type, a_field, ph->ph_root, a_cmp, \ 269 ph->ph_root); \ 270 \ 271 return (ret); \ 272 } \ 273 a_attr void \ 274 a_prefix##remove(a_ph_type *ph, a_type *phn) \ 275 { \ 276 a_type *replace, *parent; \ 277 \ 278 /* \ 279 * We can delete from aux list without merging it, but we need \ 280 * to merge if we are dealing with the root node. \ 281 */ \ 282 if (ph->ph_root == phn) { \ 283 ph_merge_aux(a_type, a_field, ph, a_cmp); \ 284 if (ph->ph_root == phn) { \ 285 ph_merge_children(a_type, a_field, ph->ph_root, \ 286 a_cmp, ph->ph_root); \ 287 return; \ 288 } \ 289 } \ 290 \ 291 /* Get parent (if phn is leftmost child) before mutating. */ \ 292 if ((parent = phn_prev_get(a_type, a_field, phn)) != NULL) { \ 293 if (phn_lchild_get(a_type, a_field, parent) != phn) \ 294 parent = NULL; \ 295 } \ 296 /* Find a possible replacement node, and link to parent. */ \ 297 ph_merge_children(a_type, a_field, phn, a_cmp, replace); \ 298 /* Set next/prev for sibling linked list. */ \ 299 if (replace != NULL) { \ 300 if (parent != NULL) { \ 301 phn_prev_set(a_type, a_field, replace, parent); \ 302 phn_lchild_set(a_type, a_field, parent, \ 303 replace); \ 304 } else { \ 305 phn_prev_set(a_type, a_field, replace, \ 306 phn_prev_get(a_type, a_field, phn)); \ 307 if (phn_prev_get(a_type, a_field, phn) != \ 308 NULL) { \ 309 phn_next_set(a_type, a_field, \ 310 phn_prev_get(a_type, a_field, phn), \ 311 replace); \ 312 } \ 313 } \ 314 phn_next_set(a_type, a_field, replace, \ 315 phn_next_get(a_type, a_field, phn)); \ 316 if (phn_next_get(a_type, a_field, phn) != NULL) { \ 317 phn_prev_set(a_type, a_field, \ 318 phn_next_get(a_type, a_field, phn), \ 319 replace); \ 320 } \ 321 } else { \ 322 if (parent != NULL) { \ 323 a_type *next = phn_next_get(a_type, a_field, \ 324 phn); \ 325 phn_lchild_set(a_type, a_field, parent, next); \ 326 if (next != NULL) { \ 327 phn_prev_set(a_type, a_field, next, \ 328 parent); \ 329 } \ 330 } else { \ 331 assert(phn_prev_get(a_type, a_field, phn) != \ 332 NULL); \ 333 phn_next_set(a_type, a_field, \ 334 phn_prev_get(a_type, a_field, phn), \ 335 phn_next_get(a_type, a_field, phn)); \ 336 } \ 337 if (phn_next_get(a_type, a_field, phn) != NULL) { \ 338 phn_prev_set(a_type, a_field, \ 339 phn_next_get(a_type, a_field, phn), \ 340 phn_prev_get(a_type, a_field, phn)); \ 341 } \ 342 } \ 343 } 344 345 #endif /* PH_H_ */ 346
