1 /*
2  * (c) 2011 Alexander Warg <warg@os.inf.tu-dresden.de>
3  *     economic rights: Technische Universität Dresden (Germany)
4  *
5  * This file is part of TUD:OS and distributed under the terms of the
6  * GNU General Public License 2.
7  * Please see the COPYING-GPL-2 file for details.
8  *
9  * As a special exception, you may use this file as part of a free software
10  * library without restriction.  Specifically, if other files instantiate
11  * templates or use macros or inline functions from this file, or you compile
12  * this file and link it with other files to produce an executable, this
13  * file does not by itself cause the resulting executable to be covered by
14  * the GNU General Public License.  This exception does not however
15  * invalidate any other reasons why the executable file might be covered by
16  * the GNU General Public License.
17  */
18 
19 #pragma once
20 
21 namespace cxx { namespace Bits {
22 
23 template< typename T >
24 class List_iterator_end_ptr
25 {
26 private:
27   template< typename U > friend class Basic_list;
28   static void *_end;
29 };
30 
31 template< typename T >
32 void *List_iterator_end_ptr<T>::_end;
33 
34 template< typename VALUE_T, typename TYPE >
35 struct Basic_list_policy
36 {
37   typedef VALUE_T *Value_type;
38   typedef VALUE_T const *Const_value_type;
39   typedef TYPE **Type;
40   typedef TYPE *Const_type;
41   typedef TYPE *Head_type;
42   typedef TYPE Item_type;
43 
nextBasic_list_policy44   static Type next(Type c) { return static_cast<Type>(&(*c)->_n); }
nextBasic_list_policy45   static Const_type next(Const_type c) { return static_cast<Const_type>(c->_n); }
46 };
47 
48 /// Internal: Common functions for all head-based list implementations.
49 template< typename POLICY >
50 class Basic_list
51 {
52 private:
53   Basic_list(Basic_list const &);
54   void operator = (Basic_list const &);
55 
56 public:
57   typedef typename POLICY::Value_type Value_type;
58   typedef typename POLICY::Const_value_type Const_value_type;
59 
60   class Iterator
61   {
62   private:
63     typedef typename POLICY::Type Internal_type;
64 
65   public:
66     typedef typename POLICY::Value_type value_type;
67     typedef typename POLICY::Value_type Value_type;
68 
69     Value_type operator * () const { return static_cast<Value_type>(*_c); }
70     Value_type operator -> () const { return static_cast<Value_type>(*_c); }
71     Iterator operator ++ () { _c = POLICY::next(_c); return *this; }
72 
73     bool operator == (Iterator const &o) const { return *_c == *o._c; }
74     bool operator != (Iterator const &o) const { return !operator == (o); }
75 
Iterator()76     Iterator() : _c(__end()) {}
77 
78   private:
79     friend class Basic_list;
__end()80     static Internal_type __end()
81     {
82       union X { Internal_type l; void **v; } z;
83       z.v = &Bits::List_iterator_end_ptr<void>::_end;
84       return z.l;
85     }
86 
Iterator(Internal_type i)87     explicit Iterator(Internal_type i) : _c(i) {}
88 
89     Internal_type _c;
90   };
91 
92   class Const_iterator
93   {
94   private:
95     typedef typename POLICY::Const_type Internal_type;
96 
97   public:
98     typedef typename POLICY::Value_type value_type;
99     typedef typename POLICY::Value_type Value_type;
100 
101     Value_type operator * () const { return static_cast<Value_type>(_c); }
102     Value_type operator -> () const { return static_cast<Value_type>(_c); }
103     Const_iterator operator ++ () { _c = POLICY::next(_c); return *this; }
104 
105     friend bool operator == (Const_iterator const &lhs, Const_iterator const &rhs)
106     { return lhs._c == rhs._c; }
107     friend bool operator != (Const_iterator const &lhs, Const_iterator const &rhs)
108     { return lhs._c != rhs._c; }
109 
Const_iterator()110     Const_iterator() : _c(0) {}
Const_iterator(Iterator const & o)111     Const_iterator(Iterator const &o) : _c(*o) {}
112 
113   private:
114     friend class Basic_list;
115 
Const_iterator(Internal_type i)116     explicit Const_iterator(Internal_type i) : _c(i) {}
117 
118     Internal_type _c;
119   };
120 
121   // BSS allocation
Basic_list(bool)122   explicit Basic_list(bool) {}
Basic_list()123   Basic_list() : _f(0) {}
124 
125   /// Check if the list is empty.
empty()126   bool empty() const { return !_f; }
127   /// Return the first element in the list.
front()128   Value_type front() const { return static_cast<Value_type>(_f); }
129 
130   /**
131    * Remove all elements from the list.
132    *
133    * After the operation the state of the elements is undefined.
134    */
clear()135   void clear() { _f = 0; }
136 
137   /// Return an iterator to the beginning of the list.
begin()138   Iterator begin() { return Iterator(&_f); }
139   /// Return a const iterator to the beginning of the list.
begin()140   Const_iterator begin() const { return Const_iterator(_f); }
141   /**
142    *  Return a const iterator that begins at the given element.
143    *
144    *  \param c  Element where the iterator should start.
145    *
146    *  \pre The element `c` must already be in a list.
147    */
iter(Const_value_type c)148   static Const_iterator iter(Const_value_type c) { return Const_iterator(c); }
149   /// Return a const iterator to the end of the list.
end()150   Const_iterator end() const { return Const_iterator(nullptr); }
151   /// Return an iterator to the end of the list.
end()152   Iterator end() { return Iterator(); }
153 
154 protected:
__get_internal(Iterator const & i)155   static typename POLICY::Type __get_internal(Iterator const &i) { return i._c; }
__iter(typename POLICY::Type c)156   static Iterator __iter(typename POLICY::Type c) { return Iterator(c); }
157 
158   /// Pointer to front of the list.
159   typename POLICY::Head_type _f;
160 };
161 
162 }}
163 
164