15a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany//===-- sanitizer_list.h ----------------------------------------*- C++ -*-===//
25a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany//
35a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany//                     The LLVM Compiler Infrastructure
45a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany//
55a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// This file is distributed under the University of Illinois Open Source
65a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// License. See LICENSE.TXT for details.
75a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany//
85a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany//===----------------------------------------------------------------------===//
95a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany//
105a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// This file contains implementation of a list class to be used by
115a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// ThreadSanitizer, etc run-times.
125a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany//
135a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany//===----------------------------------------------------------------------===//
145a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany#ifndef SANITIZER_LIST_H
155a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany#define SANITIZER_LIST_H
165a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany
175a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany#include "sanitizer_internal_defs.h"
185a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany
195a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryanynamespace __sanitizer {
205a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany
215a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// Intrusive singly-linked list with size(), push_back(), push_front()
225a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// pop_front(), append_front() and append_back().
235a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// This class should be a POD (so that it can be put into TLS)
245a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// and an object with all zero fields should represent a valid empty list.
255a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// This class does not have a CTOR, so clear() should be called on all
265a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// non-zero-initialized objects before using.
275a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryanytemplate<class Item>
285a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryanystruct IntrusiveList {
295a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  void clear() {
305a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    first_ = last_ = 0;
315a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    size_ = 0;
325a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  }
335a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany
345a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  bool empty() const { return size_ == 0; }
355a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  uptr size() const { return size_; }
365a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany
375a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  void push_back(Item *x) {
385a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    if (empty()) {
395a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      x->next = 0;
405a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      first_ = last_ = x;
415a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      size_ = 1;
425a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    } else {
435a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      x->next = 0;
445a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      last_->next = x;
455a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      last_ = x;
465a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      size_++;
475a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    }
485a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  }
495a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany
505a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  void push_front(Item *x) {
515a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    if (empty()) {
525a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      x->next = 0;
535a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      first_ = last_ = x;
545a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      size_ = 1;
555a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    } else {
565a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      x->next = first_;
575a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      first_ = x;
585a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      size_++;
595a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    }
605a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  }
615a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany
625a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  void pop_front() {
635a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    CHECK(!empty());
645a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    first_ = first_->next;
655a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    if (first_ == 0)
665a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      last_ = 0;
675a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    size_--;
685a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  }
695a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany
705a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  Item *front() { return first_; }
715a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  Item *back() { return last_; }
725a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany
735a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  void append_front(IntrusiveList<Item> *l) {
745a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    CHECK_NE(this, l);
75312de6a1ac31d295d5ae592084e605b03661acdbDmitry Vyukov    if (l->empty())
76312de6a1ac31d295d5ae592084e605b03661acdbDmitry Vyukov      return;
775a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    if (empty()) {
785a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      *this = *l;
79deafb6bd5252c2d6ccef070ea572b04329657ea9Kostya Serebryany    } else if (!l->empty()) {
80deafb6bd5252c2d6ccef070ea572b04329657ea9Kostya Serebryany      l->last_->next = first_;
815a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      first_ = l->first_;
825a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      size_ += l->size();
835a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    }
845a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    l->clear();
855a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  }
865a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany
875a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  void append_back(IntrusiveList<Item> *l) {
885a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    CHECK_NE(this, l);
89312de6a1ac31d295d5ae592084e605b03661acdbDmitry Vyukov    if (l->empty())
90312de6a1ac31d295d5ae592084e605b03661acdbDmitry Vyukov      return;
915a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    if (empty()) {
925a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      *this = *l;
935a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    } else {
945a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      last_->next = l->first_;
955a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      last_ = l->last_;
965a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      size_ += l->size();
975a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    }
985a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    l->clear();
995a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  }
1005a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany
1015a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  void CheckConsistency() {
1025a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    if (size_ == 0) {
1035a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      CHECK_EQ(first_, 0);
1045a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      CHECK_EQ(last_, 0);
1055a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    } else {
1065a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      uptr count = 0;
1075a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      for (Item *i = first_; ; i = i->next) {
1085a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany        count++;
1095a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany        if (i == last_) break;
1105a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      }
1115a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      CHECK_EQ(size(), count);
1125a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany      CHECK_EQ(last_->next, 0);
1135a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany    }
1145a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  }
1155a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany
1165a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany// private, don't use directly.
1175a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  uptr size_;
1185a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  Item *first_;
1195a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany  Item *last_;
1205a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany};
1215a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany
1225a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany}  // namespace __sanitizer
1235a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany
1245a2327c20ab8ff8185faf51d7abc72c012a763f9Kostya Serebryany#endif  // SANITIZER_LIST_H
125