aboutsummaryrefslogtreecommitdiffstats
path: root/include/litmus
diff options
context:
space:
mode:
authorAndrea Bastoni <bastoni@cs.unc.edu>2009-12-21 12:23:57 -0500
committerAndrea Bastoni <bastoni@cs.unc.edu>2010-05-29 17:20:00 -0400
commitee09f78d8faa0b988088d93142e6f5f8a6e75394 (patch)
treebc1e0b5db121be3de47d967973310d610ad943a2 /include/litmus
parent0b28a3122d6917784701377e15a863489aee1c6c (diff)
Refactor binomial heap names: heap -> bheap
- Binomial heap "heap" names conflicted with priority heap of cgroup in kernel - This patch change binomial heap "heap" names in "bheap"
Diffstat (limited to 'include/litmus')
-rw-r--r--include/litmus/bheap.h77
-rw-r--r--include/litmus/edf_common.h2
-rw-r--r--include/litmus/heap.h77
-rw-r--r--include/litmus/litmus.h2
-rw-r--r--include/litmus/rt_domain.h36
-rw-r--r--include/litmus/rt_param.h4
6 files changed, 99 insertions, 99 deletions
diff --git a/include/litmus/bheap.h b/include/litmus/bheap.h
new file mode 100644
index 000000000000..cf4864a498d8
--- /dev/null
+++ b/include/litmus/bheap.h
@@ -0,0 +1,77 @@
1/* bheaps.h -- Binomial Heaps
2 *
3 * (c) 2008, 2009 Bjoern Brandenburg
4 */
5
6#ifndef BHEAP_H
7#define BHEAP_H
8
9#define NOT_IN_HEAP UINT_MAX
10
11struct bheap_node {
12 struct bheap_node* parent;
13 struct bheap_node* next;
14 struct bheap_node* child;
15
16 unsigned int degree;
17 void* value;
18 struct bheap_node** ref;
19};
20
21struct bheap {
22 struct bheap_node* head;
23 /* We cache the minimum of the heap.
24 * This speeds up repeated peek operations.
25 */
26 struct bheap_node* min;
27};
28
29typedef int (*bheap_prio_t)(struct bheap_node* a, struct bheap_node* b);
30
31void bheap_init(struct bheap* heap);
32void bheap_node_init(struct bheap_node** ref_to_bheap_node_ptr, void* value);
33
34static inline int bheap_node_in_heap(struct bheap_node* h)
35{
36 return h->degree != NOT_IN_HEAP;
37}
38
39static inline int bheap_empty(struct bheap* heap)
40{
41 return heap->head == NULL && heap->min == NULL;
42}
43
44/* insert (and reinitialize) a node into the heap */
45void bheap_insert(bheap_prio_t higher_prio,
46 struct bheap* heap,
47 struct bheap_node* node);
48
49/* merge addition into target */
50void bheap_union(bheap_prio_t higher_prio,
51 struct bheap* target,
52 struct bheap* addition);
53
54struct bheap_node* bheap_peek(bheap_prio_t higher_prio,
55 struct bheap* heap);
56
57struct bheap_node* bheap_take(bheap_prio_t higher_prio,
58 struct bheap* heap);
59
60void bheap_uncache_min(bheap_prio_t higher_prio, struct bheap* heap);
61int bheap_decrease(bheap_prio_t higher_prio, struct bheap_node* node);
62
63void bheap_delete(bheap_prio_t higher_prio,
64 struct bheap* heap,
65 struct bheap_node* node);
66
67/* allocate from memcache */
68struct bheap_node* bheap_node_alloc(int gfp_flags);
69void bheap_node_free(struct bheap_node* hn);
70
71/* allocate a heap node for value and insert into the heap */
72int bheap_add(bheap_prio_t higher_prio, struct bheap* heap,
73 void* value, int gfp_flags);
74
75void* bheap_take_del(bheap_prio_t higher_prio,
76 struct bheap* heap);
77#endif
diff --git a/include/litmus/edf_common.h b/include/litmus/edf_common.h
index 166cdac6bcab..80d4321cc87e 100644
--- a/include/litmus/edf_common.h
+++ b/include/litmus/edf_common.h
@@ -18,7 +18,7 @@ void edf_domain_init(rt_domain_t* rt, check_resched_needed_t resched,
18int edf_higher_prio(struct task_struct* first, 18int edf_higher_prio(struct task_struct* first,
19 struct task_struct* second); 19 struct task_struct* second);
20 20
21int edf_ready_order(struct heap_node* a, struct heap_node* b); 21int edf_ready_order(struct bheap_node* a, struct bheap_node* b);
22 22
23int edf_preemption_needed(rt_domain_t* rt, struct task_struct *t); 23int edf_preemption_needed(rt_domain_t* rt, struct task_struct *t);
24 24
diff --git a/include/litmus/heap.h b/include/litmus/heap.h
deleted file mode 100644
index da959b0bec9c..000000000000
--- a/include/litmus/heap.h
+++ /dev/null
@@ -1,77 +0,0 @@
1/* heaps.h -- Binomial Heaps
2 *
3 * (c) 2008, 2009 Bjoern Brandenburg
4 */
5
6#ifndef HEAP_H
7#define HEAP_H
8
9#define NOT_IN_HEAP UINT_MAX
10
11struct heap_node {
12 struct heap_node* parent;
13 struct heap_node* next;
14 struct heap_node* child;
15
16 unsigned int degree;
17 void* value;
18 struct heap_node** ref;
19};
20
21struct heap {
22 struct heap_node* head;
23 /* We cache the minimum of the heap.
24 * This speeds up repeated peek operations.
25 */
26 struct heap_node* min;
27};
28
29typedef int (*heap_prio_t)(struct heap_node* a, struct heap_node* b);
30
31void heap_init(struct heap* heap);
32void heap_node_init(struct heap_node** ref_to_heap_node_ptr, void* value);
33
34static inline int heap_node_in_heap(struct heap_node* h)
35{
36 return h->degree != NOT_IN_HEAP;
37}
38
39static inline int heap_empty(struct heap* heap)
40{
41 return heap->head == NULL && heap->min == NULL;
42}
43
44/* insert (and reinitialize) a node into the heap */
45void heap_insert(heap_prio_t higher_prio,
46 struct heap* heap,
47 struct heap_node* node);
48
49/* merge addition into target */
50void heap_union(heap_prio_t higher_prio,
51 struct heap* target,
52 struct heap* addition);
53
54struct heap_node* heap_peek(heap_prio_t higher_prio,
55 struct heap* heap);
56
57struct heap_node* heap_take(heap_prio_t higher_prio,
58 struct heap* heap);
59
60void heap_uncache_min(heap_prio_t higher_prio, struct heap* heap);
61int heap_decrease(heap_prio_t higher_prio, struct heap_node* node);
62
63void heap_delete(heap_prio_t higher_prio,
64 struct heap* heap,
65 struct heap_node* node);
66
67/* allocate from memcache */
68struct heap_node* heap_node_alloc(int gfp_flags);
69void heap_node_free(struct heap_node* hn);
70
71/* allocate a heap node for value and insert into the heap */
72int heap_add(heap_prio_t higher_prio, struct heap* heap,
73 void* value, int gfp_flags);
74
75void* heap_take_del(heap_prio_t higher_prio,
76 struct heap* heap);
77#endif
diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h
index 380fcb8acb33..a03580bc707c 100644
--- a/include/litmus/litmus.h
+++ b/include/litmus/litmus.h
@@ -133,7 +133,7 @@ void srp_ceiling_block(void);
133#define srp_ceiling_block() /* nothing */ 133#define srp_ceiling_block() /* nothing */
134#endif 134#endif
135 135
136#define heap2task(hn) ((struct task_struct*) hn->value) 136#define bheap2task(hn) ((struct task_struct*) hn->value)
137 137
138static inline int is_np(struct task_struct *t) 138static inline int is_np(struct task_struct *t)
139{ 139{
diff --git a/include/litmus/rt_domain.h b/include/litmus/rt_domain.h
index c7c55bef3e42..c780fdfcccae 100644
--- a/include/litmus/rt_domain.h
+++ b/include/litmus/rt_domain.h
@@ -5,14 +5,14 @@
5#ifndef __UNC_RT_DOMAIN_H__ 5#ifndef __UNC_RT_DOMAIN_H__
6#define __UNC_RT_DOMAIN_H__ 6#define __UNC_RT_DOMAIN_H__
7 7
8#include <litmus/heap.h> 8#include <litmus/bheap.h>
9 9
10#define RELEASE_QUEUE_SLOTS 127 /* prime */ 10#define RELEASE_QUEUE_SLOTS 127 /* prime */
11 11
12struct _rt_domain; 12struct _rt_domain;
13 13
14typedef int (*check_resched_needed_t)(struct _rt_domain *rt); 14typedef int (*check_resched_needed_t)(struct _rt_domain *rt);
15typedef void (*release_jobs_t)(struct _rt_domain *rt, struct heap* tasks); 15typedef void (*release_jobs_t)(struct _rt_domain *rt, struct bheap* tasks);
16 16
17struct release_queue { 17struct release_queue {
18 /* each slot maintains a list of release heaps sorted 18 /* each slot maintains a list of release heaps sorted
@@ -23,7 +23,7 @@ struct release_queue {
23typedef struct _rt_domain { 23typedef struct _rt_domain {
24 /* runnable rt tasks are in here */ 24 /* runnable rt tasks are in here */
25 spinlock_t ready_lock; 25 spinlock_t ready_lock;
26 struct heap ready_queue; 26 struct bheap ready_queue;
27 27
28 /* real-time tasks waiting for release are in here */ 28 /* real-time tasks waiting for release are in here */
29 spinlock_t release_lock; 29 spinlock_t release_lock;
@@ -41,7 +41,7 @@ typedef struct _rt_domain {
41 release_jobs_t release_jobs; 41 release_jobs_t release_jobs;
42 42
43 /* how are tasks ordered in the ready queue? */ 43 /* how are tasks ordered in the ready queue? */
44 heap_prio_t order; 44 bheap_prio_t order;
45} rt_domain_t; 45} rt_domain_t;
46 46
47struct release_heap { 47struct release_heap {
@@ -49,7 +49,7 @@ struct release_heap {
49 struct list_head list; 49 struct list_head list;
50 lt_t release_time; 50 lt_t release_time;
51 /* all tasks to be released at release_time */ 51 /* all tasks to be released at release_time */
52 struct heap heap; 52 struct bheap heap;
53 /* used to trigger the release */ 53 /* used to trigger the release */
54 struct hrtimer timer; 54 struct hrtimer timer;
55 /* used to delegate releases */ 55 /* used to delegate releases */
@@ -61,47 +61,47 @@ struct release_heap {
61 61
62static inline struct task_struct* __next_ready(rt_domain_t* rt) 62static inline struct task_struct* __next_ready(rt_domain_t* rt)
63{ 63{
64 struct heap_node *hn = heap_peek(rt->order, &rt->ready_queue); 64 struct bheap_node *hn = bheap_peek(rt->order, &rt->ready_queue);
65 if (hn) 65 if (hn)
66 return heap2task(hn); 66 return bheap2task(hn);
67 else 67 else
68 return NULL; 68 return NULL;
69} 69}
70 70
71void rt_domain_init(rt_domain_t *rt, heap_prio_t order, 71void rt_domain_init(rt_domain_t *rt, bheap_prio_t order,
72 check_resched_needed_t check, 72 check_resched_needed_t check,
73 release_jobs_t relase); 73 release_jobs_t relase);
74 74
75void __add_ready(rt_domain_t* rt, struct task_struct *new); 75void __add_ready(rt_domain_t* rt, struct task_struct *new);
76void __merge_ready(rt_domain_t* rt, struct heap *tasks); 76void __merge_ready(rt_domain_t* rt, struct bheap *tasks);
77void __add_release(rt_domain_t* rt, struct task_struct *task); 77void __add_release(rt_domain_t* rt, struct task_struct *task);
78 78
79static inline struct task_struct* __take_ready(rt_domain_t* rt) 79static inline struct task_struct* __take_ready(rt_domain_t* rt)
80{ 80{
81 struct heap_node* hn = heap_take(rt->order, &rt->ready_queue); 81 struct bheap_node* hn = bheap_take(rt->order, &rt->ready_queue);
82 if (hn) 82 if (hn)
83 return heap2task(hn); 83 return bheap2task(hn);
84 else 84 else
85 return NULL; 85 return NULL;
86} 86}
87 87
88static inline struct task_struct* __peek_ready(rt_domain_t* rt) 88static inline struct task_struct* __peek_ready(rt_domain_t* rt)
89{ 89{
90 struct heap_node* hn = heap_peek(rt->order, &rt->ready_queue); 90 struct bheap_node* hn = bheap_peek(rt->order, &rt->ready_queue);
91 if (hn) 91 if (hn)
92 return heap2task(hn); 92 return bheap2task(hn);
93 else 93 else
94 return NULL; 94 return NULL;
95} 95}
96 96
97static inline int is_queued(struct task_struct *t) 97static inline int is_queued(struct task_struct *t)
98{ 98{
99 return heap_node_in_heap(tsk_rt(t)->heap_node); 99 return bheap_node_in_heap(tsk_rt(t)->heap_node);
100} 100}
101 101
102static inline void remove(rt_domain_t* rt, struct task_struct *t) 102static inline void remove(rt_domain_t* rt, struct task_struct *t)
103{ 103{
104 heap_delete(rt->order, &rt->ready_queue, tsk_rt(t)->heap_node); 104 bheap_delete(rt->order, &rt->ready_queue, tsk_rt(t)->heap_node);
105} 105}
106 106
107static inline void add_ready(rt_domain_t* rt, struct task_struct *new) 107static inline void add_ready(rt_domain_t* rt, struct task_struct *new)
@@ -113,7 +113,7 @@ static inline void add_ready(rt_domain_t* rt, struct task_struct *new)
113 spin_unlock_irqrestore(&rt->ready_lock, flags); 113 spin_unlock_irqrestore(&rt->ready_lock, flags);
114} 114}
115 115
116static inline void merge_ready(rt_domain_t* rt, struct heap* tasks) 116static inline void merge_ready(rt_domain_t* rt, struct bheap* tasks)
117{ 117{
118 unsigned long flags; 118 unsigned long flags;
119 spin_lock_irqsave(&rt->ready_lock, flags); 119 spin_lock_irqsave(&rt->ready_lock, flags);
@@ -144,7 +144,7 @@ static inline void add_release(rt_domain_t* rt, struct task_struct *task)
144 144
145static inline int __jobs_pending(rt_domain_t* rt) 145static inline int __jobs_pending(rt_domain_t* rt)
146{ 146{
147 return !heap_empty(&rt->ready_queue); 147 return !bheap_empty(&rt->ready_queue);
148} 148}
149 149
150static inline int jobs_pending(rt_domain_t* rt) 150static inline int jobs_pending(rt_domain_t* rt)
@@ -153,7 +153,7 @@ static inline int jobs_pending(rt_domain_t* rt)
153 int ret; 153 int ret;
154 /* first we need the write lock for rt_ready_queue */ 154 /* first we need the write lock for rt_ready_queue */
155 spin_lock_irqsave(&rt->ready_lock, flags); 155 spin_lock_irqsave(&rt->ready_lock, flags);
156 ret = !heap_empty(&rt->ready_queue); 156 ret = !bheap_empty(&rt->ready_queue);
157 spin_unlock_irqrestore(&rt->ready_lock, flags); 157 spin_unlock_irqrestore(&rt->ready_lock, flags);
158 return ret; 158 return ret;
159} 159}
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index c599f848d1ed..e20427846273 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -39,7 +39,7 @@ struct rt_task {
39#ifdef __KERNEL__ 39#ifdef __KERNEL__
40 40
41struct _rt_domain; 41struct _rt_domain;
42struct heap_node; 42struct bheap_node;
43struct release_heap; 43struct release_heap;
44 44
45struct rt_job { 45struct rt_job {
@@ -157,7 +157,7 @@ struct rt_param {
157 * other than this pointer (which is updated by the heap 157 * other than this pointer (which is updated by the heap
158 * implementation). 158 * implementation).
159 */ 159 */
160 struct heap_node* heap_node; 160 struct bheap_node* heap_node;
161 struct release_heap* rel_heap; 161 struct release_heap* rel_heap;
162 162
163 /* Used by rt_domain to queue task in release list. 163 /* Used by rt_domain to queue task in release list.