// vi:set ft=cpp: -*- Mode: C++ -*- /* * (c) 2008-2009 Alexander Warg * economic rights: Technische Universität Dresden (Germany) * * This file is part of TUD:OS and distributed under the terms of the * GNU General Public License 2. * Please see the COPYING-GPL-2 file for details. * * As a special exception, you may use this file as part of a free software * library without restriction. Specifically, if other files instantiate * templates or use macros or inline functions from this file, or you compile * this file and link it with other files to produce an executable, this * file does not by itself cause the resulting executable to be covered by * the GNU General Public License. This exception does not however * invalidate any other reasons why the executable file might be covered by * the GNU General Public License. */ #pragma once #include #include #include namespace cxx { /* * Classes: List_item, List */ /** * \ingroup cxx_api * \brief Basic list item. * * Basic item that can be member of a doubly linked, cyclic list. */ class List_item { public: /** * \brief Iterator for a list of ListItem-s. * * The Iterator iterates till it finds the first element again. */ class Iter { public: Iter(List_item *c, List_item *f) throw() : _c(c), _f(f) {} Iter(List_item *f = 0) throw() : _c(f), _f(f) {} List_item *operator * () const throw() { return _c; } List_item *operator -> () const throw() { return _c; } Iter &operator ++ () throw() { if (!_f) _c = 0; else _c = _c->get_next_item(); if (_c == _f) _c = 0; return *this; } Iter operator ++ (int) throw() { Iter o = *this; operator ++ (); return o; } Iter &operator -- () throw() { if (!_f) _c = 0; else _c = _c->get_prev_item(); if (_c == _f) _c = 0; return *this; } Iter operator -- (int) throw() { Iter o = *this; operator -- (); return o; } /** Remove item pointed to by iterator, and return pointer to element. */ List_item *remove_me() throw() { if (!_c) return 0; List_item *l = _c; operator ++ (); l->remove_me(); if (_f == l) _f = _c; return l; } private: List_item *_c, *_f; }; /** * \brief Iterator for derived classes from ListItem. * * Allows direct access to derived classes by * operator. * * Example: * class Foo : public ListItem * { * public: * typedef T_iter Iter; * ... * }; */ template< typename T, bool Poly = false> class T_iter : public Iter { private: static bool const P = !Conversion::exists || Poly; static List_item *cast_to_li(T *i, Int_to_type) throw() { return dynamic_cast(i); } static List_item *cast_to_li(T *i, Int_to_type) throw() { return i; } static T *cast_to_type(List_item *i, Int_to_type) throw() { return dynamic_cast(i); } static T *cast_to_type(List_item *i, Int_to_type) throw() { return static_cast(i); } public: template< typename O > explicit T_iter(T_iter const &o) throw() : Iter(o) { dynamic_cast(*o); } //TIter(CListItem *f) : Iter(f) {} T_iter(T *f = 0) throw() : Iter(cast_to_li(f, Int_to_type

