00001 /*priority queue, using a binary heap with static maximum size 00002 This code is in the public domain, but I would be glad if you leave my name in: 00003 Rene Wiermer, rwiermer@googlemail.com. Feedback is welcome. 00004 00005 The implemementation is based on Heapsort as described in 00006 "Introduction to Algorithms" (Cormen, Leiserson, Rivest, 24. printing) 00007 */ 00008 00009 /*needed for test only*/ 00010 #include <stdio.h> 00011 00012 00013 #define MAX_SIZE 100000 00014 typedef struct priormsg_s { 00015 unsigned int priority; 00016 int pe; 00017 int load; 00018 void* msg; 00019 } priormsg; 00020 00021 00022 typedef struct { 00023 priormsg* msgs[MAX_SIZE]; 00024 unsigned int size; 00025 } MsgHeap; 00026 00027 00028 void heap_init(MsgHeap* h) { 00029 h->size=0; 00030 } 00031 00032 int heap_size(MsgHeap* h) 00033 { 00034 return h->size; 00035 } 00036 void heap_heapify(MsgHeap* h,int i) { 00037 int l,r,smallest; 00038 priormsg* tmp; 00039 l=2*i; /*left child*/ 00040 r=2*i+1; /*right child*/ 00041 00042 if ((l < h->size)&&(h->msgs[l]->priority < h->msgs[i]->priority)) 00043 smallest=l; 00044 else 00045 smallest=i; 00046 if ((r < h->size)&&(h->msgs[r]->priority < h->msgs[smallest]->priority)) 00047 smallest=r; 00048 if (smallest!=i) { 00049 /*exchange to maintain heap property*/ 00050 tmp=h->msgs[smallest]; 00051 h->msgs[smallest]=h->msgs[i]; 00052 h->msgs[i]=tmp; 00053 heap_heapify(h,smallest); 00054 } 00055 } 00056 00057 void heap_addItem(MsgHeap* h, priormsg* packet) { 00058 unsigned int i,parent; 00059 h->size=h->size+1; 00060 i=h->size-1; 00061 parent=i/2; 00062 /*find the correct place to insert*/ 00063 while ((i > 0)&&(h->msgs[parent]->priority > packet->priority)) { 00064 h->msgs[i]=h->msgs[parent]; 00065 i=parent; 00066 parent=i/2; 00067 } 00068 h->msgs[i]=packet; 00069 } 00070 00071 int heap_isEmpty(MsgHeap *h) { 00072 return h->size==0; 00073 } 00074 00075 priormsg* heap_extractMin(MsgHeap* h) { 00076 priormsg* max; 00077 if (heap_isEmpty(h)) 00078 return 0; 00079 max=h->msgs[0]; 00080 h->msgs[0]=h->msgs[h->size-1]; 00081 h->size=h->size-1; 00082 heap_heapify(h,0); 00083 return max; 00084 } 00085 00086 int heap_isFull(MsgHeap *h) { 00087 return h->size>=MAX_SIZE; 00088 } 00089
1.5.5