Scheduler based on a splay tree.
Daniel D. Sleator and Robert E. Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32(3):652--686, 1985. 118.
Basic idea of this scheduler: it organizes the event queue into a binary search tree. For every insert and deque operation, "splaying" is performed aimed at shortening the search path for "similar" priorities (time_). This should give O(log(N)) amortized time for basic operations, may be even better for correlated inserts.
Implementation notes: Event::next_ and Event::prev_ are used as right and left pointers. insert() and deque() use the "top-down" splaying algorithm taken almost verbatim from the paper and in some cases optimized for particular operations. lookup() is extremely inefficient, and should be avoided whenever possible. cancel() would be better off if we had a pointer to the parent, then there wouldn't be any need to search for it (and use Event::uid_ to resolve conflicts when same-priority events are both on the left and right). cancel() does not perform any splaying, while it perhaps should.
Memory used by this scheduler is O(1) (not counting the events). |