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 #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