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#include "type_traits" 24 25namespace cxx { 26 27/** 28 * Basic element type for a double-linked H_list. 29 * 30 * \tparam ELEM_TYPE Base class of the list element. 31 */ 32template<typename ELEM_TYPE> 33class H_list_item_t 34{ 35public: 36 /** 37 * Constructor. 38 * 39 * Creates an element that is not in any list. 40 */ 41 H_list_item_t() : _pn(0) {} 42 /** 43 * Destructor. 44 * 45 * Automatically removes the element from any list it still might be 46 * enchained in. 47 */ 48 ~H_list_item_t() noexcept { l_remove(); } 49 50private: 51 H_list_item_t(H_list_item_t const &) = delete; 52 53 template<typename T, typename P> friend class H_list; 54 template<typename T, typename X> friend struct Bits::Basic_list_policy; 55 56 void l_remove() noexcept 57 { 58 if (!_pn) 59 return; 60 61 *_pn = _n; 62 if (_n) 63 _n->_pn = _pn; 64 65 _pn = 0; 66 } 67 68 H_list_item_t *_n, **_pn; 69}; 70 71/** Untyped list item. */ 72typedef H_list_item_t<void> H_list_item; 73 74/** 75 * General double-linked list of unspecified cxx::H_list_item elements. 76 * 77 * Most of the time, you want to use H_list_t. 78 */ 79template< typename T, typename POLICY = Bits::Basic_list_policy< T, H_list_item> > 80class H_list : public Bits::Basic_list<POLICY> 81{ 82private: 83 typedef typename POLICY::Item_type Item; 84 typedef Bits::Basic_list<POLICY> Base; 85 H_list(H_list const &); 86 void operator = (H_list const &); 87 88public: 89 typedef typename Base::Iterator Iterator; 90 91 // BSS allocation 92 explicit H_list(bool x) : Base(x) {} 93 H_list() : Base() {} 94 95 /** 96 * Return an iterator for an arbitrary list element 97 * 98 * \param c List element to start the iteration. 99 * 100 * \return A mutable forward iterator. 101 * 102 * \pre The element must be in a list. 103 */ 104 static Iterator iter(T *c) { return Base::__iter(c->Item::_pn); } 105 106 /// Check if the given element is currently part of a list. 107 static bool in_list(T const *e) { return e->Item::_pn; } 108 109 /// Add element to the front of the list. 110 void add(T *e) 111 { 112 if (this->_f) 113 this->_f->_pn = &e->Item::_n; 114 e->Item::_n = this->_f; 115 e->Item::_pn = &this->_f; 116 this->_f = static_cast<Item*>(e); 117 } 118 119 /// Add element to the front of the list. 120 void push_front(T *e) { add(e); } 121 122 /** 123 * Remove and return the head element of the list. 124 * 125 * \pre The list must not be empty or the behaviour will be undefined. 126 */ 127 T *pop_front() 128 { 129 T *r = this->front(); 130 remove(r); 131 return r; 132 } 133 134 /** 135 * Insert an element at the iterator position. 136 * 137 * \param e New Element to be inserted 138 * \param pred Iterator pointing to the element after which the 139 * element will be inserted. If end() is given, the 140 * element will be inserted at the beginning of the queue. 141 * 142 * \return Iterator pointing to the newly inserted element. 143 */ 144 Iterator insert(T *e, Iterator const &pred) 145 { 146 Item **x = &this->_f; 147 if (pred != Base::end()) 148 x = &(*pred)->_n; 149 150 e->Item::_n = *x; 151 152 if (*x) 153 (*x)->_pn = &(e->Item::_n); 154 155 e->Item::_pn = x; 156 *x = static_cast<Item*>(e); 157 return iter(e); 158 } 159 160 /** 161 * Insert an element after the iterator position. 162 * 163 * \param e New element to be inserted. 164 * \param pred Iterator pointing to the element after which the 165 * element will be inserted. Must not be end(). 166 * 167 * \return Iterator pointing to the newly inserted element. 168 * 169 * \pre The list must not be empty. 170 */ 171 static Iterator insert_after(T *e, Iterator const &pred) 172 { 173 Item **x = &(*pred)->_n; 174 e->Item::_n = *x; 175 176 if (*x) 177 (*x)->_pn = &(e->Item::_n); 178 179 e->Item::_pn = x; 180 *x = static_cast<Item*>(e); 181 return iter(e); 182 } 183 184 /** 185 * Insert an element before the iterator position. 186 * 187 * \param e New element to be inserted. 188 * \param succ Iterator pointing to the element before which the 189 * element will be inserted. Must not be end(). 190 */ 191 static void insert_before(T *e, Iterator const &succ) 192 { 193 Item **x = Base::__get_internal(succ); 194 195 e->Item::_n = *x; 196 e->Item::_pn = x; 197 198 if (*x) 199 (*x)->_pn = &e->Item::_n; 200 201 *x = static_cast<Item*>(e); 202 } 203 204 /** 205 * Replace an element in a list with a new element. 206 * 207 * \param p Element in list to be replaced. 208 * \param e Replacement element, must not yet be in a list. 209 * 210 * \pre `p` and `e` must not be NULL. 211 * 212 * After the operation the p element is no longer in the 213 * list and may be reused. 214 */ 215 static void replace(T *p, T *e) 216 { 217 e->Item::_n = p->Item::_n; 218 e->Item::_pn = p->Item::_pn; 219 *(p->Item::_pn) = static_cast<Item*>(e); 220 if (e->Item::_n) 221 e->Item::_n->_pn = &(e->Item::_n); 222 223 p->Item::_pn = 0; 224 } 225 226 /** 227 * Remove the given element from its list. 228 * 229 * \param e Element to be removed. Must be in a list. 230 */ 231 static void remove(T *e) 232 { e->Item::l_remove(); } 233 234 /** 235 * Remove the element at the given iterator position. 236 * 237 * \param e Iterator pointing to the element to be removed. Must not 238 * point to end(). 239 * 240 * \return New iterator pointing to the element after the removed one. 241 * 242 * \note The hlist implementation guarantees that the original iterator 243 * is still valid after the element has been removed. In fact, the 244 * iterator returned is the same as the one supplied in the `e` 245 * parameter. 246 */ 247 static Iterator erase(Iterator const &e) 248 { e->Item::l_remove(); return e; } 249}; 250 251/** 252 * Double-linked list of typed H_list_item_t elements. 253 * 254 * \note H_lists are not self-cleaning. Elements that are still chained 255 * during destruction are not removed and will therefore be in an 256 * undefined state after the destruction. 257 */ 258template< typename T > 259struct H_list_t : H_list<T, Bits::Basic_list_policy< T, H_list_item_t<T> > > 260{ 261 H_list_t() = default; 262 H_list_t(bool b) 263 : H_list<T, Bits::Basic_list_policy< T, H_list_item_t<T> > >(b) 264 {}; 265}; 266 267template< typename T > 268class H_list_bss : public H_list<T> 269{ 270public: 271 H_list_bss() : H_list<T>(true) {} 272}; 273 274template< typename T > 275class H_list_t_bss : public H_list_t<T> 276{ 277public: 278 H_list_t_bss() : H_list_t<T>(true) {} 279}; 280 281 282} 283