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