-/* $Id: ilist.hh,v 1.3 2003/09/27 21:31:04 atterer Exp $ -*- C++ -*-
+/* $Id: ilist.hh,v 1.10 2005/04/09 23:09:52 atterer Exp $ -*- C++ -*-
__ _
|_) /| Copyright (C) 2003 | richard@
| \/¯| Richard Atterer | atterer.net
under the terms of the GNU General Public License, version 2. See the file
COPYING for details.
- Intrusive list, i.e. every list member needs to derive from IListBase
+*//** @file
+
+ Intrusive list, ie every list member needs to derive publically from
+ IListBase
+
+ A speciality is that list members will remove themselves from their list
+ automatically from their dtor.
*/
#include <log.hh>
//______________________________________________________________________
-/** Never use this type or its members in your code apart from deriving
- publicly from it. */
-struct IListBase {
+/** Derived classes can be list members. */
+class IListBase {
+ template<class T> friend class IList;
+public:
IListBase() : iListBase_prev(0), iListBase_next(0) {
//msg("IListBase %1", this);
}
~IListBase() {
//msg("~IListBase %1", this);
+ iList_remove();
+ }
+ /** May use this to unlink this object from its list, if any */
+ void iList_remove() {
if (iListBase_prev == 0) return;
+ Paranoid(iListBase_next != 0);
iListBase_prev->iListBase_next = iListBase_next;
iListBase_next->iListBase_prev = iListBase_prev;
iListBase_prev = iListBase_next = 0;
}
+
+private:
IListBase* iListBase_prev;
IListBase* iListBase_next;
};
-template <class T>
+/** The list object. */
+template<class T>
class IList {
public:
-
typedef unsigned size_type;
typedef T value_type;
class iterator;
- //class const_iterator;
+ class const_iterator;
friend class iterator;
- //friend class const_iterator;
+ friend class const_iterator;
typedef T& reference;
- //typedef const T& const_reference;
+ typedef const T& const_reference;
IList() { e.iListBase_prev = e.iListBase_next = &e; }
+ /** Releases all member objects from the list, does not delete them. */
+ ~IList() {
+ IListBase* p = e.iListBase_next;
+ while (p != &e) {
+ IListBase* q = p->iListBase_next;
+ p->iListBase_prev = p->iListBase_next = 0;
+ p = q;
+ }
+ e.iListBase_prev = e.iListBase_next = 0;
+ }
bool empty() const { return e.iListBase_next == &e; }
void push_back(T& x) {
//msg("IList::push_back %1", &x);
+
+ // Object must not already be a list member
Assert(x.iListBase_prev == 0 && x.iListBase_next == 0);
+
x.iListBase_prev = e.iListBase_prev;
x.iListBase_next = &e;
x.iListBase_prev->iListBase_next = &x;
x.iListBase_next->iListBase_prev = &x;
}
+ void push_front(T& x) {
+ // Object must not already be a list member
+ Assert(x.iListBase_prev == 0 && x.iListBase_next == 0);
+
+ x.iListBase_prev = &e;
+ x.iListBase_next = e.iListBase_next;
+ x.iListBase_prev->iListBase_next = &x;
+ x.iListBase_next->iListBase_prev = &x;
+ }
T& front() const { return *static_cast<T*>(e.iListBase_next); }
T& back() const { return *static_cast<T*>(e.iListBase_prev); }
- inline iterator begin() const { return iterator(e.iListBase_next); }
- inline iterator end() const { return iterator(const_cast<IListBase*>(&e));}
+ inline iterator begin() {
+ return iterator(e.iListBase_next); }
+ inline iterator end() {
+ return iterator(&e); }
+ inline const_iterator begin() const {
+ return const_iterator(e.iListBase_next); }
+ inline const_iterator end() const {
+ return const_iterator(&e); }
private:
+ // For the iterator class, which cannot be a friend of IListBase
+ static inline IListBase* next(const IListBase* ilb) {
+ return ilb->iListBase_next; }
+ static inline IListBase* prev(const IListBase* ilb) {
+ return ilb->iListBase_prev; }
+
IListBase e;
};
-template <class T>
+/** iterator for an IList object */
+template<class T>
class IList<T>::iterator {
+ friend class const_iterator;
public:
iterator(IListBase* pp) : p(pp) { }
+ iterator(const iterator& i) : p(i.p) { }
+ iterator& operator=(const iterator& i) { p = i.p; return *this; }
+ iterator& operator=(const const_iterator& i) { p = i.p; return *this; }
+
T& operator*() { return *getT(); }
const T& operator*() const { return *getT(); }
T* operator->() { return getT(); }
const T* operator->() const { return getT(); }
- iterator& operator++() { p = p->iListBase_next; return *this; }
- iterator& operator--() { p = p->iListBase_prev; return *this; }
+ iterator& operator++() { p = IList<T>::next(p); return *this; }
+ iterator& operator--() { p = IList<T>::prev(p); return *this; }
bool operator==(const iterator i) const { return p == i.p; }
bool operator!=(const iterator i) const { return p != i.p; }
private:
+ //T* getT() { return reinterpret_cast<T*>(p); }
+ // Will not work if IListBase is an inaccessible base of T:
T* getT() { return static_cast<T*>(p); }
IListBase* p;
};
-// template <class T>
-// class IList::iterator {
-// public:
-// private:
-// IListBase* p;
-// };
+/** const_iterator for an IList object */
+template<class T>
+class IList<T>::const_iterator {
+ friend class iterator;
+public:
+ const_iterator(IListBase* pp) : p(pp) { }
+ const_iterator(const IListBase* pp) : p(pp) { }
+ explicit const_iterator(const iterator& i) : p(i.p) { }
+ const_iterator& operator=(const iterator& i) { p = i.p; return *this; }
+ const_iterator(const const_iterator& i) : p(i.p) { }
+ const_iterator& operator=(const const_iterator& i) { p = i.p; return *this; }
+
+ const T& operator*() const { return *getT(); }
+ const T* operator->() const { return getT(); }
+ const_iterator& operator++() { p = IList<T>::next(p); return *this; }
+ const_iterator& operator--() { p = IList<T>::prev(p); return *this; }
+ bool operator==(const const_iterator i) const { return p == i.p; }
+ bool operator!=(const const_iterator i) const { return p != i.p; }
+private:
+ //const T* getT() const { return reinterpret_cast<const T*>(p); }
+ // Will not work if IListBase is an inaccessible base of T:
+ const T* getT() const { return static_cast<const T*>(p); }
+ const IListBase* p;
+};
#endif