*
* Creates a new heap.
*/
-xbt_heap_t xbt_heap_new(int init_size, void_f_pvoid_t const free_func)
+XBT_INLINE xbt_heap_t xbt_heap_new(int init_size, void_f_pvoid_t const free_func)
{
xbt_heap_t H = xbt_new0(struct xbt_heap, 1);
H->size = init_size;
return H;
}
+/**
+ * @brief Set the update callback function.
+ * @param H the heap we're working on
+ * \param update_callback function to call on each element to update its index when needed.
+ */
+XBT_INLINE void xbt_heap_set_update_callback(xbt_heap_t H,
+ void (*update_callback) (void *, int))
+{
+ H->update_callback = update_callback;
+}
+
+
/**
* @brief kilkil a heap and its content
* @param H poor victim
* @param H the heap we're working on
* @return the number of elements in the heap
*/
-int xbt_heap_size(xbt_heap_t H)
+XBT_INLINE int xbt_heap_size(xbt_heap_t H)
{
return (H->count);
}
H->items =
(void *) realloc(H->items, (H->size) * sizeof(struct xbt_heapItem));
}
+
+ H->update_callback ? H->update_callback(max, -1) : NULL;
return max;
}
+/**
+ * @brief Extracts from the heap and returns the element at position i.
+ * \param H the heap we're working on
+ * \param i element position
+ * \return the element at position i if ok, NULL otherwise
+ *
+ * Extracts from the heap and returns the element at position i. The head is automatically reorded.
+ */
+void *xbt_heap_remove(xbt_heap_t H, int i)
+{
+ if ((i < 0) || (i > H->count - 1))
+ return NULL;
+ /* put element i at head */
+ if (i > 0) {
+ KEY(H, i) = MIN_KEY_VALUE;
+ xbt_heap_increaseKey(H, i);
+ }
+
+ return xbt_heap_pop(H);
+}
+
/**
* @brief returns the smallest key in the heap (heap unchanged)
* \param H the heap we're working on
*
* \return the smallest key in the heap without modifying the heap.
*/
-double xbt_heap_maxkey(xbt_heap_t H)
+XBT_INLINE double xbt_heap_maxkey(xbt_heap_t H)
{
xbt_assert0(H->count != 0, "Empty heap");
return KEY(H, 0);
struct xbt_heapItem tmp = H->items[i];
H->items[i] = H->items[greatest];
H->items[greatest] = tmp;
+ H->update_callback ? H->update_callback(CONTENT(H, i), i) : NULL;
i = greatest;
- } else
+ } else {
+ H->update_callback ? H->update_callback(CONTENT(H, i), i) : NULL;
return;
+ }
}
}
struct xbt_heapItem tmp = H->items[i];
H->items[i] = H->items[PARENT(i)];
H->items[PARENT(i)] = tmp;
+ H->update_callback ? H->update_callback(CONTENT(H, i), i) : NULL;
i = PARENT(i);
}
+ H->update_callback ? H->update_callback(CONTENT(H, i), i) : NULL;
return;
}
+