1 files changed, 63 insertions, 0 deletions
diff --git a/src/util.h b/src/util.h
index e0fa0fd0096..57422526881 100644
--- a/src/util.h
+++ b/src/util.h
@@ -45,6 +45,69 @@ namespace node {
 
 #define UNREACHABLE() abort()
 
+// TAILQ-style intrusive list node.
+template <typename T>
+class ListNode;
+
+template <typename T>
+using ListNodeMember = ListNode<T> T::*;
+
+// VS 2013 doesn't understand dependent templates.
+#ifdef _MSC_VER
+#define ListNodeMember(T) ListNodeMember
+#else
+#define ListNodeMember(T) ListNodeMember<T>
+#endif
+
+// TAILQ-style intrusive list head.
+template <typename T, ListNodeMember(T) M>
+class ListHead;
+
+template <typename T>
+class ListNode {
+ public:
+  inline ListNode();
+  inline ~ListNode();
+  inline void Remove();
+  inline bool IsEmpty() const;
+
+ private:
+  template <typename U, ListNodeMember(U) M> friend class ListHead;
+  ListNode* prev_;
+  ListNode* next_;
+  DISALLOW_COPY_AND_ASSIGN(ListNode);
+};
+
+template <typename T, ListNodeMember(T) M>
+class ListHead {
+ public:
+  class Iterator {
+   public:
+    inline T* operator*() const;
+    inline const Iterator& operator++();
+    inline bool operator!=(const Iterator& that) const;
+
+   private:
+    friend class ListHead;
+    inline explicit Iterator(ListNode<T>* node);
+    ListNode<T>* node_;
+  };
+
+  inline ListHead() = default;
+  inline ~ListHead();
+  inline void MoveBack(ListHead* that);
+  inline void PushBack(T* element);
+  inline void PushFront(T* element);
+  inline bool IsEmpty() const;
+  inline T* PopFront();
+  inline Iterator begin() const;
+  inline Iterator end() const;
+
+ private:
+  ListNode<T> head_;
+  DISALLOW_COPY_AND_ASSIGN(ListHead);
+};
+
 // The helper is for doing safe downcasts from base types to derived types.
 template <typename Inner, typename Outer>
 class ContainerOfHelper {