tor-browser

SinglyLinkedList.h (6429B)

---

/* -*- 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
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#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.
*
* The list only stores a pointer to the last element. Since the list is
* circular, that provides access to the first element and allows insertion at
* the start and end of the list.
*/
template <typename T>
class SinglyLinkedList {
 T* last_ = nullptr;

public:
 // Create an empty list.
 SinglyLinkedList() {
   static_assert(std::is_same_v<decltype(T::next), T*>,
                 "SinglyLinkedList requires T has a next field of type T*");
   MOZ_ASSERT(isEmpty());
 }

 // Create a list from an existing non-circular linked list from |first| to
 // |last|.
 SinglyLinkedList(T* first, T* last) {
   MOZ_ASSERT(first);
   MOZ_ASSERT(last);
   MOZ_ASSERT(!last->next);
   last->next = first;
   last_ = last;
   checkContains(first);
   checkContains(last);
 }

 // 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) {
   MOZ_ASSERT(&other != this);
   std::swap(last_, other.last_);
   MOZ_ASSERT(other.isEmpty());
 }
 SinglyLinkedList& operator=(SinglyLinkedList&& other) {
   MOZ_ASSERT(&other != this);
   MOZ_ASSERT(isEmpty());
   std::swap(last_, other.last_);
   return *this;
 }

 ~SinglyLinkedList() { MOZ_ASSERT(isEmpty()); }

 bool isEmpty() const { return !last_; }

 // These return nullptr if the list is empty.
 T* getFirst() const {
   if (isEmpty()) {
     return nullptr;
   }
   T* element = last_->next;
   MOZ_ASSERT(element);
   return element;
 }
 T* getLast() 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;
   MOZ_ASSERT(!isEmpty());
 }

 void append(SinglyLinkedList&& other) {
   MOZ_ASSERT(&other != this);

   if (other.isEmpty()) {
     return;
   }

   if (isEmpty()) {
     *this = std::move(other);
     return;
   }

   T* firstElement = getFirst();
   getLast()->next = other.getFirst();
   other.getLast()->next = firstElement;
   last_ = other.getLast();
   other.last_ = nullptr;
 }

 void prepend(SinglyLinkedList&& other) {
   MOZ_ASSERT(&other != this);

   if (other.isEmpty()) {
     return;
   }

   if (isEmpty()) {
     *this = std::move(other);
     return;
   }

   T* firstElement = getFirst();
   getLast()->next = other.getFirst();
   other.getLast()->next = firstElement;
   other.last_ = nullptr;
 }

 // Remove all elements between |fromExclusive| and |toInclusive|. Return the
 // removed list segment as a non-circular linked list.
 //
 // The fact that the first parameter is exclusive is a requirement for
 // implementing this in constant time for a singly linked list.
 T* removeRange(T* fromExclusive, T* toInclusive) {
   MOZ_ASSERT(fromExclusive);
   MOZ_ASSERT(toInclusive);
   MOZ_ASSERT(fromExclusive != toInclusive);
   MOZ_ASSERT(!isEmpty());

#ifdef DEBUG
   size_t index = 0;
   size_t fromIndex = SIZE_MAX;
   size_t toIndex = SIZE_MAX;
   for (T* element = getFirst(); element; element = element->next) {
     if (element == fromExclusive) {
       fromIndex = index;
     }
     if (element == toInclusive) {
       toIndex = index;
     }
     index++;
     if (index == 100) {
       break;
     }
   }
   if (index < 100) {
     MOZ_ASSERT(fromIndex != SIZE_MAX);
     MOZ_ASSERT(toIndex != SIZE_MAX);
     MOZ_ASSERT(fromIndex < toIndex);
   }
#endif

   T* result = fromExclusive->next;
   fromExclusive->next = toInclusive->next;
   toInclusive->next = nullptr;

   if (last_ == toInclusive) {
     last_ = fromExclusive;
   }

   return result;
 }

 // template <typename T>
 class Iterator {
   T* i = nullptr;
   T* last = nullptr;

  public:
   Iterator() = default;
   explicit Iterator(const SinglyLinkedList& list)
       : i(list.getFirst()), last(list.getLast()) {}
   Iterator(const SinglyLinkedList& list, T* first)
       : i(first), last(list.getLast()) {}
   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); }

 Iterator iterFrom(T* fromInclusive) {
   checkContains(fromInclusive);
   return Iterator(*this, fromInclusive);
 }

 void checkContains(T* element) {
#ifdef DEBUG
   size_t i = 0;
   for (Iterator iter(*this); !iter.done(); iter.next()) {
     if (iter.get() == element) {
       return;  // Found.
     }
     i++;
     if (i == 100) {
       return;  // Limit time spent checking.
     }
   }
   MOZ_CRASH("Element not found");
#endif
 }

 // Extracts a non-circular linked list and clears this object.
 T* release() {
   if (isEmpty()) {
     return nullptr;
   }

   T* list = getFirst();
   MOZ_ASSERT(last_->next);
   last_->next = nullptr;
   last_ = nullptr;
   return list;
 }
};

} /* namespace js */

#endif /* ds_SinglyLinkedList_h */