xref: /trafficserver/include/tscore/RbTree.h (revision 4f8cb034)
1 /** @file
2 
3   @section license License
4 
5   Licensed to the Apache Software Foundation (ASF) under one
6   or more contributor license agreements.  See the NOTICE file
7   distributed with this work for additional information
8   regarding copyright ownership.  The ASF licenses this file
9   to you under the Apache License, Version 2.0 (the
10   "License"); you may not use this file except in compliance
11   with the License.  You may obtain a copy of the License at
12 
13       http://www.apache.org/licenses/LICENSE-2.0
14 
15   Unless required by applicable law or agreed to in writing, software
16   distributed under the License is distributed on an "AS IS" BASIS,
17   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18   See the License for the specific language governing permissions and
19   limitations under the License.
20  */
21 
22 #pragma once
23 
24 namespace ts
25 {
26 namespace detail
27 {
28   /** A node in a red/black tree.
29 
30       This class provides only the basic tree operations. The client
31       must provide the search and decision logic. This enables this
32       class to be a base class for templated nodes with much less code
33       duplication.
34   */
35   struct RBNode {
36     typedef RBNode self; ///< self reference type
37 
38     /// Node colors
39     typedef enum {
40       RED,
41       BLACK,
42     } Color;
43 
44     /// Directional constants
45     typedef enum {
46       NONE,
47       LEFT,
48       RIGHT,
49     } Direction;
50 
51     /// Get a child by direction.
52     /// @return The child in the direction @a d if it exists,
53     /// @c NULL if not.
54     self *getChild(Direction d //!< The direction of the desired child
55     ) const;
56 
57     /** Determine which child a node is
58         @return @c LEFT if @a n is the left child,
59         @c RIGHT if @a n is the right child,
60         @c NONE if @a n is not a child
61     */
62     Direction
getChildDirectionts::detail::RBNode63     getChildDirection(self *const &n //!< The presumed child node
64     ) const
65     {
66       return (n == _left) ? LEFT : (n == _right) ? RIGHT : NONE;
67     }
68 
69     /** Get the parent node.
70         @return A Node* to the parent node or a @c nil Node* if no parent.
71     */
72     self *
getParentts::detail::RBNode73     getParent() const
74     {
75       return const_cast<self *>(_parent);
76     }
77 
78     /// @return The color of the node.
79     Color
getColorts::detail::RBNode80     getColor() const
81     {
82       return _color;
83     }
84 
85     self *
leftmostDescendantts::detail::RBNode86     leftmostDescendant() const
87     {
88       const self *n = this;
89       while (n->_left)
90         n = n->_left;
91 
92       return const_cast<self *>(n);
93     }
94 
95     /** Reverse a direction
96         @return @c LEFT if @a d is @c RIGHT, @c RIGHT if @a d is @c LEFT,
97         @c NONE otherwise.
98     */
99     Direction
flipts::detail::RBNode100     flip(Direction d)
101     {
102       return LEFT == d ? RIGHT : RIGHT == d ? LEFT : NONE;
103     }
104 
105     /** Perform internal validation checks.
106         @return 0 on failure, black height of the tree on success.
107     */
108     int validate();
109 
110     /// Default constructor.
RBNodets::detail::RBNode111     RBNode() {}
112     /// Destructor (force virtual).
~RBNodets::detail::RBNode113     virtual ~RBNode() {}
114     /** Rotate the subtree rooted at this node.
115         The node is rotated in to the position of one of its children.
116         Which child is determined by the direction parameter @a d. The
117         child in the other direction becomes the new root of the subtree.
118 
119         If the parent pointer is set, then the child pointer of the original
120         parent is updated so that the tree is left in a consistent state.
121 
122         @note If there is no child in the other direction, the rotation
123         fails and the original node is returned. It is @b not required
124         that a child exist in the direction specified by @a d.
125 
126         @return The new root node for the subtree.
127     */
128     self *rotate(Direction d //!< The direction to rotate
129     );
130 
131     /** Set the child node in direction @a d to @a n.
132         The @a d child is set to the node @a n. The pointers in this
133         node and @a n are set correctly. This can only be called if
134         there is no child node already present.
135 
136         @return @a n.
137     */
138     self *setChild(self *n,    //!< The node to set as the child
139                    Direction d //!< The direction of the child
140     );
141 
142     /** Remove this node from the tree.
143         The tree is rebalanced after removal.
144         @return The new root node.
145     */
146     self *remove();
147 
148     void
clearChildts::detail::RBNode149     clearChild(Direction dir)
150     {
151       if (LEFT == dir)
152         _left = nullptr;
153       else if (RIGHT == dir)
154         _right = nullptr;
155     }
156 
157     /** @name Subclass hook methods */
158     //@{
159     /** Structural change notification.
160         This method is called if the structure of the subtree rooted at
161         this node was changed.
162 
163         This is intended a hook. The base method is empty so that subclasses
164         are not required to override.
165     */
166     virtual void
structureFixupts::detail::RBNode167     structureFixup()
168     {
169     }
170 
171     /** Called from @c validate to perform any additional validation checks.
172         Clients should chain this if they wish to perform additional checks.
173         @return @c true if the validation is successful, @c false otherwise.
174         @note The base method simply returns @c true.
175     */
176     virtual bool
structureValidatets::detail::RBNode177     structureValidate()
178     {
179       return true;
180     }
181     //@}
182 
183     /** Replace this node with another node.
184         This is presumed to be non-order modifying so the next reference
185         is @b not updated.
186     */
187     void replaceWith(self *n //!< Node to put in place of this node.
188     );
189 
190     //! Rebalance the tree starting at this node
191     /** The tree is rebalanced so that all of the invariants are
192         true. The (potentially new) root of the tree is returned.
193 
194         @return The root node of the tree after the rebalance.
195     */
196     self *rebalanceAfterInsert();
197 
198     /** Rebalance the tree after a deletion.
199         Called on the lowest modified node.
200         @return The new root of the tree.
201     */
202     self *rebalanceAfterRemove(Color c,    //!< The color of the removed node.
203                                Direction d //!< Direction of removed node from parent
204     );
205 
206     //! Invoke @c structure_fixup() on this node and all of its ancestors.
207     self *rippleStructureFixup();
208 
209     Color _color  = RED;     ///< node color
210     self *_parent = nullptr; ///< parent node (needed for rotations)
211     self *_left   = nullptr; ///< left child
212     self *_right  = nullptr; ///< right child
213     self *_next   = nullptr; ///< Next node.
214     self *_prev   = nullptr; ///< Previous node.
215   };
216 
217 } /* namespace detail */
218 
219 } /* namespace ts */
220