sptbinq.cpp

Go to the documentation of this file.

// splay tree + bin queue limited to fixed step method
// for event-sets or priority queues
// this starts from the sptqueue.cpp file and adds a bin queue

/* Derived from David Brower's c translation of pascal code by
Douglas Jones.
*/
/* The original c code is included from this file but note that instead
of struct _spblk, we are really using TQItem
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <section.h>

#define leftlink left_
#define rightlink right_
#define uplink parent_
#define cnt cnt_
#define key t_
#include <sptree.h>

//extern double dt;
#define nt_dt nrn_threads->_dt

void (*nrn_binq_enqueue_error_handler)(double, TQItem*);

TQItem::TQItem() {
    left_ = 0;
    right_ = 0;
    parent_ = 0;
}

TQItem::~TQItem() {
}

bool TQItem::check() {
#if DOCHECK
#endif
    return true;
}

static void prnt(const TQItem* b, int level) {
    int i;
    for (i=0; i < level; ++i) {
        Printf("    ");
    }
    Printf("%g %c %d Q=%p D=%p\n", b->t_, b->data_?'x':'o', b->cnt_, b, b->data_);
}

static void chk(TQItem* b, int level) {
    if (!b->check()) {
        hoc_execerror("chk failed", errmess_);
    }
}

TQueue::TQueue(TQItemPool* tp, int mkmut) {
    MUTCONSTRUCT(mkmut)
    tpool_ = tp;
    nshift_ = 0;
    sptree_ = new SPTREE<TQItem>;
    spinit(sptree_);
    binq_ = new BinQ;
    least_ = 0;

#if COLLECT_TQueue_STATISTICS
    nmove = ninsert = nrem = nleast = nbal = ncmplxrem = 0;
    nfastmove = ncompare = nleastsrch = nfind = nfindsrch = 0;
#endif
}

TQueue::~TQueue() {
    TQItem* q, *q2;
    while((q = spdeq(&sptree_->root)) != nil) {
        deleteitem(q);
    }
    delete sptree_;
    for (q = binq_->first(); q; q = q2) {
        q2 = binq_->next(q);
        remove(q);
    }
    delete binq_;
    MUTDESTRUCT
}
    
void TQueue::deleteitem(TQItem* i) {
    tpool_->hpfree(i);
}

void TQueue::print() {
    MUTLOCK
#if FAST_LEAST
    if (least_) {
        prnt(least_, 0);
    }
#endif
    spscan(prnt, static_cast<TQItem*>(nil), sptree_);
    for (TQItem* q = binq_->first(); q; q = binq_->next(q)) {
        prnt(q, 0);
    }
    MUTUNLOCK
}

void TQueue::forall_callback(void(*f)(const TQItem*, int)) {
    MUTLOCK
#if FAST_LEAST
    if (least_) {
        f(least_, 0);
    }
#endif
    spscan(f, static_cast<TQItem*>(nil), sptree_);
    for (TQItem* q = binq_->first(); q; q = binq_->next(q)) {
        f(q, 0);
    }
    MUTUNLOCK
}

void TQueue::check(const char* mes) {
}

#if FAST_LEAST
// for Parallel Global Variable Timestep method.
// Assume not using bin queue.
TQItem* TQueue::second_least(double t) {
    assert(least_);
    TQItem* b = sphead(sptree_);
    if (b && b->t_ == t) {
        return b;
    }
    return 0;
}
#endif

void TQueue::move_least(double tnew) {
    MUTLOCK
    move_least_nolock(tnew);
    MUTUNLOCK
}

void TQueue::move_least_nolock(double tnew) {
    TQItem* b = least();
    if (b) {
        b->t_ = tnew;
        TQItem* nl = sphead(sptree_);
        if (nl) {
            if (tnew > nl->t_) {
                least_ = spdeq(&sptree_->root);
                spenq(b, sptree_);
            }
        }
    }
}

void TQueue::move(TQItem* i, double tnew) {
    MUTLOCK
    STAT(nmove)
    if (i == least_) {
        move_least_nolock(tnew);
    }else if (tnew < least_->t_) {
        spdelete(i, sptree_);
        i->t_ = tnew;
        spenq(least_, sptree_);
        least_ = i;
    }else{
        spdelete(i, sptree_);
        i->t_ = tnew;
        spenq(i, sptree_);
    }
    MUTUNLOCK
}

void TQueue::statistics() {
#if COLLECT_TQueue_STATISTICS
    Printf("insertions=%lu  moves=%lu removals=%lu calls to least=%lu\n",
        ninsert, nmove, nrem, nleast);
    Printf("calls to find=%lu\n",
        nfind);
    Printf("comparisons=%d\n",
        sptree_->enqcmps);
#else
    Printf("Turn on COLLECT_TQueue_STATISTICS_ in tqueue.h\n");
#endif
}

void TQueue::spike_stat(double* d) {
#if COLLECT_TQueue_STATISTICS
    d[0] = ninsert;
    d[1] = nmove;
    d[2] = nrem;
//printf("FifoQ spikestat nfenq=%lu nfdeq=%lu nfrem=%lu\n", fifo_->nfenq, fifo_->nfdeq, fifo_->nfrem);
#endif
}

TQItem* TQueue::insert(double t, void* d) {
    MUTLOCK
    STAT(ninsert);
    TQItem* i = tpool_->alloc();
    i->data_ = d;
    i->t_ = t;
    i->cnt_ = -1;
    if (t < least_t_nolock()) {
        if (least()) {
            spenq(least(), sptree_);
        }
        least_ = i;
    }else{
        spenq(i, sptree_);
    }
    MUTUNLOCK
    return i;
}

TQItem* TQueue::enqueue_bin(double td, void* d) {
    MUTLOCK
    STAT(ninsert);
    TQItem* i = tpool_->alloc();
    i->data_ = d;
    i->t_ = td;
    binq_->enqueue(td, i);
    MUTUNLOCK
    return i;
}

void TQueue::release(TQItem* q) {
    // if lockable then the pool is internally handles locking
    tpool_->hpfree(q);
}

void TQueue::remove(TQItem* q) {
    MUTLOCK
    STAT(nrem);
    if (q) {
        if (q == least_) {
            if (sptree_->root) {
                least_ = spdeq(&sptree_->root);
            }else{
                least_ = nil;
            }
        }else if (q->cnt_ >= 0) {
            binq_->remove(q);
        }else{
            spdelete(q, sptree_);
        }
        tpool_->hpfree(q);
    }
    MUTUNLOCK
}

TQItem* TQueue::atomic_dq(double tt) {
    TQItem* q = 0;
    MUTLOCK
    if (least_ && least_->t_ <= tt) {
        q = least_;
        STAT(nrem);
        if (sptree_->root) {
            least_ = spdeq(&sptree_->root);
        }else{
            least_ = nil;
        }
    }
    MUTUNLOCK
    return q;
}

TQItem* TQueue::find(double t) {
    TQItem* q;
    MUTLOCK
    // search only in the  splay tree. if this is a bug then fix it.
    STAT(nfind)
    if (t == least_t_nolock()) {
        q = least();
    }else{
        q = splookup(t, sptree_);
    }
    MUTUNLOCK
    return(q);
}

BinQ::BinQ() {
    nbin_ = 1000;
    bins_ = new TQItem*[nbin_];
    for (int i=0; i < nbin_; ++i) { bins_[i] = 0; }
    qpt_ = 0;
    tt_ = 0.;
#if COLLECT_TQueue_STATISTICS
    nfenq = nfdeq = nfrem = 0;
#endif
}

BinQ::~BinQ() {
    for (int i=0; i < nbin_; ++i) {
        assert(!bins_[i]);
    }
    delete [] bins_;
}

void BinQ::resize(int size) {
    //printf("BinQ::resize from %d to %d\n", nbin_, size);
    int i, j;
    TQItem* q;
    assert(size >= nbin_);
    TQItem** bins = new TQItem*[size];
    for (i=nbin_; i < size; ++i) { bins[i] = 0; }
    for (i=0, j=qpt_; i < nbin_; ++i, ++j) {
        if (j >= nbin_) { j = 0; }
        bins[i] = bins_[j];
        for (q = bins[i]; q; q = q->left_) {
            q->cnt_ = i;
        }
    }
    delete [] bins_;
    bins_ = bins;
    nbin_ = size;
    qpt_ = 0;
}
void BinQ::enqueue(double td, TQItem* q) {
    int idt = (int)((td - tt_)/nt_dt + 1.e-10);
    if (idt < 0) {
        if (nrn_binq_enqueue_error_handler) {
            (*nrn_binq_enqueue_error_handler)(td, q);
            return;
        }else{
            assert(idt >= 0);
        }
    }
    if (idt >= nbin_) {
        resize(idt + 100);
    }
    //assert (idt < nbin_);
    idt += qpt_;
    if (idt >= nbin_) { idt -= nbin_; }
//printf("enqueue idt=%d qpt=%d\n", idt, qpt_);
    assert (idt < nbin_);
    q->cnt_ = idt; // only for iteration
    q->left_ = bins_[idt];
    bins_[idt] = q;
#if COLLECT_TQueue_STATISTICS
    ++nfenq;
#endif
}
TQItem* BinQ::dequeue() {
    TQItem* q = bins_[qpt_];
    if (q) {
        bins_[qpt_] = q->left_;
#if COLLECT_TQueue_STATISTICS
        ++nfdeq;
#endif
    }
    return q;
}

/** Iterate in ascending bin order starting at current bin **/
TQItem* BinQ::first() {
    for (int i = 0; i < nbin_; ++i) {
        // start at least time qpt_ up to nbin_, and then wrap
        // around to 0 and go up to qpt_
        int j = (qpt_ + i)%nbin_;
        if (bins_[j]) {
            return bins_[j];
        }
    }
    return 0;
}
TQItem* BinQ::next(TQItem* q) {
    if (q->left_) { return q->left_; }
    // next non-empty bin starting at q->cnt_ + 1, until reach
    // exactly qpt_, possibly wrapping around back to 0 if reach nbin_
    for (int i = (q->cnt_ + 1)%nbin_; i != qpt_; i = (i + 1)%nbin_) {
        if (bins_[i]) {
            return bins_[i];
        }
    }
    return 0;
}

void BinQ::remove(TQItem* q) {
    TQItem* q1, *q2;
    q1 = bins_[q->cnt_];
    if (q1 == q) {
        bins_[q->cnt_] = q->left_;
        return;
    }
    for (q2 = q1->left_; q2; q1 = q2, q2 = q2->left_) {
        if (q2 == q) {
            q1->left_ = q->left_;
            return;
        }
    }
}