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 = (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->count; 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_size:
  48  * @H: the heap we're working on
  49  *
  50  * returns the number of elements in the heap
  51  */
  52 int xbt_heap_size(xbt_heap_t H)
  53 {
  54   return (H->count);
  55 }
  56
  57 /**
  58  * xbt_heap_push:
  59  * @H: the heap we're working on
  60  * @content: the object you want to add to the heap
  61  * @key: the key associated to this object
  62  *
  63  * Add an element int the heap. The element with the smallest key is
  64  * automatically moved at the top of the heap.
  65  */
  66 void xbt_heap_push(xbt_heap_t H, void *content, xbt_heap_float_t key)
  67 {
  68   int count = ++(H->count);
  69   int size = H->size;
  70   xbt_heapItem_t item;
  71   if (count > size) {
  72     H->size = 2 * size + 1;
  73     H->items =
  74         (void *) realloc(H->items,
  75                          (H->size) * sizeof(struct xbt_heapItem));
  76   }
  77   item = &(H->items[count - 1]);
  78   item->key = key;
  79   item->content = content;
  80   xbt_heap_increaseKey(H, count - 1);
  81   return;
  82 }
  83
  84 /**
  85  * xbt_heap_pop:
  86  * @H: the heap we're working on
  87  *
  88  * Extracts from the heap and returns the element with the smallest
  89  * key. The element with the next smallest key is automatically moved
  90  * at the top of the heap.
  91  */
  92 void *xbt_heap_pop(xbt_heap_t H)
  93 {
  94   void *max ;
  95
  96   if(H->count==0) return NULL;
  97
  98   max = CONTENT(H, 0);
  99
 100   H->items[0] = H->items[(H->count) - 1];
 101   (H->count)--;
 102   xbt_heap_maxHeapify(H);
 103   if (H->count < H->size / 4 && H->size > 16) {
 104     H->size = H->size / 2 + 1;
 105     H->items =
 106         (void *) realloc(H->items,
 107                          (H->size) * sizeof(struct xbt_heapItem));
 108   }
 109   return max;
 110 }
 111
 112 /**
 113  * xbt_heap_maxkey:
 114  * @H: the heap we're working on
 115  *
 116  * Returns the smallest key in the heap without modifying the heap.
 117  */
 118 xbt_heap_float_t xbt_heap_maxkey(xbt_heap_t H)
 119 {
 120   if(H->count==0) abort();
 121   return KEY(H, 0);
 122 }
 123
 124 /**
 125  * xbt_heap_maxcontent:
 126  * @H: the heap we're working on
 127  *
 128  * Returns the value associated to the smallest key in the heap
 129  * without modifying the heap.
 130  */
 131 void *xbt_heap_maxcontent(xbt_heap_t H)
 132 {
 133   if(H->count==0) abort();
 134   return CONTENT(H, 0);
 135 }
 136
 137 /**
 138  * xbt_heap_maxcontent:
 139  * @H: the heap we're working on
 140  *
 141  * Restores the heap property once an element has been deleted.
 142  */
 143 static void xbt_heap_maxHeapify(xbt_heap_t H)
 144 {
 145   int i = 0;
 146   while (1) {
 147     int greatest = i;
 148     int l = LEFT(i);
 149     int r = RIGHT(i);
 150     int count = H->count;
 151     if (l < count && KEY(H, l) < KEY(H, i))
 152       greatest = l;
 153     if (r < count && KEY(H, r) < KEY(H, greatest))
 154       greatest = r;
 155     if (greatest != i) {
 156       struct xbt_heapItem tmp = H->items[i];
 157       H->items[i] = H->items[greatest];
 158       H->items[greatest] = tmp;
 159       i = greatest;
 160     } else
 161       return;
 162   }
 163 }
 164
 165 /**
 166  * xbt_heap_maxcontent:
 167  * @H: the heap we're working on
 168  * @i: an item position in the heap
 169  *
 170  * Moves up an item at position i to its correct position. Works only
 171  * when called from xbt_heap_push. Do not use otherwise.
 172  */
 173 static void xbt_heap_increaseKey(xbt_heap_t H, int i)
 174 {
 175   while (i > 0 && KEY(H, PARENT(i)) > KEY(H, i)) {
 176     struct xbt_heapItem tmp = H->items[i];
 177     H->items[i] = H->items[PARENT(i)];
 178     H->items[PARENT(i)] = tmp;
 179     i = PARENT(i);
 180   }
 181   return;
 182 }