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