AsyncEventRef.h

// -*- C++ -*-
 
//  Copyright (c) 2005-2010, Isode Limited, London, England.
//  All rights reserved.
//                                                                       
//  Acquisition and use of this software and related materials for any      
//  purpose requires a written licence agreement from Isode Limited,
//  or a written licence from an organisation licenced by Isode Limited
//  to grant such a licence.
 
// 
//
// AsyncEventRef.h
//
// Interface to the event queue classes
//
// @VERSION@
 
#include "../include/timeutil.h"
 
#include "Event_p.h"
 
namespace Event {
 
    class AsyncEventPlainQueue : AsyncEventRef {
    private:
        static AsyncEventPlainQueue *_freelist;
 
        // A simple, doubly linked list
        AsyncEventPlainQueue   *_next;
        AsyncEventPlainQueue   *_prev;
 
        AsyncEventPlainQueue (AsyncEvent *event) : AsyncEventRef (event) {}
 
    public:
        AsyncEventPlainQueue () {
            _next = _prev = this;
        }
 
        void Insert (AsyncEvent *event) {
            AsyncEventPlainQueue *newq = _freelist;
            if ( newq ) {
                _freelist = newq->_next;
                newq->Set (event);
            } else {
                newq = new AsyncEventPlainQueue (event);
            }
 
            _prev->_next = newq;
            newq->_prev = _prev;
            newq->_next = this;
            _prev = newq;
        }
 
        virtual void extract () {
            _prev->_next = _next;
            _next->_prev = _prev;
            _next = _freelist;
 
            _freelist = this;
        }
 
        AsyncEvent * First () {
            if ( _next == this )
                return 0;
 
            return _next->Extract();
        }
 
        AsyncEvent * Last () {
            if ( _prev == this )
                return 0;
 
            return _prev->Extract();
        }
 
        bool HasEvents () const {
            return _next != this;
        }
    };
 
    //
    // This implementation is a skip list, as this should be
    // efficient. The only operations required are insertion, removal
    // and removal of the initial element.
    //
    // The probability used for determining level is 0.25, i.e. the
    // effective 'tree' has an expected fan-out of 4. There is a trade-off
    // here between getting to about the right point quickly and work involved
    // maintaining levels.
    //
    // The maximum level used is an implementation parameter. It is set to 8,
    // which means the tree will 'max out' at about 4^8 = 65536 nodes. Above
    // this the efficiency of the list will decrease.
    //
    // The Random number generator utilizes the same algorithm as that in Tcl
    // It generates numbers in the range [1, IM-1], where IM = 2^31 -1.
    // The arithmetic is done in a way to avoid integer overflow.
 
 
    template <class C, class F> class AsyncEventPrioQueue : AsyncEventRef {
    private:
        static const int _maxlevel = 8;
        static const int _shift    = 2;
        static const int _mask     = (1<<_shift) - 1;
        static const int RAND_IA = 16807;
        static const int RAND_IQ = 127773;
        static const int RAND_IR = 2836;
 
        static AsyncEventPrioQueue   *_freelist;
 
        C                      _prio;
        int                    _rand;
        AsyncEventPrioQueue   *_next[_maxlevel];
        AsyncEventPrioQueue   *_prev[_maxlevel];
        int                    _level;
 
        inline AsyncEventPrioQueue (AsyncEvent *event,
                             int         level,
                             C           prio)
            : AsyncEventRef (event) {
                _prio  = prio;
                _level = level;
            }
 
    public:
        inline AsyncEventPrioQueue () {
            _level = 1;
            _next[0] = _prev[0] = this;
            memset (&_prio, 0, sizeof _prio);
            _rand = 12345678;
        }
 
        virtual ~AsyncEventPrioQueue() {}
 
        inline void Insert (AsyncEvent *event, C prio) {
            // Generate next random number
            long int tmp = _rand/RAND_IQ;
            _rand = tmp = RAND_IA*(_rand - tmp*RAND_IQ) - RAND_IR*tmp;
 
            // Fold the upper bits into the lower bits
            tmp ^= tmp >>_maxlevel*_shift;
 
            int level = 1;
 
            while ( level < _maxlevel && level <= _level && (tmp & _mask) == _mask ) {
                level++;
                tmp >>= _shift;
            }
 
            if ( level > _level ) {
                // Need to fill in the head to head pointers
                // As level cannot be more than one more than _level,
                // there is no more than one pair to fill in
                _next[_level] = _prev[_level] = this;
                _level++;
            }
 
            AsyncEventPrioQueue *newq = _freelist;
            if ( newq ) {
                _freelist = newq->_next[0];
                newq->Set (event);
                newq->_prio = prio;
                newq->_level = level;
 
            } else {
                newq = new AsyncEventPrioQueue (event, level, prio);
            }
 
            AsyncEventPrioQueue *succ = this;
            AsyncEventPrioQueue *pred = this;
 
            // Need to traverse all levels
            level = _level;
 
            F comp(prio);
 
            while ( --level >= 0 ) {
                // At the start of the loop we know that the new item
                // Follows succ and preceeds pred.
 
                AsyncEventPrioQueue *prev = succ->_prev[level];
 
                // If the item preceeding the successor at this level
                // is the same as the predecessor at the previous level
                // there is nothing to do.
                if ( prev != pred ) {
 
                    // Chain along at the current level, while the key of
                    // the predecessor follows the key of the new event
 
                    while ( comp.preceeds (prev->_prio) ) {
                        succ = prev;
                        prev = succ->_prev[level];
                    }
 
                    pred = prev;
                }
 
 
                // Insert the new item at this point in the level
                // if the item has this level
 
                if ( level < newq->_level ) {
                    newq->_next[level] = succ;
                    newq->_prev[level] = prev;
                    succ->_prev[level] = newq;
                    pred->_next[level] = newq;
                }
            }
        }
 
        inline virtual void extract () {
            int level = _level;
            while ( --level >= 0 ) {
                _next[level]->_prev[level] = _prev[level];
                _prev[level]->_next[level] = _next[level];
            }
            _next[0] = _freelist;
            _freelist = this;
        }
 
        inline AsyncEvent *First (const C prio) {
            F comp (prio);
 
            // Only return if there is something to return and
            // The priority of the event is not lower than the given priority
            if ( _next[0] == this || comp.preceeds (_next[0]->_prio) )
                return 0;
 
            return _next[0]->Extract();
        }
 
        inline AsyncEvent *First () {
            // Only return if there is something to return
            // The priority of the event is not lower than the given priority
            if ( _next[0] == this )
                return 0;
 
            return _next[0]->Extract();
        }
 
        inline bool HasEvents () {
            return _next[0] != this;
        }
 
        inline const C *NextPrio () {
            if ( _next[0] == this )
                return 0;
 
            return &_next[0]->_prio;
        }
    };
 
    template <class C, class F> AsyncEventPrioQueue<C,F> *
    AsyncEventPrioQueue<C,F>::_freelist = 0;
 
    typedef AsyncEventPrioQueue<timespec, Timecompare> AsyncEventTimerQueue;
 
    class Integercompare {
    private:
        unsigned int  value;
    public:
        Integercompare (unsigned int v) : value(v) {}
 
        bool preceeds (unsigned int v1) { return value < v1; }
    };
 
    typedef AsyncEventPrioQueue<unsigned, Integercompare> AsyncEventPriorityQueue;
 
}