Source code
Revision control
Copy as Markdown
Other Tools
/*
* Copyright 2017 WebAssembly Community Group participants
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef WABT_INTRUSIVE_LIST_H_
#define WABT_INTRUSIVE_LIST_H_
#include <cassert>
#include <iterator>
#include <memory>
// This uses a similar interface as std::list, but is missing the following
// features:
//
// * Add "extract_" functions that remove an element from the list and return
// it.
// * Only supports move-only operations
// * No allocator support
// * No initializer lists
// * Asserts instead of exceptions
// * Some functions are not implemented (merge, remove, remove_if, reverse,
// unique, sort, non-member comparison operators)
namespace wabt {
template <typename T>
class intrusive_list;
template <typename T>
class intrusive_list_base {
private:
friend class intrusive_list<T>;
mutable T* next_ = nullptr;
mutable T* prev_ = nullptr;
};
template <typename T>
class intrusive_list {
public:
// types:
using value_type = T;
using reference = value_type&;
using const_reference = const value_type&;
class iterator;
class const_iterator;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
// construct/copy/destroy:
intrusive_list();
explicit intrusive_list(std::unique_ptr<T> node);
explicit intrusive_list(T&& node);
intrusive_list(const intrusive_list&) = delete;
intrusive_list(intrusive_list&&);
~intrusive_list();
intrusive_list& operator=(const intrusive_list& other) = delete;
intrusive_list& operator=(intrusive_list&& other);
// iterators:
iterator begin() noexcept;
const_iterator begin() const noexcept;
iterator end() noexcept;
const_iterator end() const noexcept;
reverse_iterator rbegin() noexcept;
const_reverse_iterator rbegin() const noexcept;
reverse_iterator rend() noexcept;
const_reverse_iterator rend() const noexcept;
const_iterator cbegin() const noexcept;
const_iterator cend() const noexcept;
const_reverse_iterator crbegin() const noexcept;
const_reverse_iterator crend() const noexcept;
// capacity:
size_type size() const noexcept;
bool empty() const noexcept;
// element access:
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// modifiers:
template <class... Args>
void emplace_front(Args&&... args);
template <class... Args>
void emplace_back(Args&&... args);
void push_front(std::unique_ptr<T> node);
void push_front(T&& node);
void push_back(std::unique_ptr<T> node);
void push_back(T&& node);
void pop_front();
void pop_back();
std::unique_ptr<T> extract_front();
std::unique_ptr<T> extract_back();
template <class... Args>
iterator emplace(iterator pos, Args&&... args);
iterator insert(iterator pos, std::unique_ptr<T> node);
iterator insert(iterator pos, T&& node);
std::unique_ptr<T> extract(iterator it);
iterator erase(iterator pos);
iterator erase(iterator first, iterator last);
void swap(intrusive_list&);
void clear() noexcept;
void splice(iterator pos, intrusive_list& node);
void splice(iterator pos, intrusive_list&& node);
void splice(iterator pos, intrusive_list& node, iterator it);
void splice(iterator pos,
intrusive_list& node,
iterator first,
iterator last);
private:
T* first_ = nullptr;
T* last_ = nullptr;
size_t size_ = 0;
};
/// iterator
template <typename T>
class intrusive_list<T>::iterator {
public:
using difference_type = std::ptrdiff_t;
using iterator_category = std::bidirectional_iterator_tag;
using value_type = T;
using pointer = T*;
using reference = T&;
iterator(const intrusive_list<T>& list, T* node)
: list_(&list), node_(node) {}
reference operator*() const {
assert(node_);
return *node_;
}
pointer operator->() const {
assert(node_);
return node_;
}
iterator& operator++() {
assert(node_);
node_ = node_->next_;
return *this;
}
iterator operator++(int) {
iterator tmp = *this;
operator++();
return tmp;
}
iterator& operator--() {
node_ = node_ ? node_->prev_ : list_->last_;
return *this;
}
iterator operator--(int) {
iterator tmp = *this;
operator--();
return tmp;
}
bool operator==(iterator rhs) const {
assert(list_ == rhs.list_);
return node_ == rhs.node_;
}
bool operator!=(iterator rhs) const {
assert(list_ == rhs.list_);
return node_ != rhs.node_;
}
private:
friend class const_iterator;
const intrusive_list<T>* list_;
T* node_;
};
/// const_iterator
template <typename T>
class intrusive_list<T>::const_iterator {
public:
using difference_type = std::ptrdiff_t;
using iterator_category = std::bidirectional_iterator_tag;
using value_type = T;
using pointer = const T*;
using reference = const T&;
const_iterator(const intrusive_list<T>& list, T* node)
: list_(&list), node_(node) {}
const_iterator(const iterator& other)
: list_(other.list_), node_(other.node_) {}
reference operator*() const {
assert(node_);
return *node_;
}
pointer operator->() const {
assert(node_);
return node_;
}
const_iterator& operator++() {
assert(node_);
node_ = node_->next_;
return *this;
}
const_iterator operator++(int) {
const_iterator tmp = *this;
operator++();
return tmp;
}
const_iterator& operator--() {
node_ = node_ ? node_->prev_ : list_->last_;
return *this;
}
const_iterator operator--(int) {
const_iterator tmp = *this;
operator--();
return tmp;
}
bool operator==(const_iterator rhs) const {
assert(list_ == rhs.list_);
return node_ == rhs.node_;
}
bool operator!=(const_iterator rhs) const {
assert(list_ == rhs.list_);
return node_ != rhs.node_;
}
private:
const intrusive_list<T>* list_;
T* node_;
};
template <typename T>
inline intrusive_list<T>::intrusive_list() {}
template <typename T>
inline intrusive_list<T>::intrusive_list(std::unique_ptr<T> node) {
push_back(std::move(node));
}
template <typename T>
inline intrusive_list<T>::intrusive_list(T&& node) {
push_back(std::move(node));
}
template <typename T>
inline intrusive_list<T>::intrusive_list(intrusive_list&& other)
: first_(other.first_), last_(other.last_), size_(other.size_) {
other.first_ = other.last_ = nullptr;
other.size_ = 0;
}
template <typename T>
inline intrusive_list<T>::~intrusive_list() {
clear();
}
template <typename T>
inline intrusive_list<T>& intrusive_list<T>::operator=(
intrusive_list<T>&& other) {
clear();
first_ = other.first_;
last_ = other.last_;
size_ = other.size_;
other.first_ = other.last_ = nullptr;
other.size_ = 0;
return *this;
}
template <typename T>
inline typename intrusive_list<T>::iterator
intrusive_list<T>::begin() noexcept {
return iterator(*this, first_);
}
template <typename T>
inline typename intrusive_list<T>::const_iterator intrusive_list<T>::begin()
const noexcept {
return const_iterator(*this, first_);
}
template <typename T>
inline typename intrusive_list<T>::iterator intrusive_list<T>::end() noexcept {
return iterator(*this, nullptr);
}
template <typename T>
inline typename intrusive_list<T>::const_iterator intrusive_list<T>::end()
const noexcept {
return const_iterator(*this, nullptr);
}
template <typename T>
inline typename intrusive_list<T>::reverse_iterator
intrusive_list<T>::rbegin() noexcept {
return reverse_iterator(iterator(*this, nullptr));
}
template <typename T>
inline typename intrusive_list<T>::const_reverse_iterator
intrusive_list<T>::rbegin() const noexcept {
return const_reverse_iterator(const_iterator(*this, nullptr));
}
template <typename T>
inline typename intrusive_list<T>::reverse_iterator
intrusive_list<T>::rend() noexcept {
return reverse_iterator(iterator(*this, first_));
}
template <typename T>
inline typename intrusive_list<T>::const_reverse_iterator
intrusive_list<T>::rend() const noexcept {
return const_reverse_iterator(const_iterator(*this, first_));
}
template <typename T>
inline typename intrusive_list<T>::const_iterator intrusive_list<T>::cbegin()
const noexcept {
return const_iterator(*this, first_);
}
template <typename T>
inline typename intrusive_list<T>::const_iterator intrusive_list<T>::cend()
const noexcept {
return const_iterator(*this, nullptr);
}
template <typename T>
inline typename intrusive_list<T>::const_reverse_iterator
intrusive_list<T>::crbegin() const noexcept {
return const_reverse_iterator(const_iterator(*this, nullptr));
}
template <typename T>
inline typename intrusive_list<T>::const_reverse_iterator
intrusive_list<T>::crend() const noexcept {
return const_reverse_iterator(const_iterator(*this, first_));
}
template <typename T>
inline typename intrusive_list<T>::size_type intrusive_list<T>::size()
const noexcept {
return size_;
}
template <typename T>
inline bool intrusive_list<T>::empty() const noexcept {
return size_ == 0;
}
template <typename T>
inline typename intrusive_list<T>::reference intrusive_list<T>::front() {
assert(!empty());
return *first_;
}
template <typename T>
inline typename intrusive_list<T>::const_reference intrusive_list<T>::front()
const {
assert(!empty());
return *first_;
}
template <typename T>
inline typename intrusive_list<T>::reference intrusive_list<T>::back() {
assert(!empty());
return *last_;
}
template <typename T>
inline typename intrusive_list<T>::const_reference intrusive_list<T>::back()
const {
assert(!empty());
return *last_;
}
template <typename T>
template <class... Args>
inline void intrusive_list<T>::emplace_front(Args&&... args) {
push_front(std::make_unique<T>(std::forward<Args>(args)...));
}
template <typename T>
template <class... Args>
inline void intrusive_list<T>::emplace_back(Args&&... args) {
push_back(std::make_unique<T>(std::forward<Args>(args)...));
}
template <typename T>
inline void intrusive_list<T>::push_front(std::unique_ptr<T> node) {
assert(node->prev_ == nullptr && node->next_ == nullptr);
T* node_p = node.release();
if (first_) {
node_p->next_ = first_;
first_->prev_ = node_p;
} else {
last_ = node_p;
}
first_ = node_p;
size_++;
}
template <typename T>
inline void intrusive_list<T>::push_front(T&& node) {
push_front(std::make_unique<T>(std::move(node)));
}
template <typename T>
inline void intrusive_list<T>::push_back(std::unique_ptr<T> node) {
assert(node->prev_ == nullptr && node->next_ == nullptr);
T* node_p = node.release();
if (last_) {
node_p->prev_ = last_;
last_->next_ = node_p;
} else {
first_ = node_p;
}
last_ = node_p;
size_++;
}
template <typename T>
inline void intrusive_list<T>::push_back(T&& node) {
push_back(std::make_unique<T>(std::move(node)));
}
template <typename T>
inline void intrusive_list<T>::pop_front() {
extract_front();
}
template <typename T>
inline void intrusive_list<T>::pop_back() {
extract_back();
}
template <typename T>
inline std::unique_ptr<T> intrusive_list<T>::extract_front() {
assert(!empty());
T* node = first_;
if (first_ == last_) {
first_ = last_ = nullptr;
} else {
first_ = first_->next_;
first_->prev_ = nullptr;
}
node->next_ = node->prev_ = nullptr;
size_--;
return std::unique_ptr<T>(node);
}
template <typename T>
inline std::unique_ptr<T> intrusive_list<T>::extract_back() {
assert(!empty());
T* node = last_;
if (first_ == last_) {
first_ = last_ = nullptr;
} else {
last_ = last_->prev_;
last_->next_ = nullptr;
}
node->next_ = node->prev_ = nullptr;
size_--;
return std::unique_ptr<T>(node);
}
template <typename T>
template <class... Args>
inline typename intrusive_list<T>::iterator intrusive_list<T>::emplace(
iterator pos,
Args&&... args) {
return insert(pos, std::make_unique<T>(std::forward<Args>(args)...));
}
template <typename T>
inline typename intrusive_list<T>::iterator intrusive_list<T>::insert(
iterator pos,
std::unique_ptr<T> node) {
assert(node->prev_ == nullptr && node->next_ == nullptr);
T* node_p;
if (pos == end()) {
push_back(std::move(node));
node_p = &back();
} else {
node_p = node.release();
node_p->prev_ = pos->prev_;
node_p->next_ = &*pos;
if (pos->prev_) {
pos->prev_->next_ = node_p;
} else {
first_ = node_p;
}
pos->prev_ = node_p;
size_++;
}
return iterator(*this, node_p);
}
template <typename T>
inline typename intrusive_list<T>::iterator intrusive_list<T>::insert(
iterator pos,
T&& node) {
return insert(pos, std::make_unique<T>(std::move(node)));
}
template <typename T>
inline std::unique_ptr<T> intrusive_list<T>::extract(iterator pos) {
assert(!empty());
assert(pos != end());
T* node = &*pos;
if (first_ == last_) {
first_ = last_ = nullptr;
} else {
if (node->prev_) {
node->prev_->next_ = node->next_;
} else {
first_ = node->next_;
}
if (node->next_) {
node->next_->prev_ = node->prev_;
} else {
last_ = node->prev_;
}
}
node->next_ = node->prev_ = nullptr;
size_--;
return std::unique_ptr<T>(node);
}
template <typename T>
inline typename intrusive_list<T>::iterator intrusive_list<T>::erase(
iterator pos) {
iterator next = std::next(pos);
extract(pos);
return next;
}
template <typename T>
inline typename intrusive_list<T>::iterator intrusive_list<T>::erase(
iterator first,
iterator last) {
while (first != last)
first = erase(first);
return first;
}
template <typename T>
inline void intrusive_list<T>::swap(intrusive_list& other) {
std::swap(first_, other.first_);
std::swap(last_, other.last_);
std::swap(size_, other.size_);
}
template <typename T>
inline void intrusive_list<T>::clear() noexcept {
for (T* iter = first_; iter;) {
T* next = iter->next_;
delete iter;
iter = next;
}
first_ = last_ = nullptr;
size_ = 0;
}
template <typename T>
inline void intrusive_list<T>::splice(iterator pos, intrusive_list& other) {
splice(pos, other, other.begin(), other.end());
}
template <typename T>
inline void intrusive_list<T>::splice(iterator pos, intrusive_list&& other) {
splice(pos, other, other.begin(), other.end());
}
template <typename T>
inline void intrusive_list<T>::splice(iterator pos,
intrusive_list& other,
iterator it) {
insert(pos, other.extract(it));
}
template <typename T>
inline void intrusive_list<T>::splice(iterator pos,
intrusive_list& other,
iterator first,
iterator last) {
while (first != last)
insert(pos, other.extract(first++));
}
} // namespace wabt
#endif // WABT_INTRUSIVE_LIST_H_