1  /*
   2   * \brief  Single connected list
   3   * \author Norman Feske
   4   * \date   2006-08-02
   5   */
   6  
   7  /*
   8   * Copyright (C) 2006-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__LIST_H_
  15  #define _INCLUDE__UTIL__LIST_H_
  16  
  17  namespace Genode {
  18  
  19     /*
  20      * \param LT  list element type
  21      */
  22     template <typename LT>
  23     class List
  24     {
  25        private:
  26  
  27           LT *_first;
  28  
  29        public:
  30  
  31           class Element
  32           {
  33              protected:
  34  
  35                 friend class List;
  36  
  37                 LT mutable *_next;
  38  
  39              public:
  40  
  41                 Element(): _next(0) { }
  42  
  43                 /**
  44                  * Return next element in list
  45                  */
  46                 LT *next() const { return _next; }
  47           };
  48  
  49        public:
  50  
  51           /**
  52            * Constructor
  53            *
  54            * Start with an empty list.
  55            */
  56           List() : _first(0) { }
  57  
  58           /**
  59            * Return first list element
  60            */
  61           LT       *first()       { return _first; }
  62           LT const *first() const { return _first; }
  63  
  64           /**
  65            * Insert element after specified element into list
  66            *
  67            * \param  le  list element to insert
  68            * \param  at  target position (preceding list element)
  69            */
  70           void insert(LT const *le, LT const *at = 0)
  71           {
  72              /* insert at beginning of the list */
  73              if (at == 0) {
  74                 le->Element::_next = _first;
  75                 _first = const_cast<LT *>(le);
  76              } else {
  77                 le->Element::_next = at->Element::_next;
  78                 at->Element::_next = const_cast<LT *>(le);
  79              }
  80           }
  81  
  82           /**
  83            * Remove element from list
  84            */
  85           void remove(LT const *le)
  86           {
  87              if (!_first) return;
  88  
  89              /* if specified element is the first of the list */
  90              if (le == _first) {
  91                 _first = le->Element::_next;
  92  
  93              } else {
  94  
  95                 /* search specified element in the list */
  96                 Element *e = _first;
  97                 while (e->_next && (e->_next != le))
  98                    e = e->_next;
  99  
 100                 /* element is not member of the list */
 101                 if (!e->_next) return;
 102  
 103                 /* e->_next is the element to remove, skip it in list */
 104                 e->Element::_next = e->Element::_next->Element::_next;
 105              }
 106  
 107              le->Element::_next = 0;
 108           }
 109     };
 110  
 111  
 112     /**
 113      * Helper for using member variables as list elements
 114      *
 115      * \param T  type of compound object to be organized in a list
 116      *
 117      * This helper allow the creation of lists that use member variables to
 118      * connect their elements. This way, the organized type does not need to
 119      * publicly inherit `List<LT>::Element`. Furthermore objects can easily
 120      * be organized in multiple lists by embedding multiple `List_element`
 121      * member variables.
 122      */
 123     template <typename T>
 124     class List_element : public List<List_element<T> >::Element
 125     {
 126        T *_object;
 127  
 128        public:
 129  
 130           List_element(T *object) : _object(object) { }
 131  
 132           T *object() const { return _object; }
 133     };
 134  }
 135  
 136  #endif /* _INCLUDE__UTIL__LIST_H_ */