llvm/compiler-rt/lib/scudo/standalone/list.h

//===-- 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"

// TODO: Move the helpers to a header.
namespace {
template <typename T> struct isPointer { … };

isPointer<T *>;
} // namespace

namespace scudo {

// Intrusive POD singly and doubly 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.
//
// The intrusive list requires the member `Next` (and `Prev` if doubly linked
// list)` defined in the node type. The type of `Next`/`Prev` can be a pointer
// or an index to an array. For example, if the storage of the nodes is an
// array, instead of using a pointer type, linking with an index type can save
// some space.
//
// There are two things to be noticed while using an index type,
//   1. Call init() to set up the base address of the array.
//   2. Define `EndOfListVal` as the nil of the list.

template <class T, bool LinkWithPtr = isPointer<decltype(T::Next)>::value>
class LinkOp { … };

LinkOp<T, false>;

template <class T> class IteratorBase : public LinkOp<T> { … };

template <class T> struct IntrusiveList : public LinkOp<T> { … };

template <class T> void IntrusiveList<T>::checkConsistency() const { … }

template <class T> struct SinglyLinkedList : public IntrusiveList<T> { … };

template <class T> struct DoublyLinkedList : IntrusiveList<T> { … };

} // namespace scudo

#endif // SCUDO_LIST_H_