Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(311)

Unified Diff: third_party/libevent/min_heap.h

Issue 412006: posix: upgrade libevent from 1.4.7 to 1.4.13 (Closed)
Patch Set: better readme Created 11 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
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;
}

Powered by Google App Engine
This is Rietveld 408576698