list.hh

Go to the documentation of this file.

#ifndef CLICK_LIST_HH
#define CLICK_LIST_HH 1
/*
 * list.hh -- List template
 * Eddie Kohler
 *
 * Copyright (c) 2008 Meraki, Inc.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software")
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Click LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Click LICENSE file; the license in that file is
 * legally binding.
 */
CLICK_DECLS
#define LIST_HEAD_MARKER 0 /* ((T *) 1) */
 
template <typename T> class List_member;
template <typename T, List_member<T> T::*member> class List;
 
template <typename T>
class List_member { public:
 
    List_member()
        : _next(), _prev() {
    }
 
    T *next() {
        return _next;
    }
    const T *next() const {
        return _next;
    }
 
    T *prev() {
        return _prev != LIST_HEAD_MARKER ? _prev : 0;
    }
    const T *prev() const {
        return _prev != LIST_HEAD_MARKER ? _prev : 0;
    }
 
  private:
 
    T *_next;
    T *_prev;
 
    List_member(const List_member<T> &x);
    List_member<T> &operator=(const List_member<T> &x);
    template <typename X, List_member<X> X::*member> friend class List;
 
};
 
template <typename T, List_member<T> T::*member>
class List { public:
 
    typedef T *pointer;
    typedef const T *const_pointer;
    class const_iterator;
    class iterator;
    typedef size_t size_type;
 
    List()
        : _head(0), _tail(0) {
    }
 
 
    iterator begin() {
        return iterator(_head, this);
    }
    const_iterator begin() const {
        return const_iterator(_head, this);
    }
    iterator end() {
        return iterator(this);
    }
    const_iterator end() const {
        return const_iterator(this);
    }
 
 
    bool empty() const {
        return _head == 0;
    }
 
    size_type size() const {
        size_type n = 0;
        for (T *x = _head; x; x = (x->*member)._next)
            ++n;
        return n;
    }
 
 
    pointer front() {
        return _head;
    }
    const_pointer front() const {
        return _head;
    }
    pointer back() {
        return _tail;
    }
    const_pointer back() const {
        return _tail;
    }
 
 
    void push_front(pointer x) {
        assert(x && isolated(x));
        if (((x->*member)._next = _head))
            (_head->*member)._prev = x;
        else
            _tail = x;
        _head = x;
        (_head->*member)._prev = LIST_HEAD_MARKER;
    }
 
    void push_back(pointer x) {
        assert(x && !(x->*member)._next && !(x->*member)._prev);
        if (((x->*member)._prev = _tail))
            (_tail->*member)._next = x;
        else {
            _head = x;
            (_head->*member)._prev = LIST_HEAD_MARKER;
        }
        _tail = x;
    }
 
    void pop_front() {
        assert(_head);
        pointer x = _head;
        if ((_head = (x->*member)._next) != LIST_HEAD_MARKER)
            (_head->*member)._prev = LIST_HEAD_MARKER;
        else
            _head = _tail = 0;
        (x->*member)._next = (x->*member)._prev = 0;
    }
 
    void pop_back() {
        assert(_head);
        pointer x = _tail;
        if ((_tail = (x->*member)._prev) != LIST_HEAD_MARKER)
            (_tail->*member)._next = 0;
        else
            _head = _tail = 0;
        (x->*member)._next = (x->*member)._prev = 0;
    }
 
 
    void insert(pointer pos, pointer x) {
        assert(x && isolated(x));
        T **pprev = (pos ? &(pos->*member)._prev : &_tail);
        if (((x->*member)._prev = *pprev) != LIST_HEAD_MARKER)
            ((x->*member)._prev->*member)._next = x;
        else
            _head = x;
        *pprev = x;
        (x->*member)._next = pos;
    }
 
    iterator insert(iterator it, pointer x) {
        insert(it.get(), x);
        return iterator(x);
    }
 
    template <typename InputIterator>
    void insert(iterator it, InputIterator first, InputIterator last) {
        while (first != last) {
            insert(it, *first);
            ++first;
        }
    }
 
 
    void erase(pointer x) {
        assert(x);
        T *n = (x->*member)._next, *p = (x->*member)._prev;
        if (n)
            (n->*member)._prev = p;
        else
            _tail = (p != LIST_HEAD_MARKER ? p : 0);
        if (p != LIST_HEAD_MARKER)
            (p->*member)._next = n;
        else
            _head = n;
        (x->*member)._next = (x->*member)._prev = 0;
    }
 
