libsanitizer/sanitizer_common/sanitizer_list.h

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