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 (empty()) {
  74       *this = *l;
  75     } else if (!l->empty()) {
  76       l->last_->next = first_;
  77       first_ = l->first_;
  78       size_ += l->size();
  79     }
  80     l->clear();
  81   }
  82
  83   void append_back(IntrusiveList<Item> *l) {
  84     CHECK_NE(this, l);
  85     if (empty()) {
  86       *this = *l;
  87     } else {
  88       last_->next = l->first_;
  89       last_ = l->last_;
  90       size_ += l->size();
  91     }
  92     l->clear();
  93   }
  94
  95   void CheckConsistency() {
  96     if (size_ == 0) {
  97       CHECK_EQ(first_, 0);
  98       CHECK_EQ(last_, 0);
  99     } else {
 100       uptr count = 0;
 101       for (Item *i = first_; ; i = i->next) {
 102         count++;
 103         if (i == last_) break;
 104       }
 105       CHECK_EQ(size(), count);
 106       CHECK_EQ(last_->next, 0);
 107     }
 108   }
 109
 110 // private, don't use directly.
 111   uptr size_;
 112   Item *first_;
 113   Item *last_;
 114 };
 115
 116 }  // namespace __sanitizer
 117
 118 #endif  // SANITIZER_LIST_H