src/xbt/heap.c

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