Event::AsyncEventPrioQueue< C, F > Class Template Reference

Priority queue template. More...

#include <AsyncEventRef.h>

Inheritance diagram for Event::AsyncEventPrioQueue< C, F >:

Public Member Functions
void	Insert (AsyncEvent *event, C prio)
virtual void	extract ()
AsyncEvent *	First (const C prio)
AsyncEvent *	First ()
bool	HasEvents ()
const C *	NextPrio ()

Detailed Description

template<class C, class F>
class Event::AsyncEventPrioQueue< C, F >

Priority queue template.

Definition at line 108 of file AsyncEventRef.h.

Constructor & Destructor Documentation

AsyncEventPrioQueue()

template<class C , class F >

Event::AsyncEventPrioQueue< C, F >::AsyncEventPrioQueue ( )

inline

Definition at line 134 of file AsyncEventRef.h.

                                      {
            _level = 1;
            _next[0] = _prev[0] = this;
            memset (&_prio, 0, sizeof _prio);
            _rand = 12345678;
        }

~AsyncEventPrioQueue()

template<class C , class F >

virtual Event::AsyncEventPrioQueue< C, F >::~AsyncEventPrioQueue ( )

inlinevirtual

Definition at line 141 of file AsyncEventRef.h.

{}

Member Function Documentation

Insert()

template<class C , class F >

void Event::AsyncEventPrioQueue< C, F >::Insert ( AsyncEvent *  event, C  prio  )

inline

Definition at line 143 of file AsyncEventRef.h.

                                                       {
            // 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;
                }
            }
        }

extract()

template<class C , class F >

virtual void Event::AsyncEventPrioQueue< C, F >::extract ( )

inlinevirtual

Definition at line 220 of file AsyncEventRef.h.

                                       {
            int level = _level;
            while ( --level >= 0 ) {
                _next[level]->_prev[level] = _prev[level];
                _prev[level]->_next[level] = _next[level];
            }
            _next[0] = _freelist;
            _freelist = this;
        }

First() [1/2]

template<class C , class F >

AsyncEvent * Event::AsyncEventPrioQueue< C, F >::First ( const C  prio )

inline

Definition at line 230 of file AsyncEventRef.h.

                                                {
            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();
        }

First() [2/2]

template<class C , class F >

AsyncEvent * Event::AsyncEventPrioQueue< C, F >::First ( )

inline

Definition at line 241 of file AsyncEventRef.h.

                                    {
            // 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();
        }

HasEvents()

template<class C , class F >

bool Event::AsyncEventPrioQueue< C, F >::HasEvents ( )

inline

Definition at line 250 of file AsyncEventRef.h.

                                 {
            return _next[0] != this;
        }

NextPrio()

template<class C , class F >

const C * Event::AsyncEventPrioQueue< C, F >::NextPrio ( )

inline

Definition at line 254 of file AsyncEventRef.h.

                                    {
            if ( _next[0] == this )
                return 0;
 
            return &_next[0]->_prio;
        }

---

The documentation for this class was generated from the following file:

• AsyncEventRef.h