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