src/xbt/heap.c

   1 /* a generic and efficient heap                                             */
   2
   3 /* Copyright (c) 2004, 2005, 2007, 2008, 2009, 2010. The SimGrid Team.
   4  * All rights reserved.                                                     */
   5
   6 /* This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the license (GNU LGPL) which comes with this package. */
   8
   9 #include "xbt/sysdep.h"
  10 #include "xbt/log.h"
  11 #include "heap_private.h"
  12
  13 #include <stdio.h>
  14
  15
  16 /** @addtogroup XBT_heap
  17  *  \brief This section describes the API to generic heap with O(log(n)) access.
  18  */
  19
  20 /**
  21  * @brief Creates a new heap.
  22  * \param init_size initial size of the heap
  23  * \param free_func function to call on each element when you want to free
  24  *             the whole heap (or NULL if nothing to do).
  25  *
  26  * Creates a new heap.
  27  */
  28 XBT_INLINE xbt_heap_t xbt_heap_new(int init_size,
  29                                    void_f_pvoid_t const free_func)
  30 {
  31   xbt_heap_t H = xbt_new0(struct xbt_heap, 1);
  32   H->size = init_size;
  33   H->count = 0;
  34   H->items = (xbt_heapItem_t) xbt_new0(struct xbt_heapItem, init_size);
  35   H->free = free_func;
  36   return H;
  37 }
  38
  39 /**
  40  * @brief Set the update callback function.
  41  * @param H the heap we're working on
  42  * \param update_callback function to call on each element to update its index when needed.
  43  */
  44 XBT_INLINE void xbt_heap_set_update_callback(xbt_heap_t H,
  45                                              void (*update_callback) (void
  46                                                                       *,
  47                                                                       int))
  48 {
  49   H->update_callback = update_callback;
  50 }
  51
  52
  53 /**
  54  * @brief kilkil a heap and its content
  55  * @param H poor victim
  56  */
  57 void xbt_heap_free(xbt_heap_t H)
  58 {
  59   int i;
  60   if (H->free)
  61     for (i = 0; i < H->count; i++)
  62       (*(H->free)) (H->items[i].content);
  63   free(H->items);
  64   free(H);
  65   return;
  66 }
  67
  68 /**
  69  * @brief returns the number of elements in the heap
  70  * @param H the heap we're working on
  71  * @return the number of elements in the heap
  72  */
  73 XBT_INLINE int xbt_heap_size(xbt_heap_t H)
  74 {
  75   return (H->count);
  76 }
  77
  78 /**
  79  * @brief Add an element into the heap.
  80  * \param H the heap we're working on
  81  * \param content the object you want to add to the heap
  82  * \param key the key associated to this object
  83  *
  84  * The element with the smallest key is automatically moved at the top of the heap.
  85  */
  86 void xbt_heap_push(xbt_heap_t H, void *content, double key)
  87 {
  88   int count = ++(H->count);
  89
  90   int size = H->size;
  91   xbt_heapItem_t item;
  92
  93   if (count > size) {
  94     H->size = 2 * size + 1;
  95     H->items =
  96         (void *) realloc(H->items,
  97                          (H->size) * sizeof(struct xbt_heapItem));
  98   }
  99
 100   item = &(H->items[count - 1]);
 101   item->key = key;
 102   item->content = content;
 103   xbt_heap_increaseKey(H, count - 1);
 104   return;
 105 }
 106
 107 /**
 108  * @brief Extracts from the heap and returns the element with the smallest key.
 109  * \param H the heap we're working on
 110  * \return the element with the smallest key
 111  *
 112  * Extracts from the heap and returns the element with the smallest
 113  * key. The element with the next smallest key is automatically moved
 114  * at the top of the heap.
 115  */
 116 void *xbt_heap_pop(xbt_heap_t H)
 117 {
 118   void *max;
 119
 120   if (H->count == 0)
 121     return NULL;
 122
 123   max = CONTENT(H, 0);
 124
 125   H->items[0] = H->items[(H->count) - 1];
 126   (H->count)--;
 127   xbt_heap_maxHeapify(H);
 128   if (H->count < H->size / 4 && H->size > 16) {
 129     H->size = H->size / 2 + 1;
 130     H->items =
 131         (void *) realloc(H->items,
 132                          (H->size) * sizeof(struct xbt_heapItem));
 133   }
 134
 135   if (H->update_callback)
 136     H->update_callback(max, -1);
 137   return max;
 138 }
 139
 140 /**
 141  * @brief Extracts from the heap and returns the element at position i.
 142  * \param H the heap we're working on
 143  * \param i     element position
 144  * \return the element at position i if ok, NULL otherwise
 145  *
 146  * Extracts from the heap and returns the element at position i. The head is automatically reorded.
 147  */
 148 void *xbt_heap_remove(xbt_heap_t H, int i)
 149 {
 150   if ((i < 0) || (i > H->count - 1))
 151     return NULL;
 152   /* put element i at head */
 153   if (i > 0) {
 154     KEY(H, i) = MIN_KEY_VALUE;
 155     xbt_heap_increaseKey(H, i);
 156   }
 157
 158   return xbt_heap_pop(H);
 159 }
 160
 161 /**
 162  * @brief returns the smallest key in the heap (heap unchanged)
 163  * \param H the heap we're working on
 164  *
 165  * \return the smallest key in the heap without modifying the heap.
 166  */
 167 XBT_INLINE double xbt_heap_maxkey(xbt_heap_t H)
 168 {
 169   xbt_assert0(H->count != 0, "Empty heap");
 170   return KEY(H, 0);
 171 }
 172
 173 /**
 174  * @brief returns the value associated to the smallest key in the heap (heap unchanged)
 175  * \param H the heap we're working on
 176  *
 177  * \return the value associated to the smallest key in the heap
 178  * without modifying the heap.
 179  */
 180 void *xbt_heap_maxcontent(xbt_heap_t H)
 181 {
 182   xbt_assert0(H->count != 0, "Empty heap");
 183   return CONTENT(H, 0);
 184 }
 185
 186 /* <<<< private >>>>
 187  * \param H the heap we're working on
 188  *
 189  * Restores the heap property once an element has been deleted.
 190  */
 191 static void xbt_heap_maxHeapify(xbt_heap_t H)
 192 {
 193   int i = 0;
 194   while (1) {
 195     int greatest = i;
 196     int l = LEFT(i);
 197     int r = RIGHT(i);
 198     int count = H->count;
 199     if (l < count && KEY(H, l) < KEY(H, i))
 200       greatest = l;
 201     if (r < count && KEY(H, r) < KEY(H, greatest))
 202       greatest = r;
 203     if (greatest != i) {
 204       struct xbt_heapItem tmp = H->items[i];
 205       H->items[i] = H->items[greatest];
 206       H->items[greatest] = tmp;
 207       if (H->update_callback)
 208         H->update_callback(CONTENT(H, i), i);
 209       i = greatest;
 210     } else {
 211       if (H->update_callback)
 212         H->update_callback(CONTENT(H, i), i);
 213       return;
 214     }
 215   }
 216 }
 217
 218 /* <<<< private >>>>
 219  * \param H the heap we're working on
 220  * \param i an item position in the heap
 221  *
 222  * Moves up an item at position i to its correct position. Works only
 223  * when called from xbt_heap_push. Do not use otherwise.
 224  */
 225 static void xbt_heap_increaseKey(xbt_heap_t H, int i)
 226 {
 227   while (i > 0 && KEY(H, PARENT(i)) > KEY(H, i)) {
 228     struct xbt_heapItem tmp = H->items[i];
 229     H->items[i] = H->items[PARENT(i)];
 230     H->items[PARENT(i)] = tmp;
 231     if (H->update_callback)
 232       H->update_callback(CONTENT(H, i), i);
 233     i = PARENT(i);
 234   }
 235   if (H->update_callback)
 236     H->update_callback(CONTENT(H, i), i);
 237   return;
 238 }