Add intrusive_list_tail container that maintains a pointer to the last element

2 files changed, 49 insertions, 0 deletions

diff --git a/include/intrusive_list.h b/include/intrusive_list.h
index 7a127eb58..88f3c6829 100644
--- a/include/intrusive_list.h
+++ b/include/intrusive_list.h
@@ -24,6 +24,7 @@
 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> class intrusive_list_tail;
 
 template <typename T, typename Tag = intrusive_list_def_tag>
 class intrusive_list_node
@@ -48,8 +49,18 @@ class intrusive_list_node
 	}
 
 	friend class intrusive_list<T, Tag>;
+	friend class intrusive_list_tail<T, Tag>;
 };
 
+// Intrusive list where the list only has a pointer to the head element
 #define INSPIRCD_INTRUSIVE_LIST_NAME intrusive_list
 #include "intrusive_list_impl.h"
 #undef INSPIRCD_INTRUSIVE_LIST_NAME
+
+// Intrusive list where the list maintains a pointer to both the head and the tail elements.
+// Additional methods: back(), push_back(), pop_back()
+#define INSPIRCD_INTRUSIVE_LIST_NAME intrusive_list_tail
+#define INSPIRCD_INTRUSIVE_LIST_HAS_TAIL
+#include "intrusive_list_impl.h"
+#undef INSPIRCD_INTRUSIVE_LIST_NAME
+#undef INSPIRCD_INTRUSIVE_LIST_HAS_TAIL
diff --git a/include/intrusive_list_impl.h b/include/intrusive_list_impl.h
index 41fc72a1f..0efe06d2e 100644
--- a/include/intrusive_list_impl.h
+++ b/include/intrusive_list_impl.h
@@ -66,6 +66,9 @@ class INSPIRCD_INTRUSIVE_LIST_NAME
 
 	INSPIRCD_INTRUSIVE_LIST_NAME()
 		: listhead(NULL)
+#ifdef INSPIRCD_INTRUSIVE_LIST_HAS_TAIL
+		, listtail(NULL)
+#endif
 		, listsize(0)
 	{
 	}
@@ -107,9 +110,37 @@ class INSPIRCD_INTRUSIVE_LIST_NAME
 			x->intrusive_list_node<T, Tag>::ptr_next = listhead;
 			listhead->intrusive_list_node<T, Tag>::ptr_prev = x;
 		}
+#ifdef INSPIRCD_INTRUSIVE_LIST_HAS_TAIL
+		else
+			listtail = x;
+#endif
 		listhead = x;
 	}
 
+#ifdef INSPIRCD_INTRUSIVE_LIST_HAS_TAIL
+	T* back() const
+	{
+		return listtail;
+	}
+
+	void push_back(T* x)
+	{
+		if (listsize++)
+		{
+			x->intrusive_list_node<T, Tag>::ptr_prev = listtail;
+			listtail->intrusive_list_node<T, Tag>::ptr_next = x;
+		}
+		else
+			listhead = x;
+		listtail = x;
+	}
+
+	void pop_back()
+	{
+		erase(listtail);
+	}
+#endif
+
 	void erase(const iterator& it)
 	{
 		erase(*it);
@@ -119,11 +150,18 @@ class INSPIRCD_INTRUSIVE_LIST_NAME
 	{
 		if (listhead == x)
 			listhead = x->intrusive_list_node<T, Tag>::ptr_next;
+#ifdef INSPIRCD_INTRUSIVE_LIST_HAS_TAIL
+		if (listtail == x)
+			listtail = x->intrusive_list_node<T, Tag>::ptr_prev;
+#endif
 		x->intrusive_list_node<T, Tag>::unlink();
 		listsize--;
 	}
 
  private:
 	T* listhead;
+#ifdef INSPIRCD_INTRUSIVE_LIST_HAS_TAIL
+	T* listtail;
+#endif
 	size_t listsize;
 };