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