list.hh

Click is a modular router toolkit. To use it you ll need to know how to compile and install the sof

	return iterator(x);
    }

    /** @brief Insert the elements in [@a first, @a last) before @a it.
     * @param it position to insert
     * @param first iterator to beginning of insertion sequence
     * @param last iterator to end of insertion sequence
     * @pre isolated(@a x) for each @a x in [@a first, @a last) */
    template <typename InputIterator>
    void insert(iterator it, InputIterator first, InputIterator last) {
	while (first != last) {
	    insert(it, *first);
	    ++first;
	}
    }


    /** @brief Remove @a x from the list.
     * @param x element to remove
     * @pre contains(@a x) */
    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;
    }

    /** @brief Remove the element pointed to by @a it from the list.
     * @param it element to remove
     * @return iterator pointing to the element after the removed element
     * @pre @a it.live() */
    iterator erase(iterator it) {
	assert(it);
	iterator next = iterator((it.get()->*member)._next);
	erase(it.get());
	return next;
    }

    /** @brief Remove the elements in [@a first, @a last) from the list.
     * @param first iterator to beginning of removal subsequence
     * @param last iterator to end of removal subsequence
     * @return iterator pointing to the element after the removed subsequence */
    iterator erase(iterator first, iterator last) {
	while (first != last)
	    first = erase(first);
	return first;
    }

    /** @brief Remove all elements from the list.
     * @note Equivalent to erase(begin(), end()). */
    void clear() {
	while (T *x = _head) {
	    _head = (x->*member)._next;
	    (x->*member)._next = (x->*member)._prev = 0;
	}
	_tail = 0;
    }

    /** @brief Remove all elements from the list.
     *
     * Unlike clear(), this function does not erase() any of the elements of
     * this list: those elements' next() and prev() members remain
     * unchanged. */
    void __clear() {
	_head = _tail = 0;
    }


    /** @brief Exchange list contents with list @a x. */
    void swap(List<T, member> &x) {
	T *h = x._head, *t = x._tail;
	x._head = _head, x._tail = _tail;
	_head = h, _tail = t;
    }


    /** @brief Check if @a x is isolated.
     *
     * An isolated element is not a member of any list. */
    bool isolated(const_pointer x) {
	return !(x->*member)._next && !(x->*member)._prev && x != _head;
    }

    /** @brief Check if @a x is a member of this list. */
    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 List::const_iterator
     * @brief Const iterator type for List. */
    class const_iterator { public:
	/** @brief Construct an invalid iterator. */
	const_iterator()
	    : _x(), _list() {
	}
	/** @brief Construct an iterator pointing at @a x. */
	const_iterator(const T *x)
	    : _x(const_cast<T *>(x)), _list() {
	}
	/** @brief Construct an end iterator for @a list. */
	const_iterator(const List<T, member> *list)
	    : _x(), _list(list) {
	}
	/** @brief Construct an iterator pointing at @a x in @a 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;
	/** @brief Test if this iterator points to a valid list element. */
	operator unspecified_bool_type() const {
	    return _x != 0 ? &const_iterator::live : 0;
	}
	/** @brief Test if this iterator points to a valid list element. */
	bool live() const {
	    return _x != 0;
	}
	/** @brief Return the current list element or null. */
	const T *get() const {
	    return _x;
	}
	/** @brief Return the current list element or null. */
	const T *operator->() const {
	    return _x;
	}
	/** @brief Return the current list element. */
	const T &operator*() const {
	    return *_x;
	}
	/** @brief Advance this iterator to the next element. */
	void operator++() {
	    assert(_x);
	    _x = (_x->*member).next();
	}
	/** @brief Advance this iterator to the next element. */
	void operator++(int) {
	    ++*this;
	}
	/** @brief Advance this iterator to the previous element. */
	void operator--() {
	    assert(_x ? (bool) (_x->*member).prev() : _list && _list->back());
	    if (_x)
		_x = (_x->*member).prev();
	    else
		_x = const_cast<T *>(_list->back());
	}
	/** @brief Advance this iterator to the previous element. */
	void operator--(int) {
	    --*this;
	}
	/** @brief Move this iterator forward by @a x positions.
	 * @return reference to this iterator
	 * @note This function takes O(abs(@a x)) time. */
	const_iterator &operator+=(int x) {
	    for (; x > 0; --x)
		++*this;
	    for (; x < 0; ++x)
		--*this;
	    return *this;
	}
	/** @brief Move this iterator backward by @a x positions.
	 * @return reference to this iterator
	 * @note This function takes O(abs(@a x)) time. */
	const_iterator &operator-=(int x) {
	    for (; x > 0; --x)
		--*this;
	    for (; x < 0; ++x)
		++*this;
	    return *this;
	}
	/** @brief Return an iterator @a x positions ahead. */
	const_iterator operator+(int x) const {
	    const_iterator it(*this);
	    return it += x;
	}
	/** @brief Return an iterator @a x positions behind. */
	const_iterator operator-(int x) const {
	    const_iterator it(*this);
	    return it -= x;
	}
	/** @brief Test if this iterator equals @a x. */
	bool operator==(const_iterator x) const {
	    return _x == x._x;
	}
	/** @brief Test if this iterator does not equal @a x. */
	bool operator!=(const_iterator x) const {
	    return _x != x._x;
	}
      private:
	T *_x;
	const List<T, member> *_list;
	friend class iterator;
    };

    /** @class List::iterator
     * @brief Iterator type for List. */
    class iterator : public const_iterator { public:
	/** @brief Construct an invalid iterator. */
	iterator()
	    : const_iterator() {
	}
	/** @brief Construct an iterator pointing at @a x. */
	iterator(T *x)
	    : const_iterator(x) {
	}
	/** @brief Construct an end iterator for @a list. */
	iterator(List<T, member> *list)
	    : const_iterator(list) {
	}
	/** @brief Construct an iterator pointing at @a x in @a list. */
	iterator(T *x, List<T, member> *list)
	    : const_iterator(x, list) {
	}
	/** @brief Return the current list element or null. */
	T *get() const {
	    return this->_x;
	}
	/** @brief Return the current list element or null. */
	T *operator->() const {
	    return this->_x;
	}
	/** @brief Return the current list element. */
	T &operator*() const {
	    return *this->_x;
	}
	/** @brief Move this iterator forward by @a x positions.
	 * @return reference to this iterator
	 * @note This function takes O(abs(@a x)) time. */
	iterator &operator+=(int x) {
	    for (; x > 0; --x)
		++*this;
	    for (; x < 0; ++x)
		--*this;
	    return *this;
	}
	/** @brief Move this iterator backward by @a x positions.
	 * @return reference to this iterator
	 * @note This function takes O(abs(@a x)) time. */
	iterator &operator-=(int x) {
	    for (; x > 0; --x)
		--*this;
	    for (; x < 0; ++x)
		++*this;
	    return *this;
	}
	/** @brief Return an iterator @a x positions ahead. */
	iterator operator+(int x) const {
	    iterator it(*this);
	    return it += x;
	}
	/** @brief Return an iterator @a x positions behind. */
	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 */