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   Item *front() { return first_; }
  72   const Item *front() const { return first_; }
  73   Item *back() { return last_; }
  74   const Item *back() const { return last_; }
  75
  76   void append_front(IntrusiveList<Item> *l) {
  77     CHECK_NE(this, l);
  78     if (l->empty())
  79       return;
  80     if (empty()) {
  81       *this = *l;
  82     } else if (!l->empty()) {
  83       l->last_->next = first_;
  84       first_ = l->first_;
  85       size_ += l->size();
  86     }
  87     l->clear();
  88   }
  89
  90   void append_back(IntrusiveList<Item> *l) {
  91     CHECK_NE(this, l);
  92     if (l->empty())
  93       return;
  94     if (empty()) {
  95       *this = *l;
  96     } else {
  97       last_->next = l->first_;
  98       last_ = l->last_;
  99       size_ += l->size();
 100     }
 101     l->clear();
 102   }
 103
 104   void CheckConsistency() {
 105     if (size_ == 0) {
 106       CHECK_EQ(first_, 0);
 107       CHECK_EQ(last_, 0);
 108     } else {
 109       uptr count = 0;
 110       for (Item *i = first_; ; i = i->next) {
 111         count++;
 112         if (i == last_) break;
 113       }
 114       CHECK_EQ(size(), count);
 115       CHECK_EQ(last_->next, 0);
 116     }
 117   }
 118
 119   template<class ItemTy>
 120   class IteratorBase {
 121    public:
 122     explicit IteratorBase(ItemTy *current) : current_(current) {}
 123     IteratorBase &operator++() {
 124       current_ = current_->next;
 125       return *this;
 126     }
 127     bool operator!=(IteratorBase other) const {
 128       return current_ != other.current_;
 129     }
 130     ItemTy &operator*() {
 131       return *current_;
 132     }
 133    private:
 134     ItemTy *current_;
 135   };
 136
 137   typedef IteratorBase<Item> Iterator;
 138   typedef IteratorBase<const Item> ConstIterator;
 139
 140   Iterator begin() { return Iterator(first_); }
 141   Iterator end() { return Iterator(0); }
 142
 143   ConstIterator begin() const { return ConstIterator(first_); }
 144   ConstIterator end() const { return ConstIterator(0); }
 145
 146 // private, don't use directly.
 147   uptr size_;
 148   Item *first_;
 149   Item *last_;
 150 };
 151
 152 } // namespace __sanitizer
 153
 154 #endif // SANITIZER_LIST_H