Index: third_party/libevent/min_heap.h |
diff --git a/third_party/libevent/min_heap.h b/third_party/libevent/min_heap.h |
index d47e5638ab7067f520f73418e75a59d53b8064d0..4fc83c01e76b867ecb0205d2cd122e1204e9e635 100644 |
--- a/third_party/libevent/min_heap.h |
+++ b/third_party/libevent/min_heap.h |
@@ -86,7 +86,17 @@ int min_heap_erase(min_heap_t* s, struct event* e) |
{ |
if(((unsigned int)-1) != e->min_heap_idx) |
{ |
- min_heap_shift_down_(s, e->min_heap_idx, s->p[--s->n]); |
+ struct event *last = s->p[--s->n]; |
+ unsigned parent = (e->min_heap_idx - 1) / 2; |
+ /* we replace e with the last element in the heap. We might need to |
+ shift it upward if it is less than its parent, or downward if it is |
+ greater than one or both its children. Since the children are known |
+ to be less than the parent, it can't need to shift both up and |
+ down. */ |
+ if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last)) |
+ min_heap_shift_up_(s, e->min_heap_idx, last); |
+ else |
+ min_heap_shift_down_(s, e->min_heap_idx, last); |
e->min_heap_idx = -1; |
return 0; |
} |