1 /* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */ 2 // vim: ft=cpp:expandtab:ts=8:sw=2:softtabstop=2: 3 #ident "$Id$" 4 /*====== 5 This file is part of PerconaFT. 6 7 8 Copyright (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 38 Licensed under the Apache License, Version 2.0 (the "License"); 39 you may not use this file except in compliance with the License. 40 You may obtain a copy of the License at 41 42 http://www.apache.org/licenses/LICENSE-2.0 43 44 Unless required by applicable law or agreed to in writing, software 45 distributed under the License is distributed on an "AS IS" BASIS, 46 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 47 See the License for the specific language governing permissions and 48 limitations under the License. 49 ======= */ 50 51 #ident \ 52 "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." 53 54 #pragma once 55 56 #include <string.h> 57 58 #include "../ft/comparator.h" 59 #include "../portability/memory.h" 60 #include "../portability/toku_pthread.h" 61 // PORT: we need LTM_STATUS 62 #include "../ft/ft-status.h" 63 #include "../portability/txn_subst.h" 64 #include "keyrange.h" 65 66 namespace toku { 67 68 // a node in a tree with its own mutex 69 // - range is the "key" of this node 70 // - txnid is the single txnid associated with this node 71 // - left and right children may be null 72 // 73 // to build a tree on top of this abstraction, the user: 74 // - provides memory for a root node, initializes it via create_root() 75 // - performs tree operations on the root node. memory management 76 // below the root node is handled by the abstraction, not the user. 77 // this pattern: 78 // - guaruntees a root node always exists. 79 // - does not allow for rebalances on the root node 80 81 class treenode { 82 public: 83 // every treenode function has some common requirements: 84 // - node is locked and children are never locked 85 // - node may be unlocked if no other thread has visibility 86 87 // effect: create the root node 88 void create_root(const comparator *cmp); 89 90 // effect: destroys the root node 91 void destroy_root(void); 92 93 // effect: sets the txnid and copies the given range for this node 94 void set_range_and_txnid(const keyrange &range, TXNID txnid, bool is_shared); 95 96 // returns: true iff this node is marked as empty 97 bool is_empty(void); 98 99 // returns: true if this is the root node, denoted by a null parent 100 bool is_root(void); 101 102 // returns: true if the given range overlaps with this node's range 103 bool range_overlaps(const keyrange &range); 104 105 // effect: locks the node 106 void mutex_lock(void); 107 108 // effect: unlocks the node 109 void mutex_unlock(void); 110 111 // return: node whose child overlaps, or a child that is empty 112 // and would contain range if it existed 113 // given: if cmp_hint is non-null, then it is a precomputed 114 // comparison of this node's range to the given range. 115 treenode *find_node_with_overlapping_child( 116 const keyrange &range, const keyrange::comparison *cmp_hint); 117 118 // effect: performs an in-order traversal of the ranges that overlap the 119 // given range, calling function->fn() on each node that does 120 // requires: function signature is: bool fn(const keyrange &range, TXNID 121 // txnid) requires: fn returns true to keep iterating, false to stop iterating 122 // requires: fn does not attempt to use any ranges read out by value 123 // after removing a node with an overlapping range from the tree. 124 template <class F> traverse_overlaps(const keyrange & range,F * function)125 void traverse_overlaps(const keyrange &range, F *function) { 126 keyrange::comparison c = range.compare(*m_cmp, m_range); 127 if (c == keyrange::comparison::EQUALS) { 128 // Doesn't matter if fn wants to keep going, there 129 // is nothing left, so return. 130 function->fn(m_range, m_txnid, m_is_shared, m_owners); 131 return; 132 } 133 134 treenode *left = m_left_child.get_locked(); 135 if (left) { 136 if (c != keyrange::comparison::GREATER_THAN) { 137 // Target range is less than this node, or it overlaps this 138 // node. There may be something on the left. 139 left->traverse_overlaps(range, function); 140 } 141 left->mutex_unlock(); 142 } 143 144 if (c == keyrange::comparison::OVERLAPS) { 145 bool keep_going = function->fn(m_range, m_txnid, m_is_shared, m_owners); 146 if (!keep_going) { 147 return; 148 } 149 } 150 151 treenode *right = m_right_child.get_locked(); 152 if (right) { 153 if (c != keyrange::comparison::LESS_THAN) { 154 // Target range is greater than this node, or it overlaps this 155 // node. There may be something on the right. 156 right->traverse_overlaps(range, function); 157 } 158 right->mutex_unlock(); 159 } 160 } 161 162 // effect: inserts the given range and txnid into a subtree, recursively 163 // requires: range does not overlap with any node below the subtree 164 bool insert(const keyrange &range, TXNID txnid, bool is_shared); 165 166 // effect: removes the given range from the subtree 167 // requires: range exists in the subtree 168 // returns: the root of the resulting subtree 169 treenode *remove(const keyrange &range, TXNID txnid); 170 171 // effect: removes this node and all of its children, recursively 172 // requires: every node at and below this node is unlocked 173 void recursive_remove(void); 174 175 private: 176 // the child_ptr is a light abstraction for the locking of 177 // a child and the maintenence of its depth estimate. 178 179 struct child_ptr { 180 // set the child pointer 181 void set(treenode *node); 182 183 // get and lock this child if it exists 184 treenode *get_locked(void); 185 186 treenode *ptr; 187 uint32_t depth_est; 188 }; 189 190 // the balance factor at which a node is considered imbalanced 191 static const int32_t IMBALANCE_THRESHOLD = 2; 192 193 // node-level mutex 194 toku_mutex_t m_mutex; 195 196 // the range and txnid for this node. the range contains a copy 197 // of the keys originally inserted into the tree. nodes may 198 // swap ranges. but at the end of the day, when a node is 199 // destroyed, it frees the memory associated with whatever range 200 // it has at the time of destruction. 201 keyrange m_range; 202 203 void remove_shared_owner(TXNID txnid); 204 has_multiple_owners()205 bool has_multiple_owners() { return (m_txnid == TXNID_SHARED); } 206 207 private: 208 // Owner transaction id. 209 // A value of TXNID_SHARED means this node has multiple owners 210 TXNID m_txnid; 211 212 // If true, this lock is a non-exclusive lock, and it can have either 213 // one or several owners. 214 bool m_is_shared; 215 216 // List of the owners, or nullptr if there's just one owner. 217 TxnidVector *m_owners; 218 219 // two child pointers 220 child_ptr m_left_child; 221 child_ptr m_right_child; 222 223 // comparator for ranges 224 // psergey-todo: Is there any sense to store the comparator in each tree 225 // node? 226 const comparator *m_cmp; 227 228 // marked for the root node. the root node is never free()'d 229 // when removed, but instead marked as empty. 230 bool m_is_root; 231 232 // marked for an empty node. only valid for the root. 233 bool m_is_empty; 234 235 // effect: initializes an empty node with the given comparator 236 void init(const comparator *cmp); 237 238 // requires: this is a shared node (m_is_shared==true) 239 // effect: another transaction is added as an owner. 240 // returns: true <=> added another owner 241 // false <=> this transaction is already an owner 242 bool add_shared_owner(TXNID txnid); 243 244 // requires: *parent is initialized to something meaningful. 245 // requires: subtree is non-empty 246 // returns: the leftmost child of the given subtree 247 // returns: a pointer to the parent of said child in *parent, only 248 // if this function recurred, otherwise it is untouched. 249 treenode *find_leftmost_child(treenode **parent); 250 251 // requires: *parent is initialized to something meaningful. 252 // requires: subtree is non-empty 253 // returns: the rightmost child of the given subtree 254 // returns: a pointer to the parent of said child in *parent, only 255 // if this function recurred, otherwise it is untouched. 256 treenode *find_rightmost_child(treenode **parent); 257 258 // effect: remove the root of this subtree, destroying the old root 259 // returns: the new root of the subtree 260 treenode *remove_root_of_subtree(void); 261 262 // requires: subtree is non-empty, direction is not 0 263 // returns: the child of the subtree at either the left or rightmost extreme 264 treenode *find_child_at_extreme(int direction, treenode **parent); 265 266 // effect: retrieves and possibly rebalances the left child 267 // returns: a locked left child, if it exists 268 treenode *lock_and_rebalance_left(void); 269 270 // effect: retrieves and possibly rebalances the right child 271 // returns: a locked right child, if it exists 272 treenode *lock_and_rebalance_right(void); 273 274 // returns: the estimated depth of this subtree 275 uint32_t get_depth_estimate(void) const; 276 277 // returns: true iff left subtree depth is sufficiently less than the right 278 bool left_imbalanced(int threshold) const; 279 280 // returns: true iff right subtree depth is sufficiently greater than the left 281 bool right_imbalanced(int threshold) const; 282 283 // effect: performs an O(1) rebalance, which will "heal" an imbalance by at 284 // most 1. effect: if the new root is not this node, then this node is 285 // unlocked. returns: locked node representing the new root of the rebalanced 286 // subtree 287 treenode *maybe_rebalance(void); 288 289 // returns: allocated treenode populated with a copy of the range and txnid 290 static treenode *alloc(const comparator *cmp, const keyrange &range, 291 TXNID txnid, bool is_shared); 292 293 // requires: node is a locked root node, or an unlocked non-root node 294 static void free(treenode *node); 295 296 // effect: swaps the range/txnid pairs for node1 and node2. 297 static void swap_in_place(treenode *node1, treenode *node2); 298 299 friend class concurrent_tree_unit_test; 300 }; 301 302 } /* namespace toku */ 303