src/xbt/heap.c

   1 /* a generic and efficient heap                                             */
   2
   3 /* Authors: Arnaud Legrand                                                  */
   4
   5 /* This program is free software; you can redistribute it and/or modify it
   6    under the terms of the license (GNU LGPL) which comes with this package. */
   7
   8 #include "xbt/sysdep.h"
   9 #include "xbt/error.h"
  10 #include "heap_private.h"
  11
  12 /**
  13  * xbt_heap_new:
  14  * @init_size: initial size of the heap
  15  * @free_func: function to call on each element when you want to free the whole heap (or NULL if nothing to do).
  16  *
  17  * Creates a new heap.
  18  */
  19 xbt_heap_t xbt_heap_new(int init_size, void_f_pvoid_t * const free_func)
  20 {
  21   xbt_heap_t H = xbt_new0(struct xbt_heap, 1);
  22   H->size = init_size;
  23   H->count = 0;
  24   H->items =
  25       (xbt_heapItem_t) xbt_new0(struct xbt_heapItem, init_size);
  26   H->free = free_func;
  27   return H;
  28 }
  29
  30 /**
  31  * xbt_heap_free:
  32  * @H: poor victim
  33  *
  34  * kilkil a heap and its content
  35  */
  36 void xbt_heap_free(xbt_heap_t H)
  37 {
  38   int i;
  39   if (H->free)
  40     for (i = 0; i < H->size; i++)
  41       H->free(H->items[i].content);
  42   xbt_free(H->items);
  43   xbt_free(H);
  44   return;
  45 }
  46
  47 /**
  48  * xbt_heap_push:
  49  * @H: the heap we're working on
  50  * @content: the object you want to add to the heap
  51  * @key: the key associated to this object
  52  *
  53  * Add an element int the heap. The element with the smallest key is
  54  * automatically moved at the top of the heap.
  55  */
  56 void xbt_heap_push(xbt_heap_t H, void *content, xbt_heap_float_t key)
  57 {
  58   int count = ++(H->count);
  59   int size = H->size;
  60   xbt_heapItem_t item;
  61   if (count > size) {
  62     H->size = 2 * size + 1;
  63     H->items =
  64         (void *) realloc(H->items,
  65                          (H->size) * sizeof(struct xbt_heapItem));
  66   }
  67   item = &(H->items[count - 1]);
  68   item->key = key;
  69   item->content = content;
  70   xbt_heap_increaseKey(H, count - 1);
  71   return;
  72 }
  73
  74 /**
  75  * xbt_heap_pop:
  76  * @H: the heap we're working on
  77  *
  78  * Extracts from the heap and returns the element with the smallest
  79  * key. The element with the next smallest key is automatically moved
  80  * at the top of the heap.
  81  */
  82 void *xbt_heap_pop(xbt_heap_t H)
  83 {
  84   void *max = CONTENT(H, 0);
  85   H->items[0] = H->items[(H->count) - 1];
  86   (H->count)--;
  87   xbt_heap_maxHeapify(H);
  88   if (H->count < H->size / 4 && H->size > 16) {
  89     H->size = H->size / 2 + 1;
  90     H->items =
  91         (void *) realloc(H->items,
  92                          (H->size) * sizeof(struct xbt_heapItem));
  93   }
  94   return max;
  95 }
  96
  97 /**
  98  * xbt_heap_maxkey:
  99  * @H: the heap we're working on
 100  *
 101  * Returns the smallest key in the heap without modifying the heap.
 102  */
 103 xbt_heap_float_t xbt_heap_maxkey(xbt_heap_t H)
 104 {
 105   return KEY(H, 0);
 106 }
 107
 108 /**
 109  * xbt_heap_maxcontent:
 110  * @H: the heap we're working on
 111  *
 112  * Returns the value associated to the smallest key in the heap
 113  * without modifying the heap.
 114  */
 115 void *xbt_heap_maxcontent(xbt_heap_t H)
 116 {
 117   return CONTENT(H, 0);
 118 }
 119
 120 /**
 121  * xbt_heap_maxcontent:
 122  * @H: the heap we're working on
 123  *
 124  * Restores the heap property once an element has been deleted.
 125  */
 126 static void xbt_heap_maxHeapify(xbt_heap_t H)
 127 {
 128   int i = 0;
 129   while (1) {
 130     int greatest = i;
 131     int l = LEFT(i);
 132     int r = RIGHT(i);
 133     int count = H->count;
 134     if (l < count && KEY(H, l) < KEY(H, i))
 135       greatest = l;
 136     if (r < count && KEY(H, r) < KEY(H, greatest))
 137       greatest = r;
 138     if (greatest != i) {
 139       struct xbt_heapItem tmp = H->items[i];
 140       H->items[i] = H->items[greatest];
 141       H->items[greatest] = tmp;
 142       i = greatest;
 143     } else
 144       return;
 145   }
 146 }
 147
 148 /**
 149  * xbt_heap_maxcontent:
 150  * @H: the heap we're working on
 151  * @i: an item position in the heap
 152  *
 153  * Moves up an item at position i to its correct position. Works only
 154  * when called from xbt_heap_push. Do not use otherwise.
 155  */
 156 static void xbt_heap_increaseKey(xbt_heap_t H, int i)
 157 {
 158   while (i > 0 && KEY(H, PARENT(i)) > KEY(H, i)) {
 159     struct xbt_heapItem tmp = H->items[i];
 160     H->items[i] = H->items[PARENT(i)];
 161     H->items[PARENT(i)] = tmp;
 162     i = PARENT(i);
 163   }
 164   return;
 165 }