C++ intrusive queue

intrusive_queue.hh

// All rights reserved,
// Derrick Pallas
// License: zlib

#ifndef INTRUSIVE_QUEUE_H
#define INTRUSIVE_QUEUE_H

#include <cassert>
#include <cstddef>

template <class X>
struct intrusive_queue_link {
  intrusive_queue_link() : p(NULL) { }
  ~intrusive_queue_link() { assert(!p); }

  typedef intrusive_queue_link type;
  template <class T, typename intrusive_queue_link<T>::type T::*link>
    friend class intrusive_queue;

  bool bound() const { return p; }

private:
  X* p;
};

template <class T, typename intrusive_queue_link<T>::type T::*link>
class intrusive_queue {
public:
  intrusive_queue() : head(NULL), tail(&head) { }
  ~intrusive_queue() { assert(empty()); }

  bool empty() const { return !head; }

  intrusive_queue & enqueue(T* t) {
    assert(!(t->*link).bound());
    assert(!empty() || &head == tail);

    *tail = t;
    tail = &((t->*link).p);
    *tail = t;

    assert((t->*link).bound());
    assert(!empty());
    return *this;
  }

  T* dequeue() {
    assert(!empty());

    T* t = head;
    assert((t->*link).bound());

    head = *tail != head
         ? (head->*link).p
         : NULL;

    if (empty())
      tail = &head;

    (t->*link).p = NULL;

    assert(!(t->*link).bound());
    return t;
  }

  intrusive_queue & chain(intrusive_queue & that) {
    assert(this != &that);
    assert(!that.empty());
    *tail = that.head;
    tail = that.tail;

    that.head = NULL;
    that.tail = &that.head;

    assert(that.empty());
    return *this;
  }

private:
  intrusive_queue(const intrusive_queue &);
  intrusive_queue & operator=(const intrusive_queue &);

  T * head;
  T ** tail;
};

#endif//INTRUSIVE_QUEUE