20 #ifndef _XENO_NUCLEUS_BHEAP_H
21 #define _XENO_NUCLEUS_BHEAP_H
23 #include <nucleus/compiler.h>
26 #include <nucleus/assert.h>
30 typedef unsigned long long bheap_key_t;
32 typedef struct bheaph {
38 #define bheaph_init(holder) do { } while (0)
39 #define bheaph_key(holder) ((holder)->key)
40 #define bheaph_prio(holder) ((holder)->prio)
41 #define bheaph_pos(holder) ((holder)->pos)
42 #define bheaph_lt(h1, h2) ((long long) ((h1)->key - (h2)->key) < 0 || \
43 ((h1)->key == (h2)->key && \
44 (h1)->prio > (h2)->prio))
46 typedef struct bheap {
52 #define DECLARE_BHEAP_CONTAINER(name, sz) \
55 bheaph_t *elems[sz + 1]; \
59 static inline int bheap_ordered(bheap_t *heap)
62 for (i = 2; i < heap->last; i++)
63 if (bheaph_lt(heap->elems[i], heap->elems[i / 2]))
68 #define BHEAP_CHECK(heap) \
69 XENO_BUGON(QUEUES, ((heap)->sz == 0) || !bheap_ordered(heap))
71 #define bheap_gethead(heap) \
73 bheap_t *_bheap = &(heap)->bheap; \
74 BHEAP_CHECK(_bheap); \
75 __internal_bheap_gethead(_bheap); \
78 static inline bheaph_t *__internal_bheap_gethead(bheap_t *heap)
83 return heap->elems[1];
86 #define bheap_next(heap, holder) \
88 bheap_t *_bheap = &(heap)->bheap; \
89 BHEAP_CHECK(_bheap); \
90 __internal_bheap_next(_bheap, holder); \
93 static inline bheaph_t *__internal_bheap_next(bheap_t *heap, bheaph_t *holder)
97 if (unlikely(bheaph_pos(holder) >= heap->last
98 || heap->elems[bheaph_pos(holder)] != holder))
99 return (bheaph_t *) ERR_PTR(-EINVAL);
101 pos = bheaph_pos(holder) + 1;
103 return likely(pos < heap->last) ? heap->elems[pos] : NULL;
106 static inline bheaph_t *bheaph_parent(bheap_t *heap, bheaph_t *holder)
108 const unsigned pos = holder->pos;
110 return likely(pos > 1) ? heap->elems[pos / 2] : NULL;
113 static inline bheaph_t *bheaph_child(bheap_t *heap, bheaph_t *holder,
int side)
115 const unsigned pos = 2 * holder->pos + side;
117 return likely(pos < heap->last) ? heap->elems[pos] : NULL;
120 #define bheap_init(heap, sz) __internal_bheap_init(&(heap)->bheap, sz)
122 static inline void __internal_bheap_init(bheap_t *heap,
unsigned sz)
128 #define bheap_destroy(heap) __internal_bheap_destroy(&(heap)->bheap)
130 static inline void __internal_bheap_destroy(bheap_t *heap)
136 static inline void bheap_swap(bheap_t *heap, bheaph_t *h1, bheaph_t *h2)
138 const unsigned pos2 = bheaph_pos(h2);
140 heap->elems[bheaph_pos(h1)] = h2;
141 bheaph_pos(h2) = bheaph_pos(h1);
142 heap->elems[pos2] = h1;
143 bheaph_pos(h1) = pos2;
146 static inline void bheap_up(bheap_t *heap, bheaph_t *holder)
150 while ((parent = bheaph_parent(heap, holder)) && bheaph_lt(holder, parent))
151 bheap_swap(heap, holder, parent);
154 static inline void bheap_down(bheap_t *heap, bheaph_t *holder)
156 bheaph_t *left, *right, *minchild;
159 left = bheaph_child(heap, holder, 0);
160 right = bheaph_child(heap, holder, 1);
163 minchild = bheaph_lt(left, right) ? left : right;
165 minchild = left ?: right;
167 if (!minchild || bheaph_lt(holder, minchild))
170 bheap_swap(heap, minchild, holder);
174 #define bheap_insert(heap, holder) \
176 bheap_t *_bheap = &(heap)->bheap; \
177 BHEAP_CHECK(_bheap); \
178 __internal_bheap_insert(_bheap, holder); \
181 static inline int __internal_bheap_insert(bheap_t *heap, bheaph_t *holder)
183 if (heap->last == heap->sz + 1)
186 heap->elems[heap->last] = holder;
187 bheaph_pos(holder) = heap->last;
189 bheap_up(heap, holder);
193 #define bheap_delete(heap, holder) \
195 bheap_t *_bheap = &(heap)->bheap; \
196 BHEAP_CHECK(_bheap); \
197 __internal_bheap_delete(_bheap, holder); \
200 static inline int __internal_bheap_delete(bheap_t *heap, bheaph_t *holder)
204 if (unlikely(bheaph_pos(holder) >= heap->last
205 || heap->elems[bheaph_pos(holder)] != holder))
209 if (heap->last != bheaph_pos(holder)) {
211 lasth = heap->elems[heap->last];
212 heap->elems[bheaph_pos(holder)] = lasth;
213 bheaph_pos(lasth) = bheaph_pos(holder);
214 if ((parent = bheaph_parent(heap, lasth)) && bheaph_lt(lasth, parent))
215 bheap_up(heap, lasth);
217 bheap_down(heap, lasth);
223 #define bheap_get(heap) \
225 bheap_t *_bheap = &(heap)->bheap; \
226 BHEAP_CHECK(_bheap); \
227 __internal_bheap_get(_bheap, holder); \
230 static inline bheaph_t *__internal_bheap_get(bheap_t *heap)
232 bheaph_t *holder = __internal_bheap_gethead(heap);
237 __internal_bheap_delete(heap, holder);