1//===-- sanitizer_list.h ----------------------------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file contains implementation of a list class to be used by 11// ThreadSanitizer, etc run-times. 12// 13//===----------------------------------------------------------------------===// 14#ifndef SANITIZER_LIST_H 15#define SANITIZER_LIST_H 16 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 all 26// non-zero-initialized objects before using. 27template<class Item> 28struct IntrusiveList { 29 void clear() { 30 first_ = last_ = 0; 31 size_ = 0; 32 } 33 34 bool empty() const { return size_ == 0; } 35 uptr size() const { return size_; } 36 37 void push_back(Item *x) { 38 if (empty()) { 39 x->next = 0; 40 first_ = last_ = x; 41 size_ = 1; 42 } else { 43 x->next = 0; 44 last_->next = x; 45 last_ = x; 46 size_++; 47 } 48 } 49 50 void push_front(Item *x) { 51 if (empty()) { 52 x->next = 0; 53 first_ = last_ = x; 54 size_ = 1; 55 } else { 56 x->next = first_; 57 first_ = x; 58 size_++; 59 } 60 } 61 62 void pop_front() { 63 CHECK(!empty()); 64 first_ = first_->next; 65 if (first_ == 0) 66 last_ = 0; 67 size_--; 68 } 69 70 Item *front() { return first_; } 71 Item *back() { return last_; } 72 73 void append_front(IntrusiveList<Item> *l) { 74 CHECK_NE(this, l); 75 if (empty()) { 76 *this = *l; 77 } else if (!l->empty()) { 78 l->last_->next = first_; 79 first_ = l->first_; 80 size_ += l->size(); 81 } 82 l->clear(); 83 } 84 85 void append_back(IntrusiveList<Item> *l) { 86 CHECK_NE(this, l); 87 if (empty()) { 88 *this = *l; 89 } else { 90 last_->next = l->first_; 91 last_ = l->last_; 92 size_ += l->size(); 93 } 94 l->clear(); 95 } 96 97 void CheckConsistency() { 98 if (size_ == 0) { 99 CHECK_EQ(first_, 0); 100 CHECK_EQ(last_, 0); 101 } else { 102 uptr count = 0; 103 for (Item *i = first_; ; i = i->next) { 104 count++; 105 if (i == last_) break; 106 } 107 CHECK_EQ(size(), count); 108 CHECK_EQ(last_->next, 0); 109 } 110 } 111 112// private, don't use directly. 113 uptr size_; 114 Item *first_; 115 Item *last_; 116}; 117 118} // namespace __sanitizer 119 120#endif // SANITIZER_LIST_H 121