splay-scheduler.cc File Reference

#include <scheduler.h>
#include <assert.h>

Include dependency graph for splay-scheduler.cc:

Go to the source code of this file.

Data Structures
class	SplaySchedulerClass
Defines
#define	LEFT(e)   ((e)->prev_)
#define	LINK_LEFT(l, t)
#define	LINK_RIGHT(r, t)
#define	RIGHT(e)   ((e)->next_)
#define	ROTATE_LEFT(t, x)
#define	ROTATE_RIGHT(t, x)
Variables
SplaySchedulerClass	class_splay_sched
static const char	rcsid []

---

Define Documentation

#define LEFT (  e   )     ((e)->prev_)

Definition at line 97 of file splay-scheduler.cc. Referenced by SplayScheduler::cancel(), SplayScheduler::deque(), SplayScheduler::head(), SplayScheduler::insert(), SplayScheduler::uid_lookup(), and SplayScheduler::validate().

#define LINK_LEFT (  l, t   )

Value: do { \ RIGHT(l) = (t); \ (l) = (t); \ (t) = RIGHT(t); \ } while (0) Definition at line 113 of file splay-scheduler.cc.

#define LINK_RIGHT (  r, t   )

Value: do { \ LEFT(r) = (t); \ (r) = (t); \ (t) = LEFT(t); \ } while (0) Definition at line 119 of file splay-scheduler.cc.

#define RIGHT (  e   )     ((e)->next_)

Definition at line 98 of file splay-scheduler.cc. Referenced by SplayScheduler::cancel(), SplayScheduler::deque(), SplayScheduler::insert(), SplayScheduler::uid_lookup(), and SplayScheduler::validate().

#define ROTATE_LEFT (  t, x   )

Value: do { \ RIGHT(t) = LEFT(x); \ LEFT(x) = (t); \ (t) = (x); \ } while(0) Definition at line 107 of file splay-scheduler.cc.

#define ROTATE_RIGHT (  t, x   )

Value: do { \ LEFT(t) = RIGHT(x); \ RIGHT(x) = (t); \ (t) = (x); \ } while(0) Definition at line 100 of file splay-scheduler.cc.

---

Variable Documentation

SplaySchedulerClass class_splay_sched [static]

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). The original vefsion of this code was by Yuri Pryadkin.

const char rcsid[] [static]

Initial value: "@(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/common/splay-scheduler.cc,v 1.6 2005/08/25 18:58:02 johnh Exp $" Definition at line 51 of file splay-scheduler.cc.

---