summaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
authorAttila Molnar <attilamolnar@hush.com>2014-01-24 12:37:43 +0100
committerAttila Molnar <attilamolnar@hush.com>2014-01-24 12:37:43 +0100
commit9a962e1c512ffc00bcfce105e9dbdabd9abcdd86 (patch)
tree9b8f7c3c27200c65c9533e2a62469bd8ac448ca6 /include
parentd02011d69fe1e52ec0bc38051eff9ea93a1cc88c (diff)
Add intrusive list template
Diffstat (limited to 'include')
-rw-r--r--include/intrusive_list.h162
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;
+};