Source code
Revision control
Copy as Markdown
Other Tools
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
/*
* The classes SlimLinkedList<T> and SlimLinkedListElement<T> provide a
* type-safe doubly-linked list class which uses one word for the list and two
* words for each element (for comparison mozilla::LinkedList uses three words
* for the list and for each element due to padding).
*
* This aims to be a replacement for mozilla::LinkedList although the interface
* is not identical. In particular most actions are implemented as methods on
* the list itself as opposed to the element.
*
* Private element inheritance is not supported; clients must publicly derive
* from LinkedListElement.
*/
#ifndef ds_SlimLinkedList_h
#define ds_SlimLinkedList_h
#include "mozilla/Assertions.h"
#include <algorithm>
#include <utility>
namespace js {
template <typename T>
class SlimLinkedListElement;
template <typename T>
class SlimLinkedList;
template <typename T>
class SlimLinkedListElement {
using ElementPtr = T*;
using ConstElementPtr = const T*;
// Tag bit used to indicate the start/end of the list. The tag is set on the
// prev_ pointer of the first node and the next_ pointer of the last node in
// the list.
static constexpr uintptr_t EndTag = 1;
uintptr_t next_ = 0;
uintptr_t prev_ = 0;
friend class js::SlimLinkedList<T>;
static uintptr_t UntaggedPtr(ElementPtr ptr) {
MOZ_ASSERT((uintptr_t(ptr) & EndTag) == 0);
return uintptr_t(ptr);
}
static uintptr_t GetTag(uintptr_t taggedPtr) { return taggedPtr & EndTag; }
static ElementPtr GetPtr(uintptr_t taggedPtr) {
return reinterpret_cast<ElementPtr>(uintptr_t(taggedPtr) & ~EndTag);
}
static ConstElementPtr GetConstPtr(uintptr_t taggedPtr) {
return reinterpret_cast<ConstElementPtr>(uintptr_t(taggedPtr) & ~EndTag);
}
static void LinkElements(ElementPtr a, ElementPtr b, uintptr_t maybeTag = 0) {
MOZ_ASSERT((maybeTag & ~EndTag) == 0);
a->next_ = UntaggedPtr(b) | maybeTag;
b->prev_ = UntaggedPtr(a) | maybeTag;
}
public:
SlimLinkedListElement() = default;
~SlimLinkedListElement() { MOZ_ASSERT(!isInList()); }
SlimLinkedListElement(const SlimLinkedListElement<T>& other) = delete;
SlimLinkedListElement& operator=(const SlimLinkedListElement<T>& other) =
delete;
// Don't allow moving elements that are part of a list.
SlimLinkedListElement(SlimLinkedListElement<T>&& other) {
MOZ_ASSERT(this != &other);
MOZ_ASSERT(!isInList());
MOZ_ASSERT(!other.isInList());
}
SlimLinkedListElement& operator=(SlimLinkedListElement<T>&& other) {
MOZ_ASSERT(this != &other);
MOZ_ASSERT(!isInList());
MOZ_ASSERT(!other.isInList());
return *this;
}
bool isInList() const {
MOZ_ASSERT(bool(next_) == bool(prev_));
return next_;
}
bool isLast() const {
MOZ_ASSERT(isInList());
return GetTag(next_);
}
bool isFirst() const {
MOZ_ASSERT(isInList());
return GetTag(prev_);
}
ElementPtr getNext() { return isLast() ? nullptr : getNextUnchecked(); }
ConstElementPtr getNext() const {
return isLast() ? nullptr : getNextUnchecked();
}
ElementPtr getPrev() { return isFirst() ? nullptr : getPrevUnchecked(); }
ConstElementPtr getPrev() const {
return isFirst() ? nullptr : getPrevUnchecked();
}
private:
ElementPtr getNextUnchecked() { return GetPtr(next_); }
ConstElementPtr getNextUnchecked() const { return GetConstPtr(next_); };
ElementPtr getPrevUnchecked() { return GetPtr(prev_); }
ConstElementPtr getPrevUnchecked() const { return GetConstPtr(prev_); };
ElementPtr thisElement() { return static_cast<ElementPtr>(this); }
void makeSingleton() {
MOZ_ASSERT(!isInList());
LinkElements(thisElement(), thisElement(), EndTag);
}
void insertAfter(ElementPtr newElement) {
insertListAfter(newElement, newElement);
}
/*
* Insert the list of elements from |listFirst| to |listLast| between |this|
* and the next element |next|. Any tag goes between |listLast| and |next|.
*/
void insertListAfter(ElementPtr listFirst, ElementPtr listLast) {
MOZ_ASSERT(isInList());
MOZ_ASSERT_IF(listFirst != listLast,
listFirst->getPrevUnchecked() == listLast);
MOZ_ASSERT_IF(listFirst != listLast,
listLast->getNextUnchecked() == listFirst);
ElementPtr next = GetPtr(next_);
uintptr_t tag = GetTag(next_);
LinkElements(thisElement(), listFirst);
LinkElements(listLast, next, tag);
}
void insertBefore(ElementPtr newElement) {
insertListBefore(newElement, newElement);
}
/*
* Insert the list of elements from |listFirst| to |listLast| between the
* previous element |prev| and |this|. Any tag goes between |prev| and
* |listFirst|.
*/
void insertListBefore(ElementPtr listFirst, ElementPtr listLast) {
MOZ_ASSERT(isInList());
MOZ_ASSERT_IF(listFirst != listLast,
listFirst->getPrevUnchecked() == listLast);
MOZ_ASSERT_IF(listFirst != listLast,
listLast->getNextUnchecked() == listFirst);
ElementPtr prev = GetPtr(prev_);
uintptr_t tag = GetTag(prev_);
LinkElements(prev, listFirst, tag);
LinkElements(listLast, thisElement());
}
/*
* Remove element |this| from its containing list.
*/
void remove() {
MOZ_ASSERT(isInList());
ElementPtr prev = GetPtr(prev_);
ElementPtr next = GetPtr(next_);
uintptr_t tag = GetTag(prev_) | GetTag(next_);
LinkElements(prev, next, tag);
next_ = 0;
prev_ = 0;
}
};
template <typename T>
class SlimLinkedList {
using ElementPtr = T*;
using ConstElementPtr = const T*;
ElementPtr first_ = nullptr;
public:
template <typename Type>
class Iterator {
Type current_;
public:
using iterator_category = std::forward_iterator_tag;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
explicit Iterator(Type current) : current_(current) {}
Type operator*() const { return current_; }
const Iterator& operator++() {
current_ = current_->getNext();
return *this;
}
bool operator==(const Iterator& other) const {
return current_ == other.current_;
}
bool operator!=(const Iterator& other) const { return !(*this == other); }
};
SlimLinkedList() = default;
SlimLinkedList(const SlimLinkedList<T>& other) = delete;
SlimLinkedList& operator=(const SlimLinkedList<T>& other) = delete;
SlimLinkedList(SlimLinkedList<T>&& other) {
MOZ_ASSERT(this != &other);
MOZ_ASSERT(isEmpty());
std::swap(first_, other.first_);
}
SlimLinkedList& operator=(SlimLinkedList<T>&& other) {
MOZ_ASSERT(this != &other);
MOZ_ASSERT(isEmpty());
std::swap(first_, other.first_);
return *this;
}
~SlimLinkedList() { MOZ_ASSERT(isEmpty()); }
/*
* Add |newElement| to the front of the list.
*/
void pushFront(ElementPtr newElement) {
if (isEmpty()) {
newElement->makeSingleton();
} else {
first_->insertBefore(newElement);
}
first_ = newElement;
}
/*
* Add |newElement| to the back of the list.
*/
void pushBack(ElementPtr newElement) {
if (isEmpty()) {
newElement->makeSingleton();
first_ = newElement;
return;
}
getLast()->insertAfter(newElement);
}
/*
* Move all elements from list |other| to the end of this list. |other| is
* left empty.
*/
void append(SlimLinkedList<T>&& other) {
MOZ_ASSERT(this != &other);
if (other.isEmpty()) {
return;
}
if (isEmpty()) {
*this = std::move(other);
return;
}
getLast()->insertListAfter(other.getFirst(), other.getLast());
other.first_ = nullptr;
}
/*
* Move all elements from list |other| to the start of this list. |other| is
* left empty.
*/
void prepend(SlimLinkedList<T>&& other) {
MOZ_ASSERT(this != &other);
if (other.isEmpty()) {
return;
}
if (isEmpty()) {
*this = std::move(other);
return;
}
getFirst()->insertListBefore(other.getFirst(), other.getLast());
first_ = other.first_;
other.first_ = nullptr;
}
/*
* Get the first element of the list, or nullptr if the list is empty.
*/
ElementPtr getFirst() { return first_; }
ConstElementPtr getFirst() const { return first_; }
/*
* Get the last element of the list, or nullptr if the list is empty.
*/
ElementPtr getLast() {
return isEmpty() ? nullptr : first_->getPrevUnchecked();
}
ConstElementPtr getLast() const {
return isEmpty() ? nullptr : first_->getPrevUnchecked();
}
/*
* Get and remove the first element of the list. If the list is empty, return
* nullptr.
*/
ElementPtr popFirst() {
if (isEmpty()) {
return nullptr;
}
ElementPtr result = first_;
first_ = result->getNext();
result->remove();
return result;
}
/*
* Get and remove the last element of the list. If the list is empty, return
* nullptr.
*/
ElementPtr popLast() {
if (isEmpty()) {
return nullptr;
}
ElementPtr result = getLast();
if (result == first_) {
first_ = nullptr;
}
result->remove();
return result;
}
/*
* Return true if the list is empty, or false otherwise.
*/
bool isEmpty() const { return !first_; }
/*
* Returns whether the given element is in the list.
*/
bool contains(ConstElementPtr aElm) const {
return std::find(begin(), end(), aElm) != end();
}
/*
* Remove |element| from this list.
*/
void remove(ElementPtr element) {
checkContains(element);
if (element == first_) {
first_ = element->getNext();
}
element->remove();
}
void checkContains(ElementPtr element) {
#ifdef DEBUG
size_t i = 0;
for (const auto& e : *this) {
if (e == element) {
return; // Found.
}
if (i == 100) {
return; // Limit time spent checking.
}
}
MOZ_CRASH("Element not found");
#endif
}
/*
* Remove all the elements from the list.
*
* This runs in time linear to the list's length, because we have to mark
* each element as not in the list.
*/
void clear() {
while (popFirst()) {
}
}
/*
* Remove all the elements from the list, calling |func| on each one first. On
* return the list is empty.
*/
template <typename F>
void drain(F&& func) {
while (ElementPtr element = popFirst()) {
func(element);
}
}
/**
* Return the length of elements in the list.
*/
size_t length() const { return std::distance(begin(), end()); }
/*
* Allow range-based iteration:
*
* for (MyElementPtr* elt : myList) { ... }
*/
Iterator<ElementPtr> begin() { return Iterator<ElementPtr>(getFirst()); }
Iterator<ConstElementPtr> begin() const {
return Iterator<ConstElementPtr>(getFirst());
}
Iterator<ElementPtr> end() { return Iterator<ElementPtr>(nullptr); }
Iterator<ConstElementPtr> end() const {
return Iterator<ConstElementPtr>(nullptr);
}
};
} /* namespace js */
#endif /* ds_SlimLinkedList_h */