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
#ifndef ds_SinglyLinkedList_h
#define ds_SinglyLinkedList_h
#include "mozilla/Assertions.h"
#include <utility>
namespace js {
/*
* Circular singly linked list that requires only one word per element and for
* the list itself.
*
* Requires T has field |T::next| for the link pointer.
*/
template <typename T>
class SinglyLinkedList {
T* last_ = nullptr;
public:
SinglyLinkedList() {
static_assert(std::is_same_v<decltype(T::next), T*>,
"SinglyLinkedList requires T has a next field of type T*");
MOZ_ASSERT(isEmpty());
}
SinglyLinkedList(T* first, T* last) : last_(last) {
MOZ_ASSERT(!last_->next);
last_->next = first;
}
// It's not possible for elements to be present in more than one list, so copy
// operations are not provided.
SinglyLinkedList(const SinglyLinkedList& other) = delete;
SinglyLinkedList& operator=(const SinglyLinkedList& other) = delete;
SinglyLinkedList(SinglyLinkedList&& other) {
std::swap(last_, other.last_);
MOZ_ASSERT(other.isEmpty());
}
SinglyLinkedList& operator=(SinglyLinkedList&& other) {
MOZ_ASSERT(isEmpty());
return *new (this) SinglyLinkedList(std::move(other));
}
~SinglyLinkedList() { MOZ_ASSERT(isEmpty()); }
bool isEmpty() const { return !last_; }
// These return nullptr if the list is empty.
T* first() const {
if (isEmpty()) {
return nullptr;
}
T* element = last_->next;
MOZ_ASSERT(element);
return element;
}
T* last() const { return last_; }
T* popFront() {
MOZ_ASSERT(!isEmpty());
T* element = last_->next;
if (element == last_) {
last_ = nullptr;
} else {
last_->next = element->next;
}
element->next = nullptr;
return element;
}
// popBack cannot be implemented in constant time for a singly linked list.
void pushFront(T* element) {
MOZ_ASSERT(!element->next);
if (isEmpty()) {
element->next = element;
last_ = element;
return;
}
element->next = last_->next;
last_->next = element;
}
void pushBack(T* element) {
pushFront(element);
moveFrontToBack();
}
void moveFrontToBack() {
MOZ_ASSERT(!isEmpty());
last_ = last_->next;
}
void append(SinglyLinkedList&& other) {
if (other.isEmpty()) {
return;
}
if (isEmpty()) {
new (this) SinglyLinkedList(std::move(other));
return;
}
T* firstElement = first();
last()->next = other.first();
other.last()->next = firstElement;
last_ = other.last();
other.last_ = nullptr;
}
// template <typename T>
class Iterator {
T* i = nullptr;
T* last = nullptr;
public:
explicit Iterator(const SinglyLinkedList& list)
: i(list.first()), last(list.last()) {}
bool done() const { return !i; }
void next() {
MOZ_ASSERT(!done());
i = i == last ? nullptr : i->next;
}
T* get() const {
MOZ_ASSERT(!done());
return i;
}
T& operator*() const { return *get(); }
T* operator->() const { return get(); }
};
Iterator iter() const { return Iterator(*this); }
// Extracts a non-circular linked list and clears this object.
T* release() {
if (isEmpty()) {
return nullptr;
}
T* list = first();
MOZ_ASSERT(last_->next);
last_->next = nullptr;
last_ = nullptr;
return list;
}
};
} /* namespace js */
#endif /* ds_SinglyLinkedList_h */