nsz Git - libfirm/blob - ir/adt/pqueue.c

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @author  Christian Wuerdig, Matthias Braun
   9  * @brief   Priority Queue implementation based on the heap datastructure
  10  */
  11 #include "config.h"
  12
  13 #include "array.h"
  14 #include "pqueue.h"
  15 #include "error.h"
  16
  17 /*
  18  * Implements a heap.
  19  *
  20  * Implementation note: It might seem strange that we start indexing at 0
  21  * but use 2*i and 2*i+1 to find the left and right sucessor of an index.
  22  * The trick is that for index 0 the left successor is 0 again, and the
  23  * right successor is 1 in this scheme. For the right successor 1 everything
  24  * works like usual. We simply took care in the algorithms that they still
  25  * work with the left child of 0 being 0 again. This was possible without
  26  * any extra ifs or arithmetic.
  27  * Thus we can save the wastage of 1 array position you can see in other
  28  * implementations or the ugly (i+1)*2 - 1 and (i+1)*2 for calculating the
  29  * left and right child. (At the expense that stuff easily breaks when you make
  30  * changes and don't think that the left child of 0 is 0 :-/)
  31  *
  32  */
  33
  34 typedef struct pqueue_el_t {
  35         void *data;
  36         int  priority;
  37 } pqueue_el_t;
  38
  39 struct pqueue_t {
  40         pqueue_el_t *elems;
  41 };
  42
  43 /**
  44  * Enforces the heap characteristics if the queue
  45  * starting from element at position @p pos.
  46  */
  47 static void pqueue_heapify(pqueue_t *q, size_t pos)
  48 {
  49         size_t len = ARR_LEN(q->elems);
  50
  51         while (pos * 2 < len) {
  52                 pqueue_el_t tmp;
  53                 size_t      exchange = pos;
  54
  55                 if (q->elems[exchange].priority < q->elems[pos * 2].priority) {
  56                         exchange = pos * 2;
  57                 }
  58
  59                 if ((pos * 2 + 1) < len
  60                                 && q->elems[exchange].priority < q->elems[pos * 2 + 1].priority) {
  61                         exchange = pos * 2 + 1;
  62                 }
  63
  64                 if (exchange == pos)
  65                         break;
  66
  67                 tmp                = q->elems[pos];
  68                 q->elems[pos]      = q->elems[exchange];
  69                 q->elems[exchange] = tmp;
  70
  71                 pos = exchange;
  72         }
  73 }
  74
  75 /**
  76  * Sifts up a newly inserted element at position @p pos.
  77  */
  78 static void pqueue_sift_up(pqueue_t *q, size_t pos)
  79 {
  80         while (q->elems[pos].priority > q->elems[pos / 2].priority) {
  81                 pqueue_el_t tmp;
  82
  83                 tmp               = q->elems[pos];
  84                 q->elems[pos]     = q->elems[pos / 2];
  85                 q->elems[pos / 2] = tmp;
  86
  87                 pos /= 2;
  88         }
  89 }
  90
  91 pqueue_t *new_pqueue(void)
  92 {
  93         pqueue_t *res = XMALLOC(pqueue_t);
  94         res->elems = NEW_ARR_F(pqueue_el_t, 0);
  95         return res;
  96 }
  97
  98 void del_pqueue(pqueue_t *q)
  99 {
 100         DEL_ARR_F(q->elems);
 101         free(q);
 102 }
 103
 104 void pqueue_put(pqueue_t *q, void *data, int priority)
 105 {
 106         pqueue_el_t el;
 107
 108         el.data     = data;
 109         el.priority = priority;
 110
 111         ARR_APP1(pqueue_el_t, q->elems, el);
 112
 113         pqueue_sift_up(q, ARR_LEN(q->elems) - 1);
 114 }
 115
 116 void *pqueue_pop_front(pqueue_t *q)
 117 {
 118         switch (ARR_LEN(q->elems)) {
 119                 case 0:
 120                         panic("Attempt to retrieve element from empty priority queue.");
 121                 case 1:
 122                         ARR_SHRINKLEN(q->elems, 0);
 123                         return q->elems[0].data;
 124                 default: {
 125                         void   *data = q->elems[0].data;
 126                         size_t len   = ARR_LEN(q->elems) - 1;
 127
 128                         q->elems[0] = q->elems[len];
 129                         ARR_SHRINKLEN(q->elems, len);
 130                         pqueue_heapify(q, 0);
 131
 132                         return data;
 133                 }
 134         }
 135 }
 136
 137 size_t pqueue_length(const pqueue_t *q)
 138 {
 139         return ARR_LEN(q->elems);
 140 }
 141
 142 int pqueue_empty(const pqueue_t *q)
 143 {
 144         return ARR_LEN(q->elems) == 0;
 145 }