third_party/blink/renderer/platform/wtf/tree_node.h

/*
 * Copyright (C) 2013 Google Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TREE_NODE_H_
#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TREE_NODE_H_

#include "third_party/blink/renderer/platform/wtf/assertions.h"

namespace WTF {

//
// TreeNode is generic, ContainerNode-like linked tree data structure.
// There are a few notable difference between TreeNode and Node:
//
//  * Each TreeNode node is NOT ref counted. The user have to retain its
//    lifetime somehow.
//    FIXME: lifetime management could be parameterized so that ref counted
//    implementations can be used.
//  * It checks invalid input. The callers have to ensure that given
//    parameter is sound.
//  * There is no branch-leaf difference. Every node can be a parent of other
//    node.
//
// FIXME: oilpan: Trace tree node edges to ensure we don't have dangling
// pointers.
// As it is used in HTMLImport it is safe since they all die together.
template <class T>
class TreeNode {
 public:
  typedef T NodeType;

  TreeNode()
      : next_(nullptr),
        previous_(nullptr),
        parent_(nullptr),
        first_child_(nullptr),
        last_child_(nullptr) {}

  NodeType* Next() const { return next_; }
  NodeType* Previous() const { return previous_; }
  NodeType* Parent() const { return parent_; }
  NodeType* FirstChild() const { return first_child_; }
  NodeType* LastChild() const { return last_child_; }
  NodeType* Here() const {
    return static_cast<NodeType*>(const_cast<TreeNode*>(this));
  }

  bool Orphan() const {
    return !parent_ && !next_ && !previous_ && !first_child_ && !last_child_;
  }
  bool HasChildren() const { return first_child_; }

  void InsertBefore(NodeType* new_child, NodeType* ref_child) {
    DCHECK(!new_child->Parent());
    DCHECK(!new_child->Next());
    DCHECK(!new_child->Previous());

    DCHECK(!ref_child || this == ref_child->Parent());

    if (!ref_child) {
      AppendChild(new_child);
      return;
    }

    NodeType* new_previous = ref_child->Previous();
    new_child->parent_ = Here();
    new_child->next_ = ref_child;
    new_child->previous_ = new_previous;
    ref_child->previous_ = new_child;
    if (new_previous)
      new_previous->next_ = new_child;
    else
      first_child_ = new_child;
  }

  void AppendChild(NodeType* child) {
    DCHECK(!child->Parent());
    DCHECK(!child->Next());
    DCHECK(!child->Previous());

    child->parent_ = Here();

    if (!last_child_) {
      DCHECK(!first_child_);
      last_child_ = first_child_ = child;
      return;
    }

    DCHECK(!last_child_->next_);
    NodeType* old_last = last_child_;
    last_child_ = child;

    child->previous_ = old_last;
    old_last->next_ = child;
  }

  NodeType* RemoveChild(NodeType* child) {
    DCHECK_EQ(child->Parent(), this);

    if (first_child_ == child)
      first_child_ = child->Next();
    if (last_child_ == child)
      last_child_ = child->Previous();

    NodeType* old_next = child->Next();
    NodeType* old_previous = child->Previous();
    child->parent_ = child->next_ = child->previous_ = nullptr;

    if (old_next)
      old_next->previous_ = old_previous;
    if (old_previous)
      old_previous->next_ = old_next;

    return child;
  }

  void TakeChildrenFrom(NodeType* old_parent) {
    DCHECK_NE(old_parent, this);
    while (old_parent->HasChildren()) {
      NodeType* child = old_parent->FirstChild();
      old_parent->RemoveChild(child);
      this->AppendChild(child);
    }
  }

 private:
  NodeType* next_;
  NodeType* previous_;
  NodeType* parent_;
  NodeType* first_child_;
  NodeType* last_child_;
};

template <class T>
inline typename TreeNode<T>::NodeType* TraverseNext(
    const TreeNode<T>* current,
    const TreeNode<T>* stay_within = nullptr) {
  if (typename TreeNode<T>::NodeType* next = current->FirstChild())
    return next;
  if (current == stay_within)
    return nullptr;
  if (typename TreeNode<T>::NodeType* next = current->Next())
    return next;
  for (typename TreeNode<T>::NodeType* parent = current->Parent(); parent;
       parent = parent->Parent()) {
    if (parent == stay_within)
      return nullptr;
    if (typename TreeNode<T>::NodeType* next = parent->Next())
      return next;
  }

  return nullptr;
}

template <class T>
inline typename TreeNode<T>::NodeType* TraverseFirstPostOrder(
    const TreeNode<T>* current) {
  typename TreeNode<T>::NodeType* first = current->Here();
  while (first->FirstChild())
    first = first->FirstChild();
  return first;
}

template <class T>
inline typename TreeNode<T>::NodeType* TraverseNextPostOrder(
    const TreeNode<T>* current,
    const TreeNode<T>* stay_within = nullptr) {
  if (current == stay_within)
    return nullptr;

  typename TreeNode<T>::NodeType* next = current->Next();
  if (!next)
    return current->Parent();
  while (next->FirstChild())
    next = next->FirstChild();
  return next;
}

}  // namespace WTF

using WTF::TreeNode;
using WTF::TraverseNext;
using WTF::TraverseNextPostOrder;

#endif