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 memset(ph, 0, sizeof(ph(a_type))); \ 211 } \ 212 a_attr bool \ 213 a_prefix##empty(a_ph_type *ph) \ 214 { \ 215 return (ph->ph_root == NULL); \ 216 } \ 217 a_attr a_type * \ 218 a_prefix##first(a_ph_type *ph) \ 219 { \ 220 if (ph->ph_root == NULL) \ 221 return (NULL); \ 222 ph_merge_aux(a_type, a_field, ph, a_cmp); \ 223 return (ph->ph_root); \ 224 } \ 225 a_attr void \ 226 a_prefix##insert(a_ph_type *ph, a_type *phn) \ 227 { \ 228 memset(&phn->a_field, 0, sizeof(phn(a_type))); \ 229 \ 230 /* \ 231 * Treat the root as an aux list during insertion, and lazily \ 232 * merge during a_prefix##remove_first(). For elements that \ 233 * are inserted, then removed via a_prefix##remove() before the \ 234 * aux list is ever processed, this makes insert/remove \ 235 * constant-time, whereas eager merging would make insert \ 236 * O(log n). \ 237 */ \ 238 if (ph->ph_root == NULL) \ 239 ph->ph_root = phn; \ 240 else { \ 241 phn_next_set(a_type, a_field, phn, phn_next_get(a_type, \ 242 a_field, ph->ph_root)); \ 243 if (phn_next_get(a_type, a_field, ph->ph_root) != \ 244 NULL) { \ 245 phn_prev_set(a_type, a_field, \ 246 phn_next_get(a_type, a_field, ph->ph_root), \ 247 phn); \ 248 } \ 249 phn_prev_set(a_type, a_field, phn, ph->ph_root); \ 250 phn_next_set(a_type, a_field, ph->ph_root, phn); \ 251 } \ 252 } \ 253 a_attr a_type * \ 254 a_prefix##remove_first(a_ph_type *ph) \ 255 { \ 256 a_type *ret; \ 257 \ 258 if (ph->ph_root == NULL) \ 259 return (NULL); \ 260 ph_merge_aux(a_type, a_field, ph, a_cmp); \ 261 \ 262 ret = ph->ph_root; \ 263 \ 264 ph_merge_children(a_type, a_field, ph->ph_root, a_cmp, \ 265 ph->ph_root); \ 266 \ 267 return (ret); \ 268 } \ 269 a_attr void \ 270 a_prefix##remove(a_ph_type *ph, a_type *phn) \ 271 { \ 272 a_type *replace, *parent; \ 273 \ 274 /* \ 275 * We can delete from aux list without merging it, but we need \ 276 * to merge if we are dealing with the root node. \ 277 */ \ 278 if (ph->ph_root == phn) { \ 279 ph_merge_aux(a_type, a_field, ph, a_cmp); \ 280 if (ph->ph_root == phn) { \ 281 ph_merge_children(a_type, a_field, ph->ph_root, \ 282 a_cmp, ph->ph_root); \ 283 return; \ 284 } \ 285 } \ 286 \ 287 /* Get parent (if phn is leftmost child) before mutating. */ \ 288 if ((parent = phn_prev_get(a_type, a_field, phn)) != NULL) { \ 289 if (phn_lchild_get(a_type, a_field, parent) != phn) \ 290 parent = NULL; \ 291 } \ 292 /* Find a possible replacement node, and link to parent. */ \ 293 ph_merge_children(a_type, a_field, phn, a_cmp, replace); \ 294 /* Set next/prev for sibling linked list. */ \ 295 if (replace != NULL) { \ 296 if (parent != NULL) { \ 297 phn_prev_set(a_type, a_field, replace, parent); \ 298 phn_lchild_set(a_type, a_field, parent, \ 299 replace); \ 300 } else { \ 301 phn_prev_set(a_type, a_field, replace, \ 302 phn_prev_get(a_type, a_field, phn)); \ 303 if (phn_prev_get(a_type, a_field, phn) != \ 304 NULL) { \ 305 phn_next_set(a_type, a_field, \ 306 phn_prev_get(a_type, a_field, phn), \ 307 replace); \ 308 } \ 309 } \ 310 phn_next_set(a_type, a_field, replace, \ 311 phn_next_get(a_type, a_field, phn)); \ 312 if (phn_next_get(a_type, a_field, phn) != NULL) { \ 313 phn_prev_set(a_type, a_field, \ 314 phn_next_get(a_type, a_field, phn), \ 315 replace); \ 316 } \ 317 } else { \ 318 if (parent != NULL) { \ 319 a_type *next = phn_next_get(a_type, a_field, \ 320 phn); \ 321 phn_lchild_set(a_type, a_field, parent, next); \ 322 if (next != NULL) { \ 323 phn_prev_set(a_type, a_field, next, \ 324 parent); \ 325 } \ 326 } else { \ 327 assert(phn_prev_get(a_type, a_field, phn) != \ 328 NULL); \ 329 phn_next_set(a_type, a_field, \ 330 phn_prev_get(a_type, a_field, phn), \ 331 phn_next_get(a_type, a_field, phn)); \ 332 } \ 333 if (phn_next_get(a_type, a_field, phn) != NULL) { \ 334 phn_prev_set(a_type, a_field, \ 335 phn_next_get(a_type, a_field, phn), \ 336 phn_prev_get(a_type, a_field, phn)); \ 337 } \ 338 } \ 339 } 340 341 #endif /* PH_H_ */ 342