On 4/15/09, Nick Mathewson <ni...@freehaven.net> wrote:
> On Wed, Apr 15, 2009 at 01:01:00PM +0300, Marko Kreen wrote:
> > Given heap shape of:
> >
> > 1
> > / \
> > / \
> > 10 3
> > / \ / \
> > 11 12 5 6
> >
> > And now deleting '11', it seems to fail to keep heap property.
> >
> > The bug is probably hard to notice in practice as the events
> > will reach top anyway, only later than expected.
>
> Got a patch for this?
Well, I attached a draft of it, but its totally untested and the
minheap code is not very parseable for me. So somebody with
has better understanding of the code should review it. (Maxim?)
Basic idea - if you replace an element in the middle of heap with
last element, there is chance it needs to be pushed up not down.
I found it when writing heap code for my own small libevent-compatible
event loop. I've used to writing against libevent API, but when the
program will process only small number of connections, it seems
unnecessary to create libevent dependency for it. Code can be seen here:
http://github.com/markokr/libusual/blob/0812279371dcf07ea3961642ecf88403dceda2e6/usual/heap-impl.h
> > Btw, I did not got feedback on my event struct size decreasing patch:
> >
> > http://monkeymail.org/archives/libevent-users/2008-July/001346.html
> >
> > 24 bytes on 64-bit platforms may not sound like a big memory saving,
> > but if we want to process tens or even hundreds of thousands of events
> > with maximum efficiency, then best use of CPU caches becomes important.
> > And there the bytes can matter.
>
>
> This looks pretty good. I'll apply it in 2.0;
Thanks.
> I'd prefer to leave the
> struct layout alone for the 1.4 series so as not to break binary
> compatibility more than necessary.
Yeah, thats reasonable.
--
marko
Index: minheap-internal.h
===================================================================
--- minheap-internal.h (revision 1174)
+++ minheap-internal.h (working copy)
@@ -88,7 +88,12 @@
{
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;
+ 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;
}
_______________________________________________
Libevent-users mailing list
Libevent-users@monkey.org
http://monkeymail.org/mailman/listinfo/libevent-users
