//===-- list.h --------------------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef SCUDO_LIST_H_
#define SCUDO_LIST_H_

#include "internal_defs.h"

namespace scudo {

// Intrusive POD singly-linked list.
// An object with all zero fields should represent a valid empty list. clear()
// should be called on all non-zero-initialized objects before using.
template <class Item> struct IntrusiveList {
  friend class Iterator;

  void clear() {
    First = Last = nullptr;
    Size = 0;
  }

  bool empty() const { return Size == 0; }
  uptr size() const { return Size; }

  void push_back(Item *X) {
    if (empty()) {
      X->Next = nullptr;
      First = Last = X;
      Size = 1;
    } else {
      X->Next = nullptr;
      Last->Next = X;
      Last = X;
      Size++;
    }
  }

  void push_front(Item *X) {
    if (empty()) {
      X->Next = nullptr;
      First = Last = X;
      Size = 1;
    } else {
      X->Next = First;
      First = X;
      Size++;
    }
  }

  void pop_front() {
    DCHECK(!empty());
    First = First->Next;
    if (!First)
      Last = nullptr;
    Size--;
  }

  void extract(Item *Prev, Item *X) {
    DCHECK(!empty());
    DCHECK_NE(Prev, nullptr);
    DCHECK_NE(X, nullptr);
    DCHECK_EQ(Prev->Next, X);
    Prev->Next = X->Next;
    if (Last == X)
      Last = Prev;
    Size--;
  }

  Item *front() { return First; }
  const Item *front() const { return First; }
  Item *back() { return Last; }
  const Item *back() const { return Last; }

  void append_front(IntrusiveList<Item> *L) {
    DCHECK_NE(this, L);
    if (L->empty())
      return;
    if (empty()) {
      *this = *L;
    } else if (!L->empty()) {
      L->Last->Next = First;
      First = L->First;
      Size += L->size();
    }
    L->clear();
  }

  void append_back(IntrusiveList<Item> *L) {
    DCHECK_NE(this, L);
    if (L->empty())
      return;
    if (empty()) {
      *this = *L;
    } else {
      Last->Next = L->First;
      Last = L->Last;
      Size += L->size();
    }
    L->clear();
  }

  void checkConsistency() {
    if (Size == 0) {
      CHECK_EQ(First, nullptr);
      CHECK_EQ(Last, nullptr);
    } else {
      uptr Count = 0;
      for (Item *I = First;; I = I->Next) {
        Count++;
        if (I == Last)
          break;
      }
      CHECK_EQ(size(), Count);
      CHECK_EQ(Last->Next, nullptr);
    }
  }

  template <class ItemT> class IteratorBase {
  public:
    explicit IteratorBase(ItemT *CurrentItem) : Current(CurrentItem) {}
    IteratorBase &operator++() {
      Current = Current->Next;
      return *this;
    }
    bool operator!=(IteratorBase Other) const {
      return Current != Other.Current;
    }
    ItemT &operator*() { return *Current; }

  private:
    ItemT *Current;
  };

  typedef IteratorBase<Item> Iterator;
  typedef IteratorBase<const Item> ConstIterator;

  Iterator begin() { return Iterator(First); }
  Iterator end() { return Iterator(nullptr); }

  ConstIterator begin() const { return ConstIterator(First); }
  ConstIterator end() const { return ConstIterator(nullptr); }

private:
  uptr Size;
  Item *First;
  Item *Last;
};

} // namespace scudo

#endif // SCUDO_LIST_H_