Home | History | Annotate | Download | only in sanitizer_common 
      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
    125