splay-scheduler.cc

Go to the documentation of this file.

/* -*-  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

#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;
}

---