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