Home | History | Annotate | Line # | Download | only in sanitizer_common 
      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
    168