167 lines · c
1//===-- sanitizer_list.h ----------------------------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file contains implementation of a list class to be used by10// ThreadSanitizer, etc run-times.11//12//===----------------------------------------------------------------------===//13 14#ifndef SANITIZER_LIST_H15#define SANITIZER_LIST_H16 17#include "sanitizer_internal_defs.h"18 19namespace __sanitizer {20 21// Intrusive singly-linked list with size(), push_back(), push_front()22// pop_front(), append_front() and append_back().23// This class should be a POD (so that it can be put into TLS)24// and an object with all zero fields should represent a valid empty list.25// This class does not have a CTOR, so clear() should be called on all26// non-zero-initialized objects before using.27template<class Item>28struct IntrusiveList {29 friend class Iterator;30 31 void clear() {32 first_ = last_ = nullptr;33 size_ = 0;34 }35 36 bool empty() const { return size_ == 0; }37 uptr size() const { return size_; }38 39 void push_back(Item *x) {40 if (empty()) {41 x->next = nullptr;42 first_ = last_ = x;43 size_ = 1;44 } else {45 x->next = nullptr;46 last_->next = x;47 last_ = x;48 size_++;49 }50 }51 52 void push_front(Item *x) {53 if (empty()) {54 x->next = nullptr;55 first_ = last_ = x;56 size_ = 1;57 } else {58 x->next = first_;59 first_ = x;60 size_++;61 }62 }63 64 void pop_front() {65 CHECK(!empty());66 first_ = first_->next;67 if (!first_)68 last_ = nullptr;69 size_--;70 }71 72 void extract(Item *prev, Item *x) {73 CHECK(!empty());74 CHECK_NE(prev, nullptr);75 CHECK_NE(x, nullptr);76 CHECK_EQ(prev->next, x);77 prev->next = x->next;78 if (last_ == x)79 last_ = prev;80 size_--;81 }82 83 Item *front() { return first_; }84 const Item *front() const { return first_; }85 Item *back() { return last_; }86 const Item *back() const { return last_; }87 88 void append_front(IntrusiveList<Item> *l) {89 CHECK_NE(this, l);90 if (l->empty())91 return;92 if (empty()) {93 *this = *l;94 } else if (!l->empty()) {95 l->last_->next = first_;96 first_ = l->first_;97 size_ += l->size();98 }99 l->clear();100 }101 102 void append_back(IntrusiveList<Item> *l) {103 CHECK_NE(this, l);104 if (l->empty())105 return;106 if (empty()) {107 *this = *l;108 } else {109 last_->next = l->first_;110 last_ = l->last_;111 size_ += l->size();112 }113 l->clear();114 }115 116 void CheckConsistency() {117 if (size_ == 0) {118 CHECK_EQ(first_, 0);119 CHECK_EQ(last_, 0);120 } else {121 uptr count = 0;122 for (Item *i = first_; ; i = i->next) {123 count++;124 if (i == last_) break;125 }126 CHECK_EQ(size(), count);127 CHECK_EQ(last_->next, 0);128 }129 }130 131 template<class ItemTy>132 class IteratorBase {133 public:134 explicit IteratorBase(ItemTy *current) : current_(current) {}135 IteratorBase &operator++() {136 current_ = current_->next;137 return *this;138 }139 bool operator!=(IteratorBase other) const {140 return current_ != other.current_;141 }142 ItemTy &operator*() {143 return *current_;144 }145 private:146 ItemTy *current_;147 };148 149 typedef IteratorBase<Item> Iterator;150 typedef IteratorBase<const Item> ConstIterator;151 152 Iterator begin() { return Iterator(first_); }153 Iterator end() { return Iterator(0); }154 155 ConstIterator begin() const { return ConstIterator(first_); }156 ConstIterator end() const { return ConstIterator(0); }157 158// private, don't use directly.159 uptr size_;160 Item *first_;161 Item *last_;162};163 164} // namespace __sanitizer165 166#endif // SANITIZER_LIST_H167