1  /*
   2   * \brief  Queue with first-in first-out semantics
   3   * \author Norman Feske
   4   * \date   2008-08-15
   5   */
   6  
   7  /*
   8   * Copyright (C) 2008-2013 Genode Labs GmbH
   9   *
  10   * This file is part of the Genode OS framework, which is distributed
  11   * under the terms of the GNU General Public License version 2.
  12   */
  13  
  14  #ifndef _INCLUDE__UTIL__FIFO_H_
  15  #define _INCLUDE__UTIL__FIFO_H_
  16  
  17  #include <base/printf.h>
  18  
  19  namespace Genode {
  20     
  21     template<typename> class Fifo;
  22     template <typename> class Fifo_element;
  23  }
  24  
  25  
  26  /**
  27   * Fifo queue
  28   *
  29   * \param QT  queue element type
  30   */
  31  template <typename QT>
  32  class Genode::Fifo
  33  {
  34     public:
  35  
  36        class Element
  37        {
  38           protected:
  39  
  40              friend class Fifo;
  41  
  42              QT *_next;
  43              bool _is_enqueued;
  44  
  45           public:
  46  
  47              Element(): _next(0), _is_enqueued(false) { }
  48  
  49              /**
  50               * Return true is fifo element is enqueued in a fifo
  51               */
  52              bool is_enqueued() { return _is_enqueued; }
  53  
  54              /**
  55               * Return next element in queue
  56               */
  57              QT *next() const { return _next; }
  58        };
  59  
  60     private:
  61  
  62        QT      *_head;  /* oldest element */
  63        Element *_tail;  /* newest element */
  64  
  65     public:
  66  
  67        /**
  68         * Return true if queue is empty
  69         */
  70        bool empty() { return _tail == 0; }
  71  
  72        /**
  73         * Constructor
  74         */
  75        Fifo(): _head(0), _tail(0) { }
  76  
  77        /**
  78         * Return first queue element
  79         */
  80        QT *head() const { return _head; }
  81  
  82        /**
  83         * Remove element explicitely from queue
  84         */
  85        void remove(QT *qe)
  86        {
  87           if (empty()) return;
  88  
  89           /* if specified element is the first of the queue */
  90           if (qe == _head) {
  91              _head = qe->Element::_next;
  92              if (!_head) _tail  = 0;
  93           }
  94           else {
  95  
  96              /* search specified element in the queue */
  97              Element *e = _head;
  98              while (e->_next && (e->_next != qe))
  99                 e = e->_next;
 100  
 101              /* element is not member of the queue */
 102              if (!e->_next) return;
 103  
 104              /* e->_next is the element to remove, skip it in list */
 105              e->Element::_next = e->Element::_next->Element::_next;
 106              if (!e->Element::_next) _tail = e;
 107           }
 108  
 109           qe->Element::_next = 0;
 110           qe->Element::_is_enqueued = 0;
 111        }
 112  
 113        /**
 114         * Attach element at the end of the queue
 115         */
 116        void enqueue(QT *e)
 117        {
 118           e->Fifo::Element::_next = 0;
 119           e->Fifo::Element::_is_enqueued = true;
 120  
 121           if (empty()) {
 122              _tail = _head = e;
 123              return;
 124           }
 125  
 126           _tail->Fifo::Element::_next = e;
 127           _tail = e;
 128        }
 129  
 130        /**
 131         * Remove head element from queue
 132         *
 133         * \return  head element or 0 if queue is empty
 134         */
 135        QT *dequeue()
 136        {
 137           QT *result = _head;
 138  
 139           /* check if queue has only one last element */
 140           if (_head == _tail) {
 141              _head = 0;
 142              _tail = 0;
 143           } else
 144              _head = _head->Fifo::Element::_next;
 145  
 146           /* mark fifo queue element as free */
 147           if (result) {
 148              result->Fifo::Element::_next = 0;
 149              result->Fifo::Element::_is_enqueued = false;
 150           }
 151  
 152           return result;
 153        }
 154  };
 155  
 156  
 157  /**
 158   * Helper for using member variables as FIFO elements
 159   *
 160   * \param T  type of compound object to be organized in a FIFO
 161   *
 162   * This helper allow the creation of FIFOs that use member variables to
 163   * connect their elements. This way, the organized type does not need to
 164   * publicly inherit `Fifo<QT>::Element`. Furthermore objects can easily
 165   * be organized in multiple FIFOs by embedding multiple `Fifo_element`
 166   * member variables.
 167   */
 168  template <typename T>
 169  class Genode::Fifo_element : public Fifo<Fifo_element<T> >::Element
 170  {
 171     T *_object;
 172  
 173     public:
 174  
 175        Fifo_element(T *object) : _object(object) { }
 176  
 177        /**
 178         * Get typed object pointer
 179         *
 180         * Zero-pointer save: Returns 0 if this pointer is 0 to
 181         * cover the case of accessing an empty FIFO.
 182         */
 183        inline T *object()
 184        {
 185           if (this) { return _object; }
 186           return 0;
 187        }
 188  };
 189  
 190  #endif /* _INCLUDE__UTIL__FIFO_H_ */