/* -*- Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
* splay-scheduler.cc
* Copyright (C) 2002 by the University of Southern California
* $Id: splay-scheduler.cc,v 1.6 2005/08/25 18:58:02 johnh Exp $
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License,
* version 2, as published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License along
* with this program; if not, write to the Free Software Foundation, Inc.,
* 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
*
*
* The copyright of this module includes the following
* linking-with-specific-other-licenses addition:
*
* In addition, as a special exception, the copyright holders of
* this module give you permission to combine (via static or
* dynamic linking) this module with free software programs or
* libraries that are released under the GNU LGPL and with code
* included in the standard release of ns-2 under the Apache 2.0
* license or under otherwise-compatible licenses with advertising
* requirements (or modified versions of such code, with unchanged
* license). You may copy and distribute such a system following the
* terms of the GNU GPL for this module and the licenses of the
* other code concerned, provided that you include the source code of
* that other code when and as the GNU GPL requires distribution of
* source code.
*
* Note that people who make modified versions of this module
* are not obligated to grant this special exception for their
* modified versions; it is their choice whether to do so. The GNU
* General Public License gives permission to release a modified
* version without this exception; this exception also makes it
* possible to release a modified version which carries forward this
* exception.
*
*/
// @(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/common/splay-scheduler.cc,v 1.6 2005/08/25 18:58:02 johnh Exp $
#ifndef lint
static const char rcsid[] =
"@(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/common/splay-scheduler.cc,v 1.6 2005/08/25 18:58:02 johnh Exp $";
#endif
/**
*
* 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.
**/
#include <scheduler.h>
#include <assert.h>
static class SplaySchedulerClass : public TclClass
{
public:
SplaySchedulerClass() : TclClass("Scheduler/Splay") {}
TclObject* create(int /* argc */, const char*const* /* argv */) {
return (new SplayScheduler);
}
} class_splay_sched;
#undef LEFT
#undef RIGHT
#define LEFT(e) ((e)->prev_)
#define RIGHT(e) ((e)->next_)
#define ROTATE_RIGHT(t, x) \
do { \
LEFT(t) = RIGHT(x); \
RIGHT(x) = (t); \
(t) = (x); \
} while(0)
#define ROTATE_LEFT(t, x) \
do { \
RIGHT(t) = LEFT(x); \
LEFT(x) = (t); \
(t) = (x); \
} while(0)
#define LINK_LEFT(l, t) \
do { \
RIGHT(l) = (t); \
(l) = (t); \
(t) = RIGHT(t); \
} while (0)
#define LINK_RIGHT(r, t) \
do { \
LEFT(r) = (t); \
(r) = (t); \
(t) = LEFT(t); \
} while (0)
void
SplayScheduler::insert(Event *n)
{
Event *l; // bottom right in the left tree
Event *r; // bottom left in the right tree
Event *t; // root of the remaining tree
Event *x; // current node
++qsize_;
double time = n->time_;
if (root_ == 0) {
LEFT(n) = RIGHT(n) = 0;
root_ = n;
//validate();
return;
}
t = root_;
root_ = n; // n is the new root
l = n;
r = n;
for (;;) {
if (time < t->time_) {
x = LEFT(t);
if (x == 0) {
LEFT(r) = t;
RIGHT(l) = 0;
break;
}
if (time < x->time_) {
ROTATE_RIGHT(t, x);
}
LINK_RIGHT(r, t);
if (t == 0) {
RIGHT(l) = 0;
break;
}
} else {
x = RIGHT(t);
if (x == 0) {
RIGHT(l) = t;
LEFT(r) = 0;
break;
}
if (time >= x->time_) {
ROTATE_LEFT(t, x);
}
LINK_LEFT(l, t);
if (t == 0) {
LEFT(r) = 0;
break;
}
}
} /* for (;;) */
// assemble:
// swap left and right children
x = LEFT(n);
LEFT(n) = RIGHT(n);
RIGHT(n) = x;
//validate();
}
const Event *
SplayScheduler::head()
{
Event *t;
Event *l;
#if 1
if (root_ == 0)
return 0;
for (t = root_; (l = LEFT(t)); t = l)
;
return t;
#else
Event *ll;
Event *lll;
if (root_ == 0)
return 0;
t = root_;
l = LEFT(t);
if (l == 0) {
return t;
}
for (;;) {
ll = LEFT(l);
if (ll == 0) {
return l;
}
lll = LEFT(ll);
if (lll == 0) {
return ll;
}
// zig-zig: rotate l with ll
LEFT(t) = ll;
LEFT(l) = RIGHT(ll);
RIGHT(ll) = l;
t = ll;
l = lll;
}
#endif /* 1/0 */
}
Event *
SplayScheduler::deque()
{
Event *t;
Event *l;
Event *ll;
Event *lll;
if (root_ == 0)
return 0;
--qsize_;
t = root_;
l = LEFT(t);
if (l == 0) { // root is the element to dequeue
root_ = RIGHT(t); // right branch becomes the root
//validate();
return t;
}
for (;;) {
ll = LEFT(l);
if (ll == 0) {
LEFT(t) = RIGHT(l);
//validate();
return l;
}
lll = LEFT(ll);
if (lll == 0) {
LEFT(l) = RIGHT(ll);
//validate();
return ll;
}
// zig-zig: rotate l with ll
LEFT(t) = ll;
LEFT(l) = RIGHT(ll);
RIGHT(ll) = l;
t = ll;
l = lll;
}
}
void
SplayScheduler::cancel(Event *e)
{
if (e->uid_ <= 0)
return; // event not in queue
Event **t;
//validate();
if (e == root_) {
t = &root_;
} else {
// searching among same-time events is a real bugger,
// all because we don't have a parent pointer; use
// uid_ to resolve conflicts.
for (t = &root_; *t;) {
t = ((e->time_ > (*t)->time_) ||
((e->time_ == (*t)->time_) && e->uid_ > (*t)->uid_))
? &RIGHT(*t) : &LEFT(*t);
if (*t == e)
break;
}
if (*t == 0) {
fprintf(stderr, "did not find it\n");
abort(); // not found
}
}
// t is the pointer to e in the parent or to root_ if e is root_
e->uid_ = -e->uid_;
--qsize_;
if (RIGHT(e) == 0) {
*t = LEFT(e);
LEFT(e) = 0;
//validate();
return;
}
if (LEFT(e) == 0) {
*t = RIGHT(e);
RIGHT(e) = 0;
//validate();
return;
}
// find successor
Event *p = RIGHT(e), *q = LEFT(p);
if (q == 0) {
// p is the sucessor
*t = p;
LEFT(p) = LEFT(e);
//validate();
return;
}
for (; LEFT(q); p = q, q = LEFT(q))
;
// q is the successor
// p is q's parent
*t = q;
LEFT(p) = RIGHT(q);
LEFT(q) = LEFT(e);
RIGHT(q) = RIGHT(e);
RIGHT(e) = LEFT(e) = 0;
//validate();
}
Event *
SplayScheduler::lookup(scheduler_uid_t uid)
{
lookup_uid_ = uid;
return uid_lookup(root_);
}
Event *
SplayScheduler::uid_lookup(Event *root)
{
if (root == 0)
return 0;
if (root->uid_ == lookup_uid_)
return root;
Event *res = uid_lookup(LEFT(root));
if (res)
return res;
return uid_lookup(RIGHT(root));
}
int
SplayScheduler::validate(Event *root)
{
int size = 0;
if (root) {
++size;
assert(LEFT(root) == 0 || root->time_ >= LEFT(root)->time_);
assert(RIGHT(root) == 0 || root->time_ <= RIGHT(root)->time_);
size += validate(LEFT(root));
size += validate(RIGHT(root));
return size;
}
return 0;
}
syntax highlighted by Code2HTML, v. 0.9.1