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