src: add typesafe intrusive list

This is a replacement for the QUEUE macros.  It implements the same
functionality but in a way that lets the compiler typecheck it.

PR-URL: https://github.com/iojs/io.js/pull/667
Reviewed-By: Bert Belder <bertbelder@gmail.com>
Reviewed-By: Fedor Indutny <fedor.indutny@gmail.com>
Reviewed-By: Trevor Norris <trev.norris@gmail.com>

1 files changed, 102 insertions, 0 deletions

diff --git a/src/util-inl.h b/src/util-inl.h
index 6e962feffaf..75bdb4784aa 100644
--- a/src/util-inl.h
+++ b/src/util-inl.h
@@ -5,6 +5,108 @@
 
 namespace node {
 
+template <typename T>
+ListNode<T>::ListNode() : prev_(this), next_(this) {}
+
+template <typename T>
+ListNode<T>::~ListNode() {
+  Remove();
+}
+
+template <typename T>
+void ListNode<T>::Remove() {
+  prev_->next_ = next_;
+  next_->prev_ = prev_;
+  prev_ = this;
+  next_ = this;
+}
+
+template <typename T>
+bool ListNode<T>::IsEmpty() const {
+  return prev_ == this;
+}
+
+template <typename T, ListNodeMember(T) M>
+ListHead<T, M>::Iterator::Iterator(ListNode<T>* node) : node_(node) {}
+
+template <typename T, ListNodeMember(T) M>
+T* ListHead<T, M>::Iterator::operator*() const {
+  return ContainerOf(M, node_);
+}
+
+template <typename T, ListNodeMember(T) M>
+const typename ListHead<T, M>::Iterator&
+ListHead<T, M>::Iterator::operator++() {
+  node_ = node_->next_;
+  return *this;
+}
+
+template <typename T, ListNodeMember(T) M>
+bool ListHead<T, M>::Iterator::operator!=(const Iterator& that) const {
+  return node_ != that.node_;
+}
+
+template <typename T, ListNodeMember(T) M>
+ListHead<T, M>::~ListHead() {
+  while (IsEmpty() == false)
+    head_.next_->Remove();
+}
+
+template <typename T, ListNodeMember(T) M>
+void ListHead<T, M>::MoveBack(ListHead* that) {
+  if (IsEmpty())
+    return;
+  ListNode<T>* to = &that->head_;
+  head_.next_->prev_ = to->prev_;
+  to->prev_->next_ = head_.next_;
+  head_.prev_->next_ = to;
+  to->prev_ = head_.prev_;
+  head_.prev_ = &head_;
+  head_.next_ = &head_;
+}
+
+template <typename T, ListNodeMember(T) M>
+void ListHead<T, M>::PushBack(T* element) {
+  ListNode<T>* that = &(element->*M);
+  head_.prev_->next_ = that;
+  that->prev_ = head_.prev_;
+  that->next_ = &head_;
+  head_.prev_ = that;
+}
+
+template <typename T, ListNodeMember(T) M>
+void ListHead<T, M>::PushFront(T* element) {
+  ListNode<T>* that = &(element->*M);
+  head_.next_->prev_ = that;
+  that->prev_ = &head_;
+  that->next_ = head_.next_;
+  head_.next_ = that;
+}
+
+template <typename T, ListNodeMember(T) M>
+bool ListHead<T, M>::IsEmpty() const {
+  return head_.IsEmpty();
+}
+
+template <typename T, ListNodeMember(T) M>
+T* ListHead<T, M>::PopFront() {
+  if (IsEmpty())
+    return nullptr;
+  ListNode<T>* node = head_.next_;
+  node->Remove();
+  return ContainerOf(M, node);
+}
+
+template <typename T, ListNodeMember(T) M>
+typename ListHead<T, M>::Iterator ListHead<T, M>::begin() const {
+  return Iterator(head_.next_);
+}
+
+template <typename T, ListNodeMember(T) M>
+typename ListHead<T, M>::Iterator ListHead<T, M>::end() const {
+  return Iterator(const_cast<ListNode<T>*>(&head_));
+}
+
 template <typename Inner, typename Outer>
 ContainerOfHelper<Inner, Outer>::ContainerOfHelper(Inner Outer::*field,
                                                    Inner* pointer)