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   void clear() {
  28     first_ = last_ = 0;
  29     size_ = 0;
  30   }
  31
  32   bool empty() const { return size_ == 0; }
  33   uptr size() const { return size_; }
  34
  35   void push_back(Item *x) {
  36     if (empty()) {
  37       x->next = 0;
  38       first_ = last_ = x;
  39       size_ = 1;
  40     } else {
  41       x->next = 0;
  42       last_->next = x;
  43       last_ = x;
  44       size_++;
  45     }
  46   }
  47
  48   void push_front(Item *x) {
  49     if (empty()) {
  50       x->next = 0;
  51       first_ = last_ = x;
  52       size_ = 1;
  53     } else {
  54       x->next = first_;
  55       first_ = x;
  56       size_++;
  57     }
  58   }
  59
  60   void pop_front() {
  61     CHECK(!empty());
  62     first_ = first_->next;
  63     if (first_ == 0)
  64       last_ = 0;
  65     size_--;
  66   }
  67
  68   Item *front() { return first_; }
  69   Item *back() { return last_; }
  70
  71   void append_front(IntrusiveList<Item> *l) {
  72     CHECK_NE(this, l);
  73     if (l->empty())
  74       return;
  75     if (empty()) {
  76       *this = *l;
  77     } else if (!l->empty()) {
  78       l->last_->next = first_;
  79       first_ = l->first_;
  80       size_ += l->size();
  81     }
  82     l->clear();
  83   }
  84
  85   void append_back(IntrusiveList<Item> *l) {
  86     CHECK_NE(this, l);
  87     if (l->empty())
  88       return;
  89     if (empty()) {
  90       *this = *l;
  91     } else {
  92       last_->next = l->first_;
  93       last_ = l->last_;
  94       size_ += l->size();
  95     }
  96     l->clear();
  97   }
  98
  99   void CheckConsistency() {
 100     if (size_ == 0) {
 101       CHECK_EQ(first_, 0);
 102       CHECK_EQ(last_, 0);
 103     } else {
 104       uptr count = 0;
 105       for (Item *i = first_; ; i = i->next) {
 106         count++;
 107         if (i == last_) break;
 108       }
 109       CHECK_EQ(size(), count);
 110       CHECK_EQ(last_->next, 0);
 111     }
 112   }
 113
 114 // private, don't use directly.
 115   uptr size_;
 116   Item *first_;
 117   Item *last_;
 118 };
 119
 120 }  // namespace __sanitizer
 121
 122 #endif  // SANITIZER_LIST_H