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