run_heap.c

国内一位牛人自己开发的操作系统

#include"kernel.h"

#define RUN_HEAP_EXCHANGE(s_h,d_h)			\
{							\
	int s_t,d_t;					\
	s_t=os->thread_heap.run_heap[s_h].thread;	\
	d_t=os->thread_heap.run_heap[d_h].thread;	\
							\
	os->thread_heap.run_heap[s_h].thread=d_t;	\
	os->thread_heap.run_heap[d_h].thread=s_t;	\
	os->thread[s_t].heap=d_h;			\
	os->thread[d_t].heap=s_h;			\
}

void run_heap_up_deal(int thread_id)
{
	int h,t,p,h_p,t_p,p_p;
	t=thread_id;
	h=os->thread[t].heap;
	p=os->thread[t].priority;
	for(;;){
		if(h<=0)
			break;
		h_p=(h-1)/2;
		t_p=os->thread_heap.run_heap[h_p].thread;
		p_p=os->thread[t_p].priority;
		if(p<=p_p)
			break;
		RUN_HEAP_EXCHANGE(h,h_p);
		h=h_p;
	}
	return;
}

void run_heap_down_deal(int thread_id)
{
	int h1,h2,t1,t2,p1,p2;
	
	t1=thread_id;
	h1=os->thread[t1].heap;
	p1=os->thread[t1].priority;

	for(;;){
		int h_l,h_r;
		h_l=2*h1+1;h_r=2*h1+2;
		if(h_l>=os->thread_heap.run_thread_number)
			if(h_r>=os->thread_heap.run_thread_number)
				break;
			else
				h2=h_r;
		else
			if(h_r>=os->thread_heap.run_thread_number)
				h2=h_l;
			else{
				int t_l,t_r,p_l,p_r;
				t_l=os->thread_heap.run_heap[h_l].thread;
				p_l=os->thread[t_l].priority;
				t_r=os->thread_heap.run_heap[h_r].thread;
				p_r=os->thread[t_r].priority;
				if(p_l>p_r)
					h2=h_l;
				else
					h2=h_r;
			}
		t2=os->thread_heap.run_heap[h2].thread;
		p2=os->thread[t2].priority;
		if(p1>=p2)
			break;
		RUN_HEAP_EXCHANGE(h1,h2);
		h1=h2;
	}
	return;
}

void remove_from_run_heap(int thread_id)
{
	int h1,h2,t1,t2,p1,p2;

	h1=os->thread[thread_id].heap;
	h2=os->thread_heap.run_thread_number-1;
	RUN_HEAP_EXCHANGE(h1,h2);

	t1=os->thread_heap.run_heap[h1].thread;
	p1=os->thread[t1].priority;

	t2=os->thread_heap.run_heap[h2].thread;
	p2=os->thread[t2].priority;
	os->thread_heap.run_thread_number--;

	if(p1==p2)
		return;
	if(p1>p2)
		run_heap_up_deal(t1);
	else
		run_heap_down_deal(t1);
	return;
}

void insert_into_run_heap(int thread_id)
{
	int h,t;

	t=thread_id;
	h=os->thread_heap.run_thread_number;

	os->thread[t].heap=h;
	os->thread_heap.run_heap[h].thread=t;
	os->thread_heap.run_thread_number++;
	run_heap_up_deal(t);
	return;
}