Create a gist now

Instantly share code, notes, and snippets.

C++ intrusive queue
// 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment