Rizin
unix-like reverse engineering framework and cli tools
ph.h
Go to the documentation of this file.
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, rz_phn) do { \
67  if (a_phn0 == NULL) \
68  rz_phn = a_phn1; \
69  else if (a_phn1 == NULL) \
70  rz_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  rz_phn = a_phn0; \
75  } else { \
76  phn_merge_ordered(a_type, a_field, a_phn1, a_phn0, \
77  a_cmp); \
78  rz_phn = a_phn1; \
79  } \
80 } while (0)
81 
82 #define ph_merge_siblings(a_type, a_field, a_phn, a_cmp, rz_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  rz_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, rz_phn) do { \
181  a_type *lchild = phn_lchild_get(a_type, a_field, a_phn); \
182  if (lchild == NULL) \
183  rz_phn = NULL; \
184  else { \
185  ph_merge_siblings(a_type, a_field, lchild, a_cmp, \
186  rz_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_ */