11#ifndef UTILS_GP_HEAP_H
12#define UTILS_GP_HEAP_H
20#define GP_HEAP_ENTRY(ptr, structure, member) \
21 GP_CONTAINER_OF(ptr, structure, member)
23static inline unsigned long gp_heap_size(gp_heap_head *heap)
25 return heap ? heap->children + 1 : 0;
31static inline void gp_heap_fix_up(gp_heap_head *up, gp_heap_head *old, gp_heap_head *rep)
38 else if (old == up->right)
41 GP_BUG(
"Invalid heap state");
47static inline void gp_heap_fix_up_lr(gp_heap_head *elem, gp_heap_head *up)
59static inline gp_heap_head *gp_heap_swap_left(gp_heap_head *heap)
61 gp_heap_head *left = heap->left;
63 gp_heap_fix_up(heap->up, heap, left);
69 heap->right->up = left;
71 gp_heap_fix_up_lr(left, heap);
73 heap->left = left->left;
78 GP_SWAP(heap->right, left->right);
79 GP_SWAP(heap->children, left->children);
87static inline gp_heap_head *gp_heap_swap_right(gp_heap_head *heap)
89 gp_heap_head *right = heap->right;
90 gp_heap_fix_up(heap->up, heap, right);
96 heap->left->up = right;
98 gp_heap_fix_up_lr(right, heap);
100 heap->right = right->right;
103 GP_SWAP(heap->left, right->left);
104 GP_SWAP(heap->children, right->children);
112static int gp_heap_well_balanced(
unsigned int children)
114 return !((children + 2) & (children + 1));
120GP_WUR gp_heap_head *gp_heap_ins_(gp_heap_head *heap, gp_heap_head *parent, gp_heap_head *elem,
121 int (*cmp)(gp_heap_head *e1, gp_heap_head *e2))
124 memset(elem, 0,
sizeof(*elem));
131 if (!heap->left || !gp_heap_well_balanced(heap->left->children) ||
132 (heap->right && heap->left->children == heap->right->children)) {
134 heap->left = gp_heap_ins_(heap->left, heap, elem, cmp);
136 if (cmp(heap, heap->left))
137 return gp_heap_swap_left(heap);
140 heap->right = gp_heap_ins_(heap->right, heap, elem, cmp);
142 if (cmp(heap, heap->right))
143 return gp_heap_swap_right(heap);
158 int (*cmp)(gp_heap_head *e1, gp_heap_head *e2))
160 return gp_heap_ins_(heap, NULL, elem, cmp);
180 if (!gp_heap_well_balanced(heap->left->children) ||
181 !heap->right || (heap->right->children < heap->left->children/2)) {
192static inline gp_heap_head *gp_heap_bubble_down(gp_heap_head *heap,
193 int (*cmp)(gp_heap_head *e1, gp_heap_head *e2))
195 gp_heap_head *right = heap->right;
196 gp_heap_head *left = heap->left;
199 if (right && left && cmp(right, left))
202 if (right && cmp(heap, right)) {
203 gp_heap_swap_right(heap);
204 right->right = gp_heap_bubble_down(heap, cmp);
208 if (left && cmp(heap, left)) {
209 gp_heap_swap_left(heap);
210 left->left = gp_heap_bubble_down(heap, cmp);
224 int (*cmp)(gp_heap_head *e1, gp_heap_head *e2))
235 last->left = heap->left;
236 last->right = heap->right;
237 last->children = heap->children;
240 gp_heap_fix_up_lr(last, last);
242 return gp_heap_bubble_down(last, cmp);
248GP_WUR static inline gp_heap_head *gp_heap_bubble_up(gp_heap_head *heap,
249 int (*cmp)(gp_heap_head *e1, gp_heap_head *e2))
251 if (!heap || !heap->up)
254 if (cmp(heap, heap->up))
257 gp_heap_head *up = heap->up;
259 if (up->left == heap)
260 up = gp_heap_swap_left(up);
261 else if (up->right == heap)
262 up = gp_heap_swap_right(up);
264 GP_BUG(
"Invalid heap state");
266 return gp_heap_bubble_up(up, cmp);
281 int (*cmp)(gp_heap_head *e1, gp_heap_head *e2))
296 last->left = elem->left;
297 last->right = elem->right;
298 last->children = elem->children;
301 gp_heap_fix_up(elem->up, elem, last);
302 gp_heap_fix_up_lr(last, last);
304 last = gp_heap_bubble_up(last, cmp);
305 last = gp_heap_bubble_down(last, cmp);
#define GP_SWAP(a, b)
Swaps a and b.
A compiler dependent macros.
#define GP_WUR
Expands to warn_unused_result attribute when supported by the compiler.
#define GP_BUG(...)
A debug BUG printf-like macro.
static gp_heap_head * gp_heap_pop(gp_heap_head *heap, int(*cmp)(gp_heap_head *e1, gp_heap_head *e2))
Removes top element from the heap.
static gp_heap_head * gp_heap_rem_last(gp_heap_head *heap, gp_heap_head **last)
Removes last element on the last level.
gp_heap_head * gp_heap_ins(gp_heap_head *heap, gp_heap_head *elem, int(*cmp)(gp_heap_head *e1, gp_heap_head *e2))
Inserts a node into a heap.
static gp_heap_head * gp_heap_rem(gp_heap_head *heap, gp_heap_head *elem, int(*cmp)(gp_heap_head *e1, gp_heap_head *e2))
Removes element from a heap.