js/src/ds/SinglyLinkedList.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #ifndef ds_SinglyLinkedList_h
   8 #define ds_SinglyLinkedList_h
   9
  10 #include "mozilla/Assertions.h"
  11
  12 #include <utility>
  13
  14 namespace js {
  15
  16 /*
  17  * Circular singly linked list that requires only one word per element and for
  18  * the list itself.
  19  *
  20  * Requires T has field |T::next| for the link pointer.
  21  */
  22 template <typename T>
  23 class SinglyLinkedList {
  24   T* last_ = nullptr;
  25
  26  public:
  27   SinglyLinkedList() {
  28     static_assert(std::is_same_v<decltype(T::next), T*>,
  29                   "SinglyLinkedList requires T has a next field of type T*");
  30     MOZ_ASSERT(isEmpty());
  31   }
  32
  33   SinglyLinkedList(T* first, T* last) : last_(last) {
  34     MOZ_ASSERT(!last_->next);
  35     last_->next = first;
  36   }
  37
  38   // It's not possible for elements to be present in more than one list, so copy
  39   // operations are not provided.
  40   SinglyLinkedList(const SinglyLinkedList& other) = delete;
  41   SinglyLinkedList& operator=(const SinglyLinkedList& other) = delete;
  42
  43   SinglyLinkedList(SinglyLinkedList&& other) {
  44     std::swap(last_, other.last_);
  45     MOZ_ASSERT(other.isEmpty());
  46   }
  47   SinglyLinkedList& operator=(SinglyLinkedList&& other) {
  48     MOZ_ASSERT(isEmpty());
  49     return *new (this) SinglyLinkedList(std::move(other));
  50   }
  51
  52   ~SinglyLinkedList() { MOZ_ASSERT(isEmpty()); }
  53
  54   bool isEmpty() const { return !last_; }
  55
  56   // These return nullptr if the list is empty.
  57   T* first() const {
  58     if (isEmpty()) {
  59       return nullptr;
  60     }
  61     T* element = last_->next;
  62     MOZ_ASSERT(element);
  63     return element;
  64   }
  65   T* last() const { return last_; }
  66
  67   T* popFront() {
  68     MOZ_ASSERT(!isEmpty());
  69
  70     T* element = last_->next;
  71
  72     if (element == last_) {
  73       last_ = nullptr;
  74     } else {
  75       last_->next = element->next;
  76     }
  77
  78     element->next = nullptr;
  79     return element;
  80   }
  81   // popBack cannot be implemented in constant time for a singly linked list.
  82
  83   void pushFront(T* element) {
  84     MOZ_ASSERT(!element->next);
  85     if (isEmpty()) {
  86       element->next = element;
  87       last_ = element;
  88       return;
  89     }
  90
  91     element->next = last_->next;
  92     last_->next = element;
  93   }
  94   void pushBack(T* element) {
  95     pushFront(element);
  96     moveFrontToBack();
  97   }
  98   void moveFrontToBack() {
  99     MOZ_ASSERT(!isEmpty());
 100     last_ = last_->next;
 101   }
 102
 103   void append(SinglyLinkedList&& other) {
 104     if (other.isEmpty()) {
 105       return;
 106     }
 107
 108     if (isEmpty()) {
 109       new (this) SinglyLinkedList(std::move(other));
 110       return;
 111     }
 112
 113     T* firstElement = first();
 114     last()->next = other.first();
 115     other.last()->next = firstElement;
 116     last_ = other.last();
 117     other.last_ = nullptr;
 118   }
 119
 120   // template <typename T>
 121   class Iterator {
 122     T* i = nullptr;
 123     T* last = nullptr;
 124
 125    public:
 126     explicit Iterator(const SinglyLinkedList& list)
 127         : i(list.first()), last(list.last()) {}
 128     bool done() const { return !i; }
 129     void next() {
 130       MOZ_ASSERT(!done());
 131       i = i == last ? nullptr : i->next;
 132     }
 133     T* get() const {
 134       MOZ_ASSERT(!done());
 135       return i;
 136     }
 137
 138     T& operator*() const { return *get(); }
 139     T* operator->() const { return get(); }
 140   };
 141
 142   Iterator iter() const { return Iterator(*this); }
 143
 144   // Extracts a non-circular linked list and clears this object.
 145   T* release() {
 146     if (isEmpty()) {
 147       return nullptr;
 148     }
 149
 150     T* list = first();
 151     MOZ_ASSERT(last_->next);
 152     last_->next = nullptr;
 153     last_ = nullptr;
 154     return list;
 155   }
 156 };
 157
 158 } /* namespace js */
 159
 160 #endif /* ds_SinglyLinkedList_h */