Implement queued timeouts for case where many timeouts are the same.

Libevent's current timeout code is relatively optimized for the
randomly scattered timeout case, where events are added with their
timeouts in no particular order.  We add and remove timeouts with
O(lg n) behavior.

Frequently, however, an application will want to have many timeouts
of the same value.  For example, we might have 1000 bufferevents,
each with a 2 second timeout on reading or writing.  If we knew this
were always the case, we could just put timeouts in a queue and get
O(1) add and remove behavior.  Of course, a queue would give O(n)
performance for a scattered timeout pattern, so we don't want to
just switch the implementation.

This patch gives the user the ability to explicitly tag certain
timeout values as being "very common".  These timeout values have a
cookie encoded in the high bits of their tv_usec field to indicate
which queue they belong on.  The queues themselves are each
triggered by an entry in the minheap.

See the regress_main.c code for an example use.

svn:r1517

1 files changed, 12 insertions, 12 deletions

diff --git a/minheap-internal.h b/minheap-internal.h
index 8b638ecc..ba557166 100644
--- a/minheap-internal.h
+++ b/minheap-internal.h
@@ -62,7 +62,7 @@ int min_heap_elem_greater(struct event *a, struct event *b)
 
 void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
 void min_heap_dtor(min_heap_t* s) { free(s->p); }
-void min_heap_elem_init(struct event* e) { e->min_heap_idx = -1; }
+void min_heap_elem_init(struct event* e) { e->ev_timeout_pos.min_heap_idx = -1; }
 int min_heap_empty(min_heap_t* s) { return 0u == s->n; }
 unsigned min_heap_size(min_heap_t* s) { return s->n; }
 struct event* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; }
@@ -81,7 +81,7 @@ struct event* min_heap_pop(min_heap_t* s)
     {
         struct event* e = *s->p;
         min_heap_shift_down_(s, 0u, s->p[--s->n]);
-        e->min_heap_idx = -1;
+        e->ev_timeout_pos.min_heap_idx = -1;
         return e;
     }
     return 0;
@@ -89,25 +89,25 @@ struct event* min_heap_pop(min_heap_t* s)
 
 int min_heap_elt_is_top(const struct event *e)
 {
-	return e->min_heap_idx == 0;
+	return e->ev_timeout_pos.min_heap_idx == 0;
 }
 
 int min_heap_erase(min_heap_t* s, struct event* e)
 {
-    if(((unsigned int)-1) != e->min_heap_idx)
+    if(((unsigned int)-1) != e->ev_timeout_pos.min_heap_idx)
     {
         struct event *last = s->p[--s->n];
-        unsigned parent = (e->min_heap_idx - 1) / 2;
+        unsigned parent = (e->ev_timeout_pos.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);
+        if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
+             min_heap_shift_up_(s, e->ev_timeout_pos.min_heap_idx, last);
         else
-             min_heap_shift_down_(s, e->min_heap_idx, last);
-        e->min_heap_idx = -1;
+             min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last);
+        e->ev_timeout_pos.min_heap_idx = -1;
         return 0;
     }
     return -1;
@@ -134,11 +134,11 @@ void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
     unsigned parent = (hole_index - 1) / 2;
     while(hole_index && min_heap_elem_greater(s->p[parent], e))
     {
-        (s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;
+        (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index;
         hole_index = parent;
         parent = (hole_index - 1) / 2;
     }
-    (s->p[hole_index] = e)->min_heap_idx = hole_index;
+    (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
 }
 
 void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
@@ -149,7 +149,7 @@ void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
         min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
         if(!(min_heap_elem_greater(e, s->p[min_child])))
             break;
-        (s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;
+        (s->p[hole_index] = s->p[min_child])->ev_timeout_pos.min_heap_idx = hole_index;
         hole_index = min_child;
         min_child = 2 * (hole_index + 1);
 	}