js/src/jit/InlineList.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 jit_InlineList_h
   8 #define jit_InlineList_h
   9
  10 #include "mozilla/Assertions.h"
  11
  12 namespace js {
  13
  14 template <typename T>
  15 class InlineForwardList;
  16 template <typename T>
  17 class InlineForwardListIterator;
  18
  19 template <typename T>
  20 class InlineForwardListNode {
  21  public:
  22   InlineForwardListNode() : next(nullptr) {}
  23   explicit InlineForwardListNode(InlineForwardListNode<T>* n) : next(n) {}
  24
  25   InlineForwardListNode(const InlineForwardListNode<T>&) = delete;
  26
  27  protected:
  28   friend class InlineForwardList<T>;
  29   friend class InlineForwardListIterator<T>;
  30
  31   InlineForwardListNode<T>* next;
  32 };
  33
  34 template <typename T>
  35 class InlineForwardList : protected InlineForwardListNode<T> {
  36   friend class InlineForwardListIterator<T>;
  37
  38   using Node = InlineForwardListNode<T>;
  39
  40   Node* tail_;
  41 #ifdef DEBUG
  42   int modifyCount_;
  43 #endif
  44
  45   InlineForwardList<T>* thisFromConstructor() { return this; }
  46
  47  public:
  48   InlineForwardList() : tail_(thisFromConstructor()) {
  49 #ifdef DEBUG
  50     modifyCount_ = 0;
  51 #endif
  52   }
  53
  54  public:
  55   using iterator = InlineForwardListIterator<T>;
  56
  57  public:
  58   iterator begin() const { return iterator(this); }
  59   iterator begin(Node* item) const { return iterator(this, item); }
  60   iterator end() const { return iterator(nullptr); }
  61   void removeAt(iterator where) { removeAfter(where.prev, where.iter); }
  62   void pushFront(Node* t) { insertAfter(this, t); }
  63   void pushBack(Node* t) {
  64     MOZ_ASSERT(t->next == nullptr);
  65 #ifdef DEBUG
  66     modifyCount_++;
  67 #endif
  68     tail_->next = t;
  69     tail_ = t;
  70   }
  71   T* popFront() {
  72     MOZ_ASSERT(!empty());
  73     T* result = static_cast<T*>(this->next);
  74     removeAfter(this, result);
  75     return result;
  76   }
  77   T* back() const {
  78     MOZ_ASSERT(!empty());
  79     return static_cast<T*>(tail_);
  80   }
  81   void insertAfter(Node* at, Node* item) {
  82     MOZ_ASSERT(item->next == nullptr);
  83 #ifdef DEBUG
  84     modifyCount_++;
  85 #endif
  86     if (at == tail_) {
  87       tail_ = item;
  88     }
  89     item->next = at->next;
  90     at->next = item;
  91   }
  92   void removeAfter(Node* at, Node* item) {
  93 #ifdef DEBUG
  94     modifyCount_++;
  95 #endif
  96     if (item == tail_) {
  97       tail_ = at;
  98     }
  99     MOZ_ASSERT(at->next == item);
 100     at->next = item->next;
 101     item->next = nullptr;
 102   }
 103   void removeAndIncrement(iterator& where) {
 104     // Do not change modifyCount_ here. The iterator can still be used
 105     // after calling this method, unlike the other methods that modify
 106     // the list.
 107     Node* item = where.iter;
 108     where.iter = item->next;
 109     if (item == tail_) {
 110       tail_ = where.prev;
 111     }
 112     MOZ_ASSERT(where.prev->next == item);
 113     where.prev->next = where.iter;
 114     item->next = nullptr;
 115   }
 116   void splitAfter(Node* at, InlineForwardList<T>* to) {
 117     MOZ_ASSERT(to->empty());
 118     if (!at) {
 119       at = this;
 120     }
 121     if (at == tail_) {
 122       return;
 123     }
 124 #ifdef DEBUG
 125     modifyCount_++;
 126 #endif
 127     to->next = at->next;
 128     to->tail_ = tail_;
 129     tail_ = at;
 130     at->next = nullptr;
 131   }
 132   bool empty() const { return tail_ == this; }
 133   void clear() {
 134     this->next = nullptr;
 135     tail_ = this;
 136 #ifdef DEBUG
 137     modifyCount_ = 0;
 138 #endif
 139   }
 140 };
 141
 142 template <typename T>
 143 class InlineForwardListIterator {
 144  private:
 145   friend class InlineForwardList<T>;
 146
 147   using Node = InlineForwardListNode<T>;
 148
 149   explicit InlineForwardListIterator(const InlineForwardList<T>* owner)
 150       : prev(const_cast<Node*>(static_cast<const Node*>(owner))),
 151         iter(owner ? owner->next : nullptr)
 152 #ifdef DEBUG
 153         ,
 154         owner_(owner),
 155         modifyCount_(owner ? owner->modifyCount_ : 0)
 156 #endif
 157   {
 158   }
 159
 160   InlineForwardListIterator(const InlineForwardList<T>* owner, Node* node)
 161       : prev(nullptr),
 162         iter(node)
 163 #ifdef DEBUG
 164         ,
 165         owner_(owner),
 166         modifyCount_(owner ? owner->modifyCount_ : 0)
 167 #endif
 168   {
 169   }
 170
 171  public:
 172   InlineForwardListIterator<T>& operator++() {
 173     MOZ_ASSERT(modifyCount_ == owner_->modifyCount_);
 174     prev = iter;
 175     iter = iter->next;
 176     return *this;
 177   }
 178   InlineForwardListIterator<T> operator++(int) {
 179     InlineForwardListIterator<T> old(*this);
 180     operator++();
 181     return old;
 182   }
 183   T* operator*() const {
 184     MOZ_ASSERT(modifyCount_ == owner_->modifyCount_);
 185     return static_cast<T*>(iter);
 186   }
 187   T* operator->() const {
 188     MOZ_ASSERT(modifyCount_ == owner_->modifyCount_);
 189     return static_cast<T*>(iter);
 190   }
 191   bool operator!=(const InlineForwardListIterator<T>& where) const {
 192     return iter != where.iter;
 193   }
 194   bool operator==(const InlineForwardListIterator<T>& where) const {
 195     return iter == where.iter;
 196   }
 197   explicit operator bool() const { return iter != nullptr; }
 198
 199  private:
 200   Node* prev;
 201   Node* iter;
 202
 203 #ifdef DEBUG
 204   const InlineForwardList<T>* owner_;
 205   int modifyCount_;
 206 #endif
 207 };
 208
 209 template <typename T>
 210 class InlineList;
 211 template <typename T>
 212 class InlineListIterator;
 213 template <typename T>
 214 class InlineListReverseIterator;
 215
 216 template <typename T>
 217 class InlineListNode : public InlineForwardListNode<T> {
 218  public:
 219   InlineListNode() : InlineForwardListNode<T>(nullptr), prev(nullptr) {}
 220   InlineListNode(InlineListNode<T>* n, InlineListNode<T>* p)
 221       : InlineForwardListNode<T>(n), prev(p) {}
 222
 223   // Move constructor. Nodes may be moved without being removed from their
 224   // containing lists. For example, this allows list nodes to be safely
 225   // stored in a resizable Vector -- when the Vector resizes, the new storage
 226   // is initialized by this move constructor. |other| is a reference to the
 227   // old node which the |this| node here is replacing.
 228   InlineListNode(InlineListNode<T>&& other)
 229       : InlineForwardListNode<T>(other.next) {
 230     InlineListNode<T>* newNext = static_cast<InlineListNode<T>*>(other.next);
 231     InlineListNode<T>* newPrev = other.prev;
 232     prev = newPrev;
 233
 234     // Update the pointers in the adjacent nodes to point to this node's new
 235     // location.
 236     newNext->prev = this;
 237     newPrev->next = this;
 238   }
 239
 240   InlineListNode(const InlineListNode<T>&) = delete;
 241   void operator=(const InlineListNode<T>&) = delete;
 242
 243   bool isInList() { return prev != nullptr && this->next != nullptr; }
 244
 245  protected:
 246   friend class InlineList<T>;
 247   friend class InlineListIterator<T>;
 248   friend class InlineListReverseIterator<T>;
 249
 250   InlineListNode<T>* prev;
 251 };
 252
 253 template <typename T>
 254 class InlineList : protected InlineListNode<T> {
 255   using Node = InlineListNode<T>;
 256
 257  public:
 258   InlineList() : InlineListNode<T>(this, this) {}
 259
 260  public:
 261   using iterator = InlineListIterator<T>;
 262   using reverse_iterator = InlineListReverseIterator<T>;
 263
 264  public:
 265   iterator begin() const { return iterator(static_cast<Node*>(this->next)); }
 266   iterator begin(Node* t) const { return iterator(t); }
 267   iterator end() const { return iterator(this); }
 268   reverse_iterator rbegin() const { return reverse_iterator(this->prev); }
 269   reverse_iterator rbegin(Node* t) const { return reverse_iterator(t); }
 270   reverse_iterator rend() const { return reverse_iterator(this); }
 271   void pushFront(Node* t) { insertAfter(this, t); }
 272   void pushFrontUnchecked(Node* t) { insertAfterUnchecked(this, t); }
 273   void pushBack(Node* t) { insertBefore(this, t); }
 274   void pushBackUnchecked(Node* t) { insertBeforeUnchecked(this, t); }
 275   T* popFront() {
 276     MOZ_ASSERT(!empty());
 277     T* t = static_cast<T*>(this->next);
 278     remove(t);
 279     return t;
 280   }
 281   T* popBack() {
 282     MOZ_ASSERT(!empty());
 283     T* t = static_cast<T*>(this->prev);
 284     remove(t);
 285     return t;
 286   }
 287   T* peekBack() const {
 288     iterator iter = end();
 289     iter--;
 290     return *iter;
 291   }
 292   void insertBefore(Node* at, Node* item) {
 293     MOZ_ASSERT(item->prev == nullptr);
 294     MOZ_ASSERT(item->next == nullptr);
 295     insertBeforeUnchecked(at, item);
 296   }
 297   void insertBeforeUnchecked(Node* at, Node* item) {
 298     Node* atPrev = at->prev;
 299     item->next = at;
 300     item->prev = atPrev;
 301     atPrev->next = item;
 302     at->prev = item;
 303   }
 304   void insertAfter(Node* at, Node* item) {
 305     MOZ_ASSERT(item->prev == nullptr);
 306     MOZ_ASSERT(item->next == nullptr);
 307     insertAfterUnchecked(at, item);
 308   }
 309   void insertAfterUnchecked(Node* at, Node* item) {
 310     Node* atNext = static_cast<Node*>(at->next);
 311     item->next = atNext;
 312     item->prev = at;
 313     atNext->prev = item;
 314     at->next = item;
 315   }
 316   void remove(Node* t) {
 317     Node* tNext = static_cast<Node*>(t->next);
 318     Node* tPrev = t->prev;
 319     tPrev->next = tNext;
 320     tNext->prev = tPrev;
 321     t->next = nullptr;
 322     t->prev = nullptr;
 323   }
 324   // Remove |old| from the list and insert |now| in its place.
 325   void replace(Node* old, Node* now) {
 326     MOZ_ASSERT(now->next == nullptr && now->prev == nullptr);
 327     Node* listNext = static_cast<Node*>(old->next);
 328     Node* listPrev = old->prev;
 329     listPrev->next = now;
 330     listNext->prev = now;
 331     now->next = listNext;
 332     now->prev = listPrev;
 333     old->next = nullptr;
 334     old->prev = nullptr;
 335   }
 336   void clear() { this->next = this->prev = this; }
 337   bool empty() const { return begin() == end(); }
 338   void takeElements(InlineList& l) {
 339     MOZ_ASSERT(&l != this, "cannot takeElements from this");
 340     Node* lprev = l.prev;
 341     static_cast<Node*>(l.next)->prev = this;
 342     lprev->next = this->next;
 343     static_cast<Node*>(this->next)->prev = l.prev;
 344     this->next = l.next;
 345     l.clear();
 346   }
 347 };
 348
 349 template <typename T>
 350 class InlineListIterator {
 351  private:
 352   friend class InlineList<T>;
 353
 354   using Node = InlineListNode<T>;
 355
 356   explicit InlineListIterator(const Node* iter)
 357       : iter(const_cast<Node*>(iter)) {}
 358
 359  public:
 360   InlineListIterator<T>& operator++() {
 361     iter = static_cast<Node*>(iter->next);
 362     return *this;
 363   }
 364   InlineListIterator<T> operator++(int) {
 365     InlineListIterator<T> old(*this);
 366     operator++();
 367     return old;
 368   }
 369   InlineListIterator<T>& operator--() {
 370     iter = iter->prev;
 371     return *this;
 372   }
 373   InlineListIterator<T> operator--(int) {
 374     InlineListIterator<T> old(*this);
 375     operator--();
 376     return old;
 377   }
 378   T* operator*() const { return static_cast<T*>(iter); }
 379   T* operator->() const { return static_cast<T*>(iter); }
 380   bool operator!=(const InlineListIterator<T>& where) const {
 381     return iter != where.iter;
 382   }
 383   bool operator==(const InlineListIterator<T>& where) const {
 384     return iter == where.iter;
 385   }
 386
 387  private:
 388   Node* iter;
 389 };
 390
 391 template <typename T>
 392 class InlineListReverseIterator {
 393  private:
 394   friend class InlineList<T>;
 395
 396   using Node = InlineListNode<T>;
 397
 398   explicit InlineListReverseIterator(const Node* iter)
 399       : iter(const_cast<Node*>(iter)) {}
 400
 401  public:
 402   InlineListReverseIterator<T>& operator++() {
 403     iter = iter->prev;
 404     return *this;
 405   }
 406   InlineListReverseIterator<T> operator++(int) {
 407     InlineListReverseIterator<T> old(*this);
 408     operator++();
 409     return old;
 410   }
 411   InlineListReverseIterator<T>& operator--() {
 412     iter = static_cast<Node*>(iter->next);
 413     return *this;
 414   }
 415   InlineListReverseIterator<T> operator--(int) {
 416     InlineListReverseIterator<T> old(*this);
 417     operator--();
 418     return old;
 419   }
 420   T* operator*() { return static_cast<T*>(iter); }
 421   T* operator->() { return static_cast<T*>(iter); }
 422   bool operator!=(const InlineListReverseIterator<T>& where) const {
 423     return iter != where.iter;
 424   }
 425   bool operator==(const InlineListReverseIterator<T>& where) const {
 426     return iter == where.iter;
 427   }
 428
 429  private:
 430   Node* iter;
 431 };
 432
 433 // This list type is more or less exactly an InlineForwardList without a
 434 // sentinel node. It is useful in cases where you are doing algorithms that deal
 435 // with many merging singleton lists, rather than often empty ones.
 436 template <typename T>
 437 class InlineConcatListIterator;
 438 template <typename T>
 439 class InlineConcatList {
 440  private:
 441   using Node = InlineConcatList<T>;
 442
 443   InlineConcatList<T>* thisFromConstructor() { return this; }
 444
 445  public:
 446   InlineConcatList() : next(nullptr), tail(thisFromConstructor()) {}
 447
 448   using iterator = InlineConcatListIterator<T>;
 449
 450   iterator begin() const { return iterator(this); }
 451
 452   iterator end() const { return iterator(nullptr); }
 453
 454   void append(InlineConcatList<T>* adding) {
 455     MOZ_ASSERT(tail);
 456     MOZ_ASSERT(!tail->next);
 457     MOZ_ASSERT(adding->tail);
 458     MOZ_ASSERT(!adding->tail->next);
 459
 460     tail->next = adding;
 461     tail = adding->tail;
 462     adding->tail = nullptr;
 463   }
 464
 465  protected:
 466   friend class InlineConcatListIterator<T>;
 467   Node* next;
 468   Node* tail;
 469 };
 470
 471 template <typename T>
 472 class InlineConcatListIterator {
 473  private:
 474   friend class InlineConcatList<T>;
 475
 476   using Node = InlineConcatList<T>;
 477
 478   explicit InlineConcatListIterator(const Node* iter)
 479       : iter(const_cast<Node*>(iter)) {}
 480
 481  public:
 482   InlineConcatListIterator<T>& operator++() {
 483     iter = static_cast<Node*>(iter->next);
 484     return *this;
 485   }
 486   InlineConcatListIterator<T> operator++(int) {
 487     InlineConcatListIterator<T> old(*this);
 488     operator++();
 489     return old;
 490   }
 491   T* operator*() const { return static_cast<T*>(iter); }
 492   T* operator->() const { return static_cast<T*>(iter); }
 493   bool operator!=(const InlineConcatListIterator<T>& where) const {
 494     return iter != where.iter;
 495   }
 496   bool operator==(const InlineConcatListIterator<T>& where) const {
 497     return iter == where.iter;
 498   }
 499
 500  private:
 501   Node* iter;
 502 };
 503
 504 template <typename T>
 505 class InlineSpaghettiStack;
 506 template <typename T>
 507 class InlineSpaghettiStackNode;
 508 template <typename T>
 509 class InlineSpaghettiStackIterator;
 510
 511 template <typename T>
 512 class InlineSpaghettiStackNode : public InlineForwardListNode<T> {
 513   using Parent = InlineForwardListNode<T>;
 514
 515  public:
 516   InlineSpaghettiStackNode() : Parent() {}
 517
 518   explicit InlineSpaghettiStackNode(InlineSpaghettiStackNode<T>* n)
 519       : Parent(n) {}
 520
 521   InlineSpaghettiStackNode(const InlineSpaghettiStackNode<T>&) = delete;
 522
 523  protected:
 524   friend class InlineSpaghettiStack<T>;
 525   friend class InlineSpaghettiStackIterator<T>;
 526 };
 527
 528 template <typename T>
 529 class InlineSpaghettiStack : protected InlineSpaghettiStackNode<T> {
 530   friend class InlineSpaghettiStackIterator<T>;
 531
 532   using Node = InlineSpaghettiStackNode<T>;
 533
 534  public:
 535   InlineSpaghettiStack() = default;
 536
 537  public:
 538   using iterator = InlineSpaghettiStackIterator<T>;
 539
 540  public:
 541   iterator begin() const { return iterator(this); }
 542   iterator end() const { return iterator(nullptr); }
 543
 544   void push(Node* t) {
 545     MOZ_ASSERT(t->next == nullptr);
 546     t->next = this->next;
 547     this->next = t;
 548   }
 549
 550   void copy(const InlineSpaghettiStack<T>& stack) { this->next = stack.next; }
 551
 552   bool empty() const { return this->next == nullptr; }
 553 };
 554
 555 template <typename T>
 556 class InlineSpaghettiStackIterator {
 557  private:
 558   friend class InlineSpaghettiStack<T>;
 559
 560   using Node = InlineSpaghettiStackNode<T>;
 561
 562   explicit InlineSpaghettiStackIterator(const InlineSpaghettiStack<T>* owner)
 563       : iter(owner ? static_cast<Node*>(owner->next) : nullptr) {}
 564
 565  public:
 566   InlineSpaghettiStackIterator<T>& operator++() {
 567     iter = static_cast<Node*>(iter->next);
 568     return *this;
 569   }
 570   InlineSpaghettiStackIterator<T> operator++(int) {
 571     InlineSpaghettiStackIterator<T> old(*this);
 572     operator++();
 573     return old;
 574   }
 575   T* operator*() const { return static_cast<T*>(iter); }
 576   T* operator->() const { return static_cast<T*>(iter); }
 577   bool operator!=(const InlineSpaghettiStackIterator<T>& where) const {
 578     return iter != where.iter;
 579   }
 580   bool operator==(const InlineSpaghettiStackIterator<T>& where) const {
 581     return iter == where.iter;
 582   }
 583
 584  private:
 585   Node* iter;
 586 };
 587
 588 }  // namespace js
 589
 590 #endif /* jit_InlineList_h */