core/fxcrt/tree_node.h

// Copyright 2019 The PDFium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef CORE_FXCRT_TREE_NODE_H_
#define CORE_FXCRT_TREE_NODE_H_

#include <stdint.h>

#include "core/fxcrt/check.h"
#include "core/fxcrt/unowned_ptr_exclusion.h"

namespace fxcrt {

// Implements the usual DOM/XML-ish trees allowing for a variety of
// pointer types with which to connect the nodes. Public methods maintain
// the invariants of the tree.

template <typename T>
class TreeNodeBase {
 public:
  TreeNodeBase() = default;
  virtual ~TreeNodeBase() = default;

  inline T* GetParent() const { return static_cast<const T*>(this)->m_pParent; }
  inline T* GetFirstChild() const {
    return static_cast<const T*>(this)->m_pFirstChild;
  }
  inline T* GetLastChild() const {
    return static_cast<const T*>(this)->m_pLastChild;
  }
  inline T* GetNextSibling() const {
    return static_cast<const T*>(this)->m_pNextSibling;
  }
  inline T* GetPrevSibling() const {
    return static_cast<const T*>(this)->m_pPrevSibling;
  }

  bool HasChild(const T* child) const {
    return child != this && child->GetParent() == this;
  }

  T* GetNthChild(int32_t n) {
    if (n < 0)
      return nullptr;
    T* result = GetFirstChild();
    while (n-- && result) {
      result = result->GetNextSibling();
    }
    return result;
  }

  void AppendFirstChild(T* child) {
    BecomeParent(child);
    if (GetFirstChild()) {
      CHECK(GetLastChild());
      GetFirstChild()->SetPrevSibling(child);
      child->SetNextSibling(GetFirstChild());
      SetFirstChild(child);
    } else {
      CHECK(!GetLastChild());
      SetFirstChild(child);
      SetLastChild(child);
    }
  }

  void AppendLastChild(T* child) {
    BecomeParent(child);
    if (GetLastChild()) {
      CHECK(GetFirstChild());
      GetLastChild()->SetNextSibling(child);
      child->SetPrevSibling(GetLastChild());
      SetLastChild(child);
    } else {
      CHECK(!GetFirstChild());
      SetFirstChild(child);
      SetLastChild(child);
    }
  }

  void InsertBefore(T* child, T* other) {
    if (!other) {
      AppendLastChild(child);
      return;
    }
    BecomeParent(child);
    CHECK(HasChild(other));
    child->SetNextSibling(other);
    child->SetPrevSibling(other->GetPrevSibling());
    if (GetFirstChild() == other) {
      CHECK(!other->GetPrevSibling());
      SetFirstChild(child);
    } else {
      other->GetPrevSibling()->SetNextSibling(child);
    }
    other->m_pPrevSibling = child;
  }

  void InsertAfter(T* child, T* other) {
    if (!other) {
      AppendFirstChild(child);
      return;
    }
    BecomeParent(child);
    CHECK(HasChild(other));
    child->SetNextSibling(other->GetNextSibling());
    child->SetPrevSibling(other);
    if (GetLastChild() == other) {
      CHECK(!other->GetNextSibling());
      SetLastChild(child);
    } else {
      other->GetNextSibling()->SetPrevSibling(child);
    }
    other->SetNextSibling(child);
  }

  void RemoveChild(T* child) {
    CHECK(HasChild(child));
    if (GetLastChild() == child) {
      CHECK(!child->GetNextSibling());
      SetLastChild(child->GetPrevSibling());
    } else {
      child->GetNextSibling()->SetPrevSibling(child->GetPrevSibling());
    }
    if (GetFirstChild() == child) {
      CHECK(!child->GetPrevSibling());
      SetFirstChild(child->GetNextSibling());
    } else {
      child->GetPrevSibling()->SetNextSibling(child->GetNextSibling());
    }
    child->SetParent(nullptr);
    child->SetPrevSibling(nullptr);
    child->SetNextSibling(nullptr);
  }

  void RemoveAllChildren() {
    while (T* child = GetFirstChild())
      RemoveChild(child);
  }

  void RemoveSelfIfParented() {
    if (T* parent = GetParent())
      parent->RemoveChild(static_cast<T*>(this));
  }

 private:
  // These are private because they may leave the tree in an invalid state
  // until subsequent operations restore it.
  inline void SetParent(T* pParent) {
    static_cast<T*>(this)->m_pParent = pParent;
  }
  inline void SetFirstChild(T* pChild) {
    static_cast<T*>(this)->m_pFirstChild = pChild;
  }
  inline void SetLastChild(T* pChild) {
    static_cast<T*>(this)->m_pLastChild = pChild;
  }
  inline void SetNextSibling(T* pSibling) {
    static_cast<T*>(this)->m_pNextSibling = pSibling;
  }
  inline void SetPrevSibling(T* pSibling) {
    static_cast<T*>(this)->m_pPrevSibling = pSibling;
  }

  // Child left in state where sibling members need subsequent adjustment.
  void BecomeParent(T* child) {
    CHECK(child != this);  // Detect attempts at self-insertion.
    if (child->m_pParent)
      child->m_pParent->TreeNodeBase<T>::RemoveChild(child);
    child->m_pParent = static_cast<T*>(this);
    CHECK(!child->m_pNextSibling);
    CHECK(!child->m_pPrevSibling);
  }
};

// Tree connected using C-style pointers.
template <typename T>
class TreeNode : public TreeNodeBase<T> {
 public:
  TreeNode() = default;
  virtual ~TreeNode() = default;

 private:
  friend class TreeNodeBase<T>;

  UNOWNED_PTR_EXCLUSION T* m_pParent = nullptr;       // intra-tree pointer.
  UNOWNED_PTR_EXCLUSION T* m_pFirstChild = nullptr;   // intra-tree pointer.
  UNOWNED_PTR_EXCLUSION T* m_pLastChild = nullptr;    // intra-tree pointer.
  UNOWNED_PTR_EXCLUSION T* m_pNextSibling = nullptr;  // intra-tree pointer.
  UNOWNED_PTR_EXCLUSION T* m_pPrevSibling = nullptr;  // intra-tree pointer.
};

}  // namespace fxcrt

using fxcrt::TreeNode;

#endif  // CORE_FXCRT_TREE_NODE_H_