X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/bdfe4f8674f98efbf2d67ad854ef83a1d5f855ed..16bbb8a8212497d9c44c81333ed2c0e689e0c5af:/src/xbt/heap.c diff --git a/src/xbt/heap.c b/src/xbt/heap.c index ac3cafec92..2153d42c4b 100644 --- a/src/xbt/heap.c +++ b/src/xbt/heap.c @@ -1,6 +1,6 @@ /* a generic and efficient heap */ -/* Copyright (c) 2004-2005, 2007-2013. The SimGrid Team. +/* Copyright (c) 2004-2005, 2007-2015. The SimGrid Team. * All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it @@ -13,7 +13,7 @@ #include XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_heap, xbt, "Heap"); -static void xbt_heap_max_heapify(xbt_heap_t H); +static void xbt_heap_max_heapify(xbt_heap_t H, int i); static void xbt_heap_increase_key(xbt_heap_t H, int i); /** @addtogroup XBT_heap @@ -132,7 +132,7 @@ void *xbt_heap_pop(xbt_heap_t H) items[0] = items[(H->count) - 1]; (H->count)--; - xbt_heap_max_heapify(H); + xbt_heap_max_heapify(H,0); if (H->count < size >> 2 && size > 16) { size = (size >> 1) + 1; H->items = @@ -168,6 +168,43 @@ void *xbt_heap_remove(xbt_heap_t H, int i) return xbt_heap_pop(H); } +/** @brief Remove an arbitrary element from the heap + * @param H the heap we're working on + * @param content the object you want to add to the heap + * @param key the key associated to this object + */ +void xbt_heap_rm_elm(xbt_heap_t H, void *content, double key) { + int i=0; + while (i < H->count && (KEY(H, i) != key || CONTENT(H, i) != content)) + i++; + if (i == H->count) + return; + xbt_heap_remove(H,i); +} + +/** + * @brief Updates an element of the heap with a new value. + * \param H the heap we're working on + * \param i element position + * \param key new value for the element + * + * Updates an element of the heap with a new value. + */ +void xbt_heap_update(xbt_heap_t H, int i, double key) +{ + XBT_DEBUG("Heap has %d elements: updating element %d : was %1.12f to %1.12f ",xbt_heap_size(H),i,KEY(H, i), key); + + if ((i < 0) || (i > H->count - 1) || key == KEY(H, i)) + return ; + + if(key< KEY(H, i)){ + KEY(H, i)=key; + xbt_heap_increase_key(H, i); + }else{ + KEY(H, i)=key; + xbt_heap_max_heapify(H,i); + } +} /** * @brief returns the smallest key in the heap (heap unchanged) @@ -199,9 +236,9 @@ void *xbt_heap_maxcontent(xbt_heap_t H) * * Restores the heap property once an element has been deleted. */ -static void xbt_heap_max_heapify(xbt_heap_t H) +static void xbt_heap_max_heapify(xbt_heap_t H, int index) { - int i = 0; + int i = index; int count = H->count; xbt_heap_item_t items = H->items;