ns2 Network Simulator      C++ Class Hierarchy of version ns-snapshot-20040722
|  Home |  Source Code |  Manual |  FAQ |  Mailing List Archive |  Search |  |  Download | 


Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

ns-2/common/splay-scheduler.cc File Reference

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

Compounds

class  SplaySchedulerClass

Defines

#define LEFT(e)   ((e)->prev_)
#define RIGHT(e)   ((e)->next_)
#define ROTATE_RIGHT(t, x)
#define ROTATE_LEFT(t, x)
#define LINK_LEFT(l, t)
#define LINK_RIGHT(r, t)

Variables

const char rcsid []
SplaySchedulerClass class_splay_sched

Define Documentation

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

#define LINK_LEFT (  l,
t    ) 
 

Value:

do {                            \
        RIGHT(l) = (t);                 \
        (l) = (t);                      \
        (t) = RIGHT(t);                 \
    } while (0)

#define LINK_RIGHT (  r,
t    ) 
 

Value:

do {                            \
        LEFT(r) = (t);                  \
        (r) = (t);                      \
        (t) = LEFT(t);                  \
    } while (0)

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

#define ROTATE_LEFT (  t,
x    ) 
 

Value:

do {                            \
        RIGHT(t)  = LEFT(x);            \
        LEFT(x) = (t);                  \
        (t) = (x);                      \
    } while(0)

#define ROTATE_RIGHT (  t,
x    ) 
 

Value:

do {                            \
        LEFT(t) = RIGHT(x);             \
        RIGHT(x) = (t);                 \
        (t) = (x);                      \
    } while(0)

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).

const char rcsid[] [static]
 

Initial value:

"@(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/common/splay-scheduler.cc,v 1.5 2002/12/02 21:15:43 yuri Exp $"

This document is generated by doxygen.