ceph/src/boost/tools/quickbook/src/tree.cpp

   1 /*=============================================================================
   2 Copyright (c) 2017 Daniel James
   3
   4 Use, modification and distribution is subject to the Boost Software
   5 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6 http://www.boost.org/LICENSE_1_0.txt)
   7 =============================================================================*/
   8
   9 #include "tree.hpp"
  10 #include <cassert>
  11
  12 namespace quickbook
  13 {
  14     namespace detail
  15     {
  16         void tree_node_base::add_before(tree_base* t)
  17         {
  18             assert(
  19                 t->root_ && !t->root_->parent_ && !t->root_->prev_ &&
  20                 !t->root_->next_);
  21             t->root_->parent_ = this->parent_;
  22             t->root_->next_ = this;
  23             if (this->prev_) {
  24                 t->root_->prev_ = this->prev_;
  25                 this->prev_->next_ = t->root_;
  26             }
  27             else {
  28                 this->parent_->children_ = t->root_;
  29             }
  30             this->prev_ = t->root_;
  31             t->root_ = 0;
  32         }
  33
  34         void tree_node_base::add_after(tree_base* t)
  35         {
  36             assert(
  37                 t->root_ && !t->root_->parent_ && !t->root_->prev_ &&
  38                 !t->root_->next_);
  39             t->root_->parent_ = this->parent_;
  40             t->root_->prev_ = this;
  41             t->root_->next_ = this->next_;
  42             if (this->next_) this->next_->prev_ = t->root_;
  43             this->next_ = t->root_;
  44             t->root_ = 0;
  45         }
  46
  47         void tree_node_base::add_first_child(tree_base* t)
  48         {
  49             assert(
  50                 t->root_ && !t->root_->parent_ && !t->root_->prev_ &&
  51                 !t->root_->next_);
  52             t->root_->parent_ = this;
  53             t->root_->next_ = this->children_;
  54             if (this->children_) {
  55                 this->children_->prev_ = t->root_;
  56             }
  57             this->children_ = t->root_;
  58             t->root_ = 0;
  59         }
  60
  61         void tree_node_base::add_last_child(tree_base* t)
  62         {
  63             assert(
  64                 t->root_ && !t->root_->parent_ && !t->root_->prev_ &&
  65                 !t->root_->next_);
  66             t->root_->parent_ = this;
  67             if (!this->children_) {
  68                 this->children_ = t->root_;
  69             }
  70             else {
  71                 auto it = this->children_;
  72                 while (it->next_) {
  73                     it = it->next_;
  74                 }
  75                 t->root_->prev_ = it;
  76                 it->next_ = t->root_;
  77             }
  78             t->root_ = 0;
  79         }
  80
  81         tree_base::tree_base() : root_(0) {}
  82         tree_base::tree_base(tree_node_base* r) : root_(r) {}
  83         tree_base::~tree_base() {}
  84
  85         tree_base::tree_base(tree_base&& x) : root_(x.root_) { x.root_ = 0; }
  86
  87         tree_base& tree_base::operator=(tree_base&& x)
  88         {
  89             root_ = x.root_;
  90             x.root_ = 0;
  91             return *this;
  92         }
  93
  94         tree_node_base* tree_base::extract(tree_node_base* x)
  95         {
  96             if (!x->prev_) {
  97                 if (x->parent_) {
  98                     x->parent_->children_ = x->next_;
  99                 }
 100                 else {
 101                     assert(x == root_);
 102                     root_ = x->next_;
 103                 }
 104             }
 105             else {
 106                 x->prev_->next_ = x->next_;
 107             }
 108             if (x->next_) {
 109                 x->next_->prev_ = x->prev_;
 110             }
 111             x->parent_ = 0;
 112             x->next_ = 0;
 113             x->prev_ = 0;
 114             return x;
 115         }
 116
 117         tree_builder_base::tree_builder_base()
 118             : tree_base(), current_(0), parent_(0)
 119         {
 120         }
 121
 122         tree_builder_base::tree_builder_base(tree_builder_base&& x)
 123             : tree_base(std::move(x)), current_(x.current_), parent_(x.parent_)
 124         {
 125             x.current_ = 0;
 126             x.parent_ = 0;
 127         }
 128
 129         tree_builder_base& tree_builder_base::operator=(tree_builder_base&& x)
 130         {
 131             root_ = x.root_;
 132             current_ = x.current_;
 133             parent_ = x.parent_;
 134             x.root_ = 0;
 135             x.current_ = 0;
 136             x.parent_ = 0;
 137             return *this;
 138         }
 139
 140         // Nodes are deleted in the subclass, which knows their type.
 141         tree_builder_base::~tree_builder_base() {}
 142
 143         tree_node_base* tree_builder_base::extract(tree_node_base* x)
 144         {
 145             if (!x->prev_) {
 146                 if (x->parent_) {
 147                     x->parent_->children_ = x->next_;
 148                 }
 149                 else {
 150                     assert(x == root_);
 151                     root_ = x->next_;
 152                     parent_ = 0;
 153                     current_ = root_;
 154                 }
 155             }
 156             else {
 157                 x->prev_->next_ = x->next_;
 158             }
 159             if (x->next_) {
 160                 x->next_->prev_ = x->prev_;
 161             }
 162             x->parent_ = 0;
 163             x->next_ = 0;
 164             x->prev_ = 0;
 165             return x;
 166         }
 167
 168         tree_node_base* tree_builder_base::release()
 169         {
 170             tree_node_base* n = root_;
 171             root_ = 0;
 172             current_ = 0;
 173             parent_ = 0;
 174             return n;
 175         }
 176
 177         void tree_builder_base::add_element(tree_node_base* n)
 178         {
 179             n->parent_ = parent_;
 180             n->prev_ = current_;
 181             if (current_) {
 182                 current_->next_ = n;
 183             }
 184             else if (parent_) {
 185                 parent_->children_ = n;
 186             }
 187             else {
 188                 root_ = n;
 189             }
 190             current_ = n;
 191         }
 192
 193         void tree_builder_base::start_children()
 194         {
 195             parent_ = current_;
 196             current_ = 0;
 197         }
 198
 199         void tree_builder_base::end_children()
 200         {
 201             current_ = parent_;
 202             parent_ = current_->parent_;
 203         }
 204     }
 205 }