())) {} T_iter(T *c, T *f) throw() : Iter(cast_to_li(c, Int_to_type

()), cast_to_li(f, Int_to_type

())) {} inline T *operator * () const throw() { return cast_to_type(Iter::operator * (),Int_to_type

()); } inline T *operator -> () const throw() { return operator * (); } T_iter operator ++ (int) throw() { T_iter o = *this; Iter::operator ++ (); return o; } T_iter operator -- (int) throw() { T_iter o = *this; Iter::operator -- (); return o; } T_iter &operator ++ () throw() { Iter::operator ++ (); return *this; } T_iter &operator -- () throw() { Iter::operator -- (); return *this; } inline T *remove_me() throw(); }; List_item() throw() : _n(this), _p(this) {} protected: List_item(List_item const &) throw() : _n(this), _p(this) {} public: /** Get previous item. */ List_item *get_prev_item() const throw() { return _p; } /** Get next item. */ List_item *get_next_item() const throw() { return _n; } /** Insert item p before this item. */ void insert_prev_item(List_item *p) throw() { p->_p->_n = this; List_item *pr = p->_p; p->_p = _p; _p->_n = p; _p = pr; } /** Insert item p after this item. */ void insert_next_item(List_item *p) throw() { p->_p->_n = _n; p->_p = this; _n->_p = p; _n = p; } /** Remove this item from the list. */ void remove_me() throw() { if (_p != this) { _p->_n = _n; _n->_p = _p; } _p = _n = this; } /** * \brief Append item to a list. * * Convenience function for empty-head corner case. * \param head Pointer to the current list head. * \param p Pointer to new item. * \return the pointer to the new head. */ template< typename C, typename N > static inline C *push_back(C *head, N *p) throw(); /** * \brief Prepend item to a list. * * Convenience function for empty-head corner case. * \param head pointer to the current list head. * \param p pointer to new item. * \return the pointer to the new head. */ template< typename C, typename N > static inline C *push_front(C *head, N *p) throw(); /** * \brief Remove item from a list. * * Convenience function for remove-head corner case. * \param head pointer to the current list head. * \param p pointer to the item to remove. * \return the pointer to the new head. */ template< typename C, typename N > static inline C *remove(C *head, N *p) throw(); private: List_item *_n, *_p; }; /* IMPLEMENTATION -----------------------------------------------------------*/ template< typename C, typename N > C *List_item::push_back(C *h, N *p) throw() { if (!p) return h; if (!h) return p; h->insert_prev_item(p); return h; } template< typename C, typename N > C *List_item::push_front(C *h, N *p) throw() { if (!p) return h; if (h) h->insert_prev_item(p); return p; } template< typename C, typename N > C *List_item::remove(C *h, N *p) throw() { if (!p) return h; if (!h) return 0; if (h == p) { if (p == p->_n) h = 0; else h = static_cast(p->_n); } p->remove_me(); return h; } template< typename T, bool Poly > inline T *List_item::T_iter::remove_me() throw() { return cast_to_type(Iter::remove_me(), Int_to_type

()); } template< typename T > class T_list_item : public List_item { public: T *next() const { return static_cast(List_item::get_next_item()); } T *prev() const { return static_cast(List_item::get_prev_item()); } }; template< typename LI > class L_list { private: LI *_h; public: L_list() : _h(0) {} void push_front(LI *e) { _h = LI::push_front(_h, e); } void push_back(LI *e) { _h = LI::push_back(_h, e); } void insert_before(LI *e, LI *p) { p->insert_prev_item(e); if (_h == p) _h = e; } void insert_after(LI *e, LI *p) { p->insert_next_item(e); } void remove(LI *e) { _h = LI::remove(_h, e); } LI *head() const { return _h; } }; /** * Doubly linked list, with internal allocation. * Container for items of type D, implemented by a doubly linked list. * Alloc defines the allocator policy. */ template< typename D, template class Alloc = New_allocator > class List { private: class E : public List_item { public: E(D const &d) throw() : data(d) {} D data; }; public: class Node : private E {}; typedef Alloc Node_alloc; /** * Iterator. * Forward and backward iteratable. */ class Iter { private: List_item::T_iter _i; public: Iter(E *e) throw() : _i(e) {} D &operator * () const throw() { return (*_i)->data; } D &operator -> () const throw() { return (*_i)->data; } Iter operator ++ (int) throw() { Iter o = *this; operator ++ (); return o; } Iter operator -- (int) throw() { Iter o = *this; operator -- (); return o; } Iter &operator ++ () throw() { ++_i; return *this; } Iter &operator -- () throw() { --_i; return *this; } /** operator for testing validity (syntactically equal to pointers) */ operator E* () const throw() { return *_i; } }; List(Alloc const &a = Alloc()) throw() : _h(0), _l(0), _a(a) {} /** Add element at the end of the list. */ void push_back(D const &d) throw() { void *n = _a.alloc(); if (!n) return; _h = E::push_back(_h, new (n) E(d)); ++_l; } /** Add element at the beginning of the list. */ void push_front(D const &d) throw() { void *n = _a.alloc(); if (!n) return; _h = E::push_front(_h, new (n) E(d)); ++_l; } /** Remove element pointed to by the iterator. */ void remove(Iter const &i) throw() { E *e = i; _h = E::remove(_h, e); --_l; _a.free(e); } /** Get the length of the list. */ unsigned long size() const throw() { return _l; } /** Random access. Complexity is O(n). */ D const &operator [] (unsigned long idx) const throw() { Iter i = _h; for (; idx && *i; ++i, --idx) { } return *i; } /** Random access. Complexity is O(n). */ D &operator [] (unsigned long idx) throw() { Iter i = _h; for (; idx && *i; ++i, --idx) { } return *i; } /** Get iterator for the list elements. */ Iter items() throw() { return Iter(_h); } private: E *_h; unsigned _l; Alloc _a; }; };