libsanitizer/sanitizer_common/sanitizer_list.h

   1 //===-- sanitizer_list.h ----------------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file contains implementation of a list class to be used by
  10 // ThreadSanitizer, etc run-times.
  11 //
  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_ = nullptr;
  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 = nullptr;
  42       first_ = last_ = x;
  43       size_ = 1;
  44     } else {
  45       x->next = nullptr;
  46       last_->next = x;
  47       last_ = x;
  48       size_++;
  49     }
  50   }
  51
  52   void push_front(Item *x) {
  53     if (empty()) {
  54       x->next = nullptr;
  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_)
  68       last_ = nullptr;
  69     size_--;
  70   }
  71
  72   void extract(Item *prev, Item *x) {
  73     CHECK(!empty());
  74     CHECK_NE(prev, nullptr);
  75     CHECK_NE(x, nullptr);
  76     CHECK_EQ(prev->next, x);
  77     prev->next = x->next;
  78     if (last_ == x)
  79       last_ = prev;
  80     size_--;
  81   }
  82
  83   Item *front() { return first_; }
  84   const Item *front() const { return first_; }
  85   Item *back() { return last_; }
  86   const Item *back() const { return last_; }
  87
  88   void append_front(IntrusiveList<Item> *l) {
  89     CHECK_NE(this, l);
  90     if (l->empty())
  91       return;
  92     if (empty()) {
  93       *this = *l;
  94     } else if (!l->empty()) {
  95       l->last_->next = first_;
  96       first_ = l->first_;
  97       size_ += l->size();
  98     }
  99     l->clear();
 100   }
 101
 102   void append_back(IntrusiveList<Item> *l) {
 103     CHECK_NE(this, l);
 104     if (l->empty())
 105       return;
 106     if (empty()) {
 107       *this = *l;
 108     } else {
 109       last_->next = l->first_;
 110       last_ = l->last_;
 111       size_ += l->size();
 112     }
 113     l->clear();
 114   }
 115
 116   void CheckConsistency() {
 117     if (size_ == 0) {
 118       CHECK_EQ(first_, 0);
 119       CHECK_EQ(last_, 0);
 120     } else {
 121       uptr count = 0;
 122       for (Item *i = first_; ; i = i->next) {
 123         count++;
 124         if (i == last_) break;
 125       }
 126       CHECK_EQ(size(), count);
 127       CHECK_EQ(last_->next, 0);
 128     }
 129   }
 130
 131   template<class ItemTy>
 132   class IteratorBase {
 133    public:
 134     explicit IteratorBase(ItemTy *current) : current_(current) {}
 135     IteratorBase &operator++() {
 136       current_ = current_->next;
 137       return *this;
 138     }
 139     bool operator!=(IteratorBase other) const {
 140       return current_ != other.current_;
 141     }
 142     ItemTy &operator*() {
 143       return *current_;
 144     }
 145    private:
 146     ItemTy *current_;
 147   };
 148
 149   typedef IteratorBase<Item> Iterator;
 150   typedef IteratorBase<const Item> ConstIterator;
 151
 152   Iterator begin() { return Iterator(first_); }
 153   Iterator end() { return Iterator(0); }
 154
 155   ConstIterator begin() const { return ConstIterator(first_); }
 156   ConstIterator end() const { return ConstIterator(0); }
 157
 158 // private, don't use directly.
 159   uptr size_;
 160   Item *first_;
 161   Item *last_;
 162 };
 163
 164 } // namespace __sanitizer
 165
 166 #endif // SANITIZER_LIST_H