aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBjoern B. Brandenburg <bbb@cs.unc.edu>2009-05-02 12:47:17 -0400
committerBjoern B. Brandenburg <bbb@cs.unc.edu>2009-05-02 12:47:17 -0400
commitfb9c387a4c5b6966369b7e916aef68d07a79e6f6 (patch)
tree366fb561bb952e154fdc16fb00cd00823e7ad43d
parent238187ea81334233bdb22a502db17d46a42c98a5 (diff)
litmus core: un-inline binomial heap implementation
Those functions are pretty huge, and used in a couple of plugins. This should save a lot of space, make debugging with objdump much easier, and maybe it even has some I$ benefit.
Diffstat
-rw-r--r--include/litmus/heap.h297
-rw-r--r--litmus/Makefile2
-rw-r--r--litmus/heap.c287
3 files changed, 310 insertions, 276 deletions
diff --git a/include/litmus/heap.h b/include/litmus/heap.h
index e5b4746998..19230f550f 100644
--- a/include/litmus/heap.h
+++ b/include/litmus/heap.h
@@ -28,25 +28,8 @@ struct heap {
28 28
29typedef int (*heap_prio_t)(struct heap_node* a, struct heap_node* b); 29typedef int (*heap_prio_t)(struct heap_node* a, struct heap_node* b);
30 30
31static inline void heap_init(struct heap* heap) 31void heap_init(struct heap* heap);
32{ 32void heap_node_init(struct heap_node** ref_to_heap_node_ptr, void* value);
33 heap->head = NULL;
34 heap->min = NULL;
35}
36
37static inline void heap_node_init(struct heap_node** _h, void* value)
38{
39 struct heap_node* h = *_h;
40 h->parent = NULL;
41 h->next = NULL;
42 h->child = NULL;
43 h->degree = NOT_IN_HEAP;
44 h->value = value;
45 h->ref = _h;
46}
47
48struct heap_node* heap_node_alloc(int gfp_flags);
49void heap_node_free(struct heap_node* hn);
50 33
51static inline int heap_node_in_heap(struct heap_node* h) 34static inline int heap_node_in_heap(struct heap_node* h)
52{ 35{
@@ -58,270 +41,34 @@ static inline int heap_empty(struct heap* heap)
58 return heap->head == NULL && heap->min == NULL; 41 return heap->head == NULL && heap->min == NULL;
59} 42}
60 43
61/* make child a subtree of root */
62static inline void __heap_link(struct heap_node* root,
63 struct heap_node* child)
64{
65 child->parent = root;
66 child->next = root->child;
67 root->child = child;
68 root->degree++;
69}
70
71/* merge root lists */
72static inline struct heap_node* __heap_merge(struct heap_node* a,
73 struct heap_node* b)
74{
75 struct heap_node* head = NULL;
76 struct heap_node** pos = &head;
77
78 while (a && b) {
79 if (a->degree < b->degree) {
80 *pos = a;
81 a = a->next;
82 } else {
83 *pos = b;
84 b = b->next;
85 }
86 pos = &(*pos)->next;
87 }
88 if (a)
89 *pos = a;
90 else
91 *pos = b;
92 return head;
93}
94
95/* reverse a linked list of nodes. also clears parent pointer */
96static inline struct heap_node* __heap_reverse(struct heap_node* h)
97{
98 struct heap_node* tail = NULL;
99 struct heap_node* next;
100
101 if (!h)
102 return h;
103
104 h->parent = NULL;
105 while (h->next) {
106 next = h->next;
107 h->next = tail;
108 tail = h;
109 h = next;
110 h->parent = NULL;
111 }
112 h->next = tail;
113 return h;
114}
115
116static inline void __heap_min(heap_prio_t higher_prio, struct heap* heap,
117 struct heap_node** prev, struct heap_node** node)
118{
119 struct heap_node *_prev, *cur;
120 *prev = NULL;
121
122 if (!heap->head) {
123 *node = NULL;
124 return;
125 }
126
127 *node = heap->head;
128 _prev = heap->head;
129 cur = heap->head->next;
130 while (cur) {
131 if (higher_prio(cur, *node)) {
132 *node = cur;
133 *prev = _prev;
134 }
135 _prev = cur;
136 cur = cur->next;
137 }
138}
139
140static inline void __heap_union(heap_prio_t higher_prio, struct heap* heap,
141 struct heap_node* h2)
142{
143 struct heap_node* h1;
144 struct heap_node *prev, *x, *next;
145 if (!h2)
146 return;
147 h1 = heap->head;
148 if (!h1) {
149 heap->head = h2;
150 return;
151 }
152 h1 = __heap_merge(h1, h2);
153 prev = NULL;
154 x = h1;
155 next = x->next;
156 while (next) {
157 if (x->degree != next->degree ||
158 (next->next && next->next->degree == x->degree)) {
159 /* nothing to do, advance */
160 prev = x;
161 x = next;
162 } else if (higher_prio(x, next)) {
163 /* x becomes the root of next */
164 x->next = next->next;
165 __heap_link(x, next);
166 } else {
167 /* next becomes the root of x */
168 if (prev)
169 prev->next = next;
170 else
171 h1 = next;
172 __heap_link(next, x);
173 x = next;
174 }
175 next = x->next;
176 }
177 heap->head = h1;
178}
179
180static inline struct heap_node* __heap_extract_min(heap_prio_t higher_prio,
181 struct heap* heap)
182{
183 struct heap_node *prev, *node;
184 __heap_min(higher_prio, heap, &prev, &node);
185 if (!node)
186 return NULL;
187 if (prev)
188 prev->next = node->next;
189 else
190 heap->head = node->next;
191 __heap_union(higher_prio, heap, __heap_reverse(node->child));
192 return node;
193}
194
195/* insert (and reinitialize) a node into the heap */ 44/* insert (and reinitialize) a node into the heap */
196static inline void heap_insert(heap_prio_t higher_prio, struct heap* heap, 45void heap_insert(heap_prio_t higher_prio,
197 struct heap_node* node) 46 struct heap* heap,
198{ 47 struct heap_node* node);
199 struct heap_node *min;
200 node->child = NULL;
201 node->parent = NULL;
202 node->next = NULL;
203 node->degree = 0;
204 if (heap->min && higher_prio(node, heap->min)) {
205 /* swap min cache */
206 min = heap->min;
207 min->child = NULL;
208 min->parent = NULL;
209 min->next = NULL;
210 min->degree = 0;
211 __heap_union(higher_prio, heap, min);
212 heap->min = node;
213 } else
214 __heap_union(higher_prio, heap, node);
215}
216
217static inline void __uncache_min(heap_prio_t higher_prio, struct heap* heap)
218{
219 struct heap_node* min;
220 if (heap->min) {
221 min = heap->min;
222 heap->min = NULL;
223 heap_insert(higher_prio, heap, min);
224 }
225}
226 48
227/* merge addition into target */ 49/* merge addition into target */
228static inline void heap_union(heap_prio_t higher_prio, 50void heap_union(heap_prio_t higher_prio,
229 struct heap* target, struct heap* addition) 51 struct heap* target,
230{ 52 struct heap* addition);
231 /* first insert any cached minima, if necessary */
232 __uncache_min(higher_prio, target);
233 __uncache_min(higher_prio, addition);
234 __heap_union(higher_prio, target, addition->head);
235 /* this is a destructive merge */
236 addition->head = NULL;
237}
238 53
239static inline struct heap_node* heap_peek(heap_prio_t higher_prio, 54struct heap_node* heap_peek(heap_prio_t higher_prio,
240 struct heap* heap) 55 struct heap* heap);
241{
242 if (!heap->min)
243 heap->min = __heap_extract_min(higher_prio, heap);
244 return heap->min;
245}
246 56
247static inline struct heap_node* heap_take(heap_prio_t higher_prio, 57struct heap_node* heap_take(heap_prio_t higher_prio,
248 struct heap* heap) 58 struct heap* heap);
249{
250 struct heap_node *node;
251 if (!heap->min)
252 heap->min = __heap_extract_min(higher_prio, heap);
253 node = heap->min;
254 heap->min = NULL;
255 if (node)
256 node->degree = NOT_IN_HEAP;
257 return node;
258}
259 59
260static inline void heap_delete(heap_prio_t higher_prio, struct heap* heap, 60void heap_delete(heap_prio_t higher_prio,
261 struct heap_node* node) 61 struct heap* heap,
262{ 62 struct heap_node* node);
263 struct heap_node *parent, *prev, *pos;
264 struct heap_node** tmp_ref;
265 void* tmp;
266 63
267 if (heap->min != node) { 64/* allocate from memcache */
268 /* bubble up */ 65struct heap_node* heap_node_alloc(int gfp_flags);
269 parent = node->parent; 66void heap_node_free(struct heap_node* hn);
270 while (parent) {
271 /* swap parent and node */
272 tmp = parent->value;
273 parent->value = node->value;
274 node->value = tmp;
275 /* swap references */
276 *(parent->ref) = node;
277 *(node->ref) = parent;
278 tmp_ref = parent->ref;
279 parent->ref = node->ref;
280 node->ref = tmp_ref;
281 /* step up */
282 node = parent;
283 parent = node->parent;
284 }
285 /* now delete:
286 * first find prev */
287 prev = NULL;
288 pos = heap->head;
289 while (pos != node) {
290 prev = pos;
291 pos = pos->next;
292 }
293 /* we have prev, now remove node */
294 if (prev)
295 prev->next = node->next;
296 else
297 heap->head = node->next;
298 __heap_union(higher_prio, heap, __heap_reverse(node->child));
299 } else
300 heap->min = NULL;
301 node->degree = NOT_IN_HEAP;
302}
303 67
304/* allocate a heap node for value and insert into the heap */ 68/* allocate a heap node for value and insert into the heap */
305static inline int heap_add(heap_prio_t higher_prio, struct heap* heap, 69int heap_add(heap_prio_t higher_prio, struct heap* heap,
306 void* value, int gfp_flags) 70 void* value, int gfp_flags);
307{
308 struct heap_node* hn = heap_node_alloc(gfp_flags);
309 if (likely(hn)) {
310 heap_node_init(&hn, value);
311 heap_insert(higher_prio, heap, hn);
312 }
313 return hn != NULL;
314}
315 71
316static inline void* heap_take_del(heap_prio_t higher_prio, 72void* heap_take_del(heap_prio_t higher_prio,
317 struct heap* heap) 73 struct heap* heap);
318{
319 struct heap_node* hn = heap_take(higher_prio, heap);
320 void* ret = NULL;
321 if (hn) {
322 ret = hn->value;
323 heap_node_free(hn);
324 }
325 return ret;
326}
327#endif 74#endif
diff --git a/litmus/Makefile b/litmus/Makefile
index 28a6d79916..d9e8dc042e 100644
--- a/litmus/Makefile
+++ b/litmus/Makefile
@@ -6,7 +6,7 @@ obj-y = sched_plugin.o litmus.o \
6 edf_common.o jobs.o \ 6 edf_common.o jobs.o \
7 rt_domain.o fdso.o sync.o \ 7 rt_domain.o fdso.o sync.o \
8 fmlp.o srp.o norqlock.o \ 8 fmlp.o srp.o norqlock.o \
9 cheap.o \ 9 cheap.o heap.o \
10 sched_gsn_edf.o \ 10 sched_gsn_edf.o \
11 sched_psn_edf.o \ 11 sched_psn_edf.o \
12 sched_cedf.o \ 12 sched_cedf.o \
diff --git a/litmus/heap.c b/litmus/heap.c
new file mode 100644
index 0000000000..4d0d7b96ae
--- /dev/null
+++ b/litmus/heap.c
@@ -0,0 +1,287 @@
1#include "linux/kernel.h"
2#include "litmus/heap.h"
3
4void heap_init(struct heap* heap)
5{
6 heap->head = NULL;
7 heap->min = NULL;
8}
9
10void heap_node_init(struct heap_node** _h, void* value)
11{
12 struct heap_node* h = *_h;
13 h->parent = NULL;
14 h->next = NULL;
15 h->child = NULL;
16 h->degree = NOT_IN_HEAP;
17 h->value = value;
18 h->ref = _h;
19}
20
21
22/* make child a subtree of root */
23static void __heap_link(struct heap_node* root,
24 struct heap_node* child)
25{
26 child->parent = root;
27 child->next = root->child;
28 root->child = child;
29 root->degree++;
30}
31
32/* merge root lists */
33static struct heap_node* __heap_merge(struct heap_node* a,
34 struct heap_node* b)
35{
36 struct heap_node* head = NULL;
37 struct heap_node** pos = &head;
38
39 while (a && b) {
40 if (a->degree < b->degree) {
41 *pos = a;
42 a = a->next;
43 } else {
44 *pos = b;
45 b = b->next;
46 }
47 pos = &(*pos)->next;
48 }
49 if (a)
50 *pos = a;
51 else
52 *pos = b;
53 return head;
54}
55
56/* reverse a linked list of nodes. also clears parent pointer */
57static struct heap_node* __heap_reverse(struct heap_node* h)
58{
59 struct heap_node* tail = NULL;
60 struct heap_node* next;
61
62 if (!h)
63 return h;
64
65 h->parent = NULL;
66 while (h->next) {
67 next = h->next;
68 h->next = tail;
69 tail = h;
70 h = next;
71 h->parent = NULL;
72 }
73 h->next = tail;
74 return h;
75}
76
77static void __heap_min(heap_prio_t higher_prio, struct heap* heap,
78 struct heap_node** prev, struct heap_node** node)
79{
80 struct heap_node *_prev, *cur;
81 *prev = NULL;
82
83 if (!heap->head) {
84 *node = NULL;
85 return;
86 }
87
88 *node = heap->head;
89 _prev = heap->head;
90 cur = heap->head->next;
91 while (cur) {
92 if (higher_prio(cur, *node)) {
93 *node = cur;
94 *prev = _prev;
95 }
96 _prev = cur;
97 cur = cur->next;
98 }
99}
100
101static void __heap_union(heap_prio_t higher_prio, struct heap* heap,
102 struct heap_node* h2)
103{
104 struct heap_node* h1;
105 struct heap_node *prev, *x, *next;
106 if (!h2)
107 return;
108 h1 = heap->head;
109 if (!h1) {
110 heap->head = h2;
111 return;
112 }
113 h1 = __heap_merge(h1, h2);
114 prev = NULL;
115 x = h1;
116 next = x->next;
117 while (next) {
118 if (x->degree != next->degree ||
119 (next->next && next->next->degree == x->degree)) {
120 /* nothing to do, advance */
121 prev = x;
122 x = next;
123 } else if (higher_prio(x, next)) {
124 /* x becomes the root of next */
125 x->next = next->next;
126 __heap_link(x, next);
127 } else {
128 /* next becomes the root of x */
129 if (prev)
130 prev->next = next;
131 else
132 h1 = next;
133 __heap_link(next, x);
134 x = next;
135 }
136 next = x->next;
137 }
138 heap->head = h1;
139}
140
141static struct heap_node* __heap_extract_min(heap_prio_t higher_prio,
142 struct heap* heap)
143{
144 struct heap_node *prev, *node;
145 __heap_min(higher_prio, heap, &prev, &node);
146 if (!node)
147 return NULL;
148 if (prev)
149 prev->next = node->next;
150 else
151 heap->head = node->next;
152 __heap_union(higher_prio, heap, __heap_reverse(node->child));
153 return node;
154}
155
156/* insert (and reinitialize) a node into the heap */
157void heap_insert(heap_prio_t higher_prio, struct heap* heap,
158 struct heap_node* node)
159{
160 struct heap_node *min;
161 node->child = NULL;
162 node->parent = NULL;
163 node->next = NULL;
164 node->degree = 0;
165 if (heap->min && higher_prio(node, heap->min)) {
166 /* swap min cache */
167 min = heap->min;
168 min->child = NULL;
169 min->parent = NULL;
170 min->next = NULL;
171 min->degree = 0;
172 __heap_union(higher_prio, heap, min);
173 heap->min = node;
174 } else
175 __heap_union(higher_prio, heap, node);
176}
177
178static void __uncache_min(heap_prio_t higher_prio, struct heap* heap)
179{
180 struct heap_node* min;
181 if (heap->min) {
182 min = heap->min;
183 heap->min = NULL;
184 heap_insert(higher_prio, heap, min);
185 }
186}
187
188/* merge addition into target */
189void heap_union(heap_prio_t higher_prio,
190 struct heap* target, struct heap* addition)
191{
192 /* first insert any cached minima, if necessary */
193 __uncache_min(higher_prio, target);
194 __uncache_min(higher_prio, addition);
195 __heap_union(higher_prio, target, addition->head);
196 /* this is a destructive merge */
197 addition->head = NULL;
198}
199
200struct heap_node* heap_peek(heap_prio_t higher_prio,
201 struct heap* heap)
202{
203 if (!heap->min)
204 heap->min = __heap_extract_min(higher_prio, heap);
205 return heap->min;
206}
207
208struct heap_node* heap_take(heap_prio_t higher_prio,
209 struct heap* heap)
210{
211 struct heap_node *node;
212 if (!heap->min)
213 heap->min = __heap_extract_min(higher_prio, heap);
214 node = heap->min;
215 heap->min = NULL;
216 if (node)
217 node->degree = NOT_IN_HEAP;
218 return node;
219}
220
221void heap_delete(heap_prio_t higher_prio, struct heap* heap,
222 struct heap_node* node)
223{
224 struct heap_node *parent, *prev, *pos;
225 struct heap_node** tmp_ref;
226 void* tmp;
227
228 if (heap->min != node) {
229 /* bubble up */
230 parent = node->parent;
231 while (parent) {
232 /* swap parent and node */
233 tmp = parent->value;
234 parent->value = node->value;
235 node->value = tmp;
236 /* swap references */
237 *(parent->ref) = node;
238 *(node->ref) = parent;
239 tmp_ref = parent->ref;
240 parent->ref = node->ref;
241 node->ref = tmp_ref;
242 /* step up */
243 node = parent;
244 parent = node->parent;
245 }
246 /* now delete:
247 * first find prev */
248 prev = NULL;
249 pos = heap->head;
250 while (pos != node) {
251 prev = pos;
252 pos = pos->next;
253 }
254 /* we have prev, now remove node */
255 if (prev)
256 prev->next = node->next;
257 else
258 heap->head = node->next;
259 __heap_union(higher_prio, heap, __heap_reverse(node->child));
260 } else
261 heap->min = NULL;
262 node->degree = NOT_IN_HEAP;
263}
264
265/* allocate a heap node for value and insert into the heap */
266int heap_add(heap_prio_t higher_prio, struct heap* heap,
267 void* value, int gfp_flags)
268{
269 struct heap_node* hn = heap_node_alloc(gfp_flags);
270 if (likely(hn)) {
271 heap_node_init(&hn, value);
272 heap_insert(higher_prio, heap, hn);
273 }
274 return hn != NULL;
275}
276
277void* heap_take_del(heap_prio_t higher_prio,
278 struct heap* heap)
279{
280 struct heap_node* hn = heap_take(higher_prio, heap);
281 void* ret = NULL;
282 if (hn) {
283 ret = hn->value;
284 heap_node_free(hn);
285 }
286 return ret;
287}
generated by cgit v1.2.2 (git 2.25.0) at 2025-04-14 13:47:30 -0400