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 /*====== 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 "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." 52 53 #pragma once 54 55 #include <string.h> 56 57 #include "portability/memory.h" 58 #include "portability/toku_pthread.h" 59 60 #include "ft/comparator.h" 61 #include "ft/txn/txn.h" 62 #include "locktree/keyrange.h" 63 64 namespace toku { 65 66 // a node in a tree with its own mutex 67 // - range is the "key" of this node 68 // - txnid is the single txnid associated with this node 69 // - left and right children may be null 70 // 71 // to build a tree on top of this abstraction, the user: 72 // - provides memory for a root node, initializes it via create_root() 73 // - performs tree operations on the root node. memory management 74 // below the root node is handled by the abstraction, not the user. 75 // this pattern: 76 // - guaruntees a root node always exists. 77 // - does not allow for rebalances on the root node 78 79 class treenode { 80 public: 81 82 // every treenode function has some common requirements: 83 // - node is locked and children are never locked 84 // - node may be unlocked if no other thread has visibility 85 86 // effect: create the root node 87 void create_root(const comparator *cmp); 88 89 // effect: destroys the root node 90 void destroy_root(void); 91 92 // effect: sets the txnid and copies the given range for this node 93 void set_range_and_txnid(const keyrange &range, TXNID txnid); 94 95 // returns: true iff this node is marked as empty 96 bool is_empty(void); 97 98 // returns: true if this is the root node, denoted by a null parent 99 bool is_root(void); 100 101 // returns: true if the given range overlaps with this node's range 102 bool range_overlaps(const keyrange &range); 103 104 // effect: locks the node 105 void mutex_lock(void); 106 107 // effect: unlocks the node 108 void mutex_unlock(void); 109 110 // return: node whose child overlaps, or a child that is empty 111 // and would contain range if it existed 112 // given: if cmp_hint is non-null, then it is a precomputed 113 // comparison of this node's range to the given range. 114 treenode *find_node_with_overlapping_child(const keyrange &range, 115 const keyrange::comparison *cmp_hint); 116 117 // effect: performs an in-order traversal of the ranges that overlap the 118 // given range, calling function->fn() on each node that does 119 // requires: function signature is: bool fn(const keyrange &range, TXNID txnid) 120 // requires: fn returns true to keep iterating, false to stop iterating 121 // requires: fn does not attempt to use any ranges read out by value 122 // after removing a node with an overlapping range from the tree. 123 template <class F> 124 void traverse_overlaps(const keyrange &range, F *function); 125 126 // effect: inserts the given range and txnid into a subtree, recursively 127 // requires: range does not overlap with any node below the subtree 128 void insert(const keyrange &range, TXNID txnid); 129 130 // effect: removes the given range from the subtree 131 // requires: range exists in the subtree 132 // returns: the root of the resulting subtree 133 treenode *remove(const keyrange &range); 134 135 // effect: removes this node and all of its children, recursively 136 // requires: every node at and below this node is unlocked 137 void recursive_remove(void); 138 139 private: 140 141 // the child_ptr is a light abstraction for the locking of 142 // a child and the maintenence of its depth estimate. 143 144 struct child_ptr { 145 // set the child pointer 146 void set(treenode *node); 147 148 // get and lock this child if it exists 149 treenode *get_locked(void); 150 151 treenode *ptr; 152 uint32_t depth_est; 153 }; 154 155 // the balance factor at which a node is considered imbalanced 156 static const int32_t IMBALANCE_THRESHOLD = 2; 157 158 // node-level mutex 159 toku_mutex_t m_mutex; 160 161 // the range and txnid for this node. the range contains a copy 162 // of the keys originally inserted into the tree. nodes may 163 // swap ranges. but at the end of the day, when a node is 164 // destroyed, it frees the memory associated with whatever range 165 // it has at the time of destruction. 166 keyrange m_range; 167 TXNID m_txnid; 168 169 // two child pointers 170 child_ptr m_left_child; 171 child_ptr m_right_child; 172 173 // comparator for ranges 174 const comparator *m_cmp; 175 176 // marked for the root node. the root node is never free()'d 177 // when removed, but instead marked as empty. 178 bool m_is_root; 179 180 // marked for an empty node. only valid for the root. 181 bool m_is_empty; 182 183 // effect: initializes an empty node with the given comparator 184 void init(const comparator *cmp); 185 186 // requires: *parent is initialized to something meaningful. 187 // requires: subtree is non-empty 188 // returns: the leftmost child of the given subtree 189 // returns: a pointer to the parent of said child in *parent, only 190 // if this function recurred, otherwise it is untouched. 191 treenode *find_leftmost_child(treenode **parent); 192 193 // requires: *parent is initialized to something meaningful. 194 // requires: subtree is non-empty 195 // returns: the rightmost child of the given subtree 196 // returns: a pointer to the parent of said child in *parent, only 197 // if this function recurred, otherwise it is untouched. 198 treenode *find_rightmost_child(treenode **parent); 199 200 // effect: remove the root of this subtree, destroying the old root 201 // returns: the new root of the subtree 202 treenode *remove_root_of_subtree(void); 203 204 // requires: subtree is non-empty, direction is not 0 205 // returns: the child of the subtree at either the left or rightmost extreme 206 treenode *find_child_at_extreme(int direction, treenode **parent); 207 208 // effect: retrieves and possibly rebalances the left child 209 // returns: a locked left child, if it exists 210 treenode *lock_and_rebalance_left(void); 211 212 // effect: retrieves and possibly rebalances the right child 213 // returns: a locked right child, if it exists 214 treenode *lock_and_rebalance_right(void); 215 216 // returns: the estimated depth of this subtree 217 uint32_t get_depth_estimate(void) const; 218 219 // returns: true iff left subtree depth is sufficiently less than the right 220 bool left_imbalanced(int threshold) const; 221 222 // returns: true iff right subtree depth is sufficiently greater than the left 223 bool right_imbalanced(int threshold) const; 224 225 // effect: performs an O(1) rebalance, which will "heal" an imbalance by at most 1. 226 // effect: if the new root is not this node, then this node is unlocked. 227 // returns: locked node representing the new root of the rebalanced subtree 228 treenode *maybe_rebalance(void); 229 230 // returns: allocated treenode populated with a copy of the range and txnid 231 static treenode *alloc(const comparator *cmp, const keyrange &range, TXNID txnid); 232 233 // requires: node is a locked root node, or an unlocked non-root node 234 static void free(treenode *node); 235 236 // effect: swaps the range/txnid pairs for node1 and node2. 237 static void swap_in_place(treenode *node1, treenode *node2); 238 239 friend class concurrent_tree_unit_test; 240 }; 241 242 // include the implementation here so we can use templated member functions 243 #include "treenode.cc" 244 245 } /* namespace toku */ 246