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