1238901Sandrew//===-- sanitizer_list.h ----------------------------------------*- C++ -*-===// 2238901Sandrew// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6238901Sandrew// 7238901Sandrew//===----------------------------------------------------------------------===// 8238901Sandrew// 9238901Sandrew// This file contains implementation of a list class to be used by 10238901Sandrew// ThreadSanitizer, etc run-times. 11238901Sandrew// 12238901Sandrew//===----------------------------------------------------------------------===// 13296417Sdim 14238901Sandrew#ifndef SANITIZER_LIST_H 15238901Sandrew#define SANITIZER_LIST_H 16238901Sandrew 17238901Sandrew#include "sanitizer_internal_defs.h" 18238901Sandrew 19238901Sandrewnamespace __sanitizer { 20238901Sandrew 21238901Sandrew// Intrusive singly-linked list with size(), push_back(), push_front() 22238901Sandrew// pop_front(), append_front() and append_back(). 23238901Sandrew// This class should be a POD (so that it can be put into TLS) 24238901Sandrew// and an object with all zero fields should represent a valid empty list. 25238901Sandrew// This class does not have a CTOR, so clear() should be called on all 26238901Sandrew// non-zero-initialized objects before using. 27238901Sandrewtemplate<class Item> 28238901Sandrewstruct IntrusiveList { 29276789Sdim friend class Iterator; 30276789Sdim 31238901Sandrew void clear() { 32296417Sdim first_ = last_ = nullptr; 33238901Sandrew size_ = 0; 34238901Sandrew } 35238901Sandrew 36238901Sandrew bool empty() const { return size_ == 0; } 37238901Sandrew uptr size() const { return size_; } 38238901Sandrew 39238901Sandrew void push_back(Item *x) { 40238901Sandrew if (empty()) { 41296417Sdim x->next = nullptr; 42238901Sandrew first_ = last_ = x; 43238901Sandrew size_ = 1; 44238901Sandrew } else { 45296417Sdim x->next = nullptr; 46238901Sandrew last_->next = x; 47238901Sandrew last_ = x; 48238901Sandrew size_++; 49238901Sandrew } 50238901Sandrew } 51238901Sandrew 52238901Sandrew void push_front(Item *x) { 53238901Sandrew if (empty()) { 54296417Sdim x->next = nullptr; 55238901Sandrew first_ = last_ = x; 56238901Sandrew size_ = 1; 57238901Sandrew } else { 58238901Sandrew x->next = first_; 59238901Sandrew first_ = x; 60238901Sandrew size_++; 61238901Sandrew } 62238901Sandrew } 63238901Sandrew 64238901Sandrew void pop_front() { 65238901Sandrew CHECK(!empty()); 66238901Sandrew first_ = first_->next; 67296417Sdim if (!first_) 68296417Sdim last_ = nullptr; 69238901Sandrew size_--; 70238901Sandrew } 71238901Sandrew 72321369Sdim void extract(Item *prev, Item *x) { 73321369Sdim CHECK(!empty()); 74321369Sdim CHECK_NE(prev, nullptr); 75321369Sdim CHECK_NE(x, nullptr); 76321369Sdim CHECK_EQ(prev->next, x); 77321369Sdim prev->next = x->next; 78321369Sdim if (last_ == x) 79321369Sdim last_ = prev; 80321369Sdim size_--; 81321369Sdim } 82321369Sdim 83238901Sandrew Item *front() { return first_; } 84309124Sdim const Item *front() const { return first_; } 85238901Sandrew Item *back() { return last_; } 86309124Sdim const Item *back() const { return last_; } 87238901Sandrew 88238901Sandrew void append_front(IntrusiveList<Item> *l) { 89238901Sandrew CHECK_NE(this, l); 90245614Sandrew if (l->empty()) 91245614Sandrew return; 92238901Sandrew if (empty()) { 93238901Sandrew *this = *l; 94238901Sandrew } else if (!l->empty()) { 95238901Sandrew l->last_->next = first_; 96238901Sandrew first_ = l->first_; 97238901Sandrew size_ += l->size(); 98238901Sandrew } 99238901Sandrew l->clear(); 100238901Sandrew } 101238901Sandrew 102238901Sandrew void append_back(IntrusiveList<Item> *l) { 103238901Sandrew CHECK_NE(this, l); 104245614Sandrew if (l->empty()) 105245614Sandrew return; 106238901Sandrew if (empty()) { 107238901Sandrew *this = *l; 108238901Sandrew } else { 109238901Sandrew last_->next = l->first_; 110238901Sandrew last_ = l->last_; 111238901Sandrew size_ += l->size(); 112238901Sandrew } 113238901Sandrew l->clear(); 114238901Sandrew } 115238901Sandrew 116238901Sandrew void CheckConsistency() { 117238901Sandrew if (size_ == 0) { 118238901Sandrew CHECK_EQ(first_, 0); 119238901Sandrew CHECK_EQ(last_, 0); 120238901Sandrew } else { 121238901Sandrew uptr count = 0; 122238901Sandrew for (Item *i = first_; ; i = i->next) { 123238901Sandrew count++; 124238901Sandrew if (i == last_) break; 125238901Sandrew } 126238901Sandrew CHECK_EQ(size(), count); 127238901Sandrew CHECK_EQ(last_->next, 0); 128238901Sandrew } 129238901Sandrew } 130238901Sandrew 131309124Sdim template<class ItemTy> 132280031Sdim class IteratorBase { 133276789Sdim public: 134309124Sdim explicit IteratorBase(ItemTy *current) : current_(current) {} 135309124Sdim IteratorBase &operator++() { 136309124Sdim current_ = current_->next; 137309124Sdim return *this; 138276789Sdim } 139309124Sdim bool operator!=(IteratorBase other) const { 140309124Sdim return current_ != other.current_; 141309124Sdim } 142309124Sdim ItemTy &operator*() { 143309124Sdim return *current_; 144309124Sdim } 145276789Sdim private: 146280031Sdim ItemTy *current_; 147276789Sdim }; 148276789Sdim 149309124Sdim typedef IteratorBase<Item> Iterator; 150309124Sdim typedef IteratorBase<const Item> ConstIterator; 151280031Sdim 152309124Sdim Iterator begin() { return Iterator(first_); } 153309124Sdim Iterator end() { return Iterator(0); } 154309124Sdim 155309124Sdim ConstIterator begin() const { return ConstIterator(first_); } 156309124Sdim ConstIterator end() const { return ConstIterator(0); } 157309124Sdim 158238901Sandrew// private, don't use directly. 159238901Sandrew uptr size_; 160238901Sandrew Item *first_; 161238901Sandrew Item *last_; 162238901Sandrew}; 163238901Sandrew 164296417Sdim} // namespace __sanitizer 165238901Sandrew 166296417Sdim#endif // SANITIZER_LIST_H 167