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