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 } \ 64 phn_lchild_set(a_type, a_field, a_phn0, a_phn1); \ 65 } while (0) 66 67 #define phn_merge(a_type, a_field, a_phn0, a_phn1, a_cmp, r_phn) do { \ 68 if (a_phn0 == NULL) { \ 69 r_phn = a_phn1; \ 70 } else if (a_phn1 == NULL) { \ 71 r_phn = a_phn0; \ 72 } else if (a_cmp(a_phn0, a_phn1) < 0) { \ 73 phn_merge_ordered(a_type, a_field, a_phn0, a_phn1, \ 74 a_cmp); \ 75 r_phn = a_phn0; \ 76 } else { \ 77 phn_merge_ordered(a_type, a_field, a_phn1, a_phn0, \ 78 a_cmp); \ 79 r_phn = a_phn1; \ 80 } \ 81 } while (0) 82 83 #define ph_merge_siblings(a_type, a_field, a_phn, a_cmp, r_phn) do { \ 84 a_type *head = NULL; \ 85 a_type *tail = NULL; \ 86 a_type *phn0 = a_phn; \ 87 a_type *phn1 = phn_next_get(a_type, a_field, phn0); \ 88 \ 89 /* \ 90 * Multipass merge, wherein the first two elements of a FIFO \ 91 * are repeatedly merged, and each result is appended to the \ 92 * singly linked FIFO, until the FIFO contains only a single \ 93 * element. We start with a sibling list but no reference to \ 94 * its tail, so we do a single pass over the sibling list to \ 95 * populate the FIFO. \ 96 */ \ 97 if (phn1 != NULL) { \ 98 a_type *phnrest = phn_next_get(a_type, a_field, phn1); \ 99 if (phnrest != NULL) { \ 100 phn_prev_set(a_type, a_field, phnrest, NULL); \ 101 } \ 102 phn_prev_set(a_type, a_field, phn0, NULL); \ 103 phn_next_set(a_type, a_field, phn0, NULL); \ 104 phn_prev_set(a_type, a_field, phn1, NULL); \ 105 phn_next_set(a_type, a_field, phn1, NULL); \ 106 phn_merge(a_type, a_field, phn0, phn1, a_cmp, phn0); \ 107 head = tail = phn0; \ 108 phn0 = phnrest; \ 109 while (phn0 != NULL) { \ 110 phn1 = phn_next_get(a_type, a_field, phn0); \ 111 if (phn1 != NULL) { \ 112 phnrest = phn_next_get(a_type, a_field, \ 113 phn1); \ 114 if (phnrest != NULL) { \ 115 phn_prev_set(a_type, a_field, \ 116 phnrest, NULL); \ 117 } \ 118 phn_prev_set(a_type, a_field, phn0, \ 119 NULL); \ 120 phn_next_set(a_type, a_field, phn0, \ 121 NULL); \ 122 phn_prev_set(a_type, a_field, phn1, \ 123 NULL); \ 124 phn_next_set(a_type, a_field, phn1, \ 125 NULL); \ 126 phn_merge(a_type, a_field, phn0, phn1, \ 127 a_cmp, phn0); \ 128 phn_next_set(a_type, a_field, tail, \ 129 phn0); \ 130 tail = phn0; \ 131 phn0 = phnrest; \ 132 } else { \ 133 phn_next_set(a_type, a_field, tail, \ 134 phn0); \ 135 tail = phn0; \ 136 phn0 = NULL; \ 137 } \ 138 } \ 139 phn0 = head; \ 140 phn1 = phn_next_get(a_type, a_field, phn0); \ 141 if (phn1 != NULL) { \ 142 while (true) { \ 143 head = phn_next_get(a_type, a_field, \ 144 phn1); \ 145 assert(phn_prev_get(a_type, a_field, \ 146 phn0) == NULL); \ 147 phn_next_set(a_type, a_field, phn0, \ 148 NULL); \ 149 assert(phn_prev_get(a_type, a_field, \ 150 phn1) == NULL); \ 151 phn_next_set(a_type, a_field, phn1, \ 152 NULL); \ 153 phn_merge(a_type, a_field, phn0, phn1, \ 154 a_cmp, phn0); \ 155 if (head == NULL) { \ 156 break; \ 157 } \ 158 phn_next_set(a_type, a_field, tail, \ 159 phn0); \ 160 tail = phn0; \ 161 phn0 = head; \ 162 phn1 = phn_next_get(a_type, a_field, \ 163 phn0); \ 164 } \ 165 } \ 166 } \ 167 r_phn = phn0; \ 168 } while (0) 169 170 #define ph_merge_aux(a_type, a_field, a_ph, a_cmp) do { \ 171 a_type *phn = phn_next_get(a_type, a_field, a_ph->ph_root); \ 172 if (phn != NULL) { \ 173 phn_prev_set(a_type, a_field, a_ph->ph_root, NULL); \ 174 phn_next_set(a_type, a_field, a_ph->ph_root, NULL); \ 175 phn_prev_set(a_type, a_field, phn, NULL); \ 176 ph_merge_siblings(a_type, a_field, phn, a_cmp, phn); \ 177 assert(phn_next_get(a_type, a_field, phn) == NULL); \ 178 phn_merge(a_type, a_field, a_ph->ph_root, phn, a_cmp, \ 179 a_ph->ph_root); \ 180 } \ 181 } while (0) 182 183 #define ph_merge_children(a_type, a_field, a_phn, a_cmp, r_phn) do { \ 184 a_type *lchild = phn_lchild_get(a_type, a_field, a_phn); \ 185 if (lchild == NULL) { \ 186 r_phn = NULL; \ 187 } else { \ 188 ph_merge_siblings(a_type, a_field, lchild, a_cmp, \ 189 r_phn); \ 190 } \ 191 } while (0) 192 193 /* 194 * The ph_proto() macro generates function prototypes that correspond to the 195 * functions generated by an equivalently parameterized call to ph_gen(). 196 */ 197 #define ph_proto(a_attr, a_prefix, a_ph_type, a_type) \ 198 a_attr void a_prefix##new(a_ph_type *ph); \ 199 a_attr bool a_prefix##empty(a_ph_type *ph); \ 200 a_attr a_type *a_prefix##first(a_ph_type *ph); \ 201 a_attr a_type *a_prefix##any(a_ph_type *ph); \ 202 a_attr void a_prefix##insert(a_ph_type *ph, a_type *phn); \ 203 a_attr a_type *a_prefix##remove_first(a_ph_type *ph); \ 204 a_attr a_type *a_prefix##remove_any(a_ph_type *ph); \ 205 a_attr void a_prefix##remove(a_ph_type *ph, a_type *phn); 206 207 /* 208 * The ph_gen() macro generates a type-specific pairing heap implementation, 209 * based on the above cpp macros. 210 */ 211 #define ph_gen(a_attr, a_prefix, a_ph_type, a_type, a_field, a_cmp) \ 212 a_attr void \ 213 a_prefix##new(a_ph_type *ph) { \ 214 memset(ph, 0, sizeof(ph(a_type))); \ 215 } \ 216 a_attr bool \ 217 a_prefix##empty(a_ph_type *ph) { \ 218 return (ph->ph_root == NULL); \ 219 } \ 220 a_attr a_type * \ 221 a_prefix##first(a_ph_type *ph) { \ 222 if (ph->ph_root == NULL) { \ 223 return NULL; \ 224 } \ 225 ph_merge_aux(a_type, a_field, ph, a_cmp); \ 226 return ph->ph_root; \ 227 } \ 228 a_attr a_type * \ 229 a_prefix##any(a_ph_type *ph) { \ 230 if (ph->ph_root == NULL) { \ 231 return NULL; \ 232 } \ 233 a_type *aux = phn_next_get(a_type, a_field, ph->ph_root); \ 234 if (aux != NULL) { \ 235 return aux; \ 236 } \ 237 return ph->ph_root; \ 238 } \ 239 a_attr void \ 240 a_prefix##insert(a_ph_type *ph, a_type *phn) { \ 241 memset(&phn->a_field, 0, sizeof(phn(a_type))); \ 242 \ 243 /* \ 244 * Treat the root as an aux list during insertion, and lazily \ 245 * merge during a_prefix##remove_first(). For elements that \ 246 * are inserted, then removed via a_prefix##remove() before the \ 247 * aux list is ever processed, this makes insert/remove \ 248 * constant-time, whereas eager merging would make insert \ 249 * O(log n). \ 250 */ \ 251 if (ph->ph_root == NULL) { \ 252 ph->ph_root = phn; \ 253 } else { \ 254 phn_next_set(a_type, a_field, phn, phn_next_get(a_type, \ 255 a_field, ph->ph_root)); \ 256 if (phn_next_get(a_type, a_field, ph->ph_root) != \ 257 NULL) { \ 258 phn_prev_set(a_type, a_field, \ 259 phn_next_get(a_type, a_field, ph->ph_root), \ 260 phn); \ 261 } \ 262 phn_prev_set(a_type, a_field, phn, ph->ph_root); \ 263 phn_next_set(a_type, a_field, ph->ph_root, phn); \ 264 } \ 265 } \ 266 a_attr a_type * \ 267 a_prefix##remove_first(a_ph_type *ph) { \ 268 a_type *ret; \ 269 \ 270 if (ph->ph_root == NULL) { \ 271 return NULL; \ 272 } \ 273 ph_merge_aux(a_type, a_field, ph, a_cmp); \ 274 \ 275 ret = ph->ph_root; \ 276 \ 277 ph_merge_children(a_type, a_field, ph->ph_root, a_cmp, \ 278 ph->ph_root); \ 279 \ 280 return ret; \ 281 } \ 282 a_attr a_type * \ 283 a_prefix##remove_any(a_ph_type *ph) { \ 284 /* \ 285 * Remove the most recently inserted aux list element, or the \ 286 * root if the aux list is empty. This has the effect of \ 287 * behaving as a LIFO (and insertion/removal is therefore \ 288 * constant-time) if a_prefix##[remove_]first() are never \ 289 * called. \ 290 */ \ 291 if (ph->ph_root == NULL) { \ 292 return NULL; \ 293 } \ 294 a_type *ret = phn_next_get(a_type, a_field, ph->ph_root); \ 295 if (ret != NULL) { \ 296 a_type *aux = phn_next_get(a_type, a_field, ret); \ 297 phn_next_set(a_type, a_field, ph->ph_root, aux); \ 298 if (aux != NULL) { \ 299 phn_prev_set(a_type, a_field, aux, \ 300 ph->ph_root); \ 301 } \ 302 return ret; \ 303 } \ 304 ret = ph->ph_root; \ 305 ph_merge_children(a_type, a_field, ph->ph_root, a_cmp, \ 306 ph->ph_root); \ 307 return ret; \ 308 } \ 309 a_attr void \ 310 a_prefix##remove(a_ph_type *ph, a_type *phn) { \ 311 a_type *replace, *parent; \ 312 \ 313 if (ph->ph_root == phn) { \ 314 /* \ 315 * We can delete from aux list without merging it, but \ 316 * we need to merge if we are dealing with the root \ 317 * node and it has children. \ 318 */ \ 319 if (phn_lchild_get(a_type, a_field, phn) == NULL) { \ 320 ph->ph_root = phn_next_get(a_type, a_field, \ 321 phn); \ 322 if (ph->ph_root != NULL) { \ 323 phn_prev_set(a_type, a_field, \ 324 ph->ph_root, NULL); \ 325 } \ 326 return; \ 327 } \ 328 ph_merge_aux(a_type, a_field, ph, a_cmp); \ 329 if (ph->ph_root == phn) { \ 330 ph_merge_children(a_type, a_field, ph->ph_root, \ 331 a_cmp, ph->ph_root); \ 332 return; \ 333 } \ 334 } \ 335 \ 336 /* Get parent (if phn is leftmost child) before mutating. */ \ 337 if ((parent = phn_prev_get(a_type, a_field, phn)) != NULL) { \ 338 if (phn_lchild_get(a_type, a_field, parent) != phn) { \ 339 parent = NULL; \ 340 } \ 341 } \ 342 /* Find a possible replacement node, and link to parent. */ \ 343 ph_merge_children(a_type, a_field, phn, a_cmp, replace); \ 344 /* Set next/prev for sibling linked list. */ \ 345 if (replace != NULL) { \ 346 if (parent != NULL) { \ 347 phn_prev_set(a_type, a_field, replace, parent); \ 348 phn_lchild_set(a_type, a_field, parent, \ 349 replace); \ 350 } else { \ 351 phn_prev_set(a_type, a_field, replace, \ 352 phn_prev_get(a_type, a_field, phn)); \ 353 if (phn_prev_get(a_type, a_field, phn) != \ 354 NULL) { \ 355 phn_next_set(a_type, a_field, \ 356 phn_prev_get(a_type, a_field, phn), \ 357 replace); \ 358 } \ 359 } \ 360 phn_next_set(a_type, a_field, replace, \ 361 phn_next_get(a_type, a_field, phn)); \ 362 if (phn_next_get(a_type, a_field, phn) != NULL) { \ 363 phn_prev_set(a_type, a_field, \ 364 phn_next_get(a_type, a_field, phn), \ 365 replace); \ 366 } \ 367 } else { \ 368 if (parent != NULL) { \ 369 a_type *next = phn_next_get(a_type, a_field, \ 370 phn); \ 371 phn_lchild_set(a_type, a_field, parent, next); \ 372 if (next != NULL) { \ 373 phn_prev_set(a_type, a_field, next, \ 374 parent); \ 375 } \ 376 } else { \ 377 assert(phn_prev_get(a_type, a_field, phn) != \ 378 NULL); \ 379 phn_next_set(a_type, a_field, \ 380 phn_prev_get(a_type, a_field, phn), \ 381 phn_next_get(a_type, a_field, phn)); \ 382 } \ 383 if (phn_next_get(a_type, a_field, phn) != NULL) { \ 384 phn_prev_set(a_type, a_field, \ 385 phn_next_get(a_type, a_field, phn), \ 386 phn_prev_get(a_type, a_field, phn)); \ 387 } \ 388 } \ 389 } 390 391 #endif /* PH_H_ */ 392