use CldCountTokens instead of CldLoad() to estimate the current load. CldLoad() has...
[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     int     load;
18     void* msg;
19 } priormsg;
20
21
22 typedef struct {
23     priormsg* msgs[MAX_SIZE];
24     unsigned int size;
25 } MsgHeap;
26
27
28 void heap_init(MsgHeap* h) {
29     h->size=0;
30 }
31
32 int heap_size(MsgHeap* h)
33 {
34     return h->size;
35 }
36 void heap_heapify(MsgHeap* h,int i) {
37     int l,r,smallest;
38     priormsg* tmp;
39     l=2*i; /*left child*/
40     r=2*i+1; /*right child*/
41
42     if ((l < h->size)&&(h->msgs[l]->priority < h->msgs[i]->priority))
43         smallest=l;
44     else 
45         smallest=i;
46     if ((r < h->size)&&(h->msgs[r]->priority < h->msgs[smallest]->priority))
47         smallest=r;
48     if (smallest!=i) {
49         /*exchange to maintain heap property*/
50         tmp=h->msgs[smallest];
51         h->msgs[smallest]=h->msgs[i];
52         h->msgs[i]=tmp;
53         heap_heapify(h,smallest);
54     }
55 }
56
57 void heap_addItem(MsgHeap* h, priormsg* packet) {
58     unsigned int i,parent;  
59     h->size=h->size+1;
60     i=h->size-1;
61     parent=i/2;
62     /*find the correct place to insert*/
63     while ((i > 0)&&(h->msgs[parent]->priority > packet->priority)) {
64         h->msgs[i]=h->msgs[parent];
65         i=parent;
66         parent=i/2;
67     }
68     h->msgs[i]=packet;
69 }
70
71 priormsg* heap_extractMin(MsgHeap* h) {
72     priormsg* max;
73     if (heap_isEmpty(h))
74         return 0;
75     max=h->msgs[0];
76     h->msgs[0]=h->msgs[h->size-1];
77     h->size=h->size-1;
78     heap_heapify(h,0);
79     return max;
80 }
81
82 int heap_isEmpty(MsgHeap *h) {
83     return h->size==0;
84 }
85
86 int heap_isFull(MsgHeap *h) {
87     return h->size>=MAX_SIZE;
88 }
89