[vdr] Problems with 20 Timers

Olaf Titz olaf at bigred.inka.de
Fri Feb 25 19:16:38 CET 2005


> I wonder if it would be worth rewriting cSchedule to store events in a
> binary tree based on time. A double-linked list could be included in the
> nodes pointing to allow for scanning through the schedule in the
> conventional way (for(cEvent *p = events.First()...)

The right data structure for this (or rather, the canonical data
structure for any sort of timer queue) is a binary heap. Guaranteed
O(log n) time for insert and delete(first) operation and O(1) for
lookup(first), zero memory overhead and much easier to implement than
all other sorts of balanced tree.

> What do people think, would it be worth me writing a patch?

Definitely.

Olaf




More information about the vdr mailing list