    iterator erase(iterator it) {
        assert(it);
        iterator next = iterator((it.get()->*member)._next);
        erase(it.get());
        return next;
    }
 
    iterator erase(iterator first, iterator last) {
        while (first != last)
            first = erase(first);
        return first;
    }
 
    void clear() {
        while (T *x = _head) {
            _head = (x->*member)._next;
            (x->*member)._next = (x->*member)._prev = 0;
        }
        _tail = 0;
    }
 
    void __clear() {
        _head = _tail = 0;
    }
 
 
    void swap(List<T, member> &x) {
        T *h = x._head, *t = x._tail;
        x._head = _head, x._tail = _tail;
        _head = h, _tail = t;
    }
 
 
    bool isolated(const_pointer x) {
        return !(x->*member)._next && !(x->*member)._prev && x != _head;
    }
 
    bool contains(const_pointer x) const {
        if (!isolated(x))
            for (const_pointer *it = _head; it; it = (it->*member).next())
                if (x == it)
                    return true;
        return false;
    }
 
 
    class const_iterator { public:
        const_iterator()
            : _x(), _list() {
        }
        const_iterator(const T *x)
            : _x(const_cast<T *>(x)), _list() {
        }
        const_iterator(const List<T, member> *list)
            : _x(), _list(list) {
        }
        const_iterator(const T *x, const List<T, member> *list)
            : _x(const_cast<T *>(x)), _list(list) {
        }
        typedef bool (const_iterator::*unspecified_bool_type)() const;
        operator unspecified_bool_type() const {
            return _x != 0 ? &const_iterator::live : 0;
        }
        bool live() const {
            return _x != 0;
        }
        const T *get() const {
            return _x;
        }
        const T *operator->() const {
            return _x;
        }
        const T &operator*() const {
            return *_x;
        }
        void operator++() {
            assert(_x);
            _x = (_x->*member).next();
        }
        void operator++(int) {
            ++*this;
        }
        void operator--() {
            assert(_x ? (bool) (_x->*member).prev() : _list && _list->back());
            if (_x)
                _x = (_x->*member).prev();
            else
                _x = const_cast<T *>(_list->back());
        }
        void operator--(int) {
            --*this;
        }
        const_iterator &operator+=(int x) {
            for (; x > 0; --x)
                ++*this;
            for (; x < 0; ++x)
                --*this;
            return *this;
        }
        const_iterator &operator-=(int x) {
            for (; x > 0; --x)
                --*this;
            for (; x < 0; ++x)
                ++*this;
            return *this;
        }
        const_iterator operator+(int x) const {
            const_iterator it(*this);
            return it += x;
        }
        const_iterator operator-(int x) const {
            const_iterator it(*this);
            return it -= x;
        }
        bool operator==(const_iterator x) const {
            return _x == x._x;
        }
        bool operator!=(const_iterator x) const {
            return _x != x._x;
        }
      private:
        T *_x;
        const List<T, member> *_list;
        friend class iterator;
    };
 
    class iterator : public const_iterator { public:
        iterator()
            : const_iterator() {
        }
        iterator(T *x)
            : const_iterator(x) {
        }
        iterator(List<T, member> *list)
            : const_iterator(list) {
        }
        iterator(T *x, List<T, member> *list)
            : const_iterator(x, list) {
        }
        T *get() const {
            return this->_x;
        }
        T *operator->() const {
            return this->_x;
        }
        T &operator*() const {
            return *this->_x;
        }
        iterator &operator+=(int x) {
            for (; x > 0; --x)
                ++*this;
            for (; x < 0; ++x)
                --*this;
            return *this;
        }
        iterator &operator-=(int x) {
            for (; x > 0; --x)
                --*this;
            for (; x < 0; ++x)
                ++*this;
            return *this;
        }
        iterator operator+(int x) const {
            iterator it(*this);
            return it += x;
        }
        iterator operator-(int x) const {
            iterator it(*this);
            return it -= x;
        }
    };
 
  private:
 
    T *_head;
    T *_tail;
 
    List(const List<T, member> &x);
    List<T, member> &operator=(const List<T, member> &x);
 
};
 
#undef LIST_HEAD_MARKER
CLICK_ENDDECLS
#endif /* CLICK_LIST_HH */