xref: /aosp_15_r20/external/jemalloc_new/include/jemalloc/internal/ph.h (revision 1208bc7e437ced7eb82efac44ba17e3beba411da)
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