contrib/compiler-rt/lib/sanitizer_common/sanitizer_list.h

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