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 { 295a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany void clear() { 305a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany first_ = last_ = 0; 315a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany size_ = 0; 325a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 335a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 345a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany bool empty() const { return size_ == 0; } 355a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany uptr size() const { return size_; } 365a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 375a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany void push_back(Item *x) { 385a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany if (empty()) { 395a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany x->next = 0; 405a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany first_ = last_ = x; 415a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany size_ = 1; 425a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } else { 435a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany x->next = 0; 445a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany last_->next = x; 455a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany last_ = x; 465a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany size_++; 475a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 485a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 495a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 505a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany void push_front(Item *x) { 515a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany if (empty()) { 525a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany x->next = 0; 535a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany first_ = last_ = x; 545a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany size_ = 1; 555a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } else { 565a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany x->next = first_; 575a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany first_ = x; 585a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany size_++; 595a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 605a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 615a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 625a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany void pop_front() { 635a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany CHECK(!empty()); 645a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany first_ = first_->next; 655a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany if (first_ == 0) 665a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany last_ = 0; 675a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany size_--; 685a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 695a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 705a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany Item *front() { return first_; } 715a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany Item *back() { return last_; } 725a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 735a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany void append_front(IntrusiveList<Item> *l) { 745a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany CHECK_NE(this, l); 75312de6a1ac31d295d5ae592084e605b03661acdbDmitry Vyukov if (l->empty()) 76312de6a1ac31d295d5ae592084e605b03661acdbDmitry Vyukov return; 775a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany if (empty()) { 785a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany *this = *l; 79deafb6bd5252c2d6ccef070ea572b04329657ea9Kostya Serebryany } else if (!l->empty()) { 80deafb6bd5252c2d6ccef070ea572b04329657ea9Kostya Serebryany l->last_->next = first_; 815a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany first_ = l->first_; 825a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany size_ += l->size(); 835a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 845a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany l->clear(); 855a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 865a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 875a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany void append_back(IntrusiveList<Item> *l) { 885a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany CHECK_NE(this, l); 89312de6a1ac31d295d5ae592084e605b03661acdbDmitry Vyukov if (l->empty()) 90312de6a1ac31d295d5ae592084e605b03661acdbDmitry Vyukov return; 915a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany if (empty()) { 925a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany *this = *l; 935a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } else { 945a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany last_->next = l->first_; 955a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany last_ = l->last_; 965a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany size_ += l->size(); 975a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 985a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany l->clear(); 995a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 1005a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 1015a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany void CheckConsistency() { 1025a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany if (size_ == 0) { 1035a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany CHECK_EQ(first_, 0); 1045a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany CHECK_EQ(last_, 0); 1055a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } else { 1065a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany uptr count = 0; 1075a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany for (Item *i = first_; ; i = i->next) { 1085a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany count++; 1095a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany if (i == last_) break; 1105a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 1115a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany CHECK_EQ(size(), count); 1125a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany CHECK_EQ(last_->next, 0); 1135a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 1145a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany } 1155a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 1165a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// private, don't use directly. 1175a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany uptr size_; 1185a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany Item *first_; 1195a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany Item *last_; 1205a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany}; 1215a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 1225a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany} // namespace __sanitizer 1235a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany 1245a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany#endif // SANITIZER_LIST_H 125