blob: 2d9f749f7fab750c213fe480da53de373f765988 [file] [log] [blame]
// Copyright (c) 2019 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef QUICHE_SPDY_CORE_SPDY_INTRUSIVE_LIST_H_
#define QUICHE_SPDY_CORE_SPDY_INTRUSIVE_LIST_H_
// A SpdyIntrusiveList<> is a doubly-linked list where the link pointers are
// embedded in the elements. They are circularly linked making insertion and
// removal into a known position constant time and branch-free operations.
//
// Usage is similar to an STL list<> where feasible, but there are important
// differences. First and foremost, the elements must derive from the
// SpdyIntrusiveLink<> base class:
//
// struct Foo : public SpdyIntrusiveLink<Foo> {
// // ...
// }
//
// SpdyIntrusiveList<Foo> l;
// l.push_back(new Foo);
// l.push_front(new Foo);
// l.erase(&l.front());
// l.erase(&l.back());
//
// Intrusive lists are primarily useful when you would have considered embedding
// link pointers in your class directly for space or performance reasons. An
// SpdyIntrusiveLink<> is the size of 2 pointers, usually 16 bytes on 64-bit
// systems. Intrusive lists do not perform memory allocation (unlike the STL
// list<> class) and thus may use less memory than list<>. In particular, if the
// list elements are pointers to objects, using a list<> would perform an extra
// memory allocation for each list node structure, while an SpdyIntrusiveList<>
// would not.
//
// Note that SpdyIntrusiveLink is exempt from the C++ style guide's limitations
// on multiple inheritance, so it's fine to inherit from both SpdyIntrusiveLink
// and a base class, even if the base class is not a pure interface.
//
// Because the list pointers are embedded in the objects stored in an
// SpdyIntrusiveList<>, erasing an item from a list is constant time. Consider
// the following:
//
// map<string,Foo> foo_map;
// list<Foo*> foo_list;
//
// foo_list.push_back(&foo_map["bar"]);
// foo_list.erase(&foo_map["bar"]); // Compile error!
//
// The problem here is that a Foo* doesn't know where on foo_list it resides,
// so removal requires iteration over the list. Various tricks can be performed
// to overcome this. For example, a foo_list::iterator can be stored inside of
// the Foo object. But at that point you'd be better off using an
// SpdyIntrusiveList<>:
//
// map<string,Foo> foo_map;
// SpdyIntrusiveList<Foo> foo_list;
//
// foo_list.push_back(&foo_map["bar"]);
// foo_list.erase(&foo_map["bar"]); // Yeah!
//
// Note that SpdyIntrusiveLists come with a few limitations. The primary
// limitation is that the SpdyIntrusiveLink<> base class is not copyable or
// assignable. The result is that STL algorithms which mutate the order of
// iterators, such as reverse() and unique(), will not work by default with
// SpdyIntrusiveLists. In order to allow these algorithms to work you'll need to
// define swap() and/or operator= for your class.
//
// Another limitation is that the SpdyIntrusiveList<> structure itself is not
// copyable or assignable since an item/link combination can only exist on one
// SpdyIntrusiveList<> at a time. This limitation is a result of the link
// pointers for an item being intrusive in the item itself. For example, the
// following will not compile:
//
// FooList a;
// FooList b(a); // no copy constructor
// b = a; // no assignment operator
//
// The similar STL code does work since the link pointers are external to the
// item:
//
// list<int*> a;
// a.push_back(new int);
// list<int*> b(a);
// QUICHE_CHECK(a.front() == b.front());
//
// Note that SpdyIntrusiveList::size() runs in O(N) time.
#include <stddef.h>
#include <iterator>
namespace spdy {
template <typename T, typename ListID> class SpdyIntrusiveList;
template <typename T, typename ListID = void> class SpdyIntrusiveLink {
protected:
// We declare the constructor protected so that only derived types and the
// befriended list can construct this.
SpdyIntrusiveLink() : next_(nullptr), prev_(nullptr) {}
#ifndef SWIG
SpdyIntrusiveLink(const SpdyIntrusiveLink&) = delete;
SpdyIntrusiveLink& operator=(const SpdyIntrusiveLink&) = delete;
#endif // SWIG
private:
// We befriend the matching list type so that it can manipulate the links
// while they are kept private from others.
friend class SpdyIntrusiveList<T, ListID>;
// Encapsulates the logic to convert from a link to its derived type.
T* cast_to_derived() { return static_cast<T*>(this); }
const T* cast_to_derived() const { return static_cast<const T*>(this); }
SpdyIntrusiveLink* next_;
SpdyIntrusiveLink* prev_;
};
template <typename T, typename ListID = void> class SpdyIntrusiveList {
template <typename QualifiedT, typename QualifiedLinkT> class iterator_impl;
public:
typedef T value_type;
typedef value_type *pointer;
typedef const value_type *const_pointer;
typedef value_type &reference;
typedef const value_type &const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef SpdyIntrusiveLink<T, ListID> link_type;
typedef iterator_impl<T, link_type> iterator;
typedef iterator_impl<const T, const link_type> const_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
SpdyIntrusiveList() { clear(); }
// After the move constructor the moved-from list will be empty.
//
// NOTE: There is no move assign operator (for now).
// The reason is that at the moment 'clear()' does not unlink the nodes.
// It makes is_linked() return true when it should return false.
// If such node is removed from the list (e.g. from its destructor), or is
// added to another list - a memory corruption will occur.
// Admitedly the destructor does not unlink the nodes either, but move-assign
// will likely make the problem more prominent.
#ifndef SWIG
SpdyIntrusiveList(SpdyIntrusiveList&& src) noexcept {
clear();
if (src.empty()) return;
sentinel_link_.next_ = src.sentinel_link_.next_;
sentinel_link_.prev_ = src.sentinel_link_.prev_;
// Fix head and tail nodes of the list.
sentinel_link_.prev_->next_ = &sentinel_link_;
sentinel_link_.next_->prev_ = &sentinel_link_;
src.clear();
}
#endif // SWIG
iterator begin() { return iterator(sentinel_link_.next_); }
const_iterator begin() const { return const_iterator(sentinel_link_.next_); }
iterator end() { return iterator(&sentinel_link_); }
const_iterator end() const { return const_iterator(&sentinel_link_); }
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const {
return const_reverse_iterator(end());
}
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const {
return const_reverse_iterator(begin());
}
bool empty() const { return (sentinel_link_.next_ == &sentinel_link_); }
// This runs in O(N) time.
size_type size() const { return std::distance(begin(), end()); }
size_type max_size() const { return size_type(-1); }
reference front() { return *begin(); }
const_reference front() const { return *begin(); }
reference back() { return *(--end()); }
const_reference back() const { return *(--end()); }
static iterator insert(iterator position, T *obj) {
return insert_link(position.link(), obj);
}
void push_front(T* obj) { insert(begin(), obj); }
void push_back(T* obj) { insert(end(), obj); }
static iterator erase(T* obj) {
link_type* obj_link = obj;
// Fix up the next and previous links for the previous and next objects.
obj_link->next_->prev_ = obj_link->prev_;
obj_link->prev_->next_ = obj_link->next_;
// Zero out the next and previous links for the removed item. This will
// cause any future attempt to remove the item from the list to cause a
// crash instead of possibly corrupting the list structure.
link_type* next_link = obj_link->next_;
obj_link->next_ = nullptr;
obj_link->prev_ = nullptr;
return iterator(next_link);
}
static iterator erase(iterator position) {
return erase(position.operator->());
}
void pop_front() { erase(begin()); }
void pop_back() { erase(--end()); }
// Check whether the given element is linked into some list. Note that this
// does *not* check whether it is linked into a particular list.
// Also, if clear() is used to clear the containing list, is_linked() will
// still return true even though obj is no longer in any list.
static bool is_linked(const T* obj) {
return obj->link_type::next_ != nullptr;
}
void clear() {
sentinel_link_.next_ = sentinel_link_.prev_ = &sentinel_link_;
}
void swap(SpdyIntrusiveList& x) {
SpdyIntrusiveList tmp;
tmp.splice(tmp.begin(), *this);
this->splice(this->begin(), x);
x.splice(x.begin(), tmp);
}
void splice(iterator pos, SpdyIntrusiveList& src) {
splice(pos, src.begin(), src.end());
}
void splice(iterator pos, iterator i) { splice(pos, i, std::next(i)); }
void splice(iterator pos, iterator first, iterator last) {
if (first == last) return;
link_type* const last_prev = last.link()->prev_;
// Remove from the source.
first.link()->prev_->next_ = last.operator->();
last.link()->prev_ = first.link()->prev_;
// Attach to the destination.
first.link()->prev_ = pos.link()->prev_;
pos.link()->prev_->next_ = first.operator->();
last_prev->next_ = pos.operator->();
pos.link()->prev_ = last_prev;
}
private:
static iterator insert_link(link_type* next_link, T* obj) {
link_type* obj_link = obj;
obj_link->next_ = next_link;
link_type* const initial_next_prev = next_link->prev_;
obj_link->prev_ = initial_next_prev;
initial_next_prev->next_ = obj_link;
next_link->prev_ = obj_link;
return iterator(obj_link);
}
// The iterator implementation is parameterized on a potentially qualified
// variant of T and the matching qualified link type. Essentially, QualifiedT
// will either be 'T' or 'const T', the latter for a const_iterator.
template <typename QualifiedT, typename QualifiedLinkT>
class iterator_impl : public std::iterator<std::bidirectional_iterator_tag,
QualifiedT> {
public:
typedef std::iterator<std::bidirectional_iterator_tag, QualifiedT> base;
iterator_impl() : link_(nullptr) {}
iterator_impl(QualifiedLinkT* link) : link_(link) {}
iterator_impl(const iterator_impl& x) : link_(x.link_) {}
// Allow converting and comparing across iterators where the pointer
// assignment and comparisons (respectively) are allowed.
template <typename U, typename V>
iterator_impl(const iterator_impl<U, V>& x) : link_(x.link_) {}
template <typename U, typename V>
bool operator==(const iterator_impl<U, V>& x) const {
return link_ == x.link_;
}
template <typename U, typename V>
bool operator!=(const iterator_impl<U, V>& x) const {
return link_ != x.link_;
}
typename base::reference operator*() const { return *operator->(); }
typename base::pointer operator->() const {
return link_->cast_to_derived();
}
QualifiedLinkT *link() const { return link_; }
#ifndef SWIG // SWIG can't wrap these operator overloads.
iterator_impl& operator++() { link_ = link_->next_; return *this; }
iterator_impl operator++(int /*unused*/) {
iterator_impl tmp = *this;
++*this;
return tmp;
}
iterator_impl& operator--() { link_ = link_->prev_; return *this; }
iterator_impl operator--(int /*unused*/) {
iterator_impl tmp = *this;
--*this;
return tmp;
}
#endif // SWIG
private:
// Ensure iterators can access other iterators node directly.
template <typename U, typename V> friend class iterator_impl;
QualifiedLinkT* link_;
};
// This bare link acts as the sentinel node.
link_type sentinel_link_;
// These are private and undefined to prevent copying and assigning.
SpdyIntrusiveList(const SpdyIntrusiveList&);
void operator=(const SpdyIntrusiveList&);
};
} // namespace spdy
#endif // QUICHE_SPDY_CORE_SPDY_INTRUSIVE_LIST_H_