On Wed, Oct 24, 2007 at 10:39:19AM +0200, Joerg Sonnenberger wrote:
> On Tue, Oct 23, 2007 at 10:54:35AM -0400, der Mouse wrote:
> > >> A 'heap' [...]
> > > I'm so sure about the heap.  We can't just use the classic binary
> > > heap as that needs a resizable array we don't have.
> > 
> > A heap is a particular subclass of binary tree.  Storing it in an array
> > is just a way to optimize away the parent and child pointers, and make
> > it easy to find the insertion point for new nodes.
> 
> Sure, but if you do that it is not that much cheaper then an red black
> tree anymore.

It should be, because you don't have to do any rebalancing, just a ripple
up/down on start/stop/expire. It would require 5 pointers/node, which
would end up pulling in a lot of cache lines during any operation.

	David

-- 
David Laight: david@l8s.co.uk