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