1  /*
   2   * \brief  Single connected list
   3   * \author Norman Feske
   4   * \date   2006-08-02
   5   */
   6  
   7  /*
   8   * Copyright (C) 2006-2010 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 *_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() const { return _first; }
  62  
  63           /**
  64            * Insert element into list
  65            */
  66           void insert(LT *le)
  67           {
  68              le->Element::_next = _first;
  69              _first = le;
  70           }
  71  
  72           /**
  73            * Remove element from list
  74            */
  75           void remove(LT *le)
  76           {
  77              if (!_first) return;
  78  
  79              /* if specified element is the first of the list */
  80              if (le == _first)
  81                 _first = le->Element::_next;
  82  
  83              else {
  84  
  85                 /* search specified element in the list */
  86                 Element *e = _first;
  87                 while (e->_next && (e->_next != le))
  88                    e = e->_next;
  89  
  90                 /* element is not member of the list */
  91                 if (!e->_next) return;
  92  
  93                 /* e->_next is the element to remove, skip it in list */
  94                 e->Element::_next = e->Element::_next->Element::_next;
  95              }
  96  
  97              le->Element::_next = 0;
  98           }
  99     };
 100  
 101  
 102     /**
 103      * Helper for using member variables as list elements
 104      *
 105      * \param T  type of compound object to be organized in a list
 106      *
 107      * This helper allow the creation of lists that use member variables to
 108      * connect their elements. This way, the organized type does not need to
 109      * publicly inherit `List<LT>::Element`. Furthermore objects can easily
 110      * be organized in multiple lists by embedding multiple `List_element`
 111      * member variables.
 112      */
 113     template <typename T>
 114     class List_element : public List<List_element<T> >::Element
 115     {
 116        T *_object;
 117  
 118        public:
 119  
 120           List_element(T *object) : _object(object) { }
 121  
 122           T *object() { return _object; }
 123     };
 124  }
 125  
 126  #endif /* _INCLUDE__UTIL__LIST_H_ */
© 2010 Genode Labs