2 * @file variable_pairing_heap.h
4 * @author Jeremy Maitin-Shepard <jeremy@jeremyms.com>
6 * This file defines a type-generic pairing heap implementation as
7 * several macros that generate the implementation code.
10 #ifndef _VARIABLE_PAIRING_HEAP_H
11 #define _VARIABLE_PAIRING_HEAP_H
13 #define PH_NEW_LINK(PH_ELEM_TYPE) \
16 PH_ELEM_TYPE *child, *next, *prev; \
19 #define PH_DECLARE_TYPE(PH_PREFIX, PH_ELEM_TYPE) \
20 typedef PH_ELEM_TYPE *PH_PREFIX ## _t; \
21 void PH_PREFIX ## _init(PH_PREFIX ## _t *ph); \
22 PH_ELEM_TYPE *PH_PREFIX ## _min(PH_PREFIX ## _t *ph); \
23 void PH_PREFIX ## _insert(PH_PREFIX ## _t *ph, PH_ELEM_TYPE *elem); \
24 void PH_PREFIX ## _remove(PH_PREFIX ## _t *ph, PH_ELEM_TYPE *elem); \
25 void PH_PREFIX ## _remove_min(PH_PREFIX ## _t *ph);
27 #define PH_DEFINE_TYPE(PH_PREFIX, PH_ELEM_TYPE, PH_NODE_NAME, PH_KEY_NAME) \
28 void PH_PREFIX ## _init(PH_PREFIX ## _t *ph) \
32 PH_ELEM_TYPE *PH_PREFIX ## _min(PH_PREFIX ## _t *ph) \
36 static PH_ELEM_TYPE *PH_PREFIX ## _meld(PH_ELEM_TYPE *a, \
41 if (a->PH_KEY_NAME > b->PH_KEY_NAME) \
43 PH_ELEM_TYPE *temp = a; \
47 b->PH_NODE_NAME.next = a->PH_NODE_NAME.child; \
48 b->PH_NODE_NAME.prev = a; \
49 if (a->PH_NODE_NAME.child) \
50 a->PH_NODE_NAME.child->PH_NODE_NAME.prev = b; \
51 a->PH_NODE_NAME.child = b; \
54 void PH_PREFIX ## _insert(PH_PREFIX ## _t *ph, PH_ELEM_TYPE *elem) \
56 elem->PH_NODE_NAME.child = NULL; \
57 elem->PH_NODE_NAME.next = NULL; \
58 elem->PH_NODE_NAME.prev = NULL; \
59 *ph = PH_PREFIX ## _meld(elem, *ph); \
61 static PH_ELEM_TYPE *PH_PREFIX ## _combine_children(PH_ELEM_TYPE *ph) \
63 PH_ELEM_TYPE *head = NULL, *tail = NULL, *cur = ph->PH_NODE_NAME.child, \
64 *next, *nnext, *m = NULL; \
69 if (!cur->PH_NODE_NAME.next) \
72 next = cur->PH_NODE_NAME.next->PH_NODE_NAME.next; \
73 m = PH_PREFIX ## _meld(cur, cur->PH_NODE_NAME.next); \
75 tail->PH_NODE_NAME.next = m; \
83 while (head != tail) \
85 next = head->PH_NODE_NAME.next; \
86 nnext = next->PH_NODE_NAME.next; \
87 m = PH_PREFIX ## _meld(head, next); \
90 tail->PH_NODE_NAME.next = m; \
94 m->PH_NODE_NAME.prev = NULL; \
95 m->PH_NODE_NAME.next = NULL; \
98 void PH_PREFIX ## _remove_min(PH_PREFIX ## _t *ph) \
100 *ph = PH_PREFIX ## _combine_children(*ph); \
102 void PH_PREFIX ## _remove(PH_PREFIX ## _t *ph, PH_ELEM_TYPE *elem) \
105 PH_PREFIX ## _remove_min(ph); \
108 PH_ELEM_TYPE *prev = elem->PH_NODE_NAME.prev; \
109 if (prev->PH_NODE_NAME.child == elem) \
110 prev->PH_NODE_NAME.child = elem->PH_NODE_NAME.next; \
112 prev->PH_NODE_NAME.next = elem->PH_NODE_NAME.next; \
113 if (elem->PH_NODE_NAME.next) \
114 elem->PH_NODE_NAME.next->PH_NODE_NAME.prev = prev; \
115 *ph = PH_PREFIX ## _meld \
116 (*ph, PH_PREFIX ## _combine_children(elem)); \
120 #endif /* _VARIABLE_PAIRING_HEAP_H */