Black Box 4/BlackBox.cdr/progc/aetsk100.arj/SYSQTMPL.H

C/C++ Source or Header | 1991-11-13 | 6KB | 271 lines

/*
    sysqueue.h

    templates for queues using double linked lists

    copyright (c) 1991 J. Alan Eldridge

    history:

    10/28/91    created

    10/30/91    changed class hierarchy so we now have:

                SysQ<T>     queue of Ts
                SysPriQ<T>  priority queue of Ts
                SysQP<T>    queue of ptrs to T
                SysPriQP<T> priority queue of ptrs to T

*/

template <class T> struct SysQNode {
    T           data;
    SysQNode<T> *next;
    SysQNode<T> *prev;
};

template <class T> class SysQ {
protected:
    int         nused, nfree, maxnodes;
    SysQNode<T> *head, *tail, *free;

    SysQNode<T> *getfree(int=1);
    void        putfree(SysQNode<T>*);

    SysQNode<T>         *findnode(T);
    virtual SysQNode<T> *findpred(T);

    void        create(SysQNode<T>*);
    void        insert(SysQNode<T>*, SysQNode<T>*);

    int         Ins(T);
public:
    SysQ(int n=0, int lim=INT_MAX);
    ~SysQ();
    int         Add(T);
    int         Del(T);
    int         Get(T&, int=1);
    int         Cnt()
        { return nused; }
    int         Max()
        { return maxnodes; }
};

template <class T>
SysQ<T>::SysQ(int n, int lim)
{
    nused = nfree = 0;
    head = tail = free = 0;
    maxnodes = lim;
    while (n-- > 0)
        putfree(new SysQNode<T>);
}

template <class T>
SysQ<T>::~SysQ()
{
    T           t;
    SysQNode<T> *pn;

    //  dump all nodes onto free list
    while (Get(t))
        ;
    //  delete all nodes on free list
    while ((pn = getfree(0)) != 0)
        delete pn;
}

template <class T> SysQNode<T>*
SysQ<T>::getfree(int alloc)
{
    SysQNode<T>   *pn = 0;

    if (nfree > 0) {
        pn = free;
        free = free->next;
        nfree--;
    } else if (alloc) {
        pn = new SysQNode<T>;
    }

    return pn;
}

template <class T> void
SysQ<T>::putfree(SysQNode<T> *pn)
{
    nfree++;
    pn->next = free;
    free = pn;
}

template <class T> SysQNode<T>*
SysQ<T>::findnode(T t)
{
    SysQNode<T> *pn = head;

    while (pn && !(pn->data == t))
        pn = pn->next;

    return pn;
}

template <class T> void
SysQ<T>::create(SysQNode<T> *pn)
{
    head = tail = pn;
    nused = 1;
    pn->prev = pn->next = 0;
}

template <class T> void
SysQ<T>::insert(SysQNode<T> *pnext, SysQNode<T> *pn)
{
    //  add before 0 means put at tail

    if (!nused)
        create(pn);
    else {
        if (pnext) {
            pn->prev = pnext->prev;
            if (pnext == head)
                head = pn;
            else
                pnext->prev->next = pn;
            pnext->prev = pn;
            pn->next = pnext;
        } else {
            pn->prev = tail;
            tail->next = pn;
            tail = pn;
            pn->next = 0;
        }
        nused++;
    }
}

template <class T> int
SysQ<T>::Add(T t)
{
    SysQNode<T> *pn = getfree(nused + nfree < maxnodes);

    if (pn) {
        pn->data = t;
        insert(0, pn);
    }

    return !!pn;
}

template <class T> SysQNode<T>*
SysQ<T>::findpred(T t)
{
    SysQNode<T> *pwalk;

    pwalk = head;
    while (pwalk && !(pwalk->data < t))
        pwalk = pwalk->next;
    return pwalk;
}

template <class T> int
SysQ<T>::Ins(T t)
{
    SysQNode<T> *pn = getfree(nused + nfree < maxnodes);

    if (pn) {
        pn->data = t;
        insert(findpred(t), pn);
    }

    return !!pn;
}

template <class T> int
SysQ<T>::Get(T& t, int rmv)
{
    SysQNode<T> *pn = head;

    if (pn) {
        t = head->data;
        if (rmv) {
            if ((head = head->next) != 0)
                head->prev = 0;
            else
                tail = 0;
            nused--;
            putfree(pn);
        }
    }

    return !!pn;
}

template <class T> int
SysQ<T>::Del(T t)
{
    SysQNode<T> *pn = findnode(t);

    if (pn) {
        if (nused == 1)
            head = tail = 0;
        else if (pn == head)
            (head = head->next)->prev = 0;
        else if (pn == tail)
            (tail = tail->prev)->next = 0;
        else {
            pn->next->prev = pn->prev;
            pn->prev->next = pn->next;
        }
        nused--;
        putfree(pn);
    }

    return !!pn;
}

template <class T> class SysPriQ: public SysQ<T> {
public:
    SysPriQ(int n=0, int lim=INT_MAX): SysQ<T>(n,lim) { }
    int Add(T t)
        { return SysQ<T>::Ins(t); }
};

template <class T> class SysQP: public SysQ<void *> {
protected:
    SysQNode<void*> *findpred(void *);
public:
    SysQP(int n=0,int lim=INT_MAX): SysQ<void*>(n,lim) { }
    int Add(T* t)
        { return SysQ<void*>::Add(t); }
    int Del(T* t)
        { return SysQ<void*>::Del(t); }
    int Get(T* &t,int rmv=1)
        { return SysQ<void*>::Get((void*&)t,rmv); }
    T*  Get(int rmv=1);
};

template <class T> SysQNode<void*>*
SysQP<T>::findpred(void *p)
{
    SysQNode<void*> *pwalk;

    pwalk = head;
    while (pwalk && !(*(T*)pwalk->data < *(T*)p))
        pwalk = pwalk->next;
    return pwalk;
}

template <class T> T* SysQP<T>::Get(int rmv)
{
    T   *t;
    return Get(t,rmv) ? t : 0;
}

template <class T> class SysPriQP: public SysQP<T> {
public:
    SysPriQP(int n=0, int lim=INT_MAX): SysQP<T>(n,lim) { }
    int Add(T* t)
        { return SysQP<T>::Ins(t); }
};