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   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 // private, don't use directly.
 117   uptr size_;
 118   Item *first_;
 119   Item *last_;
 120 };
 121
 122 }  // namespace __sanitizer
 123
 124 #endif  // SANITIZER_LIST_H