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