Home | History | Annotate | 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 #ifndef SANITIZER_LIST_H
     15 #define SANITIZER_LIST_H
     16 
     17 #include "sanitizer_internal_defs.h"
     18 
     19 namespace __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.
     27 template<class Item>
     28 struct IntrusiveList {
     29   friend class Iterator;
     30 
     31   void clear() {
     32     first_ = last_ = 0;
     33     size_ = 0;
     34   }
     35 
     36   bool empty() const { return size_ == 0; }
     37   uptr size() const { return size_; }
     38 
     39   void push_back(Item *x) {
     40     if (empty()) {
     41       x->next = 0;
     42       first_ = last_ = x;
     43       size_ = 1;
     44     } else {
     45       x->next = 0;
     46       last_->next = x;
     47       last_ = x;
     48       size_++;
     49     }
     50   }
     51 
     52   void push_front(Item *x) {
     53     if (empty()) {
     54       x->next = 0;
     55       first_ = last_ = x;
     56       size_ = 1;
     57     } else {
     58       x->next = first_;
     59       first_ = x;
     60       size_++;
     61     }
     62   }
     63 
     64   void pop_front() {
     65     CHECK(!empty());
     66     first_ = first_->next;
     67     if (first_ == 0)
     68       last_ = 0;
     69     size_--;
     70   }
     71 
     72   Item *front() { return first_; }
     73   Item *back() { return last_; }
     74 
     75   void append_front(IntrusiveList<Item> *l) {
     76     CHECK_NE(this, l);
     77     if (l->empty())
     78       return;
     79     if (empty()) {
     80       *this = *l;
     81     } else if (!l->empty()) {
     82       l->last_->next = first_;
     83       first_ = l->first_;
     84       size_ += l->size();
     85     }
     86     l->clear();
     87   }
     88 
     89   void append_back(IntrusiveList<Item> *l) {
     90     CHECK_NE(this, l);
     91     if (l->empty())
     92       return;
     93     if (empty()) {
     94       *this = *l;
     95     } else {
     96       last_->next = l->first_;
     97       last_ = l->last_;
     98       size_ += l->size();
     99     }
    100     l->clear();
    101   }
    102 
    103   void CheckConsistency() {
    104     if (size_ == 0) {
    105       CHECK_EQ(first_, 0);
    106       CHECK_EQ(last_, 0);
    107     } else {
    108       uptr count = 0;
    109       for (Item *i = first_; ; i = i->next) {
    110         count++;
    111         if (i == last_) break;
    112       }
    113       CHECK_EQ(size(), count);
    114       CHECK_EQ(last_->next, 0);
    115     }
    116   }
    117 
    118   class Iterator {
    119    public:
    120     explicit Iterator(IntrusiveList<Item> *list)
    121         : list_(list), current_(list->first_) { }
    122     Item *next() {
    123       Item *ret = current_;
    124       if (current_) current_ = current_->next;
    125       return ret;
    126     }
    127     bool hasNext() const { return current_ != 0; }
    128    private:
    129     IntrusiveList<Item> *list_;
    130     Item *current_;
    131   };
    132 
    133 // private, don't use directly.
    134   uptr size_;
    135   Item *first_;
    136   Item *last_;
    137 };
    138 
    139 }  // namespace __sanitizer
    140 
    141 #endif  // SANITIZER_LIST_H
    142