1/* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2// vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
3#ident "$Id$"
4/*======
5This file is part of PerconaFT.
6
7
8Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved.
9
10 PerconaFT is free software: you can redistribute it and/or modify
11 it under the terms of the GNU General Public License, version 2,
12 as published by the Free Software Foundation.
13
14 PerconaFT is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
21
22----------------------------------------
23
24 PerconaFT is free software: you can redistribute it and/or modify
25 it under the terms of the GNU Affero General Public License, version 3,
26 as published by the Free Software Foundation.
27
28 PerconaFT is distributed in the hope that it will be useful,
29 but WITHOUT ANY WARRANTY; without even the implied warranty of
30 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 GNU Affero General Public License for more details.
32
33 You should have received a copy of the GNU Affero General Public License
34 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
35======= */
36
37#ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
38
39#pragma once
40
41#include <string.h>
42
43#include "portability/memory.h"
44#include "portability/toku_pthread.h"
45
46#include "ft/comparator.h"
47#include "ft/txn/txn.h"
48#include "locktree/keyrange.h"
49
50namespace toku {
51
52// a node in a tree with its own mutex
53// - range is the "key" of this node
54// - txnid is the single txnid associated with this node
55// - left and right children may be null
56//
57// to build a tree on top of this abstraction, the user:
58// - provides memory for a root node, initializes it via create_root()
59// - performs tree operations on the root node. memory management
60// below the root node is handled by the abstraction, not the user.
61// this pattern:
62// - guaruntees a root node always exists.
63// - does not allow for rebalances on the root node
64
65class treenode {
66public:
67
68 // every treenode function has some common requirements:
69 // - node is locked and children are never locked
70 // - node may be unlocked if no other thread has visibility
71
72 // effect: create the root node
73 void create_root(const comparator *cmp);
74
75 // effect: destroys the root node
76 void destroy_root(void);
77
78 // effect: sets the txnid and copies the given range for this node
79 void set_range_and_txnid(const keyrange &range, TXNID txnid);
80
81 // returns: true iff this node is marked as empty
82 bool is_empty(void);
83
84 // returns: true if this is the root node, denoted by a null parent
85 bool is_root(void);
86
87 // returns: true if the given range overlaps with this node's range
88 bool range_overlaps(const keyrange &range);
89
90 // effect: locks the node
91 void mutex_lock(void);
92
93 // effect: unlocks the node
94 void mutex_unlock(void);
95
96 // return: node whose child overlaps, or a child that is empty
97 // and would contain range if it existed
98 // given: if cmp_hint is non-null, then it is a precomputed
99 // comparison of this node's range to the given range.
100 treenode *find_node_with_overlapping_child(const keyrange &range,
101 const keyrange::comparison *cmp_hint);
102
103 // effect: performs an in-order traversal of the ranges that overlap the
104 // given range, calling function->fn() on each node that does
105 // requires: function signature is: bool fn(const keyrange &range, TXNID txnid)
106 // requires: fn returns true to keep iterating, false to stop iterating
107 // requires: fn does not attempt to use any ranges read out by value
108 // after removing a node with an overlapping range from the tree.
109 template <class F>
110 void traverse_overlaps(const keyrange &range, F *function);
111
112 // effect: inserts the given range and txnid into a subtree, recursively
113 // requires: range does not overlap with any node below the subtree
114 void insert(const keyrange &range, TXNID txnid);
115
116 // effect: removes the given range from the subtree
117 // requires: range exists in the subtree
118 // returns: the root of the resulting subtree
119 treenode *remove(const keyrange &range);
120
121 // effect: removes this node and all of its children, recursively
122 // requires: every node at and below this node is unlocked
123 void recursive_remove(void);
124
125private:
126
127 // the child_ptr is a light abstraction for the locking of
128 // a child and the maintenence of its depth estimate.
129
130 struct child_ptr {
131 // set the child pointer
132 void set(treenode *node);
133
134 // get and lock this child if it exists
135 treenode *get_locked(void);
136
137 treenode *ptr;
138 uint32_t depth_est;
139 };
140
141 // the balance factor at which a node is considered imbalanced
142 static const int32_t IMBALANCE_THRESHOLD = 2;
143
144 // node-level mutex
145 toku_mutex_t m_mutex;
146
147 // the range and txnid for this node. the range contains a copy
148 // of the keys originally inserted into the tree. nodes may
149 // swap ranges. but at the end of the day, when a node is
150 // destroyed, it frees the memory associated with whatever range
151 // it has at the time of destruction.
152 keyrange m_range;
153 TXNID m_txnid;
154
155 // two child pointers
156 child_ptr m_left_child;
157 child_ptr m_right_child;
158
159 // comparator for ranges
160 const comparator *m_cmp;
161
162 // marked for the root node. the root node is never free()'d
163 // when removed, but instead marked as empty.
164 bool m_is_root;
165
166 // marked for an empty node. only valid for the root.
167 bool m_is_empty;
168
169 // effect: initializes an empty node with the given comparator
170 void init(const comparator *cmp);
171
172 // requires: *parent is initialized to something meaningful.
173 // requires: subtree is non-empty
174 // returns: the leftmost child of the given subtree
175 // returns: a pointer to the parent of said child in *parent, only
176 // if this function recurred, otherwise it is untouched.
177 treenode *find_leftmost_child(treenode **parent);
178
179 // requires: *parent is initialized to something meaningful.
180 // requires: subtree is non-empty
181 // returns: the rightmost child of the given subtree
182 // returns: a pointer to the parent of said child in *parent, only
183 // if this function recurred, otherwise it is untouched.
184 treenode *find_rightmost_child(treenode **parent);
185
186 // effect: remove the root of this subtree, destroying the old root
187 // returns: the new root of the subtree
188 treenode *remove_root_of_subtree(void);
189
190 // requires: subtree is non-empty, direction is not 0
191 // returns: the child of the subtree at either the left or rightmost extreme
192 treenode *find_child_at_extreme(int direction, treenode **parent);
193
194 // effect: retrieves and possibly rebalances the left child
195 // returns: a locked left child, if it exists
196 treenode *lock_and_rebalance_left(void);
197
198 // effect: retrieves and possibly rebalances the right child
199 // returns: a locked right child, if it exists
200 treenode *lock_and_rebalance_right(void);
201
202 // returns: the estimated depth of this subtree
203 uint32_t get_depth_estimate(void) const;
204
205 // returns: true iff left subtree depth is sufficiently less than the right
206 bool left_imbalanced(int threshold) const;
207
208 // returns: true iff right subtree depth is sufficiently greater than the left
209 bool right_imbalanced(int threshold) const;
210
211 // effect: performs an O(1) rebalance, which will "heal" an imbalance by at most 1.
212 // effect: if the new root is not this node, then this node is unlocked.
213 // returns: locked node representing the new root of the rebalanced subtree
214 treenode *maybe_rebalance(void);
215
216 // returns: allocated treenode populated with a copy of the range and txnid
217 static treenode *alloc(const comparator *cmp, const keyrange &range, TXNID txnid);
218
219 // requires: node is a locked root node, or an unlocked non-root node
220 static void free(treenode *node);
221
222 // effect: swaps the range/txnid pairs for node1 and node2.
223 static void swap_in_place(treenode *node1, treenode *node2);
224
225 friend class concurrent_tree_unit_test;
226};
227
228// include the implementation here so we can use templated member functions
229#include "treenode.cc"
230
231} /* namespace toku */
232