Merge branch 'charm' of charmgit:charm into charm
[charm.git] / src / conv-ldb / priorityqueue.c
1 /*priority queue, using a binary heap with static maximum size
2 This code is in the public domain, but I would be glad if you leave my name in:
3 Rene Wiermer, rwiermer@googlemail.com. Feedback is welcome.
4
5 The implemementation is based on Heapsort as described in
6 "Introduction to Algorithms" (Cormen, Leiserson, Rivest, 24. printing)
7 */
8
9 /*needed for test only*/
10 #include <stdio.h>
11 /**/
12
13 #define MAX_SIZE 100000
14 typedef struct priormsg_s {
15     unsigned int priority;
16     int     pe;
17     void* msg;
18 } priormsg;
19
20
21 typedef struct {
22     priormsg* msgs[MAX_SIZE];
23     unsigned int size;
24 } MsgHeap;
25
26
27 void heap_init(MsgHeap* h) {
28     h->size=0;
29 }
30
31 int heap_size(MsgHeap* h)
32 {
33     return h->size;
34 }
35 void heap_heapify(MsgHeap* h,int i) {
36     int l,r,smallest;
37     priormsg* tmp;
38     l=2*i; /*left child*/
39     r=2*i+1; /*right child*/
40
41     if ((l < h->size)&&(h->msgs[l]->priority < h->msgs[i]->priority))
42         smallest=l;
43     else 
44         smallest=i;
45     if ((r < h->size)&&(h->msgs[r]->priority < h->msgs[smallest]->priority))
46         smallest=r;
47     if (smallest!=i) {
48         /*exchange to maintain heap property*/
49         tmp=h->msgs[smallest];
50         h->msgs[smallest]=h->msgs[i];
51         h->msgs[i]=tmp;
52         heap_heapify(h,smallest);
53     }
54 }
55
56 void heap_addItem(MsgHeap* h, priormsg* packet) {
57     unsigned int i,parent;  
58     h->size=h->size+1;
59     i=h->size-1;
60     parent=i/2;
61     /*find the correct place to insert*/
62     while ((i > 0)&&(h->msgs[parent]->priority > packet->priority)) {
63         h->msgs[i]=h->msgs[parent];
64         i=parent;
65         parent=i/2;
66     }
67     h->msgs[i]=packet;
68 }
69
70 priormsg* heap_extractMin(MsgHeap* h) {
71     priormsg* max;
72     if (heap_isEmpty(h))
73         return 0;
74     max=h->msgs[0];
75     h->msgs[0]=h->msgs[h->size-1];
76     h->size=h->size-1;
77     heap_heapify(h,0);
78     return max;
79 }
80
81 int heap_isEmpty(MsgHeap *h) {
82     return h->size==0;
83 }
84
85 int heap_isFull(MsgHeap *h) {
86     return h->size>=MAX_SIZE;
87 }
88