15a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany//===-- sanitizer_list.h ----------------------------------------*- C++ -*-===// 25a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// 35a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// The LLVM Compiler Infrastructure 45a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// 55a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// This file is distributed under the University of Illinois Open Source 65a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// License. See LICENSE.TXT for details. 75a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// 85a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany//===----------------------------------------------------------------------===// 95a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// 105a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// This file contains implementation of a list class to be used by 115a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// ThreadSanitizer, etc run-times. 125a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// 135a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany//===----------------------------------------------------------------------===// 145a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany#ifndef SANITIZER_LIST_H 155a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany#define SANITIZER_LIST_H 165a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 175a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany#include "sanitizer_internal_defs.h" 185a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 195a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryanynamespace __sanitizer { 205a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 215a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// Intrusive singly-linked list with size(), push_back(), push_front() 225a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// pop_front(), append_front() and append_back(). 235a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// This class should be a POD (so that it can be put into TLS) 245a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// and an object with all zero fields should represent a valid empty list. 255a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// This class does not have a CTOR, so clear() should be called on all 265a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// non-zero-initialized objects before using. 275a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryanytemplate<class Item> 285a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryanystruct IntrusiveList { 292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines friend class Iterator; 302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 315a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany void clear() { 325a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany first_ = last_ = 0; 335a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany size_ = 0; 345a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 355a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 365a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany bool empty() const { return size_ == 0; } 375a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany uptr size() const { return size_; } 385a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 395a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany void push_back(Item *x) { 405a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany if (empty()) { 415a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany x->next = 0; 425a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany first_ = last_ = x; 435a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany size_ = 1; 445a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } else { 455a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany x->next = 0; 465a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany last_->next = x; 475a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany last_ = x; 485a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany size_++; 495a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 505a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 515a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 525a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany void push_front(Item *x) { 535a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany if (empty()) { 545a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany x->next = 0; 555a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany first_ = last_ = x; 565a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany size_ = 1; 575a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } else { 585a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany x->next = first_; 595a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany first_ = x; 605a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany size_++; 615a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 625a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 635a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 645a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany void pop_front() { 655a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany CHECK(!empty()); 665a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany first_ = first_->next; 675a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany if (first_ == 0) 685a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany last_ = 0; 695a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany size_--; 705a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 715a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 725a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany Item *front() { return first_; } 735a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany Item *back() { return last_; } 745a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 755a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany void append_front(IntrusiveList<Item> *l) { 765a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany CHECK_NE(this, l); 77312de6a1ac31d295d5ae592084e605b03661acdbDmitry Vyukov if (l->empty()) 78312de6a1ac31d295d5ae592084e605b03661acdbDmitry Vyukov return; 795a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany if (empty()) { 805a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany *this = *l; 81deafb6bd5252c2d6ccef070ea572b04329657ea9Kostya Serebryany } else if (!l->empty()) { 82deafb6bd5252c2d6ccef070ea572b04329657ea9Kostya Serebryany l->last_->next = first_; 835a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany first_ = l->first_; 845a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany size_ += l->size(); 855a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 865a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany l->clear(); 875a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 885a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 895a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany void append_back(IntrusiveList<Item> *l) { 905a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany CHECK_NE(this, l); 91312de6a1ac31d295d5ae592084e605b03661acdbDmitry Vyukov if (l->empty()) 92312de6a1ac31d295d5ae592084e605b03661acdbDmitry Vyukov return; 935a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany if (empty()) { 945a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany *this = *l; 955a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } else { 965a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany last_->next = l->first_; 975a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany last_ = l->last_; 985a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany size_ += l->size(); 995a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 1005a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany l->clear(); 1015a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 1025a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 1035a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany void CheckConsistency() { 1045a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany if (size_ == 0) { 1055a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany CHECK_EQ(first_, 0); 1065a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany CHECK_EQ(last_, 0); 1075a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } else { 1085a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany uptr count = 0; 1095a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany for (Item *i = first_; ; i = i->next) { 1105a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany count++; 1115a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany if (i == last_) break; 1125a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 1135a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany CHECK_EQ(size(), count); 1145a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany CHECK_EQ(last_->next, 0); 1155a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 1165a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 1175a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 1182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines class Iterator { 1192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines public: 1202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines explicit Iterator(IntrusiveList<Item> *list) 1212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines : list_(list), current_(list->first_) { } 1222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Item *next() { 1232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Item *ret = current_; 1242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (current_) current_ = current_->next; 1252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return ret; 1262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool hasNext() const { return current_ != 0; } 1282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines private: 1292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines IntrusiveList<Item> *list_; 1302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Item *current_; 1312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines }; 1322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1335a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// private, don't use directly. 1345a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany uptr size_; 1355a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany Item *first_; 1365a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany Item *last_; 1375a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany}; 1385a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 1395a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany} // namespace __sanitizer 1405a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 1415a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany#endif // SANITIZER_LIST_H 142