From ee09f78d8faa0b988088d93142e6f5f8a6e75394 Mon Sep 17 00:00:00 2001 From: Andrea Bastoni Date: Mon, 21 Dec 2009 12:23:57 -0500 Subject: 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" --- include/litmus/bheap.h | 77 +++++++++++++++++++++++++++++++++++++++++++++ include/litmus/edf_common.h | 2 +- include/litmus/heap.h | 77 --------------------------------------------- include/litmus/litmus.h | 2 +- include/litmus/rt_domain.h | 36 ++++++++++----------- include/litmus/rt_param.h | 4 +-- 6 files changed, 99 insertions(+), 99 deletions(-) create mode 100644 include/litmus/bheap.h delete mode 100644 include/litmus/heap.h (limited to 'include') 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 @@ +/* bheaps.h -- Binomial Heaps + * + * (c) 2008, 2009 Bjoern Brandenburg + */ + +#ifndef BHEAP_H +#define BHEAP_H + +#define NOT_IN_HEAP UINT_MAX + +struct bheap_node { + struct bheap_node* parent; + struct bheap_node* next; + struct bheap_node* child; + + unsigned int degree; + void* value; + struct bheap_node** ref; +}; + +struct bheap { + struct bheap_node* head; + /* We cache the minimum of the heap. + * This speeds up repeated peek operations. + */ + struct bheap_node* min; +}; + +typedef int (*bheap_prio_t)(struct bheap_node* a, struct bheap_node* b); + +void bheap_init(struct bheap* heap); +void bheap_node_init(struct bheap_node** ref_to_bheap_node_ptr, void* value); + +static inline int bheap_node_in_heap(struct bheap_node* h) +{ + return h->degree != NOT_IN_HEAP; +} + +static inline int bheap_empty(struct bheap* heap) +{ + return heap->head == NULL && heap->min == NULL; +} + +/* insert (and reinitialize) a node into the heap */ +void bheap_insert(bheap_prio_t higher_prio, + struct bheap* heap, + struct bheap_node* node); + +/* merge addition into target */ +void bheap_union(bheap_prio_t higher_prio, + struct bheap* target, + struct bheap* addition); + +struct bheap_node* bheap_peek(bheap_prio_t higher_prio, + struct bheap* heap); + +struct bheap_node* bheap_take(bheap_prio_t higher_prio, + struct bheap* heap); + +void bheap_uncache_min(bheap_prio_t higher_prio, struct bheap* heap); +int bheap_decrease(bheap_prio_t higher_prio, struct bheap_node* node); + +void bheap_delete(bheap_prio_t higher_prio, + struct bheap* heap, + struct bheap_node* node); + +/* allocate from memcache */ +struct bheap_node* bheap_node_alloc(int gfp_flags); +void bheap_node_free(struct bheap_node* hn); + +/* allocate a heap node for value and insert into the heap */ +int bheap_add(bheap_prio_t higher_prio, struct bheap* heap, + void* value, int gfp_flags); + +void* bheap_take_del(bheap_prio_t higher_prio, + struct bheap* heap); +#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, int edf_higher_prio(struct task_struct* first, struct task_struct* second); -int edf_ready_order(struct heap_node* a, struct heap_node* b); +int edf_ready_order(struct bheap_node* a, struct bheap_node* b); int edf_preemption_needed(rt_domain_t* rt, struct task_struct *t); 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 @@ -/* heaps.h -- Binomial Heaps - * - * (c) 2008, 2009 Bjoern Brandenburg - */ - -#ifndef HEAP_H -#define HEAP_H - -#define NOT_IN_HEAP UINT_MAX - -struct heap_node { - struct heap_node* parent; - struct heap_node* next; - struct heap_node* child; - - unsigned int degree; - void* value; - struct heap_node** ref; -}; - -struct heap { - struct heap_node* head; - /* We cache the minimum of the heap. - * This speeds up repeated peek operations. - */ - struct heap_node* min; -}; - -typedef int (*heap_prio_t)(struct heap_node* a, struct heap_node* b); - -void heap_init(struct heap* heap); -void heap_node_init(struct heap_node** ref_to_heap_node_ptr, void* value); - -static inline int heap_node_in_heap(struct heap_node* h) -{ - return h->degree != NOT_IN_HEAP; -} - -static inline int heap_empty(struct heap* heap) -{ - return heap->head == NULL && heap->min == NULL; -} - -/* insert (and reinitialize) a node into the heap */ -void heap_insert(heap_prio_t higher_prio, - struct heap* heap, - struct heap_node* node); - -/* merge addition into target */ -void heap_union(heap_prio_t higher_prio, - struct heap* target, - struct heap* addition); - -struct heap_node* heap_peek(heap_prio_t higher_prio, - struct heap* heap); - -struct heap_node* heap_take(heap_prio_t higher_prio, - struct heap* heap); - -void heap_uncache_min(heap_prio_t higher_prio, struct heap* heap); -int heap_decrease(heap_prio_t higher_prio, struct heap_node* node); - -void heap_delete(heap_prio_t higher_prio, - struct heap* heap, - struct heap_node* node); - -/* allocate from memcache */ -struct heap_node* heap_node_alloc(int gfp_flags); -void heap_node_free(struct heap_node* hn); - -/* allocate a heap node for value and insert into the heap */ -int heap_add(heap_prio_t higher_prio, struct heap* heap, - void* value, int gfp_flags); - -void* heap_take_del(heap_prio_t higher_prio, - struct heap* heap); -#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); #define srp_ceiling_block() /* nothing */ #endif -#define heap2task(hn) ((struct task_struct*) hn->value) +#define bheap2task(hn) ((struct task_struct*) hn->value) static inline int is_np(struct task_struct *t) { 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 @@ #ifndef __UNC_RT_DOMAIN_H__ #define __UNC_RT_DOMAIN_H__ -#include +#include #define RELEASE_QUEUE_SLOTS 127 /* prime */ struct _rt_domain; typedef int (*check_resched_needed_t)(struct _rt_domain *rt); -typedef void (*release_jobs_t)(struct _rt_domain *rt, struct heap* tasks); +typedef void (*release_jobs_t)(struct _rt_domain *rt, struct bheap* tasks); struct release_queue { /* each slot maintains a list of release heaps sorted @@ -23,7 +23,7 @@ struct release_queue { typedef struct _rt_domain { /* runnable rt tasks are in here */ spinlock_t ready_lock; - struct heap ready_queue; + struct bheap ready_queue; /* real-time tasks waiting for release are in here */ spinlock_t release_lock; @@ -41,7 +41,7 @@ typedef struct _rt_domain { release_jobs_t release_jobs; /* how are tasks ordered in the ready queue? */ - heap_prio_t order; + bheap_prio_t order; } rt_domain_t; struct release_heap { @@ -49,7 +49,7 @@ struct release_heap { struct list_head list; lt_t release_time; /* all tasks to be released at release_time */ - struct heap heap; + struct bheap heap; /* used to trigger the release */ struct hrtimer timer; /* used to delegate releases */ @@ -61,47 +61,47 @@ struct release_heap { static inline struct task_struct* __next_ready(rt_domain_t* rt) { - struct heap_node *hn = heap_peek(rt->order, &rt->ready_queue); + struct bheap_node *hn = bheap_peek(rt->order, &rt->ready_queue); if (hn) - return heap2task(hn); + return bheap2task(hn); else return NULL; } -void rt_domain_init(rt_domain_t *rt, heap_prio_t order, +void rt_domain_init(rt_domain_t *rt, bheap_prio_t order, check_resched_needed_t check, release_jobs_t relase); void __add_ready(rt_domain_t* rt, struct task_struct *new); -void __merge_ready(rt_domain_t* rt, struct heap *tasks); +void __merge_ready(rt_domain_t* rt, struct bheap *tasks); void __add_release(rt_domain_t* rt, struct task_struct *task); static inline struct task_struct* __take_ready(rt_domain_t* rt) { - struct heap_node* hn = heap_take(rt->order, &rt->ready_queue); + struct bheap_node* hn = bheap_take(rt->order, &rt->ready_queue); if (hn) - return heap2task(hn); + return bheap2task(hn); else return NULL; } static inline struct task_struct* __peek_ready(rt_domain_t* rt) { - struct heap_node* hn = heap_peek(rt->order, &rt->ready_queue); + struct bheap_node* hn = bheap_peek(rt->order, &rt->ready_queue); if (hn) - return heap2task(hn); + return bheap2task(hn); else return NULL; } static inline int is_queued(struct task_struct *t) { - return heap_node_in_heap(tsk_rt(t)->heap_node); + return bheap_node_in_heap(tsk_rt(t)->heap_node); } static inline void remove(rt_domain_t* rt, struct task_struct *t) { - heap_delete(rt->order, &rt->ready_queue, tsk_rt(t)->heap_node); + bheap_delete(rt->order, &rt->ready_queue, tsk_rt(t)->heap_node); } static 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) spin_unlock_irqrestore(&rt->ready_lock, flags); } -static inline void merge_ready(rt_domain_t* rt, struct heap* tasks) +static inline void merge_ready(rt_domain_t* rt, struct bheap* tasks) { unsigned long flags; spin_lock_irqsave(&rt->ready_lock, flags); @@ -144,7 +144,7 @@ static inline void add_release(rt_domain_t* rt, struct task_struct *task) static inline int __jobs_pending(rt_domain_t* rt) { - return !heap_empty(&rt->ready_queue); + return !bheap_empty(&rt->ready_queue); } static inline int jobs_pending(rt_domain_t* rt) @@ -153,7 +153,7 @@ static inline int jobs_pending(rt_domain_t* rt) int ret; /* first we need the write lock for rt_ready_queue */ spin_lock_irqsave(&rt->ready_lock, flags); - ret = !heap_empty(&rt->ready_queue); + ret = !bheap_empty(&rt->ready_queue); spin_unlock_irqrestore(&rt->ready_lock, flags); return ret; } 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 { #ifdef __KERNEL__ struct _rt_domain; -struct heap_node; +struct bheap_node; struct release_heap; struct rt_job { @@ -157,7 +157,7 @@ struct rt_param { * other than this pointer (which is updated by the heap * implementation). */ - struct heap_node* heap_node; + struct bheap_node* heap_node; struct release_heap* rel_heap; /* Used by rt_domain to queue task in release list. -- cgit v1.2.2