1// vi:set ft=cpp: -*- Mode: C++ -*-
2/*
3 * (c) 2011 Alexander Warg <warg@os.inf.tu-dresden.de>
4 *     economic rights: Technische Universität Dresden (Germany)
5 *
6 * This file is part of TUD:OS and distributed under the terms of the
7 * GNU General Public License 2.
8 * Please see the COPYING-GPL-2 file for details.
9 *
10 * As a special exception, you may use this file as part of a free software
11 * library without restriction.  Specifically, if other files instantiate
12 * templates or use macros or inline functions from this file, or you compile
13 * this file and link it with other files to produce an executable, this
14 * file does not by itself cause the resulting executable to be covered by
15 * the GNU General Public License.  This exception does not however
16 * invalidate any other reasons why the executable file might be covered by
17 * the GNU General Public License.
18 */
19
20#pragma once
21
22#include "bits/list_basics.h"
23
24namespace cxx {
25
26class S_list_item
27{
28public:
29  S_list_item() : _n(0) {}
30  explicit S_list_item(bool) {}
31
32private:
33  template<typename T, typename P> friend class S_list;
34  template<typename T, typename P> friend class S_list_tail;
35  template<typename T, typename X> friend struct Bits::Basic_list_policy;
36
37  S_list_item(S_list_item const &);
38  void operator = (S_list_item const &);
39
40  S_list_item *_n;
41};
42
43/**
44 * Simple single-linked list.
45 *
46 * \tparam T  Type of elements saved in the list. Must inherit from
47 *            cxx::S_list_item
48 */
49template< typename T, typename POLICY = Bits::Basic_list_policy< T, S_list_item > >
50class S_list : public Bits::Basic_list<POLICY>
51{
52private:
53  S_list(S_list const &);
54  void operator = (S_list const &);
55
56  typedef typename Bits::Basic_list<POLICY> Base;
57
58public:
59  typedef typename Base::Iterator Iterator;
60
61  // BSS allocation
62  explicit S_list(bool x) : Base(x) {}
63
64  S_list() : Base() {}
65
66  /// Add an element to the front of the list.
67  void add(T *e)
68  {
69    e->_n = this->_f;
70    this->_f = e;
71  }
72
73  template< typename CAS >
74  void add(T *e, CAS const &c)
75  {
76    do
77      {
78        e->_n = this->_f;
79      }
80    while (!c(&this->_f, e->_n, e));
81  }
82
83  /// Add an element to the front of the list.
84  void push_front(T *e) { add(e); }
85
86  /**
87   *  Remove and return the head element of the list.
88   *
89   *  \pre The list must not be empty or the behaviour will be undefined.
90   */
91  T *pop_front()
92  {
93    T *r = this->front();
94    if (this->_f)
95      this->_f = this->_f->_n;
96    return r;
97  }
98
99  void insert(T *e, Iterator const &pred)
100  {
101    S_list_item *p = *pred;
102    e->_n = p->_n;
103    p->_n = e;
104  }
105
106  static void insert_before(T *e, Iterator const &succ)
107  {
108    S_list_item **x = Base::__get_internal(succ);
109
110    e->_n = *x;
111    *x = e;
112  }
113
114  static void replace(Iterator const &p, T*e)
115  {
116    S_list_item **x = Base::__get_internal(p);
117    e->_n = (*x)->_n;
118    *x = e;
119  }
120
121  static Iterator erase(Iterator const &e)
122  {
123    S_list_item **x = Base::__get_internal(e);
124    *x = (*x)->_n;
125    return e;
126  }
127
128};
129
130
131template< typename T >
132class S_list_bss : public S_list<T>
133{
134public:
135  S_list_bss() : S_list<T>(true) {}
136};
137
138template< typename T, typename POLICY = Bits::Basic_list_policy< T, S_list_item >  >
139class S_list_tail : public S_list<T, POLICY>
140{
141private:
142  typedef S_list<T, POLICY> Base;
143
144public:
145  S_list_tail() : Base(), _tail(&this->_f) {}
146
147  void push_back(T *e)
148  {
149    e->_n = 0;
150    *_tail = e;
151    _tail = &e->_n;
152  }
153
154  void clear()
155  {
156    Base::clear();
157    _tail = &this->_f;
158  }
159
160  void append(S_list_tail &o)
161  {
162    T *x = o.front();
163    *_tail = x;
164    if (x)
165      _tail = o._tail;
166    o.clear();
167  }
168
169  void move_to(S_list_tail &t)
170  { t._f = this->_f; t._tail = _tail; clear(); }
171
172private:
173  S_list_item **_tail;
174};
175
176}
177