diff options
| -rw-r--r-- | include/intrusive_list.h | 162 |
1 files changed, 162 insertions, 0 deletions
diff --git a/include/intrusive_list.h b/include/intrusive_list.h new file mode 100644 index 000000000..399dc33e8 --- /dev/null +++ b/include/intrusive_list.h @@ -0,0 +1,162 @@ +/* + * InspIRCd -- Internet Relay Chat Daemon + * + * Copyright (C) 2013-2014 Attila Molnar <attilamolnar@hush.com> + * + * This file is part of InspIRCd. InspIRCd is free software: you can + * redistribute it and/or modify it under the terms of the GNU General Public + * License as published by the Free Software Foundation, version 2. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more + * details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + + +#pragma once + +#include <iterator> + +struct intrusive_list_def_tag { }; + +template <typename T, typename Tag = intrusive_list_def_tag> class intrusive_list; + +template <typename T, typename Tag = intrusive_list_def_tag> +struct intrusive_list_node +{ + T* ptr_next; + T* ptr_prev; + + void unlink() + { + if (ptr_next) + ptr_next->intrusive_list_node<T, Tag>::ptr_prev = this->ptr_prev; + if (ptr_prev) + ptr_prev->intrusive_list_node<T, Tag>::ptr_next = this->ptr_next; + ptr_next = ptr_prev = NULL; + } + + public: + intrusive_list_node() + : ptr_next(NULL) + , ptr_prev(NULL) + { + } + + friend class intrusive_list<T, Tag>; +}; + +template <typename T, typename Tag> +class intrusive_list +{ + public: + class iterator : public std::iterator<std::bidirectional_iterator_tag, T*> + { + T* curr; + + public: + iterator(T* i = NULL) + : curr(i) + { + } + + iterator& operator++() + { + curr = curr->intrusive_list_node<T, Tag>::ptr_next; + return *this; + } + + iterator operator++(int) + { + iterator ret(*this); + operator++(); + return ret; + } + + void operator--() + { + curr = curr->intrusive_list_node<T, Tag>::ptr_prev; + return *this; + } + + iterator operator--(int) + { + iterator ret(*this); + operator--(); + return ret; + } + + bool operator==(const iterator& other) const { return (curr == other.curr); } + bool operator!=(const iterator& other) const { return (curr != other.curr); } + T* operator*() const { return curr; } + }; + + typedef iterator const_iterator; + + intrusive_list() + : listhead(NULL) + , listsize(0) + { + } + + bool empty() const + { + return (size() == 0); + } + + size_t size() const + { + return listsize; + } + + iterator begin() const + { + return iterator(listhead); + } + + iterator end() const + { + return iterator(); + } + + void pop_front() + { + erase(listhead); + } + + T* front() const + { + return listhead; + } + + void push_front(T* x) + { + if (listsize++) + { + x->intrusive_list_node<T, Tag>::ptr_next = listhead; + listhead->intrusive_list_node<T, Tag>::ptr_prev = x; + } + listhead = x; + } + + void erase(const iterator& it) + { + erase(*it); + } + + void erase(T* x) + { + if (listhead == x) + listhead = x->intrusive_list_node<T, Tag>::ptr_next; + x->intrusive_list_node<T, Tag>::unlink(); + listsize--; + } + + private: + T* listhead; + size_t listsize; +}; |