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