Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
C++ intrusive ordered queue + fast tail inserts
// All rights reserved,
// Derrick Pallas
// License: zlib
#ifndef INTRUSIVE_ORDER_H
#define INTRUSIVE_ORDER_H
#include <cassert>
#include <cstddef>
#include <algorithm>
template <class X>
struct intrusive_order_link {
intrusive_order_link() : p(NULL) { }
~intrusive_order_link() { assert(!p); }
typedef intrusive_order_link type;
template <class T, typename intrusive_order_link<T>::type T::*link,
typename K, K T::*key>
class intrusive_order;
bool bound() const { return p; }
private:
X* p;
};
template <class T, typename intrusive_order_link<T>::type T::*link,
typename K, K T::*key>
class intrusive_order {
public:
intrusive_order() : head(NULL), tail(&head) { }
~intrusive_order() { assert(empty()); }
bool empty() const { return !head; }
intrusive_order & insert(T* t) {
assert(!(t->*link).bound());
assert(!empty() || &head == tail);
if (empty() || !(t->*key < (*tail)->*key)) {
*tail = t;
tail = &(t->*link).p;
*tail = t;
} else {
T ** c;
for (c = &head ; c != tail ; c = &((*c)->*link).p)
if (!((*c)->*key < t->*key))
break;
(t->*link).p = *c;
*c = t;
}
assert((t->*link).bound());
assert(!empty());
return *this;
}
T & front() {
assert(!empty());
return *head;
}
const T & front() const {
assert(!empty());
return *head;
}
T & back() {
assert (!empty());
return **tail;
}
const T & back() const {
assert (!empty());
return **tail;
}
T* remove() {
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_order & merge(intrusive_order & that) {
assert(this != &that);
intrusive_order result;
while (!this->empty() && !that.empty())
result.insert( this->head->*key < that.head->*key
? this->remove()
: that.remove() );
if (!this->empty())
result.chain(*this);
if (!that.empty())
result.chain(that);
swap(result);
return *this;
}
void swap(intrusive_order & that) {
std::swap(this->head, that.head);
std::swap(this->tail, that.tail);
}
private:
intrusive_order(const intrusive_order &);
intrusive_order & operator=(const intrusive_order &);
T * head;
T ** tail;
intrusive_order & chain(intrusive_order & that) {
assert(this != &that);
assert(!that.empty());
*tail = that.head;
tail = that.tail;
assert(!empty());
that.head = NULL;
that.tail = &that.head;
assert(that.empty());
return *this;
}
};
#endif//INTRUSIVE_ORDER
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment